THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES

NOAM GREENBERG, RICHARD A. SHORE, AND THEODORE A. SLAMAN

Abstract. Sacks [Sa1966a] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as O^{(ω)} or, equivalently, that of the truth set of L_{ω_{1}^{CK}}.

1. Introduction

The study of recursive ordinals and hyperarithmetic sets that began with the work of Church and Kleene [ChKl1937], Church [Chu1938] and Kleene [Kl1938] suggested many analogies between the Π_{1}^{1} and hyperarithmetic sets and the recursively enumerable and recursive ones, respectively. The analogy was not perfect, however. At the basic level, for example, the range of a hyperarithmetic function on a hyperarithmetic set is always hyperarithmetic rather than an arbitrary Π_{1}^{1} set. At a deeper level, all nonhyperarithmetic Π_{1}^{1} sets are of the same hyperarithmetic degree. Kreisel [Kre1961] studied this situation and came to the realization that while Π_{1}^{1} is analogous to r.e., the correct analog for hyperarithmetic is not recursive but finite. This insight lead first to the development with Kreisel and Sacks [KreSa1963, KreSa1965] of metarecursion theory as the study of recursion theory on the recursive ordinals (those less than ω_{1}^{CK}, the first nonrecursive ordinal) or, equivalently, on their notations in a Π_{1}^{1} path through Kleene’s O. In this setting, the metar.e. subsets of ω are the Π_{1}^{1} ones and the metafinite ones are hyperarithmetic.

Another approach to generalizing recursion theory to ordinals started with Takeuti’s [Ta1960, Ta1965] development of Gödel’s [Go1939] constructible universe L through a recursion theory on the class of all ordinals. These two approaches came together in the common generalization of recursion on admissible ordinals of Kripke [Kri1964] and Platek [Pl1965]. Here the domain of discourse is an ordinal α or the initial segment L_{α} of L up to α for admissible α, i.e. L_{α} satisfies Σ_{1}-replacement. In this vein, α-r.e. is Σ_{1} over L_{α}, α-recursive is then Δ_{1} over L_{α} while α-finite means a member of L_{α}. These notions coincide with those of metarecursion theory when α = ω_{1}^{CK}.

The research of the first and second authors was partially supported by NSF Grant DMS-0100035.

The research of the third author was partially supported by NSF Grant DMS-97-96121.

We should also note that care has to be taken in the definition of “αrecursive in”, the analog of Turing reducibility. Here too, the crucial issue is that of finiteness. It no longer suffices to require that one be able to answer single membership question about A in a computation from B to say that A is reducible to B. Instead one defines α-reducible, ≤_{α}, by requiring that all α-finite sets of such questions about A can be computed on the basis of α-finitely much information about B.

The motivation and goals for generalizing recursion theory in this way included the hopes of elucidating the underlying nature of the notions fundamental to recursion theory and the essences of the constructions that are used to prove its most important theorems. In accordance with Kreisel’s insight, a prominent role should be played by the analysis of finiteness along with recursive and recursively enumerable. Such an analysis might lead to a good axiomatic treatment or reveal approaches that would be less dependent on the specific combinatorial properties of ω exploited in these notions and constructions. In this way the study might also produce applications to both classical recursion theory and other domains (set theory, model theory, proof theory and, in hindsight, computer science) where the notions of effectiveness play many roles.

It was relatively easy to formalize the basic notions or recursion theory in these settings but also in much more general ones. Kreisel’s test of a generalization worthy of investigation was the Freidberg-Muchnik theorem solving Post’s problem by showing that there are incomparable r.e. degrees. As Sacks [Sa1990, p. ix] puts it, this brings us from the static or syntactic realm into the dynamic one. It is in this domain that priority arguments and the deeper investigations into the notion of enumerability and relative computability were developed in classical recursion theory. First metarecursion theory (Sacks [Sa1966b]) and then α-recursion theory (Sacks and Simpson [SaSi1972]) passed this test.

The route to the solution to Post’s problem in α-recursion theory was the ability to make Σ_{1}-replacement suffice for arguments that in classical recursion theory seemed to naturally rely on Σ_{2}-replacement (or induction). Further investigations in α-recursion theory indicated that many of the more complicated priority arguments of the classical subject used yet higher levels of replacement and did not generalize so readily to all admissible α. The density theorem was successfully generalized to all admissible α (Shore [Sh1976a]) but to this day the theorems epitomizing the basic construction of classical recursion theory have not been settled for all admissible ordinals. Almost always more admissibility suffices and at times other conditions as well. Early examples include the existence of an incomplete high α-r.e. degree (Shore [Sh1976b]) and minimal pairs (Lerman and Sacks [LeSa1972]) for which Σ_{2} admissibility suffice and at times something less.

Perhaps not surprisingly, the first differences between α-r.e. sets for various α arose early on in the set theoretic realm rather than in the setting of the α-degrees. Here one works in E_{α}^{∗}, the lattice of α-r.e. sets modulo the α^{∗}- finite (i.e. α-finite and of order type less than α^{∗}) ones. The first examples concerned maximal sets which do not exist in E_{ℵ_{1}}^{∗} by Sacks ([Sa1966c]) and in general exist for an arbitrary α if and only if α is projectable into ω in a specific reasonably effectively way by Lerman ([Le1974]). Many other differences were found in this setting among different α (see Lerman ([Le1978]) for a large array of examples). None of them, however, provably distinguished between ω and ω_{1}^{CK} in terms of classical theorems about E_{α}^{∗}.

The problem of provably distinguishing between different admissible α was more difficult in the setting of the α-r.e. degrees. Eventually, an elementary difference even between the r.e. degrees and the α -r.e. degrees for some α was established by finding certain admissible ordinals for which, contrary to Lachlan’s [La1975] nonsplitting theorem, one can combine splitting and density for all pairs of α-r.e. degrees (Shore [Sh1978]). (That is, for certain α it is always possible to find, for every pair a < b of α -r.e. degrees, two incomparable α-r.e. degrees b_{0} and b_{1} between a and b such that b_{0}∨b_{1} = b.) This work did indeed elucidate the role of various replacement or induction like principles in recursion theoretic arguments and much later played a role in analyzing such arguments in reverse mathematics (e.g. Slaman and Woodin [SlWo1989] and Mytilinaios [My1989]). Other aspects of generalized recursion theory found applications in complexity theory (e.g. Shinoda and Slaman [ShSl1990]). They did not however have much to say directly about the role of finiteness. Moreover, once the basic techniques are understood, all these constructions can be fairly easily carried out in metarecursion theory.

The crucial fact about ω_{1}^{CK} needed to carry out all these arguments is that there is a metarecursive projection of ω_{1}^{CK} into ω. This allows one to arrange priority requirements in an ω list and so carry out constructions in such a way that one only ever really needs to worry about there being truly finitely many predecessors of any requirement. For example, density was proved by Driscoll [Dr1968] and minimal pairs constructed by Sukonick [Su1969]. It seemed as if everything one could do in classical recursion theory could be done in metarecursion theory as well. It was in this setting that Sacks [Sa1966a] posed as his final Question whether R_{ω_{1}^{CK}}, the meta-r.e. degrees with ω_{1}^{CK}-reducibility, and R, the r.e. ones with Turing reducibility, are elementarily equivalent. This seemed possible at the time. Indeed, at that time people still thought that there should be some nice characterization of the structure R that would indicate that it was simple in some way. Shoenfield’s conjecture that it was ω-saturated and so categorical had been disproven with the construction of a minimal pair of r.e. degrees but, nonetheless, Sacks still conjectured in [Sa1966a] that the theory was decidable and that the structure was isomorphic to the degrees r.e. in and above d for every degree d.

