Cantor–Bendixson ranks of effectively closed sets in admissible recursion theory

Definition 2.1.

Let X be a topological space, A ⊆ X closed. A limit point of A is an x ∈ A such that for any open U containing x, A ∩ ( U ∖ { x } ) is nonempty. The Cantor–Bendixson derivative A ′ of A is the set of limit points of A.

The iterated Cantor–Bendixson derivatives of A are defined inductively:

A ( 0 ) = A

A ( α + 1 ) = ( A ( α ) ) ′

For α a limit ordinal, A ( α ) = ⋂ β < α A ( β ) .

The Cantor–Bendixson rank of A is the least ordinal α so that A ( α ) = A ( α + 1 ) , in which case A ( α ) is called the perfect core of A. The Cantor–Bendixson rank of a particular x ∈ A is the least ordinal α so that x ∉ A ( α + 1 ) , or ∞ if there is no such α.

Definition 2.2.

For σ ∈ 2 < ω 1 , let [ σ ] denote the subset of 2 ω 1 consisting of all extensions of σ to length ω 1 .

A subset X ⊂ 2 ω 1 is a basic open set if it is ⋃ σ ∈ Y [ σ ] for some set Y ⊆ 2 α and some countable ordinal α.

X is closed if it is the intersection of basic open sets, and open if it is the union of basic open sets. Sets which are both open and closed are called clopen.

Given the topology defined by Definition 2.2, the terms defined in Definition 2.1 can be given more convenient interpretations. Notably, a limit point of X is the limit of an ω 1 -sequence of distinct members of X in the lexicographic sense; i.e., a point x such that x ( i ) = lim α < ω 1 y α ( i ) for a sequence of y α ∈ X and each i < ω 1 .

The sets of particular interest in this paper are Π 1 0 -classes, so it is necessary to define the notion of a tree in 2 < ω 1 and the related notion of embedding.

Definition 2.3.

A (binary) tree is a subset T of 2 < ω 1 that is closed under initial segments. A path through T is a point x ∈ 2 ω 1 so that x ↾ α ∈ T for all countable ordinals α; [ T ] is the set of all paths through T.

Definition 2.4.

An embedding of a tree T into a tree U is an injective map f : T → U such that f ( σ ) ≼ f ( τ ) iff σ ≼ τ .

The following is a direct analogue to the countable case.

Proposition 2.5.

Closed sets in 2 ω 1 may be represented by trees in 2 < ω 1 , in the following sense.

A set X ⊆ 2 ω 1 is closed if and only if X = [ T ] for some tree T ⊆ 2 < ω 1 .

A set X ⊆ 2 ω 1 is perfect if and only if X = [ T ] for some tree T ⊆ 2 < ω 1 such that every σ ∈ T is an initial segment of at least two distinct points in X.

If X ⊆ 2 ω 1 is closed and T ⊆ 2 < ω 1 is a tree so that X = [ T ] , then the Cantor–Bendixson derivative of X is [ T ˆ ] , where T ˆ ⊆ T is the set of all σ ∈ T that are initial segments of at least two distinct points in X.

Proof.

(i) Let X ⊆ 2 ω 1 be closed. Then X = ⋂ α Y α , where the Y α are clopen sets. By taking intersections, it is clear that without loss of generality we can suppose that Y α = ⋃ σ ∈ Z [ σ ] for some Z ⊂ 2 α . Then taking T = { τ ∈ 2 < ω 1 ∣ ( ∀ α < | τ | ) τ ↾ α ∈ Y α } is sufficient. Conversely, given a tree T ⊆ 2 < ω 1 , the set [ T ] is ⋂ α ⋃ σ ∈ T ∩ 2 α [ σ ] , which is closed.

