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

Abstract

The range of possible ordinal values for the Cantor–Bendixson rank of an effectively closed set in Cantor space, and the relationship between the ranks and the Turing degrees of its members, have been closely studied. The wide array of results on this topic have often made use of useful topological features of Cantor space (notably, compactness) and of key properties of computable well-orders. In this paper, a number of these results are extended to the case of Cantor space on the first uncountable ordinal, in which these properties do not hold, using admissible recursion theory.

Keywords

Computability admissible recursion theory point-set topology

1. Introduction

1.1. Motivations and key results

The study of the Cantor–Bendixson derivative and the corresponding rank was initiated by Cantor in 1872, originally as a topological notion measuring the loci of concentration of subsets of the real line. A thorough treatment of the subject in general can be found in [5]. Since then, the notion has been extended to a wide range of other topological spaces.

For a computability theorist, the natural application is to subsets of Cantor space, $2^{ω}$ ; and, because the Cantor–Bendixson rank is defined particularly for closed sets, the subsets in question are most naturally taken to be effectively closed sets, or $Π_{1}^{0}$ -classes. In the classical setting, it is evident that every countable ordinal is achievable as the Cantor–Bendixson rank of some closed subset of $2^{ω}$ ; the closed sets in question, however, appear to increase in complexity in a qualitative sense as the rank increases. This raises the following question:

Question 1.1.
Which ordinals are possible as the Cantor–Bendixson rank of a $Π_{1}^{0}$ -class in $2^{ω}$ and under what conditions? Which Turing degrees are represented by points of particular Cantor–Bendixson ranks?

Cenzer, Clote, Smith, Soare, and Wainer showed in [1] that every computable ordinal can be realized as the Cantor–Bendixson rank of a member of a $Π_{1}^{0}$ -class, and put precise bounds on the Turing degree of the member in question. In light of the fact that the Cantor–Bendixson derivative of a $Π_{1}^{0}$ -class can be obtained by an arithmetic operation on the representing tree, and therefore the rank is necessarily a computable ordinal, this effectively settled the question for $2^{ω}$ , but of course left the problem open for many other topological spaces.

One such space is the analogue of Cantor space in higher cardinalities: $2^{κ}$ for κ an uncountable cardinal, equipped with an analogous topology. From a classical perspective, $2^{κ}$ is sufficiently similar to $2^{ω}$ that the standard results of the Cantor–Bendixson derivative and rank continue to hold; on the other hand, it appears to be more complex – again, in a qualitative sense, as we have not yet presented a means of making this precise. For example, while $2^{ω}$ is compact in the initial-segment topology, $2^{κ}$ is not even Lindelöf in the same topology; since many results in computability theory hinge on the compactness of Cantor space, it is reasonable to expect that a question analogous to 1.1 formulated in $2^{κ}$ might have a different conclusion.

In order to formulate such a question, we require a generalization of computability that bears a similar relationship to $2^{κ}$ that classical computability does to $2^{ω}$ ; the natural choice is α-recursion. In α-recursion, we replace the ω appearing throughout computability theory with some fixed (admissible) ordinal α – for example, if classical computability is predicated on Turing machines which run on a tape of length ω and for ω steps of computation, then α-recursion is based on α-Turing machines which run on a tape of length α and for α steps of computation. A reader interested in α-recursion in general may find excellent treatments in [2,8], and [10]. By reformulating 1.1 in terms of κ-recursion, we have the following:
Question 1.2.
Which ordinals are possible as the Cantor–Bendixson rank of a κ- $Π_{1}^{0}$ class in $2^{κ}$ , and under what conditions? Which κ-Turing degrees are represented by points of particular Cantor–Bendixson ranks?

In an effort to progress toward an answer to this question, we consider in this paper a simplified case: the case in which $α = ω_{1}$ and $2^{ω_{1}} \subseteq L$ . A brief summary of $ω_{1}$ -recursion under these assumptions and the results necessary for this paper will be presented in Section 1.3; for more details on this case, please see [3].

Section 2 will discuss the Cantor–Bendixson ranks of $Π_{1}^{0}$ -classes in $2^{ω_{1}}$ as a whole, leading to the following main result.
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 α.

In Section 3, the Cantor–Bendixson ranks of individual points within $Π_{1}^{0}$ -classes will be considered, concluding with the second main result of the paper: Theorem 1.4.
Let α be any ordinal that is $Δ_{1}^{1}$ -definable over $L_{ω_{1}}$ . Then there exists an $X \in 2^{ω_{1}}$ so that the following conditions hold:
There is a $Π_{1}^{0}$ -class in which X is a point of Cantor–Bendixson rank exactly α; and

There is no $Π_{1}^{0}$ -class in which X is a point of Cantor–Bendixson rank lower than α.

1.2. Notation