Both of these conjectures turned out to be false (Harrington-Shelah [HaSh1982], Shore [Sh1982]). Indeed, these results and others showed that R was very complicated in various ways. Shore [Sh1982] showed that it is not recursively presentable and later Harrington and Slaman and Slaman and Woodin (see Slaman [Sl1991]) showed that its theory is recursively isomorphic to true arithmetic. These sorts of results changed the paradigm for understanding R from a hope for simplicity to an approach to its characterization by its complexity. (For more of the history and further discussion, see Shore [Sh1997] and [Sh1999]). Once one had this view of R, it became natural to believe that the answer to Sacks’ question was “no” just because it seemed that one could prove all the results of classical recursion theory in metarecursion theory. If the meta-r.e. degrees, like the r.e. ones, are as complicated as possible then R_{ω_{1}^{CK}} is more complicated than R. In this way, Odell [Od1983] established an analog of Shore [Sh1982] for the meta-r.e. degrees to show that R_{ω_{1}^{CK}} is not arithmetically presentable and so not isomorphic to R. Once Harrington and Slaman and Slaman and Woodin had proven that the theory of R is recursively isomorphic to true arithmetic, it became, as Sacks is fond of saying, “morally certain” that the two structures are not even elementarily equivalent.

Shore and Slaman, as announced in Shore [Sh1997], managed to carry out enough of the relevant constructions in metarecursion theory to prove this result. The proof was fairly elaborate and required lifting several major theorems of classical recursion theory to ω_{1}^{CK}. It also failed to give a full characterization of the degree of the theory of R_{ω_{1}^{CK}}. The expected result was that it should be recursively isomorphic to the theory of ⟨L_{ω_{1}^{CK}}, ∈⟩ or, equivalently, of degree O^{(ω)}. This result awaited further developments in classical recursion theory. Nies, Shore and Slaman [NiShSl1998] provided a definable standard model of arithmetic in R and so a more direct proof that the degree of its theory is 0^{(ω)}. This work also provided a simpler and more powerful approach to the analysis of other definability aspects of R. In the present paper, we follow the same original intuition from the 60s about the similarity of R and R_{ω_{1}^{CK}} to lift enough of Nies, Shore and Slaman [NiShSl1998] to metarecursion theory to prove that a standard model of arithmetic with a predicate for O is definable in R_{ω_{1}^{CK}} and so its theory, as expected, is recursively isomorphic to both that of L_{ω_{1}^{CK}} and to O^{(ω)}.

Once again, the crucial property of ω_{1}^{CK} is its metarecursive projectability into ω and the results on the definability of a standard model of arithmetic are carried out for all such admissible ordinals. The proofs also show that there is a standard model of arithmetic with a predicate for any Δ_{2}(L_{α}) set definable from parameters in the α-r.e. degrees if α^{∗}, the Σ_{1} (or equivalently the α-recursive) projection of α is ω. Thus no two of these structures are isomorphic and none are elementarily equivalent to R.

Our results thus answer Sacks’s original question by providing an elementary difference between R and R_{ω_{1}^{CK}}. However, they do so by continuing along the path following the intuition that one can lift all constructions of r.e. degrees to ω_{1}^{CK} by using projectability to convert requirements lists to ones of length ω and to any admissible ordinal satisfying enough replacement to handle requirements in order type α. These illusions will be dispelled in further work by the first author (Greenberg [Gr2006]) that, for the first time in the setting of the α-r.e. degrees, illuminates the role of true finiteness in various classical constructions. Ones similar to those used here will be shown to require that α have cofinality ω in some effective sense. Entirely different ones will show that there are simple theorems about lattice embeddings in the r.e. degrees that can be true of the α-r.e. ones only if α is actually countable in a strong, effective way. These constructions will be shown to rely very explicitly on considerations involving true finiteness. All of the work taken together will show that no R_{α} is elementarily equivalent to R. ^{1}

For the rest of the paper we assume a basic familiarity with α-recursion theory and refer to the standard texts of Sacks [Sa1990] or Chong [Cho1984] for background and terminology with one caveat. Purely as a notational simplification, we generally drop the initial α. Thus for the rest of this paper, recursive means α-recursive, r.e. means α-r.e., regular means α-regular, unbounded means unbounded in α, etc. However, in keeping with our eventual goal of understanding the role of true finiteness, it will remain necessary to distinguish between finite and α-finite and so finite means finite. We also assume that the reader is familiar with Nies, Shore and Slaman [NiShSl1998].

2. Coding

Suppose that α is an admissible ordinal such that α^{∗} = ω. We use the coding machinery developed in [NiShSl1998], and apply it to the (α-)r.e. degrees. We code models of arithmetic into the r.e. degrees by using SWsets. We recall that the domain of an SW set determined by parameters p̄ = (p, q, r, l) is the collection of degrees g below r which are minimal with respect to the property g∨p ≥ q, and that a partial ordering on this domain is given by

g ≤p̄ g′ ⇔ g ≤ g′ ∨ l.

Structures in the language of arithmetic are coded by partial orderings, again as described in [NiShSl1998]: The domain is the collection of minimal elements; further elements code pairs of numbers (an element c codes (a, b) if there is a 2-chain from a to c and a 3-chain from b to c). Binary functions (such as + and ×) are now coded by the pairs (add a 4-chain from a + b to (a, b) and a 5-chain from ab to (a, b)).

1Recent work yields a single, natural sentence that differentiates between R and R_{α} for any admissible α, including ω_{1}^{CK}. The first author (Greenberg [Gr2006]) has shown that for any admissible α > ω, an incomplete α-r.e. degree bounds a copy of the 1-3-1 lattice in R_{α} iff it bounds a critical triple iff it can compute a counting of α. However, in recent work, Greenberg and Downey ([DoGr], see [DoGr2006]) have shown that there is an r.e. degree which bounds a critical triple but not a copy of the 1-3-1 (this degree is totally < ω^{ω}-r.e. but not totally ω-r.e.)

In this paper, we wish to code models of arithmetic with an extra set of natural numbers, also coded by the partial ordering. To a structure coded as above, we add a 6-chain above every number in the set coded. Overall, we get a coding scheme S_{M}(p̄) to code models of arithmetic (with a subset) in the α-r.e. degrees. We will find a (nonempty) correctness condition on p̄ which will ensure that the model coded is a standard model of arithmetic, and that the set coded is Kleene’s O. For this we will use the comparison maps described in [NiShSl1998]. In fact, once we prove the following theorems, we can simply repeat the coding arguments in [NiShSl1998] without change to get a correctness condition which implies that the model coded is standard, and get a uniform scheme for the isomorphism between any two such models:

Theorem 2.1. If ⪯ is a Δ_{2}(L_{α}) partial ordering on ω, and a > 0 is any r.e degree, then there is some low SW set coding ⪯ below a (i.e. some p̄ such that ≤p̄≅⪯ with r ≤ a and low.)

Theorem 2.2. If ⪯ is a Δ_{2}(L_{α}) partial ordering on ω, H a recursive set of ⪯-minimal elements, ⟨u_{i}⟩_{i∈H} a sequence of uniformly r.e. degrees, and ⟨v_{i,j}⟩_{i∈H,j<ω} an array of uniformly r.e., uniformly low degrees such that for all i ∈ H and j < ω, u_{i} ≰ v_{i,j}, then there is a low SW set ⟨g_{i}⟩_{i<ω} coding ⪯ such that for i ∈ H and j < ω, g_{i} ≤ u_{i} and g_{i} ≰ v_{i,j}.