(ii) Let X ⊆ 2 ω 1 be perfect, and let T be a tree so that X = [ T ] , as required by (i). Suppose that σ ∈ T is an initial segment of some point x ∈ X . Since X is perfect, x is a limit point of X; in particular, there must be another point of X within the clopen neighborhood [ σ ] . So there exists a y ∈ X , y ≠ x , with σ ≺ y ; therefore at least two paths of T pass through σ. Let T ˆ ⊆ T be { σ ∈ T ∣ ( ∃ x ∈ [ T ] ) σ ≺ x } . Then every σ ∈ T ˆ is an initial segment of at least two distinct points in X, and X = [ T ˆ ] .

Conversely, suppose T ⊆ 2 < ω 1 is such that every σ ∈ T is an initial segment of at least two distinct points in [ T ] . Let x ∈ [ T ] . Define a sequence ⟨ y α ∣ α < ω 1 ⟩ by taking y α to be the y ≠ x extending x ↾ α for each α. This sequence is a sequence in [ T ] witnessing that x is a limit point of [ T ] ; therefore, [ T ] is perfect.

(iii) Let X ⊆ 2 ω 1 be closed, T ⊆ 2 < ω 1 a tree so that X = [ T ] . Let X ′ be the Cantor–Bendixson derivative of X, and let T ˆ be as described in the proposition.

Fix x ∈ X ′ , and let σ ∈ T be an arbitrary initial segment of x. Because x is a limit point of X, there exists a y ≠ x in X ∩ [ σ ] ; that is, a y ∈ [ T ] which extends σ and is not x. Therefore σ ∈ T ˆ . So X ′ ⊆ [ T ˆ ] .

Fix x ∈ [ T ˆ ] . We may define the same sequence ⟨ y α ∣ α < ω 1 ⟩ as in the proof of (ii), witnessing that x is a limit point of X and is hence in X ′ . So [ T ˆ ] ⊆ X ′ . This completes the proof. □

Observe that, unlike the countable case, it is not easy (that is, not obviously computable, arithmetic, hyperarithmetic, or even Δ 1 1 ) to construct the Cantor–Bendixson derivative of a Π 1 0 -class in the sense of ω 1 -recursion; detecting whether a node of the representing tree should be removed appears to require determining whether it has a path passing through it, which is a Σ 1 1 -complete task. Thus it is not clear that the rank of a Π 1 0 -class need even be Δ 1 1 ; for a definition of a Δ 1 1 ordinal, see Definition 2.12.

It is worth noting that this is not the only possible way to define a topology on 2 ω 1 . Another natural possibility would be to restrict the union in the definition of basic clopen sets to countable sets only; in this case, we must replace tree in the second definition with tree of countable width. For the purposes of this paper, we will not consider this alternative definition.

In order to pursue an answer to the question of which ω 1 -Turing degrees can appear as the degrees of points with a given Cantor–Bendixson rank, and of which ordinals can appear as the Cantor–Bendixson rank of a computable tree, we require the following theorem.

Theorem 2.6.

Suppose that X is a path of Cantor–Bendixson rank zero in some computable tree; further suppose that there is a tree T computable in X with Cantor–Bendixson rank α and empty perfect core. Then there is a computable tree T ˆ that likewise has Cantor–Bendixson rank α and empty perfect core. Furthermore, the rank-α paths in T ˆ are exactly the joins of the rank-α paths in T with X.

Throughout the argument, some nodes of the tree under construction will be designated as roots of Aronszajn trees; a copy of a particular computable Aronszajn tree will be built by stages above that point, until that designation is removed. The effect is that if a particular element of the tree is designated an Aronszajn root, and never loses that designation, there will be no branch of the tree passing through that element; nevertheless, if the designation is lifted at any countable stage, there will remain extensions of that element the membership of which has not yet been decided.

We require the following lemmas.

Lemma 2.7.

There exists a computable tree U ⊆ 2 < ω 1 such that | U ∩ 2 α | ⩾ 2 for every 0 < α < ω 1 , and for any y ∈ 2 ω 1 there exists an α such that y ↾ α ∉ U .

Proof.

