The n-r.e. degrees: undecidability and Σ_{1} substructures

Mingzhong Cai ^{†} Department of Mathematics Cornell University Ithaca NY 14853

Richard A. Shore^{∗} Department of Mathematics Cornell University Ithaca NY 14853

Theodore A. Slaman^{‡} Department of Mathematics University of Califonia, Berkeley

August 11, 2010

1 Introduction

Turing reducibility (introduced in Turing [1939]) captures the intuitive notion of one set A ⊆ ℕ being computable from another B, We write A ≤_{T} B, A is Turing reducible to or computable from B to mean that there is a Turing machine (program) Φ that can compute A if given access to an “oracle” for B in the sense that the computing machine is augmented by a procedure that allows it to ask for any number n it computes if n ∈ B and to receive the correct answer. This reducibility naturally induces a partial order ≤_{T} on the set D of equivalence classes (called Turing degrees or simply degrees) a = {B|A ≤_{T} B & B ≤_{T} A}. The structure of D then captures that of relative complexity of computation of sets and functions (on ℕ). The study of this relation on all sets (functions), and on many important subclasses of sets has been a major occupation of recursion (computability) theory ever since its introduction.

In addition to the full structure, D, the most important substructures studied have been those of the recursively enumerable degrees, R, and D(≤ 0′), the degrees below the halting problem, K = {e|Φ_{e}(e) converges} whose degree is denoted by 0′. The recursively enumerable sets are those which can be enumerated (listed) by a recursive (computable) function. They can also be seen as those sets A for which there is a very simple approximation procedure, a recursive function f(x, s) to the characteristic function A(x) of A such that ∀x(f(x, 0) = 0 & lim f(x, s) = A(x)) that changes its mind about membership in A at most once, i.e. there is at most one s such that f(x, s) ≠ f(x, s + 1). Shoenfield’s Limit Lemma [1959] says that the sets (or functions) computable from the halting problem 0′ are precisely those with some convergent recursive approximation, i.e. the sets A such that there is a recursive function f(x, s) such that ∀x(f(x, 0) = 0 & lim f(x, s) = A(x)). So, while for each x there are only finitely many changes, the number of such changes over all x may be unbounded.

†Partially supported by NSF Grant DMS-0852811.

∗Partially supported by NSF Grants DMS-0554855, DMS-0852811 and John Templeton Foundation Grant 13408.

‡Partially supported by NSF Grant DMS-1001551 and by the John Templeton Foundation.

In this paper we study a natural hierarchy of intermediate classes of sets and degrees. The n-r.e. sets are those for which there is a recursive approximation f(x, s) as above for which there are at most n changes of value at each x. The corresponding degree structures are denoted D_{n}, the degrees of the n-r.e. sets. (So D_{1} = R the r.e. degrees.) This hierarchy was introduced by Putnam [1965] and Gold [1965]. It was extended into the transfinite by Ershov [1968, 1968a, 1970] who proved that the sets in the transfinite hierarchy he defined are precisely those computable from 0′.

The early work on degree theories began with the investigation of local algebraic or order-theoretic properties of the structures. This work continues in full force to this day. In the past three decades or so, a more global approach has emerged as well. Here one studies issues such as the decidability or, more generally, the complexity of the theories of degree structures as well as related questions about definability in, and possible automorphisms of, these structures.

For the first couple of decades, a major motivating idea was that (at least some of) these structures should be simple and characterizable by basic algebraic properties. Shoenfield’s conjecture [1965] would have been such a complete characterization of R analogous to that of the rationals as the countable dense linear order without endpoints. Even after the conjecture had been refuted by Lachlan [1966] and Yates [1966], Sacks [1966] still conjectured that the r.e. degrees were decidable. More recent results have produced a dramatically different prevailing paradigm for D, D(≤_{T} 0′) and R as well as many degree structures for other notions of reducibility. Rather than seeing the complexity of the structures as an obstacle to characterization, it suggests that a sufficiently strong proof of complexity would completely characterize each structure. Instead of expecting the structures to be decidable and homogeneous with many automorphisms (like the rationals), one looks to prove that the theories are as complicated as possible, there are definable degrees and that the structure has few automorphisms.

Typical results include the following:

Theorem 1.1. D, D(≤_{T} 0′) and R are each undecidable by Lachlan [1968]; Epstein [1979] and Lerman [1983]; and Harrington and Shelah [1982], respectively.

Theorem 1.2. The theories of D, D(≤_{T} 0′) and R are as complicated as possible, i.e. recursively isomorphic to true second order arithmetic for D and to true first order arithmetic for D(≤_{T} 0′) and R by Simpson [1977]; Shore [1981]; and Harrington and Slaman and then Slaman and Woodin (both unpublished) (see Nies, Shore and Slaman [1998] for a proof and stronger results), respectively.

Theorem 1.3. All relations invariant under the double jump that are definable in arithmetic are definable in D, D(≤_{T} 0′) and R where for D we mean second order arithmetic and for the others first order by Slaman and Woodin [2001] (see Slaman [1991] for an announcement and Shore [2007] for a quite different proof that applies to various substructures of D as well), essentially Shore [1988] (but see also Nies, Shore and Slaman [1998, Theorem 3.11 and the remarks following it])and Nies, Shore and Slaman [1998], respectively. (The converse holds by the definability of these degree structures in arithmetic.)

A survey paper for this area is Shore [2006].

In this paper we take the first steps on this road for the structures D_{n} by proving that they are all undecidable. We conjecture that our work can be extended along the lines of Nies, Shore and Slaman [1998] to show that their theories are also all recursively isomorphic to that of true arithmetic. Perhaps one can even prove definability results as done there for R. Basic survey papers on the structure of the D_{n} are Arslanov [2009, 2010] and Stephan, Yang and Yu [2009].

Another important theme in the study of these degree structures has been delimiting the similarities and explicating the differences among them. While it is relatively easy to distinguish among D, D(≤_{T} 0′) and R in many way the issue becomes particularly compelling when we turn to the D_{n}. It is easy to imagine, and was proved early on, that moving from R to all sets or even to the unlimited approximations characterizing those below 0′ introduces many differences. For the D_{n}, however, the question is what does the ability to change precisely one more time buy us in terms of additional degrees, algebraic structure and complexity.

Of course, the first question is are the D_{n} actually distinct. Indeed, there are, for each n, (n + 1)-r.e. degrees which are not n-r.e. ([Cooper [1971] with the stronger result that they can be found not even n-rea in Jockusch and Shore [1984]]). While the one quantifier theory of all the degree structures from R to D are the same since one can embed all finite (even countable) partial orderings into R (and so all the rest as well), there were many early results establishing elementary differences between R and the other D_{n} with cupping, density and lattice embedding properties playing the featured role (as in, for example, Arslanov [1985] Cooper et al. [1991], Downey [1989], respectively). Differences between any of the other D_{n}, however, seemed hard to find. Downey [1989] even conjectured that they might all be elementarily equivalent, i.e. all sentences (in the first order language with ≤) true in any D_{n} for n ≥ 2 is true in all of them. This conjecture was not refuted until quite recently. Arslanov, Kalimullin and Lempp [2010] provide an elementary difference between D_{2} and D_{3}. In fact, the sentence they exhibit on which the structures differ is at the smallest possible level: two quantifiers (∀∃). They conjecture (as one would now expect) that the D_{n} are pairwise not elementarily equivalent. They also conjecture that this level of difference (∀∃) is as small as possible in the strong sense that every ∃∀ sentence true in any D_{n} is true in every D_{m} for m ≥ n.

Now an ∃∀ sentence is true if there are choices (parameters substitutable) for the existentially quantified variables such that the resulting universal sentence is true of these parameters. The strongest way that their conjecture could be true is for the same parameters to work in both structures. This view brings to mind a much earlier question raised about other pairs of our degree structures. Are any Σ_{1} substructures of any others. (M is a Σ_{1} substructure of N, M ⪯_{1} N, if for any Σ_{1} formula ∃ȳφ(x̄, ȳ) where φ is quantifier free and any choice of elements ā from M, M ⊨ ∃ȳφ(ā, ȳ) ⇔ N ⊨ ∃ȳφ(ā, ȳ).)