Now Kleene’s O is r.e. (α-finite if α > ω_{1}^{CK}), and so the partial ordering coding the standard model of arithmetic together with O is Δ_{2}(L_{α}). Hence some of the models satisfying the correctness condition of [NiShSl1998] code O. Now if ψ(Y) is any arithmetic statement, we can add it to the correctness condition to demand that the set coded satisfies ψ. There is such a ψ such that O is the least (inclusion-wise) set satisfying ψ (see [Sa1990, p. 8]). Using the comparison maps between the coded models (with sets satisfying ψ), we can isolate the models coding O by a further correctness condition (stating that the set coded is included in the set coded in every other model). This coding shows that Th(ω; +, ×, O), which is clearly (ω)-recursively isomorphic to O^{(ω)}, is 1-1 reducible to Th(R_{α}; ≤_{α}).

Theorem 2.3. Let α = ω_{1}^{CK}. The following are ω-recursively equivalent: Th(L_{α}; ∈), Th(R_{α}; ≤_{α}), and O^{(ω)}.

Proof. We clearly have T h(R_{α}; ≤_{α}) 1-1 reducible to T h(L_{α}; ∈). Now (L_{α}; ∈) can be coded by an r.e. subset of ω (use a recursive bijection between L_{α} and α, and then a 1-1 recursive map from α into ω); this set is of course Π_{1}^{1} and hence reducible to O. □

3. Preliminaries

The rest of the paper is devoted to the proofs of theorems 2.1 and 2.2. We fix a partial recursive, onto p: ω ↠ α.

All the sets we will get involved with will be regular and hyperregular. Regularity allows us to use Turing functionals which only appeal to initial segments of their oracles. We use both weak Turing functionals (which take numbers as input) and (strong) Turing functionals (which give answers for α-finitely many questions at once). By regularity of the set being computed, we always ask about initial segments of the computed set. Thus elements of the functionals are of the form (σ, τ) for σ, τ α-finite binary strings with ordinal domain (and the pair means: from oracle σ compute τ) or for weak functionals (σ, x, i) where σ is such a string, x < α and i ∈ {yes,no}.

Terminology. For a functional Ξ with intended oracle A, ξ(A; β) (for β < α) is the use of the computation (if convergent): the least γ < α such that Ξ(A ↾ γ; β) ↓. However, we often use the same notation to mean A ↾ ξ(A; β), i.e. the actual information used. This should rarely cause confusion. Similarly, we have ξ(A; β)[s] (the use of the computation at stage s).

Regularity also allows us to assume that if Ξ is a functional and Ξ(A; x) ↓ then the use ξ(A; x) > x. We note that for hyperregular sets, there is no difference between ≤_{α} and ≤_{wα}, thus there is no distinction in this case between the computing power of strong or weak functionals.

Say A is an intended oracle for Ξ; we can alter Ξ and its approximation according to an enumeration of A, such that if Ξ(A; x) ↓ [s], t > s and A did not change below the use of the computation at s, then Ξ(A; x) ↓ [t] with the same use.

The constructions all involve low sets, that is, sets A such that A′ ≤_{α} ∅′. All low r.e. sets are regular and hyperregular ([Sh1976b]). A sufficient criterion for a regular r.e. set A to be low is the existence of an effective enumeration A[s] of s such that for all weak Turing functionals Ξ and all α-finite sets K, if for every x ∈ K there are unboundedly many stage s at which Ξ(A; x) is convergent, then at some stage s^{∗}, for all x ∈ K, Ξ(A; x) ↓ via an A-correct computation.

Also, if A is low and Ξ is a functional, then we can alter our approximation to Ξ(A) (or more precisely, redefine when Ξ(A; x) ↓ [s]) such that the last property holds (without changing the value of Ξ(A)). A recursive index for this approximation (for all functionals) can be obtained uniformly from a lowness index for A.

We will also make use of the notion of a uniformly low sequence ⟨A_{i}⟩; this is a sequence of low sets such that a lowness index for A_{i} can be obtained effectively from i. If ⟨A_{i}⟩ is such a sequence, and ϕ(x, X) is a Σ_{1}(L_{α}) formula (with unary predicate), then the relation P (x, i) ⇔ ϕ(x, A_{i}) is Δ_{2}(L_{α}).

4. Construction of an SW set

We first show how to construct an SW set in the r.e. degrees. We assume familiarity with the techniques of constructing SW sets in the ω-r.e. degrees, as presented in [NiShSl1998]. We build an ω-sequence of sets G_{i}, sets P, Q and R, together with (weak) Turing functionals Γ_{n} and Δ_{n,j} for n, j < ω. We let R = ⨁_{i} G_{i} = {(i, x) : x ∈ G_{i}}. Preserving the notation of [NiShSl1998], we let ⟨Ψ_{e}⟩_{e<α} be an enumeration of all (weak) Turing functionals, and similarly let ⟨Ξ_{e}⟩_{e<α} enumerate all weak Turing functionals including ones appearing in the construction with approximations as built in the construction. We let (Θ_{i}, Φ_{i}, W_{i})_{i<α} enumerate all triples consisting of a Turing functional, a weak Turing functional, and an r.e. set.

We strive to satisfy the following requirements:

(1) T_{n}: Γ_{n}(G_{n} ⊕ P) = Q.

(2) M_{i}: If Θ_{i}(R) = W_{i} and Φ_{i}(W_{i} ⊕ P) = Q then there are j and n such that G_{j} =^{∗} Δ_{n,j}(W_{i}).

(3) D_{i,j,e}: If j ≠ i, then Ψ_{e}(G_{i}) ≠ G_{j}.

(4) K_{e,K}: If for every x ∈ K there are unboundedly many s s.t. Ξ_{e}(R ⊕ P ⊕ Q; x) ↓ [s] then at some stage s^{∗}, Ξ_{e}(R ⊕ P ⊕ Q; x) ↓ is correct for all x ∈ K. [Here K ranges over all α-finite sets.]

(A =^{∗} B means that A and B are eventually equal, i.e. for some β < α, A ↾ [β, α) = B ↾ [β, α). Regularity of G_{j} implies that the conclusion of M_{i} ensures that G_{j} ≤_{α} W_{i}.)

The biggest obvious difference between the classical construction and this one is the number of requirements. Initially, we arrange the requirements (except for the T requirements) effectively in order-type α. We then use the map p in order to re-arrange the requirements in order-type ω. Another way to visualize this is to imagine we have ω agents on the construction site. Agent n, for n ∈ dom p, works for the requirement in place p(n). We also let agent n work for T_{n}. An agent working for some requirement might discover at some stage a stronger requirement which just appeared; but this happens only finitely many times. The classical approach to showing the construction is fair will now apply: showing that with no disturbances, each requirement eventually ceases all action, will show that each requirement gets its turn to act.

The fact that α > ω and as far as we can effectively tell, is a regular cardinal, allows for some simplifications in comparison with the classical construction. We no longer require a tree of outcomes to guess the true restraint on a particular requirement (which is the liminf of the restraint over time); the fact that restraint falls back on a (recursive) club allows us to show that the restraints of finitely many requirements will fall back simultaneously. The price to pay is that the restraint has to fall back on limits of expansionary stages, which may be not expansionary themselves; thus in theory a requirement might wish to impose further restraint at such a limit stage, and dropping the restraint might damage the success of the requirement. This does not happen in our construction, as the responsibility to act often lies with the lowness requirements associated with specific tasks (which are of a simpler, finitary nature); the minimality (M) requirements only need to act at successor expansionary stages, and so dropping the restraint at limits of expansionary stages will not harm their success.