Let 0 α denote the string consisting of a length-α sequence of zeros, and let U be the set of strings σ ⌢ 0 α ∈ 2 < ω 1 such that σ ∈ 2 ⩽ ω and σ ∉ L α . Certainly U is a computable tree. Because L α is countable for any countable α, the set of σ ∈ 2 ω with σ ⌢ 0 α ∉ U is always countable; therefore, U ∩ 2 α is uncountable.

Let y ∈ 2 ω 1 . Because y ∈ L by the set-theoretic assumption 2 ω 1 ⊆ L , y ↾ ω ∈ L ω 1 , and therefore y ↾ ω ∈ L α for some countable α. Then, by construction, no extension of y ↾ ω of length ω + α is in U, and in particular y ↾ ( ω + α ) ∉ U . □

In the constructions to follow, a computable Aronszajn tree – a tree as in Lemma 2.7 with the additional requirement that | U ∩ 2 α | ⩽ ℵ 0 for all α – may be used instead, if a particularly narrow tree is desired; this approach was used extensively in [4]. However, for the present usage, Lemma 2.7 in the form above is sufficient.

Throughout the constructions to follow, it will be useful to be able to ensure that a string σ is never “abandoned” by having all extensions omitted from a tree, without requiring the existence of an unbounded branch passing through σ. In order to achieve this, such nodes will sometimes be designated Aronszajn roots. To an Aronszajn root σ is always attached a partial isomorphism F σ mapping the extensions of σ currently in the tree into the standard tree U. Once σ designated an Aronszajn root, at each successive stage of construction, strings will be enumerated into the tree extending σ so that F σ may be extended to cover one further level of U. This process has the effect of ensuring that each such string always has an extension whose membership in the tree is not yet decided, without risking the creation of a path passing through that string.

Lemma 2.8.

Let T , U ⊆ 2 < ω 1 be trees, and suppose that there exists an embedding f : T → U such that every path through U is the f-image of a path through T. Then the Cantor–Bendixson rank of any path through U is the same as the Cantor–Bendixson rank of the f-preimage of that path. As a consequence, T and U have the same Cantor–Bendixson rank.

Proof.

By Proposition 2.5, it suffices to show that T ˆ and U ˆ , defined in that Proposition as the sets of strings belonging to at least two paths in each tree respectively, are likewise related by f; that is, that f : T ˆ → U ˆ is an embedding, and that every path through U ˆ is the f-image of a path through T ˆ .

To see that f embeds T ˆ into U ˆ , consider σ ∈ T ˆ . Then there exist two paths Y 0 , Y 1 ∈ [ T ] such that σ ≺ Y 0 and σ ≺ Y 1 . By hypothesis, the f-images of Y 0 and Y 1 are distinct paths in U which must extend f ( σ ) ; therefore, σ ∈ U ˆ .

Let X ∈ [ U ˆ ] . Since U ˆ ⊆ U , X ∈ [ U ] . By hypothesis, X is therefore the f-image of a path Y through T. For each σ ≺ Y , f ( σ ) has at least one path Z ≠ X passing through it in U; the f-preimage of Z is then a path through T extending σ and not equal to Y. Every initial segment of Y extends to at least two distinct paths through T; therefore, Y ∈ [ T ˆ ] . □

Proof of Theorem 2.6.

Given a partial function f : 2 < ω 1 → 2 , the tree given by f is the subset of 2 < ω 1 given by { σ : ( ∀ τ ≼ σ ) f ( τ ) = 1 } . The tree given by f is partial if f is a partial function and there exists some σ such that f ( τ ) = 1 for every proper initial segment τ of σ, but σ itself is not in the domain of f.

We begin by defining, for a Turing functional Γ and a set Y ⊆ ω 1 , a tree T ( Γ , Y ) with the following properties:

There is a Y-computable embedding from the tree given by Γ Y (as a subset of 2 < ω 1 ) into T ( Γ , Y ) that induces a Cantor–Bendixson rank-preserving bijection on the branches of each;

T ( Γ , Y ) ∩ 2 α is uniformly computable in an index for Γ and Y ↾ α ; and

T ( Γ , Y ) is total regardless of the totality of Γ Y , and is unbounded if the tree given by Γ Y is partial.

