COUNTABLE THIN Π_{1}^{0} CLASSES

Douglas Cenzer, Rodney Downey, Carl Jockusch and Richard Shore

University of Florida; Victoria University of Wellington, New Zealand; University of Illinois; Cornell University

July 15, 1991

Abstract. A Π_{1}^{0} class P ⊂ {0, 1}^{ω} is thin if every Π_{1}^{0} subclass Q of P is the intersection of P with some clopen set. Countable thin Π_{1}^{0} classes are constructed having arbitrary recursive Cantor-Bendixson rank. A thin Π_{1}^{0} class P is constructed with a unique nonisolated point A of degree 0′. It is shown that, for all ordinals α > 1, no set of degree ≥ 0′′ can be a member of any thin Π_{1}^{0} class. An r.e. degree d is constructed such that no set of degree d can be a member of any thin Π_{1}^{0} class. It is also shown that between any two distinct comparable r.e. degrees, there is a degree (not necessarily r.e. ) that contains a set which is of rank one in some thin Π_{1}^{0} class. It is shown that no maximal set can have rank one in any Π_{1}^{0} class, while there exist maximal sets of rank 2. The connection between Π_{1}^{0} classes, propositional theories and recursive Boolean algebras is explored, producing several corollaries to the results on Π_{1}^{0} classes. For example, call a recursive Boolean algebra thin if it has no proper non-principal recursive ideals. Then no thin recursive Boolean algebra can have a maximal ideal of degree 0′′.

Introduction.

This paper examines the relation between the Cantor-Bendixson and other structure of a countable Π_{1}^{0} class and the recursion-theoretic complexity of the members of that class.

A recursively bounded Π_{1}^{0} class P is simply an effectively closed subset of the Baire space ω^{ω} such that some recursive function f is greater than every element of P, that is, for all x ∈ P and for all n, f(n) > x(n). It is easy to see that every recursively bounded (r.b. ) Π_{1}^{0} class is recursively homeomorphic to a Π_{1}^{0} subclass of the Cantor space {0, 1}^{ω} of infinite sequences of 0’s and 1’s. Therefore, in this paper, a Π_{1}^{0} class will always be an effectively closed subset of {0, 1}^{ω}. An element x of the Cantor space is the characteristic function (χ_{A}) of some subset A of the natural numbers ω; we will frequently identify A with χ_{A}.

Π_{1}^{0} classes have been examined in many areas of mathematics. They have been studied in connection with logical theories, since, for any recursively enumerable

This research was done for the most part at the MSRI, Berkeley during the Logic year 1989-1990; all authors thank the MSRI for support, including NSF grant DMS 85-05550; Downey acknowledges support of the U.S./N.Z. cooperative science foundation and IGC grant from Victoria; Jockusch partially supported by NSF grant DMS 89-02641; Shore partially supported by NSF grant DMS 89-12797.

Typeset by AMS-TEX

2DOUGLAS CENZER, RODNEY DOWNEY, CARL JOCKUSCH AND RICHARD SHORE

theory Γ, the class of complete extensions of Γ is a Π_{1}^{0} class. Also, every Π_{1}^{0} class is degree-isomorphic to the class of complete extensions of some axiomatizable theory. They have also been studied in connection with recursive Boolean algebras, since the family of ultrafilters of a recursive Boolean algebra is a Π_{1}^{0} class and every recursive Boolean algebra is recursively isomorphic to the family of relatively clopen subsets of a Π_{1}^{0} class.

The connection between recursive Boolean algebras, logical theories and Π_{1}^{0} classes is illustrated by examining the lattice L(B) of recursively enumerable filters of a recursive Boolean algebra B. For instance, consider the countable free Boolean algebra Q of propositions generated by a countable set {P_{i}, ¬P_{i} : i ∈ ω} of literals. Under this identification, we have the following correspondences: proper filters with consistent theories, recursively enumerable filters with axiomatizable theories, recursive filters with decidable theories, and ultrafilters with complete theories. The natural way to study the filter structure of Q is via the Stone space S(Q). Recall that if F is a filter of Q , then S(F) is the collection of all ultrafilters containing F. S(F) can be viewed as a Π_{1}^{0} subclass of S(Q). This provides a correspondence between the r.e. filters of Q and the Π_{1}^{0} subclasses of S(Q). This also provides a correspondence between recursively enumerable Boolean algebras and Π_{1}^{0} classes, since B is an r.e. Boolean algebra if and only if B is effectively isomorphic to a quotient Q/F for some r.e. filter F. While all of this is well known, the connections have not appeared explicitly in print, so in section four we will explicitly spell out these basic results as well as the implications of our particular results on Π_{1}^{0} classes.

There are many other examples of the deep connections between Π_{1}^{0} classes and effective problems in mathematics. For example, one can try to generalize the above results by considering the Zariski topology of a recursive ring. Then if I is an r.e. ideal, the collection of prime ideals containing I forms a Π_{1}^{0} class. A nice open problem here (due to Friedman-Simpson-Smith [13]) is whether for any Π_{1}^{0} class C, there is a recursive ring R such that the collection of prime ideals of R corresponds with C. Another nice example is the proof of Metakides and Nerode [25] that Craven’s classification of the cone C(R) of orderings of a formally real field is effectively tight, that is: For any r.b. Π_{1}^{0} class C, there is a recursive formally real field R such that there is an effective one-to-one correspondence between the members of C(R) and the members of C which preserves many-one degree.

Recursively bounded Π_{1}^{0} classes arise naturally in the study of recursive combinatorics. The set of solutions to an infinite recursive cominbatorial problem may be represented as a Π_{1}^{0} class. For example, the set of k-colorings of an infinite recursive graph forms a r.b. Π_{1}^{0} class. The paper [3] of Cenzer and Remmel includes a survey of such problems, including also the marriage problem, the decomposition problem for partially ordered (p.o. ) sets and the dimension of p.o. sets problem. In some cases, every r.b. Π_{1}^{0} class can be represented as the set of solutions to some recursive problem. This was shown by Manaster, Rosenstein and Jockusch [21] for the surjective marriage problem and by Remmel [26] for the coloring problem. Cenzer and Remmel [4] obtained a similar result for the set of winning strategies of an effectively closed infinite game of perfect information.

One reason that Π_{1}^{0} classes arise so naturally in these problems is that the existence of a solution to an infinite problem can be derived from the existence of solutions to finite versions of the problem by applying Konig’s Lemma, that is, the fact that every infinite finite branching tree has an infinite path. It turns out that in most of these cases, the existence theorem for solutions to one of these infinite problems also implies Konig’s Lemma in a certain subsytem of second-order arithmetic. These results, part of the program of “reverse mathematics”, depend on an analysis of the corresonding Π_{1}^{0} classes (see [3]).

The situation is rather akin to the realization that the notions of an r.e. set and Turing reducibility lay at the heart of incompleteness proofs. A natural question arising from that realization was Post’s problem, which led to the analysis of the degrees of r.e. sets. The analogous question for r.b. Π_{1}^{0} classes was the determination of the possible degrees of their members. The first to address this question were Jockusch and Soare [15,16]. They showed in [15, Corollary 1.1], among other things, that for every nonzero degree d ≤ 0′, there is a set A of degree d which is a member of some Π_{1}^{0} class with no recursive elements. This means, for instance, that there is a recursive formally real field with no recursive orderings and all orderings having mutually incompatible degree.

Research in this area is still ongoing as we have by no means yet fully understood the possible degrees of members of Π_{1}^{0} classes. One apparently hard question here is whether there is a r.b. Π_{1}^{0} class all of whose members bound minimal degrees. A positive solution would solve an old question since it would show that all complete systems of arithmetic bound minimal degrees.

Recursively enumerable sets not only have degree, they also have algebraic structure. Thus we seek to understand the relationship between the structure of the lattice E of r.e. sets and the degrees. Hallmark results here are Martin’s result [19] that an r.e. set M is maximal (i.e. a co-atom in the quotient lattice of E modulo finite sets) if and only if M has high degree (i.e. M′ ≡_{T} ∅′′) and Soare’s result [27] that the lattice of supersets of a low set is isomorphic to E. The first says that very high information content corresponds to high algebraic complexity and the second asserts that sets with low information content resemble recursive sets.

The analogous situation for Π_{1}^{0} classes is poorly understood. Here there are several notions of algebraic structure associated with a Π_{1}^{0} class. One such notion is the Cantor-Bendixson rank and this is closely associated with the degrees of members of (countable) Π_{1}^{0} classes. In [1], the degrees of members of countable Π_{1}^{0} classes were first studied. This analysis will be explained in detail below. It was shown in [1] that for any recursive ordinal α, there is a Π_{1}^{0} class P with elements of Turing degree to 0^{(2α)} and 0^{(2α+1)} and having rank α in P. Moreover, for any degree d ≤ 0′′ which is comparable to 0′, there is a set A of degree d which has rank 1 in some Π_{1}^{0} class. In the sequel, [2], to that paper, the notion of the Cantor-Bendixson rank of a set (that is, the least ordinal α such that |A|_{P} = α for some Π_{1}^{0} class) was explored further. It was shown that every co-RE set is Turing equivalent to a hyperimmune co-RE set of rank one and that every hyperimmune set is Turing equivalent to a set which is not ranked. It was also shown that there can be two setts A and B of the same degree such that A is ranked while B is either not ranked or has a different rank than A. In particular, there are sets of degree 0′ which have arbitrarily high recursive rank, whereas none of the sets 0^{(α)} are ranked at all. These studies were further continued by Downey [8], who constructed a degree b > 0 such that if A has degree ≤ b , then A has rank ≤ 1.

Another notion of algebraic structure is given by analyzing the direct analogue of E, the lattice L(2^{ω}) of Π_{1}^{0} subclasses of 2^{ω}. Here work is still in its infancy.

In the present paper we focus on one feature of L(2^{ω}): the analogue of a maximal set in E. Since everything is dual in L(2^{ω}), the corresponding notion will be one of minimality: one would expect that a minimal Π_{1}^{0} class will correspond to a maximal filter.

The first construction of such an object was due to Martin and Pour-El [24], who constructed in Q an axiomatizable, essentially undecidable theory T each axiomatizable extension of which was a finite one. In the language of filters, this was a perfect member of L(Q) such that each extension was principal. When we interpret this in L(2^{ω}), we arrive at the central notion of the present paper: a thin Π_{1}^{0} class. A Π_{1}^{0} subset of {0, 1}^{ω} is said to be thin if, for every Π_{1}^{0} subset Q of P, there is a clopen set U such that Q = U ∩ P. The notion of thinness was first made explicit in Downey [8]. Thin classes were also independently constructed by Simpson (unpublished) and are related to superminimal profinite groups by the work of Rick Smith [29]. The stronger notion of a minimal Π_{1}^{0} class C is one such that every Π_{1}^{0} subclass Q of C is either finite or cofinite in C.

The notion of a thin Π_{1}^{0} class can also be looked at in connection with recursive combinatorics. For example, let C be the Π_{1}^{0} class of k-colorings of a recursive graph G = (V, E). One of the elementary properties of rank is that an isolated member of a Π_{1}^{0} class must be recursive. Now a coloring ϕ of G will be isolated in C if and only if there is some finite subgraph G′ of G such that ϕ is the unique extension of the coloring ϕ ↾ G′ to the entire graph G. Now we will show in section one that in a thin class any recursive member has to be isolated. Thus if C is thin, then any recursive coloring of G is uniquely determined by its restriction to some finite subgraph. Now fix a recursive coloring ψ of a recursive subgraph G′ of G. Then the class C_{ψ} of all extensions ϕ of ψ to G is a Π_{1}^{0} subclass of C. Thus if C is minimal, it follows that either all but finitely many colorings of G agree with ψ or only fintely many of them agree with ψ. It follows from the result of Remmel [26] cited above that once we have constructed thin and minimal classes, there will also be recursive graphs with the properties discussed here.

If F is a r.e. filter, then the degree of F is the same as the degree of the set of extendible nodes in the Π_{1}^{0} class C(F) representing F in 2^{ω}. For perfect Π_{1}^{0} classes these degree classes are well understood. In the same way as the maximal sets correspond to the high degrees, it was found that Martin-Pour El theories have degrees corresponding to a new natural subclass of the r.e. degrees that correspond to natural “multiple permitting arguments”. This class was subsequently found to occur in a number of other constructions in the literature and the class has recently been extended to the degrees at large. (See Downey-Jockusch-Stob [10].) It is not known if the analogues of Soare’s maximal set result holds for such filters. Is it the case that if C_{1} and C_{2} are two perfect thin Π_{1}^{0} classes, then there is an automorphism Φ of L(2^{ω}) with Φ(C_{1}) = C_{2}?

In the present paper we continue the investigation of L(2^{ω}) focusing now on thin theories and upon lattice theoretical properties of members of Π_{1}^{0} classes. As the title suggests we will particularly concern ourselves with countable (thin) Π_{1}^{0} classes and degree classes associated with them.

The goal of the paper is thus twofold: we continue the analysis of L(2^{ω}) and continue to extend the general programme of seeing which degrees contain ranked points, and what properties of a set may imply that the set is, or is not, ranked.

The paper is organized as follows. We begin with a section of preliminaries. In section 2, countable thin Π_{1}^{0} classes are constructed having all members of all possible Cantor-Bendixson ranks, that is, all recursive ranks. A thin Π_{1}^{0} class P is constructed with D(P) = {A}, where A has degree 0′. On the other hand, a general result is proved which implies that, for all ordinals α > 1, no set of degree 0^{(α)} can be a member of a thin Π_{1}^{0} class. An r.e. degree d is constructed such that no element of degree d can be a member of any thin Π_{1}^{0} class.A density result is given which finds, between any two comparable r.e. degrees, a Turing degree which has a member of rank one in some thin Π_{1}^{0} class.

In section three, we study the class of r.e. sets one would most likely expect to be associated with thinness or ranking: the maximal sets. We show that although no maximal set can have rank one, there exist maximal sets of rank 2. In fact, we show that no Σ_{2}^{0} hyper-hyper-immune set can have rank one, although we do not know if a hhi set can have rank one.

In section 4, as mentioned earlier, we will make explicit the connection between Π_{1}^{0} classes and recursive Boolean algebras. This produces several theorems concerning Boolean algebras which are corollaries of the results of section 2. A recursive Boolean algebra will be said to be thin if it has no proper non-principal recursive ideals. Then, for example, if the Boolean algebra B is thin, then it cannot have a maximal ideal of degree 0′′.

1. Preliminaries.

Some definitions are needed. Let 2^{ω} be the Cantor set of infinite sequences of 0’s and 1’s and ω^{ω} be the Baire space of infinite sequences of natural numbers. Let 2^{<ω} be the set of finite strings of 0’s and 1’s and let ω^{<ω} be the set of finite strings of natural numbers. We think of a string σ as a function from {0, 1, ..., n − 1} into ω and write lh(σ) = n. The empty string has length 0 and will be denoted by ∅. A constant string σ of length n will be denoted k^{n} and the constant infinite string will be denoted by k^{ω}. For m < lh(σ), σ ↾ m is the restriction of σ to {0, 1, ..., m − 1}; τ is an extension of σ (σ ≺ τ) if σ = τ ↾ m for some m. We say that σ and τ are compatible if either σ ≺ τ or τ ≺ σ. The concatenation σ^{⌢}τ (or sometimes just στ) is defined by

σ^{⌢}τ = (σ(0), σ(1), ..., σ(m − 1), τ(0), τ(1), ..., τ(n − 1)), where lh(σ) = m and lh(τ) = n. In particular, we let σ^{⌢}a represent σ^{⌢}(a) and a^{⌢}σ represent (a)^{⌢}σ, where a is a letter. A tree is a set T of strings such that if τ ∈ T and σ ≺ τ, then σ ∈ T; for any σ, T ↾ σ = {τ ∈ T : σ and τ are compatible}. For an element x of ω^{ω}, x ↾ n denotes the finite sequence (x(0), x(1), ..., x(n − 1)). We say that σ is an initial segment of x (σ ≺ x) if σ = x ↾ n for some n. We write y = σ^{⌢}x to mean that y(i) = σ(i) for i < lh(σ) = n and y(n + i) = x(i) for all i. The set [T] of paths through T is {x : x ↾ m ∈ T for all m}. The set Ext(T) of extendible nodes of T is defined by

σ ∈ Ext(T) ⟺ (∃x ∈ [T])[σ ≺ x]. A node σ ∈ T is said to be a dead end if σ ∉ Ext(T). A subset P of ω^{ω} is Π_{1}^{0} if P = [T] for some recursive tree T. It is importanant to note that any Π_{1}^{0} class is actually equal to [T] for some primitive recursive tree T. (In fact, it is shown in [4] that polynomial time trees suffice.) Thus we can effectively enumerate the Π_{1}^{0} classes by enumerating the primitive recursive trees. This will be used in several places.

Now we will frequently want to code up a finite sequence (a_{0} < a_{1} < ⋯ < a_{n}) of natural numbers by a finite sequence σ =< a_{0}, a_{1}, …, a_{n} >∈ {0, 1}^{<ω}. We will do this by choosing σ to be the finite sequence of length a_{n} so that, for all i < a_{n}, σ(i) = 1 ⟺ (∃k < n)D[a_{k} = i]. Thus σ is the restriction to a_{n} of the characteristic function of the set {a_{0}, …, a_{n−1}}. This is made explicit as follows.

Definition. For any finite sequence a_{0} < a_{1} < ⋯ < a_{n} of natural numbers,

< a_{0}, a_{1}, …, a_{n} >= 0^{a_{0}}10^{a_{1}−a_{0}−1}1 … 0^{a_{k−1}−a_{n−2}−···−a_{0}−n+1}10^{a_{n}−...−a_{0}−n}.

An arbitrary sequence σ_{0}, …, σ_{n} of strings from {0, 1}^{<ω} will be coded by a number k = [σ_{0}, …, σ_{n}], where k is the number which has base 3 representation 2^{⌢}σ_{0}^{⌢} ⋯ ⌢ 2^{⌢}σ_{n}. A sequence a_{0}, …, a_{n} of natural numbers will be coded by [a_{1}, a_{2}, …, a_{n}], where each a_{n} is given its binary representation.

Let ϕ_{e}^{A} be the e^{t}h partial recursive function with oracle A. We write ϕ_{e}^{A}(n) ↓ to mean that ϕ_{e}^{A}(n) exists (or converges ) and we write ϕ_{e}^{A}(n) ↑ to mean that ϕ_{e}^{A}(n) diverges . Then A′ (the Turing jump ) of A is {e : ϕ_{e}^{A}(e) ↓}. The degree a of a set A is written in boldface. The empty set is written as 0 and has degree 0 . The reader is referred to Soare [31] for basic definitions and facts about r.e. sets and degrees.

The Cantor-Bendixson derivative D(P) of a closed set P is the set of nonisolated points of P. The iterated Cantor-Bendixson derivative D^{α}(P) is defined for all ordinals α by the following transfinite induction. D^{0}(P) = P and, for any α,

D^{α+1}(P) = D(D^{α}(P).

For any limit ordinal λ,

D^{λ}(P) = ∩_{α<λ}D^{α}(P).

The Cantor-Bendixson rank of a countable closed subset P of 2^{ω} is the least ordinal α such that the α+1st derivative is empty. The (effective) Cantor-Bendixson rank of a point A ∈ {0, 1}^{ω} is the least ordinal α such that, for some Π_{1}^{0} subset P of {0, 1}^{ω}, the αth derivative of P is {A}.

The topology of ω^{ω} (and also of 2^{ω}) has a basis of intervals of the form I(σ) = {x : σ ≺ x}. Note that each interval is a clopen set and that any clopen set is just a finite union of intervals. This implies the following important observation. For any element x of a closed subset Q of 2^{ω}, x is in D(Q) if and only if for every clopen set U containing x, there is a point y different from x in U ∩ Q. Equivalently, x is not in D(Q) if and only if there is a clopen set U containing x such that U ∩ Q = {x} .

Another useful observation is the following: For any compact set P, D(P) is empty if and only if P is finite. (See Kuratowski [17, p. 76] for background on the derivative.)

We need the following well-known lemma, which is a simple consequence of König’s Infinity Lemma.

Lemma 1.1. For any x ∈ 2^{N}, x is recursive if and only if {x} is a Π_{1}^{0} class.

Theorem 2.15. There is an r. e. set A such that no set B of the same Turing degree as A belongs to any thin Π_{1}^{0} class.

Proof. Let (Φ_{e}, Γ_{e}, T_{e}) be an effective list of all triples with first two elements partial recursive {0, 1}-valued functionals and third entry a primitive recursive tree. We will construct an r. e. set A and recursive trees T′_{e} such that for each e we satisfy the requirement R_{e} represented by the e^{th} triple in one of the following ways:

(1)_{e}Φ_{e}(A) is not total

(2)_{e}Γ_{e}Φ_{e}(A) is not total

(3)_{e}Γ_{e}Φ_{e}(A) ≠ A

(4)_{e}Φ_{e}(A) ∉ [T_{e}]

(5)_{e}[T′_{e}] is a Π_{1}^{0} subclass of [T_{e}] which is not clopen in [T_{e}].

Our approach to satisfying (5)_{e} is as follows: We will (in the limit) try to define an increasing sequence of disjoint intervals [x_{e,i}, z_{e,i}) such that there is, for each i ≥ 1, an infinite branch of T_{e} extending Φ_{e}(A) ↾ x_{e,i} but not Φ_{e}(A) ↾ z_{e,i}. The idea is that if we cannot define one of these intervals or T_{e} has no such infinite branch then we will satisfy one of (1)_{e} − (4)_{e}. On the other hand, if we succeed in defining all of them and each contains an infinite branch of T_{e}, then we will define T′_{e} such that for every i ≥ 1

i) all nodes of T_{e} extending Φ_{e}(A) ↾ x_{e,2i+1} but not Φ_{e}(A) ↾ z_{e,2i+1} are on T′_{e} ii) T′_{e} contains no infinite branches extending Φ_{e}(A) ↾ x_{e,2i} but not Φ_{e}(A) ↾ z_{e,2i}.

In this case it is clear that we will satisfy (5)_{e}.

We consider first how to handle one requirement e but include in our description ways to accommodate the possible actions of other requirements. We divide up R_{e} into infinitely many requirements R_{e,i} for i ∈ ω. We think of R_{e,0} as trying for a “global” win by satisfying one of (1)_{e} − (4)_{e} and of R_{e,i} for i ≥ 1 as trying to correctly define the i^{th} interval [x_{e,i}, z_{e,i}) as described above. We will also define an auxiliary sequence of numbers y_{e,i} with x_{e,i} < y_{e,i} < z_{e,i}. Our construction proceeds by stages. At stage s we have an approximation A_{s} to A and approximations x_{e,i,s}, y_{e,i,s} and z_{e,i,s} to some of the numbers x_{e,i}, y_{e,i} and z_{e,i}. We follow the usual conventions that whenever we injure some requirement R_{e,i} by violating its restraint, we initialize it and all lower priority requirements by declaring them unsatisfied and making all the corresponding numbers undefined. We now define when each requirement requires action and the action it requires in each case. Requiring attention:

R_{e,i} for i ≥ 1 :

e.i.1) If x_{e,i,s} is undefined, set x_{e,i,s} = s.

e.i.2) If x_{e,i,s} and φ_{e,s}(x_{e,i,s}) are defined but y_{e,i,s} is not, choose a value for y_{e,i,s} ≥ φ(x_{e,i,s}) and impose restraint preserving A ↾ y_{e,i,s} +1. (For a single requirement, we could simply set y_{e,i,s} = φ(x_{e,i,s}). When we consider more requirements we will have to impose other conditions to assure compatibility.)