Construction

We now give the formal construction of a SW-set.

Let #(s) be the largest number used in the construction by the end of stage s. (The largest number used at a stage is recursive as a function of the stage, hence #(s) < α and is a recursive function.)

Initialisation. The way agents impose finitary-type restraint is by initialising all weaker agents. An agent n will initialize weaker agents whenever it first discovers the requirement it works for (i.e. when p(n) ↓ first); whenever it enumerates numbers into a set; and in general, whenever it declares victory. Further instances at which specific requirements initialize weaker ones will be given as part of the instructions for these requirements.

When an agent gets initialized, we cancel all of its followers and chits. We disregard all functionals created by the agent and start new ones (formally, we can build α functionals indexed by stages; at stage s, the agent n works with the functional indexed by init(n, s) = sup{r < s : n was initialized at r}.)

Agreement, Expansion and Restraint. A number y is i-confirmed at a stage s if Φ_{i}(W_{i} ⊕ P; y) ↓= Q(y)[s] with use σ ⊕ π = ϕ_{i}(y)[s] and σ ⊂ Θ_{i}(R)[s]. We let

l(i)[s] = max{z | ∀y < z, y is i-confirmed at s}.

A stage s is i-expansionary if for all t < s, l(i)[t] < l(i)[s].

At stage s, if agent n is working for M_{i}, let