We construct T ( Γ , Y ) as follows, together with the embedding F : Γ Y → T ( Γ , Y ) required by the first condition. For ease of notation, we will not distinguish between Γ Y and the tree given by Γ Y except where the context is not clear. We approximate Γ Y at stage α by Γ Y ↾ α ; recall that, by convention, computations with use exceeding α are considered to diverge.

Begin construction by mapping the root of Γ Y to the root of T ( Γ , Y ) , and designate the root of T ( Γ , Y ) as the root of an Aronszajn tree. At stage α, extend T ( Γ , Y ) to continue growing an Aronszajn tree above each existing Aronszajn root. If σ ⌢ i enters Γ Y and F ( σ ) was previously designated an Aronszajn root, remove that designation; set F ( σ ⌢ i ) to be some maximal-length extension of F ( σ ) in T ( Γ , Y ) . Fix another maximal-length extension of F ( σ ) , and designate both as Aronszajn roots. At limit stages, if σ of limit length is a limit of strings currently in the range of F, include σ in T ( Γ , Y ) and designate it an Aronszajn root.

This completes the construction of T ( Γ , Y ) . For σ ∈ 2 < ω 1 , let T ( Γ , σ ) = T ( Γ , Y ) ∩ 2 < | σ | for any Y extending σ; note that this is independent of the choice of Y, because the elements of T ( Γ , Y ) ↾ 2 < β are determined by Y ↾ β for any β.

Finally, let X be as named in the statement, and let Γ be a functional so that T = Γ X . Let U be a computable tree in which the unique path is X. Let T ˆ = { σ ⊕ τ ∣ σ ∈ U ∧ τ ∈ T ( Γ , σ ) ∧ | σ | = | τ | } . Claim 2.9.

F is a Y-computable embedding of Γ Y into T ( Γ , Y ) , and every path in T ( Γ , Y ) is the image of a path in Γ Y .

Proof.

That F is Y-computable and is an embedding of the trees is immediate from the construction.

Let Z ∈ 2 ω 1 be a path in T ( Γ , Y ) . If the range of F includes unboundedly many initial segments of Z, then those initial segments form a path in Γ Y with image Z. Suppose instead that the range of F does not include unboundedly many initial segments of Z; then there exists some minimal initial segment σ ≺ Z so that no initial segment of Z extending σ is in the range of F. By construction, whether σ is of limit or successor length, when it was included it was designated an Aronszajn root. Nodes extending Aronszajn roots are added only to extend the isomorphism with the standard tree U of Lemma 2.7; since U has no uncountable branches, this contradicts the existence of Z. □

Claim 2.10.

T ( Γ , Y ) has the desired properties.

Proof.

That F : Γ Y → T ( Γ , Y ) induces a Cantor–Bendixson rank-preserving bijection on the branches holds simply because it is an embedding of the trees and every path in T ( Γ , Y ) is the image of a path in Γ Y , by Claim 2.9.

The construction uses only Y ↾ α to construct T ( Γ , Y ) ∩ 2 α , so the second condition is met.

If Γ Y is total, T ( Γ , Y ) will clearly be total. If the tree given by Γ Y is partial, then for the earliest σ on which Γ Y is not defined, F ( σ ) or its predecessor will be the root of an Aronszajn subtree; thus T ( Γ , Y ) will be both total and unbounded. □

Claim 2.11.

T ˆ has the desired properties.

Proof.

Every path through T ˆ is a join with X, by construction. Let Y = X ⊕ Z be a path through T ˆ . Z, by construction, is a path through T ( Γ , X ) . We therefore have a map G : T ( Γ , X ) → T ˆ which induces a bijection on paths, and which is Cantor–Bendixson rank-preserving by Lemma 2.8. By construction, we have an embedding F : T → T ( Γ , X ) which induces a similar bijection. F preserves Turing degree, while G takes Z to X ⊕ Z . The composition G ∘ F then induces a bijection of paths in T with paths in T ˆ , so that the image of each path Z is Turing-equivalent to X ⊕ Z . □