Slaman ([1983]) proved early on that this fails at the extreme ends: R ⪯̸_{1} D(≤ 0′) (and so, a fortiori, D_{n} ⪯̸_{1} D(≤ 0′) for any n ≥ 1. Slaman and then others raised the natural question of whether it could be that D_{n} ⪯_{1} D_{m} for any n < m. Yang and Yu [2006] provided a negative answer for n = 1 and m = 2 (and so for any m ≥ 2). We complete the picture by showing that D_{n} ⪯̸_{1} D_{m} for any n < m. (We have just heard that Arslanov and Yamaleev are preparing a different proof for the case n = 2.)

Turning now to our proofs, we begin with undecidability. As usual (see for essentially our situation §2 of Nies, Shore and Slaman [1998] or for a more general model theoretic treatment Hodges [1993, 5.3]), we have a formula φ_{D}(x, p̄) which, for each choice of parameters p̄, defines a subset D of our structure D_{n} and another formula φ_{R}(x, y, p̄) which defines a binary relation R on D. To prove undecidability it suffices to show that, as the parameters vary over D_{n}, a sufficiently rich class of structures (D, R) are coded in this way. In our case, we code partial orders. As the (r.e.) set of theorems of the theory of partial orders is recursively inseparable from the (r.e.) set of sentences (of the language of partial orders) that are false in some finite partial order (Taitslin [1962]), it suffices to code any collection of relations containing all finite partial orders. The point here is that if D_{n} were decidable then the set of sentences true in every partial order coded by φ_{D} and φ_{R} as the parameters p̄ range over all elements of D_{n} would be recursive. Of course, it contains the theorems of the theory of partial orders and, if we code all finite ones, is disjoint from the set of sentences with finite counterexamples. As it turns out, it is no more difficult to prove that one can code all recursive partial orders than all finite ones. This is what we do explicitly in our proof of Theorem 1.4. We use the basic idea of the domain being maximal degrees g ≤_{T} a not joining some other degree p above q from Harrington and Shelah [1982] and build on their work.

Theorem 1.4. Given a recursive partial order (ω, ≤_{∗}) and an n ≥ 1, there exist uniformly n-r.e. sets G_{i} for each i ∈ ω, an n-r.e. set L and r.e. sets P and Q such that:

1. Each g_{i} is a maximal n-r.e. degree below a such that q ≰ g_{i} ∨ p where A = ⨁_{i} G_{i}.

2. g_{i} ≤ g_{j} ∨ l if and only if i ≤_{∗} j.

Thus the required formulas φ_{D} and φ_{R} defining our domains and order relations have parameters a, p and q. The first says that x is a maximal degree below a such that q ≰ x ∨ p. The second says that x ≤ y ∨ l. so we have the desired result.

Theorem 1.5. The theories of D_{n} are undecidable for every n.

If instead of recursive inseparability, we wanted to rely only on the undecidability of the theory of partial orders, we should code all partial orders recursive in 0′ as every sentence which is not a theorem (of the theory) has a counterexample recursive in 0′ by the effective version of the completeness theorem.

One can with only minor modifications not affecting the structure of our proof handle partial orders recursive in 0′. We precisely describe the modifications needed in 6.5. With some additional work and a serious reorganization of the priority tree, one can get all partial orders recursive in 0′′. One puts in a new type of node which guesses in a Δ_{3} procedure at each bit of information about this partial order and bases later work on these guesses. The added complexity is considerable without much gain for applications. It seems that one can even get any Σ_{3} partial order by a slightly more complicated procedure. We briefly describe this procedure in 6.5 as well.

It is worth remarking that our proof works for n = 1 as well as all larger n. Indeed, it can be significantly simplified for n = 1 by omitting all items that consider the possibility that the G_{i} and W_{i} (the list of n-r.e. sets recursive in A) are not r.e. This gives a considerably simplified proof of the undecidability of R along the lines suggested in Harrington and Shelah but with a simpler statement using fewer parameters and a significantly easier construction. We do not believe any proof even for R along these lines has been published before.

We next turn to Σ_{1} substructures.

Theorem 1.6. D_{n} ⪯̸_{1} D_{m} for n < m.

The technical result needed here is the following generalization of Theorem 1.12 in Yang and Yue [2006] who do the case n = 1:

Theorem 1.7. For any n ≥ 1, there are r.e. degrees g, p, q, an n-r.e. degree a and an n + 1-r.e. degree d such that:

1. For every n-r.e. degree w ≤ a, either q ≤ w ∨ p, or w ≤ g.

2. d ≤ a, q ≰ d ∨ p, and d ≰ g.

This theorem shows directly that D_{n} is not a Σ_{1} elementary substructure of D_{n+1} in the language with ∨ as well as ≤: In D_{n}, no w below a has the property that q ≰ w ∨ p and w ≰ g while in R_{n+1}, d ≤_{T} a has both properties. We can eliminate ∨ by rephrasing the property of w as ∃z(w, p ≤ z & q ≰ z) & w ≰ g which is Σ_{1} in just ≤ and so the existence of a w with this property is true in D_{n+1} (i.e. d) but false in D_{n}. Of course, as d is in D_{m} for every m ≥ n + 1, D_{n} ⪯̸_{1} D_{m} as well.

Much of the construction and verification is the same for Theorems 1.4 and 1.7. We treat the first theorem as primary. In §2 where we cover basic notions and conventions common to both, we use curly brackets {} to indicate changes (usually alphabetic only at this stage) for the second theorem. The rest of the paper is divided into two parts, one for each of the theorems. Each part describes first the requirements (§3, 7), then the priority tree (§4, 8), the construction (§5, 9) and finally the verifications that the construction succeeds (§6, 10). We describe everything in full detail for the first theorem and then for the second describe only the changes needed. In our descriptions of the constructions, material enclosed in square brackets [] is meant to convey intuition or describe aspects of the construction that will only be verified later. It is not part of the formal definition of the construction procedures.

As might be expected from the types of requirements, both constructions are 0′′′ arguments even for the case n = 1. As these constructions go, however, ours are at the simpler end: the priority tree is finitely branching, there is no backtracking and only one type of requirement is injured along the true path. The key idea for carrying the arguments from the r.e. case (n = 1) to the n-r.e. one (n > 1) in Theorem 1.4 is what we call shuffling (§5.2). Roughly speaking, at the crucial 0′′′ determined nodes, we are attempting to construct functionals Δ that, to working towards the maximality of the g_{i}, try to compute some given n-r.e. set W = Φ(A) from one G_{i} that we are building over the full construction. The most delicate part of the verification of the first construction is the correctness of these functionals (Lemma 6.8). We argue that the cause of an incorrect computation, say of Δ(u), must be that some number z entered A for the first time and allowed W (u) to change. Another delicate argument shows that if W also changed for the first time, we could correct the functional Δ (or see that we are not on the true path). If the change in W was not that u entered for the first time, we argue that we can shuffle A between two past values (giving, via Φ, two different values for W (u)) by repeatedly taking z out and putting it back in as necessary so as to eventually show that W ≠ Φ(A).The point here is that z has entered A for the first time while the change in W is not a first change. Thus as W_{l} can make no more than n changes overall, it can make no more than n − 2 additional changes. On the other hand, as z has entered A for the first time, we can make n − 1 more changes in A and so eventually guarantee that W ≠ Φ(A).

In the second construction (§9.2.1), the correctness of the functionals Δ becomes immediate as we simply change G when necessary. The crucial problem then becomes guaranteeing the correctness of computations from G diagonalizing against D (§10). Here we take advantage of the fact that D can change one more time than any other set by using a procedure like one used in Yang and Yu [2006] to remove a number (that entered for the first time) from D. In our case it allows us to either cure some problem we are facing or start a shuffling procedure for A diagonalizing against the offending W.

2 Basic Notions and Conventions

Given a set A, let A ↾ u be the initial segment of A of length u.

We use upper case Greek letters to denote Turing functionals. For any Turing functional Δ, the use of a convergent Δ(A; x) is defined as the least number u such that Δ(A ↾ u; x) ↓. We use lower case Greek letters corresponding to the Turing functional to denote the use, e.g. δ(A; x) denotes the use of Δ at x. More importantly, we injure the computation by adding δ(A; x) − 1 into A, but not by adding δ(A; x) into A. If it doesn’t cause confusion, we may omit A and write δ(x).

We will have families Ψ, Π, Θ and Φ which specify standard enumerations of all the Turing functionals. We follow the usual conventions for such standard enumerations such as the approximations to these functionals for any (approximation to an) oracle set at stage s asks questions about (makes use of) only numbers less than s and converges only at inputs less than s. We also assume, without loss of generality, that for the standard enumerations with two oracles such as Θ(G ⊕ P; x) the uses on both are always the same and we denote it by θ(x).

We will also construct two families of Turing functionals Δ(G) and Γ(W ⊕P). For the ones with two oracles, we do not require that the uses of W and P are the same. Hence we can write γ(W; x) and γ(P; x) to denote the W and P parts of the use, respectively. Although for simplicity we generally work as if we are specifically defining these oracles at each individual x with the associated uses, we really are assuming that the uses are monotonic in x and make all changes to keep them that way, usually without explicit mention. As Q is r.e., when we are computing it from W ⊕ P by Γ, except for this monotonicity condition, we only need to produce computations (axioms) that at x give output 0 when x ∉ Q. These may be injured and new ones put into Γ (perhaps with larger use). In the case that x ∉ Q and we are expecting Γ to compute Q, we must eventually settle on a convergent computation (axiom) applying to W_{i} ⊕ P. If x ∈ Q, when x enters Q it suffices to kill any current computation of 0 from W_{i} ⊕ P. We do this by putting a number less than the P -use into P. We can then simply keep the value of Γ at 1 without changing the use (remembering that P is r.e.).

In our two constructions, we specify priority trees which grow downward. At each stage s of the construction, we build a path of length s {at most s} of accessible nodes along the priority tree. Our convention is that, the nodes to the left of, or above, a node α have higher priority. We always preserve the information used at previous stages by the nodes that are to the left of the accessible ones by initializing the nodes that are to the right of the accessible ones, i.e., remove all information from previous stages such as witness numbers, defined functionals and imposed restraints.

Nodes can impose two types of restraint: a permanent one or an alternating one. Permanent restraint means that no node of lower priority can act so as to injure the restraint by changing a set where restrained. By convention permanent restraint imposed at stage s restrains the initial segments of length s of L and all the G_{i} {A, D and G}. Any permanent restraint on P must be mentioned specifically. [We never need to restrain Q.] Alternating restraints are caused by the announcements of A-stages or P -stages which we describe later in the construction. Basically, during A-stages, we remove the alternating restraint for L and the G_{i} {A and D} allowing numbers to enter (or leave) these sets and we impose an alternating restraint on P and Q {and G} so that no numbers can enter P or Q {or G} at this stage. During P -stages, we do the opposite (except that no numbers ever leave the r.e. sets P or Q {or G}).

3 Requirements I

We now begin the proof of our main technical result.

Theorem 1.4. Given a recursive partial order (ω, ≤_{∗}) and an n ≥ 1, there exist uniformly n-r.e. sets G_{i} for each i ∈ ω, an n-r.e. set L and r.e. sets P and Q such that:

1. Each g_{i} is a maximal n-r.e. degree below a such that q ≰ g_{i} ∨ p where A = ⨁_{i} G_{i}.

2. g_{i} ≤ g_{j} ∨ l if and only if i ≤_{∗} j.

First, for the negative order facts, we have requirements for each pair i ≰_{∗} j and each e:

Ψ_{e,i,j} : Ψ_{e}(L ⊕ G_{j}) ≠ G_{i}.

Similarly for each triple (i, j, e) with i ≠ j, we also want:

Π_{e,i,j} : Π_{e}(G_{j}) ≠ G_{i},

i.e., the G_{i}’s are pairwise incomparable.

Then for each pair (i, e) we need:

Θ_{e,i} : Θ_{e}(G_{i} ⊕ P) ≠ Q.

We also need the main requirements that each g_{i} is a maximal n-r.e. degree g ≤_{T} a such that q ≰ g ∨ p. We let W_{i} be an effective list of all the n-r.e. sets.

Φ_{e,i} : Φ_{e}(A) = W_{i} → [∃Γ(Γ(W_{i} ⊕ P) = Q) ∨ (∃k(W_{i} ≤_{T} G_{k}))].

• Note that these Φ requirements by themselves do not ensure that each g_{i} is maximal. That is why we need the Π requirements to make all the G_{i}’s pairwise incomparable. The Φ requirements then do guarantee that the g_{i} are maximal.

If it does not cause confusion, we may omit the subscripts of the requirements and sets in our argument to simplify the notation.

Finally, we have to deal with the positive order facts, i.e., G_{i} ≤_{T} L ⊕ G_{j} for i <_{∗} j. We will guarantee that, for x > i, j, x ∈ G_{i} ⇔ x ∈ L or x ∈ G_{j}. Putting numbers into a G_{i} is initiated only by a Ψ or Π requirement. For Π action, we simply put a witness x that is going into G_{i} (for diagonalization) into L as well. When action is initiated for diagonalization by Ψ at stage s, we put x into G_{i} and also into each G_{l} with l >_{∗} i for each l < x. As, in this case, i ≰_{∗} j, this action does not add elements to G_{j} and so it does not injure the Ψ computation initiating the action. We say that each witness x (for a Ψ or Π requirement) has an associated block of sets (the G_{l} such that l < x and i ≤ l or G_{i} and L, respectively). During the construction x moves into or out of all the sets in its block simultaneously.

4 Priority Tree I

We put all the Ψ, Π, Θ and Φ requirements into one priority list. Our priority tree consists of nodes and branches. Each node is associated with a requirement in the list and each branch leaving a node is assigned an outcome. We label each node with its associated requirement and each branch with the assigned outcome. When we list outcomes of a node we do so in a left to right order that specifies the left to right order on the priority tree of the branches leaving that node

A Ψ or Π node has two outcomes: d and w, which stand for “diagonalization” and “wait” respectively.

A Φ node has outcomes s_{n−1}, s_{n−2}, ..., s_{1}, i and w. Outcome s_{i} stands for “shuffle” for the i-th time. We will explain what this means in detail in the construction. Roughly, it means that we expect to shuffle between two versions of A (by removing numbers from A and then possibly putting them back in) as we cycle back to this node. The expected result of this shuffling is to guarantee that Φ(A) ≠ W by a diagonalization. Outcome i stands for “infinite” agreement between Φ(A) and W and outcome w stands for “wait”.

A Θ node β has outcomes d, g_{α_{1}}, g_{α_{2}},...,g_{α_{k}} and w. As usual, d and w stand for “diagonalization” and “wait” respectively. Each α_{i} is a Φ node above β which has outcome i along β. If γ is a node below β extending the g_{α_{i}} branch from β, then we say that γ sees an α_{i} −β pair. [The intuition here is that γ believes that α_{i} and its associated requirement is satisfied by β.]

A Φ node α is active at γ ⊃ α if α has outcome i along γ and γ does not see an α′ − β′ pair such that α′ ⊆ α ⊂ β′ ⊂ γ. For there to be a g_{α_{i}} outcome of a Θ node β, we also require that α_{i} be active at β. We order these g_{α_{i}}’s from left to right in descending order going down the tree to β, i.e., α_{1} ⊂ α_{2} ⊂ ... ⊂ α_{k}. [This choice of left to right order comes into play at the very end of the proof of Lemma 6.16 and is discussed in §??.]

The priority tree is defined recursively as follows: suppose τ is an immediate extension of σ, we associate τ with the highest priority requirement among all requirements which either have not appeared above τ or are Φ requirements that, above τ, have appeared only at nodes δ with outcome i such that τ sees an α−β pair with α ⊂ δ ⊂ β. [So δ looks inactive but not really satisfied, i.e. if satisfied at some earlier point it has since been “captured” by some other pair.] Then we add the corresponding number of branches (outcomes) below τ. It is easy to see that this tree is recursive.

5 Construction I

At stage s of the construction, we build a path of length s of the accessible nodes along the priority tree. It is possible that at some accessible node we will announce that s is an A-stage or a P -stage. All later nodes accessible at s must respect this announcement by acting according the the rules governing A-stages or P -stages: no changes in A can occur once a P -stage has been announced and none in P or Q once an A-stage has been announced. In the construction, we will make sure that the first accessible Θ node with a type g outcome (if any) makes the announcement for the stage s. An over-riding rule is that permanent restraint imposed by a node (not since initialized) is not violated by action at any node of lower priority (i.e. below it or to its right). If any instruction below leads to any such situation, we do not carry it out and instead go to outcome w [and do nothing].

In this section, we first describe the construction at stage s for each node when there has been as yet no announcement for the stage and then specify the modifications for when there has already been one.

5.1 no announcement, Ψ or Π node

The actions at Ψ and Π nodes are quite standard: If it is the first time we come to this node (after it was last initialized), then we pick a witness number x which is fresh, i.e., larger than any number we have seen by this point in the construction. In general, at a Ψ (Ψ(L ⊕ G_{j}) ≠ G_{i}) or a Π (Π(G_{j}) ≠ G_{i}) node with a witness x already assigned (and not yet canceled by initialization), we check whether the computation at x converges to 0. If it diverges or converges to a nonzero number, then we do nothing and go to the w outcome. If it converges to 0 and x ∉ G_{i}, then we do a diagonalization: put x into G_{i} and into all the other sets in its block as described in Section 3, impose permanent restraint [to preserve the use of the computation] and go to the d outcome. If x is already in G_{i}, then we (again) go to outcome d [and keep the restraint already imposed].

5.2 no announcement, Φ node

At a Φ node α (Φ(A) = W) if we have not yet had a type s outcome (since α was last initialized) let t be the last stage at which α was accessible (since last initialized). If there is a such stage and a u < l_{α}(t), l_{α}(s) such that Φ(u) (and so W (u)) differ at t and s with the difference not being that u has entered W for the first time and the only change in A ↾ ϕ(u) at t is that some z has entered its block of sets for the first time because of the action of a node extending α then we initiate a shuffle on z by removing z from its block of sets, impose permanent restraint and go to outcome s_{1}. We call this shuffle strategy Plan S with shuffle points sp1(= t) < sp2(= s). [Note that these shuffle points have the property that A_{sp1}(= A_{sp1} ↾ sp1) and A_{sp2}(= A_{sp2} ↾ sp2) differ below sp1 only in that z is in its block of sets in A_{sp2} and out of them in A_{sp1}. More crucially, they produce different values for Φ at some u, i.e. Φ(A_{sp1}; u) ≠ Φ(A_{sp2}; u).] If we had an outcome of type s at the last stage t at which α was accessible, we check whether W (u) is different at s than at t. If so, restore the initial segment of A to the version of A which is different from the current one (by putting z into or taking it out of its block of sets), impose permanent and let the outcome be s_{i+1}. If not, we stay at the s_{i} outcome. [This maintains any previously imposed permanent restraint.]

If we haven’t initiated shuffling, let l_{α}(s) be the length of agreement between the current versions of Φ(A) and W. Note that whenever we initialize this node α, we also initialize the values of this function to be 0. If this is the first time that l_{α}(s) > 0 after it has last been initialized, or l_{α}(s) > l_{α}(t) where t is the last stage when α had an i outcome, then we go to the i outcome; otherwise we go to the w outcome.

If we go to the i outcome, we continue to define a functional Γ [aiming to make Γ(W ⊕ P) = Q]. At this point, we enumerate a new axiom making Γ(W ↾ l_{α}(s) ⊕ P ↾ v; w) = Q(w), where v is a fresh number and w is one more than the largest number where we have previously defined Γ (since it was last initialized). If P has changed on its Γ-use at some x < w and the change was caused by the action of a node βˆ g_{α} [necessarily extending αˆ i] with witness x as in §5.4.2, then we redefine Γ(x) to be the current value of Q(x) with W -use l_{α}(s) and fresh P -use. [As P is r.e. this change permanently invalidates the previous axiom for Γ(x).] Similarly, if W has changed on its use u_{1} (where its old P -use is v_{1}) so as to make Γ(x) divergent but x has not entered Q, we see if x is currently the witness for some Θ node β below α (for G). If so, we look at the last stage t at which β was accessible and see if its outcome was g_{α}. If G has not changed on θ(x) as defined at the point of stage t at which β was reached and the change in W includes one at some u making it different from the common value of Δ(u) and W (u) at t, then we redefine Γ(x) with W -use l_{α}(s) = u_{2} and fresh P -use. In all other cases of a W or P change on γ(W; x) or γ(P; x), respectively, that makes Γ(x) divergent we redefine Γ(x) with the same uses as it last had but for the new values of W and P (subject, of course, to our monotonicity requirements on the use).

5.3 no announcement, Θ node

At a Θ node β accessible for first time after it has been last initialized, we pick a fresh witness x for diagonalizing Θ(G_{i} ⊕ P) ≠ Q. In general, if we have a witness x already assigned (and not yet canceled by initialization), we check whether the computation converges at the witness x. [As usual when there are higher priority requirements that are expected to put infinitely many numbers into a set, we restrict our attention to computations that are consistent with our beliefs as prescribed by our actions in §5.4.2. Here this means the following:] We also require that the computation be believable, i.e. for every requirement Θ̂ assigned to a node α with witness x̂ and αˆ gα̂ ⊆ β for some α̂, θ(x) < γα̂(P; x̂) and if γα̂(P; x̂) has been previously increased by a Ŵ change (as described at the end of §5.2) from say u_{1} to u_{2} and v_{1} − 1 is not yet in P then θ(x) < v_{1} as well. If Θ(x) does not converge with a believable computation or so converges to a nonzero number, then we go to the w outcome and do nothing.

[If the believable computation Θ(G_{i} ⊕ P; x) converges to 0 with P -use θ(x), then we would like to diagonalize, i.e., put x into Q and preserve the P and G_{i} use of the computation. However, we must worry about whether doing so injures some already defined Γ computation at a node above β. For example, if there is a such a Γ(W ⊕P) = Q which computes Q(x) = 0 with γ(P; x) ≤ θ(x), then our desired diagonalization would falsify this computation of Q while correcting the Γ computation (by putting its use into P and redefining the functional) would injure our Θ computation for diagonalization. Our plans must be more subtle.] If Θ(x) converges with a believable computation we proceed as follows:

Let α_{1} ⊂ α_{2} ⊂ ... ⊂ α_{k} be all the active nodes above β with each α_{j} defining its functional Γ_{j}(W_{l_{j}} ⊕ P). Let γ_{j}(P; x) be the P -use of Γ_{j} at x, if it has already been defined. [See §?? for some comments on the left-right ordering indicted here for these nodes and the associated outcomes g_{α_{j}} below.]

5.3.1 Plan D: diagonalization

If θ(x) < γ_{j}(P; x) for all j for which γ_{j}(P; x) is defined, we do a modified diagonalization: We enumerate x into Q and also enumerate γ_{α_{j}}(P; x) − 1 into P for each j. [This allows us to correct the Γ_{j}(x) when α_{j}ˆ i is next accessible.] We now impose the usual permanent restraint but also one on P ↾ θ(x) [to preserve the Θ computation] and go to outcome d. Until β is initialized, it has outcome d at every later stage at which it is accessible.

5.4 Stage Announcements

If we cannot follow Plan D, i.e., θ(x) ≥ γ_{j}(P; x) for some j, then we take the largest j such that θ(x) ≥ γ_{j}(P; x) [and are likely to go to outcome g_{α_{j}} where we build a functional Δ computing W_{l_{j}} from G_{i}]. [The choice of j is relevant at the very end of the proof of Lemma 6.8 but our choice of the largest j (rather than say the smallest) doesn’t make any difference in this construction. It does, however, matter in the at the end of the proof of Lemma 10.1 for our second theorem.] 5.4.1 Plan A: A-stage announcement

If this is the first time (since the last initialization) that we would go to the g_{α_{j}} outcome or the last time we went there we announced a P -stage then we go to outcome g_{α_{j}} and announce an A-stage [and so allow elements to be enumerated into or taken out of A].

Otherwise, let t be the last stage when βˆ g_{α_{j}} was accessible. By our construction and case assumption, t must have been announced as an A-stage at βˆ g_{α_{j}}. (If some node to the right or left of βˆ g_{α_{j}} made an announcement at stage t then β would not have been accessible at t. If some node α above β made an announcement at t then one would also have to be made above β at s contrary to our case assumption that no announcement has been made at this stage before we reached β.)

5.4.2 Plan P: P -stage announcement

We now go to the g_{α_{j}} outcome and extend Δ by adding axioms computing W_{l_{j}}(u) from G_{i} with fresh use for any u < l_{α_{j}}(s) for which Δ has not previously been defined. In addition, we put γ_{j}(P; x) − 1 into P to injure the current Θ computation (since γ_{j}(P; x) ≤ θ(x)). [This kills the current computation of Γ(x) and as P is r.e. it can never apply to W ⊕ P again.] Moreover, if γ_{j}(P; x) has been previously increased by a Ŵ change (as described at the end of §5.2 from say u_{1} to u_{2} and v_{1} − 1 is not yet in P then we also put v_{1} − 1 into P. [This kills the old computation of Γ_{j}(x) as well as and guarantees that it too will never again apply to W ⊕ P.] [We will redefine Γ_{j} with axioms using the new version of P with a fresh P -use and W_{l_{j}} use l_{α_{j}}(v) when we next get to α_{j}ˆ i at v. The result of this action is that we increase the Γ_{j} use from P and W_{l_{j}} and so the next time when this β is accessible with the g_{α_{j}} outcome, the use θ(x) must be larger than that of this stage. If this happens infinitely often Γ_{j}(x) diverges but we expect to satisfy the associated Φ requirement by building Δ(G_{i}) = W_{l_{j}} at βˆ g_{α_{j}}. We then also satisfy the Θ requirement associated with β as Θ(x) diverges as well.] We now announce that the current stage is a P -stage.

If there has been a change in G_{i} that leaves Δ(u) undefined where it had previously been defined, we put in a new axiom computing the current value of W_{l_{j}}(u) with the old use.

[We shall argue for β on the true path with true outcome g_{α_{j}} that we build Δ consistently and correctly compute W_{l_{j}} at each stage (Lemma 6.8). Typically, it turns out that, along the true path, if W_{l_{j}} has changed where previously computed, then G_{i} must have changed at the corresponding part used in the computation.]

5.5 modifications with a stage announcement

When there is has already been a stage announcement before we reach β, the node β has to obey the appropriate rules. For a Ψ, Π or Θ node, we see what we would have done if there had been no stage announcement as yet. If that action is compatible with the current stage announcement (no announcement of an A-stage or change in A if a P -stage; no change in P or Q and no announcement of a P -stage if an A-stage), we proceed as if there had been no announcement. If not, we do nothing and go to outcome w.

For a Φ node, the modification is slightly trickier. [Later we will need the fact that each node along the true path passes down alternating A and P restraints in the construction.] Here in order to go to the i outcome, we need to wait (with outcome w) for a stage when the stage announcement is different from the last stage t when we had an i outcome, and also the length of agreement is longer than its last value. [In this way, the Φ node passes down alternating A and P restraints along the i outcome.] When we have already initiated shuffling, we act as before at A-stages and at P -stages we go to outcome w. [This maintains the permanent restraint imposed when we initiated shuffling or last shuffled as the nodes that imposed it are now to our left.]

6 Verification I

6.1 True path and true outcome

First of all, as in usual priority tree arguments, there is a leftmost path accessible infinitely often. (Each node has only finitely many outcomes.) This is the true path and the outcomes along it the true outcomes.

Lemma 6.1. Numbers enter or leave A or L only when permanent restraint is imposed by a Π, Ψ or Φ node. When such nodes β impose permanent restraint, we move to the left of any previous outcome that has been accessible since β was last initialized.

Proof. By inspection of the construction.

Lemma 6.2. At most one node acts to change A at any stage s.

Proof. If we first act at α to change A at s then we move to an outcome to the left of all previously accessible ones (since α was last initialized) by Lemma 6.1. So all later nodes accessible at s that can change A are accessible for the first time since last initialized and so at most appoint fresh witnesses or (for Φ nodes) begin their construction of Γ anew. None of these witnesses can go in at s as no convergences can be seen at numbers larger than s. No shuffling can been initiated for any of the Φ nodes by construction.

Lemma 6.3. If a node α is initialized at stage s then it never later acts to change any set below s.

Proof. If α is a Π, Ψ or Θ node it only acts to put numbers at least as large as its witness x into A or P and any witness appointed after s is larger than s. For Π and Ψ nodes this is immediate. For Θ, its action puts numbers of the form γ(P; x) − 1 into P and by construction γ(P; x) > x. For Φ nodes, the only action changing sets is shuffling. This shuffling only involves numbers appointed below α at stages when α was accessible since it was last initialized.

Recursively along the true path, we now determine the actions of the nodes on it after no node to their left is ever accessible and prove that all the requirements are satisfied along it. For any node β on the true path we let s(β) be the first stage at which β is accessible but after which no node to its left is ever accessible again.

Lemma 6.4. Any permanent restraint imposed by a node β at any s ≥ s(β) is never injured by any other node.

Proof. The only actions that can injure such restraint after s(β) are ones by nodes above it on the true path. None can change A or L by Lemma 6.1. As for P, the only permanent restraint imposed on P is by Θ nodes when we go to outcome d and restrain P ↾ θ(x). Now nodes β̂ above β of type Θ with outcomes gα̂ may put numbers into P but they only put in ones of the form γα̂(P; x̂) and our believability requirement on the computation of Θ(x) guarantees that all of the current values of these γα̂(P; x̂) are larger than θ(x). The only way one of them could decrease is if it had previously been increased from u_{1} to u_{2} by a change in W as described at the end of §5.2 and then W changes back to the old value before the old computation is killed by v_{1} − 1 going into P. However, our believability condition also requires that θ(x) is less than these v_{1} as well. Any later change increases the use above the previous values Thus no changes every occur in P below θ(x).

Lemma 6.5. The final witness for any node β chosen at s(β) is larger than any permanent restraint of higher priority than β.

Proof. By construction the witness is chosen fresh and so larger than anything previously seen. The only nodes of higher priority that can impose permanent restraint later are ones above β. None of type Π, Ψ or Φ can do so by Lemma 6.1. One of type Θ also imposes permanent restraint only when it moves left to outcome d contradicting our definition of s(β).

Before we show that the requirements are satisfied we analyze the alternating restraint.

6.2 Alternating A and P -stages

Lemma 6.6. Every node along the true path above the first Θ node β with type g outcome on the true path never sees or makes a stage announcement (imposes alternating restraint) when accessible. For the other nodes α on the true path, their true outcomes, o, are accessible at infinitely many A and P -stages. Indeed, after s(αˆ o), the stages at which αˆ o is accessible alternate between A and P ones (the node passes down alternating A and P restraints along its true outcome).

Proof. For any node above β the claim is immediate from the rules of the construction. For a Π or Ψ node below β, it is immediate from the construction that after s(β) either we always have outcome w or, whenever we are at β after the first time we have outcome d we also have outcome d. So for these nodes the Lemma is obvious. For a Φ node below β, either the true outcome is shuffling (s), or waiting (w), or infinitary (i). In the two former cases, the outcome is again eventually constant: Once we move to a type s outcome, the construction guarantees that we can move only to the left to another type s outcome. Thus the outcome is eventually constant at some type s outcome. As for outcome w, any rightmost outcome that is the true outcome of a node β on the true path is the outcome at almost every stage at which β is accessible. In the third case, our construction in §5.5 ensures that it passes down alternating A and P restraint along the outcome i as required.

The Θ node β which first makes the announcements along the true path must have true outcome some g_{α}. Then according to our construction, if it announced a P -stage the last time it was accessible, we follow Plan A and make an A-stage announcement. If it last announced an A-stage, then we follow Plan P and announce a P -stage.

Finally for any other Θ node β′ on the true path, the claim is also immediate for true outcome d or w as above. In the case of a g_{α} outcome, the construction automatically guarantees that it always waits for an alternation in the type of restraint to move again to the true g_{α} outcome.

We next analyze the functionals Δ and Γ that we construct.

6.3 The functionals are well-defined and correct

Lemma 6.7. The functionals Γ built at nodes αˆ i on the true path starting at s(αˆ i) are well-defined, i.e., we do not add contradictory axioms in the construction and when defined give the correct current value for Q. They are defined on arbitrarily large initial segments of ω and so, if convergent at every x, they correctly compute the desired sets.

Proof. It is clear by construction that we define Γ(x) at least once for each x: As αˆ i is on the true path, l_{α}(s) is going to infinity on the stages at which αˆ i is accessible. On each of these stages we define Γ on a new number. Once defined Γ(x) is then defined at every stage at which αˆ i is accessible by construction. As for consistency and correctness, note first that it is immediate from the construction that at any stage at most one axiom in Γ applies to the current value of W ⊕ P. Now, the only way any problem could arise is if Q(x) has changed for some x but W and P have not changed on the corresponding use or they change and then W reverts back to a previous value that applies to some older computation (with value 0). However, in our construction, Q(x) can change only when we implement Plan D to put x into Q at a some stage v for a Θ node β̂. Any number x put into Q by such nodes to the right of αˆ i must be both appointed fresh and then put in while we are to the right of αˆ i without αˆ i becoming accessible in between. Thus when αˆ i is again accessible Γ has not been defined at x and so when we define Γ(x) we set it equal to 1 with the first axiom and all later ones as well. Any x put in by nodes to the left of αˆ i are in by s(αˆ i) and so we define Γ correctly on them as well.

Thus we can assume that β̂ is below αˆ i. If α is active at β̂, then when x enters Q at v we put γ(P; x) − 1 into P by construction and so kill the current computation and put in a new one giving the correct answer when we next reach αˆ i. If α is not active at β̂, there must be a first β′ ⊂ β̂ with β′ ˆ α̂ ⊂ β̂ for some α̂ ⊆ α. So in particular, α is active at β′. Now β′ has a witness x′ necessarily less than x (as x is appointed later) and at stage v when we reached β′ˆ gα̂ we put γ(x′) < γ(x) into P and so kill the current computation of Γ(x) and correct it when we next reach αˆ i. Note that both P and Q are r.e. so γ(P; x) − 1 has never been in P before and x will never leave Q. As we impose permanent restraint when we go to outcome d and diagonalize, no later change in W can return us to any old computation.

Lemma 6.8. The functional Δ defined at the true g_{α} outcome of a Θ node β (for G_{i}) on the true path starting at s(βˆ g_{α}) is well-defined. When Δ(u) is convergent while we are at βˆ g_{α}, it always give the current value of W (u) on an initial segment of ω. Indeed, Δ(G_{i}) = W as desired. (For notational convenience we assume that α is assigned the Φ requirement for W which is constructing the functional Γ at its i outcome.)

Proof. As for the final claim, note first that by construction if Δ(u) is ever defined it is defined at every u′ < u and then it is defined there at every later P -stage at which βˆ g_{α} is accessible. Moreover, at these stages we extend its domain of definition to l_{α}(s) which is going to infinity since αˆ i ⊆ β is on the true path. Once Δ(u) is defined, its use never changes by construction and so if, at every stage when defined at βˆ g_{α}, it correctly computes W (u), it does so in the end.

For correctness, we argue by induction on the stages at which βˆ g_{α} is accessible beginning at s(βˆ g_{α}) that Δ(u) = W (u) at every u at which Δ is defined. This is obviously true by construction if s is the first stage at which Δ(u) is defined. Suppose it is true at s and the next stage at which βˆ g_{α} is accessible is t and the problem occurs at u.

Note that no change in A ↾ s or P ↾ θ(x) can occur between s and t. No node to the right of βˆ g_{α} can make such a change by Lemma 6.3. No node to its left can do so as they are never accessible after s(βˆ g_{α}). No node above βˆ g_{α} can change A at all by Lemma 6.1. Nodes above βˆ g_{α} may act to put numbers of the form γα̂(P; x̂) into P via other Θ requirements β̂ above β with outcome gα̂ but by our believability condition on the Θ(x) computation, at stage s none of them are below θ(x) at s. The only way one of them could decrease is if it had previously been increased from u_{1} to u_{2} by a change in W as described at the end of §5.2 and then W changes back to the old value before the old computation is killed by v_{1} − 1 going into P. However, our believability condition requires that θ(x) is also less than these v_{1}.

If s was a P -stage then no change occurred in A ↾ s at s so none has by stage t. Thus if W (u) at t is different from its value at s it would be different from Φ(A; u) at t since that is the same as it was at s. This would move us to outcome w at α and so βˆ g_{α} would not be accessible for a contradiction.

Suppose then that s was an A-stage. No change in P ↾ θ(x) occurs at s as no node above the one announcing the A-stage can change P without declaring a P -stage or moving left and none after it can because it is an A-stage. Moreover, none can occur before t as above. If no change occurs in A at s then, as none occurs before t, Φ(u) and Δ(u) would be the same at t as at s. If this value is not that of W (u) at t then αˆ i would again not be accessible at t for a contradiction. Thus there has been some change in A at s. By Lemma 6.2, there is precisely one z that entered or left its block of sets at s. By Lemmas 6.1 and 6.3, the node σ causing the change must extend βˆ g_{α} as we are after s(βˆ g_{α}) and βˆ g_{α} is accessible. Now if there is no change in W (u) between s and t, then the only way we could have a disagreement with Δ(u) at t (so the old axiom for Δ(u) at s is no longer valid but we cannot simply put in a new one with the same value) is that the change for z returns us to a previous computation of Δ(u) giving a different value. However, such a change in z can be caused only by σ shuffling z. Such a shuffle returns A ↾ v to its value at a previous stage v. If Δ(u) was defined at v then by induction it would have the same value as Φ(u) and W (u) and no change can have happened in any of these when we reach t. Thus we would still have agreement at t as required. So we may also assume that W (u) is different at s and t.

Suppose first that z < θ(x) and G_{i} is in its block of sets. Next, suppose the change occurred because of some shuffling procedure at σ. If Δ(u) was first defined before the shuffling began at σ, then we would have a contradiction as above.

If Δ(u) was first defined after the shuffling began, say at v ≤ s with, for the sake of definiteness, z ∈ G, then its use is fresh at v and so larger than z. Let v′ ≥ v be the next stage after v at which we shuffle z at σ. If v′ = s then z has been in G_{i} from v to s and is removed at stage s by our action at σ ⊃ βˆ g_{α}. Thus when we next return to βˆ g_{α} at t we have z ∉ G_{i} for the first time since Δ(u) was defined and we redefine it to be the current value of W (u) as required. So we may assume that v′ < s and at stage v′ we have Φ(u) = W (u) = Δ(u) at βˆ g_{α} by induction. When we reach σ at v′ we remove z from its block of sets including G_{i} and impose permanent restraint. When βˆ g_{α} is next accessible, say at v′′ ≤ s, we redefine Δ(u) = W (u) = Φ(u) with z ∉ G_{i} (and its block of sets) but with the rest of A ↾ v′ the same as it was at v′ (because of the permanent restraint imposed at v′ which, by Lemma 6.1, could be violated only by moving to the left of σ which could then not cause our problem at s). If v′′ = s then at stage s we shuffle z back into G_{i} (and its block of sets) at σ and impose permanent restraint. We next return to βˆ g_{a} at t and have Φ(u) and Δ(u) and so W (u) the same as they were at stage v′ at βˆ g_{α}, i.e. they all agree as required. Finally, if v′′ < s then later at stage s we shuffle at σ between the values for all of these sets and functionals that we had at v′ and v′′. Thus once again when we reach βˆ g_{α} at t all agree.

Thus the change that has occurred is that z entered G_{i} for the first time at s. If the change in W (u) is not that u has entered for the first time, then we would have initiated a shuffling procedure at α at stage t and so move to αˆ s_{1} hence to the left of βˆ g_{α} ⊃ αˆ i for a contradiction.

Thus through stage s, W (u) = 0. Suppose Δ(u) was first defined at s′, of course with value 0 and fresh use q. We claim that z < q and so its entry into G allows us to correct Δ(u) at t as desired. If not, it was chosen fresh as a witness for σ at a point in the construction during a stage s′′ ≥ s′ after Δ(u) was defined at s′ but before s. In this case, however, z > s′′ and so z > ϕ(u) at s′′. Note that Φ(u) is defined at s′′ because z is appointed at σ ⊃ β ⊃ αˆ i. Now from the point of stage s′′ at which αˆ i is accessible to stage s any change in A ↾ s′′ would initialize σ and so z could not enter A at s. (At s′′ no node between αˆ i and σ can change A without moving left of σ. Then at σ all nodes to the right of σ are initialized and so cannot make any changes below s′′ by Lemma 6.3. As σ appointed a witness at s′′, this is the first stage at which σ has been accessible since it was last initialized so all A action by nodes below σ also involve only numbers larger than s′′. Finally, any A action after s′′ by a node of higher priority than σ would also initialize it by Lemma 6.1.) Thus at s, ϕ(u) and A ↾ ϕ(u) are the same as they were at s′′, i.e. Φ(A, u) = 0 = W (u) at s with the same computations as at s′′. Now the only changes in A during stage s is that z enters its block of sets but z > s′′ and then no changes occur in A ↾ s before stage t. Thus at stage t we also have Φ(A, u) = 0 and so if W (u) = 1 at t, the outcome of α would not be i, for a contradiction.

Finally, suppose z ≥ θ(x) or G_{i} is not in its block so no change occurs in G_{i} ↾ θ(x) at s and so none before t. When Δ(u) was defined at the P -stage v (necessarily before the A-stage s), u < l_{α}(v) and so after v, u < γ(W; x) whenever it is defined. In fact, at each P -stage during which we reach βˆ g_{α} (starting with v) we put γ(P; x) into P and subsequently increase γ(W; x) to l_{α}(v′) > l_{α}(v) when we are next at αˆ i (at v′ > v). Each computation of Γ(x) killed in this way can never to reapply to W ⊕ P as P is r.e. As we cannot reach βˆ d, the only other way γ(x) can change requires a W change that causes a difference between the previously computed common values of Δ and W. By our induction assumption this cannot have occurred before s. So all axioms for Γ(x) provided before s are invalid by the end of stage s.

As W (u) has different values at s and t, the change in W introduces a value of W (u) that we see at αˆ i at some first stage v′′ after s but no later than t. As we have argued, no old computation of Γ(x) is still valid at v′′. Thus by construction we would increase γ(P; x) at v′′ to a fresh value larger than θ(x). When we return to βˆ g_{α} at t, γ(P; x) is now larger than θ(x) which has not changed since s. Thus by construction, g_{α} cannot be the outcome of β at t for a contradiction.

6.4 All requirements are satisfied

Finally we want to show that all requirements are satisfied.

The positive order requirements are easily verified by our construction.

Lemma 6.9. If i <_{∗} j then G_{i} ≤_{T} L ⊕ G_{j}.

Proof. Consider an x > i, j. To decide if x ∈ G_{i} go to stage x of the construction and see if x has been appointed as a witness for some Π or Ψ requirement with G_{i} in its block. If not, then x ∉ G_{i}. (Indeed x is not in any G_{k}.) If it is in the block for a Π requirement then L is also in its block. If for a Ψ requirement then G_{j} is in the block. In any case, as once appointed x moves into or out of all sets in its block during the entire construction, x ∈ G_{i} ⇔ x ∈ L in the Π case and x ∈ G_{i} ⇔ x ∈ G_{j} in the Ψ case.

We now move to the negative (diagonalization) requirements.

Lemma 6.10. The Π and Ψ requirements are satisfied.

Proof. Suppose the requirement is assigned to the node β on the true path. If, after s(β), we ever go to outcome d and so diagonalize, the result is immediate from the construction and Lemma 6.4. If not, it must be that the outcome is always w after after s(β). If the relevant computation converged to 0 the correct computation would be available from some point on and so by Lemma 6.6 we would eventually see it at an A-stage and so move to outcome d by Lemma 6.5. If not, then x never enters G_{i} and we also satisfy the requirement as desired.

We next consider the Θ requirements.

Lemma 6.11. If a Θ node β on the true path has true outcome d then the associated requirement is satisfied.

Proof. Consider the stage s(βˆ d) when β has outcome d (and is never again initialized). We put the witness x into Q and impose permanent restraint to preserve the computations Θ(G_{i} ⊕ P; x) = 0. Lemma 6.4 shows that this computation is preserved.

Lemma 6.12. If a Θ node β on the true path has true outcome g_{α}, then its requirement is satisfied. Indeed, for x the final witness for β, both θ(x) and γ_{α}(x) go to infinity on the stages when βˆ g_{α} is accessible. Moreover, any time we increase γ_{α}(x) because of a W change as at the end of §5.2, we later kill the P -use of the old computation as well by putting v_{1} into P.

Proof. In this case, by our construction (and Lemmas 6.5 and 6.6), we infinitely often put numbers (γ(P; x) − 1) into P and redefine Γ(W_{i} ⊕ P) with a fresh P -use. (The first of these Lemmas implies that the numbers we want to put into P are larger than any permanent restraint as they are of the form γ(P; x) which is larger than the witness x for β.) So by our criteria for going to outcome g_{α}, we infinitely often see θ(x) > γ(P; x), so θ(x) must go to infinity (when βˆ g_{α} is accessible) along with γ(P; x) and the computation Θ(G_{i} ⊕ P; x) diverges. As for any increase in γ(x) because of W change as in §5.2, the next time we are at βˆ g_{α} we put the associated v_{1} into P by construction.

Lemma 6.13. If a Θ node β on the true path has true outcome w then the associated requirement is satisfied.

Proof. Note that if the outcome of β were d at any stage after s(β) then d would be the true outcome by construction. Thus in our case, we never put the final witness x for β into G_{i}. So our only concern is that Θ(G_{i} ⊕ P; x) = 0. In this case, there is a stage after which it always converges to 0 and with a fixed use. By the previous Lemma this computation is believable at almost every stage when we are at β. Thus by construction and Lemmas 6.5 and 6.6, as in Lemma 6.12, we would eventually have outcome d for a contradiction.

We now turn to the Φ requirements.

Lemma 6.14. If a Φ node β on the true path has true outcome of type s, then the associated requirement is satisfied.

Proof. The nature of the shuffling points guarantees that, at every stage with outcome of type s, Φ(A; x) ↓≠ W (x) and so this is true at the end of the construction as well and the requirement is satisfied. The crucial point here is that the permanent restraint imposed by β which are increasing as we move left among the type s outcomes can never be injured (other than by the shuffling done by β itself) by Lemma 6.4.

Lemma 6.15. If a Φ node β on the true path has true true outcome w then the associated requirement is satisfied.

Proof. If Φ(A) = W then the length of agreement would go to infinity and so, by construction and Lemma 6.6, we would eventually move to outcome i after s(βˆ w) for a contradiction.

Finally, we have to deal with the case that every Φ node on the true path has true outcome i.

Lemma 6.16. Every Φ requirement is satisfied.

Proof. As usual in a 0′′′ priority tree argument, we want to consider the last node α along the true path assigned to a given Φ requirement. To see that there is such a node, argue by induction on the Φ requirements. The point here is that any Φ requirement, once assigned to a node that is never again initialized, can return to the list of requirements from which we draw to make assignments of requirements to nodes (along the true path) only when a strictly higher priority node becomes inactive. So once no node with a higher priority Φ requirement assigned ever becomes inactive again, the next node β assigned to Φ either becomes inactive once along the true path (by being satisfied by action at a lower Θ node on the true path) and then remains inactive or it never becomes inactive on the true path. In either case, Φ is never assigned to a node below β by the definition of the priority tree.

Let α be the last node along the true path assigned to the Φ requirement (Φ(A) = W_{i}). By the previous two Lemmas, we may assume that its true outcome is i. If there is an Θ node β (Θ(G_{k} ⊕ P) ≠ Q) on the true path with true outcome g_{α}, then we have built a functional Δ at βˆ g_{α} that computes W_{i} from G_{k} by Lemma 6.8.

If there is no such Θ node β, then we claim that we have successfully built Γ(W_{i}⊕P) = Q starting at s(αˆ i). By Lemma 6.7, we only have to verify that γ(x) is eventually constant for each x. We begin to define our Γ at s(αˆ i). Assume inductively that γ(x̂) has stabilized for x̂ < x. Thereafter, once Γ(x) is defined, our construction allows γ(x) to increase because of a change in P at most once for each time some βˆ g_{α} below αˆ i is accessible and the Θ requirement assigned to β has witness x or once when βˆ d is accessible (again with witness x for β). It can increase because of a W change at most finitely often for each such βˆ g_{α} and stage. (At worst only when W changes on the domain of Δ at that stage.) At most one β has x assigned as a witness. If β is not on the true path, it can be accessible with witness x at most finitely often. If β is on the true path, once βˆ d is accessible, βˆ g_{α} cannot be accessible again unless β is initialized and so chooses a new witness. If βˆ g_{α} is accessible infinitely often, then some gα̂ (possibly to the left of g_{α}) would be its true outcome and so α̂ ⊆ α. If α = α̂ we contradict our case assumption. If α̂ ⊂ α then α would be come inactive and Φ would be reassigned later to a node below βˆ g_{α} on the true path contradicting our choice of α. Thus Γ(x) can change at most finitely often as required.

6.5 Δ_{2}^{0} and Δ_{3}^{0} partial orders

To handle partial orders recursive in 0′ we make the following changes in the construction:

We begin with a recursive approximation f(i, j, s) to the (characteristic function of the) relation i ≤_{∗} j. We now have requirements Ψ_{e,i,j} for every e, i, j with a new additional leftmost outcome n. At stage s at a node α for Ψ_{e,i,j}, if f(i, j, , s) = 1 (so we think we do not want to diagonalize) we go to outcome n and do nothing. If f(i, j, s) = 0 we act as before with a new definition of the block for our witness x. When x (necessarily larger than i and j) is appointed as a witness, we determine its block by calculating f(k, l, t) for each k, l < x and t > x until we reach a t at which either f(i, j, t) = 1 or the relation on numbers k, l < x defined by f(k, l, t) is a partial order ⪯. In the first case, the outcome is again n and we do nothing. In the second case, we put G_{k} into the block for x if and only if i ⪯ k (i.e. f(i, k, t) = 1). Note that f(i, j, t) = 0 by our case assumption and so G_{j} is not in the block.

To see that this modification works, note that if i ≰_{∗} j then from some point on f(i, j, t) = 0 and so we never again have an outcome n for Ψ_{e,i,j} and so satisfy the negative order requirements as before. For the positive ones, suppose k ≤_{∗} l and for t ≥ t_{0}, f(k, l, t) = 1. For any witness x ≥ k, l, t_{0}, if its block does not contain k then, of course, x ∉ k. If it does contain k it also contains l and so x ∈ G_{k} if and only if x ∈ G_{l}. (The case for Π requirements is as before.)

The modifications needed for partial orders recursive in 0′′ are more complicated. For each i, j we insert a requirement into the priority order used for the Δ_{2}^{0} case and so on each path of the priority tree a node ε that guesses in a Δ_{3}^{0} way whether i ≤_{∗} j, i.e. the node has infinitely many outcomes ⟨x, k⟩ with x ∈ w and k ∈ {0, 1} ordered lexicographically. We organize determining the outcome of ε at each stage s so that if ⟨x, k⟩ is the leftmost outcome accessible infinitely often then x is the least witness to the Σ_{3} formula which says that i ≤_{∗} j if k = 1 and the least witness to the Σ_{3} formula which says that i ≰_{∗} j if k = 0. In addition we coordinate this guessing with the stage announcements so that the true outcome passes on alternating restraint as before. We then act at nodes as in the Δ_{2}^{0} case but using at each node only the information about the ordering coded on the outcomes of the ε type nodes above it. So for for a Ψ type requirement, if the relation given in this way is not a partial order ⪯ or says that i ⪯ j, we go to outcome n. (We put the ε nodes on the tree so that any node for a requirement Ψ_{e,i,j} has an ε type node above it assigned to i ≤_{∗} j.) If it is does specify a partial order with i ⪯̸ j, then we act as before but now the block of sets for a witness x consists of all G_{k} with i ⪯ k. One can now verify that the construction works. The argument for the positive order relations runs as follows: If i ≤_{∗} j, find the node σ on the true path by which that fact has been decided. Nodes to the left of σ put only finitely many x into G_{i} and can be ignored. For nodes to its right that appoint any witness x (necessarily before stage x), we can wait for the node to be initialized to see if x enters G_{i}. For nodes below σ in the tree assigned to any Ψ requirement, any witness x that puts G_{i} in its block also puts G_{j} and so for those x, x ∈ G_{i} ⇔ x ∈ G_{j}. Of course, for witness x for Π_{e,i,k} type nodes, x ∈ G_{i} ⇔ x ∈ L as before. Of course, for any x not appointed as a witness for one of these type nodes, x ∉ G_{i}.

If the partial order is only Σ_{3}, then one adjust the previous procedure by instead of single nodes with Δ_{3} guessing at i ≤_{∗} j putting in individual nodes for each i and j guessing that a particular number is the (least) witness to the Σ_{3} fact that i ≤_{∗} j. Along a path with the Π_{2}^{0} outcome that the witness is correct, one follows a coding stratgey incorporating this individual fact. If it is true, then some node σ on the true path has the correct witness and all nodes below it obey the required coding strategy. Nodes not below this one, are handled as above. For each node guessing a witness for the Σ_{3} fact, where we see that it is false, i.e. along a path with the Σ_{2}^{0} outcome, we put in one more Ψ requirement for i ≰_{∗} j. So if i ≰_{∗} j, then along the true path, we will put in Ψ_{e,i,j} requirements for every e and so satisfy the requirement.

7 Requirements II

We now turn to our second technical result:

Theorem 1.7. For any n ≥ 1, there are r.e. degrees g, p, q, an n-r.e. degree a and an n + 1-r.e. degree d such that:

1. For every n-r.e. degree w ≤ a, either q ≤ w ∨ p, or w ≤ g.

2. d ≤ a, q ≰ d ∨ p, and d ≰ g.

Our list of requirements is very similar to the one used for our first technical theorem:

1. Ψ_{e} : Ψ_{e}(G) ≠ D;

2. Θ_{e} : Θ_{e}(D ⊕ P) ≠ Q;

3. Φ_{e,i} : (Φ_{e}(A) = W_{i}) → [∃Γ(Γ(W_{i} ⊕ P) = Q) ∨ ∃Δ(Δ(G) = W_{i})].

In addition, we need to make D ≤_{T} A. Note that we only add elements into D by diagonalization for Ψ requirements. Whenever we pick a witness x for D, x is fresh at that stage, and we reserve the pair (x, x + 1) for coding D into A. If x enters D for the first time, then we also put x into A. If x leaves D later, we either take x out of A or put x + 1 into A. In the first case, we may shuffle x into and out of A and D simultaneously but allowing at most n changes. In the second case, we may shuffle x + 1 into and out of A and D simultaneously again allowing at most n changes in A (but this may make for n + 1 changes in D altogether). Therefore in the end x is in D if and only if x is in A and x + 1 is not in A. No numbers other than these Ψ-witnesses enter or leave D in our construction, and so D is recursive in A, A is n-r.e. and D is (n + 1)-r.e.

8 Priority Tree II

Our priority tree here is almost the same as the one used in the first theorem. Of course, we do not have Π nodes. For any Θ node β, we put a new [temporary] outcome r_{α_{j}} to the left of each g_{α_{j}}. So the outcomes of β are d, r_{α_{1}}, g_{α_{1}}, r_{α_{2}},...,g_{α_{k}} and w. We do not add nodes below these type r outcomes. [So a stage s may terminate at such an outcome before we reach level s of the priority tree. We show, however, in Lemma 10.1 that no node of type r can be on the true path.] The notions of active Φ nodes, α − β pairs are defined in the same way as in Section 4.

9 Construction II

We only specify the construction at stage s when there is no stage announcement. In the case when there is a stage announcement, we act as in §5.5. Note that in this construction we only change G during P stages. The default permanent restraint is on A, D and G while for P it must be specifically mentioned.

9.1 Ψ node and Φ node

At a Ψ node, the action is the same as the one in §5.1 with G for L ⊕ G_{i} and D for G_{i}.

At a Φ node α, we follow almost the same procedure as we did in §5.2. The only difference is in how we revise the computations from old Γ-axioms. As in the first construction, if P has changed and the change was caused by some β with g_{α} outcome by putting the old use into P, then we increase the W -use to l_{s}(α) and P -use to be fresh. If a W change caused some Γ(x) to be undefined, then we check whether x is a diagonalization witness for some β below α, if so, we also check whether D has changed by putting in some number for the first time at the previous stage when β was accessible (and β has not been initialized since). If so, we then redefine Γ(x) with W -use up to l_{s}(α) and fresh P -use. In all other cases we redefine the axiom without changing the uses.

9.2 Θ node

[At a Θ node, the obvious difference from the first construction is that we use D in our Θ computation but use G in our Δ computation. So the arguments in 6.3 are no longer valid. In the case that W changes, we have no reason to expect a G change. In fact, so far we have no requirements or procedures that put numbers into G. Here we actively put numbers into G to correct Δ computations. We will make full use of the fact that D is n + 1-r.e., i.e., it has one more chance to change than A and the W_{i}. We may remove a number from D while leaving it in A but putting z + 1 into A. This will afford us the opportunity to produce a situation in which we may initiate shuffling.]

At a Θ node β accessible for first time after it has been last initialized, we pick a fresh witness x for diagonalizing Θ(D ⊕ P) ≠ Q. If we have a witness x already assigned (and not yet canceled by initialization) at β, we check whether the Θ computation converges at the witness x. If we do not have a believable (defined in the same way as in our first theorem) computation Θ(D ⊕ P; x), we go to outcome w. If we do, we follow Plan D as in §5.3.1 if we can. If not, we have a planned outcome g_{α_{j}} as in §5.4.1 and check whether we have not been at this outcome since β was last initialized or whether the previous stage t when we went to this outcome was a P -stage. If so we announce an A-stage and continue the construction below β.

Otherwise, we have two possibilities.

9.2.1 Plan R: removal

Let t be the last stage at which β was accessible. If there is a y < γ(W; x) such that W (y) has different values at t and s and the only change in A ↾ t is that some element z entered D and A for the first time at stage t because of the action of a node below β [necessarily a Ψ node], we remove z from D and add z + 1 into A [so we restore the version of D at stage t up to the θ use]. We go to the r_{α_{j}} outcome and terminate the current stage of the construction. We call the least such y the key witness for the removal plan.

[The idea here is that, before β can become accessible again without being initialized, we would see at α_{j} if y has left W. If so we would initiate a shuffle there on z + 1 and initialize β. If not, we will argue that we must go to the left of g_{α_{j}} and r_{α_{j}}. Roughly, the idea is that the computation Θ(D ⊕ P; x) will be the same as that at stage t while γ_{j}(P; x) will have been increased above θ(x) by y entering W. ]

9.2.2 Plan G: change G

If we satisfy none of the above criteria, we go to the outcome g_{α_{j}} and continue to build Δ consistently. For each u, if Δ(u) was defined at the last stage t at which βˆ g_{α_{j}} was accessible and W (u) has not changed since then, we simply update the Δ axiom with the current version of G (if necessary) without changing the use. If Δ(u) was defined at t but W (u) is now different, then let δ(u) be the use of G in the old Δ computation. We add δ(x) − 1 into G and redefine Δ with a fresh use in G. [We preserve the consistency of Δ by doing this as G is r.e.] Then we also define a new computation Δ(u) for the next u which was undefined with fresh G-use. Finally, we follow Plan P to add γ uses into P as in Section 5.4.2 and announce a P -stage.

10 Verification II

We can go through most of Section 6 and show that we have a leftmost path visited infinitely often (that it is actually infinite follows from Lemma 10.1), and each node along the true path is passing down alternating A-stages and P -stages along the true path. There are obvious alphabetic changes needed In Lemmas 6.1-6.6 – no L or Π. Otherwise, note first that Plan R action for Ψ nodes are an exception to Lemma 6.1. Next, Lemma 6.2 applies to D as well as A and we have to remark that if we implement Plan R no node is even accessible thereafter, while Plan R action cannot be the second type to change A (or D) at s by the arguments given in the proof of Lemma 6.2. Finally, for the proof of 6.3 note that G-uses for Δ are also chosen fresh. It is then not difficult to see that functionals are well-defined and complete the job we assigned if they are along the true path. For the Γ’s, use Lemma 6.7. For the Δ’s, it is directly guaranteed by our construction. [The complicated argument for Lemma 6.8 is not needed but see the proof of Lemma 10.1 for some remnants of it.]

For the verification that all the requirements are satisfied we continue as in §6.4. The positive order requirements (Lemma 6.9) are simply replaced by the requirement that D ≤_{T} A. Our construction guarantees that x is in D if and only if x is in A and x + 1 is not. Except for the satisfaction of the Ψ requirements (Lemma 6.10) in the case of d outcome all the other verifications proceed as in §6.4.

As for the Ψ requirements, the major issue is that here we add elements into G (when we construct Δ) and this action might, a priori, injure some apparently satisfied Ψ requirement of lower priority. To show that the Ψ requirements are all satisfied, we first need a few lemmas.

Lemma 10.1. No outcome of type r can be on the true path.

Proof. The argument is similar to the one in the end of the proof of Lemma 6.8. Consider any Θ node β on the true path and suppose, for the sake of a contradiction, that its true outcome is r_{α}.

Let s = s(βˆ r_{α}) and, as in the construction, let t be the previous stage at which β had outcome g_{α}; x, the diagonalization witness at β; y, the key witness for Plan R at s; and z, the unique element that entered D for the first time at t. We remove z from D at s following Plan R. Let s′ be the next stage at which β is accessible with a believable Θ computation. If y was ever out of W between s and s′ (when α was accessible) then, we would have initiated a shuffle plan at α and so moved left of β ⊇ αˆ i for a contradiction. (As we terminate stage s at βˆ r_{α} with no action, there is no change in A at s. Between s and s′ Lemma 6.3 shows that A ↾ s is preserved. So if W (y) changes we satisfy the conditions for shuffling at α.) Thus we also assume that y remains in W at every stage at which α is accessible through stage s′.

Now at stage s we restored the computation Θ(D ⊕ P, x) of stage t by removing z from D: z is the only change to D up to θ(x) at t by Lemma 6.2, and P is preserved by the A-stage announcement at t. Between t and s, D ↾ t is preserved by Lemma 6.3 and P ↾ θ(x) is not injured by nodes to the right. Finally, our believability condition guarantees that P ↾ θ(x) is also not injured by nodes above β. Thus at stage s′ we still have the same computation of Θ(x) as at stage t.

Now consider the Γ computation we build at αˆ i. At stage s the conditions for Plan R guarantee that y < γ(W; x) (at t) has entered W for the first time after t and by s. So when this happens and we are at α we see a change in the W part of Γ(x) which makes Γ(x) undefined. Therefore, by our construction, we add a new axiom with W - use the current length of agreement and P -use fresh, which is larger than θ(P, x) at t. This γ(P, x) remains large since y remains in W, therefore at stage s′ we will see that γ(P, x) > θ(P, x).

For other active α_{l}’s between α and β, the corresponding γ_{l}(W_{l}; x)are larger than θ(P, x) at stage t by the rules for going to outcome g_{α}. The only way that anyone of these uses can decrease is by W_{l} changing at some stage v ≤ s′ from its value on γ_{l}(W_{l}; x) at t back to an older version. If this happens, then when α_{l} is accessible at v ≤ s′ we initiate a shuffle at α_{l} by shuffling z + 1 which we added into A by Plan R at t with shuffle points t and v. This would move us to the left of β for a contradiction. Therefore these uses cannot decrease, and at stage s′ they are still larger than θ(P, x). Hence at stage s′ we will go to the left of the r_{α} outcome by our construction for the desired contradiction.

Lemma 10.2. In the construction at a Θ node β, if we change G as in 9.2.2 at a stage s > s(β), then it must be the case that at the previous stage t when βˆ g_{α} was accessible, we followed either Plan S or Plan R to change D at some node σ below β.

Proof. By our construction, if we must change G by putting in some δ(u)−1, then W (u) and therefore A ↾ ϕ(u) must be different at stage s from stage t. By Lemmas 6.3 (for nodes to the right), 6.2 (for nodes below), 6.1 (for nodes above not of type r) and 10.1 (to see that there are no type r nodes above), such a change in A can only happen at stage t. Thus we must have changed A and D at stage t below β since β was accessible.

We can change A and D in only three ways: diagonalization at a Ψ node, Plan S or Plan R. By Lemma 6.2 if we have applied diagonalization at a node below β, then it is the only change at stage t, so at stage s according to our construction we would want to apply Plan R to remove the element added into D at stage t [and restore the Θ computation]. Depending on the current stage announcement we would then have outcome either r or w. Since by assumption the outcome at s is g_{α_{j}}, we must have followed either Plan S or Plan R at t.

Now we can prove that Ψ requirements are not injured by Plan G.

Lemma 10.3. If σ is a Ψ node (Ψ(G) ≠ D) on the true path and we go to outcome d after stage s(σ), then the diagonalization will not be injured thereafter, i.e., the Ψ-use in G is preserved and the diagonalization witness x is not removed from D and so the Ψ requirement is satisfied.

Proof. Suppose at stage s > s(σ) we diagonalized at σ by putting x into D and so impose permanent restraint on D. First of all, x cannot be taken out of D at subsequent stages, since only nodes above σ could do so and then only if we follow either Plan S or Plan R at a node above σ. Plan S action would move us to the left for a contradiction and there are no outcomes r above σ by Lemma 10.1.

Next we claim that the G-use is also preserved. No node below or to the right of σ can add elements below this G-use into G after stage s, since their Δ-uses are defined to be fresh. The only worry is that some Θ node β with βˆ g_{α} above σ might follow Plan G (at stage s_{1} > s) to add δ(y) − 1 into G for some changed u in W in order to correct some Δ axiom. The Δ(G; u) axiom being killed must have been enumerated before stage s, since its use was chosen fresh. So W (u) = Φ(A; u) at stage s.

By Lemma 10.2, the only circumstances under which we change G at stage s_{1} in response to this change in W is that D has already changed by some other node τ below βˆ g_{α} following Plan S or Plan R at the previous stage t at which βˆ g_{α} was accessible. Such a τ cannot be above σ as we would then move to its left, so it must be to the right of, or below, σˆ d.

Then there must be another Ψ′ node σ′ (below τ) which added a number into D after stage s (since at stage s we initialized all nodes to the right of τ, any change before s cannot be used in shuffling or removal) and the number is taken out by τ. However, σ′ cannot be below, or to the right of, σ, as its witness would then be larger than s and so could not affect the value of W (u) which agrees with Φ(A; u) at stage s. So we get a contradiction.

In another words, once we apply diagonalization for σ, we (automatically) implement restraints for A and D and hence to W ’s up to the part that we have coded in. So we can guarantee that there can be no change in W which makes us change G on the uses we have already seen, and in particular, the Ψ-use of G is preserved.

11 Bibliography

Arslanov, M. M. [1985], Lattice properties of the degrees below 0′, Doklady Ak. Nauk SSR 283, 270-273.

Arslanov, M. M. [2009], Definability and elementary equivalence in the Ershov difference hierarchy in Logic Colloquium 2006, Lecture Notes in Logic, Association for Symbolic Logic and Cambridge University Press, New York, 1–17.

Arslanov, M. M. [2010], The Ershov hierarchy in Computability in Context: Computation and Logic in the Real World, Cooper, S. B. and Sorbi, A. eds., Imperial College Press, London.

Arslanov, M. M., Kalimullin, I. Sh. and Lempp, S. [2010], On Downey’s Conjecture, Journal of Symbolic Logic 75, 401-441.

Cooper, S. B. [1971], Degrees of Unsolvability, Ph.D. Thesis, Leicester University. Cooper, S. B. Harrington, L., Lachlan, A. H.. Lempp S. and Soare, R. I.[1991], The

d-r.e. degrees are not dense, Annals of Pure and Applied Logic 55, 125-151.

Downey, R. G. [1989], D-r.e. degrees and the non-diamond theorem, Bulletin London Mathematical Society 21, 43-50.

Epstein, R. L. [1979], Degrees of Unsolvability: Structure and Theory, LNM 759, Springer-Verlag, Berlin.

Ershov, Y. I. [1968], On a hierarchy of sets I, Algebra and Logic 7, 25-43.

Ershov, Y. I. [1968], On a hierarchy of sets II, Algebra and Logic 7, 212-232.

Ershov, Yu. I. [1970], On a hierarchy of sets III, Algebra and Logic 9, 20-31.

Gold, E. M. [1965], Limiting recursion, Journal of Symbolic Logic 30, 28-48.

Harrington, L. and Shelah, S. [1982], The undecidability of the recursively enumerable degrees (research announcement), Bulletin of the American Mathematical. Society, N.S. 6, 79-80.

Hodges, W. [1993], Model Theory, Cambridge University Press, Cambridge U.K. Jockusch, C. G. Jr. and Shore, R. A. [1984], Pseudo-jump operators II: transfinite

iterations, hierarchies and minimal covers, Journal of Symbolic Logic 49, 1205-1236.

Lachlan, A. H. [1966], Lower bounds for pairs of recursively enumerable degrees, Proceedings of the London Mathematical. Society (3) 16, 537-569.

Lachlan, A. H. [1968], Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grund. Math. 14, 457-472.

Lerman, M. [1983], Degrees of Unsolvability, Springer-Verlag, Berlin.

Nies, A., Shore, R. A. and Slaman, T. A. [1998], Interpretability and definability in the recursively enumerable degrees, Proceedings of the London Mathematical. Society (3) 77, 241-291.

Putnam, H. [1965], Trial and error predicates and the solution to a problem of Mostowski, Journal of Symbolic Logic 30, 44-50.

Sacks, G. E. [1966], Degrees of unsolvability, Annals of Math. Studies 55, Princeton University Press, 2^{nd} ed., Princeton NJ.

Shoenfield, J. R., [1959], On degrees of unsolvability, Annals of Mathematics 69, 644-653.

Shoenfield, J. R. [1965], An application of model theory to degrees of unsolvability, in Symposium on the Theory of Models, J. W. Addison, L. Henkin and A. Tarski eds., North-Holland, Amsterdam, 359-363.

Shore, R. A. [1981], The theory of the degrees below 0′, Journal of the London Mathematical Society 24, 1-14.

Shore, R. A. [1988], Defining jump classes in the degrees below 0′, Proceedings of the American Mathematical Society 104, 287-292.

Shore, R. A. [2006], Degree structures: Local and global investigations, Bulletin of Symbolic Logic 12, 369-389.

Shore, R. A. [2007], Direct and local definitions of the Turing jump, Journal of Mathematical Logic 7, 229-262.

Simpson, S. G. [1977], First order theory of the degrees of recursive unsolvability, Annals of Mathematics (2), 105, 121-139.

Slaman, T. A. [1983] The recursively enumerable degrees as a substructure of the Δ_{2}^{0} degrees, handwritten notes.

Slaman, T. A. [1991], Degree structures, in Proceedings Int. Cong. Math., Kyoto 1990, Springer-Verlag, Tokyo, 303-316.

Slaman, T. A. and Woodin, H. [2001], Definability in Degree Structures, preprint. Stephan, F. Yang, Y. and Yu, L. [2009], Turing degrees and the Ershov hierarchy

in Proceedings of the Tenth Asian Logic Conference, Kobe, Japan, 1-6 September 2008, World Scientific, 300-321.

Taitslin, M. A. [1962], Effective inseparability of the sets of identically true and finitely refutable formulas of elementary lattice theory, Algebra i Logika 3, 24-38.

Turing, A. M. [1939], Systems of logic based on ordinals, Proceedings of the London Mathematical. Society (3) 45, 161-228.

Yang, Y. and Yu, L. [2006], R is not a Σ_{1}-elementary substructure of D_{n}, Journal of Symbolic Logic 71, 1223–1236.

Yates, C. E. M. [1966], A minimal pair of recursively enumerable degrees, Journal of Symbolic Logic 31, 159-168.