Many conventions of notation will be preserved from the classical setting of ω-computability, extended into the uncountable setting. For countable ordinals e, $Φ_{e}$ or $φ_{e}$ refer to the eth $ω_{1}$ -computable function. For $X \subseteq ω_{1}$ , $Φ_{e}^{X}$ denotes the eth $ω_{1}$ -computable function with oracle X. A boldface lower-case letter $a, b, c, \dots$ will be used for $ω_{1}$ -Turing degrees unless otherwise specified.

In general, we will use e, i, and j to denote countable ordinals that represent the indices of computable functions. Lower-case Greek letters $α, β, γ, \dots$ will be used to denote ordinals in general; for finite ordinals, n and m will typically be used.

Much of this paper will work with the structure $2^{< ω_{1}}$ ; the elements of this set are binary strings of countable length, and will usually use the symbols $σ, τ, ρ, θ$ . The symbol ⌢ will denote concatenation of two such strings, and $| σ |$ will denote the length of the string σ.

Upper-case Greek letters $Γ, Δ, \dots$ will be used to denote $ω_{1}$ -Turing functionals. Upper-case letters $A, B, C, \dots$ will represent subsets of $ω_{1}$ or the requirements of a priority argument; T will be reserved almost exclusively for binary trees.

For countable ordinals e, s, and x, $Φ_{e, s} (x)$ denotes the eth computable function evaluated at x within the first s stages. By convention, when σ is a countable string, $Φ_{e}^{σ}$ is evaluated only up to stage $| σ |$ and is said to diverge if it requires further information from the oracle.

For simplicity, we will refrain from using the $ω_{1}$ - prefix when referring to $ω_{1}$ -computability, and instead say simply “computability”. When a notion from classical computability is required, it will be referred to as “ω-computability” or similar.

1.3. Background on $ω_{1}$ -recursion

The following definitions are essentially due to Kripke [7].

Definition 1.5.
A set is hereditarily countable if its transitive closure is countable. Let $HC$ denote the collection of hereditarily countable sets. For the purposes of this paper, we will make the simplifying set-theoretic assumption that $HC = L_{ω_{1}}$ .

A first-order formula φ in the language of set theory is called $Δ_{0}^{0}$ if every quantifier appearing in φ is bounded (of the form $\forall x \in y$ or $\exists x \in y$ ). A formula is $Σ_{1}^{0}$ if it has the form $(\exists x) φ (x)$ , where φ is $Δ_{0}^{0}$ . More generally, a formula is $Π_{n}^{0}$ if it is the negation of a $Σ_{n}^{0}$ formula, and is $Σ_{n + 1}^{0}$ if it has the form $(\exists x) φ (x)$ for φ a $Π_{n}^{0}$ formula.

We say a subset $X \subseteq L_{ω_{1}}$ is computably enumerable if it is definable over $L_{ω_{1}}$ by a $Σ_{1}^{0}$ formula with parameters. X is computable if both X and $L_{ω_{1}} ∖ X$ are computably enumerable. More generally, X is $Σ_{n}^{0}$ if it is definable by a $Σ_{n}^{0}$ formula, $Π_{n}^{0}$ if it is definable by a $Π_{n}^{0}$ formula, and $Δ_{n}^{0}$ if it is both.

One compelling reason to consider this a reasonable extension of classical computability to the uncountable setting is its range of equivalent definitions; notably, that X is computable in this sense if and only if it is computable by a Turing machine with a tape of length $ω_{1}$ which is permitted to run for any countable number of stages.

Because of this equivalence, for the purposes of this paper we will operate under an uncountable analogue of the Church–Turing thesis; a set is computable if and only if it is “intuitively” computable by a machine capable of storing a hereditarily countable amount of memory and running for any countable length of time.

Relative computability extends to the uncountable setting in the natural way: for $Y \subseteq ω_{1}$ , we say X is computable from Y if it is computable using information in Y. In other words, if X and its complement are both definable over $L_{ω_{1}}$ by $Σ_{1}^{0}$ formulas using parameters from $L_{ω_{1}}$ and a unary predicate symbol for Y. In this manner, we can define Turing reducibility, Turing equivalence, and Turing degrees in the uncountable setting. There is also a natural analogue to the Turing jump, presented in detail in Definition 3.2.

Working within L confers one significant advantage from a computability-theoretic perspective, namely the presence of the well-ordering $<_{L}$ of the universe. The only important properties of this ordering for the purposes of this paper are that it is a well-ordering, and that its restriction to $L_{ω_{1}}$ is a computable relation with order-type $ω_{1}$ . For this reason, we need not distinguish between subsets of $ω_{1}$ and subsets of $L_{ω_{1}}$ , in the same manner that classical computability theory often does not distinguish between subsets of ω and, for example, $ω^{< ω}$ .

For the purposes of this paper, we also require one definition less typical for introductions to $ω_{1}$ -computability: the analogue to the first few levels of the classical analytic hierarchy.
Definition 1.6.
$X \subseteq ω_{1}$ is said to be $Σ_{1}^{1}$ if there exists an arithmetic formula $φ (x, Z)$ so that $\begin{array}{l} x \in X ⟺ (\exists Z \subseteq L_{ω_{1}}) φ (x, Z) \end{array}$ $X \subseteq ω_{1}$ is $Π_{1}^{1}$ if $ω_{1} ∖ X$ is $Σ_{1}^{1}$ ; X is $Δ_{1}^{1}$ if it is both $Σ_{1}^{1}$ and $Π_{1}^{1}$ .