This completes the proof of Theorem 2.6. □

In order to more completely charactize the class of ordinals which can appear as the rank of a Π 1 0 -class, we require an additional definition.

Definition 2.12.

Recall that a Σ 1 1 formula is a formula of the form ∃ A φ , where φ is first-order, and A ranges over subsets of the universe; likewise, a Π 1 1 formula is a formula of the form ∀ A φ .

We say that an ordinal α is Δ 1 1 -definable over L ω 1 if there exists a subset of L ω 1 which is the diagram of an ordering of order-type α, and is definable in L ω 1 both by a Σ 1 1 formula with parameters from L ω 1 and by a Π 1 1 formula with parameters from L ω 1 .

This diagram is called a Δ 1 1 -presentation of α, and the ordered pair consisting of the indices for the Σ 1 1 and Π 1 1 formulas (with parameters) is called a Δ 1 1 -code for α.

Using Theorem 2.6, we may show the following

Theorem 1.3.

Let α be any ordinal that is Δ 1 1 -definable over L ω 1 . Then there is a Π 1 0 -class with Cantor–Bendixson rank α.

To complete the proof, we will first require a generalization of the notion of a computable ordinal to the setting of ω 1 . The following is a natural generalization of Kleene’s O [6] to the uncountable case, suggested by Greenberg and Turetsky (personal communication, 2014).

Definition 2.13.

Define O ⊆ L ω 1 as the minimal set satisfying the following conditions, together with a rank function | · | : O → ω 2 and an ordering < O on O .

0 ∈ O , and | 0 | = 0 .

If a ∈ O , then a + : = ⟨ 0 , a ⟩ ∈ O . | a + | = | a | + 1 , and c < O a + if and only if c < O a or c = a .

If ⟨ a n ∣ n < ω ⟩ is an < O -increasing ω-sequence of elements of O , then a : = ⟨ 1 , ⟨ a n ∣ n < ω ⟩ ⟩ ∈ O . | a | = sup n | a n | , and c < O a if and only if c < O a n for some n.

If ⟨ a α ∣ α < ω 1 ⟩ is a computable < O -increasing ω 1 -sequence of elements of O and e ∈ ω 1 is such that a α = Φ e ( α ) for each α, then a : = ⟨ 2 , e ⟩ ∈ O . | a | = sup α | a α | , and c < O a if and only if c < O a α for some α < ω 1 .

For an ordinal α, a ∈ O is a notation for α if | a | = α . We say α is computable if there exists a notation for α.

Most of the basic results regarding Kleene’s O hold without modification in the uncountable case, with the notable exception that O as defined here is Π 1 0 rather than Π 1 1 -complete.

In general, we will not distinguish between an ordinal and a notation for that ordinal except when ambiguity would arise. Lemma 2.14.

If β is an ordinal computable from X, then X computes a tree (uniformly in a notation for β) which has Cantor–Bendixson rank β. Furthermore, this tree may be chosen so that every path in this tree is computable from X, and the tree has exactly one path of rank β.

Proof.

We construct, by effective transfinite recursion on a notation b for β, an X-computable tree U b with Cantor–Bendixson rank β. There are four cases.

If b = 0 , let U 0 = { 0 γ ∣ γ < ω 1 } .

Suppose b = ⟨ 0 , a ⟩ for an ordinal notation a. In this case, let U b be the closure of { 0 δ ⌢ 1 ⌢ σ ∣ σ ∈ U a ∧ δ < ω 1 } under taking initial segments.

Suppose b = ⟨ 1 , ⟨ a n ∣ n < ω ⟩ ⟩ , for a countable sequence of ordinal notations a n . In this case, let U b be the closure under initial segments of { 0 ω δ + n ⌢ 1 ⌢ σ ∣ σ ∈ U a n ∧ δ < ω 1 } .

Suppose b = ⟨ 2 , e ⟩ . In this case, let U b be the closure under initial segments of { 0 Φ e X ( i ) ⌢ 1 ⌢ σ ∣ σ ∈ U Φ e X ( i ) ∧ i < ω 1 }