e.i.3) If y_{e,i,s} and γ_{e,s}(y_{e,i,s} + f(e, i)) are defined but z_{e,i,s} is not, set z_{e,i,s} = γ_{e,s}(y_{e,i,s} + f(e, i)), impose restraint preserving A ↾ z_{e,i,s} and declare R_{e,i} satisfied. Here f(e, i) is some recursive function that will be chosen so as to leave room to act for other requirements. In the case of a single requirement, it can be taken to be identically 0.)

R_{e,0} :

e.0.1) If, for some i, Γ_{e,s}(Φ_{e,s}(y_{e,i,s})) ↓= 1 but y_{e,i,s} ∉ A, we impose restraint preserving A ↾ γ_{e,s}φ_{e,s}(y_{e,i,s}) and declare R_{e,i} satisfied for all i.

e.0.2) If we see that, for some i, Γ_{e,s}(Φ_{e,s}(y_{e,i,s})) ↓= 0 but T_{e} has no extendible nodes extending Φ_{e,s}(A_{s}) ↾ x_{e,i,s} but not Φ_{e,s}(A_{s}) ↾ z_{e,i,s}, we put y_{e,i,s} into A, impose restraint preserving A ↾ φ_{e,s}(x_{e,i,s}) and declare R_{e,i} satisfied for all i.

Of course, at stage s of the construction we simply act for R_{e} according to the above prescriptions for the highest priority requirement which is not currently satisfied for which there is something we can do.

Note that (by the construction), if at stage s y_{e,i,s} and z_{e,i,s} are defined, then so is Φ_{e,s}(A) ↾ z_{e,i,s}. In fact, once they are defined at s they and A ↾ γ_{e,s}(φ_{e,s}(y_{e,i,s})) remain fixed until R_{e,i} is initialized at some t > s. If they are ever redefined at u > t, they are all then defined with values bigger than t.

Definition of T′_{e} at stage s : First, for each i for which x_{e,2i,s} and z_{e,2i,s} are defined, we declare all nodes on T′_{e} extending Φ_{e,s}(A) ↾ x_{e,2i,s} but not Φ_{e,s}(A) ↾ z_{e,2i,s} terminal in T′_{e}. Next, we put on T′_{e} every node in T_{e} of length at most s which is not above any node already declared terminal in T′_{e}. It is clear that T′_{e} is a recursive subtree of T_{e}.

The verifications now proceed in the standard way. Suppose that each R_{e,i} is injured (and so initialized) at most finitely often. Moreover, we assume that no requirement can injure R_{e,0}. (For the case of a single requirement, these facts are, of course, obvious.) We claim that we satisfy one of (1)_{e} − (5)_{e}.

The crucial point of the analysis is considering what happens if we ever act for R_{e,0}. By our assumptions, the restraint we now impose is never violated. Thus if we acted as in (e.0.1) above, we clearly satisfy (3)_{e}. Suppose then that we act as in (e.0.2) at some stage s. In this case, A_{s} ↾ φ_{e,s}(x_{e,i,s}) = A ↾ φ_{e,s}(x_{e,i,s}) because of the restraint we impose at stage s. Thus Φ_{e,s}(A_{s}) ↾ x_{e,i,s} is an initial segment of Φ_{e}(A). Now if Φ_{e,s}(A_{s}) ↾ z_{e,i,s} is also an initial segment of Φ_{e}(A), then Γ_{e}(Φ_{e}(A))(y_{e,i,s}) = Γ_{e,s}(Φ_{e}(A))(y_{e,i,s}) = 0 but A(y_{e,i,s}) = 1 and we again satisfy (3)_{e}. Thus, if Φ_{e}(A) is total, it cannot extend Φ_{e,s}(A_{s}) ↾ z_{e,i,s}. In particular, it cannot lie on T_{e} as by the hypothesis of our action T_{e} has no infinite branches extending Φ_{e,s}(A_{s}) ↾ x_{e,i,s} but not Φ_{e,s}(A_{s}) ↾ z_{e,i,s}. In this case we satisfy either (1)_{e} or (4)_{e}.

Thus, in either case of acting for R_{e,0}, we see that we guarantee one of (1)_{e}−(4)_{e}, R_{e,i} is permanently satisfied for every i and we therefore never again act for any R_{e,i}. We therefore assume that we never act for R_{e,0}.

Again by our assumptions that each R_{e,i} is initialized at most finitely often, it is easy to see that each acts at most finitely often and that the x_{e,i,s}, y_{e,i,s} and z_{e,i,s} all go to limits (say x_{e,i}, y_{e,i} and z_{e,i} respectively or possibly they are undefined in the limit) as s goes to infinity. In particular, suppose that we never act for any requirement of higher priority than R_{e,i} after stage s and that x_{e,j,s}, y_{e,j,s} and z_{e,j,s} are defined for all j < i. (They are then fixed at these values for all t ≥ s by construction.) It is clear that we must define x_{e,i,s+1} = s + 1 (following (e.i.1) of the instructions above) if it is not already defined. Once defined after stage s it remains constant by construction say at x_{e,i}. If φ_{e,t}(x_{e,i}) is never defined for any t > s + 1, then Φ_{e}(A)(x) is undefined and we satisfy (1)_{e}. If φ_{e,t}(x_{e,i}) is eventually defined then it, and so y_{e,i,t}, are eventually constant (we act for (e.i.2)) at say φ_{e}(x_{e,i}) and y_{e,i} respectively. Now in this case if γ_{e,t}(y_{e,i} + f(e, i)) is never defined, then Γ_{e}(Φ_{e}(A)) is not total and we satisfy (2)_{e}. If it, and so z_{e,i,t}, is eventually defined (we act for (e.i.3)), they too remain constant thereafter say at z_{e,i} and R_{e,i} is satisfied at every later stage. Thus we either satisfy one of (1)_{e} − (4)_{e} or successfully define x_{e,i}, y_{e,i} and z_{e,i} for every i. In the latter case, the assumption that we never act for R_{e,0} guarantees that there is, for each i, an infinite branch on T_{e} which extends Φ_{e}(A) ↾ x_{e,i} but not Φ_{e}(A) ↾ z_{e,i} as desired.

It only remains to verify that in this last case (i. e. we satisfy every R_{e,i} for i ≥ 1 but not R_{e,0}) :

i) T′_{e} contains, for every i ≥ 1, every node on T_{e} extending Φ_{e}(A) ↾ x_{e,2i+1} but not Φ_{e}(A) ↾ x_{e,2i+2} and

ii) there are no infinite branches on T′_{e} extending Φ_{e}(A) ↾ x_{e,2i} but not Φ_{e}(A) ↾ z_{e,2i} for any i ≥ 1. If there is only the one requirement R_{e} to consider, this is obvious from our definition of T′_{e}. The problem is that with other requirements included some y_{d,j,s} may be put into A and so force Φ(A) to extend a node that we have already declared to be non-extendible in T′_{e}. The crux of combining requirements is then to choose the points y_{d,j} so that this cannot happen. It suffices to choose them inside the intervals (y_{e,2i+1,s}, y_{e,2i+1,s} + f(e, 2i + 1)) as the changes in Φ_{e}(A) that can be forced by such a y entering A are the same as those produced by y_{e,2i,s} entering A. That is, we can make Φ_{e}(A) extend Φ_{e}(A) ↾ x_{e,2i+1,s} but not Φ_{e}(A) ↾ x_{e,2i+2,s}. These nodes, however, have all been kept in T′_{e} by definition.

Combining requirements:

Consider the requirements R_{0} and R_{1}. The first question for R_{1} to consider is whether R_{0} has a finitary or infinitary outcome. (By an infinitary outcome for R_{e} we mean that x_{e,i}, y_{e,i} and z_{e,i} are defined for every i ≥ 1. Otherwise we say that its outcome is finitary.) If the outcome for R_{0} is finitary, then it succeeds by satisfying one of (1)_{0} − (4)_{0} and never acts after some stage s_{0}. In this case, R_{1} simply begins acting anew at s_{0}. It then succeeds just as if it were the only requirement. The coordination problems arise only if R_{0} has an infinitary outcome. We use the standard tree construction to guess at the nature of the outcomes for the requirements R_{e}. As usual, above the guess that R_{0} never acts after s_{0}, we simply start the action for R_{1} at s_{0}. We must now describe the action for R_{1} under the assumption that R_{0} eventually defines every one of its intervals. (Of course we are defining different subtrees T′_{1} as well as different sequences of triples x_{1,j}, y_{1,j} and z_{1,j} for each guess as to the outcome of R_{0}.) The only detail we have to specify is the choice of y_{1,j} when we act for (1.j.2). As we are assuming that R_{0} has an infinitary outcome, we may wait to define y_{1,j} until we have a new x_{0,2i+1,s}, y_{0,2i+1,s} and z_{0,2i,s} defined for some i ≥ ⟨1, j⟩. We can then choose y_{1,j} to be y_{0,2i+1,s} + c for some c < f(0, 2i + 1). (In this case, with only two requirements, we could simply take c = 1.)

Now the only way R_{0} can act to put a number into A is to satisfy R_{0,0}. Such action will, however, guarantee a finitary outcome for R_{0}. Thus if the outcome of R_{0} is infinitary, R_{1} is in the same situation as R_{0} and we have no additional concerns about R_{1}. We must argue however that the actions of R_{1} do not interfere with the satisfaction of R_{0}. At the most basic level, R_{1} can act to put a number y_{1,j,s} into A only once for it will then satisfy R_{1,0} and remain satisfied forever. (It can never be injured as by our assumption R_{0} never puts any element into A.) When this happens, it may injure some R_{0,i}. By our choice of the y_{1,j,s}, however, it cannot injure any with i < ⟨1, j⟩. The others can be injured and so reset at most once by action by R_{1}. Thus the assumptions about injuries made in the analysis of the success of R_{0} in the case of an infinitary outcome remain valid: all the x_{0,i,s}, y_{0,i,s} and z_{0,i,s} are eventually defined and constant and for each i there is an infinite path on T_{0} extending Φ_{0}(A) ↾ x_{0,i} but not Φ_{0}(A) ↾ z_{0,i}. It only remains to verify that Φ_{0}(A) is a path on T′_{0}. Indeed we wish to argue by induction that Φ_{0}(A) ↾ x_{0,i} and Φ_{0}(A) ↾ z_{0,i} are on T′_{0} and that all nodes on T_{0} extending Φ_{0}(A) ↾ x_{0,2i+1} but not Φ_{0}(A) ↾ z_{0,2i+1} are on T′_{0}. As it is clear that there are no infinite branches on T′_{0} extending Φ_{0}(A) ↾ x_{0,2i} but not Φ_{0}(A) ↾ z_{0,2i} by the definition of T′_{0}, this will suffice to guarantee that we satisfy (5)_{0}. Suppose then by induction that no requirement R_{0,j} for j < i is ever injured after stage s_{i} (and so x_{0,j,t}, y_{0,j,t} and z_{0,j,t} are constant for t > s at say x_{0,j}, y_{0,j} and z_{0,j} respectively for j < i) and that Φ_{0}(A) ↾ z_{0,j} is on T′_{0} for all j < i. From the stage at which z_{0,i−1} was last defined until z_{0,i,s} is first defined all nodes on T_{0} extending Φ_{0}(A) ↾ z_{0,i−1} are put on T′_{0} and no nodes extending Φ_{0}(A) ↾ z_{0,i−1} are declared terminal on T′_{0} by definition. Suppose now that that R_{0,i} first acts via (0.i.3) at stage s > s_{i} to define z_{0,i,s}. If i is even then the only way R_{0,i} could now be injured would be for us to act for R_{0,0} by putting y_{0,i,s} into A. As this would guarantee a finitary outcome for R_{0} contrary to hypothesis, R_{0,i} is never injured. Thus Φ_{0}(A) ↾ z_{0,i} = Φ_{0,s}(A_{s}) ↾ z_{0,i,s}. As this node is on T_{0} (or again we would have a finite win via (4)_{0}), it is on T′_{0} by definition. (Of course, the nodes extending Φ_{0}(A) ↾ x_{0,i} but not Φ_{0}(A) ↾ z_{0,i} are declared terminal on T′_{0}.) Suppose then that i is odd so that we may have various y_{d,j} in the interval from φ(x_{0,i}) to z_{0,i}. However, by construction there are no such numbers below φ(x_{0,i,s}) which will therefore remain fixed. Of course, if none of the y_{d,j} in this interval ever enter A, we are done as everything remains fixed and the definition of T′_{0} keeps in it everything up to Φ_{0}(A) ↾ z_{0,i} which is on T_{0}. Thus our only concern is that some y_{d,j}(d ≠ 0) may enter A (and so injure the requirement and change Φ_{0}(A) ↾ z_{0,i,s}). The worry is that while we are waiting for such an injury to occur, we are continuing to define more triples and hence to declare various nodes terminal in T′_{0}. Perhaps then when the injury occurs, Φ_{0}(A) changes to extend such a node. The crucial point is that, on the one hand, all such terminal nodes extend Φ_{0}(A) ↾ z_{0,i,s} by the definition of the triples and T′_{0}. On the other hand if any y_{d,j} is put into A and we later have Φ_{0}(A) extending Φ_{0}(A) ↾ z_{0,i,s} we would have a finite win satisfying (3)_{0} as we would have Γ_{0}(Φ_{0}(A))(y_{j,d}) = 0 but A(y_{j,d}) = 1.

The situation for more requirements is handled in the same way. We always choose y_{d,j} to be in the same intervals as y_{e,2i} for some i > [d, j] for each e < d which has an infinitary outcome. The function f is simply chosen so as to leave enough room. □

On the other hand, it follows from the results of Downey-Jockusch-Stob [10] that all array non-recursive (a.n.r. ) sets and hence all non − low_{2} degrees contain thin points. Note that the r. e. set A of Theorem 2.15 can be made to have low_{2} degree by making it 1-topped.

In contrast with the previous theorem, we now give a result which implies that there are many degrees containing sets of thin rank one.

Theorem 2.16. Let A and C be r. e. sets such that the Turing degree of A is strictly below the Turing degree of C. Then there is a set B with Turing degree strictly between those of A and C and a thin Π_{1}^{0} class P with D(P) = {B}.

Proof. Let A and C be r. e. sets with the degree of A strictly below the degree of C. By the Sacks density theorem, we may assume that A is non-recursive. Now let A be the union of uniformly recursive sets A^{s} and let C be the union of uniformly recursive sets C^{s}. To simplify the argument, we may assume that A ⊂ C. (This can be done by taking a set which has a copy of A on the even numbers and a copy of C on the odd numbers.)

Let T_{0}, T_{1}, … be an effective enumeration of the primitive recursive trees on 2^{<ω} and let P_{e} = [T_{e}] for each e.

We will construct a set B = {b_{0} < b_{1} < ⋯ } by a Δ_{2}^{0} approximation B^{s} and a recursive tree T so that B and P = [T] satisfy the conclusion of the theorem.

The construction will be a finite injury priority argument combining ideas from the basic construction given in the proof of Theorem 2.2 with the construction given in Theorem 2.9. We are going to construct the set B in stages, B^{s} = {b_{0}^{s} < b_{1}^{s} < ⋯ b_{k(s)}^{s}} ⊂ {0, 1, …, s − 1}. Thus the characteristic function of B will be the limit of the sequence β^{s} =< b_{0}^{s}, …, b_{k(s)}^{s}, s >, which is just the restriction of the characteristic function of B^{s} to s. At the same time we will construct the recursive tree T in stages, so that at stage s, we will have defined the tree T^{s} = {σ ∈ T : lh(σ) ≤ s}. This will ensure that T is recursive. Then B = lim_{s} B^{s} will be the unique infinite set in the Π_{1}^{0} class P = [T].

We will make A recursive in B by ensuring, for each n, the n^{th} A-requirement, as follows:

(1)_{e}: For any n, n ∈ A if and only if n ∈ A^{b_{n}}.

Let us say that σ =< x_{0}, …, x_{k}, x > is A − correct at stage s if for all a ≤ k, a ∈ A^{s} ⟺ a ∈ A^{x_{a}} and let us say that σ is A-correct if σ is A-correct at all stages s. (In particular, 0^{s−1⌢}1 is A-correct at stage s − 1 for all s.) Finally, let us say that a set X is A − correct, if X ↾ n is A-correct for all n. It is clear that if X is infinite and is A-correct, then A is recursive in X. The definition of T^{s+1} will ensure that every set X ∈ P is A-correct by making sure that, for every s, every string σ ∈ T of length s + 1 is A-correct at stage s. In particular, if β^{s} is not A-correct at stage s, then we will revert back to β^{t}, where t is the most recent stage prior to s such that β^{t} is A-correct at stage s.

We will obtain D(P) = {B} as follows. First, we ensure that D(P) ⊂ {B} by ensuring that at stage s + 1, β^{s+1} is the only possible string ending in ”1” which is in T^{s+1} \ T^{s}. To show that D(P) = {B}, it then suffices to show that P is infinite, which the construction will also ensure.

We will make P thin as in Theorem 2.2 by ensuring, for any e, the e^{th} thinning requirement, as follows:

(2)_{e}: If B ∈ P_{e}, then P \ P_{e} is finite.

Taken together with the fact that D(P) ⊂ {B}, this will imply that P is thin (in fact, minimal) by the same argument as in Theorem 2.2. There is a natural notion of e − state for the thinning requirement which is analogous to the usual e-state notion from the maximal set construction. Let us define the s-state of a sequence σ to be the sequence (i_{0}, …, i_{s}) ∈ {0, 1}^{s+1} where i_{e} = 1 if and only if σ ∈ T_{e}. We say that σ has a better s-state than τ if the s-state of σ precedes the s-state of τ in the usual lexicographic ordering. Thus we will satisfy the thinning requirements by choosing β^{s+1} at stage s + 1 to have the best possible s-state.

The final complication in the construction is the requirement that B is recursive in C. This means that the move from β^{s} to β^{s+1} can only take place when permitted by C in a manner described below. Then we will demonstrate the thinning requirements by showing that if one of them fails, then the set C would be recursive in A.

Now once we have shown that P is thin and that D(P) = {B}, it will follow that B is not recursive and therefore must be infinite, which will finally imply that A is recursive in B.

We begin the construction at stage 1 by setting β^{1} = (1) and T^{1} = {∅, (0), (1)}. Now suppose we have completed the construction as far as stage s. Then we will

have a tree T^{s} of strings of length ≤ s, all of which are A-correct at stage s − 1 and a unique finite path β^{s} ∈ T^{s} which has length s and ends in a 1.

There are two cases in the definition of B^{s+1}.

First, suppose that β^{s} is A-correct at stage s. Then we will simply try to improve the s-state at stage s + 1. Let us say that σ is eligible at stage s + 1 if the following three conditions are satisfied.

(i) lh(σ) = s and σ ∈ T^{s}.

(ii) σ is A-correct at stage s.

(iii) For all i ≤ s, if σ(i) ≠ β^{s}(i), then there is a c ≤ i such that c ∈ C^{s} \ C^{s−1}. Clause (i) is needed to ensure that T is actually a tree. Clause (ii) will ensure

that all infinite paths in the tree T are A-correct, thus ensuring that A is recursive in any such infinite path. Clause (iii) is the usual permitting requirement, which will ensure that the set B which is being constructed is recursive in C, as well as ensuring that the construction converges.

Now let η be the best s-state of those sequences eligible at stage s + 1 and let σ be the lexicographically least eligible sequence among those with s-state η. Now we let β^{s+1} = σ^{⌢}1 and we let the tree T^{s+1} consist of β^{s+1} together with all strings τ^{⌢}0 such that τ ∈ T^{s} and τ is A-correct at stage s.

Second, suppose that β^{s} is not A-correct at stage s. Let t be the largest number less than s such that β^{t} is A-correct at stage s. Then we modify the notion of eligibility at stage s + 1 defined above by changing the permitting requirement to the following.

(iii)’ For all i ≤ s, if σ(i) ≠ β^{s}(i), then there is a c ≤ i such that c ∈ C^{s} \ C^{t}. We need to show that there is at least one sequence σ which is eligible at stage

s+1 under this definition. Let σ^{s} = β^{t}0^{s−t} and note that σ^{s} is A-correct at stage s, whereas β^{t+1} is A-correct at stage t but is A-incorrect at stage s. Now σ^{s} certainly has the right length and is in T^{s} since it is an A-correct extension by 0’s of an element (β^{t}) of T. The fact that β^{t} is A-correct at stage s + 1 implies that σ^{s} is also A-correct at stage s + 1. The permitting requirement is satisfied by the following argument. Let i be least such that σ^{s}(i) ≠ β^{s}(i). We claim that there is a c ≤ i such that c ∈ C^{s} \ C^{t}. There are two possibilities. First, suppose that i < t.

Then there had to be some stage q + 1 with t ≤ q < s where β^{q+1} first differed from β^{t} at i. Since β^{t} is of course A-correct at all stages q ≤ s, it follows that there is some c ≤ i such that c ∈ C^{q} \ C^{s} which permitted this change at stage q + 1. Second, suppose that i ≥ t. Now note that β^{t+1} is A-incorrect at stage s but was A-correct at stage t. Let b = b_{e}^{t+1} be the e^{th} 1 in the sequence β^{t+1}. Then there is some a ∈ A^{s} \ A^{t} such that a ∉ A^{b} and therefore a ∈ C^{s} \ C^{t}, since by assumption A is just the set of even numbers in C. Since lh(β^{t+1}) = t, it follows that b_{a}^{t+1} ≤ t, so that a ≤ t < i.

Now at stage s + 1, we again choose the best s-state of any eligible sequence and then choose the lexicographically least eligible sequence σ having that s-state. Then we let β^{s+1} = σ^{⌢}1 and define T^{s+1} as above.

Observe that in both cases, we have extended all A-correct nodes τ in T^{s} by at least one node (τ^{⌢}0) in T^{s+1} and we have abandoned all nodes which are not A-correct at stage s.

Let T = ∪_{s}T^{s} and let P = [T].

The construction will ensure that β^{s} is always A-correct at stage s−1. However, we actually need stages s such that β^{s} is A-correct. Let us say that a stage s is A-correct if β^{s} is A-correct. Then we have the following.

Claim 1. There are infinitely many A-correct stages.

Proof of Claim 1: Let us say that s is an A-true stage if any sequence σ of length s which is A-correct at stage s is A-correct. It follows that β^{s} is A-correct for any A-true stage s. It clearly suffices now to show that there are infinitely many A-true stages. We do this as follows. For any t, let a be the least element of A which comes in after stage t and choose s so that so that a ∈ A^{s} \ A^{s−1}. Now suppose that σ =< b_{0}, …, b_{k} > is A-correct at stage s and b_{k} = s. Observe that we must have k ≤ a since a ∈ A^{s} \ A^{s−1} and, for all x ≤ a, x ∈ A^{s} ⟺ x ∈ A^{b_{x}}. Then the choice of a implies that, for all x ≤ a, x ∈ A ⟺ x ∈ A^{s}, so that σ is A-correct. □

Next we show that the construction converges.

Claim 2. The sequence β^{s} converges to a limit.

Proof of Claim 2: For any n, let s > n be a correct stage large enough so that A^{s} ↾ n = A ↾ n. We claim that β^{q+1} ↾ n = β^{q} ↾ n for all q ≥ s. This is because of the permitting clause of the construction. Observe that for any q ≥ s, the most recent stage t such that A^{t} is A-correct at stage t is no less than s, since A^{s} is completely A-correct. Thus if β^{q+1} differs from β^{q} below n, then there would have to be some i < n such that i ∈ A^{q} \ A^{s}, which contradicts the choice of s. □

Now let β = lim_{s} β^{s} and let B = {n : β(n) = 1}.