It is worth noting that, unlike the countable case, the notions of $Δ_{1}^{1}$ and “hyperarithmetic” (which we have not defined here, though there are several reasonable definitions) do not coincide; as a result, arguments by an uncountable analogue to effective transfinite recursion are not sufficient to prove claims regarding the class of $Δ_{1}^{1}$ sets.
2. Ranks of sets

In this section, we will introduce the notion of the Cantor–Bendixson derivative and the corresponding rank to be used throughout the remainder of the paper, and present several results regarding the Cantor–Bendixson rank of a $Π_{1}^{0}$ -class considered as a whole, concluding with the complete characterization of the possible ranks of a $Π_{1}^{0}$ -class given in Theorem 1.3. Results regarding the Cantor–Bendixson ranks of individual points within a $Π_{1}^{0}$ -class, and their relationship to the Turing degrees of these points, will appear in the next section.

Definition 2.1.
Let X be a topological space, $A \subseteq X$ closed. A limit point of A is an $x \in A$ such that for any open U containing x, $A \cap (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 \in A$ is the least ordinal α so that $x \notin A^{(α + 1)}$ , or ∞ if there is no such α.
Definition 2.2.
For $σ \in 2^{< ω_{1}}$ , let $[σ]$ denote the subset of $2^{ω_{1}}$ consisting of all extensions of σ to length $ω_{1}$ .

A subset $X \subset 2^{ω_{1}}$ is a basic open set if it is $⋃_{σ \in Y} [σ]$ for some set $Y \subseteq 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_{α} \in 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 \in 2^{ω_{1}}$ so that $x ↾ α \in 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 \to 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 \subseteq 2^{ω_{1}}$ is closed if and only if $X = [T]$ for some tree $T \subseteq 2^{< ω_{1}}$ .

A set $X \subseteq 2^{ω_{1}}$ is perfect if and only if $X = [T]$ for some tree $T \subseteq 2^{< ω_{1}}$ such that every $σ \in T$ is an initial segment of at least two distinct points in X.

If $X \subseteq 2^{ω_{1}}$ is closed and $T \subseteq 2^{< ω_{1}}$ is a tree so that $X = [T]$ , then the Cantor–Bendixson derivative of X is $[\hat{T}]$ , where $\hat{T} \subseteq T$ is the set of all $σ \in T$ that are initial segments of at least two distinct points in X.

Proof.
(i) Let $X \subseteq 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_{α} = ⋃_{σ \in Z} [σ]$ for some $Z \subset 2^{α}$ . Then taking $T = {τ \in 2^{< ω_{1}} ∣ (\forall α < | τ |) τ ↾ α \in Y_{α}}$ is sufficient. Conversely, given a tree $T \subseteq 2^{< ω_{1}}$ , the set $[T]$ is $⋂_{α} ⋃_{σ \in T \cap 2^{α}} [σ]$ , which is closed.

(ii) Let $X \subseteq 2^{ω_{1}}$ be perfect, and let T be a tree so that $X = [T]$ , as required by (i). Suppose that $σ \in T$ is an initial segment of some point $x \in 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 \in X$ , $y \neq x$ , with $σ ≺ y$ ; therefore at least two paths of T pass through σ. Let $\hat{T} \subseteq T$ be ${σ \in T ∣ (\exists x \in [T]) σ ≺ x}$ . Then every $σ \in \hat{T}$ is an initial segment of at least two distinct points in X, and $X = [\hat{T}]$ .

Conversely, suppose $T \subseteq 2^{< ω_{1}}$ is such that every $σ \in T$ is an initial segment of at least two distinct points in $[T]$ . Let $x \in [T]$ . Define a sequence $⟨ y_{α} ∣ α < ω_{1} ⟩$ by taking $y_{α}$ to be the $y \neq 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 \subseteq 2^{ω_{1}}$ be closed, $T \subseteq 2^{< ω_{1}}$ a tree so that $X = [T]$ . Let $X^{'}$ be the Cantor–Bendixson derivative of X, and let $\hat{T}$ be as described in the proposition.

Fix $x \in X^{'}$ , and let $σ \in T$ be an arbitrary initial segment of x. Because x is a limit point of X, there exists a $y \neq x$ in $X \cap [σ]$ ; that is, a $y \in [T]$ which extends σ and is not x. Therefore $σ \in \hat{T}$ . So $X^{'} \subseteq [\hat{T}]$ .

Fix $x \in [\hat{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 $[\hat{T}] \subseteq 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 $\hat{T}$ that likewise has Cantor–Bendixson rank α and empty perfect core. Furthermore, the rank-α paths in $\hat{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 \subseteq 2^{< ω_{1}}$ such that $| U \cap 2^{α} | ⩾ 2$ for every $0 < α < ω_{1}$ , and for any $y \in 2^{ω_{1}}$ there exists an α such that $y ↾ α \notin U$ .
Proof.
Let $0^{α}$ denote the string consisting of a length-α sequence of zeros, and let U be the set of strings $σ ⌢ 0^{α} \in 2^{< ω_{1}}$ such that $σ \in 2^{⩽ ω}$ and $σ \notin L_{α}$ . Certainly U is a computable tree. Because $L_{α}$ is countable for any countable α, the set of $σ \in 2^{ω}$ with $σ ⌢ 0^{α} \notin U$ is always countable; therefore, $U \cap 2^{α}$ is uncountable.

Let $y \in 2^{ω_{1}}$ . Because $y \in L$ by the set-theoretic assumption $2^{ω_{1}} \subseteq L$ , $y ↾ ω \in L_{ω_{1}}$ , and therefore $y ↾ ω \in L_{α}$ for some countable α. Then, by construction, no extension of $y ↾ ω$ of length $ω + α$ is in U, and in particular $y ↾ (ω + α) \notin U$ . □

In the constructions to follow, a computable Aronszajn tree – a tree as in Lemma 2.7 with the additional requirement that $| U \cap 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 \subseteq 2^{< ω_{1}}$ be trees, and suppose that there exists an embedding $f : T \to 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 $\hat{T}$ and $\hat{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 : \hat{T} \to \hat{U}$ is an embedding, and that every path through $\hat{U}$ is the f-image of a path through $\hat{T}$ .

To see that f embeds $\hat{T}$ into $\hat{U}$ , consider $σ \in \hat{T}$ . Then there exist two paths $Y_{0}, Y_{1} \in [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, $σ \in \hat{U}$ .

Let $X \in [\hat{U}]$ . Since $\hat{U} \subseteq U$ , $X \in [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 \neq 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 \in [\hat{T}]$ . □
Proof of Theorem 2.6.
Given a partial function $f : 2^{< ω_{1}} \to 2$ , the tree given by f is the subset of $2^{< ω_{1}}$ given by ${σ : (\forall τ ≼ σ) 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 \subseteq ω_{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) \cap 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} \to 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 $σ \in 2^{< ω_{1}}$ , let $T (Γ, σ) = T (Γ, Y) \cap 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 $\hat{T} = {σ \oplus τ ∣ σ \in U \land τ \in T (Γ, σ) \land | σ | = | τ |}$ . 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 \in 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} \to 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) \cap 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.
$\hat{T}$ has the desired properties.
Proof.
Every path through $\hat{T}$ is a join with X, by construction. Let $Y = X \oplus Z$ be a path through $\hat{T}$ . Z, by construction, is a path through $T (Γ, X)$ . We therefore have a map $G : T (Γ, X) \to \hat{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 \to T (Γ, X)$ which induces a similar bijection. F preserves Turing degree, while G takes Z to $X \oplus Z$ . The composition $G \circ F$ then induces a bijection of paths in T with paths in $\hat{T}$ , so that the image of each path Z is Turing-equivalent to $X \oplus 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 $\exists A φ$ , where φ is first-order, and A ranges over subsets of the universe; likewise, a $Π_{1}^{1}$ formula is a formula of the form $\forall 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 \subseteq L_{ω_{1}}$ as the minimal set satisfying the following conditions, together with a rank function $| \cdot | : O \to ω_{2}$ and an ordering $<_{O}$ on $O$ .
$0 \in O$ , and $| 0 | = 0$ .

If $a \in O$ , then $a^{+} : = ⟨ 0, a ⟩ \in 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 < ω ⟩ ⟩ \in 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 \in ω_{1}$ is such that $a_{α} = Φ_{e} (α)$ for each α, then $a : = ⟨ 2, e ⟩ \in O$ . $| a | = {sup}_{α} | a_{α} |$ , and $c <_{O} a$ if and only if $c <_{O} a_{α}$ for some $α < ω_{1}$ .

For an ordinal α, $a \in 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 ⌢ σ ∣ σ \in U_{a} \land δ < ω_{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 ⌢ σ ∣ σ \in U_{a_{n}} \land δ < ω_{1}}$ .

Suppose $b = ⟨ 2, e ⟩$ . In this case, let $U_{b}$ be the closure under initial segments of $\begin{matrix} {0^{Φ_{e}^{X} (i)} ⌢ 1 ⌢ σ ∣ σ \in U_{Φ_{e}^{X} (i)} \land i < ω_{1}} \end{matrix}$

As typical in a classical argument by effective transfinite recursion, suppose that $U_{b}$ is undefined for some $b \in 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 $\hat{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.

Definition 3.1.

Let a be a Turing degree, $α < ω_{2}$ an ordinal. We say a can be represented with Cantor–Bendixson rank α if there is a $Π_{1}^{0}$ -class P and an $A \in P$ so that A has Turing degree a and Cantor–Bendixson rank α in P.

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

Definition 3.2.

Fixing a countable language, an index for a formula φ is a sequence of finite ordinals representing the symbols of the language in the order they appear in φ, together with an element of $L_{ω_{1}}$ which is a function mapping variable symbols to parameters.

For $X \subseteq ω_{1}$ , $X^{'}$ is the set of indices for $Σ_{1}^{0} [X]$ formulas φ with parameters in $L_{ω_{1}}$ , such that $L_{ω_{1}} ⊧ φ (c)$ .

Theorem 3.3.

There exists a $Δ_{3}^{0}$ degree that can be represented with Cantor–Bendixson rank 1, but not rank 0.

Proof.

We prove the theorem by constructing a set X representing the desired degree, as a path through a computable tree T in which X has Cantor–Bendixson rank 1. We will make use of an unbounded injury argument with a tree of strategies, closely analogous to an infinite injury argument from the classical setting, together with the Aronszajn root technique introduced in the proof of Theorem 2.6.

Let $⟨ T_{i} : i < ω_{1} ⟩$ be an effective enumeration of computable binary trees. The strategies within the tree of strategies alternate by level between requirements of the following types:

$X \neq Φ_{e}$ .

If $Φ_{e}^{X} \in [T_{i}]$ , then $T_{i}$ has a computable path.

Observe that, if the $D_{e}$ requirements are met, X will not be computable; if the $C_{e}^{i}$ requirements are also met, then any computable tree with an X-computable path will also have a computable path. If both sets of requirements are met, this will ensure that whenever $Y \equiv_{T} X$ is a path through a computable tree $T_{i}$ , the subtree of $T_{i}$ extending $Y ↾ α$ will include at least one path which is not Y. In particular, Y will be a limit point of $[T_{i}]$ and will therefore have Cantor–Bendixson rank at least 1.

The final condition of the claim, that X itself be $Δ_{3}^{0}$ , will be a consequence of the construction.

Each strategy η maintains an outcome and an active string. Strategies pursuing $D_{e}$ requirements have two outcomes, 0 and 1. Strategies pursuing $C_{e}^{i}$ requirements have uncountably many outcomes, indexed by ordinals in $ω_{1} + 1$ , with the priority ordering $ω_{1} < 0 < 1 < 2 < \dots$ . Strategies pursuing $C_{e}^{i}$ requirements also maintain an additional string called a key node. Throughout, any key nodes and active strings maintained by a strategy will be required to be proper extensions of the active strings of that strategy’s predecessors. At a stage s, let $X_{s}$ denote the union of the active strings of the strategies that are themselves active at the beginning of stage s; $X_{s}$ will be an approximation to the final path X.

Regardless of the requirement that a strategy η is pursuing, it designates its active string (and its key node, for a strategy pursuing a C requirement) as an Aronszajn root.

Let $T$ be a tree of strategies such that the following conditions hold:

Strategies at level $α ω + 2 n$ are assigned the requirement $D_{α ω + n}$ , and have successors corresponding to each outcome; and

Strategies at level $α ω + 2 n + 1$ are assigned the requirement $C_{e}^{i}$ , where $⟨ e, i ⟩ = α ω + n$ under a standard effective pairing function $⟨ \cdot, \cdot ⟩$ , and have successors corresponding to each outcome.

At any stage s, a strategy is called active if all of its predecessors are active and it has been initialized. Some strategies may require attention at stage s, to be defined later. The construction at stage s proceeds by the following steps:

Any strategy which was active at the beginning of the stage and which requires attention is permitted to act, beginning from the lowest-level strategies and proceeding upwards.

The lowest-level strategy which has not been initialized and every predecessor of which is active is initialized.

Throughout the construction, it will be maintained that by stage s, $T \cap 2^{< s}$ is decided; that is, no string of length $< s$ will be enumerated into the tree at stage s. This will ensure that T is itself a computable tree.

Certain strings will have been designated Aronszajn roots during the construction, as previously used in Theorem 2.6. It is important to note that the copies of the standard branchless tree U above each of these roots continue to be built as usual, even when the strategies responsible for them are not active; this is essential for maintaining the aforementioned decidability condition.

Let η be a strategy pursuing requirement $D_{e}$ . When η is initialized at stage s, it begins in outcome 0, and finds the $<_{L}$ -least σ which is an extension of all of the active strings of its predecessors and has not yet been excluded from T. The strategy enumerates σ, its immediate successors $σ ⌢ 0$ and $σ ⌢ 1$ , and all of its initial segments into T. It takes $σ ⌢ 1$ as its active string, and designates $σ ⌢ 0$ as an Aronszajn root.

At any later stage t, if $Φ_{e, t} (| σ |) ↓ = 1$ , then η is said to require attention. If permitted to act, then it switches to outcome 1 and makes $σ ⌢ 0$ its active string.

At a limit stage s, the outcome of η is taken to be 0 if and only if η had outcome 0 at every previous stage; otherwise, the outcome is taken to be 1. Likewise, the active string of η is $σ ⌢ 1$ if it has been $σ ⌢ 1$ at every previous stage, and $σ ⌢ 0$ otherwise.

Let η instead be a strategy pursuing requirement $C_{e}^{i}$ . When η is initialized at stage s, it performs steps very similar to a strategy pursuing requirement $D_{e}$ : it begins in outcome 0, and finds the $<_{L}$ -least σ which is an extension of all of the active strings of its predecessors and has not yet been excluded from T. The strategy then enumerates σ, $σ ⌢ 0$ , $σ ⌢ 1$ , and all of their initial segments into T. It then takes $σ ⌢ 1$ as its active string, and designates $σ ⌢ 0$ as an Aronszajn root. The notable difference from a $D_{e}$ strategy is that a $C_{e}^{i}$ strategy must also select a key node; η selects $σ ⌢ 1$ as its key node. It also defines an ordinal $ℓ = 0$ .

At any later stage t, the behavior of η depends on whether or not it is currently in outcome $ω_{1}$ . While η is not in outcome $ω_{1}$ , it waits for $Φ_{e, t}^{X_{t}} ↾ (ℓ + 1) ↓ \in T_{i}$ . If this occurs, η is said to require attention. When permitted to act, η sets ℓ to the least ordinal such that $Φ_{e, t}^{X_{t}} ↾ (ℓ + 1) ↑$ , designates $X_{t}$ as its new key node and an Aronszajn root, switches to outcome $ω_{1}$ , and sets its active string to $σ ⌢ 0$ .

While η is in outcome $ω_{1}$ , η waits until there exists an $x < t$ such that $Φ_{e}^{τ} ↾ (ℓ + 1) ↑$ for every extension τ of its current key node with $| τ | < t$ , and at least one stage has passed since η entered outcome $ω_{1}$ . When this holds, η is again said to require attention; when permitted to act, η sets its active string to its current key node and switches to its first unused countable outcome. If, instead, there exists a τ extending the current key node of length less than t with $Φ_{e}^{τ} ↾ (ℓ + 1) ↓$ and $Φ_{e}^{ρ} ↾ (ℓ + 1) ↑$ for every proper initial segment ρ of τ, then η takes τ as its new key node and designates it an Aronszajn root, and increments ℓ, but takes no further action.

At a limit stage s, η takes the least outcome (in the priority order) which it has held cofinally often before stage s; in other words, it takes outcome $ω_{1}$ if it has been in outcome $ω_{1}$ cofinally often, and a countable outcome α if η eventually entered outcome α prior to stage s and did not leave. Note that, because by construction η does not change between countable outcomes without passing through outcome $ω_{1}$ , these are the only two options. If η is in outcome $ω_{1}$ at stage s, its active string is taken to be $σ ⌢ 0$ ; if, instead, it is in a countable outcome, its active string is taken to be the limit of its active strings prior to stage s. Regardless of the outcome of η, its key node at stage s is taken to be the limit of its previous key nodes, and ℓ is taken to be the limit of its previous values. The resulting active string and key node are enumerated into T.

Let X be the leftmost string in $2^{ω_{1}}$ which extends $X_{s}$ for uncountably many s. Define the true path to be the (unique) sequence of strategies which are active at uncountably many stages. Claim 3.4.

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

Proof.

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

Let η be a strategy that is itself visited unboundedly often. Suppose the strategy η is pursuing the requirement $C_{e}^{i}$ for some e and some i. If η visits the outcome $ω_{1}$ unboundedly often, the set of these stages is automatically closed by the prescribed behavior at limit stages. If, instead, η eventually ceases to visit the outcome $ω_{1}$ , then it reaches a fixed countable outcome and remains there for the rest of the constructino.

Suppose instead that η is pursuing the requirement $D_{e}$ for some e. Then either η eventually acts, in which case it remains in outcome 1 from that point forward, or it does not, in which case it remains in outcome 0 for the entire construction.

Since every strategy pursues one of these two requirements, this completes the proof. □

Claim 3.5.

Every $D_{e}$ requirement is satisfied.

Proof.

Suppose that $X = Φ_{e}$ . Let η be the strategy along the true path to which the requirement $D_{e}$ was assigned, and let σ be the string selected by $D_{e}$ on initialization. If $Φ_{e} (| σ |) = 0$ , then η never requires attention, and the active string of η remains $σ ⌢ 1$ . Then $X ≻ σ ⌢ 1$ , and in particular $X (| σ |) = 1$ .

If, on the other hand, $Φ_{e} (| σ |) = 1$ , then this occurs at some stage s. After that stage, η requires attention. At the next stage at which η is active, η is permitted to act; it changes its active string to $σ ⌢ 0$ . Then $X ≻ σ ⌢ 0$ , and in particular $X (| σ |) = 0$ . □

Claim 3.6.

Every $C_{e}^{i}$ requirement is satisfied.

Proof.

Suppose that $Φ_{e}^{X} \in [T_{i}]$ . Let η be the strategy along the true path to which the requirement $C_{e}^{i}$ was assigned, and let σ and ℓ be as defined by η. $Φ_{e}^{X}$ is a total branch of $T_{i}$ , so it is unboundedly often true that $Φ_{e, t}^{X_{t}} ↾ (ℓ + 1) ↓ T_{i}$ . If this occurs while η is not in outcome $ω_{1}$ , η then enters outcome $ω_{1}$ ; therefore, η is in outcome $ω_{1}$ unboundedly often.

By construction, η continues extending its key nodes without bound, because both re-entering outcome $ω_{1}$ and remaining in a fixed countable outcome require extending the key node. The resulting sequence of key nodes is computable, and therefore defines a computable path $Y \in [T]$ . Furthermore, $Φ_{e}^{Y} \in [T_{i}]$ . Therefore, $T_{i}$ has a computable path. □

Claim 3.7.

Every path in T other than X is the sequence of key nodes belonging to a $C_{e}^{i}$ strategy.

Proof.

Let $Y \in [T]$ , $Y \neq X$ . Y cannot be the limit of a sequence of active strings, because the only unbounded sequence of pairwise-comparable active strings is that along the true path, which generates X. Hence, there is some α such that $Y ↾ β$ is not an active string of any strategy for $β > α$ . Since Y is a path, it cannot be relegated to the strings above a fixed Aronszajn root; instead, it must be the union of a sequence of Aronszajn roots. Because these are all extensions of the same collection of active strings, they must all have been enumerated into T on behalf of a single strategy. The only example of this behavior in the construction is the sequence of key nodes generated by a $C_{e}^{i}$ strategy. □

Claim 3.8.

X has the desired degree.

Proof.

X is $Δ_{3}^{0}$ by virtue of the fact that $0^{″}$ is sufficient to determine the leftmost path encountered unboundedly often. As noted at the beginning of the argument, the success of the $D_{e}$ requirements ensures that X is not computable; this, in combination with the success of the $C_{e}^{i}$ requirements, guarantees that any computable tree with a path Turing-equivalent to X must have another path as well. Thus, if $Y \equiv_{T} X$ is a member of $[T_{i}]$ for a computable tree $T_{i}$ , then Y has Cantor–Bendixson rank at least 1 in $T_{i}$ .

Finally, by Claim 3.7, all paths in T are either X or the sequence of key nodes belonging to a single strategy. In the latter case, the path is automatically isolated, and hence has Cantor–Bendixson rank 0; therefore, in T, X has Cantor–Bendixson rank 1. This witnesses that, while X cannot be represented with Cantor–Bendixson rank 0, it can appear with rank 1. □

This completes the proof of Theorem 3.3. □

Note that in fact the above proof shows something slightly stronger; we label it here as a “corollary” because it is a corollary of the proof, though not of the theorem.

Corollary 3.9.

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.

In light of the existence of degrees like the one specified in Theorem 3.3, we introduce some additional terminology.

Definition 3.10.

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 $< α$ .

It is evident that not every ordinal $α < ω_{2}$ may be realized as the proper Cantor–Bendixson rank of a subset of $ω_{1}$ , if only because there are only $ℵ_{1}$ distinct $Π_{1}^{0}$ -classes. However, it is the case that any computable ordinal α is so realizable.

Theorem 3.11.

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

Proof.

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 $\hat{T}$ , there will be a series of embeddings of trees of increasing Cantor–Bendixson rank into the neighborhoods around that point in $\hat{T}$ ensuring that the point has Cantor–Bendixson rank at least α.

Given α, fix a computable sequence of computable ordinals $⟨ α_{β} ∣ β < ω_{1} ⟩$ so that $α = {lim sup}_{β \to ω_{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 \to ω} γ_{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 < \dots$ . We operate on the tree of outcomes $Λ^{< ω_{1}}$ ; the strategies assigned to each level pursue requirements as follows.

If $Φ_{e}^{X} \in [T_{i}]$ , then one of the following holds.

$T_{α_{e}}$ computably embeds into the intersection of $T_{i}$ and the set of extensions in T of a string in T; or

$Φ_{e}^{X}$ is computable.

We assign limit levels to the least $R_{e, i}$ requirement not yet assigned.

Any strategy $η \in Λ^{< ω_{1}}$ has an anchor point $σ \in 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 \in Λ^{ω_{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}} \to 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 $τ \in 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

τ is not in the domain of F, and no member of $T_{α_{e}}$ other than τ extends all of the proper initial segments of τ.

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.

Proof.

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} \in [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 $τ \mapsto Φ_{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}^{ρ} \in T_{i}$ for all $ρ ≺ X$ ; $Φ_{e}^{X}$ may therefore be computed by evaluating $Φ_{e}^{ρ}$ for the first $ρ \in 2^{< ω_{1}}$ extending τ such that $Φ_{e}^{ρ} \in 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} \in [T_{i}]$ , then either η is in outcome $ω_{1}$ unboundedly often and the map $τ \mapsto Φ_{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. □

Claim 3.13.

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

Proof.

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. □

Claim 3.14.

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

Proof.

Let $Y \neq 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}} \to 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. □

Claim 3.15.

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

Proof.

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 \in [T_{i}]$ ; so by the satisfaction of the requirement $R_{e, i}$ , $T_{α_{e}}$ computably embeds into $T_{i} \cap [X ↾ e]$ . Since $[T_{α_{e}}]$ has Cantor–Bendixson rank $α_{e} > β$ , it must be that $[T_{i}] \cap [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. □

Claim 3.16.

X has proper Cantor–Bendixson rank α.

Proof.

Suppose that $\hat{T}$ is a computable tree and $Y \equiv_{T} X$ so that Y has Cantor–Bendixson rank $β < α$ in $[\hat{T}]$ . Since $\hat{T}$ is computable, there exists an i so that $T_{i} = \hat{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} \cap {τ ∣ τ ≽ 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 α. □

This completes the proof of Theorem 3.11. □

Corollary 3.17.

Let α be an ordinal computable from the unique path X of a tree T. Then there exists (uniformly in an X-notation for α) a set $Y ⩽_{T} X^{″}$ with proper Cantor–Bendixson rank α.

Proof.

By Theorem 3.11 relativized to X, there exists a $Z ⩽_{T} X^{″}$ which has Cantor–Bendixson rank α in some X-computable tree U, and never has rank less than α in any computable tree. It is further evident that we can choose Z so that $X <_{T} Z$ . By Theorem 2.6, there is a computable tree $\hat{U}$ so that the paths of $\hat{U}$ are in one-to-one rank-preserving correspondence with those of U, and furthermore that the image of any path P in U under this correspondence is equivalent to $P \oplus X$ . Since $Z >_{T} X$ , $Z \oplus X \equiv_{T} Z$ , so the image of Z is of the same degree as Z. Z therefore has proper Cantor–Bendixson rank α. □

An immediate consequence of Corollary 3.17 is the main theorem of the section:

Theorem 1.4.

Let α be any ordinal that is $Δ_{1}^{1}$ -definable over $L_{ω_{1}}$ . Then there exists an $X \in 2^{ω_{1}}$ so that the following conditions hold:

There is a $Π_{1}^{0}$ -class in which X is a point of Cantor–Bendixson rank exactly α; and

There is no $Π_{1}^{0}$ -class in which X is a point of Cantor–Bendixson rank lower than α.

In fact, a somewhat stronger result can be shown.

Corollary 3.18.

Let α be any $Δ_{1}^{1}$ ordinal. Then there exists a set X with proper Cantor–Bendixson rank α. Furthermore, both a $Δ_{1}^{1}$ -code for X and an index for a computable tree witnessing the rank of X may be found uniformly in a $Δ_{1}^{1}$ -code for a presentation of α.

Proof.

This is an immediate consequence of the previous result, together with Theorem 1.23 of [4]. □

References

Cenzer,

Clote,

R.L.

Smith,

R.I.

Soare and

S.S.

Wainer, Members of countable

Π_{1}^{0}

classes, Annals of Pure and Applied Logic 31 (1986), 145–163. doi:10.1016/0168-0072(86)90067-9.

C.-T.

Chong, Techniques of Admissible Recursion Theory, Springer, Berlin, 1984.

Greenberg and

Knight, Computable structure theory using admissible recursion theory on ω₁, in: Effective Mathematics of the Uncountable,

Greenberg,

Hirschfeldt,

J.D.

Hamkins and

Miller, eds, ASL-Cambridge, Cambridge, UK, 2013, pp. 50–80. doi:10.1017/CBO9781139028592.005.

Johnston, Computability in uncountable binary trees, The Journal of Symbolic Logic 84(3) (2019), 1049–1098. doi:10.1017/jsl.2019.5.

A.S.

Kechris, Classical Descriptive Set Theory, Springer, Berlin, 2012.

S.C.

Kleene, On notation for ordinal numbers, The Journal of Symbolic Logic 3(04) (1938), 150–155. doi:10.2307/2267778.

Kripke, Transfinite recursion on admissible ordinals, Journal of Symbolic Logic 29 (1964), 161–162.

G.E.

Sacks, Higher Recursion Theory, Springer-Verlag, Berlin, 1990.

R.A.

Shore, On the jump of an α-recursively enumerable set, Transactions of the American Mathematical Society 217 (1976), 351–363. doi:10.1090/S0002-9947-1976-0424544-2.

10.

R.A.

Shore, α-recursion theory, Handbook of Mathematical Logic (1977), 653–680. doi:10.1016/S0049-237X(08)71118-2.

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

Abstract

Keywords

1. Introduction

1.1. Motivations and key results

1.3. Background on ω 1 -recursion

References

1.3. Background on $ω_{1}$ -recursion