As typical in a classical argument by effective transfinite recursion, suppose that U b is undefined for some b ∈ O X . Then by the well-foundedness of the ordering on O X , there is some < O -minimal such b; however, by construction, if U a is defined for all a < O b , U b is also defined, contradicting the choice of b. □

Proof of Theorem 1.3.

Let A be a Δ 1 1 presentation of α. By Theorem 1.23 in [4], there exists a computable tree T such that T has exactly one path X, and that path computes A. The theorem in question in fact supplies a tree of countable width, but this is not needed for this proof.

By Lemma 2.14, X computes a tree U α with Cantor–Bendixson rank α. By Theorem 2.6, there therefore exists a computable tree T ˆ with Cantor–Bendixson rank α. □

3. Ranks of degrees

The previous section discussed only the Cantor–Bendixson ranks of Π 1 0 -classes considered as whole sets, without regard for the rank or Turing degree of the individual points. We now direct our focus towards this relationship between Cantor–Bendixson rank and Turing degree, concluding with a proof of Theorem 1.4.

The following definition is essentially laid out by Shore [9], though our focus on the particular ordinal ω 1 allows a simplified phrasing:

This completes the proof of Theorem 3.3. □

There is a Δ 3 0 degree which can be represented with Cantor–Bendixson rank 1, but does not compute any noncomputable element of rank zero.

We say a Turing degree a has proper Cantor–Bendixson rank α if there is a Π 1 0 -class in which some representative of a has rank α but none in which a representative of a has rank < α .

Let α be any computable ordinal. Then there is a Δ 3 0 degree, uniformly in a notation for α, which has proper Cantor–Bendixson rank α.

We prove the theorem by constructing, given (a notation for) α, a tree T with a distinguished path X, so that X will be of the desired degree and will have Cantor–Bendixson rank α in [ T ] . The approach will be to ensure that whenever X is equivalent to a path through a computable tree T ˆ , there will be a series of embeddings of trees of increasing Cantor–Bendixson rank into the neighborhoods around that point in T ˆ ensuring that the point has Cantor–Bendixson rank at least α.

Given α, fix a computable sequence of computable ordinals ⟨ α β ∣ β < ω 1 ⟩ so that α = lim sup β → ω 1 ( α β + 1 ) ; note that the constant sequence α β = γ will suffice in the event that α = γ + 1 . Likewise, note that the sequence α beta ω + n = γ n will suffice if α has countable cofinality and α = lim sup n → ω γ n .

Fix computable trees T α β corresponding to α β by Lemma 2.14, so that every path through T α β is computable, and T α β has a unique path of rank α β and none of higher rank. Fix also an effective enumeration ⟨ T e ⟩ e < ω 1 of computable trees so that every computable tree appears in this enumeration at a set of indices on which α e is cofinal in α.

We prove the theorem by an unbounded injury argument on a tree of strategies. Let Λ = ω 1 + 1 , endowed with the order ω 1 < 0 < 1 < ⋯ . We operate on the tree of outcomes Λ < ω 1 ; the strategies assigned to each level pursue requirements as follows.

If Φ e X ∈ [ T i ] , then one of the following holds.

We assign limit levels to the least R e , i requirement not yet assigned.

Any strategy η ∈ Λ < ω 1 has an anchor point σ ∈ T ; this is a string so that every string added to T on behalf of η or any strategy extending η will extend σ. The true path is the leftmost element P ∈ Λ ω 1 so that the current sequence of outcomes is unboundedly often an initial segment of P; X will be the limit of the anchor points of the strategies along P, and hence will be Δ 3 0 . That this true path exists is not entirely obvious, and will be shown in Claim 3.13.

When a strategy η directs construction along a string σ, it requires that all strategies extending η choose anchor points that extend σ.