Claim 3. D(P) = {B}.

Proof of Claim 3: For any s, let B_{s} = β^{s⌢}0^{ω}. Then B = lim_{s} B_{s} and B_{s} ∈ P for all A-correct stages s. Since β^{s}(s − 1) = 1, it follows that the B_{s} are distinct. This shows that B ∈ D(P). Now let X ∈ P be different from B. Let X(n) ≠ B(n) and let s be large enough so that β^{s}(n) has converged by stage s. It follows that X ↾ s is not an initial segment of β^{t} for any t > s, so that X ↾ s ∗ 0^{ω} is the only possible infinite path through P which extends X ↾ s. This now implies that X is isolated in P. □

Claim 4. For each e, the sequence of e-states of the A-correct stages β^{s} goes to a limit.

Proof of Claim 4: Since there are only finitely many different e-states, it clearly suffices to prove that the e-states of the A-correct stages are non-decreasing. We will prove the stronger statement that if β^{s} is A-correct and e ≤ s ≤ t, then β^{s} has e-state no worse than that of β^{t}. The proof is by induction on t. The case of t = s is obvious. Suppose now that β^{t} has e-state no worse than β^{s} and consider what happens in the construction at stage t + 1. If β^{t} is A-correct at stage t, then β^{t} is eligible at stage t+1 and it immediately follows that β^{t+1} has e-state no worse than that of β^{t} and therefore no worse than that of β^{s}. If β^{t} is not A-correct at stage t, then we recall the definition of σ^{t} = β^{q}0^{t−q}, where β^{q} is the most recent A-correct stage before s. Since s ≤ t and s is an A-correct stage, it follows that s ≤ q, so that β^{q} has e-state no worse than that of β^{s}. Now σ^{t} clearly has e-state no worse than that of β^{q} and is eligible at stage t + 1. It follows from the construction that β^{t+1} has e-state no worse than that of β^{s}. □

Claim 5. For any e, if B ∈ P_{e}, then P \ P_{e} is finite.

Proof of Claim 5: The proof is by induction on e. Suppose therefore that Claim 5 is true for all i < e. Thus there is an n such that every infinite extension X of B ↾ n in P has the same (e − 1)-state as B. By Claims 2 and 4, we can fix an s large enough so that β^{t} ↾ n = β ↾ n for all t ≥ s and such that β^{t} has the same e-state as B for every A-correct stage t ≥ s. Now assume that B ∈ P_{e} but, by way of contradiction, that there are infinitely many members of P which are not in P_{e}. Then, for any c ≥ s, there is an infinite path X ∈ P \ P_{e} such that X ↾ c = B ↾ c. Now let q be the least such that X ↾ q ∉ T_{e}. (Note that q > c, since B ∈ P_{e}.) Fix an A-correct stage t ≥ q and let y be least such that X(y) ≠ B(y). Note that y > c. It is clear that we can never have X ↾ (t + 1) = β^{t+1}, since X ↾ (t + 1) must be A-correct and therefore have the same e-state as B. Furthermore, X ↾ t cannot even be eligible at any A-correct stage t + 1 > q, since then the e-state of β^{t+1} would again have e-state better than that of B. We claim that X ↾ t can never be eligible even if β^{t+1} is not A-correct. To see this, consider what happens at the next A-correct stage r + 1 > t + 1. It follows from the permitting clause (iii)’ that (X ↾ t)^{⌢}0^{r−t} would be eligible at stage r + 1, so that the e-state of β^{r+1} would be no worse than that of X ↾ t. But X ↾ t and β^{r+1} have the same (e − 1)-state and X ↾ t ∉ T_{e}, which implies that β^{r+1} ∉ T_{e}, contradicting the assumption that β^{r+1} must have the same e-state as B.

We will now argue that C is recursive in A, contradicting the original assumption that A has Turing degree strictly below that of C. Let a number c ≥ s be given. Here is how we test c for membership in C. Use oracle A to compute the shortest (and lexicographically least) A-correct string γ ∈ T \ T_{e} such that c ≤ lh(γ) = q and γ ↾ n = B ↾ n. (Such a γ exists by the above argument.) Then it follows from the argument above that γ^{⌢}0^{t−q} is not eligible at any stage t > q. This means that, for all d ≤ y, d ∉ C^{t} \ C^{t−1}. Since this is true for all t > q, it follows that for all d ≤ y, d ∈ C if and only if d ∈ C^{q}. It follows that in particular c ∈ C if and only if c ∈ C^{q}, which completes the computation of whether c ∈ C.

This establishes Claim 5. □

Claim 6. P is thin and minimal.

Proof of Claim 6: It follows from Claim 5 as in the proof of Theorem 2.9 that P is thin. It then follows from Claim 3 and Lemma 2.1 that P is also minimal. □

Claim 7. A is recursive in B.

Proof of Claim 7: Since P is minimal by Claim 6 and D(P) = {B} by Claim 3, it follows from Lemma 2.1 that B is not recursive. Thus B is infinite. Now let b_{e} be the e^{th} element of B in increasing order. Then e ∈ A if and only if e ∈ A^{b_{e}}. □

Claim 8. B is recursive in C.

Proof of Claim 8: This is a direct consequence of the permitting clause of the construction. Let a number b be given. Here is how we use oracle C to test b for membership in B. Recall that A is recursive in C and note that the set of s such that A^{s} is A-correct is of course recursive in A and that, by Claim 1, there are infinitely many A-correct stages. Let s be large enough so that C ↾ (b + 1) = C^{s} ↾ (b + 1) and find a A-correct stage β^{t} with t > s. It follows immediately from the permitting clause of the construction that b ∈ B if and only if β^{t}(b) = 1. □

Finally, we want to get the degree of B strictly between the degrees of A and C. To do this, we use the Sacks density theorem to obtain r. e. sets A′ and C′ such that deg(A) < deg(A′) < deg(C′) < deg(C) and then use the argument just given to construct B with degree between the degrees of A′ and C′. □

Theorem 2.17. There is a minimal degree a < 0′ such that no set A of degree a is a member of any thin Π_{1}^{0} class.

Proof. As usual we let (Φ_{e}, T_{e}) be an effective list of all pairs where the first element is a partial recursive {0, 1} valued functional and the second is a primitive recursive tree. We will construct a set A by a procedure recursive in 0′ following the basic format of the standard construction of a minimal degree below 0′ as can be found in Lerman [20, Ch. IX]. We will, however, have an extra step in our construction to guarantee that, if Φ_{e}(A) is total and non-recursive and [T_{e}] is thin, then Φ_{e}(A) is not a member of [T_{e}]. To facilitate this step we stress some standard notational conventions. We assume that all partial recursive functionals Φ_{e}^{σ} are defined on initial segments of length at most that of σ. We also define a procedure for forming a subtree of a given partial recursive tree which will leave room to split [T_{e}] in the sense of showing that it is not thin.

Definition. (i) Two binary strings σ and τ e-split at x if Φ_{e}^{σ} ↾ x = Φ_{e}^{τ} ↾ x but Φ_{e}^{σ}(x) ↓≠ Φ_{e}^{τ}(x) ↓ .

(ii) If T is a partial recursive tree we define a partial recursive subtree S of T called the e-splitting subtree of T which we denote by SP(T,e) by induction as usual: S(∅) = T (∅). If S(σ) = T (τ), then S(σ^{⌢}i) = T (τ_{i}) where τ_{0}, τ_{1} is the first pair of strings extending τ (in some standard order for searching) such that T (τ_{i}) e-split. If the trees are clear from the context, we let x_{σ} be the point at which T (τ_{i}) e-split.

(iii) If T is a partial recursive tree, we define a partial recursive subtree S of T called the even subtree of T and denoted by E(T) by induction: S(∅) = T (∅). If S(σ) = T (τ), then S(σ^{⌢}i) = T (τ^{⌢}0^{⌢}i).

(iv) We use Ext(T, σ) to denote the full subtree of T above σ : Ext(T, τ) = T (σ^{⌢}τ) for every τ.

Construction: We proceed recursively in 0′. At each stage s of the construction we will have defined a number k(s), a string α_{s} and sequences P_{j,s} and σ_{j,s} for j ≤ k(s) of partial recursive trees and binary strings respectively such that P_{j,s}(σ_{j,s}) = α_{s} for each j ≤ k(s). For every s, P_{0,s} is the identity tree. For each j < k(s), P_{j+1,s} will be either E(SP (P_{j,s}, j)) or Ext(P_{j,s}, σ) for some σ. If P_{j+1,s} = E(SP (P_{j}, j)), then we let τ_{j,s} be such that SP (P_{j,s}, j)(τ_{j,s}) = α_{s}. The strings α_{s} will be increasing in s and their union will be the characteristic function of our set A. We begin the construction by setting k(0) = 0, α_{0} = ∅, P_{0,0} = identity tree and σ_{0,0} = ∅.

Stage s + 1 : Let j < k(s) be least such that P_{j+1,s}(σ_{j+1,s}^{⌢}i) is undefined for i = 0 or 1. (Note that by the requirement of leastness, P_{j+1,s} cannot be a full subtree of P_{j,s} and so must be E(SP (P_{j,s}, j)).)

Case 1: If there is no such j, set k(s + 1) = k(s) + 1 and P_{k(s+1),s+1} = E(SP (P_{k(s),s}(σ_{k(s),s}), k(s))).

Case 2: If there is such a j, let n < j be least such that the following two conditions hold:

(1) P_{n+1,s} = E(SP (P_{n,s}, n))

(2) Φ_{n}^{SP (P_{n,s},n)(μ)} ↾ x + 1 is not an extendible node in T_{n} for μ = τ_{n,s}^{⌢}i or μ = τ_{n,s}^{⌢}0^{⌢}i and i = 0 or 1 and x is the point of n-splitting associated with the definition of SP (P_{n,s})(μ).

Case 2a: If there is no such n, set k(s+1) = j+1. As P_{j+1,s} = E(SP (P_{j,s}, j)) and P_{j+1,s}(σ_{j+1,s}^{⌢}i) is undefined, SP (P_{j,s}) is undefined at μ = τ_{n,s}^{⌢}i or τ_{n,s}^{⌢}0^{⌢}i. Let σ be such that P_{j,s}(σ) = SP (P_{j,s}, j)(μ) and set P_{k(s+1),s+1} = Ext(P_{j,s}, σ).

Case 2b: If there is such an n, set k(s + 1) = n + 1 and let P_{s} = Ext(P_{n,s}, ν) where P_{n,s}(ν) = SP (P_{n,s})(μ) for a μ satisfying the defining condition (2) for n.

In every case we set α_{s+1} = P_{k(s+1),s+1}(∅). For j < k(s+1), we let P_{j,s+1} = P_{j,s}. We can now choose σ_{j,s+1} for j ≤ k(s+1) such that P_{j,s+1}(σ_{j,s+1}) = α_{s+1} for every j ≤ k(s + 1) to complete step s of the construction.

Verifications: As in the standard construction of a minimal degree below 0′, the trees P_{j,s} are each eventually constantly equal to a fixed tree P_{j} and A lies on P_{j} for every j. The crucial point is that, by construction, once the tree P_{j,s} has reached a limiting value P_{j}, P_{j+1,s} can be defined once as E(SP (P_{j})) via Case 1 and then can change at most once to Ext(P_{j}, σ) for some σ via Case 2a or 2b. Once it has changed in this way, it remains constant.