r(n)[s] = \{ \begin{matrix}0 & if s is i-expansionary or a limit of i-expansionary stages, \\ #(t) & if not, and t = sup\{u < s : u is i-expansionary\}. \end{matrix}

Let Rest(n)[s] = max_{m<n} r(m)[s].

Followers. An agent n working for D_{i,j,e} may have a follower. The follower is targeted for G_{j}. A follower x is realized at stage s if Ψ_{e}(G_{i}; x) ↓= 0[s].

Chits. Say agent n works for M_{i}. n defines functionals Δ_{n,j} (for j ≤ n), with intended oracle W_{i}. n only tries to define Δ_{n,j}(x) at stage s for the least x such that Δ_{n,j}(W_{i}; x) ↑ [s]. To each computation (σ; x, l) ∈ Δ_{n,j} is associated a chit (y, π) (we sometimes also refer to y as the chit). When n wishes to define Δ_{n,0}(x), it picks a new chit; a chit (y, π) is suitable to be picked if y ∈ α^{[n]}, y < l(i, s), and ϕ_{i}(W_{i} ⊕ P; y)[s] = σ ⊕ π. If n picked such a chit, then it defines Δ_{n,0}(x) with use σ.

For j > 0, to define Δ_{n,j}(x) at s, n searches for a j − 1-eligible chit, i.e. a chit (y, π) for a computation Δ_{n,j−1}(x′) with use σ, which is still active (i.e. σ ⊕ π ⊂ W_{i} ⊕ P [s]; an inactive chit is called cancelled) and such that the computation Δ_{n,j−1}(x′) is failed, i.e. Δ_{n,j−1}(W_{i}; x′) = 0 ≠ G_{j−1}(x′). If such a chit is found and used, then n defines Δ_{n,j}(x) with use σ. When we define Δ_{n,j}(x) at s, we always let the value be G_{j}(x)[s].

One last requirement on the suitability of a chit y for a Δ_{n,j} computation is that of size: if we wish to use it at stage s, and

r = sup{t < s : n defined a Δ_{n,j}-computation at stage t} ∪ init(n, s),

then we require that y > #(r).

At a certain stage s, n may wish to use a chit (y, π) for purposes of victory. A chit (y, π) is cleared by Γ_{m} at stage s if it is not the case that Γ_{m}(G_{m} ⊕ P; y) ↓= 0[s], or if Γ_{m}(G_{m} ⊕ P; y) ↓= 0[s] with use γ_{m}(G_{m} ⊕ P; y)[s] > dom π. The chit y is victorious if it is i-confirmed at s, still active, y > Rest(n)[s], and is cleared by all Γ_{m} for all m ≤ n.

Pointers. The modus operandi of an agent n which works for K_{e,K}, is at turns to take an element x ∈ K, wait for Ξ_{e}(R ⊕ P ⊕ Q; x) to converge and then initialise weaker agents so that this computation becomes correct; it then moves to another element x ∈ K (or rests if all have been covered). The pointer i(n)[s] is the element under consideration. Whenever n is initialised, we define i(n)[s] = min K. On a segment of stages during which n is never initialised, i(n)[s] is non-decreasing, so at limit stages s we let

i(n)[s] = min K \ lim t < si(n)[t]

[unless of course unboundedly often before s, n has been initialised, at which case we consider n initialised at s.]

However, if K ⊆ lim_{t<s} i(n)[t] then all elements of K have been covered and n is declared satisfied and never acts again (unless it is later initialised.)

The Construction. Stage s of the construction has two phases. First, we check all agents in sub-stages. At the sub-stage devoted to agent n, if n declared victory since init(n, s) or does not work for any requirement (other than T_{n}), we skip it, and go to the next sub-stage. Otherwise, we describe n’s actions based on the type of requirement for which it works:

M_{i}: If there is some σ ⊂ Θ_{i}^{R}[s] and some x < dom σ s.t. σ(x) = 0∧x ∈ W_{i}[s],

declare victory (this is called “easy victory”).

If r(n)[s] > 0, skip this sub-stage. If we didn’t skip or win yet, look for victorious chits. If there is one, enumerate the least one y into Q, and for all m ≤ n, if Γ_{m}(G_{m} ⊕P; y) ↓= 0[s], put γ_{m}(G_{n} ⊕P; y)[s]−1 into P. Declare victory.

If we haven’t won yet, and the stage is i-expansionary, then try to extend Δ_{n,j}(W_{i}) as described above. Suppose n just defined Δ_{n,j}(x). Suppose that agent m > n works for some D requirement at s, and that x is a follower for m, targeted for G_{j}. Then m now initializes all weaker nodes.

K_{e,x}: If n is not currently satisfied, and if Ξ_{e}(R⊕P ⊕Q; i(n)) ↓ [s], then initialise all weaker agents, and redefine i(n)[s+1] = min K\i(n)[s]+1, i.e., the next element of K. [However, if i(n)[s] = max K then n is now declared satisfied.] D_{i,j,e}: If the agent n doesn’t have a follower, pick one in α^{[n]}, larger than #(s). If the follower x is realized, n enumerates it into G_{j} and declares victory.

If the next agent was initialized in this stage, we halt the first phase. Otherwise, we move on to the next sub-stage.

At the second phase, we tend to the requirements T_{n}; for every n < ω, we find the least x such that Γ_{n}(G_{n}⊕P; x) ↑ [s], and set Γ_{n}(G_{n}⊕P; x) ↓= Q(x)[s] with large use (γ_{n}(G_{n} ⊕ P; x) > #(s), and not a limit ordinal).

Verifications

We sketch the verifications, noting all the instances that are different from the classical case.

Fairness and finitary success. Suppose that n is an agent that eventually stops being initialized, i.e. r^{∗} = init(n, α) < α.

Lemma 4.1. Suppose n works for M_{i}. Suppose s > r^{∗}, Δ_{n,j}(W_{i}; x) ↓ [s] with use σ, and at t > s, σ ⊂ Θ_{i}(R)[t]. Then n does not redefine Δ_{n,j}(x) at t.

Proof. n only redefines Δ_{n,j}(x) if σ ⊄ W_{i}[t]. But then, it would declare “easy victory” and not define anything. □

Lemma 4.2. n eventually stops initialising weaker agents.

Proof. If n works for an M requirement, then n initializes at most once after r^{∗}, (when declaring victory). Suppose that n works for K_{e,K}. The collection K′ of x ∈ K such that at some s ≥ r^{∗} we have x = i(n)[s] is an initial segment of K and hence is α-finite. The function taking x ∈ K′ to the least s ≥ r^{∗} such that x = i(n)[s] is recursive and so has bounded range, say bounded by some s^{∗}. After stage s^{∗}, n initialises weaker agents at most once.

If n works for D_{i,j,e}, then it either declares victory after r^{∗} and ceases all action after that; or it has a permanent follower x. n may then initialize at s > r^{∗} for the sake of a stronger agent m < n working for some M_{k}, when Δ_{m,j}(x) gets defined, say with use σ and chit (y, π). For each such m, this may happen at most once after r^{∗}, since σ ⊂ Θ_{k}(R) will be preserved; note that y < l(k)[s] since s is k-expansionary, and y < l(k) when it is first picked. □

We can now verify that the requirements D succeed, just as in the classical case. Also, each K_{e,K} succeeds: if it is not declared satisfied after some stage s^{∗} < α, then x = i(n)[s] is eventually constant and it is not the case that Ξ_{e}(R ⊕ P ⊕ Q; x) converges at unboundedly many stages. As noted, we get that R ⊕ P ⊕ Q is low, hence regular and hyperregular.

The success of T_{n} is also verified as in the classical case. The only difference is in showing that dom Γ_{n}(G_{n} ⊕ P) = α. As for ω, we know that for every x < α, if Γ_{n}(G_{n} ⊕ P) ↾ x has stabilized by some stage s, then so would Γ_{n}(G_{n} ⊕ P; x) (this follows from the fact that attempts at defining Γ_{n} at x would be made each time it isn’t defined, and from the success of the corresponding K-requirement). What we need to show is that for limit x, if for all y < x, Γ_{n}(G_{n} ⊕ P; y) eventually stabilizes, then so does Γ_{n}(G_{n} ⊕ P) ↾ x. The reason for this is the hyperregularity of G_{n} ⊕ P; for each y < x, the least stage s at which Γ_{n}(G_{n} ⊕ P; y)[s] = Γ_{n}(G_{n} ⊕ P; y) is computable from the oracle (simply find when the computation is correct), hence the collection of such stages is bounded.

Δ Δ Δ_{n,j}. The following will be useful here and in later proofs. Suppose that n works for M_{i} and that j ≤ n.

Lemma 4.3. Δ_{n,j}(W_{i}) is use-monotone: dom Δ_{n,j}(W_{i}) is an ordinal and for x_{0} < x_{1} < dom Δ_{n,j}(W_{i}), δ_{n,j}(W_{i}; x_{0}) < δ_{n,j}(W_{i}; x_{1}).

Proof. We show, by induction on s ≤ α, that dom Δ_{n,j}(W_{i})[s] is an ordinal, and that if x_{0} < x_{1} < dom Δ_{n,j}(W_{i})[s], then the computation Δ_{n,j}(W_{i}; x_{0})[s] has shorter use than the computation Δ_{n,j}(W_{i}; x_{1})[s].

Suppose that s is a limit, x_{0} < x_{1}, and that Δ_{n,j}(W_{i}; x_{1}) ↓ [s]. For some t < s, Δ_{n,j}(W_{i}; x_{1}) ↓ [t] is the same computation (which remains up till s). By induction, Δ_{n,j}(W_{i}; x_{0}) ↓ [t] with shorter use, and so this computation still holds at s.

Assume the lemma at the beginning of s. At the beginning of s, a new number is enumerated into W_{i}; it destroys some Δ_{n,j}(W_{i}) computations, but an initial segment remains. A new computation may be now defined for x_{1} = the new domain, say with chit (y, π) and use σ ⊂ W_{i}[s]. By suitability of the chit, y > δ_{n,j}(W_{i}; x_{0})[s] for all x_{0} < x_{1}, and dom σ = ϕ_{i}(y) > y. □

It follows that if β < dom Δ_{n,j}(W_{i}), then Δ_{n,j}(W_{i}) ↾ β eventually stabilizes. This is actually true also when β = dom Δ_{n,j}(W_{i}) < α, from hyperregularity of W_{i} in the case the hypotheses of M_{i} hold. (If they do not, then the length of agreement is bounded and so the i-expansionary stages will be bounded, so eventually M_{i} ceases all action. We do not use this fact and so omit the proof.)

Lemma 4.4. For all x, there is a stage after which n stops defining Δ_{n,j}(W_{i}; x).

Proof. Use the K requirement protecting the functional which converges with use ρ ⊂ R at stage s if at that stage Δ_{n,j}(W_{i}; x) ↓ with use σ and σ ⊂ Θ_{i}(R) with use ρ. If there are unboundedly many attempts by n to define Δ_{n,j}(x), then this functional converges unboundedly often (we noted before that whenever Δ_{n,j}(x) gets defined with chit y, y is i-confirmed) and so will get protected, and so for some s and σ, Δ_{n,j}(x) is defined with use σ, and σ ⊂ Θ_{i}(R) at the end. By lemma 4.1, Δ_{n,j}(x) doesn’t get redefined after s. □

M M M_{i}. Suppose agent n works for M_{i}. Let r^{∗} = init(n, α). If n declares victory after r^{∗} then the hypotheses of M_{i} are false (so it succeeds). The proof is identical to the classical one. From now on, we assume that the hypotheses of M_{i} are true.

Lemma 4.5. lim_{s} l(i)[s] = α.

Proof. This is because W_{i} ⊕ P ⊕ R is hyperregular. The least stage at which a number x is i-confirmed with correct uses for Θ_{i}(R) and Φ_{i}(W_{i} ⊕ P) is computable (as a function of x) from W_{i} ⊕ P ⊕ R; hence bounded on initial segments of α. □

It follows that there are unboundedly many i-expansionary stages.

Lemma 4.6. Rest(n)[s] is bounded on a recursive club.

Proof. Take any m < n which works for some M_{k}. r(m)[s] is constant on a recursive club: if there are unboundedly many k-expansionary stages, then the set of stages at which r(m) = 0 is a (recursive) club. If not, then r(m)[s] is eventually constant. A finite intersection of recursive clubs is a recursive club. □

Lemma 4.7. dom Δ_{n,0}(W_{i}) = α.

Proof. By induction on x, we show that Δ_{n,0}(W_{i}; x) ↓. If x ≤ dom Δ_{n,0}(W_{i}), then by hyperregularity of W_{i}, we know that Δ_{n,0}(W_{i}) ↾ x eventually stabilizes. It is enough now to show that for unboundedly many s, Δ_{n,j}(W_{i}; x) ↓ [s]; by lemma 4.4, after some t, n stops defining Δ_{n,0}(x), hence all computations Δ_{n,0}(W_{i}; x)[s] for s > t must be the same computation, which is permanent.

Suppose by s^{∗} > r^{∗}, Δ_{n,0}(W_{i}) ↾ x is permanent. Suppose t > r^{∗} and Δ_{n,0}(W_{i})(x) ↑ [t]. Find some i-expansionary stage s > t such that l(i)[s] is large enough so that there is some y ∈ α^{[n]} such that #(t) < y < l(i)[s]. Now if n didn’t define Δ_{n,0}(x) between t and s, then y is a suitable chit (because n did not define any Δ_{n,0} computations between t and s), thus would define Δ_{n,0}(x) at s. □

Lemma 4.8. Say j ∈ [1, n]. If there are unboundedly many chits which are eventually j − 1-eligible (and never cancelled), then dom Δ_{n,j}(W_{i}) = α.

Proof. This is like the last lemma; we find an expansionary stage t > s such that at t, there is a chit y which is eventually j − 1 eligible and is never cancelled, such that #(t) < y < l(i)[s]; this is possible by the assumption that there are unboundedly many such y. □

Now just as in the classical case (with the same proof), if at s, y is an active chit for a failed Δ_{n,n} computation, then it is cleared by all Γ_{m} for m ≤ n; we only need to notice that by the suitability of the chits, if y is a chit for Δ_{n,j}(x) then x ≤ y.

Lemma 4.9. If there were unboundedly many chits which are eventually n-eligible (and never cancelled), then n would declare victory after r^{∗}.

Proof. On a recursive club C, Rest(n)[s] is constant (call the value Rest(n)), and r(n)[s] = 0. If y > Rest(n) is a permanently n-eligible chit, and at some s ∈ C it is i-confirmed and already assigned to a computation which is already failed, then at s, y is victorious and n gets to enumerate it into Q and win. If there were unboundedly many permanent, failed chits, then such y and s would be discovered, since C is unbounded, and we can wait until y’s computation is failed and y is i-confirmed. □

The following concludes the verifications.

Lemma 4.10. Suppose that j ≤ n and dom Δ_{n,j}(W_{i}) = α but Δ_{n,j}(W_{i}) ≠^{∗} G_{j}. Then there are unboundedly many j-eligible chits which are never cancelled.

Proof. Much of the proof goes along classical lines. Given β < α, let the functional Ξ converge at t > r^{∗} with use ρ ⊕ π ⊂ R ⊕ P [t] if there is some σ ⊂ W_{i}[t] such that σ ⊂ Θ_{i}(R)[t] and there is some y > β such that at t, (y, π) is an active chit for a failed Δ_{n,j} computation. If Ξ converges unboundedly often, the success of the relevant K-requirement would show that there is some j-eligible chit which is never cancelled and is greater than β (since protection of ρ ⊕ π ⊂ R ⊕ P would ensure that σ ⊂ W_{i}).

Suppose that t^{∗} > r^{∗} is any stage. As in the classical proof, we take some x > β, t^{∗} whose final Δ_{n,j} computation is failed; suppose that that computation was defined at stage s > t^{∗} with associated chit (y, π). Let t > s be the stage at which this computation failed (i.e. some agent m > n enumerated x into G_{j} at t), and let u be the least stage greater than t at which r(n) = 0. Classical arguments show that until u, π ⊂ P is preserved (so the chit is still active): m initialized at s and wasn’t initialized until after t, so π ⊂ P is protected between s and t; no numbers went into P at t (since m acted at t); and n imposed restraint between t and u. We now notice that by the nature of our definition of u, u must be i-expansionary, and thus y is i-confirmed at u, and so Ξ converges at u. □

5. Ordering

We can code any Δ_{2}(L_{α}) partial ordering ⪯ on ω by a SW-set, exactly as is done classically, by adding a coding set L, so that n ⪯ m iff G_{n} ≤_{α} G_{m}⊕L. When enumerating a follower into its targeted set, D-agents also enumerate the follower into L. New N requirements ensure the negative part of the coding; their action is as in the classical case, and the rest of the construction goes through without changes.

6. Permitting

In this section we prove theorem 2.1. We are given a nonrecursive, regular r.e. set A and construct a SW-set such that R, L ≤_{α} A, by waiting for A to permit followers (for the diagonalisation requirements D and N) to enter their target sets. This might result in a requirement having an infinite set of followers. This would worry us for two reasons: we need to argue for fairness, that such a requirement will not initialize unboundedly often for the sake of these followers; and we need to verify that if the requirement does not declare victory, there is a last follower which isn’t realized at the end. Luckily, both conditions hold without further changes to the construction.

Construction

We are given a Δ_{2}(L_{α}) partial ordering ⪯ on ω. Let ⪯ [s] be a recursive approximation to ⪯. We assume that at every stage s, n ⪯ n[s] for all n. We are also given a nonrecursive, regular r.e. set A.

We describe the changes from the basic construction given above. We add new requirements N_{i,j,e}: If j ⪯̸ i then G_{j} ≠ Ψ_{e}(G_{i} ⊕ L). If agent n works for N_{i,j,e} and j ⪯ i[s] changes at s, we initialize n (and, of course, all weaker requirements) [Since i ⪯ j[s] stabilizes, this will not affect fairness].

Followers. At stage s, an agent n working for D_{i,j,e} or N_{i,j,e} may have followers. Followers are targeted for G_{j} and L in the D case, and for every G_{l} such that j ⪯ l[s]. A follower x for D_{i,j,e} is realized at stage s if Ψ_{e}(G_{i}; x) ↓= 0[s]; a follower x for N_{i,j,e} is realized at s if Ψ_{e}(G_{i} ⊕ L; x) ↓= 0[s]. A follower x is permitted at s if some y < x enters A at s.

The Construction. In the instructions for M_{i}: suppose that the agent n working for M_{i} defines Δ_{n,j}(x) at s, and x is a follower for some agent m > n; then m initializes all weaker agents. [Note that we do this even if x is not currently targeted for G_{j}, since it may be targeted for G_{j} later. This is not a problem since there are only finitely many functionals Δ defined by agents stronger than m.]

The new instructions for D_{i,j,e} and N_{i,j,e}: Assume n works for this requirement and has not declared victory since init(n, s). We skip this sub-stage if the requirement is N_{i,j,e} and j ⪯ i[s]. Otherwise: if some follower x is realized and permitted, enumerate the least one into the target sets, and declare victory. If not, and some follower x is realized but wasn’t realized before, initialize all weaker agents. Otherwise, if there are no unrealized followers, pick a new, large follower in α^{[n]}.

The rest of the construction is followed verbatim.

Verifications Fairness and finitary success. For fairness, we need to show that if r^{∗} = init(n, α) < α and n works for N_{i,j,e} or D_{i,j,e}, then it initializes on behalf of a stronger requirement m defining Δ_{m,j}(x) for some follower x of n only boundedly many times. Of course if n ever declares victory after r^{∗}, then it succeeds, abandons all followers and ceases all action for ever, so we assume this doesn’t happen. For s > r^{∗}, let K_{s} be the set of followers n has at the beginning of stage s.

Lemma 6.1. Every x ∈ K_{s} is realized at s, except perhaps for a maximal element.

Proof. We show this by induction on s. Note that if x ∈ K_{s} is realized at s then it remains realized for ever by force of n’s initialisation at the least stage at which x is realized.

Now assume that s is a limit stage and that x ∈ K_{s} is not maximal; take some y > x, y ∈ K_{s}. For some t < s, x, y ∈ K_{t}. By induction, x is realized at t; hence is realized at s as well. Assume the statement holds for K_{s}; then it holds for K_{s+1}, since at stage s all previously realized balls are still realized, and n perhaps appoints a new follower, larger than sup K_{s}, only if every x ∈ K_{s} is realized. □

Lemma 6.2. n eventually stops appointing new followers.

Proof. This is a standard permitting argument. If this fails, then we compute A by asserting that whenever x ∈ K_{s} is realized, then A ↾ x [s] = A ↾ x; this is because x will never be permitted. If n keeps appointing followers, then these followers are unbounded in size (since we appoint large ones), and each follower appointed eventually gets realized. □

We note that lemmas 4.1 and 4.3 hold for this construction. We can now verify that for a particular Δ_{m,j} for m < n, n eventually stops initialising. Let K be the eventual set of followers for n; it is α-finite. Let K′ be the set of followers x ∈ K such that n initializes for the sake of a Δ_{m,j}(x) computation. For x ∈ K′, let s(x) be the unique stage at which m defines Δ_{m,j}(x) and n initializes for this reason. Note that if x, y ∈ K′ and x < y then s(x) < s(y), since initialisation ensures that after s(y), Δ_{m,j}(x) will not be defined again. This ensures that s[K′] is bounded (since it is r.e. and of α-finite order-type), and thus ensures fairness. [In fact, if y ∈ K′, x ∈ K and x < y, then x ∈ K′. This is because Δ_{m,j}(x) must be defined at some times before s(y); at that stage, x is already a follower of n (it cannot be chosen later, since it is chosen large), thus n would initialize for x at that stage. Thus K′ = K ∩ sup K′ is α-finite, which shows that s[K′] is α-finite as well.]

Now we see that if n does not declare victory after r^{∗}, then there is a last, largest follower x appointed, and it never gets realized. This ensures success for n (together with the fact that j ⪯ i[s] eventually stabilizes at the right value).

Ordering. Since numbers entering R and L are permitted by A, we get that R, L ≤_{α} A (note that we need the regularity of A here). Success of the N requirements ensures that if j ⪯̸ i then G_{j} ≰_{α} G_{i} ⊕ L. Suppose that j ⪯ i; this is detected from some point onwards, and so from some stage, if x enters G_{j} because of some N requirement, then it enters G_{i} as well; otherwise it enters L. This ensures that G_{j} ≤_{α} G_{i} ⊕ L.

7. Cone Avoiding and Comparison

We prove theorem 2.2, by adding the Z requirements of the classical construction. We are given a Δ_{2}(L_{α}) partial ordering ⪯ on ω, and a recursive set of ⪯-minimal elements H. We are also given uniformly r.e. arrays ⟨U_{i}⟩_{i∈H} and ⟨V_{i,j}⟩_{i∈H,j<ω} (of regular sets), the latter being also uniformly low, and such that for all i ∈ H and j < ω, U_{i} ≰_{α} V_{i,j}. We add the requirements Z_{i,j,e}: If i ∈ H, then G_{i} ≠ Ψ_{e}(V_{i,j}).

Construction

Followers. At stage s, an agent n working for D_{i,j,e}, N_{i,j,e} or Z_{i,j,e} may have followers. If the requirement is D_{i,j,e}, followers are targeted for G_{j} and L; for every G_{l} such that j ⪯ l[s] if the requirement is N_{i,j,e}; and for G_{i} and L if the requirement is Z_{i,j,e}. A follower x for D_{i,j,e} is realized at stage s if Ψ_{e}(G_{i}; x) ↓= 0[s]; a follower x for N_{i,j,e} is realized at s if Ψ_{e}(G_{i} ⊕ L; x) ↓= 0[s]; a follower x for Z_{i,j,e} is realized at s if Ψ_{e}(V_{i,j}; x) ↓= 0[s]. A follower x is permitted at s if the requirement is D_{j,i,e}, N_{j,i,e} or Z_{i,j,e}, i ∈ H and some y < x enters U_{i} at s; if i ∉ H, then every follower is always permitted.

Guessing. Fix recursive functions f, g (whose exact identity will be revealed shortly). Suppose that agent n works for Z_{i,j,e}. Suppose that x ∈ G_{i}, and that x is realized at s (i.e. Ψ_{e}(V_{i,j}; x) ↓= 0[s]). To guess x’s success at s, n finds the least t > s such that f(n, t) = 1, or such that the computation is discovered to be incorrect by t (i.e. V_{i,j} changes on its use at t). n believes that x succeeds if at that t, the former happens. Note that the fact that this search halts will depend on the properties of the particular function f we pick later.

Suppose that x is a realized, permitted follower of n at s. To guess if x is useful at s, it finds the least t > s at which g(n, t) = 1 or the computation (for x) is discovered to be incorrect. It believes x is useful if the former happens.

The Construction. Directions for old requirements are identical to those of the last construction (of course, the meaning of ‘permitted’ has changed for the D and N requirements). Note that Z requirements initialize for M requirements just like D and N requirements. Note that enumerated followers are not considered followers here, even though the Z requirement never declares victory.

Instructions for n, working for Z_{i,j,e}: If n believes that some realized x ∈ G_{i}[s] is successful, skip this sub-stage. If not, and if there is some follower which is realized and permitted, check if it is useful, and if so, enumerate it into G_{i} and L, and initialize all weaker agents. If there are no useful followers, but all followers are realized, pick a new, large follower from α^{[n]}.

Recursion Theorem. Since the V_{i,j} are uniformly low, the recursion theorem implies the existence of total, recursive functions f, g such that if used above in the construction, satisfy that for all n, lim_{s→α} f(n, s) and lim_{s→α} g(n, s) exists and are either 0 or 1; and that if n works for Z_{i,j,e}, then lim_{s→α} f(n, s) = 1 iff at some stage of the construction there is a x ∈ G_{i} which is realized by a V_{i,j}-correct computation; and lim_{s→α} g(n, s) = 1 iff at some stage of the construction we didn’t skip the sub-stage devoted to n (due to some x ∈ G_{i} thought to be successful), and at that stage there is some follower for n which is permitted and realized by a correct computation.

One can see now that using these f and g in our construction, the guessing procedures always terminate; a realized x ∈ G_{i}[s] is either incorrectly realized (and this will be eventually discovered), or a witness to lim f(n, s) = 1; similarly for g.

Verifications

Verifications follow closely the previous ones, or the classical ones. In particular, verifications for D_{i,j,e} for j ∉ H are as in the first construction, and for j ∈ H are as in the proof of theorem 2.1, with U_{j} replacing A.

Now suppose that n works for Z_{i,j,e} and r^{∗} = init(n, α) < α.

Lemma 7.1. n eventually stops appointing new followers or enumerating followers into G_{i}.

Proof. This is classical. If lim f(n, s) = 1 then from some stage we skip n. If lim g(n, s) = 1 then lim f(n, s) = 1; the witness for the former is believed useful and enumerated. If lim g(n, s) = lim f(n, s) = 0 and both stabilize after t^{∗} > r^{∗}, then after t^{∗}, no follower is deemed useful, so n doesn’t enumerate followers after t^{∗}. If n keeps appointing new followers, then each follower x is eventually correctly realized; this is because at unboundedly many stages, larger followers are appointed, and at those stages, x is realized; and V_{i,j} is low. A correctly realized follower cannot be permitted after t^{∗} (or would get enumerated, since we do not skip n); this gives us a procedure of computing U_{i} from V_{i,j} (since there are followers unbounded in size). □

Just like for the D and N requirements, we get that n eventually stops initialising for the sake of stronger requirements M_{j}, and so fairness is maintained. We can now show that n succeeds: If lim f(n, s) = 1 this is clear. If not, and after t^{∗}, n ceases all action, then there is some follower x which isn’t eventually realized (this ensures success); otherwise, there is a stage at which all permanent followers are correctly realized (the function taking the follower to the stage at which it is correctly realized is computable from V_{i,j}, which is hyperregular, and the set of followers is α-finite.) But after that stage, n would appoint a new follower (we do not skip it). The rest of the verifications follow as before.

References

[Chu1938] A. Church, ‘The Constructive Second Number Calss’, Bulletin of the American Mathematical Society, 44, 224-232.

[ChKl1937] A. Church and S. C. Kleene, ‘Formal Definitions in the Theory of Ordinal Numbers’, Fundamenta Mathematica, 28, 11-21.

[Cho1984] C.T. Chong, Techniques of Admissible Recursion Theory, Lecture Notes in Mathematics, 1106 (Springer, Berlin).

[DoGr] R.G. Downey and N. Greenberg, ‘Totally < ω^{ω}-computably enumerable degrees and bounding M_{5}’, in preparation.

[DoGr2006] ’Totally < ω^{ω}-computably enumerable degrees and m-topped degrees, in Theory and Applications of Models of Computation (Cai, Cooper, Li, eds.), proceedings of TAMC 2006, Beijing, Lecture Notes in Computer Science 3959, Springer (2006), pp. 46-60.

[Dr1968] G.C. Driscoll, Jr., ‘Metarecursively Enumerable Sets and Their Metadegrees’, Journal of Symbolic Logic, 33, 389-411.

[Go1939] K.F. Gödel, ‘Consistency-Proof for the Generalized Continuum-Hypothsis’, Proceedings of the National Academy of Sciences USA, 25, 220-224.

[Gr2006] N. Greenberg, ‘The Role of True Finiteness in the Admissible Recursively Enumerable Degrees’, Memoirs of the American Mathematical Society, 181, no. 854 (2006), 99 pages.

[HaSh1982] L. Harrington and S. Shelah, ‘The Undecidability of the Recursively Enumerable Degrees’, Bulletin of the American Mathematical Society 6, no. 1, 79-80.

[Kl1938] S.C. Kleene, ‘On Notations for Ordinal Numbers’, Journal of Symbolic Logic, 3, 150-155.

[Kre1961] G. Kreisel, ‘Set Theoretic Problems Suggested by the Notion of Potential Totality’, in Infinitistic Methods, Proceedings of the Symposium on Foundations of Mathematics, Warsaw, 2-9 September 1959, (Pergamon Press, Oxford), 103-140.

[KreSa1963] G. Kreisel and G.E. Sacks, ‘Metarecursive Sets I, II’ (abstracts), Journal of

Symbolic Logic, 28, 304-305. [KreSa1965] G. Kreisel and G.E. Sacks, ‘Metarecursive Sets’, Journal of Symbolic Logic,

30, 318-338.

[Kri1964] S. Kripke, ‘Transfinite Recursion on Admissible Ordinals I, II’ (abstracts), Journal of Symbolic Logic, 29, 161-162.

[La1975] A. Lachlan, ‘A Recursively Enumerable Degree Which Will Not Split Over All Lesser Ones’, Annals of Mathematical Logic, 9, 307-365.

[Le1974] M. Lerman, Maximal α-r.e. sets, Transactions of the American Mathematical Society, 188, 341-386.

[Le1978] M. Lerman, Lattices of α-recursively enumerable sets, in Generalized Recursion Theory, J.E. Fenstad, R.O. Gandy and G.E. Sacks, eds., North-Holland, 1978, 223-238.

[LeSa1972] M. Lerman and G.E. Sacks, ‘Some Minimal Pairs of α-Recursively Enumerable Degrees’, Annals of Mathematical Logic, 4, 415-442.

[My1989] M. Mytilinaios, ‘Finite injury and Σ_{1}-induction’, Journal of Symbolic Logic, 54, 38-49.

[NiShSl1998] A. Nies, R.A. Shore, and T.A. Slaman, ‘Interpretability and Definability in the Recursively Enumerable Degrees’, Proceedings of the London Mathematical Society (3) 77, 241-291.

[Od1983] D. Odell, ‘Trace Constructions in α-Recursion Theory’, Ph. D. Thesis, Cornell University, Ithaca. NY.

[Pl1965] R. Platek, ‘Foundations of Recursion Theory’, Ph. D. Thesis, Stanford University, Stanford, CA.

[Sa1966a] G.E. Sacks, Degrees of Unsolvability, Annals of Mathematical Studies, Vol. 55 (Princeton University Press, Princeton, NJ, 2nd Ed).

[Sa1966b] G.E. Sacks, ‘Metarecursively Enumerable Sets and Admissible Ordinals’, Bulletin of the American Mathematical Society, 72, 59-64.

[Sa1966c] G. E. Sacks, Post’s problem, admissible ordinals, and regularity, Transactions of the American Mathematical Society, 124, 1-23.

[Sa1990] G.E. Sacks, Higher Recursion Theory (Springer, Berlin).

[SaSi1972] G.E. Sacks and S.G. Simpson, ‘The α-Finite Injury Method’, Annals of Mathematical Logic, 4, 323-367.

[ShSl1990] J. Shinoda and T.A. Slaman, ‘On the Theory of the PTIME Degrees of the Recursive Sets’, Journal of Computater and System Sciences, 41, 321-366.

[Sh1975] R.A. Shore, ‘The Irregular and Non-Hyperregular α-r.e. Degrees’, Israel Journal of Mathematics 22 (1975) 28-41.

[Sh1976a] R.A. Shore, ‘The Recursively Enumerable α-Degrees are Dense’, Annals of Mathematical Logic, 9, 123-155.

[Sh1976b] R.A. Shore, ‘On the Jump of an α-Recursively enumerable Set’, Transactions of the American Mathematical Society 217, 351-363.

[Sh1978] R.A. Shore, ‘On the ∀∃-Sentences of α-Recursion Theory’, in Generalized Recursion Theory II, E. Fenstad, R. O. Gandy and G. E. Sacks, eds., (North-Holland), 331-354

[Sh1982] R.A. Shore, ‘On Homogeneity and Definability in the First Order Theory of the Turing Degrees’, Journal of Symbolic Logic, 47, 8-16.

[Sh1997] R.A. Shore ‘Conjectures and Questions from Gerald Sacks’s Degrees of Unsolvability’, Sacks Symposium (Cambridge, MA, 1993), Archive for Mathematical Logic, 36, 233-253.

[Sh1999] R.A. Shore, ‘The Recursively Enumerable Degrees’, in Handbook of Computability Theory, E. Griffor ed., Studies in Logic and the Foundations of Mathematics (North-Holland, Amsterdam), 140, 169-197.

[Sl1991] T.A. Slaman, ‘Degree Structures’, in Proceedings of the International Congress of Mathematicians, (Kyoto, 1990) (Mathematical Society of Japan, Tokyo), 303-316.

[SlWo1989] T.A. Slaman and W.H. Woodin, ‘Σ_{1}-Collection and the Finite Injury Priority Method’, in Mathematical Logic and Applications (Kyoto, 1987), J. Shnoda, T. A. Slaman and T. Tugué eds., Lecture Notes in Mathematics, 1388, (Springer, Berlin), 178-188.

[Su1969] J. Sukonick, ‘Lower Bounds for Pairs of Metarecursively Enumerable Degrees’, Ph. D. Thesis, M.I.T., Cambridge, MA.

[Ta1960] G. Takeuti, ‘On the Recursive Functions of Ordinal Numbers’, Journal of the Mathematical Society of Japan, 12, 119-128.

[Ta1965] G. Takeuti, ‘Formalization of the Theory of Ordinal Numbers’, Journal of Symbolic Logic, 30, 295-317.

Department of Mathemcatics, Cornell Univeristy, Ithaca NY 14853

Department of Mathemcatics, Cornell Univeristy, Ithaca NY 14853

Department of Mathemcatics, University of California, Berkeley, Berkeley, CA 94720