When initialized at stage s, an strategy η assigned to requirement R e , i takes its anchor to be a string σ with length s extending the anchors and directions of construction of all higher-priority strategies, such that every proper initial segment of σ is already in T, and enumerates σ and its immediate successors σ ⌢ 0 and σ ⌢ 1 into the tree. The strategy begins in outcome ω 1 , and directs construction along σ ⌢ 0 , designating σ ⌢ 1 an Aronszajn root.

Throughout, η maintains a partial embedding F : T α e → T ; when initialized, η takes F ( ⟨ ⟩ ) to be σ ⌢ 1 .

At each stage s, η searches through the first s strings in the standard effective enumeration of 2 < ω 1 for a string τ ∈ T α e such that every proper initial segment of τ is already in the domain of F and one of the following conditions hold:

τ is in the domain of F, but τ ⌢ 0 and τ ⌢ 1 are in T α e − dom F ; or

If the τ found is an instance of case (i), then η searches for a pair of strings ρ 0 and ρ 1 within the first s strings in the standard effective enumeration of 2 < ω 1 such that ρ i ≻ F ( τ ) and Φ e ρ 0 and Φ e ρ 1 are incomparable members of T i . If such a pair is found, η extends F to include the definitions F ( τ ⌢ i ) = ρ i for each i; otherwise, if η is in outcome ω 1 , η is said to require attention.

If the τ found is instead an instance of case (ii), then η searches for a string ρ within the first s strings in the standard effective enumeration of 2 < ω 1 such that ρ ≻ sup θ ≺ τ F ( θ ) and Φ e ρ is a proper extension of sup θ ≺ τ Φ e F ( θ ) in T i . If such a ρ is found, η extends F to include the definition F ( τ ) = ρ ; otherwise, if η is in outcome ω 1 , η is said to require attention.

When η is in outcome ω 1 , requires attention, and is permitted to act, it changes its outcome to the first countable outcome it has not yet used, and directs construction along the string τ in question.

While η is not in outcome ω 1 , it is only said to require attention if the condition which caused it to leave outcome ω 1 ceases to hold – i.e., if the necessary strings ρ 0 and ρ 1 are found in case (i), or if the necessary string ρ is found in case (ii). When permitted to act, η changes its outcome back to ω 1 and directs construction back along σ ⌢ 0 .

At a limit stage s, the outcome of η is taken to be ω 1 if the outcome of η has been ω 1 cofinally often before stage s. Otherwise, by construction, there was some stage t < s after which η remained at a fixed countable outcome α; let the outcome of η at stage s likewise be α.

Finally, let X be the limit of the sequence of anchor strings of the strategies falling along the leftmost path P in Λ < ω 1 that was visited unboundedly often during the construction.

This completes the construction; it remains to verify that the tree T and the path X are as desired. Claim 3.12.

Every requirement is satisfied.

Let R e , i be a requirement, η a strategy along the true path pursuing that requirement; by induction, suppose that all higher-priority requirements are satisfied.

Suppose that Φ e X ∈ [ T i ] (otherwise the satisfaction of R e , i is vacuous). If η never requires attention, or if it returns to outcome ω 1 unboundedly often, then at every stage during which it is active and in outcome ω 1 it will be able to add to the embedding F it is building. Then, in the limit, the map τ ↦ Φ e F ( τ ) will be a (computable) embedding of T α e into T i , and R e , i will be satisfied.

If, on the other hand, η eventually requires attention and does not re-enter outcome ω 1 afterwards, then there are two possibilities.

The first possibility is that η left outcome ω 1 because it encountered a τ in case (i) above and never found appropriate strings ρ 0 and ρ 1 . Then for every ρ 0 , ρ 1 ≻ F ( τ ) , Φ e ρ 0 and Φ e ρ 1 are either comparable strings or not members of T i . Because the strategy ensures that X ≻ F ( τ ) , Φ e ρ ∈ T i for all ρ ≺ X ; Φ e X may therefore be computed by evaluating Φ e ρ for the first ρ ∈ 2 < ω 1 extending τ such that Φ e ρ ∈ T i and Φ e ρ is sufficiently long. Therefore Φ e X is computable.