The verification that A is of minimal degree is essentially the same as in the standard construction. To consider Φ_{e}(A) look at the limit tree P_{j+1} for a j such that Φ_{j} = Φ_{e} and T_{j} = identity tree. When P_{j+1,s} is first defined after P_{j,s} has reached its final value (say at s_{0}), it is defined via Case 1 as E(SP (P_{j}, j)). As every node is extendible on T_{j}, we never alter P_{j+1} as in Case 2b of the construction. Thus P_{j+1} = E(SP (P_{j}, j)) if and only if E(SP (P_{j}, j))(σ_{j,s}^{⌢}i) is defined for i = 0, 1 at every s > s_{0}. In this case A lies on E(SP (P_{j}, j) and so on SP (P_{j}, j). As SP (P_{j}, j) is a j-splitting tree, the standard arguments show that if Φ_{j}(A) = Φ_{e}(A) is total, it is of the same degree as A. On the other hand, if P_{j+1,s} is set equal to Ext(P_{j}, σ) at some stage s, then SP (P_{j}) is undefined at μ^{⌢}i where SP (μ) = α_{s+1}. In this case we argue as usual that if Φ_{e}(A) is total, it is recursive as there are then no e-splits in P_{j+1}. Finally, we could have taken steps in the construction to guarantee that A is not recursive by an explicit diagonalization. This is, however, not necessary by Posner’s Lemma (see [20, p. 192]).

We must now argue that if Φ_{j}(A) is total and non-recursive then either it is not on T_{j} or [T_{j}] is not thin. Suppose P_{j+1,s} is defined for the first time at s_{0} after P_{j,s} has reached its limit P_{j}. It is defined as E(SP (P_{j}, j)) and, if Φ_{j}(A) is total and nonrecursive, we can see from the previous argument that it can never be changed by an instance of Case 2a in the construction. Thus if we ever set P_{j+1,s} = Ext(P_{j}, σ) for s > s_{0}, it must be by an application of Case 2b of the construction. In this case the construction guarantees that Φ_{j}(A) is not on T_{j}. Thus we may assume that we are never in this case and so that P_{j+1,s} = E(SP (P_{j}, j)) and that P_{j+1,s}(σ_{j+1,s}^{⌢}i) and SP (P_{j}, j)(τ_{j,s}^{⌢}i) are defined for every s > s_{0}. For each such s, let x_{s} = x_{τ_{j,s}} be the point at which SP (P_{j}, j)(τ_{j,s}^{⌢}0) and SP (P_{j}, j)(τ_{j,s}^{⌢}1) j-split. As we are never in the second case of the construction, Φ_{j}(SP (P_{j}, j)(τ_{j,s}^{⌢}i)) ↾ x_{s} + 1 is extendible in T_{j} for i = 0, 1. They are distinct nodes in T_{j} by the definition of being a j-splitting. We can thus demonstrate that [T_{j}] is not thin by considering a subtree T′_{j} defined by making all nodes of the form Φ_{j}(SP (P_{j}, j)(τ^{⌢}1)) ↾ x_{τ} + 1 with τ of even length non-extendible in T′_{j}. As SP (P_{j}, j) is a partial recursive tree, this set of nodes is r. e. and so such a T′_{j} can be defined as a recursive tree. As α_{s} = SP (P_{j}, j)(τ_{j,s}) is on E(SP (P_{j}, j)) for every s, every τ_{j,s} is of even length. Thus each node of the form Φ_{j}(SP (P_{j}, j)(τ_{j,s}^{⌢}1)) ↾ x_{s} + 1 which is extendible in T_{j} is nonextendible in T′_{j}. On the other hand, every SP (P_{j}, j)(τ^{⌢}0) is an initial segment of A for τ of even length as A is on E(SP (P_{j}, j)). Thus every node of T_{j} declared nonextendible in T′_{j} is incomparable with A. As A is on T_{j}, it is in [T_{j}] − [T′_{j}]. On the other hand, for each n there is by construction a set A_{n} ≠ A in [T_{j}] − [T′_{j}] such that A_{n} ↾ n = A ↾ n. Thus [T′_{j}] is not the intersection of [T_{j}] with any clopen set and so [T_{j}] is not thin as required. □

In this theorem and in Theorem 2.9 we constructed Δ_{2}^{0} sets which belonged to countable thin Π_{1}^{0} classes. We would like to show that not all members of countable thin Π_{1}^{0} classes are recursive in 0′. This is implied by the following result.

Theorem 2.18. There is a minimal Π_{1}^{0} class P with unique nonisolated point A such that A ⊕ 0′ is Turing equivalent to 0′′.

Proof. This is based on the proof of Theorem 2.1 of [1], where it is shown that any Σ_{2}^{0} set A, with 0′ recursive in A, is Turing equivalent to a set with rank one.

Let B be a Π_{2}^{0} set of degree 0′′ and let S be a recursive relation so that, for any e,

e ∈ B ⟺ (∀n)(∃m)S(m, n, e).

Now let the recursive relation Q be defined by

Q(m, n, e) ⟺ m ≥ n ∧ (∀n′ ≤ n)(∃m′ ≤ m)R(m, n, e).

Then it is clear that

e ∈ B ⟺ (∀n)(∃m)Q(m, n, e)

and that, for any m′ ≥ m and any n′ ≤ n, Q(m, n, e) → Q(m′, n′).

Now define the recursive relation R by

R(m, e) ⟺ (∃n ≤ m)[Q(m, n, e)∧ ≠ Q(m − 1, n, e)].

It is easy to see that

e ∈ B ⟺ (∀n)(∃m > n)R(m, e).

Let T_{e} as usual be the e^{th} primitive recursive tree and let P_{e} = [T_{e}].

We will define a set A = {a_{0} < a_{1} < ⋯ } and a Π_{1}^{0} class P such that

(1) D(P) = {A}.

(2) B is recursive in A ⊕ 0′.

(3) For any e, if A ∈ [T_{e}], then P \ P_{e} is finite.

It will follows as in the proof of Theorem 2.9 that P is minimal.

Let us briefly recall the idea of Theorem 2.1 of [1]. There we were defining a Π_{1}^{0} class P and a set A of degree 0′′ such that D(P) = {A}. (Note that by Corollary 2.11, P can not be thin.) There the set A = {a_{0} < a_{1} < ⋯ } was made to have degree 0′′ by making each a_{n} a witness for whether n ∈ B. That is, we had n ∈ B if and only if R(a_{n}, n). In addition, we made a_{n} large enough so that if n ∉ B, then ¬R(a, n) for all a > a_{n} and so that, for any m < n, if m ∈ B, then there is a witness a such that a_{m} < a ≤ a_{n} such that R(a, m).

Now the difficulty in constructing the set A and a recursive tree T such that P = [T] is that at any finite stage s, we have no definite information about the set A. Thus the Π_{1}^{0} class P consists of all the possible values of A(X) for any guess X at the actual set B. There are two ways in which such a guess X could first go wrong. First, if n ∉ X but n ∈ B, then any possible choice of a_{n} will be seen to be incorrect as soon as another witness to n ∈ B shows up. Thus A(X) will have at most n elements. Second, if n ∈ X but n ∉ B, then after constructing some a_{0} < ⋯ < a_{k}, we run out of witnesses for n. Thus A(X) will again be a finite set. In either case, the construction will ensure that A(X) will be isolated in P.

The present construction has the additional complication needed to make P a minimal Π_{1}^{0} class. Thus we also must choose a_{n} large enough so that < a_{0}, …, a_{n} >∉ P_{e} for e ≤ n whenever possible. Now in particular the goal of avoiding P_{0} will have highest priority, so that if we find < a_{0}, …, a_{n−1}, s >∉ T_{0} at stage s of the construction, then we will restart the B-requirements by letting s = a_{n+1} be the witness for whether or not 0 ∈ B. As long as this s is not a false witness for 0 ∉ B, then a_{0}, …, a_{n+1} will not change again during the construction. When computing B from A ⊕ 0′, we can use the 0′ oracle to search for the stage s at which the construction moved out of T_{0} and thus determine the witness a_{n+2}. If there is no such stage, then a_{0} is the witness for 0 ∈ B.

The previous discussion indicates that the construction of the sets A(X) for various guesses X can now interact with each other. That is, when < a_{0}, …, a_{n−1}, s >∉ T_{0}, it may be that σ =< a_{0}, …, a_{n−1} > comes from an incorrect guess X (for example, that 0 ∈ B when it isn’t). After stage s, σ becomes the common initial segment of all A(X). Of course, an incorrect guess that n ∉ B when in fact n ∈ B will be proved wrong (that is, the witness for n ∉ B will be seen to fail) by some finite stage and thus the path corresponding to this guess will be abandoned.

For a finite sequence σ =< u_{0}, …, u_{k}, u >, the predictor function p = p_{σ} associated with σ is defined recursively by letting p(0) be the least j ≤ k such that < u_{0}, …, u_{j−1} >∉ T_{0}, if any, and p(0) = 0 otherwise. Then, for any e, p(e + 1) is the least j ≤ k such that j > p(e) and such that if < u_{0}, …, u_{k} >∉ T_{e+1}, then < u_{0}, …, u_{j−1} >∉ T_{e+1}. Now let β = (i_{0}, …, i_{s−1}) ∈ {0, 1}^{s}, so that β represents a guess at B ↾ s. Then we say that σ =< u_{0}, …, u_{k}, u > is β-correct at stage s if the following conditions are satisfied for all e ∈ Dom(p):

(1) If i_{e} = 0, then ¬R(m, e) for all m with u_{p(e)} ≤ m ≤ s.

(2) If i_{e} = 1, then R(p(e), e) and, for all j with p(e) < j < k, there is some m with u_{j} ≤ m < u_{j+1} such that R(m, e).

As in the proof of Theorem 2.16, we define the s−state (i_{0}, …, i_{s}) of σ by i_{e} = 1 if and only if σ ∈ T_{e}.

Construction: We proceed recursively to define, for each s and each i_{0}, …, i_{s−1} ∈ {0, 1}^{s}, an associated sequence σ_{β} ∈ {0, 1}^{s}. The tree T is defined recursively so that T^{s+1} contains all initial segments of the σ_{β} for lh(β) = s together with all correct extensions by 0 of members of T^{s}. Then, for each X ∈ {0, 1}^{ω}, we will let A(X) be the limit of the sequence {σ_{X↾n}}, so that in particular A = A(B).

We begin the construction at stage 0 by setting σ_{∅} = ∅ at stage s = 0.

At stage s = 1, there are two guesses β = (0) and β = (1) as to whether 0 ∈ B. There are two possible cases in the definition of σ_{β} for these two values of β.

(Case 1): R(0, 0). In this case σ_{(0)} = (0) (since we don’t yet have a witness to 0 ∉ B) and σ_{(1)} = (1).

(Case 2): ¬R(0, 0). In this case σ_{(0)} = (1) and σ_{(1)} = (0).

In either case, we have T^{1} = {∅, (0), (1)}.

Now suppose we have completed the construction as far as stage s. Then we will have defined σ_{β} for all sequences β of length ≤ s and we will have defined T^{s}. As in the proof of Theorem 2.16, we will now define a notion of an eligible sequence for β at stage s + 1 and then we will choose σ_{β} to have the best s-state of the sequences which are eligible for β.

Let σ =< u_{0}, …, u_{k}, u >= σ_{β↾s} and τ =< v_{0}, …, v_{ℓ}, v >. We say that τ is eligible for β at stage s + 1 if it satisfies the following conditions:

(1) lh(τ) = lh(β) = s + 1

(2) τ ↾ s ∈ T^{s}

(3) τ is β-correct at stage s + 1.

(4) For any e ≤ k, if v_{e} ≠ u_{e} or if ℓ < k, then either

(a) β(e) = 0 and v_{e} = s or

(b) τ has a strictly better e-state than σ.

The restriction in clause (4) indicates that the B-correctness requirement for b < e has higher priority than the e-state requirement and is needed so that the construction will converge.

Now at stage s+1, we simply define σ_{β} to be the lexicographically largest among the sequences τ which are eligible for β and have the best possible s-state. The tree T^{s} is just the set of all initial segments of σ_{β} where β has length s + 1 together with all sequences τ^{⌢}0 such that τ ∈ T^{s} and τ^{⌢}0 is β-correct at stage s + 1 for some β of length ≤ s + 1.

Finally, let T = ⋃_{s} T^{s}. It follows from (2) that T is a tree.

Verifications:

For each infinite guess X for B, let σ_{X,s} = σ_{X↾s}. Let P = [T].

Claim 1. For each X, the sequence σ_{X,s} converges to a limit.

Proof of Claim 1. Fix X and let σ_{X,s} = β^{s} =< b_{0}^{s}, …, b_{k}(s)^{s} > for each s. We will prove by induction on e that b_{e}^{s} either converges to some finite limit b_{e} or else diverges to ω. In the latter case the limit σ_{x} of the sequence σ_{X}^{s} can be given and the induction argument stops. Suppose therefore that, for some t, b_{i}^{s} = b_{i} for all i < e and all s > t. (It follows that k(s) ≥ e for all s > t, so that b_{e}^{s} always exists.) Now let β^{r} have the best e-state of all β^{s} with s > t. It then follows from the construction that the sequence b_{e}^{s} is non-decreasing for s > r. Now there are two cases. Either the limit b_{e} = lim_{s} b_{e}^{s} exists, or else lim_{s} b_{e}^{s} = ω. In the latter case, we see that lim_{s} β^{s} =< b_{0}, …, b_{e−1} >^{⌢} 1^{⌢}0^{ω}. Finally, if lim_{s} b_{e}^{s} = b_{e} exists for all e, then the sequence β^{s} clearly converges to a limit. □

In the proof of Claim 1, it follows that the set A(X) = {b_{0}, …, b_{e}}, where e is the largest such that lim_{s} b_{e}^{s} = b_{e} converges. In particular, let A = A(B). We will show that A is an infinite set and is the only infinite set in P. □

Claim 2. B is Turing reducible to A ⊕ 0′.

Proof of Claim 2: First we demonstrate that A is infinite. Suppose by way of contradiction that A = A(B) = {b_{0}, …, b_{e−1}} and let β^{s} =< b_{0}^{s}, …, b_{d}k(s)^{s} > for each s. Let t be large enough so that b_{i}^{s} = b_{i} for all s > t and i < e and let β^{r} have the best e-state of all β^{s} with s > t. Now it follows as in the proof of Claim 1 that b_{e}^{s} diverges to ω and therefore increases infinitely often. But, since the e-state has converged by stage r, it also follows from the construction that b_{e}^{s} only increases when < b_{0}^{s}, …, b_{e}^{s} > is not B-correct. Since X = B is the true guess for B, this can only happen finitely often, that is, while we wait for the witnesses to x ∈ B for some finite list of values of x all less than e. This contradiction shows that A(B) is actually infinite.

Next we show how to compute B given A and an oracle for 0′. We will show how to compute the predictor function p for B so that, for each e, e ∈ B if and only if R(p(e), e). Note that we cannot simply compute the predictor directly from A by examining the e-state of A, because this would require an oracle for A′. Instead we obtain the predictor by examining the recursive tree T constructed. Begin by using an oracle for 0′ to see whether there is a σ ∈ T \ T_{0}. If not, then the predictor p(0) = 0. If so, then σ will automatically be eligible for β = B ↾ s at stage s = lh(σ). It follows from the construction that σ_{β} ∉ T_{0}. Now let σ_{B}^{s} =< u_{0}, …, u_{k}, s >. Then the predictor p(0) = k. Having defined p(0), …, p(e), we now let τ =< a_{0}, …, a_{p(e)} > and use the oracle for 0′ to see whether there is an extension σ of τ which is in T \ T_{e+1}. If not, then p(e + 1) = p(e) + 1. If so, then σ will be eligible for β = B ↾ s at stage s = lh(σ). It follows from the construction that σ_{β} ∉ T_{e+1}. Then p(e + 1) = k, where σ_{β} =< u_{0}, …, u_{k} >. □

Claim 3. For any e, the sequence of e-states of σ_{B↾s} for s ≥ e, is non-decreasing.

Proof of Claim 3: Let β_{s} = B ↾ s and let σ_{s} = σ_{β_{s}}. Observe that since σ_{s} is β_{s}-correct at stage s and X = B is the correct guess, then σ_{s}^{⌢}0^{t−s} is β_{t}-correct at any stage t > s and is in T by the construction. Thus σ_{s}^{⌢}0^{t−s} is eligible for β_{t} at stage t. Since σ_{t} is chosen to have the best possible e-state, this clearly implies that σ_{t} has e-state no worse than that of σ_{s}. □

Claim 4. D(P) = {A}.

Proof of Claim 4: It follows from Claim 2 that A is not recursive and hence A ∈ D(P) by Lemma 1.2 of [1]. It remains to be shown that every other element of P is isolated. Let Y = {y_{0} < y_{1} < … } be an element of P which is different from A. We first show that Y must be finite. Suppose by way of contradiction that Y is infinite. Then we can define a predictor function p for X as in the proof of Claim 2 above by checking whether Y ∈ [T_{e}] for each e. We can then define the set X = {e : R(p(e), e)} predicted by Y. Since Y ≠ A, it follows that X ≠ B. . Now let e be the least such that X(e) ≠ B(e) and let k = p(e). There are two cases.

(Case 1) Suppose that e ∈ B, but e ∉ X and choose m > k so that R(m, e). Then Y ↾ (m + 1) cannot be X ↾ (m + 1)-correct, contradicting the fact that Y ↾ (m + 1 must be in T.

(Case 2) Suppose that e ∉ B, but e ∈ X. Now let m be the largest such that R(m − 1, e). Since p(m) ≥ m, it follows that Y ↾ p(m) cannot be X ↾ p(m)-correct, contradicting the fact that Y ↾ p(m) must be in T.

It follows that Y = {y_{0}, …, y_{n−1}} is finite. We claim that there are at most two possible values of s such that σ =< y_{0}, …, y_{n−1}, s, s+1 >∈ T. Not first that by the construction, there must be for each such σ some e_{s} such that the predictor p_{σ}(e) = s. Now suppose by way of contradiction that there were three such values for s_{1} < s_{2} < s_{3} and the corresponding σ_{i} =< y_{0}, …, y_{n−1}, s_{i}, s_{i} + 1 >. Then two of them, say s_{1} and s_{3}, must predict the same sequence β. But then < y_{0}, …, y_{n−1}, s_{1}, s_{3} + 1 > would be eligible at stage s_{3} and would be lexicographically greater than σ_{3}, which would prevent σ_{e} from being chosen as σ_{β}. This contradiction shows that at most two such values are possible for s. Now let s be the larger of the values. It then follows that Y is the only infinite extension in P of Y ↾ (s + 2), which demonstrates that Y is isolated in P. □

Claim 5. P is minimal.

Proof of Claim 5: As usual, we prove that for any e, if A ∈ P_{e}, then P \ P_{e} is finite. Suppose therefore that A ∈ P_{e} and let k > p(e) be large enough so that, for all i < e, < a_{0}, …, a_{k} >∈ T_{i} if and only if A ∈ P_{i}. Since A is the only nonisolated point in P (by Claim 4), there can only be finitely many members of P which do not extend < a_{0}, …, a_{k} >. Now let Y = {a_{0} < a_{1} < … < a_{k} < c_{k+1} < … < c_{m}} ∈ P. We claim that Y ∈ P_{e}. Suppose not, by way of contradiction. It then follows from the construction that Y ↾ c_{m} would be eligible for β = X ↾ c_{m}, which implies that σ_{β} ∉ T_{e}. But this would mean that σ_{β} had a better e-state than A, contradicting Claim 3. It follows that every infinite extension of < a_{0}, …, a_{k} > is in P_{e}, so that P \ P_{e} is finite. □

To complete the proof of Theorem 2.18, observe that A is recursive in 0′′ by Claim 4 and Lemma 2.1 of [1], which implies together with Claim 2 that A ⊕ 0′ is Turing equivalent to 0′′. □

We next wish to consider the question of whether an entire degree can be ranked. Downey showed in [9] that there is a completely ranked non-zero degree below 0′′, that is a Δ_{3}^{0} set A such that every set B of the same Turing degree as A is ranked. The final result of this section is a strengthening of this result for thin rank.

Theorem 2.19. There is a Δ_{3}^{0} set A such that every non-recursive set B ≤_{T} A is a rank 1 member of a thin Π_{1}^{0} class, indeed the unique rank 1 member of a minimal Π_{1}^{0} class.

Proof. Downey [9] constructs a Π_{1}^{0} class C with exactly one point A of rank one. The set A is therefore automatically recursive in 0′′. In addition A is constructed to be hyperimmune free. It is straightforward to modify such a construction to make C thin (indeed minimal) by adding on a finite injury type requirement (interspersed with the e-state requirements used to make A h.i. free) to guarantee that Q_{e} does not split C for any Π_{1}^{0} class Q_{e}. [When one is working above some e-states preference node, p(α, s) = σ(α) is the e-state, s the stage and σ the node on the tree, one looks for a node τ ⊇ σ on the tree which is not in Q_{e}. If one finds such a node τ at stage t, p(α, t) is redefined to be τ. Thus in the limit either all extensions of p(α) for the final e-state α are in Q_{e} or none of them are, i. e. Q_{e} does not split C.]

As the unique rank one point A of the class C so constructed is hyperimmune free, any set B ≤_{T} A is, in fact, truth table reducible to A. We now claim that any non-recursive set B ≤_{tt} A is itself the unique rank one point of a minimal Π_{1}^{0} class. To see this suppose that B is reducible to A via the truth functional operator Ψ, i. e. B = Ψ^{A}. Let T be the recursive tree such that [T] = C. Consider the image of T under Ψ, i. e. Ψ(T) = {σ : (∃τ ∈ T)(σ ⊆ Ψ^{τ})}. As Ψ is a truth functional reduction, Ψ(T) is a recursive tree which defines a Π_{1}^{0} class Ψ(C) = [Ψ(T)]. Note that if C ∈ C then Ψ^{C} ∈ Ψ(C). Thus in particular B ∈ Ψ(C). Moreover, as Ψ induces a homomorphism from [T] to [Ψ(T)], the rank of any point Ψ^{C} in [Ψ(T)] is less than or equal to the rank of C in [T]. As B = Ψ^{A} is not recursive, it must then be the unique point of rank one in [Ψ(T)].

Finally, we claim that if C is minimal then so is Ψ(C). If not, say Q splits Ψ(C). We then claim that Ψ^{−1}(Q) splits C for a contradiction where Ψ^{−1}(Q) = {σ : Ψ^{σ} ∈ Q}. (By convention Ψ^{σ} is a string of length ≤ lh(σ).) To see this note first that if some X ∈ [Ψ(T)], then there is a Y ∈ [T] such that Ψ^{Y} = X. (Ψ^{−1}{σ : σ ⊂ X} ∩ T is infinite and so has an infinite path.) Thus, if there are infinitely many X ∈ [Q ∩ Ψ(T)], then there are infinitely many Y ∈ [T] with Ψ^{Y} ∈ [Q ∩ Ψ(T)]. Now if Ψ^{Y} ∈ Q, then Y ∈ Ψ^{−1}(Q). As the same considerations apply to [Q̄∩Ψ(T)], we see that Ψ^{−1}(Q) splits C = [T] for the desired contradiction. As B is a non-recursive member of the minimal class Ψ(C), it must be its unique rank one point as required. □

2. Thin Π_{1}^{0} classes.

Recall that a coinfinite r. e. set M is said to be maximal if for any r. e. set A, if M ⊂ A, then either A \ M is finite or ω \ A is finite. A Π_{1}^{0} subset C of ω is said to be co-maximal if ω \ C is maximal, that is, C is infinite and for every Π_{1}^{0} subset B of C, either B is finite or C \ B is finite. A. H. Lachlan [18] showed that an infinite Π_{1}^{0} set C is co-hyperhypersimple if and only if every Π_{1}^{0} subset of C is the intersection of C with a recursive set. These notions have natural versions for Π_{1}^{0} classes. (Since we will be considering both sets and classes in this paper, we will use the term “minimal” for classes rather than co-maximal.)

Definition. (a) A Π_{1}^{0} class P is said to be minimal if for every Π_{1}^{0} subclass Q, either Q is finite or P \ Q is finite.

(b) A Π_{1}^{0} class P is said to be thin if every Π_{1}^{0} subclass Q of P is relatively clopen in P, that is, there is a clopen set U such that Q = U ∩ P.

The connection between thin and minimal classes will be made below in Lemma 2.1. Let us first make a few observations about the derivatives of thin sets. Recall that if x is any isolated point in a Π_{1}^{0} class P, then x is recursive and {x} is a relatively clopen subset of P. Now, if the Π_{1}^{0} class P has Cantor-Bendixson rank 0, then P is finite and all its elements are isolated. It follows that every subset of P is finite and is also relatively clopen, so that P must be minimal and also thin. It is not so easy to find a thin Π_{1}^{0} class P with Cantor-Bendixson rank one. The difficulty is indicated by the following lemma.

Lemma 2.0. For any thin Π_{1}^{0} class P and any element x of P, x is isolated in P if and only if x is recursive.

Proof. (only if) This is true for any Π_{1}^{0} class.

(if) If x is recursive, then {x} is a Π_{1}^{0} subclass of P by Lemma 1.1. Since P is thin, it follows that {x} is a relatively clopen subclass of P. This implies that x is isolated. □

This means that any infinite thin Π_{1}^{0} class must contain non-recursive elements, which makes a countable thin Π_{1}^{0} intrinsically difficult to construct. However, thin classes of rank one are more manageable, due to the following connection with minimal classes. The following lemma will be used to construct thin classes of rank one.

Lemma 2.1. Let P be a Π_{1}^{0} class.

(a) If P is thin and the Cantor-Bendixson derivative D(P) is a singleton, then P is minimal.

(b) If P is minimal and infinite, then the Cantor-Bendixson derivative D(P) is a singleton.

(c) If P is minimal and has a non-recursive member, then P is thin.

Proof. (a) Suppose that P is thin and let D(P) = {A}. Now let Q be a Π_{1}^{0} subclass of P. Since P is thin, it follows that Q = P ∩ U for some clopen set U. This means that P \Q = P \U is also a Π_{1}^{0} subclass of P. Now suppose by way of contradiction that both Q and P \ Q were infinite. Then both sets would have to contain limit points. But both D(Q) and D(P \ Q) are subsets of D(P) = {A}, so that A is the only possible limit point in either set. Since the two sets are disjoint, it is impossible for A to belong to both of them.

(b) Suppose that P is minimal and infinite. Then there is some limit point A in D(P). We claim that D(P) = {A}. Suppose for the sake of a contradiction therefore that B is any other element of P. Then of course there is some clopen set U such that A ∈ P ∩ U and B ∈ P \ U. Since A is a limit point of P, P ∩ U must be infinite. Since P is minimal and P ∩ U is a Π_{1}^{0} subclass of P, it follows that P \ U is finite. But this implies that B is isolated in P.

(c) Suppose next that P is minimal and has a non-recursive member A. Then A ∈ D(P) and it follows from (b) that in fact D(P) = {A}. Thus for any other set BinP, B is isolated in P, so that there exists a clopen set U(B) such that P ∩ U(B) = {B}.

Now let Q be any Π_{1}^{0} subclass of P. There are two cases.

(Case 1) Q is finite. Then all members of Q are recursive, so that A ∉ Q and

Q = P ∩ ⋃_{B∈Q} U(B).

(Case 2) Q is infinite and P \ Q is finite. Then D(Q) is nonempty and since D(Q) ⊂ D(P) = {A}, we must have A ∈ Q, so that

Q = P ∩ [2^{ω} \ ⋃_{B∈P \Q} U(B)]. □

Theorem 2.2. For every recursive ordinal α, there is a thin Π_{1}^{0} class P_{α} with Cantor-Bendixson rank α. Furthermore, we may take P_{α} as the set of paths through a recursive tree with no dead ends.

Proof. The proof employs a transfinite inductive definition. To illustrate the general argument, we first give the basic construction of a thin Π_{1}^{0} class with Cantor-Bendixson rank one.

Let T_{e} ⊂ {0, 1}^{<ω} be the e^{th} primitive recursive tree, so that [T_{0}], [T_{1}], … is an effective enumeration of all Π_{1}^{0} subsets of {0, 1}^{ω}. We are going to construct a point A, a sequence τ_{0} ≺ τ_{1} ≺ … of strings with A = ∪_{i}τ_{i} and a Π_{1}^{0} class P such that

(1) D(P) = {A}.

(2) For any e and any extension B ∈ P of τ_{e}, if A ∈ [T_{e}], then B ∈ [T_{e}].

Property (1) states directly that P has Cantor-Bendixson rank one. Properties (1) and (2) imply that P is minimal, by the following argument.

Note first that, for all B ∈ P, if B ≠ A, then the point B is isolated in P by property (1), so that there exists a clopen set U(B) such that P ∩ U(B) = {B}. Suppose now that [T_{e}] is a subset of P. Then there are two cases.

(Case 1) If A ∉ [T_{e}], then, since A is the only limit point of P and every infinite class has a limit point, it follows that [T_{e}] is finite.

(Case 2) If A ∈ [T_{e}], then it follows from property (2) that every extension of τ_{e} is also in T_{e}. Now the set P \ I(τ_{e}) of paths through T which are not extensions of τ_{e} is a closed set and has no limit point (since A is the only limit point of P). Thus P \ I(τ_{e}) is finite and, since P \ [T_{e}] ⊂ P \ I(τ_{e}), P \ [T_{e}] is also finite.

It also follows from properties (1) and (2) that A is not recursive. To see this, suppose by way of contradiction that A were recursive. Then {A} would be a Π_{1}^{0} class, so that {A} = [T_{e}] for some e. Now by property (2), we have P ∩I(τ_{e}) ⊂ [T_{e}], which makes A isolated in P, contradicting property (1). This demonstrates that A is not recursive. It now follows from Lemma 2.1 that P is thin.

It remains to construct the set P. The construction will proceed in stages. At stage s we will have, for e ≤ s, finite sequences τ_{e}^{s} such that, for all e < s, τ_{e}^{s⌢}1 ≺ τ_{e+1}^{s}. The construction will ensure the existence of the limits τ_{e} = lim_{s} τ_{e}^{s} for each e. The point A will the union of {τ_{e} : e ∈ ω}. At the same time we will be defining a sequence k(0) < k(1) < ⋯ so that s ≤ k(s) and constructing a recursive tree T in stages T^{s}. At stage s, we will have decided whether each finite sequence of length k(s) is in T. This will ensure that T is recursive. We will always put σ^{⌢}0 into T whenever σ is in T. This will imply that x_{e} = τ_{e}^{⌢}0^{ω} ∈ P for all e; since A is non-recursive and therefore infinite, there are infinitely many distinct x_{e}, so that A ∈ D(P). To obtain D(P) = {A}, we do the construction so that, whenever τ_{e}^{s+1} = τ_{e}^{s}, then there are no new branches added below τ_{e}^{s}. Thus once we have reached a stage s such that τ_{e}^{s} = τ_{e} and counted the number n of distinct branches of T^{s} not passing through τ_{e}^{s}, then we know that all but n points of P will pass through τ_{e}. Now suppose that some path B is in D(P) but is different from A. Just let k be the least number such that A(k − 1) ≠ B(k − 1) and let e be least such that A ↾ k ⊂ τ_{e}. Then no extension of B ↾ k passes through τ_{e}. It follows that the set of extensions of B ↾ k in P is finite, so that B is isolated in P. This will take care of property (1).

In order to satisfy property (2), we want the construction to ensure the following requirements for each e.

(R_{e}): If τ_{e} ∈ T_{e}, then every extension of τ_{e} which is in T is also in T_{e}.

We begin the construction by setting k(0) = 1, putting (0) and (1) in T^{0} and setting τ_{0}^{0} = ∅.

Now suppose we have completed the construction as far as stage s. At stage s+1, we look for the least number e ≤ s such that τ_{e}^{s} ∈ T^{s} but τ_{e}^{s} has some extension τ ∈ T^{s} which is not in T_{e}. If there is such an e , then we act on requirement R_{e} at stage s + 1, as follows. Let τ be the lexicographically least sequence of length k(s) which is in T^{s} \ T_{e}. Then let τ_{e}^{s+1} = τ. For i < e, let τ_{i}^{s+1} = τ_{i}^{s}. For i ≤ s − e + 1, let τ_{e+i}^{s+1} = τ^{⌢}1^{i}. Now let k(s + 1) = k(s) + s − e + 1 and define T^{s+1} to be the union of T^{s} with the set of the following strings. First, for any σ ∈ T^{s} of length k(s) and any i ≤ s − e + 1, the extension σ^{⌢}0^{i}. Next, for any i ≤ s − e + 1, and any j ≤ s − e + 1 − i, the extension τ^{⌢}(1^{i})^{⌢}(0^{j}).

If there is no such e, just let τ_{i}^{s+1} = τ_{i}^{s} for all i ≤ s and let τ_{s+1}^{s+1} = τ_{s}^{s}^{⌢}1. Let k(s + 1) = k(s) and let T^{s+1} be the union of T^{s} with the set of all strings σ^{⌢}0 where σ ∈ T^{s} and the string τ_{s+1}^{s+1}.

Observe that in either case, we have extended all nodes in T^{s} by at least one node in T^{s+1}, so that T will have no dead ends.

Claim 1. For every e, the sequence τ_{e}^{s} converges to some limit τ_{e}.

Proof of Claim 1: This is by induction on e. Suppose therefore that Claim 1 is proved for all i < e and that we have reached a stage s such that τ_{i}^{s} = τ_{i} for all i < e. There are two cases. If τ_{e}^{r} = τ_{e}^{s} for all r > s, then the limit τ_{e} = τ_{e}^{s} and we are done. Otherwise, let r > s be least such that τ_{e}^{r} ≠ τ_{e}^{s}. It follows from the construction that we must have τ_{e}^{r} ∉ T_{e}. After stage r, there is no way that τ_{e}^{t} can be different from τ_{e}^{r}. Thus the limit τ_{e} = τ_{e}^{r}. □

Since τ_{e}^{s} ≺ τ_{e+1}^{s} for all s and e, it follows that τ_{e} ≺ τ_{e+1} for all e. Thus we can define the set A to have characteristic function ∪_{e}τ_{e}.

Claim 2. For any e and any s, if τ_{e}^{s+1} = τ_{e}^{s}, then there are no new branches in T^{s+1} \ T^{s} which do not pass through τ_{e}^{s}.

Proof of Claim 2: This follows immediately from the construction. □

It now follows that, for any e, all but finitely many points of P pass through τ_{e}. Now let A be the union of the set of τ_{e}. It follows from the discussion preceding the construction that D(P) = {A}.

Claim 3. If τ_{e} ∈ T_{e}, then every extension of τ_{e} which is in T is also in T_{e}.

Proof of Claim 3: Suppose by way of contradiction that τ_{e} ∈ T_{e} but that τ_{e} has some extension τ ∈ T such that τ ∉ T_{e}. Consider a stage s > lh(τ) such that τ_{i}^{s} = τ_{i} for all i ≤ e and τ ∈ T^{s}. Then at stage s + 1, we have τ ∈ T^{s} so the construction dictates that we act on requirement R_{e} and make τ_{e}^{s+1} = τ, contradicting the assumption that τ_{e}^{s} = τ_{e}. □

This establishes property (1) and (2) above and thus completes the proof of Theorem 2.2 for α = 1.

Now for the general argument, let κ be a fixed recursive ordinal. We will prove the result for ordinals less than κ. Since κ is arbitrary, this will prove the theorem for all recursive ordinals.

We need a recursively related, univalent system of notations for the ordinals less than κ, as described in Rogers [28]. This is a one-to-one map o from the natural numbers (or a finite subset thereof) onto κ such that each of the following relations is recursive.

“o(a) < o(b)”;

“o(b) = o(a) + 1”;

“o(a) is a limit ordinal”.

We may assume that o(0) = 0.

We will construct, by a transfinite inductive definition, a uniformly recursive family of recursive trees S_{a}(σ) such that, for each natural number a with o(a) = α and each σ ∈ {0, 1}^{∗}, P_{α}(σ) = [S_{a}(σ)] is a thin Π_{1}^{0} class with Cantor-Bendixson rank α and every string in S_{a}(σ) is compatible with σ. For α = 0, let S_{0}(σ) = {τ : (∃n)[τ ≺ σ^{⌢}0^{n}]} and [S_{0}(σ)] = {σ^{⌢}0^{ω}}.

Now suppose that the trees S_{b}(σ) have been constructed for all b with o(b) < o(a). Fix a string σ_{0}. We will now give the construction of the tree S_{a}(σ_{0}). There are two cases, which we can recognize recursively by the third property of our system of notations.

(Case 1) o(a) = α > 1 is a successor ordinal. In this case, compute b such that o(b) = β, where o(a) = o(b) + 1 and proceed as follows to construct the tree T = S_{a}(σ), the sequence τ_{0}, τ_{1}, …, with τ_{e}^{⌢}1 ≺ τ_{e+1} for all e, and the point A = ∪_{i}τ_{i} with the following properties.

(1) For each e, the set of strings in T which are compatible with τ_{e}^{⌢}0 is precisely S_{b}(τ_{e}^{⌢}0).

(2) For any e and any extension B ∈ P of τ_{e}, if A ∈ [T_{e}], then B ∈ [T_{e}].

(3) For each e, there are only finitely many points B in [T] which extend τ_{e}^{⌢}1 but do not extend τ_{e+1}.

Let us first show that these three properties are sufficient to make P = [T] thin and to have D^{α}(P) = {A}.

For each n, let U(n) be the clopen set of extensions of A ↾ n which disagree with A ↾ (n + 1). Let us consider D^{β}(P ∩ U(n)) for each n. There are two possibilities.

If A ↾ n = τ_{e} for some e then by property (1), P ∩ U(n) = S_{b}(τ_{e}) so that D^{β}(P ∩ U(n) will be a singleton. (Note that there are infinitely many n of this type.)

If not, then by property (3), P ∩ U(n) will be finite, so that D^{β}(P ∩ U(n)) will be empty, since β > 0.

Now it follows from Lemma 1.2 of [2] that D^{β}(P)∩U(n)) = D^{β}(P ∩U(n). Thus for the infinitely many n of the first type, we have a single element in D^{β}(P)∩U(n). Now the point A must be a limit of those elements, so that A ∈ D^{α}(P), since α = β + 1.

On the other hand, we have D^{α}(P ∩ U(n)) = ∅ for all n. But any element of P other than A must lie in one of the P ∩ U(n). It follows that only A can be in D^{α}(P).

This shows that D^{α}(P) = {A} as desired.

Now consider the thinness of P. Note that as mentioned above, every element of P, other than A, must lie in exactly one of the sets P ∩ U(n). Now if n is of the first type, then P ∩ U(n) = S_{b}(τ_{e}) and is itself a thin Π_{1}^{0} class by the inductive construction. If n is of the second type, then P ∩ U(n) is finite, which implies that any point B in P ∩ U(n) is isolated in P, so that there exists a clopen set U(B) such that P ∩ U(B) = {B}. Suppose now that [T_{e}] is a subset of P. Then there are two cases.

(Case i) Suppose A ∉ [T_{e}], then, since [T_{e}] is closed, there must be some p such that no extension of A ↾ p is in T_{e}. Thus [T_{e}] is a subset of ⋃_{n<p} P ∩ U(n). Recall the two possibilities discussed above. If n is of the first type and A ↾ n = τ_{i} for some i < e, then, since P ∩ U(n) is thin, we must have some clopen V (n) ⊂ U(n) such that P ∩U(n)∩[T_{e}] = P ∩V (n). Let V = ∪_{n<p}V (n). If n is of the second type, then any element B of [T_{e}] ∩ U(n) is isolated in P, so we have some clopen U(B) ⊂ U(n) with P ∩ U(B) = {B}. Now let K be the set of B such that B ∈ [T_{e}] ∩ U(n) for some n < p of the second type and let U = ⋃_{B∈K} U(B). Then it is easy to check that [T_{e}] = P ∩ (U ∪ V).

(Case ii) If A ∈ [T_{e}], then it follows from property (2) that every extension of τ_{e} which is in P is also in T_{e}. Thus P ∩ I(τ_{e}) = [T_{e}] ∩ I(τ_{e}). Now [T_{e}] \ I(τ_{e}) = ⋃_{n<p}[T_{e}] ∩ U(n), where p = lh(τ_{e}). Thus we can construct as in Case i a clopen set W such that [T_{e}] \ I(τ_{e}) = P ∩ W. It then follows that [T_{e}] = P ∩ (I(τ_{e}) ∪ W).

It remains to construct the set P. The construction will proceed in stages. At stage s we will have, for e ≤ s, strings τ_{e}^{s} such that, for all e < s, τ_{e}^{s}^{⌢}1 ≺ τ_{e+1}^{s}. The construction will ensure the existence of the limits τ_{e} = lim_{s} τ_{e}^{s} for each e. The point A will the union of the {τ_{e} : e ∈ N}. At the same time we will be constructing a recursive tree T in stages T^{s}. At stage s, we will have decided whether all finite sequences of length k(s) are in T, where s ≤ k(s). This will ensure that T is recursive. We will always put σ^{⌢}0 into T whenever σ is in T. This will imply that there are no dead ends in the tree. The construction will make the extensions of τ_{e}^{⌢}0 in T^{s} just those in the tree S_{b}^{s}(τ_{e}^{⌢}0) of length ≤ k(s). This will guarantee that we have property (1).

To obtain property (3), we do the construction so that, whenever τ_{e+1}^{s+1} = τ_{e+1}^{s}, then τ_{i}^{s+1} = τ_{i}^{s} for all i ≤ e and there are no new branches added which extend τ_{e}^{s⌢}1 but do not extend τ_{e}^{s+1}. Thus once we have reached a stage s such that τ_{e+1}^{s} = τ_{e+1}, the number of distinct branches of T^{s} which extend τ_{e} but not τ_{e+1} will remain fixed and therefore finite.

In order to satisfy property (2), we want the construction to ensure the following requirement for each e.

(R_{e}): If τ_{e} ∈ T_{e}, then every extension of τ_{e} which is in T is also in T_{e}.

This will certainly ensure property (2), since it implies that if B is an infinite extension of τ_{e}, then all initial segments of B longer than τ_{e} must be in T_{e}, so that B itself must be in [T_{e}].

We begin the construction of the recursive tree T = S_{a}(σ_{0}) by setting k(0) = lh(σ), setting τ_{0} = σ_{0}, and making T^{0} the set of initial segments of σ_{0}.

Now suppose we have completed the construction as far as stage s. At stage s+1, we look for the least number e ≤ s such that τ_{e}^{s} ∈ T^{s} but τ_{e} has some extension τ ∈ T^{s} which is not in T_{e}. If there is such an e, then we act on requirement R_{e} at stage s + 1, as follows. Let τ be the lexicographically least sequence of length k(s) which is in T^{s} \ T_{e}. Then let τ_{e}^{s+1} = τ. For i < e, let τ_{i}^{s+1} = τ_{i}^{s}. For i ≤ s − e + 1, let τ_{e+i}^{s+1} = τ^{⌢}1^{i}. Now let k(s + 1) = k(s) + s − e + 1 and define T^{s+1} to be the union of T^{s} with the set of the following strings. First, for any σ ∈ T^{s} of length k(s) and any i ≤ s − e + 1, the extension σ^{⌢}0^{i}. Next, for any i ≤ s − e + 1, and any j ≤ s − e + 1 − i, the extension τ^{⌢}(1^{i})^{⌢}(0^{j}). Finally, for all i ≤ e, T^{s+1} contains all of the strings in S_{b}(τ_{i}^{s+1⌢}0) of length ≤ k(s). (Of course these are all in S_{b}^{k(s+1)}(τ_{e}^{s+1⌢}0).

If there is no such e, just let τ_{i}^{s+1} = τ_{i}^{s} for all i ≤ s and let τ_{s+1}^{s+1} = τ_{s}^{s}^{⌢}1. Let k(s + 1) = k(s) and let T^{s+1} contain all strings in T^{s} together with all strings σ^{⌢}0 where σ ∈ T^{s} and the string τ_{s+1}^{s+1}, as well as all of the strings in S_{b}(τ_{i}^{s+1⌢}0) of length ≤ k(s).

Observe that in either case, we have extended all nodes in T^{s} by at least one node in T^{s+1}, so that T will have no dead ends.

Claim 5. For every e, the sequence τ_{e}^{s} converges to some limit τ_{e}.

Proof of Claim 5: This is exactly as above in the α = 1 case. □

Claim 6. For any e, the set of extensions of τ_{e}^{⌢}0 in T are just the points in S_{b}(τ_{e}^{⌢}0).

Proof of Claim 6: Let s be the first stage at which τ_{e}^{s} = τ_{e}. Then we know that k(r) < lh(τ_{e}) for all r < s, so that there were no extensions of τ_{e} in T^{s}. From stage s onwards, the construction always puts the same extensions of τ_{e}^{⌢}0 in T that it puts into S_{b}(τ_{e}^{⌢}0). □

Claim 7. For any e and any stage s such that τ_{e+1}^{s+1} = τ_{e+1}^{s}, there are no new branches added at stage s + 1 which extend τ_{e}^{s⌢}1 but do not extend τ_{e+1}^{s}.

Proof of Claim 7: It follows from the construction that branches are added at stage s + 1 only if they are extensions of some τ_{i}^{s+1⌢}0 which lie in S_{b}(τ_{i}^{s+1⌢}0). If τ_{e}^{s⌢}1 ≺ σ but τ_{e}^{s} is not ≺ σ, then σ cannot extend any τ_{i}^{s+1⌢}0. □

Now let A be the union of the set of τ_{e}. It follows from Claims 6 and 7 and the discussion preceding the construction that D^{α}(P) = {A}.

It remains to be shown that P is thin.

Claim 8. If τ_{e} ∈ T_{e}, then every extension of τ_{e} which is in T is also in T_{e}.

Proof of Claim 8: This is exactly the same as the corresponding result (Claim 3) for the case α = 1. □

It follows from Claim 8 and the discussion preceding the construction that P = [S_{a}(σ_{0})] is thin.

A few words need to be said about why the trees S_{a} are uniformly recursive in a. The definition of the trees S_{a} is by effective transfinite induction which is justified by the recursion theorem. See Rogers [28, Chapter 11] for details. This construction is uniformly effective.

Next we consider the limit case of the construction. We will omit most of the details since they are similar to those in the successor case.

(Case 2) o(a) = α is a limit ordinal. In this case, compute the sequence b_{0} < b_{1} < … of {b : o(b) < o(a)} in numerical order and proceed as follows to the construction of the tree T = S_{a}(σ_{0}), the sequence τ_{0}, τ_{1}, …, with τ_{e} ≺ τ_{e+1} for all e, and the point A = ∪_{i}τ_{i} with the same properties as in the successor case, except for

(1)′ For each e, the set of strings in T which are compatible with τ_{e}^{⌢}0 is precisely S_{b_{e}}(τ_{e}^{⌢}0).

As in the successor case, the three properties are sufficient to make P = [T] thin and to have D^{α}(P) = {A}.

For each e, let β_{e} = o(b_{e}).

In the proof that D^{α}(P) = {A}, we have the following changes. If A ↾ n = τ_{e}, then D^{β}(P ∩ U(n)) is empty if and only if β > β_{e}. It follows that for any e, D^{β_{e}}(P ∩ U(n)) is nonempty for infinitely many n, that is, all n with A ↾ n = τ_{i} for i ≥ e. Thus, for any e, D^{β_{e}}(P) is infinite and therefore contains A. Since β is the supremum of the β_{e}, it follows that A ∈ D^{β}(P). On the other hand, for every n, D^{β}(P ∩ U(n)) is empty. But any element of P other than A must lie in one of the P ∩ U(n). It follows that only A can be in D^{α}(P).

This shows that D^{α}(P) = {A} as desired.

The proof of the thinness of P goes through as before.

Finally, let us see why the construction is effective at a limit stage. This is because, to determine whether a string of length s is in the tree, we only need to consider at most the trees S_{b_{e}} where e ≤ s. Thus we have gone down in the hierarchy of notations from a to at most b_{e}. As discussed above, the fact that the ordinals referred to in the construction are strictly decreasing implies that the construction is effective. □

Now consider the special case of Theorem 2.2 for α = 1. Since there are no dead ends in the tree constructed, it follows from Lemma 2.1 of [2] that the unique nonisolated point A is recursive in 0′, that is, Δ_{2}^{0}. We now want to see whether we can improve this result in two possible ways. First, can A actually be an r. e. set? Second, can A have any arbitrary degree below 0′? Now if we do not require that the tree has no dead ends, we know that for Π_{1}^{0} classes which are not necessarily thin we might even have A Turing equivalent to 0′′. Therefore we would also like to see whether we can get A to have degree 0′′.

We begin with a general method of obtaining a recursively enumerable set A and a Π_{1}^{0} class P (not necessarily thin) such that D(P) = {A}.

Let us say that a subset B of a set A = {a_{0} < a_{1} < ⋯ } is an initial subset of A if, for any b ∈ B and any a ∈ A, if a < b then a ∈ B. Thus the initial subsets of A are A itself and all subsets of the form A_{n} = {a_{0}, a_{1}, …, a_{n−1}} for finite n. Let P (A) be the class of initial subsets of A.

Definition. A set A = {a_{0} < a_{1} < … } is said to be retraceable if there is a partial recursive function Φ such that, for any n, Φ(a_{n+1}) = a_{n}.

Retraceable sets were introduced by J.C.E. Dekker and J. Myhill in [6]. Observe that if A is a retraceable Π_{1}^{0} set, then the function Φ may be modified to obtain a total recursive retracing function Φ^{+} as follows. Given an input a, simultaneously enumerate the r. e. set E = (ω\)A ∪ {a_{0}} while attempting to compute Φ(a). If a is enumerated into E before Φ(a) converges, let Φ^{+}(a) = 0; if not, then eventually Φ(a) must converge and we let Φ^{+}(a) = Φ(a). Thus Φ^{+} is a total recursive function and Φ^{+}(a_{n+1}) = a_{n} for all n.

Lemma 2.3. A Π_{1}^{0} set A = {a_{0} < a_{1} < ⋯ } is retraceable if and only if there is a recursive function Ψ such that, for all n, Ψ(a_{n}) = n.

Proof. If A is retraceable, let Φ be a retracing function. Then given a ∈ A, we can repeatedly apply Φ to count the number of elements of A below a. On the other hand, suppose that we have the function Ψ with Ψ(a_{n}) = n. Then given a = a_{n+1} ∈ A, we can compute from Ψ that there are exactly n + 1 elements of A below a. Then we can recover the sequence a_{0} < ⋯ < a_{n} by searching for a stage at which the remaining a − n − 1 numbers below a have all fallen out of A. Ψ ↾ A can be extended to the complement of A in the same way that the retracing function was extended above. □

It is clear that the class P (A) of initial subsets of any set A is closed and that, if A is infinite, then D(P (A)) = {A}. Our next result provides a natural family of Π_{1}^{0} classes with Cantor-Bendixson rank one.

Lemma 2.4. The set A = {a_{0} < a_{1} < … } is Π_{1}^{0} and retraceable if and only if the class P(A) of initial subsets of A is Π_{1}^{0}.

Proof. Suppose that A = {a_{0} < a_{1} < … } is Π_{1}^{0} and retraceable, and let Φ be a recursive function such that Φ(a_{n+1}) = a_{n} for all n. Also, let A^{s} denote the recursive approximation to the set A at stage s. Now define the recursive tree T as follows.

< b_{0}, b_{1}, …, b_{n}, s >∈ T ⟺ (∀i ≤ n)(b_{i} ∈ A^{s} & (i > 0 → Φ(b_{i}) = b_{i−1})).

It is easy to check that [T] = P (A), so that P (A) is Π_{1}^{0}.

Now suppose that P (A) is Π_{1}^{0}. Then we have a recursive tree T such that, for any a = a_{n+1} ∈ A, there is only one string σ =< a_{0}, a_{1}, …, a_{n}, a_{n+1} >^{⌢} 1 of length a + 1 and ending in 1, which has an extension in [T]; then Φ(a) = a_{n} can be decoded from σ. To find σ, we just search through all strings of length m > a until we find m large enough so that all strings τ in T, of length m and with τ(a) = 1, start with the same initial segment (σ) of length a + 1. To see that A is a Π_{1}^{0} set, recall that Ext(T) is Π_{1}^{0} and observe that

a ∈ A ⟺ (∃σ)[lh(σ) = a + 1 & σ ∈ Ext(T) & σ(a) = 1].

□

This Lemma now gives a quick proof that any retraceable non-recursive Π_{1}^{0} set A = {a_{0} < a_{1} < ⋯ } is hyperimmune, that is, not dominated by any recursive function. This result is Theorem T4 of [6].

Lemma 2.5. (Dekker-Myhill) If A = {a_{0} < a_{1} < ⋯ } is a retraceable nonrecursive Π_{1}^{0} set, then A is hyperimmune

Proof. By Lemma 2.4, P (A) is a Π_{1}^{0} class. Now suppose by way of contradiction that f were a recursive function which dominated A. Then the set {A} would be the intersection of P (A) with the following Π_{1}^{0} class:

{B : (∀n)(card(B ∩ {0, 1, …, f(n)}) ≥ n}.

Thus {A} would be a Π_{1}^{0} class, so that A would be recursive by Lemma 1.1. This contradiction demonstrates the Lemma. □

Now the class P (A) has the derivative structure that we want, that is, the set A always has rank one in P (A) and all other sets in P (A) have rank 0. If A is Π_{1}^{0}, then we would like to express P (A) as the class [S] of paths through a recursive tree S with no dead ends for two reasons. First, we know from [1] that if A has rank one in [S] where S is recursive and has no dead ends, then A is recursive in 0′; thus we would like to try to get such a representation for any set recursive in 0′. Second, the question of whether a recursive tree has no dead ends will will be an important consideration in the study of recursive Boolean algebras in Section 4.

Lemma 2.6. For any infinite set A, P(A) is closed and D(P (A)) = {A}. Furthermore, if A is a retraceable Π_{1}^{0} set, then there is a recursive tree S with no dead ends such that D([S]) = {A}.

Proof. As above, let A = {a_{0}, a_{1}, … } where a_{0} < a_{1} < ⋯ and let A_{e} = {a_{i} : i < e}. It is clear that A is the limit of the sets A_{e}, so that A ∈ D(P (A)). Now, for any e, define the clopen set U_{e} to be

{C : a_{e} ∉ C & (∀i < e)[a_{i} ∈ C]}.

Then {A_{e}} = P ∩ U_{e}, so that A_{e} is isolated in P (A). It follows that D(P) = {A}. Now any set B not in P (A) either contains an element b not in A, so that B ∈ {C : b ∈ C}, an open set disjoint from P (A) or else belongs to one of the sets U_{e} above. This shows that P (A) is closed.

Now if A is retraceable and Π_{1}^{0}, then it follows from Lemma 2.4 that P (A) is Π_{1}^{0}. However, the recursive tree T as defined in Lemma 2.4 such that P (A) = [T] will quite possibly have dead ends. To get a tree with no dead ends, we have to add a few more points to the set P (A).

Let A^{s} be the s^{th} recursive approximation to the set A, so that A^{s+1} ⊂ A^{s} for all s and A = ∩_{s}A^{s}. Let Φ be a retracing function for A. Now define the recursive tree S by

< b_{0}, b_{1}, …, b_{n}, s >∈ S ⟺ (∀i ≤ n)(b_{i} ∈ A^{b_{n}} & (i > 0 → Φ(b_{i}) = b_{i−1})). S has no dead ends because for any string σ ∈ S, it is clear that σ^{⌢}0 ∈ S. By

comparing this to the definition of the tree T with [T] = P (A) in Lemma 2.4, we see that T ⊂ S, so that P (A) ⊂ [S]. It follows that A ∈ D([S]). Now the elements of [S] \ [T] must differ from A somewhere. We will use this to show that they all have rank one. Let B = {b_{0} < b_{1} < ⋯ } ∈ [S] differ from A. Observe that from the definition of S we must have Φ(b_{n+1}) = b_{n} for all n. Now there are two possibilities.

First, B might be a subset of A. In this case, the fact that Φ(b_{n+1}) = b_{n} for all n implies that B is one of the initial subsets A_{n} = {a_{0}, …, a_{n−1}} of A which was already in P (A). Now let s be a stage large enough so that all of the numbers between a_{n−1} and a_{n} have fallen out of A^{s} and let σ =< a_{0}, …, a_{n−1}, s >. Then it is clear that I(σ) ∩ [S] = {A_{n}}. Thus B is isolated in [S].

The other possibility is that B is not a subset of A. In this case, let b be the least element of B \ A and let s be a stage such that b ∉ A^{s}. Let σ = B ↾ s. It follows from the definition of S given above that B = σ^{⌢}0^{ω} and that I(σ) ∩ [S] = {B}. Thus again B is isolated in [S].

It follows that D([S]) = {A} as desired. □

We now construct a thin Π_{1}^{0} class P with Cantor-Bendixson rank 1 such that the unique nonisolated point in P is a Π_{1}^{0}-complete set.

The following Lemma will be needed.

Lemma 2.7. Suppose that the set A = {a_{0} < a_{1} < … } is defined recursively by a Π_{1}^{0} relation Q(x,y) such that, for all n and x, x = a_{n} ⟺ Q(x, < a_{0}, …, a_{n−1} >). Then A is a Π_{1}^{0} set and is retraceable.

Proof. Let Q have uniformly recursive approximations Q^{s}(x, y) such that Q^{s+1}(x, y) → Q^{s}(x, y) for all x,y and s. Now define the uniformly recursive relation R^{s}(n, x) by the following recursion. R^{s}(n, x) ⟺ (∃x_{0} < x_{1} < ⋯ < x_{n−1} < x)[Q^{s}(x, < x_{0}, …, x_{n−1} >) & (∀i < n)R^{s}(i, x_{i})].

Claim. For all n, x = a_{n} ⟺ (∀s)R^{s}(n, x).

Proof of Claim: The proof is by induction on n. In the case that n = 0, it is clear that R^{s}(0, x) ⟺ Q^{s}(x, <>), so that

(∀s)R^{s}(0, x) ⟺ (∀s)Q^{s}(x, <>) ⟺ Q(x, <>) ⟺ x = a_{0}.

Now take as our induction hypothesis that the claim is true for all i < n. We will then prove the claim for n.

Suppose first that x = a_{n}. Then let x_{i} = a_{i} for all i < n. By induction we have R^{s}(i, x_{i}) for all s and by the inductive definition of a_{n} from Q, we have Q^{s}(x, < x_{0}, …, x_{n−1} >). It follows that R^{s}(n, x) for all s.

Next suppose that R^{s}(n, x) for all s. Choose s large enough so that

(∀i < n)(∀y < x)(R^{s}(i, y) ⟺ y = a_{i}).

This can be done since the claim is assumed to be true for i < n.

Now, since R^{s}(n, x), we have x_{0} < x_{1} < … < x_{n−1} < x such that R^{s}(i, x_{i}) for all i < n and such that Q^{s}(x, < x_{0}, …, x_{n−1} >). Now by the choice of s, R^{s}(i, x_{i}) implies that x_{i} = a_{i}. Then Q^{s}(x, < x_{0}, …, x_{n−1} >) for all sufficiently large s, which implies that x = a_{n}. This proves the claim. □

Now the set A is Π_{1}^{0} since

a ∈ A ⟺ (∃i ≤ a)(∀s)R^{s}(i, a).

To show that A is retraceable we will show that there is a recursive function f with f(a_{n}) = n for all n. Given a, we know that there is at most one n ≤ a such that a = a_{n}, that is, such that (∀s)R^{s}(n, a). Then f(a) can be computed by searching for an s large enough so that R^{s}(n, a) for only one number n ≤ a and letting f(a) = n. □

This result can now be applied to give a quick proof of the following theorem from [1, p. 979]. Part (a) is Theorem T3 of [6]. We state the theorem to contrast with upcoming theorems on thin classes and sketch the proof to indicate how Lemma 2.7 will be applied later.

Theorem 2.8. (a) Every r. e. set B is Turing equivalent to a retraceable Π_{1}^{0} set A.

(b) Every r. e. non-recursive set B is Turing equivalent to a set A of rank one; furthermore there is a recursive tree T with no dead ends such that D([T]) = {A}.

Proof. (a) Let the r. e. set B be the union of uniformly recursive sets B^{s} and define the set A by Π_{1}^{0} recursion as follows.

s = a_{0} ⟺ [(s = 0 & 0 ∉ B) ∨ (0 ∈ B^{s} & (∀x < s)(0 ∉ B^{x}))], and s = a_{n+1} ⟺ [(s = a_{n} + 1 & (n + 1 ∉ B ∨ n + 1 ∈ B^{s})) ∨ (s > a_{n} & n + 1 ∈

B^{s} & (∀x < s)(n + 1 ∉ B^{x}))].

It is clear from this definition that A is recursive in B. On the other hand, for any n, we have n ∈ B ⟺ n ∈ B^{a_{n}}, so that B is recursive in A.

It follows from Lemma 2.7 that A is Π_{1}^{0} and retraceable.

(b) This is immediate from (a) and Lemma 2.6. □

Now we apply this same technique to obtain thin classes.

Theorem 2.9. There is a Π_{1}^{0} set A of degree 0′ and a thin Π_{1}^{0} class P such that D(P) = {A}.

Proof. Let B = 0′ be the union of uniformly recursive sets B^{s}. Let T_{0}, T_{1}, … be an effective enumeration of the primitive recursive trees on 2^{<ω}. We will define a Π_{1}^{0} retraceable set A = {a_{0} < a_{1} < ⋯ } and a corresponding Π_{1}^{0} class P = P (A) of initial subsets of A, with the following properties.

(1) For any e, e ∈ B ⟺ e ∈ B^{a_{e}}.

(2) For any Π_{1}^{0} class P_{e} = [T_{e}], if A ∈ P_{e}, then A_{n} ∈ P_{e} for all n ≥ e.

Recall that P (A) = {A} ∪ {A_{n} : n < ω}, where

A_{n} = {a_{i} : i < n}.

Let us see why these properties imply the theorem. Lemma 2.6 implies that D(P) = {A}.

It follows from property (1) that 0′ is recursive in A. Since A is Π_{1}^{0}, this makes A a set of degree 0′.

To see that P is a thin class, suppose that P_{e} = [T_{e}] is a Π_{1}^{0} subclass of P. Recall from Lemma 2.6 that, for each n, A_{n} is isolated in P, so that we have a clopen set U_{n} such that P ∩ U_{n} = {A_{n}}. For use in later theorems, we will show directly from property (2) that P is thin, without using the fact that A is non-recursive and D(P) = {A}. There are two cases.

(Case 1) If A ∉ P_{e}, then, since A is the only limit point of P and P_{e} ⊂ P, P_{e} must be finite. Now let J = {n : A_{n} ∈ P_{e}} and let U = ⋃_{n∈J} U_{n}. Then P_{e} = P ∩U.

(Case 2) If A ∈ P_{e}, then it follows from property (2) that A_{n} ∈ P_{e} for all n ≥ e. Thus P \ P_{e}} is finite. Now let I = {n : A_{n} ∉ P_{e}} and let V = 2^{ω} \ ⋃_{n∈I} U_{n}. Then P_{e} = P ∩ V.

This shows that P is minimal. Since A is a non-recursive member of P, it follows from Lemma 2.1 that P is also thin.

The sequence a_{0} < a_{1} ⋯ is defined by the following Π_{1}^{0} recursion. For each n, a_{n} is the least number a which satisfies the following.

(i) For all m < n, a_{m} < a. (ii) n ∈ B → n ∈ B^{a}. (iii) For all m < n, either < a_{0}, …, a_{n−1}, a >∉ T_{m} or (∀x)(< a_{0}, …, a_{n−1}, x >∈ T_{m}). It is clear that the three properties above define a Π_{1}^{0} relation Q_{1} so that a_{n} is

the least number a which satisfies Q_{1}(a, < a_{0}, …, a_{n−1} >). Now we can take into account the minimality condition on a, and define a Π_{1}^{0} relation Q such that

x = a_{n} ⟺ Q(x, < a_{0}, …, a_{n−1} >), by making Q(x, < x_{0}, …, x_{n−1} >) hold if and only if Q_{1}(a, < x_{0}, …, x_{n−1} >) and, for all x < a, either

(0) x ≤ x_{n−1} or

(1) n ∈ B^{a} \ B^{x} or

(2) for some m < n, < x_{0}, x_{1}, …, x_{n−1}, x >∈ T_{m} & < x_{0}, x_{1}, …, x_{i}, a >∉ T_{m}. Thus the set A is defined by a Π_{1}^{0} recursion and is therefore Π_{1}^{0} and retraceable

by Lemma 2.7.

It remains to check the final property of the construction. Suppose therefore that A ∈ [T_{e}] and let n ≥ e. Then in the definition of a_{n}, we must have < a_{0}, …, a_{n} >∈ T_{e}, since this string is the characteristic function of A restricted to a_{n}. It follows from the definition of A that < a_{0}, …, a_{n−1}, x >∈ T_{e} for every x > a_{n−1}. But this string is the characteristic function of A_{n} restricted to x. It follows that A_{n} ∈ [T_{e}], as desired.

This demonstrates property (2) and completes the proof of Theorem 2.9. □

Let us now define the thin rank of a set A to be the least ordinal α, if any, such that, for some thin Π_{1}^{0} class P, |A|_{P} = α. Thus we have shown in Theorem 2.8 that there is a co-r. e. set A of degree 0′ with thin rank one. Several natural questions arise here. First, can this result be extended to all degrees below 0′′ and comparable with 0′, as was the case for rank one in [1]? Second, can the result be extended to find sets of degree 0^{(α)} which have thin rank related to α, again as was done in [1]? The following results show strongly that neither of these extensions can be achieved.

Recall that Ext(T) is the set of nodes in T such that some infinite extension x of σ is in [T]. It was shown in Lemma 1.2 of [1] that, if T is recursive, then Ext(T) is a Π_{1}^{0} set. Of course, T has no dead ends if and only if Ext(T) = T. It also follows from Lemma 1.2 of [1] that if |A|_{[T]} = 1, then A is recursive in Ext(T)′; thus if T is recursive then A is always recursive in 0′′ and, if in addition T has no dead ends then A is recursive in 0′.

The join A ⊕ B of two sets A and B is defined to be A ⊕ B = {2n : n ∈ A} ∪ {2n + 1 : n ∈ B}.

Theorem 2.10. (a) If A is any element of a thin Π_{1}^{0} class, then A′ is recursive in A ⊕ 0′′.

(b) If A is any element of a thin Π_{1}^{0} class P = [T] with Ext(T) recursive, then A′ is recursive in A ⊕ 0′.

Proof. (a) Let T be a recursive tree such that P = [T] is a thin Π_{1}^{0} class and let A ∈ P. Recall that A′ = {e : {e}^{A}(e) ↓}. Now, for any e, let

Q_{e} = {C : {e}^{C}(e) ↑}.

The key idea of the proof is that Q_{e} is a Π_{1}^{0} class. Thus, since P is thin, we must have for every e, a clopen set U(e) such that P ∩ Q_{e} = P ∩ U(e).

Now suppose that {e}^{A}(e) ↑. Then A ∈ P ∩ Q_{e}, so that A ∈ P ∩ U(e). Thus there is some initial segment σ = A ↾ n such that every infinite extension of σ is in U(e). This means that every infinite extension B of σ which is in P is also in Q_{e}.

Now define the Π_{2}^{0} relation R(e, σ) which says that σ forces any extension to be in Q_{e} by

R(e, σ) ⟺ (∀τ ≻ σ)[(τ ∈ T & {e}^{τ} (e) ↓) → τ ∉ Ext(T)].

Then R is recursive in 0′′. Here is the procedure for computing whether or not e ∈ A′ from A together with 0′′. Search for the least number n such that σ = A ↾ n satisfies one of the following.

(1) {e}^{σ}(e) ↓. In this case, we have e ∈ A′.

or

(2) R(e, σ). In this case, σ forces that e ∉ A′.

It is clear from the discussion above that exactly one of these two cases will apply.

(b) 0bserve that if Ext(T) is recursive, then the relation R defined above will be Π_{1}^{0}. It follows then that A′ is recursive in A ⊕ 0′. □

Recall that a set A is said to be low if A′ ≡_{T} 0′.

Corollary 2.11. (a) No set A such that 0′′ ≤_{T} A can belong to any thin Π_{1}^{0} class.

(b) For any ordinal α > 1, no set A of degree 0^{(α)} can belong to any thin Π_{1}^{0} class.

(c) No set A such that 0′ ≤_{T} A can belong to any thin Π_{1}^{0} class P = [T] with Ext(T) recursive.

(d) If A has rank one in a thin Π_{1}^{0} class P = [T] with Ext(T) recursive, then A is low.

Proof. (a) Suppose that 0′′ ≤_{T} A. Then A ⊕ 0′′ is Turing equivalent to A. But if A belonged to a thin Π_{1}^{0} class, then A′ would be Turing reducible to A ⊕ 0′′, by Theorem 2.10. This leads to the contradiction that A′ is Turing reducible to A.

(b) This is immediate from (a), since 0′′ is Turing reducible to 0^{(α)} whenever α > 1.

(c) Suppose 0′ ≤_{T} A. Then A ⊕ 0′ is Turing equivalent to A. It follows from Theorem 2.10 that A cannot belong to a thin Π_{1}^{0} class P = [T] with Ext(T) recursive.

(d) Since A has rank one in a Π_{1}^{0} class P = [T], we have A recursive in 0′ by Lemma 1.2 of [1]. Now since P is thin and Ext(T) recursive, we have A′ recursive in A ⊕ 0′, so that A is recursive in 0′. □

Now recall that every r. e. set is Turing equivalent to a set having rank one, although there are particular r. e. sets (such as 0′) which are not ranked. The situation is different for thin rank.

Here are two more observations about the relation between Ext(T) and the the unique nonisolated set A in [T]. It follows from Theorem 2.8 that we may have Ext(T) recursive while A has arbitrary r. e. degree. On the other hand, it is not hard to construct a recursive tree T with D([T]) = {0^{ω}} and Ext(T) of arbitrary r. e. degree. (Given a coinfinite r. e. set B which is the union of uniformly recursive sets B^{s}, let T consist of all strings of the form 0^{n} together with strings of the form 0^{n⌢}1^{⌢}0^{s} where 1 ∉ B^{s}. Then Ext(T) = {0^{n} : n < ω}∪{0^{n⌢}1^{⌢}0^{s} : n ∉ B, s < ω}, so that Ext(T) has the same degree as B. Furthermore, [T] = {0^{ω}} ∪ {0^{n⌢}10^{ω} : n ∉ B}, so that D([T]) = {0^{ω}}.)

Theorem 2.12. For any r. e. degree d, there is a recursive tree T and an r. e. set A of degree d such that D(P) = {A} and Ext(T) has degree d.

Proof. Let B be an r. e. set of degree d , and let the Π_{1}^{0} retraceable set A = {a_{0} < a_{1} < ⋯ } be given by Theorem 2.8. Now let T be the tree defined in Lemma 2.4 with P (A) = [T]. It follows that

Ext(T) = {< a_{0}, a_{1}, …, a_{n−1}, s >: n ∈ ω, s > a_{n−1}}.

It is easy to check that Ext(T) is Turing equivalent to A. □

The following result indicates a general situation wherein Ext(T) is recursive in the unique nonisolated set A in [T].

Theorem 2.13. Let T be a recursive tree, let P = [T] and suppose that P has a unique nonisolated path A such that A is a Π_{1}^{0} set. Let S(A) be the class of subsets of A. Then

(a) If P ⊂ S(A), then A is recursive in Ext(T).

(b) If P is thin, then A is recursive in Ext(T).

Proof. (a) For any n, test whether n ∈ A as follows. Look for a σ of length n + 1 such that σ ∈ Ext(T) and such that σ(n) = 1. If you find such a σ, then there is an infinite extension B of σ with B ∈ P and n ∈ B. But B ⊂ A since P ⊂ S(A), so that n ∈ A. On the other hand, we have A ∈ P by assumption, so if n ∈ A, then A ↾ (n + 1) = σ ∈ Ext(T) and σ(n) = 1. Thus this procedure computes A from Ext(T).

(b) Consider the Π_{1}^{0} subclass Q = P ∩ S(A) of P. Since P is thin, we must have Q = P ∩ U for some clopen set U = I(σ_{0}) ∪ ⋯ ∪ I(σ_{k}). Now define the recursive tree T_{Q} to be

T_{Q} = {σ ∈ T : σ is compatible with σ_{i}, for some i ≤ k}.

Then it is clear that Q = [T_{Q}] and that

Ext(T_{Q}) = {σ ∈ Ext(T) : σ is compatible with σ_{i} for some i ≤ k} is recursive in Ext(T). Now we have Q ⊂ S(A), so that A is recursive in Ext(T_{Q}) by part (a). It follows that A is recursive in Ext(T). □

Corollary 2.14. Let T be a recursive tree and let P be a thin Π_{1}^{0} class such that P = [T]. If Ext(T) is recursive, then P cannot contain any non-recursive Π_{1}^{0} (or RE) sets.

Proof. It follows from Theorem 2.13 that if P contains a Π_{1}^{0} set A, then A is recursive in Ext(T) and therefore recursive. If A is an r. e. set, then ω \ A is Π_{1}^{0} and belongs to the thin Π_{1}^{0} class {ω \ X : X ∈ P }. □

We next show that Theorem 2.8 cannot be strengthened from ”rank” to ”thin rank”.

3. Maximal r. e. sets.

The second question to be considered in this paper is the possible Cantor-Bendixson rank of a maximal set A. Recall that a coinfinite r. e. set A is said to be maximal if there is no coinfinite r. e. set B such that B \ A is infinite. We will show that such a set can have rank two but cannot have rank one. Since the rank of a set and the rank of its complement are the same, we will actually consider co-r. e. sets.

In section 2, we showed that a retraceable non-recursive Π_{1}^{0} set A will always have Cantor-Bendixson rank 1. Now it is easy to see that a comaximal set A = {a_{0} < a_{1} < ⋯ } cannot be retraceable, since B = {a_{2n} : n < ω} is an infinite Π_{1}^{0} subclass of A with A \ B also infinite.

This leads us to the notion of a second-retraceable Π_{1}^{0} set.

Definition. A Π_{1}^{0} set A = {a_{0} < a_{1} < … } is said to be second-retraceable if there is a (total) recursive function Φ such that, for any a, b ∈ A with a < b, Φ(a, b) is the unique n such that a = a_{n}.

Now define the class P_{2}(A) to be the union of P(A) with the set of all A_{n} ∪ {b} where a_{n} < b and b ∈ A. It is clear that the class P_{2}(A) is closed, that D(P_{2}(A)) = P (A) and that D^{2}(P (A)) = {A}. Our next result provides a natural family of Π_{1}^{0} classes with Cantor-Bendixson rank two.

Theorem 3.1. The Π_{1}^{0} set A = {a_{0} < a_{1} < … } is second-retraceable if and only if the class P_{2}(A) is Π_{1}^{0}.

Proof. Suppose that A = {a_{0} < a_{1} < … } is second-retraceable and let Φ be a recursive function such that Φ(a_{n}, a_{m}) = n for all n < m. Let A^{(s)} denote the usual recursive approximation to the set A at stage s. Now define the recursive tree T as follows.

< b_{0}, b_{1}, …, b_{n}, b_{n+1}, s >∈ T ⟺ (∀i ≤ n + 1)(b_{i} ∈ A^{(s)} & Φ(b_{n}, b_{n+1}) = n). It is easy to check that [T] = P_{2}(A), so that P_{2}(A) is Π_{1}^{0}. We leave the other direction to the reader. □

Theorem 3.2. There is a maximal set A with Cantor-Bendixson rank at most two.

Proof. The Friedberg construction of a co-maximal set A = {a_{0} < a_{1} < … } is modified to yield such a set A which is second-retraceable. (This suffices by Theorem 3.1 and the remarks just above it.) Specifically, we meet the comaximality requirements in standard fashion and, in addition, ensure that whenever a_{e}^{s} ≠ a_{e}^{s+1}, then a_{e+1}^{s+1} ≥ s + 1. This easily implies that A is second-retraceable with Φ(a, b) defined to be the unique n with a = a_{n}^{b}.

The details are left to the reader. □

We next show that Theorem 3.2 is the best possible result, that is, that no maximal set can have Cantor-Bendixson rank 1. In fact we consider a wider class than the comaximal sets. An infinite set A is called hyperhyperimmune (h. h. i.) if there is no uniformly r. e. sequence {U_{e}} of pairwise disjoint finite sets all intersecting A.

Theorem 3.3. If A is a ∑_{2}^{0} h. h. i. set, then there is no Π_{1}^{0} class P ⊆ 2^{ω} with D(P) = {A}.

Proof. The following lemma shows that if P ⊆ 2^{ω} is a Π_{1}^{0} class and D(P) = {A} then A has a property akin to retraceability. The rest of the proof is then to show that this property is not possessed by any h. h. i. set. (There is an analogous but easier result that no ∑_{2}^{0} retraceable set is h. h. i. . To see the latter, note that every ∑_{2}^{0} hhi set is s. h. h. i. and no retraceable set is s. h. h. i. (see Yates [32]), where A is s. h. h. i. if there is no uniformly r. e. sequence of pairwise disjoint r. e. sets (not necessarily finite), all intersecting A.)

Lemma 1. Suppose that P ⊆ 2^{ω} is a Π_{1}^{0} class and D(P) = {A}. Then there are uniformly r. e. cofinite sets Y_{0}, Y_{1}, … such that

(∀x ∈ Y_{i} ∩ A)[|{y : y ∈ A & y < x}| ≥ i]

(Aside: The connection with retraceability is the following. We will not need that each Y_{i} is cofinite, only that A−Y_{i} is finite. Then every retraceable set satisfies this slightly weaker version of the lemma with Y_{i} = {x : (∃j ≥ i)[ψ^{j}(x) = a_{0}]}, where ψ is a retracing function for A, ψ^{i} is the result of iterating ψ i times, and a_{0} is the least element of A. Also it is easy to see that the conclusion of the lemma as stated holds of A whenever A is retraced by a total recursive function.)

Proof of Lemma 1: Let E be the set of all strings σ such that σ ⊆ B for some B ∈ P . Then E is a co−r.e. set of strings. Let S(σ, x) = |{y : y < x & σ(y) = 1}| , and define

Y_{i} = {x : (∀σ)_{lh(σ)=x+1}[S(σ, x) < i & σ(x) = 1 → σ ∉ E]}

Since S is recursive and E is co − r.e., Y_{i} is r.e. uniformly in i . If x ∈ A and card(A ∩ {0, 1, …, x − 1}) < i, let σ = A ↾ x + 1 . Then σ witnesses that x ∉ Y_{i} .

Thus it remains only to show that each Y_{i} is cofinite. Suppose not and fix i with Y_{i} coinfinite. For each x ∉ Y_{i} , let σ_{x} witness that x ∉ Y_{i} , i.e., |σ_{x}| = x + 1, σ_{x}(x) = 1 , S(σ_{x} , x) < i and there is a set B_{x} ⊇ σ_{x} with B_{x} ∈ P . There cannot exist i + 1 distinct x’s with the same B_{x} (since if z is the largest of i + 1 such x’s, σ_{z} takes the value 1 on at least i arguments < z , i.e. on all the other x’s). Thus there are infinitely many distinct sets B_{x} as x ranges over \overline{Y_{i}}. By the compactness of 2^{ω} , there is a set B which is a limit point of such B_{x}’s, and B ∈ P since P is closed. Now card(B) ≤ i , since each B_{x} has < i elements < x. Also we may assume that A is infinite since otherwise the lemma is trivial with Y_{i} = ω \ A for all i . Hence B ≠ A , so B is a limit point of P distinct from A. This contradiction completes the proof of Lemma 1. □

To complete the proof of the theorem, we fix sets Y_{i} as in Lemma 1 and enumerate sets V_{i} which witness that A is not h.h.i., i.e., the sets V_{i} are uniformly r.e., pairwise disjoint, finite, and V_{i} ∩ A ≠ ϕ for all i. Let V_{i,s} be the finite set of numbers enumerated in V_{i} by the end of stage s. To make the sets V_{i} pairwise disjoint, we require that for each s there is at most one i with V_{i,s+1} ≠ V_{i,s} , and furthermore no element of V_{i,s+1} −V_{i,s} is in V_{j,s} for any j ≠ i. Let A^{s} be a recursive approximation to A as a ∑_{2}^{0} set, i.e., A^{s} is recursive uniformly in s, and A = {x : x ∈ A^{s} for all sufficiently large s}. To ensure that V_{i} is finite, we require that V_{i,s+1} ≠ V_{i,s} only if V_{i,s} ∩ A^{s} = ϕ. This clearly implies that V_{i} is finite if V_{i} ∩ A ≠ ϕ. The main job of the construction is to meet for each i the requirement P_{i} that V_{i} ∩ A ≠ ϕ. Let V_{i,s} be the set of numbers put into V_{i} by the end of stage s. First let us consider P_{0}. A primitive strategy for P_{0} is, at every stage s + 1 with V_{0,s} ∩A_{s} = ϕ to put the least number not in V_{i,s} for any i into V_{0,s+1}. The difficulty with meeting P_{0} is that every element a of A may possibly be put into some V_{i} for i > 0 at a stage s + 1 with V_{0,s} ∩ A_{s} ≠ ϕ. This difficulty can be overcome by requiring that an element x can be put into V_{i,s+1} for i > 0 only if x ∈ Y_{p,s} for some p > 0. Since the least element a_{0} of A is not in Y_{p,s} for any p > 0, this leaves a_{0} free to enter V_{0}. Although this idea suffices to meet P_{0}, it is still not clear how to meet P_{i} for i > 0. For instance, to meet P_{1} we should require that if x is put into V_{i} for i > 1, then x ∈ Y_{p} for some appropriately large value of p, so that it is guaranteed that an element of A−V_{0} is not put into any V_{i} for any i > 1 and hence is left free for V_{1}. The difficulty is that although V_{0} ∩A is finite we have no effective bound on the greatest i with a_{i} ∈ V_{0} ∩ A and thus no obvious way to choose p. In fact we obtain p by recursive approximation during the construction. To carry this out we define a notion “x is available for V_{i} at s + 1” meaning roughly that x ∈ Y_{p,s} for some p sufficiently large so that, if x ∈ A, there are sufficient elements y < x with y ∈ A to meet P_{j} for all j < i. To make it feasible to do this, we make the strategy for each P_{i} be kind to all P_{j} for j > i by requiring that x cannot be put into V_{i} if it is available for some V_{j} for some j > i. This is not too injurious to P_{i} because if x is available for V_{j} with j > i there should exist y < x which can be used to meet P_{i} . Furthermore, this restriction is helpful to P_{j} since it gives a stock of elements which will not be used by P_{i} and thus may be available for P_{j}. The construction is as follows:

Stage 0. Let V_{i,0} = ϕ for all i.

Stage s + 1. Let V_{i,s} be the set of numbers already in V_{i}. First define the notion “x is available for V_{i} at s + 1” by induction on i:

Definition. x is available for V_{i} at s + 1 if there exists p ≤ s such that x ∈ Y_{p,s} and for any set D ⊆ {y : y < x} of cardinality p and any j < i, D has an element available for V_{j} at s + 1 and not in V_{k,s} for any k < j.

Let i be the least number ≤ s with V_{i,s} ∩ A^{s} = ϕ such that, for some x, x is available for V_{i} at s + 1, x is not available at s + 1 for any V_{j} with i < j ≤ s, and x ∉ ∪_{j}V_{j,s}. Let V_{i,s+1} = V_{i,s} ∪ {x} for the least such x, and let V_{j,s+1} = V_{j,s} for all j ≠ i (or all j if no such i exists). This completes the construction.

Obviously, the sets V_{i} = ∪_{s}V_{i,s} are uniformly r. e. and pairwise disjoint. Also, a simple induction shows that if x is available for V_{i} at s, then x is available for V_{i} at all t > s. (The proof uses the fact that if D has an element u available for V_{j} and not in V_{k,s} for any k < j, then u remains available for V_{j} by inductive hypothesis and hence never enters any V_{k} with k < j by construction.) The following lemma completes the proof.

Lemma 2. For all j the following hold:

(i) All but finitely many numbers are available for V_{j} at cofinitely many stages. (ii) V_{j} ∩ A ≠ ϕ. (iii) V_{j} is finite.

Proof of Lemma 2: The proof is by induction on j. Assume that (i)-(iii) hold for all i < j.

(i) Let F be the set of numbers in any V_{i} for i < j or which, for some i < j , are never available for V_{i}. F is finite by inductive hypothesis, so let p exceed the cardinality of F. Let x be any element of the cofinite set Y_{p}. It is easily seen that x is available for V_{j} at cofinitely many stages. (This uses the fact that, for i < j, any element ever available for V_{i} is available for V_{i} at cofinitely many stages.)

(ii) There are two cases. First assume that no element of A is ever available for any V_{k} with k > j. Let x be the least element of A which is eventually available for V_{j} and not in V_{i} for any i < j. Such an x exists because A is infinite, (i) holds for j, and (iii) holds for i < j. Then, if V_{j} ∩ A = ϕ, we get x ∈ V_{j} by construction. (To see this, we observe that there are infinitely many stages s with V_{j,s} ∩ A_{s} = ϕ. This is clear if V_{j} is infinite. We may assume without loss of generality that we have chosen the recursive approximation {A_{s}} so that if F is any finite set disjoint from A there are infinitely many stages s with F ∩ A_{s} = ϕ [14, p. 430]. Thus also if V_{j} is finite and disjoint from A, there are infinitely many stages s with V_{j,s} ∩ A_{s} = ϕ.)

Now assume that some element of A is available for some V_{k} with k > j. Let x be the least element of A ever available for any V_{k} with k > j. Fix i > j and s so that x is available for V_{i} at s, and let p witness this availability. Since x ∈ A∩Y_{p,s}, there are at least p elements of A which are less than x. Let D consist of p such elements. Since x is available for V_{i}, there is an element u of D which is available for V_{j} at s, and not in V_{k,s} for any k < j. Since u < x, by the minimality condition on x, u is never available for any V_{k} with k > j, and hence also u ∉ V_{k} for any k > j. Also, since u ∉ V_{k,s} for all k < j and u is available for V_{j} at s, we get that u ∉ V_{k} for all k < j. If u ϵ V_{j}, we are done. Otherwise, we have the existence of a number which is not in any V_{k}, is never available for any V_{k} with k > j, and is eventually available for V_{j}. If V_{j} ∩A = ϕ, the construction eventually puts the least such number into A as in the first case above.

(iii) This is immediate from (ii) and the fact that V_{j} only gets a new element at s + 1 if V_{j,s} ∩ A_{s} = ϕ.

The proof of the lemma, and thus of the theorem, is complete. □

Open question: Is there any h. h. i. set (or any cohesive set) which is the unique nonisolated point of a Π_{1}^{0} class? The case where we require the set to be Π_{2}^{0} is also open.

Recall that in Theorem 2.15 we constructed an r. e. set A which does not belong to any thin Π_{1}^{0} class. The next result brings together the two central concepts of this paper, maximal sets and thin classes.

Theorem 3.4. There is a maximal set A which is not a member of any thin Π_{1}^{0} class.

Proof. The construction is a variation on the standard construction of a maximal set as in Soare [31, Ch. X]. We use a set of movable markers m_{e} which at stage s sit on the number m_{e,s} to describe our enumeration A_{s} of A. As usual the numbers m_{2e,s} are never in A_{s} and every number not in A_{s} is the position of some marker at stage s. However, there will be circumstances in which numbers of the form m_{2e+1,s} are in A_{s}. Another divergence from the general format of the standard construction is that we always move markers m_{2e} and m_{2e+1} together. Thus if we move either one, we move both. The purpose of this pairing of markers is to leave room to satisfy the requirements that A not be on any thin tree T_{i}. As usual when the least marker moved at stage s is m_{e} it is moved to a marker position m_{i,s} which is not in A_{s} for some i > e. The motion of the other markers and the enumeration of numbers into A is slightly perturbed from the standard procedure by our having to move markers in pairs.

Construction:

Recall that the e-state of a number x is the sequence (W_{0}(x), W_{1}(x), ...., W_{e−1}(x)). The e-state at stage s is simply the same sequence but with W_{i,s} replacing W_{i} for i < e. The e-states are ordered lexicographically. Markers are moved to maximize the minimum of the e-states of m_{2e,s} (and m_{2e+1,s} if m_{2e+1,s} is not in A_{s}). More precisely, at each even stage s of the construction we check for each e < s if one of the following two conditions hold:

1) m_{2e+1,s} is in A_{s} and there are marker positions m_{i,s} < m_{j,s} for some i > 2e+1 which are not in A_{s} and are in higher e-states than m_{2e,s}.

2) m_{2e+1,s} is not in A_{s} and there are marker positions m_{i,s} < m_{j,s} not in A_{s} such that i > 2e + 1 and the e-states of m_{i,s} and m_{j,s} are both higher than the minimum of the e-states of m_{2e,s} and m_{2e+1,s}.

If there is such an e < s, we let (e, i, j) be the (lexicographically) least such triple. We move m_{2e} and m_{2e+1} to m_{i,s} and m_{j,s} respectively. We also put all numbers m_{k,s} into A for 2e ≤ k < i and i < k < j. Markers m_{n} with n > 2e + 1 are moved in order to the first available marker positions which are not in A.

We next describe the odd stages of the construction which are designed to guarantee that A is not on any thin T_{i}. We have defined restraint functions and may put a number into A to satisfy the requirement for some T_{i} if it does not violate this restraint. We then impose some additional restraint to try to keep this requirement satisfied. There is almost no visible interaction between this argument and the e-state construction. When we put a number into A at an odd stage of the construction we move no markers and we move markers at even stages to maximize e-states as above without regard to the restraint imposed. Numbers less than some restraint entering A do, however, injure the restraint and reset it to 0. Let [i, j] be a standard coding of a pair (i, j) of natural numbers as a natural number.

We check if there is an e = [i, j] < s such that A_{s} ↾ m_{2e+1,s} has not been seen to be non-extendible in T_{i} (in s steps), m_{2e+1,s} is greater than R(i, s) and not in A_{s} and A_{s} ↾ m_{2e+1,s}^{⌢}1 has been seen to be non-extendible in T_{i}. If so, we let (i, j) be the lexicographically least such pair. We put m_{2e+1,s} into A but do not move any markers. We also define a restraint function r(i, s + 1) = m_{2e+1,s}. As usual, r(i, t) remains constant at this value until a stage t > s at which we put a number less than r(i, s + 1) into A. At such a stage we reset r(i, t) to 0. As is standard, R(i, s) = max{r(j, s) : j < i}.

Verifications:

Claim 1. Each marker eventually stops moving, i.e., for each e lim m_{e,s} exists and is less than ∞. We will denote this limit by m_{e}^{∗}. Hence ω \ A is infinite.

Proof of Claim 1: Suppose for the sake of an induction argument that all markers m_{k} for k < 2e have reached a limit by stage s_{0}. As each time we move m_{2e} and m_{2e+1} after s_{0} we increase the minimum of the e-states of their positions (ignoring m_{2e+1,s} if it is in A) and there are only finitely many e-states, it is clear that we can move them only finitely often. □

Claim 2. For each r, the r-states of the m_{e} which are not in A are eventually constant (as e → ∞) and so A is a maximal set.

Proof of Claim 2: We proceed by induction on r. We thus assume that for for all e > e_{0} > r the (r − 1)-state of m_{e} is constant for m_{e} ∉ A. Suppose for the sake of a contradiction that there are infinitely many final marker positions outside of A which are in each of the two possible r-states. Thus there is some e > e_{0} such that m_{2e}^{∗} or m_{2e+1}^{∗} (which is not in A) is in the lower r-state. By our assumption, we eventually reach a stage at which we see that two marker positions m_{k,s} and m_{n,s} both larger than m_{2e+1,s} = m_{2e+1}^{∗} are in the higher r-state. Our instructions for moving markers would now force us to move m_{2e} and m_{2e+1} for the desired contradiction. □

Claim 3. For each i and all sufficiently large j, m_{2[i,j]+1}^{∗} ∉ A and, if A ∈ [T_{i}], then A ↾ m_{2[i,j]+1}^{∗}^{⌢}1 is an extendible node on T_{i}.

Proof of Claim 3: We proceed by induction. Thus we may assume that m_{2[k,n]+1}^{∗} ∉ A for every k < i and every n > n_{0} for some n_{0}. We may also choose s_{0} such that, for k < i and any n, if m_{2[k,n]+1}^{∗} is in A, it is in A_{s_{0}}. Consider any marker m_{2[i,j]+1} whose final position is greater than s_{0} and has not been enumerated in A by stage s_{0}. (Clearly only finitely many markers are excluded by this proviso.) If the final position m_{2[i,j]+1}^{∗} of this marker is put into A at stage s (necessarily > s_{0}), then we claim that A ∉ [T_{i}]. It can be put in at stage s only if A_{s} ↾ m_{2[i,j]+1,s}^{⌢}1 is non-extendible on T_{i}. Putting m_{2[i,j]+1,s} into A makes A_{s} ↾ m_{2[i,j]+1,s}^{⌢}1 an initial segment of A_{s}. Our assumptions on s_{0}, the definition of the restraint function and the fact that this marker (and so each smaller one) has reached its final position guarantee that no further numbers can be enumerated in A below m_{2[i,j]+1,s}. Thus A ∉ T_{i}. In this case, no later final marker position m_{2[i,k]+1}^{∗} for k > j can be put into A at a stage t > s by construction. This same consideration applies in any situation in which A ∉ [T_{i}] : no final marker position larger than the initial segment of A that forces it off [T_{i}] can ever be put into A after the stage by which this initial segment has been seen to be off [T_{i}]. On the other hand, if A ↾ m_{2[i,j]+1}^{∗}^{⌢}1 is non-extendible on T_{i}, then we will eventually discover this fact at some stage s_{1} > s_{0}. Let s > s_{1} be the stage at which the least marker ever moved after stage s_{1} is moved. At stage s all restraints imposed when non-final positions of markers are enumerated in A are reset to 0. Thus R(i, s) < s_{0} by our choice of s_{0}. Now as m_{2[i,j]+1,s} > s_{0} > R(i, s), we put m_{2[i,j]+1,s} = m_{2[i,j]+1}^{∗} into A forcing A off T_{i} as described above. □

Claim 4. For each i, if A is on T_{i} then [T_{i}] is not thin.

Proof of Claim 4: Fix i and suppose that A ∈ [T_{i}]. We will define a subtree T′_{i} of T_{i} such that A ∈ [T′_{i}] but there are infinitely many numbers m such that A ↾ m^{⌢}0 ≺ A (and so is extendible on T_{i} and T′_{i}) while A ↾ m^{⌢}1 is extendible on T_{i} but not on T′_{i}. For each such m, we will thus have a distinct element of [T_{i}]\[T′_{i}], which shows that [T − i] \ [T′_{i}] is infinite. On the other hand, since A is maximal and therefore non-recursive, the fact that A ∈ [T′_{i}] will imply that [T′_{i}] is infinite. This, of course, will show that T_{i} is not thin. By Claim 3, there is a j_{0} such that for all j ≥ j_{0}, m_{2[i,j]+1}^{∗} ∉ A and A ↾ m_{2[i,j]+1}^{∗}^{⌢}1 is extendible in T_{i}. Let s_{0} be such that all markers m_{e} for e ≤ 2[i, j_{0}] + 1 have reached their final positions. Define T′_{i} to be the subtree of T_{i} gotten by making every string of the form A_{s} ↾ m_{2[i,j]+1,s}^{⌢}1 with j > j_{0} and s > s_{0} terminal in T′_{i}. Thus there are infinitely many m (all the m_{2[i,j]+1}^{∗} for j > j_{0}) such that A ↾ m^{⌢}1 is extendible in T_{i} but not in T′_{i}. All that remains is to show that A ∈ [T′_{i}]. This could fail only if there is some j > j_{0} and s > s_{0} such that A_{s} ↾ m_{2[i,j]+1,s}^{⌢}1 is an initial segment of A. Now m_{2[i,j]+1,s} cannot equal m_{2[i,j]+1}^{∗} since by our choice of j_{0}, m_{2[i,j]+1}^{∗} ∉ A. Thus there is a t > s at which we move m_{2[i,j]+1,s}. As we can move m_{2[i,j]+1,s} only if we also move m_{2[i,j],s}, m_{2[i,j],s} must enter A and so A_{s} ↾ m_{2[i,j]+1,s}^{⌢}1 is not an initial segment of A as required. This completes the proof of Theorem 3.4. □

4. Recursive Boolean algebras and Martin–Pour-El Theories. The Stone Representation Theorem implies that every Boolean algebra is iso-

morphic to the Boolean algebra of clopen sets of a topological space (indeed of a Boolean space). If the Boolean algebra is countable, the proof shows that it is isomorphic to the Boolean algebra RC(P) of relatively clopen sets of a closed class P contained in 2^{ω}, and of course RC(P) is countable for every closed class P contained in 2^{ω}. In this section we point out effectivized versions of this correspondence and use them to transfer some of our results on Π_{1}^{0} classes to results on Boolean algebras which can be obtained as the quotient of a recursive Boolean algebra by an r. e. equivalence relation. In particular, Theorem 4.8 is an effective version of the Stone Representation Theorem. We determine the meaning of thinness and of the Cantor-Bendixson derivative in the setting of Boolean algebras. We also look at the connection between recursive Boolean algebras and theories of propositional calculus, in particular with Martin–Pour-El theories. Finally, we interpret the results of the previous sections on Π_{1}^{0} classes for recursive Boolean algebras and for theories of propositional calculus.

Some of the results are known as part of the folklore of the subject. For more on recursive Boolean algebras, see Remmel [27].

We first consider as our underlying recursive Boolean algebra a recursive countable atomless Boolean algebra. The Boolean algebra Q of propositions discussed in the introduction is such a Boolean algebra. Now it follows from a theorem of LaRoche [17] and Goncharov [13] that any two recursive atomless Boolean algebras are recursively isomorphic. Thus in order to relate more directly to our results on Π_{1}^{0} classes, we will use the countable atomless Boolean algebra of clopen subclasses of 2^{ω}.

For any closed class P ⊂ 2^{ω}, let RC(P) be the Boolean algebra of relatively clopen subclasses of P with the standard set operations. The standard countable atomless Boolean algebra is RC(2^{ω}), which has no atoms. Now for any nonempty subclass P of 2^{ω}, let

F(P) = {U ∈ RC(2^{ω}) : P ⊂ U}.

It is easy to see that F(P) is a filter in RC(2^{ω}).

Define the filter generated by an element x of P to be F(x) = {K ∈ RC(P) : x ∈ K}.

Theorem 4.1. For any closed class P ⊂ 2^{ω}:

(a) A relatively clopen subset K of P is an atom of RC(P) if and only if K = {x} for some x ∈ P.

(b) For any x ∈ P, {x} ∈ RC(P) if and only if x is isolated in P.

(c) A subset F of RC(P) is an ultrafilter of RC(P) if and only if F = F(x) for some x ∈ P.

(d) RC(P) is isomorphic to the quotient RC(2^{ω})/F(P).

Proof. (a) Suppose that the relatively clopen subclass K of P is an atom of RC(P). We claim that K has exactly one element. By the definition of an atom, K ≠ 0^{RC(P)}, that is, K cannot be empty. Now suppose by way of contradiction that K has two distinct elements x and y. Choose an interval U such that x ∈ U but y ∉ U. Then U(x)∩K is a proper subset of K, which shows that K is not an atom.

(b) This follows immediately from the observation in Section 1 that an element of a closed class P is isolated if and only if there is an interval U such that U ∩P = {x}.

(c) It is clear that for any clopen set U, either U∩P ∈ F(x) or (2^{ω}\U)∩P ∈ F(x), so that F(x) is an ultrafilter.

On the other hand, suppose that F is an ultrafilter in RC(P). Then F is a family of closed subsets of P with the finite intersection property, that is, for any K_{1}, …, K_{n} ∈ F, K_{1} ∩ ⋯ ∩ K_{n} ≠ ∅. It follows that ⋂ F ≠ ∅. Now choose x ∈ ⋂ F. We claim that F = F(x). The choice of x implies that x ∈ U for all U ∈ F, so that F ⊂ F(x). But F is an ultrafilter, that is, it is not included in any larger filter. Thus F = F(x).

(d) For any U ∈ RC(2^{ω}), let [U] be the equivalence class in the quotient algebra. Recall that the equivalence relation modulo F(P) is defined so that [U] = [V] means that U and V agree on a set in F(P), which is the same thing as U ∩ P = V ∩ P. Now let

Φ_{P} (U ∩ P) = [U].

It is clear that Φ_{P} is a Boolean isomorphism from RC(P) onto RC(2^{ω})/F(P). □

Now we want to consider a recursive representation of the Boolean algebras RC(P). We begin with the underlying algebra RC(2^{ω}). For any finite sequence of strings σ_{0}, …, σ_{m−1}, the number s = [σ_{0}, …, σ_{m−1}] will represent the clopen set U(s) = I(σ_{0}) ∪ ⋯ ∪ I(σ_{m−1}). Let B(2^{ω}) be the set of all such codes for finite sequences of strings. This is a recursive subset of ω, that is, just the set of numbers which begin with a “2” in the base three representation. For any ρ ∈ 2^{<ω} and any s ∈ B(2^{ω}), we have

I(ρ) ⊂ U(s) ⟺ (∀τ)[(lh(τ) ≤ k & ρ ≺ τ) → (∃i < m)(σ_{i} ≺ τ)], where k is the maximum of {lh(σ_{i}) : i < m}. Then if t = [τ_{0}, …, τ_{n−1}] is another element of B(2^{ω}), we have

U(s) ⊂ U(t) ⟺ (∀i < m)[I(σ_{i}) ⊂ U(t)].

Then of course we have

U(s) = U(t) ⟺ (U(s) ⊂ U(t) & U(t) ⊂ U(s).

The latter defines an equivalence relation on B(2^{ω}), written s ≡ t.

We see by inspection that each of these relations is recursive. Now let us consider the Boolean operations on the clopen sets. For two elements s = [σ_{0}, …, σ_{m−1}] and t = [τ_{0}, …, τ_{n−1}] of B(2^{ω}) as described above, we can define

¬s = [ρ_{0}, …, ρ_{p−1}], where {ρ_{0}, …, ρ_{p−1}} lists in lexicographic order the strings of length k which are incompatible with each of the σ_{i}.

We can define

s ∨ t = [σ_{0}, …, σ_{m−1}, τ_{0}, …, τ_{n−1}].

Finally, we can define s ∧ t = ¬(¬(s) ∨ ¬(t)).

Then each of these operations is recursive on B(2^{ω}) and it is easy to check that U(¬(s)) = 2^{ω} \ U(s), U(s ∨ t) = U(s) ∪ U(t) and U(s ∧ t) = U(s) ∩ U(t). This gives us a recursive representation of the Boolean algebra RC(2^{ω}). Note

that B(2^{ω}) is not itself a Boolean algebra. Rather the quotient of B(2^{ω}) modulo the equivalence relation ≡ is a Boolean algebra which is clearly isomorphic to RC(2^{ω}) and will turn out to be recursive by the next Lemma.

Let us define a recursive quotient Boolean algebra to be the quotient B/ ≡^{B}, where B = (B, ≡^{B}, ¬^{B}, ∧^{B}, ∨^{B}) is a recursive structure such that B ⊂ ω, such that ≡^{B} is an equivalence relation on B, such that the unary operation ¬^{B} and the two binary operations ∨^{B} and ∧^{B} preserve the equivalence classes, and such that the set of equivalence classes forms a Boolean algebra.

Lemma 4.2. Any recursive quotient Boolean algebra B is isomorphic to a recursive Boolean algebra A.

Proof. Define the universe A of A by A = {b ∈ B : (∀a < b)¬(a ≡^{B} b)}. For any b ∈ B, let ψ(b) be the least a such that a ≡^{B} b. Then define the

operations on A by ¬^{A}(a) = ψ(¬^{B}(a)), a ∨^{A} b = ψ(a ∨^{B} b), and a ∧^{A} b = ψ(a ∧^{B} b). It is clear that the set A together with these operations forms a Boolean algebra

which is isomorphic to the Boolean algebra on the equivalence classes of B and that the set A and each of the Boolean operations is recursive. The ordering relation on A is also recursive, since it is given by a ≤^{A} b ⟺ a ∨^{A} b = b. □

It follows that the Boolean algebra RC(2^{ω}) is isomorphic to a recursive Boolean algebra. Now we want to consider the Boolean algebra of relatively clopen subclasses of an arbitrary Π_{1}^{0} subclass of 2^{ω}. Thus we need to examine Boolean algebras which are defined by recursively enumerable equivalence relations. With the previous lemma in mind, we define an r. e. quotient Boolean algebra to be the quotient B/ ≡ of B, where B/ ≡^{B} is a recursive quotient Boolean algebra, ≡ is an r. e. equivalence relation such that ≡^{B}⊂≡ and the unary operation ¬^{B} and the two binary operations ∨^{B} and ∧^{B} preserve the equivalence classes under ≡, and such that the set of equivalence classes forms a Boolean algebra. This notion is due to Feiner [11] , who refers to r. e. quotient Boolean algebras as r. e. Boolean algebras.

Now the equivalence relation ≡^{B} naturally determines an r. e. filter F^{B} = {b : b ≡ 1^{B}} which includes {b : b ≡^{B} 1^{B}}. On the other hand, any r. e. filter F which includes {b : b ≡^{B} 1^{B}} also determines an r. e. equivalence relation ≡_{F}, where

a ≡_{F} b ⟺ ((a ∧^{B} ¬^{B}b) ∨ (¬^{B}a ∧^{B} b)) ∈ F.

Thus for any r. e. filter F on B, we can define B/F to be the quotient B/ ≡_{F}. We will just observe that an r. e. quotient Boolean algebra can be realized as a

co-r. e. set A with operations which have relatively r. e. graphs in A. Given a Π_{1}^{0} class P, define the equivalence relation ≡_{P} on B(2^{ω}) by s = [σ_{0}, …, σ_{m−1}] ≡_{P} t = [τ_{0}, …, τ_{n−1}] ⟺ P ∩ U(s) = P ∩ U(t). For any

s ∈ 2^{ω}, let [s]^{P} be the equivalence class of s under ≡_{P} and let Φ_{P} (s) = U(s) ∩ P. Let B(P) be the quotient algebra of B(2^{ω}) modulo the equivalence relation ≡_{P}.

Theorem 4.3. Let T be a recursive tree and let the Π_{1}^{0} class P = [T]. Then the quotient algebra B(P) is isomorphic to the Boolean algebra RC(P) of relatively clopen subsets of P, the equivalence relation ≡_{P} is recursively enumerable and B(2^{ω})/ ≡_{P} is a recursively enumerable quotient Boolean algebra. Furthermore, if T has no dead ends, then ≡_{P} is recursive and B(2^{ω})/ ≡_{P} is a recursive quotient Boolean algebra.

Proof. Following the definition of s ≡ t above, we begin with the relation I(ρ)∩P ⊂ U(s) ∩ P, as follows.

(I(ρ) ∩ P) ⊂ (U(s) ∩ P) ⟺ (∃k)(∀τ)[(lh(τ) = k & ρ ≺ τ & τ ∈ T) → (∃i < m)(σ_{i} ≺ τ)].

This relation is r. e. and therefore the following relation is also r. e. :

(U(s) ∩ P) ⊂ (U(t) ∩ P) ⟺ (∀i < m)[(I(σ_{i}) ∩ P) ⊂ (U(t) ∩ P)].

Finally, ≡_{P} is r. e. , since

s ≡_{P} t ⟺ [U(s) ∩ P) ⊂ U(t) ∩ P & U(s) ∩ P ⊂ U(t) ∩ P].

If T has no dead ends, then we can take k to be the maximum of {lh(σ_{i}) : i < m}, as in the definition of ≡, so that each relation is again recursive.

It is clear that an isomorphism Φ_{P} between B(2^{ω}) and RC(P) is given by Φ_{P} ([s]^{P}) = U(s) ∩ P. □

We next consider the implications for B(P) if P is thin. Some definitions are needed.

Let B/ ≡^{B} be a recursive quotient Boolean algebra and let F and G be r. e. filters such that B/F and B/G are both r. e. quotient Boolean algebras. We say that B/G is an r. e. quotient of B/F if F ⊂ G. Define the r. e. filter

F ∨ G = {c ∈ B : (∃a ∈ F)(∃b ∈ G)[a ∧^{B} b ≤^{B} c]}.

It is easy to see that F ∨ G is the smallest filter which includes both F and G. Then an r. e. quotient of the r. e. quotient Boolean algebra B/F is just an r. e. quotient Boolean algebra B/(F ∨ G) for some G. Let us then say that F is a thin r. e. filter and that B/F is a thin r. e. quotient Boolean algebra if any r. e. quotient of B/F is isomorphic to B/(F ∨ G) for some principal filter G =< b >.

Now for a Π_{1}^{0} class P, there is a filter F (P) on B(2^{ω}) defined by s ∈ F (P) ⟺ s ≡_{P} ∅, or equivalently s ∈ F (P) ⟺ P ⊂ U(s). Thus F (P) is always r. e., and is recursive if T has no dead ends. On the other hand, let F be any r. e. filter on B(2^{ω}) and define the Π_{1}^{0} class P (F) by

P (F) = {x ∈ 2^{ω} : (∀s ∈ B(2^{ω}))(s ∈ F → x ∈ U(s)).

This gives a one-to-one correspondence between the r. e. filters on B(2^{ω}) and the Π_{1}^{0} subclasses of 2^{ω}, as demonstrated by the following.

Lemma 4.4. (a) For any closed set P, P(F(P)) = P.

(b) For any filter F, F(P(F)) = F.

Proof. (a) Suppose first that x ∈ P and let s ∈ F (P). Then P ⊂ U(s) and therefore x ∈ U(s). It follows that x ∈ P (F (P)).

Suppose next that x ∈ P (F (P)). Since P is a closed set, it will follows that x ∈ P if we can show that for any clopen set U(s) which includes P, x ∈ U(s). Suppose therefore that P ⊂ U(s). Then s ∈ F (P). But the definition of P (F (P)) now implies that x ∈ U(s), as desired.

(b) Suppose first that b ∈ F. We claim that P (F) ⊂ U(b). To see the claim, let x ∈ P (F). Then, letting s = b in the definition of P(F), we see that b ∈ F implies x ∈ U(b), as desired. It now follows that b ∈ F (P (F)).

Suppose next that b ∈ F (P (F)). Then P (F) ⊂ U(b). But P (F) is the intersection of the family {U(s) : s ∈ F } of clopen sets. It follows by compactness that there is a finite set {s_{1}, …, s_{n}} of elements of F such that U(s_{1}) ∩ ⋯ ∩ U(s_{n}) ⊂ U(b). Now let s = s_{1} ∧ ⋯ ∧ s_{n}. Then s ∈ F and U(s) ⊂ U(b), so that s ≤^{B} b and therefore b ∈ F.

It is clear that if P and Q are Π_{1}^{0} classes and Q ⊂ P, then F (P) ⊂ F (Q) and that if F and G are r. e. filters and F ⊂ G, then P (G) ⊂ P (F).

Lemma 4.5. (a) For any closed sets P and Q, F (P ∩ Q) = F (P) ∨ F (Q). (b) For any filters F and G, P (F ∨ G) = P (F) ∩ P (G).

Proof. (a) Suppose first that s ∈ F (P ∩Q). Then P ∩Q ⊂ U(s). Thus the closed set P is a subset of the open set U(s)∪(2^{ω}\Q). It follows that P ⊂ U(t) ⊂ U(s)∪(2^{ω}\Q) for some t. Then Q ⊂ U(s) ∪ U(¬^{B}t) = U(s ∨^{B} ¬^{B}t), so that we have t ∈ F (P) and s ∨^{B} t ∈ F (Q). But t ∧ (s ∨^{B} ¬^{B}t) = s ∧^{B} t ≤^{B} s, so that s ∈ F (P) ∨ F (Q), as desired.

Suppose next that s ∈ F (P) ∨ F (Q). Then there are t ∈ F (P) and u ∈ F (Q) such that t∧^{B} u ≤^{B} s. Now P ⊂ U(t) and Q ⊂ U(u), so that P ∩Q ⊂ U(t)∩U(u) = U(t ∧^{B} u). But U(t ∧^{B} u) ⊂ U(s) and it follows that s ∈ F (P ∩ Q).

(b) Let P = P (F) and let Q = P (G). It follows from (a) that F (P ∩ Q) = F (P)∨F (Q) = F ∨G. But this implies by Lemma 4.4 that P (F ∨G) = P (F)∩P (G). □

Theorem 4.6. The Π_{1}^{0} class P is thin if and only if B(P) is a thin r. e. quotient Boolean algebra.

Proof. Let B = B(2^{ω}). Note that for any b, P (< b >) = U(b) and F (U(b)) =< b >. Let P be a Π_{1}^{0} class. For the first direction, let P be a thin Π_{1}^{0} class and suppose that B/G is an r. e. quotient of B(P). Then the Π_{1}^{0} class Q = P (G) is a subset of P, since F = F (P) ⊂ G = F (Q). Now, since P is thin, there is a clopen set U(b) such that Q = P ∩ U(b). It now follows from Lemma 4.5 that G = F (Q) = F (P) ∨ F (U(b)) = F ∨ < b >. This shows that B(P) is a thin r. e. quotient Boolean algebra and completes one direction of the theorem.

For the second direction, suppose that B(P) is a thin r. e. quotient Boolean algebra and let Q be a Π_{1}^{0} subclass of P. Then F = F (P) ⊂ F (Q) = G. Since B(P) = B/F is thin, this means that G = F ∨ < b > for some b ∈ B. It now follows from Lemma 4.5 that Q = P (G) = P (F) ∩ P (< b >) = P ∩ U(b). This shows that P is a thin Π_{1}^{0} class as desired. □

Next we consider the Cantor-Bendixson derivative and the corresponding derivative for Boolean algebras.

For any Boolean algebra B, an element a of B is said to be an atom if a ≠ 0^{B} but for any b <^{B} a, b = 0^{B}. Then the ideal generated by the atoms is I_{A} = {a_{1} ∨ ⋯ ∨ a_{n} : a_{1}, …, a_{n} are atoms} and the filter F_{A} = {¬b : b ∈ I_{A}}. The derivative B′ of the Boolean algebra B is defined to be the quotient B/F_{A}. It is then possible to define the iterated derivative B^{α} of the Boolean algebra by taking B^{α+1} = (B^{α})′ for all ordinals α and letting B^{λ} be the limit of the sequence B^{α} for limit ordinals α in the following manner. Note that each B^{α} can be viewed as a quotient of the original Boolean algebra B modulo a filter F (α), where the ideals I(α) form an increasing sequence under inclusion. The limit algebra B^{λ} is then defined to be the quotient of B modulo the filter F^{λ} = ⋃_{α<λ} F^{α}. Thus we can define the rank of a Boolean algebra to be the least ordinal α such that B^{α} is finite.

Theorem 4.7. For any closed set P and any countable ordinal α, B(D^{α}(P)) = B(P)^{α}.

Proof. The proof is by induction on α. For α = 0, this is trivial. The proof for successor ordinals is immediate once we give the case α = 1. Now observe that an element a ∈ B(2^{ω}) is an atom of B(P) if and only if U(a) ∩ P is a singleton. Thus the ideal generated by the atoms consists of

I_{A} = {s : U(s) ∩ P is finite}.

Thus the filter

F_{A} = {s : P \ U(s) is finite}.

Now B(P′) = B(2^{ω})/(F (P) ∨ F_{A}). But the filter F (P) is clearly a subset of F_{A}, so that F (P) ∨ F_{A} = F_{A} and we have

B(P)′ = B(2^{ω})/F_{A}.

On the other hand, B(P′) = B(2^{ω})/F (P′). But it follows from the definition of P′ that for any s, P′ ⊂ U(s) if and only if P \ U(s) is finite}. Thus F (P′) = {s : P′ ⊂ U(s)} = F_{A}. It follows that B(P′) = B(P)′.

Now let λ be a limit ordinal and let Q = D^{λ}(P) = ⋂_{α} D^{α}(P). Then F (Q) = {s : Q ⊂ U(s)} = ⋃_{α<λ}{s : D^{α}(P) ⊂ U(s)} = ⋃_{α<λ}{F (D^{α}(P)}, where the second equality follows by compactness. It follows from the definitions above that B(Q) = B(2^{ω})/F (Q) = B(P)^{λ}, as desired. □

Next we consider the reverse direction of the correspondence between Π_{1}^{0} classes and r. e. quotient Boolean algebras. For any Boolean algebra B with universe B = ω, let P (B) be the class of ultrafilters on B. It is easy to see that P (B) is a closed subclass of 2^{ω}, where an ultrafilter F is represented as by its characteristic function.

Theorem 4.8. (a) If A is an r. e. quotient Boolean algebra, then P (A) is a Π_{1}^{0} class and if B is a recursive Boolean algebra, then there is a recursive tree with no dead ends such that P (B) = [T].

(b) For any Boolean algebra B with universe B = ω, RC(P (B)) is isomorphic to B and, for any closed set P, P (B(P)) is homeomorphic to P.

(c) For any r. e. quotient Boolean algebra A, B(P (A)) is recursively isomorphic to A.

Proof. (a) Suppose that A = B/ ≡ is an r. e. quotient Boolean algebra. We can represent the class P (A) of ultrafilters on A as follows.

x ∈ P (A) ⟺

(1) (∀a)(∀b)[a ≡ b → x(a) = x(b)] and

(2) (∀a)(∀b)[x(a) = x(b) = 1 → x(a ∧^{B} b) = 1] and

(3) (∀a)(∀b)[x(a) = 1 → x(a ∨^{B} b) = 1] and

(4) (∀a)[x(a) = 1 ⟺ x(¬^{B}a) = 0].

This clearly defines a Π_{1}^{0} class. Observe that we cannot have x(0^{B}) = 1 since it would follows from (3) that x(1^{B}) = 1 and it would follow from (4) that x(1^{B}) = 0. Now if B is actually a recursive Boolean algebra, then we can omit clause (1) and define a recursive tree T with no dead ends such that P (A) = [T] is defined to be the set of finite sequences x = (x(0), …, x(n − 1)) which satisfy the following, where lh(x) = n.

(2) (∀a < n)(∀b < n)[(x(a) = x(b) = 1 & a ∧^{B} b < n) → x(a ∧^{B} b) = 1] and (3) (∀a < n)(∀b < n)[(x(a) = 1 & a ∨^{B} b < n) → x(a ∨^{B} b) = 1] and

(4) (∀a < n)[(x(a) = 1 & ¬^{B}a < n) ⟺ x(¬^{B}a) = 0].

(5)_{k} (∀a_{1} < a_{2} < ⋯ < a_{k} < n)(x(a_{1}) = ⋯ = x(a_{k}) = 1 → a_{1} ∧^{B} a_{2} ⋯ ∧^{B} a_{k} ≠ 0^{B}).

Clause (5) is needed to establish the finite intersection property for {a < n : x(a) = 1} which will ensure that any x ∈ T can be extended to an ultrafilter in P (B). This then implies that T has no dead ends.

(b) Let B be a Boolean algebra with universe B = ω. The isomorphism from B to RC(P (B)) is given by mapping the element b to {F : F is an ultrafilter of B & b ∈ F }. The homeomorphism from P onto P (B(P)) is given by mapping the real x ∈ P to Φ_{P} (F(x)).

(c) Now let A = B/ ≡ be an r. e. quotient Boolean algebra, let P = P (B). Then B(P) = B(2^{ω})/ ≡_{P}). The recursive isomorphism between B(P (A) and A is defined by a map Φ from B to B(2^{ω}) such that

(i) a ≡^{B} b ⟺ Φ(a) ≡_{P} Φ(b).

(ii) a ≤^{A} b ⟺ Φ(a) ≤ Φ(b).

Here a ≤^{A} b means that a ∧^{B} ¬^{B}b ≡^{B} 0. The map Φ is defined by

Φ(b) = s if and only if s codes the sequence σ_{0}, …, σ_{n} which lists in lexicographic order all finite strings σ of length b + 1 such that σ(b) = 1.

It follows that if s = Φ(b), then U(s) = {x : x(b) = 1}.

Now let a, b ∈ B. Suppose that a ≡^{B} b. Then, by the definition of P = P (B) above, we have x(a) = x(b) for any x ∈ P (B). It follows that U(Φ(a)) ∩ P) = U(Φ(b)) ∩ P, which in turn implies that Φ(a) ≡_{P} Φ(b). For the converse, suppose that a is not equivalent to b. Then, without loss of generality a ∧^{B} ¬^{B}b is not equivalent to 0^{B} and it follows that there is a coded ultrafilter x ∈ P such that x(a) = 1 whereas x(b) = 0. Now this means that x ∈ U(Φ(a) but x ∉ U(Φ(b)), so that Φ(a) is not equivalent to Φ(b).

Suppose that a ≤^{A} b. Then for any x ∈ P, x(a) = 1 implies that x(b) = 1. Thus U(Φ(a)) ∩ P ⊂ U(Φ(b)) ∩ P. But this is equivalent to saying that Φ(a) ≤ Φ(b) in the Boolean algebra B(P). For the converse, suppose that Φ(a) ≤ Φ(b). Then U(Φ(a)) ∩ P ⊂ U(Φ(b)) ∩ P. But this means that any ultrafilter which contains a must also contain b and this can only happen if a ≤^{A} b. □

Corollary 4.9. Every r. e. quotient Boolean algebra is recursively isomorphic to the Boolean algebra B(P) of some Π_{1}^{0} class P. □

Next we look at the connection with the propositional calculus. Let Q(ω) be the propositional calculus generated by a countable sequence A_{0}, A_{1}, … of atoms. The connection is based on the following simple observation.

Proposition 4.10. The Boolean algebra RC(2^{ω}) of clopen subsets of 2^{ω} is isomorphic to the Boolean algebra Q(ω).

Proof. The isomorphism is determined by mapping the atom A_{i} to the subset {x ∈ 2^{ω} : x(i) = 1}.

Now a filter in Q(ω) is just a theory of propositional calculus. It is then easy to see that proper filters correspond to consistent theories and ultrafilters correspond to complete theories. Of course, Q(ω) has a recursive representation which is recursively isomorphic to the recursive representation of RC(2^{ω}). Then we also see that recursive filters correspond to decidable theories and recursively enumerable filters correspond to axiomatizable theories.

The work of Martin and Pour-El [24] on axiomatizable theories with few axiomatizable extensions constructed axiomatizable theories f such that every axiomatizable extension of f is generated by a single new proposition. Let us call such a theory a Martin–Pour-El theory . Then it is clear that Martin–Pour-El theories correspond to thin r. e. filters.

The original construction of Martin and Pour-El had the filter F = F (A, B) generated by the set {A_{i} : i ∈ A} ∪ {¬A_{j} : j ∈ B}, where A and B are recursively inseparable. This implies that F has no complete decidable extensions, so that the Π_{1}^{0} class P (F) has no recursive members and is therefore perfect. Thus the work of Martin and Pour-El yields a thin perfect Π_{1}^{0} class.

Our results now provide Martin–Pour-El theories with only countably many complete extensions.

Before giving the applications of our results on thin classes to Boolean algebras and Martin–Pour-El theories, we first consider further the filter F (A, B). Degreetheoretically, we understand the degrees of such filters well. They are precisely the a.n.r. degrees of Downey, Jockusch and Shore [10]. Clearly if F (A, B) is thin, then A ∪ B is simple. In [7], it was observed that if F (A, B) is Martin–Pour-El (indeed if F (A, B) possesses a somewhat weaker condition), then A ∪ B is hypersimple. On the other hand, degree-theoretical arguments show that there exist hypersimple C such that if C is the disjoint union C_{1} ∪ C_{2}, then F (C_{1}, C_{2}) is not Martin–Pour-El. The remaining question left over from [7] and [8] was whether for any maximal set A, there exists a splitting A = A_{1} ∪ A_{2} such that F (A_{1}, A_{2}) is Martin–Pour-El. Downey has recently constructed a maximal set with no such splitting.

We can now define the rank of a theory to be the rank of the corresponding Boolean algebra.

We are now ready to give the Boolean algebra and Martin–Pour-El theory versions of the results of the previous sections. We will state only a few examples and leave the others to the reader.

Theorem 4.11. For every recursive ordinal α, (a) There is an r. e. quotient Boolean algebra of rank α.

(b) There is a Martin–Pour-El theory of rank α.

Proof. This follows immediately from Theorems 2.2 and 4.7.

Theorem 4.12. (a) There is a thin r. e. quotient Boolean algebra with exactly one non-recursive ultrafilter and that ultrafilter has degree 0′.

(b) There is a Martin–Pour-El theory with exactly one undecidable complete extension and that extension has degree 0′.

Proof. This follows from Theorem 2.9. □

Theorem 4.13. (a) If U is an ultrafilter of a thin r. e. quotient Boolean algebra, then U′ is recursive in U ⊕ 0′′.

(b) If U is an ultrafilter of a thin recursive Boolean algebra, then U′ is recursive in U ⊕ 0′.

(c) If Γ is a complete extension of a Martin–Pour-El theory, then Γ′ is recursive in Γ ⊕ 0′′.

Proof. This follows from Theorem 2.10 □

Theorem 4.14. (a) There is an r. e. degree a such that no ultrafilter of any thin r. e. quotient Boolean algebra has degree a.

(b) There is an r. e. degree a such that no complete extension of any Martin– Pour-El theory has degree a.

Proof. This follows from Theorem 2.15 □

Theorem 4.15. Let a and c be r. e. degrees such that a < c. Then there is a degree b between a and c such that

(a) There is an r. e. quotient Boolean algebra of rank one and a unique nonrecursive ultrafilter and that ultrafilter has degree b.

(b) There is a Martin–Pour-El theory with exactly one undecidable complete extension and that extension has degree b.

Proof. This follows from Theorem 2.17. □

References

1. D. Cenzer, P. Clote, R. Smith, R. Soare and S. Wainer, Members of countable Π_{1}^{0} classes, Ann. of Pure and Appl. Logic 31 (1986), 145-163.

2. D. Cenzer and R. Smith, The ranked points of a Π_{1}^{0} set, J. Symbolic Logic 54 (1989), 975-991.

3. D. Cenzer and J. Remmel, Π_{1}^{0} classes in mathematics (to appear).

4. D. Cenzer and J. Remmel, Recursively presented games and strategies, Mathematical Social Sciences (to appear).

5. P. Clote, On recursive trees with a unique infinite branch, Proc. Amer. Math. Soc. 93 (1985), 335-342.

6. J. Dekker and J. Myhill, Retraceable sets, Canad. J. Math. 10 (1958), 357-373.

7. R. Downey, Abstract dependence, recursion theory and the lattice of recursively enumerable filters, Dissertation (1982), Monash University.

8. R. Downey, Maximal theories, Ann. Pure and Appl. Logic 33 (1987), 245-282.

9. R. Downey, On Π_{1}^{0} classes and their ranked points (to appear).

10. R. Downey, C. Jockusch and M. Stob, Array nonrecursive sets and multiple permitting arguments (to appear).

11. L. Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365-374.

12. H. Friedman, S. Simpson and R. Smith, Countable algebra and set existence axioms, Ann. Pure and Appl. Logic 25 (1983), 141-181.

13. S. Goncharov, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365-373.

14. C. Jockusch, Jr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420-436.

15. C. Jockusch and R. Soare, Π_{1}^{0} classes and degrees of theories, Trans. Amer. Math. Soc. 142 (1969), 229-237.

16. C. Jockusch and R. Soare, Degrees of members of Π_{1}^{0}classes, Pacific J. Math. 40 (1972), 605-616.

17. K. Kuratowski, Topology, vol. I, Acad. Press, 1966.

18. A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1-37.

19. P. LaRoche, Contributions to recursive algebra, Dissertation, Cornell University.

20. M. Lerman, Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, 1983.

21. A. Manaster and J. Rosenstein, Effective matchmaking, Proc. London Math. Soc. 25 (1972), 615-654.

22. D. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Zeit. Math. Logik Grundlag. Math. 12 (1966), 295-310.

23. D. Martin and W. Miller, Degrees of hyperimmune sets, Zeit. Math. Logik Grundl. Math. 14 (1968), 159-166.

24. D. A. Martin and M. B. Pour-El, Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic 35 (1970), 205-209.

25. A. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), 147-171.

26. J. Remmel, Graph colorings and recursively bounded Π_{1}^{0} classes, Ann. Pure and Appl. Logic 36 (1986), 185-194.

27. J. Remmel, Recursively enumerable Boolean algebras, Ann. Math. Logic 14 (1978), 75-107.

28. H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1968.

29. R. Smith, Effective aspects of profinite groups, J. Symbolic Logic 46 (1981), 851-863.

30. R. Soare, Automorphisms of the lattice of recursively enumerable sets, Ann. Math. Logic 22 (1982), 69-107.

31. R. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.

32. C. E. M. Yates, Recursively enumerable sets and retracing functions, Z. Math. Logik Grundlagen Math. 8 (1962), 331-345.

Department of Mathematics, University of Florida, Gainesville, Florida 32611; Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand; Department of Mathematics, University of Illinois, 1409 West Green Street, Urbana, IL 61801; Department of Mathematics, Cornell University, Ithaca, NY 14853