The second possibility is that η left outcome ω 1 because it encountered a τ in case (ii) above and never found an appropriate string ρ. However, since η ensures that X ≻ F ( τ ) , and Φ e X is total, a sufficiently long initial segment of X would have sufficed as an appropriate string ρ. This is a contradiction, so this possibility cannot in fact occur.

Therefore, if Φ e X ∈ [ T i ] , then either η is in outcome ω 1 unboundedly often and the map τ ↦ Φ e F ( τ ) is a computable embedding of T α e into the intersection of T i and the set of extensions in T of the anchor point of η, or η eventually ceases to enter outcome ω 1 and Φ e X is computable. □

The true path exists and is the only path in the tree of strategies that is visited unboundedly often.

It suffices to show that for each strategy, there is at most one outcome that is visited unboundedly often, and that this outcome is visited on a closed and unbounded set of stages.

Let η be a strategy that is itself visited on a closed and unbounded set of stages. The strategy η is pursuing the requirement R e , i for some e and some i. If η visits uncountably many distinct countable outcomes, then by construction it visited the outcome ω 1 unboundedly often as well; and by the prescribed behavior at limit stages, the set of stages at which η has outcome ω 1 is automatically closed.

By construction, if η ever leaves a particular countable outcome, then it will not return; therefore, if η visits outcome α unboundedly often, then either α = ω 1 or η enters outcome α and remains there for the remainder of the construction. In either case, η visits only one outcome unboundedly often, and does so on a closed and unbounded set of stages. □

Every path in T other than X has Cantor–Bendixson rank < α in T.

Let Y ≠ X be a path in T, and let σ be the maximal string so that σ ≺ Y and σ ≺ X . By construction, σ is the anchor node of some strategy η along the true path. Let R e , i be the requirement pursued by η.

There are then two possibilities: either η is successful in defining an embedding F : T α e → T above σ ⌢ 1 , or it is not. If η is successful, then all of the paths extending σ ⌢ 1 are computable images of paths in T α e ; so Y is contained in a clopen subset of [ T ] with Cantor–Bendixson rank α e < α , and therefore itself has Cantor–Bendixson rank less than α.

If η is unsuccessful, then eventually the construction will be directed along some extension of σ ⌢ 1 . Then σ ⌢ 1 ≺ X , contradicting our choice of Y. □

X has Cantor–Bendixson rank α in [ T ] .

T is a computable tree, and is therefore T i for some index i. Fix β < α . Let e be an index for the identity functional (i.e., Φ e A = A for any oracle A) so that β < α e . Certainly Φ e X = X , and X ∈ [ T i ] ; so by the satisfaction of the requirement R e , i , T α e computably embeds into T i ∩ [ X ↾ e ] . Since [ T α e ] has Cantor–Bendixson rank α e > β , it must be that [ T i ] ∩ [ X ↾ e ] has Cantor–Bendixson rank greater than β. But by construction, there are unboundedly many i so that T i = T ; so unboundedly many neighborhoods about X have elements of Cantor–Bendixson rank at least β. Therefore X has Cantor–Bendixson rank at least β.

Since X is the only element of [ T ] that may not have Cantor–Bendixson rank < α , X must therefore have Cantor–Bendixson rank exactly α in X. □

X has proper Cantor–Bendixson rank α.

Suppose that T ˆ is a computable tree and Y ≡ T X so that Y has Cantor–Bendixson rank β < α in [ T ˆ ] . Since T ˆ is computable, there exists an i so that T i = T ˆ . Fix e so that Φ e X = Y ; by the Padding Lemma, there are unboundedly many of these.

By the satisfaction of the requirement R e , i , T α e computably embeds into T i ∩ { τ ∣ τ ≽ Y ↾ e } . Because each T α e has Cantor–Bendixson rank α e , Y is therefore the sole member of the intersection of a decreasing sequence of neighborhoods with Cantor–Bendixson ranks cofinal in α; thus Y itself has Cantor–Bendixson rank at least α. □