Extensions of two constructions of Ahmad

Abstract

In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable $Σ_{2}^{0}$ -enumeration degrees $a_{0}$ and $a_{1}$ such that every enumeration degree $x < a_{0}$ is $⩽ a_{1}$ . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable $Σ_{2}^{0}$ -enumeration degrees $a_{0}$ and $a_{1}$ such that every enumeration degree $x_{0} < a_{0}$ is $⩽ a_{1}$ and such that every enumeration degree $x_{1} < a_{1}$ is $⩽ a_{0}$ .

In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no $Σ_{2}^{0}$ -enumeration degrees $a_{0}$ , $a_{1}$ and $a_{2}$ such that both $(a_{0}, a_{1})$ and $(a_{1}, a_{2})$ are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable $Σ_{2}^{0}$ -enumeration degrees $a_{0}$ , $a_{1}$ and $a_{2}$ such that every enumeration degree $x < a_{0}$ is also $⩽ a_{1}$ or $⩽ a_{2}$ ; however neither $(a_{0}, a_{1})$ nor $(a_{0}, a_{2})$ is an Ahmad pair.

Keywords

Enumeration degrees Ahmad pairs Ahmad triples

1. Introduction

Enumeration reducibility is a positive reducibility between sets of natural numbers. It arises naturally as a notion of relative computability for partial functions and has applications in effective mathematics, especially in computable topology, in computable model theory and in group theory.

We associate an algebraic presentation of this reducibility as a degree structure. The structure of the enumeration degrees is a partial order with least upper bound and a jump operator (just like its more famous cousin, the structure of the Turing degrees). In this article we focus on structural properties of its local substructure – the degree structure of the enumeration degrees of the $Σ_{2}^{0}$ -sets, which can be defined also as those enumeration degrees below the degree $0_{e}^{'}$ . Here, $0_{e}^{'}$ is the enumeration degree of the complement $\overline{K}$ of the halting problem $K = {e ∣ φ_{e} (e) ↓}$ . The $Σ_{2}^{0}$ -enumeration degrees can be viewed as the counterpart in enumeration reducibility of either the c.e. Turing degrees or the Turing degrees $⩽ 0^{'}$ , i.e., the $Δ_{2}^{0}$ -Turing degrees. Both analogies are imperfect, but reasonable in certain respects. We refer the reader to [14] for more information on current trends in research on the enumeration degrees.

One of the common questions about a degree structure viewed as a partial order is that of the complexity of its first-order theory. For most degree structures commonly being considered, the theory turns out to be as complicated as possible: global structures like the Turing degrees or the enumeration degrees have theories that are computably isomorphic to the theory of second-order arithmetic, while local structures usually have theories that are equivalent to the theory of first-order arithmetic. We then wonder about the fragments of the first-order theory, identified by restricting sentences to a certain quantifier complexity. We find that decidability breaks down at level 3, i.e., the $\exists \forall \exists$ -fragment is not decidable. On the other hand the ∃- and often even the $\forall \exists$ -fragment is decidable.

For the $Σ_{2}^{0}$ -enumeration degrees, the first of these questions has been completely settled: The full first-order theory was shown to be undecidable by Slaman and Woodin [13], and equivalent to full first-order arithmetic by Ganchev and Soskova [4].

As for the second question, the ∃-fragment is easily seen to be decidable, whereas Kent [5] showed the $\exists \forall \exists$ -fragment to be undecidable. The decidability of the $\forall \exists$ -fragment remains open.

The decidability of the $\forall \exists$ -fragment can be rephrased algebraically as (uniformly effectively) deciding the following

Question 1.1.
For any given finite partial orders $P$ and $Q_{i} \supseteq P$ (for $i ⩽ n$ ), can any embedding of $P$ into the $Σ_{2}^{0}$ -enumeration degrees be extended to an embedding of $Q_{i}$ for some $i ⩽ n$ (where i may depend on the particular embedding of $P$ )? (Without loss of generality, we will from now on assume that any finite partial order is bounded, i.e., has a least element 0 and a greatest element 1.)

Two major subproblems of Question 1.1 have been shown to be decidable:

Lempp, Slaman and Sorbi [8] showed that the above question is decidable for $n = 0$ , i.e., given any finite partial orders $P \subseteq Q$ , it is decidable whether any embedding of $P$ into the $Σ_{2}^{0}$ -enumeration degrees can be extended to an embedding of $Q$ .

Lempp and Sorbi [10] showed that all finite lattices can be embedded, even preserving 0 and 1. (The lattice embeddings question can be seen as a disjunction of extending embeddings to certain one-point extensions $Q_{i}$ of a finite lattice $P$ viewed as a partial order.)

As noted earlier, the $Σ_{2}^{0}$ -enumeration degrees are often compared to the c.e. Turing degrees. Both are dense structures with full first-order theories as complicated as the theory of first-order arithmetic. For the c.e. Turing degrees this was proved by Slaman and Woodin (unpublished, see Nies, Shore and Slaman [11]); for the c.e. Turing degrees we have that in addition the ∃-fragment is decidable, whereas Lempp, Nies and Slaman [7] showed the $\exists \forall \exists$ -fragment to be undecidable. However, the lattice embeddings problem for the c.e. Turing degrees remains one of the main open problems dating back to the 1960’s (see Lempp, Lerman and Solomon [6] for the most recent update), and thus the decidability of the $\forall \exists$ -theory of the c.e. Turing degrees remains wide open as well.

An important algebraic difference between the c.e. Turing degrees and the $Σ_{2}^{0}$ -enumeration degrees was discovered by Ahmad in her Ph.D. thesis [1] (see Ahmad and Lachlan [2, Corollary 3.2]): There are incomparable $Σ_{2}^{0}$ -enumeration degrees $a_{0}$ and $a_{1}$ (called an “Ahmad pair”) such that any degree $x < a_{0}$ is also $< a_{1}$ . (This makes $a_{0}$ “non-splitting”, i.e., join-irreducible, and thus cannot happen in the c.e. Turing degrees by the Sacks Splitting Theorem [12].) More interestingly even, Ahmad also showed (see Ahmad and Lachlan [2, Theorem 3.3]) that this phenomenon is not symmetric: For any two incomparable $Σ_{2}^{0}$ -enumeration degrees $a_{0}$ and $a_{1}$ , there is either a degree $x_{0} < a_{0}$ which is $≰ a_{1}$ , or there is a degree $x_{1} < a_{1}$ which is $≰ a_{0}$ .

In the language of Question 1.1, Ahmad’s results can be rephrased as stating that not every embedding of $P = {0, a_{0}, a_{1}, 1}$ with incomparable $a_{0}$ and $a_{1}$ can be extended to an embedding of $Q_{0} = {0, x_{0}, a_{0}, a_{1}, 1}$ where $0 < x_{0} < a_{0}$ and $x_{0} ≰ a_{1}$ , but that every embedding of $P$ can be extended to an embedding of either $Q_{0}$ or of $Q_{1} = {0, a_{0}, x_{1}, a_{1}, 1}$ where $0 < x_{1} < a_{1}$ and $x_{1} ≰ a_{0}$ .

In this paper, we prove two extensions of Ahmad’s results in different directions, thus adding to our toolbox toward our ultimate goal, deciding the $\forall \exists$ -theory of the $Σ_{2}^{0}$ -enumeration degrees. Again in the language of Question 1.1, our first result can be rephrased as stating that every embedding of $P = {0, a_{0}, a_{1}, a_{2}, 1}$ with incomparable $a_{0}$ , $a_{1}$ and $a_{2}$ can be extended to an embedding of $Q_{0} = {0, x_{0}, a_{0}, a_{1}, a_{2}, 1}$ where $0 < x_{0} < a_{0}$ and $x_{0} ≰ a_{1}$ or an embedding of $Q_{1} = {0, x_{1}, a_{0}, a_{1}, a_{2}, 1}$ where $0 < x_{1} < a_{1}$ and $x_{1} ≰ a_{2}$ (leaving the relationship between $x_{0}$ and $a_{2}$ , and between $x_{1}$ and $a_{0}$ , unspecified so as to not have too many cases); a similar formulation can be found for our second result.

We first present, in Section 2, a direct proof of Ahmad’s result that there is no symmetric Ahmad pair. (Currently, the only published proof in the literature is indirect and hard to modify.) In Section 3, we show that there is no Ahmad triple, i.e., there are no $Σ_{2}^{0}$ -degrees $a_{0}$ , $a_{1}$ and $a_{2}$ such that both $(a_{0}, a_{1})$ and $(a_{1}, a_{2})$ form an Ahmad pair. On the other hand, in Section 4, we also show that there is a weak Ahmad triple, i.e., there are pairwise incomparable $Δ_{2}^{0}$ -enumeration degrees $a_{0}$ , $a_{1}$ and $a_{2}$ such that every enumeration degree $x < a_{0}$ is also $⩽ a_{1}$ or $⩽ a_{2}$ ; however, neither $(a_{0}, a_{1})$ nor $(a_{0}, a_{2})$ forms an Ahmad pair. We should add here that Kent (personal communication around 2006) identified the existence of an Ahmad triple and of a “cupping Ahmad pair” (i.e., an Ahmad pair whose join is $0_{e}^{'}$ ) as the two main initial obstacles toward a decision procedure for the $\forall \exists$ -theory of the $Σ_{2}^{0}$ -enumeration degrees.

It is worth pointing out that the first two results are specific to the $Σ_{2}^{0}$ -enumeration degrees. Lempp, Slaman, and Soskova [9] have shown that every finite distributive lattice L can be embedded as an interval of $Π_{2}^{0}$ -enumeration degrees $[a, b]$ so that for every enumeration degree $x < b$ we have that $x \in [a, b]$ or $x < a$ . Embedding the diamond in such a way shows that symmetric Ahmad pairs are possible in general.
2. A direct proof that there is no symmetric Ahmad pair

In this section, we will present a direct proof of the following

Theorem 2.1 (Ahmad [1] (see Ahmad and Lachlan [2, Corollary 3.2])).

There is no symmetric Ahmad pair in the $Σ_{2}^{0}$ -enumeration degrees, i.e., there are no incomparable $Σ_{2}^{0}$ -degrees $a_{0}$ and $a_{1}$ such that every enumeration degree $x_{0} < a_{0}$ is $⩽ a_{1}$ , and every enumeration degree $x_{1} < a_{1}$ is $⩽ a_{0}$ .

To show that the degrees of a pair of sets $A_{0}$ and $A_{1}$ is not an Ahmad pair, we need to build a set $X_{0} <_{e} A_{0}$ such that $X_{0} ≰_{e} A_{1}$ . Cooper’s density proof [3] builds precisely such a set $X_{0}$ assuming that in addition $A_{1} <_{e} A_{0}$ . Under this additional assumption, we can build $X_{0} = Φ_{0} (A_{0})$ as follows: We satisfy two types of requirements. The first type ensures that for every e, we have $X_{0} \neq Γ_{e} (A_{1})$ by threatening to code $A_{0}$ into the e-th column of $X_{0}$ . The second type of requirement ensures that for every i, we have $A_{0} \neq Γ_{i} (X_{0})$ by threatening to make $Γ_{i} (X_{0}) = Γ_{i} (X_{0}^{[⩽ i]} \cup N^{[> i]})$ , which (assuming $X_{0}^{[⩽ i]}$ is computable) is a c.e. set. Here $X^{[⩽ n]} = {⟨ m, x ⟩ ∣ m ⩽ n}$ and $X^{[> n]} = {⟨ m, x ⟩ ∣ m > n}$ . To make this idea work, the construction uses a good approximation to the set $A_{0}$ , i.e., a uniformly computable sequence of finite sets ${A_{0, s}}_{s < ω}$ such that

for every n, there is a stage s such that $A_{0} ↾ n \subseteq A_{0, s} \subseteq A_{0}$ ; and

for every n, there is a stage s such that for every $t ⩾ s$ , if $A_{0, t} \subseteq A_{0}$ then $A_{0} ↾ n \subseteq A_{0, t}$ .

Stages at which

A_{0, s} \subseteq A_{0}

are called good. The sets reducible to

A_{0}

, namely,

X_{0}

A_{1}

Γ_{e} (A_{1})

, and

Γ_{i} (X_{0})

, are approximated with correct approximations – good approximations whose good stages include all good stages for the approximation of

A_{0}

. If we restrict our attention to good stages for

A_{0}

, then two sets with correct approximations are the same if and only the length of agreement between them measured at such stages is unbounded. So, if we enumerate elements into

X_{0, s}

only by enumerating axioms of the form

⟨ x, A_{0, s} ⟩

into

Φ_{0}

, then we ensure that

X_{0}

gains new elements only at good stages for

A_{0}

, and this allows us to limit the activity of each requirement to a finite set.

If $A_{1}$ is not bounded by $A_{0}$ , then this construction fails: It can be that there are infinitely many good stages for $A_{0}$ that are bad for $A_{1}$ , causing us to falsely assume that a requirement of the first type requires attention again and again and forcing it to contribute an infinite set to $X_{0}$ . This, in turn, is in critical conflict with the second type of requirements, which depend on the assumption that each column in $X_{0}$ is finite. The problem we see should not surprise us, because Ahmad pairs do exist. Ahmad’s original proof of Theorem 2.1 uses the Gutteridge operator to show that if $A_{0}$ and $A_{1}$ form an Ahmad pair, then $A_{0}$ and all sets bounded by $A_{0}$ have eventually correct approximations with respect to the approximation to $A_{1}$ , and so we can build $X_{1} <_{e} A_{1}$ with $X_{1} ≰_{e} A_{0}$ using essentially the same construction as the one described above. The proof is ingenious, though difficult to modify. We give a direct construction, using the priority method and a tree of strategies. The main idea is to build the sets $X_{0}$ and $X_{1}$ in a more entangled way so that our failure to prove that $X_{1} <_{e} A_{0}$ allows us to switch off unwanted axioms enumerated into $X_{0}$ and avoid the problem described above.

Assume that $A_{0}$ and $A_{1}$ are incomparable $Σ_{2}^{0}$ -sets. (If $A_{0}$ and $A_{1}$ are comparable, then their enumeration degrees do not form an Ahmad pair by definition.)

We fix approximations for $A_{0}$ and $A_{1}$ so that ${A_{0, s} \oplus A_{1, s}}_{s < ω}$ is a good approximation to $A_{0} \oplus A_{1}$ . So even though we cannot ensure that good stages for $A_{0}$ are good for $A_{1}$ or vice versa, we may at least ensure that there are infinitely many common good stages.

2.1. Requirements

The construction builds an enumeration operator $Φ_{1}$ , attempting to satisfy the following requirements for each enumeration operator $Γ_{1}$ and each enumeration operator $Δ_{1}$ : $\begin{array}{l} R_{Γ_{1}} : Φ_{1} (A_{1}) \neq Γ_{1} (A_{0}) \\ S_{Δ_{1}} : A_{1} \neq Δ_{1} (Φ_{1} (A_{1})) . \end{array}$

If some $R_{Γ_{1}}$ requirement fails then we will construct an enumeration operator $Φ_{0}$ satisfying the following subrequirements for each of the enumeration operators $Γ_{0}$ and $Δ_{0}$ : $\begin{array}{l} R_{Γ_{1}, Γ_{0}} : Φ_{0} (A_{0}) = Γ_{0} (A_{1}) ⟹ A_{0} = Ψ (A_{1}) (for a Ψ built by us) \\ S_{Γ_{1}, Δ_{0}} : A_{0} \neq Δ_{0} (Φ_{0} (A_{0})) . \end{array}$

Clearly, satisfying either group of requirements, namely, all $R_{Γ_{1}}$ - and all $S_{Δ_{1}}$ -requirements, or, for some fixed $Γ_{1}$ , all $R_{Γ_{1}, Γ_{0}}$ - and all $S_{Γ_{1}, Δ_{0}}$ -requirements, will suffice since $A_{0} ≰_{e} A_{1}$ .

We will denote $Φ_{i} (A_{i})$ by $X_{i}$ (for $i < 2$ ) whenever the operator $Φ_{i}$ is clear from the context.

2.2. Tree of strategies

Order each of the types of requirements and subrequirements in a priority of order type ω. We have four types of strategies: an $R_{Γ_{1}}$ -strategy α, an $R_{Γ_{1}, Γ_{0}}$ -strategy β, an $S_{Δ_{1}}$ -strategy γ, and an $S_{Γ_{1}, Δ_{0}}$ -strategy δ.

The root of the tree of strategies T is ∅, an $R_{Γ_{1}}$ -strategy working on the highest-priority $R_{Γ_{1}}$ -requirement. An $R_{Γ_{1}}$ -strategy has only one outcome $⟨ 0 ⟩$ and is immediately followed by an $R_{Γ_{1}, Γ_{0}}$ -strategy, working on the highest-priority $R_{Γ_{1}, Γ_{0}}$ -requirement.

An $R_{Γ_{1}, Γ_{0}}$ -strategy β has outcomes $⟨ 2 k ⟩$ , $⟨ 2 k + 1, old ⟩$ , $⟨ 2 k + 1, off ⟩$ , and $⟨ 2 k + 1, new ⟩$ for all $k \in ω$ , ordered as follows: $\begin{matrix} ⟨ 0 ⟩ <_{L} ⟨ 1, old ⟩ <_{L} ⟨ 1, off ⟩ <_{L} ⟨ 1, new ⟩ <_{L} ⟨ 2 ⟩ <_{L} \dots \end{matrix}$ For every $k < ω$ , the nodes $β \hat{} ⟨ 2 k ⟩$ and $β \hat{} ⟨ 2 k + 1, off ⟩$ are $S_{Γ_{1}, Δ_{0}}$ -strategies working on the highest-priority $S_{Γ_{1}, Δ_{0}}$ -requirement that is not assigned to any of β’s predecessors. The nodes $β \hat{} ⟨ 2 k + 1, old ⟩$ and $β \hat{} ⟨ 2 k + 1, new ⟩$ are $S_{Δ_{1}}$ -strategies working on the highest-priority $S_{Δ_{1}}$ -requirement that is not assigned to any of β’s predecessors.

An $S_{Δ_{1}}$ -strategy γ has outcomes $⟨ k ⟩$ , where $k \in ω$ is ordered by the standard ordering on ω. Each such immediate successor of this strategy is a main $R_{Γ_{1}}$ -strategy, working on the highest-priority $R_{Γ_{1}}$ -requirement that is not assigned to any of its predecessors.

Similarly, an $S_{Γ_{1}, Δ_{0}}$ -strategy δ has outcomes $⟨ k ⟩$ , where $k \in ω$ is ordered by the standard ordering on ω. Each such immediate successor of this strategy is an $R_{Γ_{1}, Γ_{0}}$ -strategy, working on the highest-priority $R_{Γ_{1}, Γ_{0}}$ -requirement (for the same $Γ_{1}$ as δ) that is not assigned to any of its predecessors.

2.3. Construction

At stage 0, all strategies are in initial state: All operators associated with these strategies are empty, all parameters are undefined. At stage $s > 0$ , we build a path $f_{s}$ of length $⩽ s$ . The intention is that there will be a true path defined by $\begin{matrix} f (n) = \underset{f_{s} ⪰ f ↾ n}{lim inf} f_{s} (n) \end{matrix}$ that correctly describes the outcomes of each strategy. The construction consists of substages t for $t < s$ , where we act for some strategy $f_{s} ↾ t$ of length t depending on the current outcome of the strategy which acted at the previous substage starting at the root. When a strategy is activated at stage s, it first ensures that it is not missing any good stages by adjusting the approximations to $A_{0}$ and $A_{1}$ : If $s^{-}$ is the previous stage at which this strategy was active, then it replaces $A_{i, s}$ by $⋂_{u \in [s^{-}, s]} A_{i, u}$ for $i < 2$ . We describe further actions of each strategy depending on its type below.

At the end of stage s, we initialize all strategies of lower priority than $f_{s}$ , i.e., strategies extending or to the right of the strategies which acted at stage s.

Each $R_{Γ_{1}, Γ_{0}}$ -strategy β and each $S_{Γ_{1}, Δ_{0}}$ -strategy δ works with the version of $Φ_{0}$ and $X_{0}$ determined by the longest $R_{Γ_{1}}$ -strategy $α ≺ β$ , δ (we say that β and δ work for α); this version of $Φ_{0}$ is the set of $Φ_{0}$ -axioms enumerated by all the $R_{Γ_{1}, Γ_{0}}$ - and $S_{Γ_{1}, Δ_{0}}$ -strategies working for the same $R_{Γ_{1}}$ -strategy α.

2.3.1. $S_{Δ_{1}}$

We begin with the $S$ -strategies, as they are directly lifted from the density construction. So, let γ be an $S_{Δ_{1}}$ -strategy. The first time a strategy is visited after initialization, the strategy receives a unique number $s_{γ}$ , the stage of first visit after initialization. To keep this assignment of stages injective, we interrupt the stage s construction if s is the first stage when γ is visited: We set $f_{s} = γ$ , $s_{γ} = s$ , and move on to stage $s + 1$ . If $s_{γ} < s$ is already defined, then we consider the length $l_{γ, s} < s$ of the common initial segment of $A_{1, s}$ and $Δ_{1, s} (X_{1, s})$ up to s. For every number $n ⩽ l_{γ, s}$ , if $n \in Δ_{1, s} (X_{1, s}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ , we search for the axiom $⟨ n, F ⟩ \in Δ_{1}$ that has been valid the longest and enumerate each element of the form $⟨ r, x ⟩ \in F$ , where $r ⩾ s_{γ}$ into the set $X_{1, s}$ via the axiom $⟨ ⟨ r, x ⟩, A_{1, s} ⟩$ . The outcome of the strategy is $⟨ k ⟩$ , where k is the standard code of the finite set $D_{k}$ of all numbers for which γ has enumerated an axiom that looks valid at stage s. The only thing we assume about the coding of finite sets, in addition to its effective properties, is that $D_{k_{1}} \subseteq D_{k_{2}}$ implies $k_{1} ⩽ k_{2}$ .

We will be able to argue that if γ is on the true path, then γ enumerates only a finite set D into $X_{1}$ , as the sequence ${l_{γ, s}}_{s is good}$ must be bounded. At sufficiently large stages in the approximation to $A_{1}$ , the outcome we select will always correspond to a superset of D. At stages that are also good (i.e., stages s such that $A_{1, s} \subseteq A_{1}$ ), we will be able to correctly identify the code of D as the correct outcome. In other words, the code of the set D will be γ’s true outcome.

2.3.2. $S_{Γ_{1}, Δ_{0}}$

An $S_{Γ_{1}, Δ_{0}}$ -strategy δ works similarly to the $S_{Δ_{1}}$ -strategy. It also receives a unique number $s_{δ}$ , the stage of first visit after initialization, and interrupts the stage s construction if s is the first stage when δ is visited. Otherwise, we consider the length $l_{δ, s} < s$ of the common initial segment of $A_{0, s}$ and $Δ_{0, s} (X_{0, s})$ up to s. For every number $n ⩽ l_{δ, s}$ , if $n \in Δ_{0, s} (X_{0, s}^{[< s_{δ}]} \cup N^{[⩾ s_{δ}]})$ , we search for the axiom $⟨ n, F ⟩ \in Δ_{0}$ that has been valid the longest and enumerate each element of the form $⟨ r, x ⟩ \in F$ , where $r ⩾ s_{δ}$ is in the set $X_{0, s}$ via the axiom $⟨ ⟨ r, x ⟩, A_{0, s} ⟩$ . The outcome of the strategy is $⟨ k ⟩$ , where k is the standard code of the finite set $D_{k}$ of all numbers for which δ has enumerated an axiom that looks valid at stage s.

2.3.3. $R_{Γ_{1}}$

The $R_{Γ_{1}}$ -strategy does nothing, has only one outcome $⟨ 0 ⟩$ , and determines the version of $Φ_{0}$ and $X_{0}$ that all the $R_{Γ_{1}, Γ_{0}}$ - and $S_{Γ_{1}, Δ_{0}}$ -strategies working for the $R_{Γ_{1}}$ -strategy use.

2.3.4. $R_{Γ_{1}, Γ_{0}}$

The $R_{Γ_{1}, Γ_{0}}$ -strategy β attempts to construct an enumeration operator Ψ such that $A_{0} = Ψ (A_{1})$ by enumerating axioms into $Φ_{1}$ and its version of $Φ_{0}$ .

At the first stage after initialization, the $R_{Γ_{1}, Γ_{0}}$ -strategy β is assigned the parameter $s_{β}$ . Note that we can assume that $s_{β}$ is larger than $max (D_{k})$ for any k such that a higher-priority $S$ -strategy λ (which can be either an $S_{Δ_{1}}$ - or an $S_{Γ_{1}, Δ_{0}}$ -strategy) has $λ \hat{} k ⪯ β$ . Until its next initialization, β will only contribute numbers to the $s_{β}$ -th columns of $X_{0}$ and $X_{1}$ . To every element a, we assign the coding location $x_{a} = ⟨ s_{β}, a ⟩$ targeted for $X_{0}$ . The coding locations $m_{a}$ that we associate with a given number a but are targeted for $X_{1}$ will change more dynamically during the construction. Initially, we assign $m_{a} = ⟨ s_{β}, a ⟩$ as well.

At a stage $s > s_{β}$ , β does the following. It orders the elements of $A_{0, s} \cup Ψ_{s} (A_{1, s})$ by age: For each $a \in A_{0, s} \cup Ψ_{s} (A_{1, s})$ , we define its age (at stage s) as follows. $\begin{array}{l} {age}_{0}^{s} (a) = 2 k + 1 for k = min (s + 1, μ t \forall u \in [t, s] (a \in A_{0, u})) \\ {age}_{1}^{s} (a) = 2 k for k = min (s + 1, μ t \forall u \in [t, s] (a \in Ψ (A_{1, u}) [u] via the same axiom)) \\ {age}^{s} (a) = min {{age}_{0}^{s} (a), {age}_{1}^{s} (a)} . \end{array}$

Without loss of generality, we will assume that at most one element enters the approximation to $A_{0}$ or $Ψ (A_{1})$ at a fixed stage s. (We can ensure this by artificially delaying the approximations if necessary.) And so, for every stage $t ⩽ s$ , there may be at most one element with ${age}^{s} (a) = t$ . Furthermore, if $a \in A_{0, s} ∖ Ψ_{s} (A_{1, s})$ , then ${age}^{s} (a)$ is odd, and if $a \in Ψ_{s} (A_{1, s}) ∖ A_{0, s}$ , then ${age}^{s} (a)$ is even. At stage s, we will say that b is older than a if ${age}^{s} (b) < {age}^{s} (a)$ .

If $A_{0, s} = Ψ_{s} (A_{1, s})$ , then we exit this strategy with outcome $⟨ 2 (s + 1) ⟩$ (this is an outcome that has not been visited so far). Since $A_{0}$ is infinite, this will only be a temporary situation. Otherwise, we pick the oldest number a such that $A_{0, s} (a) \neq Ψ_{s} (A_{1, s}) (a)$ . Let $k = {age}^{s} (a)$ . We must ensure that β’s effect on $X_{1}$ is computable, and so the strategy will dump into $X_{1}$ all elements of the form $⟨ s_{β}, n ⟩ \in (m_{a}, s]$ and assign new markers $m_{a^{'}} = ⟨ s_{β}, n ⟩ > s$ to all elements $a^{'}$ with ${age}^{s} (a^{'}) > k$ . (Here, to dump an element m into $X_{1}$ means to enumerate the axiom $⟨ m, \emptyset ⟩$ into $Φ_{1}$ .) We have two cases depending on the parity of k.

Case 1: If k is even, i.e., if $a \in Ψ_{s} (A_{1, s}) ∖ A_{0, s}$ , then we will be able to argue that $x_{a} = ⟨ s_{β}, a ⟩ \in Γ_{0} (A_{1}) ∖ X_{0}$ . The strategy selects outcome $⟨ k ⟩$ . While a maintains its age, we will design axioms for younger elements enumerated into $X_{0}$ by β so that their use includes a. Thus, if this is β’s true outcome, they will be invalid and hence β contributes finitely much to $X_{0}$ .

Case 2: If k is odd, i.e., if $a \in A_{0, s} ∖ Ψ_{s} (A_{1, s})$ , then we would like to add an axiom for a into Ψ, but to do this we need some preparation. We will identify an axiom $⟨ x_{a}, F_{a} ⟩$ in $Γ_{0} (A_{1})$ and use it. Let $s_{k}$ be the previous stage when β considered k:

If some b with ${age}^{s} (b) < k$ has $m_{b} \notin Γ_{1} (A_{0, t})$ at some stage $t \in [s_{k}, s]$ , then, since b is older than a, we may assume that we have identified $F_{b}$ for b and that $F_{b} \subseteq A_{1, s}$ . (Otherwise, b would be our choice for the oldest disagreement.) We can therefore enumerate the axiom $⟨ m_{b}, F_{b} ⟩ \in Φ_{1}$ so that $m_{b} \in X_{1, s} ∖ Γ_{1} (A_{0, s})$ . The outcome is $⟨ k, old ⟩$ . If this is the true outcome, then we do not care what happens to $X_{0}$ as strategies below this outcome will be working with new versions of this set.

Otherwise, for every b with ${age}^{s} (b) < k$ , we can associate a set $G_{b}$ , the use of the oldest valid axiom for $m_{b}$ in the set $Γ_{1}$ . We enumerate into $Φ_{0, s}$ the axiom $\begin{matrix} ⟨ x_{a}, ⋃_{{age}^{s} (b) < k} G_{b} \cup {b ∣ {age}^{s} (b) ⩽ k} ⟩ . \end{matrix}$ Next, we check whether $x_{a} \in Γ_{0} (A_{1})$ . If $x_{a} \notin Γ_{0} (A_{1, s})$ , then we have evidence that this requirement may be satisfied by $x_{a} \in X_{0} ∖ Γ_{0} (A_{1})$ . Unfortunately, we have no evidence that the effect of β on $X_{0}$ is finite, so we use the marker $m_{a}$ . We will always only enumerate axioms of the form $⟨ m_{a}, F_{a} ⟩$ into $Φ_{1}$ , where $F_{a}$ is the use of a $Γ_{0}$ -axiom for $x_{a}$ . The case we are in suggests that $m_{a} \notin X_{1}$ .

If $m_{a} \notin Γ_{1} (A_{0, t})$ at some stage $t \in [s_{k}, s]$ , then we can guarantee that under this outcome, β’s effect on $X_{0}$ is finite. This is because we include the use of a $Γ_{1}$ -axiom for $m_{a}$ in the use of every axiom we enumerate into $Φ_{0}$ for numbers $a^{'}$ with age larger than k. (This is true as long as a maintains its age.) We set the outcome to be $⟨ k, off ⟩$ .

Otherwise, $m_{a} \in Γ_{1} (A_{0, t})$ at all stages $t \in [s_{k}, s]$ , so we have evidence that $m_{a} \in Γ_{1} (A_{0}) ∖ X_{1}$ . We end with outcome $⟨ k, new ⟩$ and let strategies below forget about this version of $X_{0}$ .

Finally, if $x_{a} \in Γ_{0} (A_{1, t})$ at all stages $t \in [s_{k}, s]$ (by the same axiom at all stages since the last visit), then let $⟨ x_{a}, F_{a} ⟩ \in Γ_{0}$ be the axiom that has been valid the longest. Enumerate $⟨ a, F_{a} ⟩$ into $Ψ_{s}$ . We have eliminated a as a difference, and so we may proceed to pick the oldest difference once again.

2.4. Verification

We define the true path f in the tree of strategies as the leftmost path of strategies visited infinitely often. If $λ \hat{} o ≺ f$ , then we will say that λ has true outcome o. If s is a stage at which λ is visited, then we say that s is λ-true. We need to prove that f is well defined and strategies along it satisfy their requirements. We do so by showing the following properties of the construction by simultaneous induction.

Lemma 2.2.
The true path f is infinite, furthermore:
If β is an $R_{Γ_{1}, Γ_{0}}$ -strategy and $β ⪯ f$ , then:

There is a leftmost outcome o that β visits at infinitely many stages.

There are finitely many values of the parameter $s_{β}$ , and for each such value, $X_{1}^{[s_{β}]}$ is a computable set.

If $o \in {⟨ 2 k ⟩, ⟨ 2 k + 1, off ⟩ ∣ k \in ω}$ , then $R_{Γ_{1}, Γ_{0}}$ is satisfied, and for every value of $s_{β}$ , the set $X_{0}^{[s_{β}]}$ is finite.

If $o \in {⟨ 2 k + 1, old ⟩, ⟨ 2 k + 1, new ⟩ ∣ k \in ω}$ , then $R_{Γ_{1}}$ is satisfied.

If γ is an $S_{Δ_{1}}$ -strategy and $γ ⪯ f$ , then:

There is a leftmost outcome o that γ visits at infinitely many stages.

The set $D_{o}$ consists of all numbers that γ contributes to $X_{1}$ .

The requirement $S_{Δ_{1}}$ is satisfied.

If δ is an $S_{Γ_{1}, Δ_{0}}$ -strategy and $δ ⪯ f$ , then:

There is a leftmost outcome o that δ visits at infinitely many stages.

The set $D_{o}$ consists of all numbers that γ contributes to $X_{0}$ .

The requirement $S_{Γ_{1}, Δ_{0}}$ is satisfied.

Proof.
We will prove the statements above in turn, assuming that all statements are true for higher-priority strategies along the true path. We first note that $R_{Γ_{1}}$ -strategies along the true path have only one possible outcome, visited at every true stage, hence cannot cause f to be finite.

A. Let $β ⪯ f$ be an $R_{Γ_{1}, Γ_{0}}$ -strategy. It follows from the definition of the true path that β is visited at infinitely many stages and initialized finitely often. There is a stage at which β is first visited after its last initialization. At this stage, $s_{β}$ receives its final value, and by construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. By construction, no strategy has so far enumerated any element into the $s_{β}$ -th column of $X_{0}$ or $X_{1}$ : Lower-priority strategies σ are initialized at stage $s_{β}$ , so their parameter $s_{σ}$ (if defined) will have higher value than $s_{β}$ . Higher-priority strategies λ will not add elements to the $s_{β}$ -th column of $X_{0}$ or $X_{1}$ , either. To see this, note that they are either not visited at further stages, hence do not act any longer; they are $R_{Γ_{1}, Γ_{0}}$ -strategies with $s_{λ} < s_{β}$ and hence enumerate elements into smaller columns of $X_{0}$ or $X_{1}$ ; or they are $S$ -strategies whose true outcome is extended by β and hence by B(2) and C(2), they will not enumerate any more valid axioms into either operator $Φ_{0}$ or $Φ_{1}$ . Thus β is the unique strategy that adds elements into the $s_{β}$ -th column of $X_{0}$ or $X_{1}$ . If $t < s_{β}$ is a previous value of the parameter $s_{β}$ , then our analysis shows that no strategy can add valid axioms for numbers in the t-th columns of $X_{0}$ and $X_{1}$ after stage $s_{β}$ .

Let $Ψ = ⋃ Ψ_{s}$ be the enumeration operator constructed by β. By assumption, $A_{0} ≰_{e} A_{1}$ , hence $Ψ (A_{1}) \neq A_{0}$ . Let a be the oldest disagreement, where the age of the disagreement is defined as in the construction. This means that there is some stage $s_{a}$ such that at all stages $t > s_{a}$ , we have that if ${age}^{t} (b) < {age}^{t} (a)$ , then $b \in A_{0, t} \cap Ψ (A_{1, t})$ with a fixed marker $m_{b}$ . The age c of a remains constant, and at stages $t > s_{a}$ , the strategy β will not visit any outcome left of the c-outcomes (which depend on the parity of c), so the marker $m_{a}$ will remain fixed. Furthermore, the way β adjusts the approximation to $A_{0}$ and $A_{1}$ when visited ensures that there are infinitely many stages $t > s_{a}$ at which we visit β, and a is the oldest disagreement at stage t. At such stages, β will visit a c-outcome, and since there are finitely many c-outcomes (only one c-outcome $⟨ c ⟩$ if c is even, and three c-outcomes $⟨ c, old ⟩$ , $⟨ c, off ⟩$ , and $⟨ c, new ⟩$ if c is odd), there is a leftmost outcome visited at infinitely many stages, proving $(1)$ . Note that if β reaches Case 2.3 infinitely often, then β also ends in Case 2.2 infinitely often because if t is such that $a \notin Ψ (A_{1, t})$ , but $a \in Ψ (A_{1, t^{-}})$ , where $t^{-}$ is the previous β-true stage, then our convention ensures that $x_{a} \notin Γ_{0} (A_{1, t})$ . All numbers greater than $m_{a}$ in the $s_{β}$ -th column of $X_{1}$ will be dumped into $X_{1}$ , hence the $s_{β}$ -th column of $X_{1}$ is cofinite, proving $(2)$ .

If $a \notin A_{0}$ , then the age of a after stage $s_{a}$ is $c = 2 k$ , where k is the stage such that at all $t ⩾ k$ , we have that $a \in Ψ (A_{1, t})$ via the same axiom $⟨ a, F_{a} ⟩$ , say. As we argued above, $⟨ 2 k ⟩$ is β’s true outcome. We prove that $x_{a} \in Γ_{0} (A_{1}) ∖ X_{0}$ : That $x_{a} \notin X_{0}$ is clear, as by construction, any axiom that β enumerates into $Φ_{0}$ for $x_{a}$ contains a in its use, and as we already argued, no other strategy enumerates valid axioms for $x_{a} = ⟨ s_{β}, a ⟩$ . On the other hand, β enumerated the valid axiom $⟨ a, F_{a} ⟩$ into Ψ because it saw that $⟨ x_{a}, F_{a} ⟩ \in Γ_{0}$ , and since $F_{a} \subseteq A_{1}$ , it follows that $x_{a} \in Γ_{0} (A_{1})$ . Up until stage $s_{a}$ , there are only finitely many axioms enumerated into $Φ_{0}$ by β. After stage $s_{a}$ , any axiom enumerated by β into $Φ_{0}$ will include a in its use because the age of a remains constant. It follows that all such axioms are invalid, and so β contributes a finite set to $X_{0}^{[s_{β}]}$ .

Suppose $a \in A_{0}$ . Then $c = 2 k + 1$ , and we have several cases, depending on the leftmost outcome visited infinitely often. If this is $⟨ 2 k + 1, old ⟩$ , then infinitely often after stage $s_{a}$ , we visit β, and it stops at Case 2.1 of the construction, because some b with ${age}^{s} (b) < k$ has $m_{b} \notin Γ_{1} (A_{0, t})$ at some stage t since we last considered a. There are finitely many such b, and hence the described scenario happens infinitely often with some fixed such b. As pointed out in the construction, since b is older than a, we know that $b \in Ψ (A_{1, t})$ at such stages via the same axiom $⟨ b, F_{b} ⟩$ , and so the construction ensures that $m_{b} \in X_{1}$ using this axiom. It follows that $m_{b} \in X_{1} ∖ Γ_{1} (A_{0})$ .

Otherwise, there is a stage $s_{b} > s_{a}$ such that at all β-true stages $t > s_{b}$ at which a is the oldest disagreement, Case 2.1 does not apply. This means that for every older b, there is a fixed valid axiom $⟨ m_{b}, G_{b} ⟩ \in Γ_{1}$ . This means that the axiom that we enumerate into $Φ_{0}$ for $x_{a}$ is valid, and so $x_{a} \in X_{0}$ . On the other hand, since infinitely often we are in Case 2.2, $x_{a} \notin Γ_{0} (A_{1})$ , and so $R_{Γ_{0}, Γ_{1}}$ is satisfied.

If β’s true outcome is $⟨ 2 k + 1, off ⟩$ , then $m_{a} \notin Γ_{1} (A_{0})$ . In this case, we already know that $R_{Γ_{0}, Γ_{1}}$ is satisfied. After stage $s_{b}$ , any axiom enumerated by β into $Φ_{0}$ will include some $G_{a}$ in its use, where $⟨ m_{a}, G_{a} ⟩ \in Γ_{1}$ . It follows that all such axioms are invalid, and so β contributes a finite set to $X_{0}^{[s_{β}]}$ . This ensures that (3) is true.

Otherwise, there is a stage $s_{c} > s_{b}$ after which Case 2.2.a does not apply. The true outcome is $⟨ 2 k + 1, new ⟩$ , and $m_{a} \in Γ_{1} (A_{0, t})$ at all stages $t > s_{c}$ by the same axiom. It follows that $m_{a} \in Γ_{1} (A_{0})$ . To complete the proof, we will show that $m_{a} \notin X_{1}$ . Any $Φ_{1}$ -axiom enumerated for $m_{a}$ has the form $⟨ m_{a}, F_{a} ⟩$ . Such an axiom can only be enumerated after the axiom $⟨ a, F_{a} ⟩$ is enumerated into Ψ. Since $a \notin Ψ (A_{1})$ , it follows that $m_{a} \notin X_{1}$ . We conclude that $R_{Γ_{1}}$ is satisfied, proving $(4)$ .

B. Let $γ ⪯ f$ be an $S_{Δ_{1}}$ -strategy. It follows from the definition of the true path that γ is visited at infinitely many stages and initialized finitely often. There is a first stage at which γ is visited after its last initialization. This is the stage at which $s_{γ}$ receives its final value, and by construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. Lower-priority strategies σ have $s_{σ} > s_{γ}$ . Higher-priority strategies are the only ones that can enumerate elements into $X_{1}^{[< s_{γ}]}$ , so by induction, $X_{1}^{[< s_{γ}]}$ is a computable set. If s is a good stage in the approximation to $A_{1}$ , then $A_{1, s} \subseteq A_{1}$ and $Δ_{1} (X_{1, s}) \subseteq Δ_{1} (X_{1})$ . Suppose that ${l_{γ, s}}_{A_{1, s} \subseteq A_{1}}$ is unbounded. Then we can argue that $A_{1} = Δ_{1} (X_{1})$ : If $a \in A_{1}$ , then pick a good stage s at which $a \in A_{1, s}$ and $l_{γ, s} > a$ . It follows that $a \in Δ_{1} (X_{1, s}) \subseteq Δ_{1} (X_{1})$ . Similarly, if $a \in Δ_{1} (X_{1})$ , then we can pick a good stage s at which $a \in Δ_{1} (X_{1, s})$ and $l_{γ, s} > a$ . It follows that $a \in A_{1, s} \subseteq A_{1}$ .

Furthermore, if ${l_{γ, s}}_{A_{1, s} \subseteq A_{1}}$ is unbounded then we can also argue that $Δ_{1} (X_{1}) = Δ_{1} (X_{1}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ . One inclusion follows from the fact that $X_{1} \subseteq X_{1}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]}$ . For the reverse inclusion, fix $n \in Δ_{1} (X_{1}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ . Let $⟨ n, F ⟩$ be the oldest valid axiom. (Note that the age of this axiom depends only on $X_{1}^{[< s_{γ}]}$ .) Pick a good stage $s > s_{γ}$ that is greater than the age of this axiom and at which $l_{γ, s} > n$ . At this stage, we enumerate all $⟨ r, x ⟩ \in F$ , where $r ⩾ s_{γ}$ , into the set $X_{1, s}$ via the axiom $⟨ ⟨ r, x ⟩, A_{1, s} ⟩$ . Since s is good, these are valid axioms, and hence $n \in Δ_{1} (X_{1})$ . It follows that $A_{1} = Δ_{1} (X_{1}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ , contradicting the fact that $A_{1}$ is not c.e. (otherwise it would be comparable with $A_{0}$ ).

Thus $l_{γ, s}$ is bounded by some number $l_{γ}$ , say, at all good stages in the construction. At good stages, the strategy γ enumerates axioms only in response to finitely many n. For each such n, we know by the fact that we are looking at a good stage that $n \in Δ_{1} (A_{1})$ . Eventually, the oldest valid axiom will emerge, and so γ will keep selecting the same axiom $⟨ n, F ⟩$ for this element, and thus ultimately γ will enumerate only finitely many elements into $X_{1}$ , and all these elements will be enumerated at good stages. Let $D = D_{k}$ be the set of these elements. Let $s_{k}$ be a stage such that at all $t ⩾ s_{k}$ , we have that $D \subseteq X_{1}$ . At all γ-true stages $t ⩾ s_{k}$ , the strategy γ will have outcome $⟨ m ⟩$ , where $D_{k} \subseteq D_{m}$ . By our choice of coding, we have that $⟨ k ⟩ ⩽ ⟨ m ⟩$ . By the adjustment that γ makes to the approximation of $A_{1}$ , we know that γ is visited at infinitely many good stages for the approximation to $A_{1}$ . At such stages, γ will have outcome $⟨ k ⟩$ . This proves (1) and (2).

To see that the requirement is satisfied, we prove that there is some element $n ⩽ l_{γ}$ such that $A_{1} (n) \neq Δ_{1} (X_{1}) (n)$ . Assume that this is not the case. Pick a stage s such that all elements $n ⩽ l_{γ}$ that are in $A_{1}$ are in $A_{1, s}$ and s is good. There are infinitely many such stages, and we visit γ at such stages. At such a γ-true stage t, we have that $l_{γ, t} > l_{γ}$ , contradicting our choice of $l_{γ}$ .

C. The case where $δ ⪯ f$ is an $S_{Γ_{1}, Δ_{0}}$ -strategy is proved similarly to Case B. □
Lemma 2.3.
Either all requirements $R_{Γ_{1}}$ and $S_{Δ_{1}}$ are satisfied, or there is some requirement $R_{Γ_{1}}$ such that all requirements $R_{Γ_{1}, Γ_{0}}$ and $S_{Γ_{1}, Δ_{0}}$ are satisfied.
Proof.
If there are infinitely many $R_{Γ_{1}}$ -strategies along the true path f, then by the construction of the tree, it follows that there are infinitely many $S_{Δ_{1}}$ -requirements assigned to nodes on the true path, as only such strategies have immediate successors that are $R_{Γ_{1}}$ -strategies. Thus all $S_{Δ_{1}}$ -requirements are assigned to nodes on the true path and hence by Lemma 2.2 are satisfied. Consider any $R_{Γ_{1}}$ -strategy $α ≺ f$ . Let $γ ≺ f$ be the next $S_{Δ_{1}}$ -strategy along the true path. By the construction of the tree, γ’s immediate predecessor is an $R_{Γ_{1}, Γ_{0}}$ -strategy β with true outcome $⟨ 2 k + 1, old ⟩$ or $⟨ 2 k + 1, new ⟩$ for some k. It follows from Lemma 2.2 that $R_{Γ_{1}}$ is satisfied, thus all requirements $R_{Γ_{1}}$ are satisfied.

If there are finitely many $R_{Γ_{1}}$ -strategies along f, then fix the longest such α. Every immediate successor of α along the true path is either an $R_{Γ_{1}, Γ_{0}}$ -strategy with true outcome $⟨ 2 k ⟩$ or $⟨ 2 k + 1, off ⟩$ or an $S_{Γ_{1}, Δ_{0}}$ -strategy. Hence there are infinitely many of each, and by Lemma 2.2, they are all successful. By the design of the tree, it follows that all requirements $R_{Γ_{1}, Γ_{0}}$ and $S_{Γ_{1}, Δ_{0}}$ are satisfied. □

3. No Ahmad triple

In this section, we extend the ideas introduced in the previous section to prove our main result:

Theorem 3.1.
There is no Ahmad triple in the $Σ_{2}^{0}$ -enumeration degrees, i.e., there are no $Σ_{2}^{0}$ -degrees $a_{0}$ , $a_{1}$ , and $a_{2}$ such that $a_{0} ≰ a_{1}$ but every enumeration degree $x_{0} < a_{0}$ is $⩽ a_{1}$ , and such that $a_{1} ≰ a_{2}$ but every enumeration degree $x_{1} < a_{1}$ is $⩽ a_{2}$ .

3.1. Requirements

Suppose $A_{0}$ , $A_{1}$ and $A_{2}$ are $Σ_{2}^{0}$ -sets. The construction builds an enumeration operator $Φ_{0}$ , attempting to satisfy the following requirements for each of the enumeration operators $Γ_{0}$ and $Δ_{0}$ : $\begin{array}{l} R_{Γ_{0}} : Φ_{0} (A_{0}) \neq Γ_{0} (A_{1}), \\ S_{Δ_{0}} : A_{0} \neq Δ_{0} (Φ_{0} (A_{0})) . \end{array}$

If some $R_{Γ_{0}}$ -requirement fails, then we will construct an enumeration operator $Φ_{1}$ satisfying the following subrequirements for each of the enumeration operators $Γ_{1}$ and $Δ_{1}$ : $\begin{array}{l} R_{Γ_{0}, Γ_{1}} : Φ_{1} (A_{1}) \neq Γ_{1} (A_{2}) \\ S_{Γ_{0}, Δ_{1}} : A_{1} \neq Δ_{1} (Φ_{1} (A_{1})) . \end{array}$

If some $R_{Γ_{0}, Γ_{1}}$ -requirement fails, then we will construct an enumeration operator $Φ_{2}$ satisfying the following subsubrequirements for each of the enumeration operators $Γ_{2}$ and $Δ_{2}$ : $\begin{array}{l} R_{Γ_{0}, Γ_{1}, Γ_{2}} : Φ_{2} (A_{0}) = Γ_{2} (A_{1}) ⟹ A_{0} = Ψ_{0} (A_{1}) or A_{1} = Ψ_{1} (A_{2}) \\ (for Ψ_{0} and Ψ_{1} built by us) \\ S_{Γ_{0}, Γ_{1}, Δ_{2}} : A_{0} \neq Δ_{2} (Φ_{2} (A_{0})) . \end{array}$

We will denote $Φ_{0} (A_{0})$ by $X_{0}$ , $Φ_{1} (A_{1})$ by $X_{1}$ , and $Φ_{2} (A_{0})$ by $X_{2}$ whenever the operator $Φ_{i}$ is clear from the context.

3.2. Overview

We first give a high-level overview of how the overall construction works, without going into the specifics of the priority tree layout and the arrangement of different outcomes. At each node α of the priority tree, there will be an active version of $X_{1}$ and $X_{2}$ (where $X_{0}$ is, of course, maintained globally). Each version of $X_{1}$ and $X_{2}$ is built in some cone; $X_{1}$ is built in a cone with an $R_{Γ_{0}}$ -requirement at the top of the cone, while $X_{2}$ is built in a cone with an $R_{Γ_{0}, Γ_{1}}$ -requirement at the top. These cones are nested in the sense that each node where a particular set $X_{2}$ is active is also a node where a set $X_{1}$ is active; but a cone for $X_{1}$ can contain many different $X_{2}$ -cones. The setup here is typical of a non-uniform argument; the situation in our construction is perhaps slightly more complicated than a typical non-uniform argument due to having to keep track of three levels of non-uniformity. However, the overall spirit is the same: The set $X_{0}$ is maintained globally, and there will only be one version of it, i.e., every node in the tree is in the one $X_{0}$ -cone. Inside each $X_{2}$ -cone, we will have the active sets $X_{0}$ and $X_{1}$ . Inside this $X_{2}$ -cone, we actively try and satisfy the $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ - and the $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies, while leveraging on the assumption that the $R_{Γ_{0}, Γ_{1}}$ - and $R_{Γ_{0}}$ -strategies at the top of the $X_{2}$ - and $X_{1}$ -cones are unsuccessful. While this assumption is not violated, we stay in the $X_{2}$ -cone and only consider the $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ - and the $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies.

If we ever detect that the $R_{Γ_{0}, Γ_{1}}$ -strategy is successful, we will exit the $X_{2}$ -cone and immediately place the next $S_{Γ_{0}, Δ_{1}}$ -strategy before starting a new $X_{2}$ -cone below it. Similarly, if we ever detect that the $R_{Γ_{0}}$ -strategy is successful, we will end the current $X_{1}$ - and $X_{2}$ -cones and immediately place the next $S_{Δ_{0}}$ -strategy before starting a new $X_{1}$ - and a new $X_{2}$ -cone below. In this way, depending on how many different $X_{1}$ - and $X_{2}$ -cones the true path of the construction crosses, we will be able to argue that along the true path, either all $R_{Γ_{0}}$ - and $S_{Δ_{0}}$ -requirements are satisfied, or all $R_{Γ_{0}, Γ_{1}}$ - and $S_{Γ_{0}, Γ_{1}}$ -requirements are satisfied in some final $X_{1}$ -cone, or all $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ - and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -requirements are satisfied in some final $X_{2}$ -cone.

It remains to describe how a node α assigned to a requirement $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ is able to either detect the success of its parent $R_{Γ_{0}, Γ_{1}}$ -strategy, or the success of its grandparent $R_{Γ_{0}}$ -strategy, or be able to leverage on the failure of both to ensure the success of its own requirement. By our experience with the $S$ -strategies thus far, it is important to note that α must not be too liberal with enumerating true axioms into $Φ_{0}$ , $Φ_{1}$ and $Φ_{2}$ ; if we do not exit the current $X_{2}$ -cone, we must make sure that α’s contribution to $X_{2}$ is finite or at least computable. If we do not exit the current $X_{1}$ -cone, then α’s contribution to $X_{1}$ must be finite, while α’s contribution to $X_{0}$ must be finite regardless of the true outcome. (If we do not ensure this, then along the true path, when we have the next $S_{Δ_{0}}$ , $S_{Γ_{0}, Δ_{1}}$ - or $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -node, we will not be able to run the respective basic $S$ -strategy.)

With the foregoing comment in mind, consider a node α assigned to a requirement $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ . The obvious strategy is to associate each number a (targeted for $A_{1}$ ) with a number $x_{a}$ (targeted for $X_{1} = Φ_{1} (A_{1})$ ) and try to maintain that $a \in A_{1}$ iff $x_{a} \in X_{1}$ . We build a reduction $Ψ_{1}$ which will emulate $Γ_{1}$ . Since $A_{1} = Ψ_{1} (A_{2})$ cannot possibly hold, we must be able to find some $x_{a}$ where $X_{1} (x_{a}) \neq Γ_{1} (A_{2}) (x_{a})$ , and hence $R_{Γ_{0}, Γ_{1}}$ will be satisfied. This naive strategy will work to satisfy $R_{Γ_{0}, Γ_{1}}$ in isolation; unfortunately, we may not be able to guarantee that the effect on $X_{1}$ is finite; as discussed above, if we satisfy $R_{Γ_{0}, Γ_{1}}$ , we stay in the $X_{1}$ -cone, and we will need the strategy to enumerate only finitely many true axioms for $Φ_{1} (A_{1})$ . Notice that if there is some $x_{a} \in Γ_{1} (A_{2}) ∖ X_{1}$ , then this condition can be ensured, since the strategy for α will only need to enumerate further axioms putting some $x_{a^{'}}$ into $Φ_{1} (A_{2})$ if the length of agreement goes up; hence all newer axioms in $Φ_{1}$ will include the number a. However, if the disagreement is witnessed by some $x_{a} \in X_{1} ∖ Γ_{1} (A_{2})$ , then there is no way to prevent infinitely many elements $x_{a^{'}}$ from being put into $X_{1}$ by the strategy. Note that the same problem applies even if we try and diagonalize $X_{0}$ and $Γ_{0} (A_{1})$ , or $X_{2}$ and $Γ_{2} (A_{1})$ . The solution to this problem is to ensure that under the problematic outcome where $x_{a} \in X_{1} ∖ Γ_{1} (A_{2})$ , all future axioms enumerated by α putting some $x_{a^{'}}$ into $X_{1} = Φ_{1} (A_{1})$ must also include the use of certain elements in $Γ_{0} (A_{1})$ and $Γ_{2} (A_{1})$ . If we entangle the axioms for newer $x_{a^{'}}$ in this way correctly, then we will be able to argue that in the end, either we will be able to diagonalize $X_{0}$ and $Γ_{0} (A_{1})$ , or we can diagonalize $X_{2}$ and $Γ_{2} (A_{1})$ , or else we can force all newer $x_{a^{'}}$ -axioms enumerated by α to become invalid.

To arrange for this entangling to work properly, we will need another setup. Under the assumption that $a \in A_{1} ∖ Ψ_{1} (A_{2})$ and $x_{a} \in X_{1} ∖ Γ_{1} (A_{2})$ hold, we will need to start a backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy, which we will name β. Each time β sees further proof that $a \in A_{1} ∖ Ψ_{1} (A_{2})$ and $x_{a} \in X_{1} ∖ Γ_{1} (A_{2})$ hold, it will extend the reduction $A_{0} = Ψ_{0} (A_{1})$ that it builds. The basic working of β is that it associates each number b targeted for $A_{0}$ with a number $y_{b}$ targeted for $X_{2} = Φ_{2} (A_{0})$ and a number $m_{b}$ targeted for $X_{0} = Φ_{0} (A_{0})$ . (For technical reasons, in the construction, the association $b \mapsto y_{b}$ will be fixed while the association $b \mapsto m_{b}$ will be dynamic, but we do not encumber ourselves with these details at this time.) The plan will be to let $Ψ_{0}$ emulate $Γ_{2}$ , so that the necessary disagreement between $A_{0}$ and $Ψ_{0} (A_{1})$ must produce a corresponding disagreement between $X_{2}$ and $Γ_{2} (A_{1})$ . Fix the element b so that we have either

$b \in A_{0} ∖ Ψ_{0} (A_{1})$ and $y_{b} \in X_{2} ∖ Γ_{2} (A_{1})$ and $m_{b} \in X_{0}$ , or

$b \in Ψ_{0} (A_{1}) ∖ A_{0}$ and $y_{b} \in Γ_{2} (A_{1}) ∖ X_{2}$ and $m_{b} \notin X_{0}$ .

Since b will eventually be in one of the

Σ_{2}^{0}

-sets involved above, almost every axiom enumerated by the main strategy α putting some

x_{a^{'}}

into

X_{1} = Φ_{1} (A_{1})

will be able to observe and use the information provided by this number b.

Consider a future stage s when the strategy α is deciding whether or not to enumerate an axiom putting some $x_{a^{'}}$ into $X_{1} = Φ_{1} (A_{1})$ . By our assumption on b, we must see either $y_{b} \in X_{2} [s]$ or $y_{b} \in Γ_{2} (A_{1}) [s]$ . If the strategy for α sees $y_{b} \in X_{2} [s]$ but $y_{b} \notin Γ_{2} (A_{1}) [s]$ , then it does not need to proceed with its strategy and does not enumerate any axiom for $x_{a^{'}}$ into $X_{1}$ since it currently looks like $X_{2} \neq Γ_{2} (A_{1})$ . If, however, α sees $y_{b} \in Γ_{2} (A_{1}) [s]$ but $m_{b} \notin Γ_{0} (A_{1})$ , then it also does not need to enumerate an axiom for $x_{a^{'}}$ into $X_{1}$ . This is because either $b \in A_{0}$ , in which case both $y_{b} \in X_{2}$ and $m_{b} \in X_{0}$ , or they are all three out of the respective sets, and so we must currently see $X_{2} \neq Γ_{2} (A_{1})$ or $X_{0} \neq Γ_{0} (A_{1})$ . Therefore, the only time when α enumerates $x_{a^{'}}$ into $X_{1}$ is when it sees both $y_{b} \in Γ_{2} (A_{1}) [s]$ and $m_{b} \in Γ_{0} (A_{1}) [s]$ , in which case it will include the use of the latter two in the axiom for $x_{a^{'}}$ in $X_{1}$ .

Now finally assume that β is along the true path of the construction. If the first case (i) above applies to b, then almost every axiom $x_{a^{'}}$ enumerated by the strategy for α will be invalid, since they will include the use of $y_{b} \in Γ_{2} (A_{1})$ , which was exactly what we wanted to achieve. If the second case (ii) applies and $m_{b}$ is not eventually in $Γ_{0} (A_{1})$ , then again almost every axiom $x_{a^{'}}$ enumerated by the strategy for α will be invalid, since they will include the use of $m_{b} \in Γ_{0} (A_{1})$ . Finally, assume that the second case (ii) applies and $m_{b} \in Γ_{0} (A_{1})$ . Then in this case, it may be possible that the strategy for α enumerates infinitely many elements into $X_{1}$ , but then we would have $m_{b} \in Γ_{0} (A_{1}) ∖ X_{0}$ , and we will exit the current $X_{1}$ -cone. In this case, the current set $X_{1}$ will be irrelevant anyway.

3.3. Tree of strategies

Order each of the types of requirements, subrequirements and subsubrequirements in a priority of order type ω such that each $R_{Γ_{0}}$ -requirement precedes all the $R_{Γ_{0}, Γ_{1}}$ -subrequirements, and each $R_{Γ_{0}, Γ_{1}}$ -subrequirement precedes all the $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -subsubrequirements.

The root of the tree of strategies T is ∅, an $R_{Γ_{0}}$ -strategy working on the highest-priority $R_{Γ_{0}}$ -requirement. An $R_{Γ_{0}}$ -strategy has only one outcome $⟨ 0 ⟩$ and is immediately followed by an $R_{Γ_{0}, Γ_{1}}$ -strategy, working on the highest-priority $R_{Γ_{0}, Γ_{1}}$ -requirement. An $R_{Γ_{0}, Γ_{1}}$ -strategy has only one outcome $⟨ 0 ⟩$ and is immediately followed by an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy, working on the highest priority $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -requirement.

An $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy α has outcomes $⟨ 2 k ⟩$ , $⟨ 2 k + 1, old ⟩$ , $⟨ 2 k + 1, off ⟩$ , $⟨ 2 k + 1, new ⟩$ , and $⟨ 2 k + 1, backup ⟩$ for all $k \in ω$ , ordered as follows: $\begin{matrix} ⟨ 0 ⟩ <_{L} ⟨ 1, old ⟩ <_{L} ⟨ 1, off ⟩ <_{L} ⟨ 1, new ⟩ <_{L} ⟨ 1, backup ⟩ <_{L} ⟨ 2 ⟩ <_{L} \dots \end{matrix}$ For every $k < ω$ , the nodes $α \hat{} ⟨ 2 k ⟩$ are $S_{Γ_{0}, Δ_{1}}$ -strategies working on the highest-priority $S_{Γ_{0}, Δ_{1}}$ -requirement that is not assigned to any of α’s predecessors. The nodes $α \hat{} ⟨ 2 k + 1, old ⟩$ and $α \hat{} ⟨ 2 k + 1, off ⟩$ are $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies working on the highest priority $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -requirement that is not assigned to any of α’s predecessors. The nodes $α \hat{} ⟨ 2 k + 1, new ⟩$ are $S_{Δ_{0}}$ -strategies working on the highest-priority $S_{Δ_{0}}$ -requirement that is not assigned to any of α’s predecessors. Finally, the nodes $α \hat{} ⟨ 2 k + 1, backup ⟩$ are backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategies with their own outcomes (defined below).

An $S_{Δ_{0}}$ -strategy γ has outcomes $⟨ k ⟩$ , where $k \in ω$ ordered by the standard ordering on ω. Each such immediate successor of this strategy is a main $R_{Γ_{0}}$ -strategy, working on the highest-priority $R_{Γ_{0}}$ -requirement that is not assigned to any of its predecessors. The outcomes and immediate successors of the $S_{Γ_{0}, Δ_{1}}$ - and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies are defined analogously ( $R_{Γ_{0}, Γ_{1}}$ and $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ , respectively).

Finally, a backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy β has outcomes $⟨ 2 l, off ⟩$ , $⟨ 2 l, new ⟩$ and $⟨ 2 l + 1 ⟩$ for all $l \in ω$ , ordered as follows: $\begin{matrix} ⟨ 0, off ⟩ <_{L} ⟨ 0, new ⟩ <_{L} ⟨ 1 ⟩ <_{L} ⟨ 2, off ⟩ <_{L} \dots \end{matrix}$ For every $l < ω$ , the nodes $β \hat{} ⟨ 2 l, off ⟩$ and $β \hat{} ⟨ 2 l + 1 ⟩$ are $S_{Γ_{0}, Δ_{1}}$ -strategies working on the highest-priority $S_{Γ_{0}, Δ_{1}}$ -requirement that is not assigned to any of β’s predecessors. The nodes $β \hat{} ⟨ 2 l, new ⟩$ are $S_{Δ_{0}}$ -strategies working on the highest-priority $S_{Δ_{0}}$ -requirement that is not assigned to any of β’s predecessors.

3.4. Construction

This construction has many properties that are similar to the one in Section 2. At stage 0, all strategies are in initial state: All operators associated with these strategies are empty, and all parameters are undefined. At stage $s > 0$ , we build a path $f_{s}$ of length $⩽ s$ with the intention of building a true path defined by $\begin{matrix} f (n) = \underset{f_{s} ⪰ f ↾ n}{lim inf} f_{s} (n) . \end{matrix}$ When a strategy is activated at stage s, it first adjusts the approximations to $A_{0}$ , $A_{1}$ , and $A_{2}$ : If $s^{-}$ is the previous stage at which this strategy was active, then it replaces $A_{i, s}$ by $⋂_{u \in [s^{-}, s]} A_{i, u}$ for $i ⩽ 2$ . At the end of stage s, we initialize all strategies of lower priority than $f_{s}$ , i.e., strategies extending or to the right of the strategies which acted at stage s.

Each strategy β works with the version of $Φ_{1}$ and $X_{1}$ determined by the longest $R_{Γ_{0}}$ -strategy $α ≺ β$ (we say that β works for α); this version of $Φ_{1}$ is the set of $Φ_{1}$ -axioms enumerated by all the $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategies and $S_{Γ_{0}, Δ_{1}}$ -strategies working for the same $R_{Γ_{0}}$ -strategy. Similarly, each strategy β works with the version of $Φ_{2}$ and $X_{2}$ determined by the longest $R_{Γ_{0}, Γ_{1}}$ -strategy $α ≺ β$ ; this version of $Φ_{2}$ is the set of $Φ_{2}$ -axioms enumerated by all the backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategies and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies working for the same $R_{Γ_{0}, Γ_{1}}$ -strategy.

3.4.1. $S_{Δ_{0}}$ , $S_{Γ_{0}, Δ_{1}}$ , $S_{Γ_{0}, Γ_{1}, Δ_{2}}$

The $S$ -strategies work precisely as in the previous construction. Let γ be such a strategy. The first time γ is visited after initialization, it receives a unique number $s_{γ}$ , the stage of first visit after initialization, and stops the construction of $f_{s} = γ$ for this stage. If $s_{γ} < s$ is already defined, then we consider the length $l_{γ, s} < s$ of the common initial segment up to s of the sets $A_{j, s}$ and $Δ_{i, s} (X_{i})$ that are named in the corresponding requirement: For $S_{Δ_{0}}$ , these are $A_{0, s}$ and $Δ_{0, s} (X_{0, s})$ ; for $S_{Γ_{0}, Δ_{1}}$ , these are $A_{1, s}$ and $Δ_{1, s} (X_{1, s})$ ; and for $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ , these are $A_{0, s}$ and $Δ_{2, s} (X_{2, s})$ . For every number $n ⩽ l_{γ, s}$ , if $n \in Δ_{i, s} (X_{i, s}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ , then we search for the axiom $⟨ n, F ⟩ \in Δ_{i}$ that has been valid the longest, and we enumerate each element of the form $⟨ r, x ⟩ \in F$ , where $r ⩾ s_{γ}$ , into the set $X_{i, s}$ via the axiom $⟨ ⟨ r, x ⟩, A_{j, s} ⟩$ . Note that this action might enumerate some number $⟨ r, x ⟩$ into $X_{i, s}$ where $⟨ r, x ⟩$ is already in $X_{i, s}$ via an axiom enumerated by a different node.

The outcome of the strategy is $⟨ k ⟩$ , where k is the standard code of the finite set $D_{k}$ of all numbers for which γ has enumerated an axiom that looks valid at stage s. As before, we assume that $D_{k_{1}} \subseteq D_{k_{2}}$ implies $k_{1} ⩽ k_{2}$ .

3.4.2. $R_{Γ_{0}}$ , $R_{Γ_{0}, Γ_{1}}$

The $R_{Γ_{0}}$ -strategy and the $R_{Γ_{0}, Γ_{1}}$ -strategy do nothing, have only one outcome $⟨ 0 ⟩$ , and determine the version of $Φ_{1}$ and $X_{1}$ , or $Φ_{2}$ and $X_{2}$ , respectively, that substrategies work with.

3.4.3. $R_{Γ_{0}, Γ_{1}, Γ_{2}}$

The $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy α attempts to construct an enumeration operator $Ψ_{1}$ such that $A_{1} = Ψ_{1} (A_{2})$ by enumerating axioms into $Φ_{1}$ . (It will not enumerate axioms into either $Φ_{0}$ or $Φ_{2}$ , only its backup strategies will.)

At the first stage after initialization, the $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy α is assigned the parameter $s_{α}$ . We can assume that $s_{α}$ is larger than $max (D_{k})$ for any k such that a higher-priority $S$ -strategy λ has $λ \hat{} k ⪯ α$ . Until its next initialization, α will only contribute numbers to the $s_{α}$ -th columns of $X_{1}$ . To every element a, we assign the coding location $x_{a} = ⟨ s_{α}, a ⟩$ targeted for $X_{1}$ .

At stage $s > s_{α}$ , α does the following. It orders the elements of $A_{1, s} \cup Ψ_{1, s} (A_{2, s})$ by age: $\begin{array}{l} {age}_{1}^{s} (a) = 2 k + 1 for k = min (s + 1, μ t \forall u \in [t, s] (a \in A_{1, u})) \\ {age}_{2}^{s} (a) = 2 k for k = min (s + 1, μ t \forall u \in [t, s] (a \in Ψ_{1} (A_{2, u}) [u] via the same axiom)) \\ {age}^{s} (a) = min {{age}_{1}^{s} (a), {age}_{2}^{s} (a)} . \end{array}$

Once again, we assume the age is defined injectively, i.e., for every stage $t ⩽ s$ , there may be at most one element with ${age}^{s} (a) = t$ . Also, if $a \in A_{1, s} ∖ Ψ_{1, s} (A_{2, s})$ , then ${age}^{s} (a)$ is odd, and if $a \in Ψ_{1, s} (A_{2, s}) ∖ A_{1, s}$ , then ${age}^{s} (a)$ is even.

If $A_{1, s} = Ψ_{1, s} (A_{2, s})$ , then we exit this strategy with outcome $⟨ 2 (s + 1) ⟩$ . Otherwise, we pick the oldest number a such that $A_{1, s} (a) \neq Ψ_{1, s} (A_{2, s}) (a)$ . Let $k = {age}^{s} (a)$ . We have two cases depending on the parity of k.

Case 1: If k is even, i.e., if $a \in Ψ_{1, s} (A_{2, s}) ∖ A_{1, s}$ , then we will be able to argue that $x_{a} = ⟨ s_{α}, a ⟩ \in Γ_{1} (A_{2}) ∖ X_{1}$ . The strategy selects outcome $⟨ k ⟩$ . While a maintains its age, we will design axioms for younger elements enumerated into $X_{1}$ by α so that their use includes a. Thus if this is α’s true outcome, they will be invalid, and hence α contributes finitely much to $X_{1}$ . Under this outcome, we do not care about $X_{2}$ .

Case 2: If k is odd, i.e., if $a \in A_{1, s} ∖ Ψ_{1, s} (A_{2, s})$ , then we would like to add an axiom for a into $Ψ_{1}$ . We will follow a similar scheme as in the previous construction: We will add an axiom for $x_{a}$ into $Φ_{1}$ , wait until $x_{a}$ shows up in $Γ_{1} (A_{2})$ , and use the (currently) valid axiom $⟨ x_{a}, F_{a} ⟩$ to define an axiom for a in $Ψ_{1}$ . We entangle the axiom for $x_{a}$ with axioms from both $Γ_{0}$ and $Γ_{2}$ . First, we consider all $z \in X_{2, s}$ such that the age of z in $X_{2}$ (i.e., the least $t ⩽ s$ such that $z \in X_{2, u}$ for all $u \in [t, s]$ ) is less than k. Let $s_{k}$ be the previous stage when α considered k:

If some such $z \in X_{2, s}$ is not in $Γ_{2} (A_{1, t})$ via the same axiom for all stages $t \in [s_{k}, s]$ , then we have evidence that $z \in X_{2} ∖ Γ_{2} (A_{1})$ , and so we exit with outcome $⟨ k, old ⟩$ . If b is younger than a, then α will always include the use of an axiom for z being in $Γ_{2} (A_{2})$ in the use of the axiom for $x_{b}$ being in $Φ_{1} (A_{1})$ , so if this is the true outcome, then $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ is satisfied and α’s effect on $X_{1}$ is finitary.

Otherwise, for every $z \in X_{2, s}$ that is older than a, we can associate a set $G_{z}$ , the use of the oldest valid axiom for z being in $Γ_{2} (A_{1})$ . Next, we consider every backup strategy β (an immediate successor of α) that is not in initial state, every number $y_{b}^{β} = ⟨ s_{β}, b ⟩ \in Γ_{2, s} (A_{1, s})$ such that the age of $y_{b}^{β}$ (i.e., the least $t ⩽ s$ such that at all $u \in [t, s]$ , we have $y_{b}^{β} \in Γ_{2, u} (A_{1, u})$ via the same axiom) is less than k, and for each such $y_{b}^{β}$ , the coding locations $m_{b}^{β} < k$ that are associated with b by β. (Note that we do not restrict β to the ones that extend an older outcome than k. There will only be finitely many such backup strategies being considered due to the restriction on the age of $y_{b}^{β}$ .)

If for some such $y_{b}^{β} \in Γ_{2, s} (A_{1, s})$ , there is an $m_{b}^{β} < k$ such that $m_{b}^{β} \notin Γ_{0} (A_{1, t})$ at some stage $t \in [s_{k}, s]$ , then we have two cases:

If $b \notin A_{0, t}$ at some stage $t \in [s_{k}, s]$ , then we have evidence that $y_{b}^{β} \in Γ_{2} (A_{1}) ∖ X_{2}$ . We exit with outcome $⟨ k, off ⟩$ and argue that if this is the true outcome, then $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ is satisfied and α enumerates finitely many valid axioms into $Φ_{1}$ because they all must include the use of a $Γ_{0}$ -axiom for all such $m_{b}^{β}$ .

If $b \in A_{0, t}$ at all $t \in [s_{k}, s]$ , then the outcome is $⟨ k, new ⟩$ . We have evidence that $m_{b}^{β} \in X_{0}$ as it was either dumped there (i.e., we enumerated the axiom $⟨ m_{b}^{β}, \emptyset ⟩$ into $Φ_{0}$ ) or its axiom has use ${b}$ . If this is the true outcome, then we aim to show that $R_{Γ_{0}}$ is satisfied by $m_{b}^{β} \in X_{0} ∖ Γ_{0} (A_{1})$ . In this case, we do not care about α’s effect on $X_{1}$ even though that effect will be finitary as we argued in the previous case.

Otherwise, for every older $y_{b}^{β} \in Γ_{2, s} (A_{1, s})$ and each $m_{b}^{β} < k$ associated with b, we can associate a set $G_{m_{b}^{β}}$ , the use of the oldest valid axiom for $m_{b}^{β}$ in the set $Γ_{0}$ . We enumerate into $Φ_{1, s}$ the axiom for $x_{a}$ whose use consists of

all b such that ${age}^{s} (b) ⩽ k$ (note that this includes a),

all $G_{z}$ for older $z \in X_{2, s}$ , and

all $G_{m_{b}^{β}}$ where β is a substrategy of α not in initial state (at the end of this stage) with older $y_{b}^{β} \in Γ_{2, s} (A_{1, s})$ , and corresponding $m_{b}^{β} < k$ .

Next, we check whether

x_{a} \in Γ_{1} (A_{2})

. If

x_{a} \notin Γ_{1, t} (A_{2, t})

at some stage

t \in [s_{k}, s]

, then we have evidence that

R_{Γ_{0}, Γ_{1}}

may be satisfied by

x_{a} \in X_{1} ∖ Γ_{1} (A_{2})

. Unfortunately, we have no evidence that the effect of α on

X_{1}

is finite. So we activate the backup strategy below outcome

⟨ k, backup ⟩

. The backup strategy will either turn off future axioms enumerated by α or ensure that

R_{Γ_{0}}

is satisfied.

Finally, if $x_{a} \in Γ_{1} (A_{2, t})$ (by the same axiom at all stages since the last visit), then let $⟨ x_{a}, F_{a} ⟩ \in Γ_{1}$ be the axiom that has been valid longest. Enumerate $⟨ a, F_{a} ⟩ \in Ψ_{1, s}$ . We have now eliminated a as a difference, and so we will pick the oldest difference once again, starting over at the current substage. (This can happen at most finitely often at any substage.)

Notice that the set $X_{2}$ is only relevant under the outcomes $⟨ k, old ⟩$ and $⟨ k, off ⟩$ of α (corresponding to items (1) and (2a) above, respectively). Since α itself does not add axioms to $Φ_{2} (A_{0})$ , but rather, they are only added by the backup strategies, whenever some outcome $⟨ k^{'}, backup ⟩$ of α is played, the effect on each column of $X_{2}$ will be finite if α has true outcome $⟨ k, old ⟩$ or $⟨ k, off ⟩$ . This is also the reason we have multiple backup strategies for α.

3.4.4. Backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$

The backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy β works with its immediate predecessor α and attempts to construct an enumeration operator $Ψ_{0}$ such that $A_{0} = Ψ_{0} (A_{1})$ by enumerating axioms into $Φ_{0}$ and its version of $Φ_{2}$ .

Just like α, the strategy β is assigned the parameter $s_{β}$ at the first stage after initialization. We can assume that $s_{β}$ is larger than $max (D_{k})$ for any k such that a higher priority $S$ -strategy λ has $λ \hat{} k ⪯ β$ . The strategy β associates to every element b the coding location $y_{b} = ⟨ s_{β}, b ⟩$ targeted for $X_{2}$ . To certain elements b, it will also dynamically assign a coding location $m_{b}$ targeted for $X_{0}$ .

At a stage $s > s_{β}$ , β orders the elements of $A_{0, s} \cup Ψ_{0, s} (A_{1, s})$ by age so that if $b \in A_{0, s} ∖ Ψ_{0, s} (A_{1, s})$ , then ${age}^{s} (b)$ is odd, and if $b \in Ψ_{0, s} (A_{1, s}) ∖ A_{0, s}$ , then ${age}^{s} (b)$ is even.

If $A_{0, s} = Ψ_{0, s} (A_{1, s})$ , then we exit this strategy with outcome $⟨ 2 (s + 1) + 1 ⟩$ . Otherwise, we pick the oldest number b such that $A_{0, s} (b) \neq Ψ_{s} (A_{1, s}) (b)$ . If there is no marker $m_{b}$ associated with b, then we choose $m_{b}$ to be the least number of the form $⟨ s_{β}, n ⟩$ which has not been chosen as a marker. We also enumerate the axiom $⟨ m_{b}, {b} ⟩$ into $Φ_{0}$ .

Let $l = {age}^{s} (b)$ . We must ensure that β’s effect on $X_{0}$ is computable and so the strategy will dump into $X_{0}$ all markers which are currently associated with any number $b^{'}$ with ${age}^{s} (b^{'}) > l$ . Furthermore, to each such $b^{'}$ , we associate a new marker $m_{b^{'}}$ , which is the least number of the form $⟨ s_{β}, n ⟩$ which has not been chosen as a marker. We also enumerate the axiom $⟨ m_{b^{'}}, {b^{'}} ⟩$ into $Φ_{0}$ .

We will not ensure that β’s effect on $X_{2}$ is finitary or computable because if β is on the true path, then either $R_{Γ_{0}}$ or $R_{Γ_{0}, Γ_{1}}$ will be satisfied and $X_{2}$ will not be relevant to strategies extending β.

We now have two cases depending on the parity of l.

Case 1: If l is even, i.e., if $b \in Ψ_{0, s} (A_{1, s}) ∖ A_{0, s}$ , then unlike for α, we cannot simply take the easy win $y_{b} \in Γ_{2} (A_{1}) ∖ X_{2}$ , because we still have not guaranteed that α’s effect on $X_{1}$ is finitary. For that reason, we will instead consider the marker $m_{b}$ . We will argue that $b \notin A_{0, s}$ is evidence that $m_{b}$ is not an element of $X_{0}$ , and so we check whether $m_{b} \in Γ_{0} (A_{1})$ . Let $s_{l}$ be the previous stage when α considered l:

If $m_{b}$ is not in $Γ_{0} (A_{1, t})$ for some $t \in [s_{l}, s]$ (via the same axiom), then we will be able to argue that if this is the true outcome, then α enumerates only finitely many axioms into $X_{1}$ as all but finitely many of them will include an axiom for $m_{b}$ in $Γ_{0}$ . In this case, $R_{Γ_{0}, Γ_{1}}$ is satisfied, and α’s action on $X_{1}$ is finitary. So we take outcome $⟨ l, off ⟩$ .

Otherwise, we have evidence that $m_{b} \in Γ_{0} (A_{1}) ∖ X_{0}$ and so if this is the true outcome, then $R_{Γ_{0}}$ is satisfied and we take the outcome $⟨ l, new ⟩$ . Below this outcome, we do not care anymore what happens to $X_{1}$ .

Case 2: If l is odd, i.e., if

b \in A_{0, s} ∖ Ψ_{0, s} (A_{1, s})

, then we enumerate the axiom

⟨ y_{b}, {b} ⟩

into the operator

Φ_{2}

If $y_{b} \notin Γ_{2} (A_{1, s})$ , then, if this is the true outcome, all but finitely many axioms that α enumerates will contain the use of an axiom for $y_{b}$ being in $Γ_{2} (A_{1})$ which is invalid. It follows that once again, $R_{Γ_{0}, Γ_{1}}$ is satisfied and α’s action on $X_{1}$ is finitary. We exit with outcome $⟨ l ⟩$ .

Finally, if $y_{b} \in Γ_{2} (A_{1, s})$ (by the same axiom at all stages since the last visit), then let $⟨ y_{b}, F_{b} ⟩ \in Γ_{2}$ be the axiom that has been valid longest. Enumerate $⟨ b, F_{b} ⟩$ into $Ψ_{0, s}$ . We have now eliminated b as a difference, and so we will pick the oldest difference once again, starting over at the current substage. (This can happen at most finitely often at any substage.)

3.5. Verification

We define the true path f in the tree of strategies as the leftmost path of strategies visited infinitely often. If $λ \hat{} o ⪯ f$ , then we will say that λ has true outcome o. If s is a stage at which λ is visited, we say that s is λ-true. We need to prove that f is well-defined and strategies along it satisfy their requirements. We do so by showing the following properties of the construction by simultaneous induction.

Lemma 3.2.
The true path f is infinite, furthermore:
If α is an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy and $α ≺ f$ , then:

There are finitely many values of the parameter $s_{α}$ .

There is a leftmost outcome o that α visits at infinitely many stages.

If $o \in {⟨ 2 k ⟩ ∣ k \in ω}$ , then $R_{Γ_{0}, Γ_{1}}$ is satisfied, and for every value of $s_{α}$ , the set $X_{1}^{[s_{α}]}$ is finite.

If $o \in {⟨ 2 k + 1, old ⟩, ⟨ 2 k + 1, off ⟩ ∣ k \in ω}$ , then $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ is satisfied, and for every value of $s_{α}$ , the set $X_{1}^{[s_{α}]}$ is finite.

If $o \in {⟨ 2 k + 1, new ⟩ ∣ k \in ω}$ , then $R_{Γ_{0}}$ is satisfied.

If $o \in {⟨ 2 k + 1, backup ⟩ ∣ k \in ω}$ , then $R_{Γ_{0}, Γ_{1}}$ is satisfied.

If β is a backup strategy for an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy α and $β ≺ f$ , then:

There are finitely many values of the parameter $s_{β}$ .

There is a leftmost outcome o that β visits at infinitely many stages.

For every value of $s_{β}$ , the set $X_{0}^{[s_{β}]}$ is computable.

If $o \in {⟨ 2 l, off ⟩, ⟨ 2 l + 1 ⟩ ∣ l \in ω}$ , then $R_{Γ_{0}, Γ_{1}}$ is satisfied, and for every value of $s_{α}$ , the set $X_{1}^{[s_{α}]}$ is finite.

If $o \in {⟨ 2 l, new ⟩ ∣ l \in ω}$ , then $R_{Γ_{0}}$ is satisfied.

If $γ ≺ f$ is an $S_{Δ_{0}}$ -, $S_{Γ_{0}, Δ_{1}}$ -, or $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategy, respectively, then:

There is a leftmost outcome o that γ visits at infinitely many stages.

The set $D_{o}$ consists of all numbers that γ contributes to $X_{0}$ , $X_{1}$ , or $X_{2}$ , respectively.

The requirement $S_{Δ_{0}}$ , $S_{Γ_{0}, Δ_{1}}$ , or $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ , respectively, is satisfied.

Proof.
A. Since $α ≺ f$ , there is a least stage at which α is visited after its final initialization. At this stage, $s_{α}$ receives its final value, proving (1). By construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. We claim that α is the only strategy that adds elements to $X_{1}^{[s_{α}]}$ . By construction, no strategy has enumerated any element into $X_{1}^{[s_{α}]}$ so far. Lower-priority strategies σ are initialized at stage $s_{α}$ , so any future values of $s_{σ}$ will be greater than $s_{α}$ . Once that occurs, σ cannot add elements to $X_{1}^{[s_{α}]}$ . Higher-priority strategies will not add elements to $X_{1}^{[s_{α}]}$ , either. To see this, note that any strategy λ of higher priority that potentially adds elements into $X_{1}$ after stage $s_{α}$ is either an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy with $s_{λ} < s_{α}$ , or an $S_{Γ_{0}, Δ_{1}}$ -strategy which will not enumerate any valid $Φ_{1}$ -axioms for numbers into $X_{1}^{[⩾ s_{α}]}$ by inductive hypothesis and our choice of $s_{α}$ . This proves our claim. Note that if $t < s_{α}$ is a previous value of the parameter $s_{α}$ , then our analysis shows that no strategy can add elements into $X_{1}^{[t]}$ after stage $s_{α}$ . It follows that $X_{1}^{[t]}$ is finite.

Let $Ψ_{1} = ⋃_{s > s_{α}} Ψ_{1, s}$ be the enumeration operator constructed by α. By assumption, $A_{1} ≰_{e} A_{2}$ , hence $Ψ_{1} (A_{2}) \neq A_{1}$ . Let a be the oldest disagreement between $Ψ_{1} (A_{2})$ and $A_{1}$ . This means that there is some stage $s_{a}$ such that at all stages $t > s_{a}$ , we have that ${age}^{t} (a)$ stabilizes, and if ${age}^{t} (b) < {age}^{t} (a)$ , then $b \in A_{1, t} \cap Ψ_{1, t} (A_{2, t})$ . Furthermore, the way α adjusts the approximation to $A_{1}$ and $A_{2}$ when visited ensures that there are infinitely many stages $t > s_{a}$ at which we visit α and a is the oldest disagreement at stage t. At such stages, α will visit an ${age}^{t} (a)$ -outcome, and since there are finitely many ${age}^{t} (a)$ -outcomes, there is a leftmost outcome o visited at infinitely many stages, proving (2).

To prove (3), suppose that o is $⟨ 2 k ⟩$ . In order to show that $R_{Γ_{0}, Γ_{1}}$ is satisfied, we will show that $x_{a} \in Γ_{1} (A_{2}) ∖ X_{1}$ . Since o is $⟨ 2 k ⟩$ , we have $a \notin A_{1, t}$ for infinitely many stages t, so $a \notin A_{1}$ . We argued above that only α can enumerate $Φ_{1}$ -axioms for $x_{a}$ . By construction, the use of any such axiom contains a. So $x_{a} \notin X_{1}$ . As for $Γ_{1} (A_{2})$ , note that $a \notin A_{1}$ implies that $a \in Ψ_{1} (A_{2})$ . For any $Ψ_{1}$ -axiom for a, there is a corresponding $Γ_{1}$ -axiom for $x_{a}$ with the same use. The latter axiom witnesses that $x_{a} \in Γ_{1} (A_{2})$ as desired.

To show that $X_{1}^{[s_{α}]}$ is finite, it suffices (by our reasoning above) to show that there is a stage after which no $Φ_{1}$ -axiom enumerated by α is valid. This holds because any $Φ_{1}$ -axiom enumerated by α when the current outcome is o or to the right of o must contain a in its use, yet $a \notin A_{1}$ . This completes the proof of (3).

To prove (4), first suppose that o is $⟨ 2 k + 1, old ⟩$ . In order to show that $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ is satisfied, we will show that $X_{2} ⊈ Γ_{2} (A_{1})$ . Since o is $⟨ 2 k + 1, old ⟩$ , there are infinitely many stages s such that there is some $z \in X_{2, s}$ with age less than $2 k + 1$ and $z \notin Γ_{2} (A_{1, t})$ , where $t \in [s_{k}, s]$ . (Recall that $s_{k}$ is the last stage before s at which α considered $2 k + 1$ .) There are only finitely many z which ever have age less than $2 k + 1$ , so the scenario described happens infinitely often with some fixed z. It follows that $z \in X_{2} ∖ Γ_{2} (A_{1})$ as desired.

To show that $X_{1}^{[s_{α}]}$ is finite, note that for all but finitely many stages at which we visit α, the age of z in $X_{2}$ is smaller than the age of the oldest disagreement between $A_{1}$ and $Ψ_{1} (A_{2})$ . At such stages, if α enumerates a $Φ_{1}$ -axiom, its use contains the use $G_{z}$ of a $Γ_{2}$ -axiom for z being in $Γ_{2} (A_{1})$ . Since $z \notin Γ_{2} (A_{1})$ , it follows that α only enumerates finitely many valid $Φ_{1}$ -axioms. Therefore, $X_{1}^{[s_{α}]}$ is finite (as α is the only strategy which adds elements into $X_{1}^{[s_{α}]}$ ). This completes the analysis if o is $⟨ 2 k + 1, old ⟩$ .

Next suppose o is $⟨ 2 k + 1, off ⟩$ . In this case, we will show that $Γ_{2} (A_{1}) ⊈ X_{2}$ . By assumption on o (and the fact that there are only finitely many backup strategies β and numbers b such that the age of $y_{b}^{β}$ in $Γ_{2} (A_{1})$ is ever less than $2 k + 1$ ), there are a backup strategy β, a number b, and a number $m < 2 k + 1$ such that at infinitely many stages s at which we visit α, we have that
the age of $y_{b}^{β}$ in $Γ_{2, s} (A_{1, s})$ is less than $2 k + 1$ ;

m is one of the markers $m_{b}^{β}$ that β associates with b; and

$m \notin Γ_{0, t} (A_{1, t})$ for some $t \in [s_{k}, s]$ .
It follows that $y_{b}^{β} \in Γ_{2} (A_{1})$ and $m \notin Γ_{0} (A_{1})$ . Since o is $⟨ 2 k + 1, off ⟩$ , we have $b \notin A_{0}$ . We will show that $y_{b}^{β} \notin X_{2}$ . The only $Φ_{2}$ -axiom enumerated by β for $y_{b}^{β}$ has use ${b}$ , so it is not valid. Furthermore, one can show that β is the only strategy that adds elements into $X_{2}^{[s_{β}]}$ . The proof is similar to that for α and $X_{1}^{[s_{α}]}$ : Note that while β may not be along the true path, its immediate predecessor α is along the true path and therefore so are all of its predecessors. We have shown that $y_{b}^{β} \in Γ_{2} (A_{1}) ∖ X_{2}$ .

To show that $X_{1}^{[s_{α}]}$ is finite, note that for all but finitely many stages when we visit α, the age of $y_{b}^{β}$ in $Γ_{2} (A_{1})$ is smaller than the age of the oldest disagreement between $A_{1}$ and $Ψ_{1} (A_{2})$ . At such stages, if α enumerates a $Φ_{1}$ -axiom, its use contains the use $G_{m}$ of a $Γ_{0}$ -axiom for m. Since $m \notin Γ_{0} (A_{1})$ , it follows that α only enumerates finitely many valid $Φ_{1}$ -axioms. Therefore, $X_{1}^{[s_{α}]}$ is finite (as α is the only strategy which adds elements into $X_{1}^{[s_{α}]}$ ). This completes the proof of (4).

To prove (5), suppose that o is $⟨ 2 k + 1, new ⟩$ . To show that $R_{Γ_{0}}$ is satisfied, we will show that $X_{0} ⊈ Γ_{0} (A_{1})$ . Fix β, b and m, following the analysis in the case where o is $⟨ 2 k + 1, off ⟩$ . As before, we have $m \notin Γ_{0} (A_{1})$ . However, since o is $⟨ 2 k + 1, new ⟩$ , we have $b \in A_{0}$ . Since we enumerated the $Φ_{0}$ -axiom $⟨ m, {b} ⟩$ when associating m with b, it follows that $m \in X_{0}$ . So $m \in X_{0} ∖ Γ_{0} (A_{1})$ .

To prove (6), suppose o is $⟨ 2 k + 1, backup ⟩$ . We have $x_{a} \notin Γ_{1} (A_{2})$ . To show that $x_{a} \in X_{1}$ , consider a stage $s^{'}$ large enough such that for all $s > s^{'}$ ,
if ${age}^{s} (b) ⩽ 2 k + 1$ , then $b \in A_{1}$ ;

if the age of z in $X_{2, s}$ is less than $2 k + 1$ , then $z \in X_{2} \cap Γ_{2} (A_{1})$ , and the use $G_{z}$ of the oldest valid $Γ_{2}$ -axiom for z has stabilized; and

if β is a backup strategy for α and the age of (the current value of) $y_{b}^{β}$ in $Γ_{2, s} (A_{1, s})$ is less than $2 k + 1$ , then

$y_{b}^{β}$ has stabilized and lies in $Γ_{2} (A_{1})$ ;

each $m_{b}^{β}$ lies in $Γ_{0} (A_{1})$ ; and

the use $G_{m_{b}^{β}}$ for the oldest valid $Γ_{0}$ -axiom for each $m_{b}^{β}$ has stabilized.
Such $s^{'}$ exists because o is $⟨ 2 k + 1, backup ⟩$ . At any stage $s > s^{'}$ at which we visit α, we would enumerate a valid $Φ_{1}$ -axiom for $x_{a}$ . We conclude that $x_{a} \in X_{1} ∖ Γ_{1} (A_{2})$ as desired.

B. Since $β ≺ f$ , there is a least stage at which β is visited after its final initialization. At this stage, $s_{β}$ receives its final value, proving (1). By construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction. One can show that β is the only strategy that adds elements into $X_{0}^{[s_{β}]}$ , and if t is a previous value of $s_{β}$ , then no strategy adds elements into $X_{0}^{[t]}$ after stage $s_{β}$ . It follows that $X_{0}^{[t]}$ is computable for every previous value t of $s_{β}$ .

Let $Ψ_{0} = ⋃_{s > s_{β}} Ψ_{0, s}$ be the enumeration operator constructed by β. By assumption, $A_{0} ≰_{e} A_{1}$ , hence $Ψ_{0} (A_{1}) \neq A_{0}$ . Let b be the oldest disagreement between $Ψ_{0} (A_{1})$ and $A_{0}$ . Following similar reasoning as that for α, there is a leftmost outcome o of the form $⟨ 2 l, off ⟩$ , $⟨ 2 l, new ⟩$ or $⟨ 2 l + 1 ⟩$ which is visited at infinitely many stages, proving (2).

To prove (3), we begin by showing that $m_{b}^{β}$ stabilizes. Once $s_{β}$ and ${age}^{s} (b)$ have stabilized, the only way that $m_{b}^{β}$ changes is if some $b^{'}$ with ${age}^{s^{'}} (b^{'}) < 2 l$ is the oldest disagreement between $A_{0, s^{'}}$ and $Ψ_{0, s^{'}} (A_{1, s^{'}})$ . At such a stage $s^{'}$ , the current outcome of β would be to the left of o. This only occurs finitely often, proving that $m_{b}^{β}$ stabilizes. Then all numbers greater than $m_{b}^{β}$ in the $s_{β}$ -th column of $N$ will eventually be dumped into $X_{0}$ , implying that $X_{0}^{[s_{β}]}$ is cofinite. As for older values of $s_{β}$ , we mentioned above that the corresponding columns of $X_{0}$ are computable.

To prove (4), first note that by A(6), $R_{Γ_{0}, Γ_{1}}$ is satisfied. It remains to show that for every value of $s_{α}$ , the set $X_{1}^{[s_{α}]}$ is finite. As reasoned above, it suffices to show that α only enumerates valid $Φ_{1}$ -axioms for finitely many elements in $X_{1}^{[s_{α}]}$ , where $s_{α}$ has stabilized. The proof differs depending on whether o is $⟨ 2 l, off ⟩$ or $⟨ 2 l + 1 ⟩$ .

Suppose o is $⟨ 2 l, off ⟩$ . We have $b \in Ψ_{0} (A_{1}) ∖ A_{0}$ and $m_{b}^{β} \notin Γ_{0} (A_{1})$ . By β’s construction of $Ψ_{0}$ , we have $y_{b}^{β} \in Γ_{2} (A_{1})$ (via an axiom with the same use as a $Ψ_{0}$ -axiom for b). Let t be the age of $y_{b}^{β}$ in $Γ_{2} (A_{1})$ . Consider any stage s such that $s_{α}$ , $s_{β}$ , the age of $y_{b}^{β}$ in $Γ_{2} (A_{1})$ , and $m_{b}^{β}$ all have stabilized. Suppose α enumerates a $Φ_{1}$ -axiom for some $x_{a^{'}}$ at stage s. Then $a^{'}$ is the oldest disagreement between $A_{1, s}$ and $Ψ_{1, s} (A_{2, s})$ . Furthermore, if $t, m_{b}^{β} < {age}^{s} (a^{'})$ , then the use of the $Φ_{1}$ -axiom enumerated by α contains the use of a $Γ_{0}$ -axiom for $m_{b}^{β}$ , rendering it invalid (because $m_{b}^{β} \notin Γ_{0} (A_{1})$ ). But there are only finitely many $a^{'}$ for which there is some s such that ${age}^{s} (a^{'}) ⩽ max {t, m_{b}^{β}}$ , so α can only enumerate valid $Φ_{1}$ -axioms for finitely many $x_{a^{'}}$ as desired.

If o is $⟨ 2 l + 1 ⟩$ , the analysis proceeds similarly but with $y_{b}^{β}$ instead of $m_{b}^{β}$ . In this case, we have that $b \in A_{0} ∖ Ψ_{0} (A_{1})$ and $y_{b}^{β} \notin Γ_{2} (A_{1})$ . By β’s construction of $X_{2}$ , we have $y_{b}^{β} \in X_{2}$ via $⟨ y_{b}^{β}, {b} ⟩ \in Φ_{2}$ . Let t be the age of $y_{b}^{β}$ in $X_{2}$ . Consider any stage s such that $s_{α}$ , $s_{β}$ and the age of $y_{b}^{β}$ in $X_{2}$ all have stabilized. Suppose α enumerates a $Φ_{1}$ -axiom for some $x_{a^{'}}$ at stage s. Then $a^{'}$ is the oldest disagreement between $A_{1, s}$ and $Ψ_{1, s} (A_{2, s})$ . Furthermore, if $t < {age}^{s} (a^{'})$ , then the use of the $Φ_{1}$ -axiom enumerated by α contains the use of a $Γ_{2}$ -axiom for $y_{b}^{β}$ , rendering it invalid (because $y_{b}^{β} \notin Γ_{2} (A_{1})$ ). But there are only finitely many $a^{'}$ for which there is some s such that ${age}^{s} (a^{'}) ⩽ t$ , so α can only enumerate valid $Φ_{1}$ -axioms for finitely many $x_{a^{'}}$ as desired. This completes the proof of (4).

To prove (5), suppose o is $⟨ 2 l, new ⟩$ . We will show that $m_{b}^{β} \in Γ_{0} (A_{1}) ∖ X_{0}$ . Since o is $⟨ 2 l, new ⟩$ , we have $m_{b}^{β} \in Γ_{0} (A_{1})$ . To show that $m_{b}^{β} \notin X_{0}$ , note first that the only $Φ_{0}$ -axiom enumerated by β for $m_{b}^{β}$ has use ${b}$ , so it is not valid. Furthermore, as mentioned above, β is the only strategy that adds elements into $X_{0}^{[s_{β}]}$ , so $m_{b}^{β} \notin X_{0}$ . This completes the proof of (5).

C. We will prove (1)–(3) in the case where γ is an $S_{Δ_{0}}$ -strategy. Then we will sketch how to modify the proof to address the $S_{Γ_{0}, Δ_{1}}$ - and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies.

Since $γ ≺ f$ , there is a least stage at which γ is visited after its final initialization. At this stage, $s_{γ}$ receives its final value, proving (1). By construction, we interrupt this stage so that no other strategy has the same parameter at any point during the construction.

Consider the sequence of good stages s, i.e., stages at which $A_{0, s} \subseteq A_{0}$ . This sequence is infinite because ${A_{0, s}}_{s \in ω}$ is a good approximation to $A_{0}$ . We claim that the length of agreement $l_{γ, s}$ between $A_{0, s}$ and $Δ_{0} (X_{0, s})$ is bounded on this sequence. Towards a contradiction, suppose not. We begin by showing that $Δ_{0} (X_{0}) = A_{0}$ : First, if $a \in A_{0}$ , then pick a good stage s such that $a \in A_{0, s}$ and $l_{γ, s} > a$ . Then $a \in Δ_{0} (X_{0, s}) \subseteq Δ_{0} (X_{0})$ . Conversely, if $a \in Δ_{0} (X_{0})$ , then pick a good stage s such that $a \in Δ_{0} (X_{0, s})$ and $l_{γ, s} > a$ . Then $a \in A_{0, s} \subseteq A_{0}$ as desired.

Next, we shall show that $Δ_{0} (X_{0}) = Δ_{0} (X_{0}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ . The forward inclusion is trivial. To prove the backwards inclusion, consider $n \in Δ_{0} (X_{0}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ . Let $⟨ n, F ⟩$ be the oldest $Δ_{0}$ -axiom putting n into $Δ_{0} (X_{0}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ . Pick a good stage $s > s_{γ}$ such that $F^{[< s_{γ}]}$ is permanently in $X_{0}$ and $l_{γ, s} > n$ . When we first visit γ at some stage $s^{'} ⩾ s$ , we enumerate a $Φ_{0}$ -axiom $⟨ ⟨ r, x ⟩, A_{0, s^{'}} ⟩$ for each $⟨ r, x ⟩ \in F^{[⩾ s_{γ}]}$ . By the way that γ adjusts the approximation to $A_{0}$ , we have $A_{0, s^{'}} \subseteq A_{0, s} \subseteq A_{0}$ . Therefore, $F \subseteq X_{0}$ , implying that $n \in Δ_{0} (X_{0})$ . This proves the reverse inclusion.

By inductive hypotheses B(3) and C(2), $X_{0}^{[< s_{γ}]}$ is computable, because the only strategies that contribute elements to $X_{0}^{[< s_{γ}]}$ after stage $s_{γ}$ are backup strategies $β ≺ γ$ or $S_{Δ_{0}^{'}}$ -strategies $γ^{'} ≺ γ$ . The equality proved in the previous paragraph then implies that $Δ_{0} (X_{0})$ , and hence $A_{0}$ , is c.e., contradicting our assumption on $A_{0}$ . Therefore $l_{γ, s}$ is bounded on the sequence of good stages s. Fix a bound $l_{γ}$ . Using this, we will prove (1) and (2). First note that γ can only contribute numbers to $X_{0}$ at good stages, because every $Φ_{0}$ -axiom enumerated by γ at stage s has use $A_{0, s}$ . This means that only numbers $n ⩽ l_{γ}$ can cause γ to enumerate valid $Φ_{0}$ -axioms. If $n \notin Δ_{0} (X_{0}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ , then $n \notin Δ_{0, s} (X_{0, s}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ at good stages, so n will not cause γ to enumerate any valid $Φ_{0}$ -axioms. As for $n \in Δ_{0} (X_{0}^{[< s_{γ}]} \cup N^{[⩾ s_{γ}]})$ , the oldest valid $Δ_{0}$ -axiom for n will appear to be the oldest valid axiom at all sufficiently large good stages, because we are working with a good approximation to $A_{0}$ . Therefore, at all sufficiently large good stages, γ does not enumerate any valid $Φ_{0}$ -axioms not already in $Φ_{0}$ . This proves that γ enumerates only finitely many elements into $X_{0}$ . Let $D = D_{k}$ be the set of these elements. To prove (1) and (2), it remains to show that $⟨ k ⟩$ is the leftmost outcome that γ visits at infinitely many stages. Consider a stage s after which D lies permanently in $X_{0}$ . At any γ-true stage $s^{'} ⩾ s$ , γ’s current outcome $⟨ k^{'} ⟩$ satisfies $D_{k} \subseteq D_{k^{'}}$ . This implies that $⟨ k ⟩ ⩽_{L} ⟨ k^{'} ⟩$ . By the adjustment that γ makes to the approximation of $A_{0}$ , we know that γ is visited at infinitely many good stages. At all such stages (after stage s), γ will have outcome $⟨ k ⟩$ . This proves (1) and (2).

Finally, to prove (3), we show that there is $n ⩽ l_{γ}$ such that $A_{0} (n) \neq Δ_{0} (X_{0}) (n)$ . Assume that this is not the case. Fix a stage s such that for all $s^{'} ⩾ s$ and each $n ⩽ l_{γ}$ in $A_{0} \cap Δ_{0} (X_{0})$ , we have $n \in A_{0, s^{'}} \cap Δ_{0, s^{'}} (X_{0, s^{'}})$ . Consider any good stage $s^{'} ⩾ s$ at which we visit γ. If $n \notin A_{0} \cap Δ_{0} (X_{0})$ , then we must have $n \notin A_{0, s^{'}} \cup Δ_{0, s^{'}} (X_{0, s^{'}})$ . So $l_{γ, s^{'}} > l_{γ}$ , contradicting our choice of $l_{γ}$ .

This proves (1)–(3) in the case where γ is an $S_{Δ_{0}}$ -strategy. As for the $S_{Γ_{0}, Δ_{1}}$ - and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategies, most of the above proof goes through if we simply replace $A_{0}$ , $Δ_{0}$ , and $X_{0}$ by the appropriate sets or operators. The only nontrivial change is in proving that $X_{1}^{[< s_{γ}]}$ is computable (for $S_{Γ_{0}, Δ_{1}}$ ) or $X_{2}^{[< s_{γ}]}$ is computable (for $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ ), respectively. To prove the former, apply inductive hypotheses A(3), A(4), B(4), and C(2). Note that A(5) and B(5) are not relevant because any strategy above γ with such a true outcome works with a different version of $X_{1}$ . To prove the latter, apply inductive hypothesis C(2). Any backup strategy above γ works with a different version of $X_{2}$ , so we are not concerned with it. □
Lemma 3.3.
One of the following holds:
All requirements $R_{Γ_{0}}$ and $S_{Δ_{0}}$ are satisfied.

There is some operator $Γ_{0}$ such that all requirements $R_{Γ_{0}, Γ_{1}}$ and $S_{Γ_{0}, Δ_{1}}$ are satisfied.

There are operators $Γ_{0}$ and $Γ_{1}$ such that all requirements $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ are satisfied.

Proof.
First, suppose there are infinitely many $R_{Γ_{0}}$ -strategies along the true path f. By construction of the tree of strategies, there must be infinitely many $S_{Δ_{0}}$ -strategies along f as well. Thus all $S_{Δ_{0}}$ -strategies are assigned to nodes on the true path and hence are satisfied. To show that $R_{Γ_{0}}$ is satisfied, fix an $R_{Γ_{0}}$ -strategy $α ≺ f$ . Let γ be the next $S_{Δ_{0}}$ -strategy along f. By construction of the tree of strategies, γ’s immediate predecessor is either an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy with true outcome of the form $⟨ 2 k + 1, new ⟩$ , or a backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy with true outcome of the form $⟨ 2 l, new ⟩$ . In both cases, the previous lemma shows that $R_{Γ_{0}}$ is satisfied.

Second, if there are only finitely many $R_{Γ_{0}}$ -strategies along f, fix $α ≺ f$ and $Γ_{0}$ such that α is an $R_{Γ_{0}}$ -strategy and no immediate successor of α is an $R_{Γ_{0}^{'}}$ -strategy. If there are infinitely many $R_{Γ_{0}, Γ_{1}}$ -strategies along f, we claim that all requirements $R_{Γ_{0}, Γ_{1}}$ and $S_{Γ_{0}, Δ_{1}}$ are satisfied. By construction of the tree of strategies, there must be infinitely many $S_{Γ_{0}, Δ_{1}}$ -strategies along f. Thus all $S_{Γ_{0}, Δ_{1}}$ -strategies are assigned to nodes on the true path and hence are satisfied. To show that $R_{Γ_{0}, Γ_{1}}$ is satisfied, fix an $R_{Γ_{0}, Γ_{1}}$ -strategy $β ≺ f$ extending α. Let δ be the next $S_{Γ_{0}, Δ_{1}}$ -strategy along f. By construction of the tree of strategies, δ’s immediate predecessor is either an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy with true outcome of the form $⟨ 2 k ⟩$ , or a backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy with true outcome of the form $⟨ 2 l, off ⟩$ or $⟨ 2 l + 1 ⟩$ . In each case, the previous lemma shows that $R_{Γ_{0}, Γ_{1}}$ is satisfied. This proves our claim.

Finally, suppose there are only finitely many $R_{Γ_{0}, Γ_{1}}$ -strategies along f. Fix $α^{'} ≺ f$ extending α and $Γ_{1}$ such that $α^{'}$ is an $R_{Γ_{0}, Γ_{1}}$ -strategy and no immediate successor of $α^{'}$ is an $R_{Γ_{0}, Γ_{1}^{'}}$ -strategy. (Such $α^{'}$ exists because α’s only immediate successor, which must lie along f, is an $R_{Γ_{0}, Γ_{1}}$ -strategy.) Then no immediate successor of α along f can be a backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy, so every immediate successor of $α^{'}$ along f is either an $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ -strategy with true outcome of the form $⟨ 2 k + 1, old ⟩$ or $⟨ 2 k + 1, off ⟩$ , or an $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ -strategy. By the previous lemma and the design of the tree, all requirements $R_{Γ_{0}, Γ_{1}, Γ_{2}}$ and $S_{Γ_{0}, Γ_{1}, Δ_{2}}$ are satisfied. □

4. A weak Ahmad triple

In the previous section, we saw that an Ahmad triple is not possible in the $Σ_{2}^{0}$ -enumeration degrees. In this section, we show a positive result, the existence of what we call a weak Ahmad triple.

Theorem 4.1.
There are pairwise incomparable $Δ_{2}^{0}$ -enumeration degrees $a_{1}$ , $a_{2}$ , and $a_{3}$ such that
there are $Δ_{2}^{0}$ -degrees $a_{12} ≰ a_{3}$ and $a_{23} ≰ a_{1}$ with $a_{12} \lor a_{23} = a_{2}$ ; and

for every $Σ_{2}^{0}$ -degree $x < a_{2}$ , we have that either $x ⩽ a_{1}$ or $x ⩽ a_{3}$ .
We call such a triple of degrees $a_{1}$ , $a_{2}$ , and $a_{3}$ a weak Ahmad triple.

4.1. Requirements

We will construct $Δ_{2}^{0}$ -sets $A_{1}$ , $A_{3}$ , $A_{12}$ , and $A_{23}$ satisfying the following list of requirements for every natural number e: $\begin{array}{l} N_{e}^{12} : A_{12} \neq Θ_{e} (A_{3} \oplus A_{23}); \\ N_{e}^{23} : A_{23} \neq Θ_{e} (A_{1} \oplus A_{12}); \\ R_{e}^{1} : X = Φ_{e} (A_{12} \oplus A_{23}) \Rightarrow (\exists Γ) [X = Γ (A_{1} \oplus A_{12})] or (\exists Δ) [A_{23} = Δ (X)]; \\ R_{e}^{3} : Y = Ψ_{e} (A_{12} \oplus A_{23}) \Rightarrow (\exists Γ) [Y = Γ (A_{3} \oplus A_{23})] or (\exists Δ) [A_{12} = Δ (Y)] . \end{array}$

Then $a_{1} = {deg}_{e} (A_{1} \oplus A_{12})$ , $a_{2} = {deg}_{e} (A_{12} \oplus A_{23})$ , and $a_{3} = {deg}_{e} (A_{3} \oplus A_{23})$ clearly satisfy clauses (1) and (2) of the theorem: Indeed, if $Z ⩽_{e} A_{12} \oplus A_{23}$ , then Z will take the role of X for some requirement $R_{e}^{1}$ and the role of Y for some requirement $R_{e^{'}}^{3}$ . If either requirement is satisfied by the first disjunct, then we know that $Z ⩽_{e} A_{1} \oplus A_{12}$ or $Z ⩽_{e} A_{3} \oplus A_{23}$ , respectively. Otherwise, we have that both $A_{12} ⩽_{e} Z$ and $A_{23} ⩽_{e} Z$ , and so $A_{12} \oplus A_{23} \equiv_{e} Z$ . Finally, by the definition of the degrees and by density, our requirements imply that $a_{1}$ , $a_{2}$ and $a_{3}$ are pairwise incomparable: Clearly, $a_{2} ≰ a_{j}$ for each $j \in {1, 3}$ by (1). Similarly, $a_{j} ⩽ a_{4 - j}$ for some $j \in {1, 3}$ contradicts (1). If $a_{j} < a_{2}$ for some $j \in {1, 3}$ , then fix x with $a_{j} < x < a_{2}$ , so $x ⩽ a_{4 - j}$ by (2), and in particular $a_{j} < a_{4 - j}$ , contradicting the last sentence.

The reader might recognize the $R$ -requirements to be very similar to the requirements for making an Ahmad pair. Indeed, we can think of $R_{e}^{1}$ as being the strategy making $(A_{23}, A_{1})$ an Ahmad pair “relative” to $A_{12}$ , while $R_{e}^{3}$ is the strategy making $(A_{12}, A_{3})$ an Ahmad pair “relative” to $A_{23}$ . In fact, as we will see, the addition of $A_{12}$ to the oracle in $R_{e}^{1}$ will not pose additional difficulties, and a similar Ahmad pair strategy can be used.

4.2. Naive description of the strategies

We start by briefly outlining naive strategies to satisfy each requirement and then discuss how to modify them in order to avoid conflicts between them. The construction shares many similarities with the usual construction of an Ahmad pair on a tree. We will use the usual setup of a tree of strategies ordered by priority.

An $N$ -requirement $N^{12}$ , say, is satisfied using a standard Friedberg–Muchnik strategy α: It picks a witness $z_{α}$ and enumerates it into $A_{12}$ . It waits to see if this witness will ever enter the set $Θ_{α} (A_{3} \oplus A_{23})$ . It wins if this never happens, provided that $z_{α}$ remains in $A_{12}$ . If $z_{α} \in Θ_{α} (A_{3} \oplus A_{23})$ , we say that $z_{α}$ is realized. In that case, α can win by extracting $z_{α}$ from $A_{12}$ and ensuring that $z_{α}$ will remain in $Θ_{α} (A_{3} \oplus A_{23})$ by imposing a finite restraint on the sets $A_{3}$ and $A_{23}$ .

Of course, this puts $N^{12}$ -strategies and $N^{23}$ -strategies in conflict, and so already we see the need for a priority ordering between strategies. This is an easy obstacle to deal with. The complexity of our construction will only be revealed once we think about the $R$ -strategies as well.

Consider an $R$ -requirement $R^{3}$ , say, and its strategy β. Its initial goal is to build the operator $Γ_{β}$ so that $Γ_{β} (A_{3} \oplus A_{23}) = Y_{β}$ , where $Y_{β} = Ψ_{β} (A_{12} \oplus A_{23})$ . When activated at stage s, for every natural number $n < s$ , it checks whether $n \in Y_{β} ∖ Γ_{β} (A_{3} \oplus A_{23})$ , and if so, it enumerates a new axiom $⟨ n, D ⟩$ into $Γ_{β}$ , where D contains a fresh number $a_{3} (n)$ that we enumerate into $A_{3}$ . If, on the other hand, $n \in Γ_{β} (A_{3} \oplus A_{23}) ∖ Y_{β}$ , then the strategy invalidates all valid axioms for n by extracting from $A_{3}$ the corresponding marker $a_{3} (n)$ . A new fresh value is then picked for $a_{3} (n)$ to use in the next Γ-axiom. (This allows us to keep our sets $Δ_{2}^{0}$ .)

The $R^{1}$ - and $R^{3}$ -strategies do not interfere with each other: They modify the sets $A_{1}$ and $A_{3}$ , respectively; however, $R^{1}$ -strategies do not involve the set $A_{3}$ , and $R^{3}$ -strategies do not involve the set $A_{1}$ . $R$ -strategies do not interfere with higher priority $N$ -strategies, as our priority tree will ensure that whenever an $N$ -strategy imposes a restraint, all lower-priority strategies are initialized and choose all of their parameters (specifically, numbers or witnesses they might later on like to extract from some set) as fresh numbers, larger than any number seen in the construction so far. An $N^{12}$ -strategy does not directly interfere with $R^{1}$ -strategies of higher priority: Its extraction of the witness z from $A_{12}$ may cause some x to leave X. However, our design of the axioms that are enumerated into $Γ_{1}$ will guarantee in that case that x will also leave $Γ_{1} (A_{1} \oplus A_{12})$ , and hence the $R^{1}$ -strategy will not even have to act in response.

The situation is quite different, unfortunately, when one considers how the extraction of $z_{α}$ from $A_{12}$ by an $N^{12}$ -strategy α affects a higher-priority $R^{3}$ -strategy β: In that case as well, some y may be forced out of $Y_{β}$ through this extraction, and so β will react by extracting $a_{3} (y)$ from $A_{3}$ . This action, however, might directly interfere with the restraint that α is trying to impose on $A_{3}$ in order to keep $z_{α} \in Θ_{α} (A_{3} \oplus A_{23})$ . In order to deal with this problem, we will need to modify our strategies.

4.3. An $N$ -strategy working below a single $R$ -strategy

For simplicity, we describe first the actions and outcomes of an $N^{12}$ -strategy α with one $R^{3}$ -strategy β of higher priority working above it. In the formal construction below, we will deal with the more general case.

The $N^{12}$ -strategy α will start by defining a threshold $d_{α}$ to be larger than any number mentioned so far. This threshold is meant to allow the $R$ -strategy β enough room to satisfy its requirement. If $Γ_{β} (A_{3} \oplus A_{23})$ changes its value on a number $x ⩽ d_{α}$ , then α will be restarted. So α can assume that $Γ_{β} (A_{3} \oplus A_{23})$ does not change below $d_{α}$ and hence $A_{3}$ does not change on any $a_{3} (n)$ for $n ⩽ d_{α}$ . From this point on, α (temporarily) takes over control of the operator $Γ_{β}$ : It defines a killing point $k_{α}$ as a fresh number and enumerates it into $A_{3}$ . It will require that the strategy β adds this killing point to the axiom that it enumerates into $Γ_{β}$ for any $x ⩾ d_{α}$ . Whenever α is restarted, all parameters that α had at the previous stage will be canceled except for the threshold $d_{α}$ and the killing point $k_{α}$ . The killing point $k_{α}$ is extracted from $A_{3}$ (thereby invalidating all axioms that were enumerated into $Γ_{β}$ for any element $x ⩾ d_{α}$ ). Finally, a new value for $k_{α}$ will be set – a fresh number, not seen in the construction so far, and this fresh number is added to $A_{3}$ . Note that (assuming $Γ_{β} (A_{3} \oplus A_{23}) ↾ d_{α}$ changes finitely often, which is something we will prove in Lemma 4.4), this restart can happen at most finitely often.

The strategy α has three outcomes, $stop <_{L} \infty <_{L} wait$ . Once it has completed its initial setup (defining thresholds and killing points), the strategy picks a witness $z_{α}$ as a fresh number and enumerates it into $A_{12}$ as before. It waits to see if $z_{α}$ becomes realized, and while waiting, the strategy has its rightmost outcome $wait$ . Suppose $z_{α}$ enters $Θ_{α} (A_{3} \oplus A_{23})$ via an axiom $⟨ z_{α}, E_{z_{α}} \oplus X ⟩$ . The strategy first checks if it can extract $z_{α}$ without causing $Γ_{β}$ -correction that will extract from $A_{3}$ some number in $E_{z_{α}}$ . At this point, the strategy is willing to sacrifice all other setups that it has made so far and enumerate into $A_{12}$ and $A_{23}$ as many numbers as necessary in order to guarantee this, with the exception of a certain pair of finite sets $R^{12}$ and $R^{23}$ consisting of witnesses selected by higher-priority strategies and kept out of their corresponding set. So if it is possible to add to $A_{12}$ and $A_{23}$ some finite set of numbers that make the extraction of $z_{α}$ essentially harmless, then the strategy extracts $z_{α}$ from $A_{12}$ and takes outcome $stop$ , where it will remain forever (unless initialized or restarted).

Suppose that this is not possible. In this case, the strategy α gives up on the witness $z_{α}$ (at least for now) and decides to prove that β’s requirement is satisfied by initiating the construction of Δ so that $Δ (Y_{β}) = A_{12}$ . We say that α switches β from Γ to Δ. The fact that an extraction of $z_{α}$ from $A_{12}$ causes the extraction of a finite set $F_{z_{α}}$ from $Y_{β}$ can now be turned into the first axiom in Δ. We would like to have a stronger relationship: $z_{α} \in A_{12}$ if and only if $F_{z_{α}} \subseteq Y_{β}$ . Of course, currently there might be other numbers in $A_{12}$ and $A_{23}$ whose extraction may also cause $F_{z_{α}}$ to leave $Y_{β}$ . In order to remove their influence, we will dump into $A_{12}$ and $A_{23}$ , respectively, all numbers that were ever in $A_{12}$ or $A_{23}$ unless they belong to a higher-priority $N$ -strategy (i.e., are in $R^{12}$ or $R^{23}$ ) or a lower-priority $N$ -strategy $γ ⪰ α \hat{} \infty$ : We collect those elements in $P_{12}$ and $P_{23}$ . The act of dumping means that we enumerate these numbers into $A_{12}$ or $A_{23}$ , respectively, and never again allow them to leave these sets. (Note that any numbers controlled by strategies to the right of the outcome ∞ of α, or which will be replaced by new versions, can be dumped without harm.) We begin the construction of the operator Δ by enumerating the axiom $⟨ z_{α}, F_{z_{α}} ⟩$ , along with $⟨ x, \emptyset ⟩$ for every element x that is dumped into $A_{12}$ . At the end of this stage, we will visit the outcome ∞, but before we do so, we set things up for a new round: We extract the killing point $k_{α}$ from $A_{3}$ and redefine it as a fresh number. We record the parameters $⟨ z_{α}, E_{z_{α}}, F_{z_{α}} ⟩$ in a list W that we keep track of and then redefine the value of $z_{α}$ as a new fresh number. At the next visit, the strategy α will start a new attempt at diagonalization with this new witness, but it will keep an eye on the previous witness z and its parameters $E_{z}$ and $F_{z}$ . If it ever sees that by dumping into $A_{12}$ and $A_{23}$ elements outside of $R^{12} \cup R^{23}$ , it can restore $E_{z} \subseteq A_{3}$ and extract z from $A_{12}$ (and this extraction will not cause β to extract any element from $E_{z}$ back out of $A_{3}$ to correct $Γ_{β}$ ), then the strategy α will do so and take outcome $stop$ forever.

Below the outcome ∞ of α, we will have a duplicate strategy for every requirement of lower priority than β’s requirement, including the one that α failed to satisfy. These strategies will not have to worry about the strategy β any longer as its requirement is satisfied in a different way. Specifically, an $N^{12}$ -strategy γ will be able to employ the original Friedberg–Muchnik strategy with a couple of modifications: The witnesses that γ can use have to be the witnesses that α formerly used for its definition of Δ; these will be collected in a stream $S^{12}$ that α controls. Every time α has outcome ∞, it adds one more element to the stream $S^{12}$ . The strategy γ will wait for the stream to contain a currently unused witness z before it can carry on. It will then proceed as usual; however, it will only trust $A_{3}$ below the current killing point of α. So z will be realized if $z \in Θ_{γ} (A_{3} ↾ k_{α} \oplus A_{23})$ at the current stage. If ∞ is α’s true outcome, i.e., if α visits this outcome infinitely often, then β’s activity is pushed away by the extraction of the infinite unbounded sequence of killing points, thereby destroying $Γ_{β}$ as discussed above, but giving γ enough room to faithfully realize its witness. Note that since ${k_{α, s}}_{s < ω}$ is unbounded, we will still have that if the witness is never realized then it does not belong to $Θ_{γ} (A_{3} \oplus A_{23})$ . Finally, if γ succeeds in realizing a witness, then it extracts it from $A_{12}$ and declares victory with outcome $stop$ . This might have an unanticipated effect on the operator Δ that α is constructing. It is possible that an axiom for some number $z^{'} > z$ was enumerated into Δ under the assumption that z remains in $A_{12}$ . The extraction of z from $A_{12}$ may cause $F_{z^{'}}$ to not be a subset of $Y_{β}$ , even though $z^{'} \in A_{12}$ . To prevent complications in the operator Δ, we will in this case dump (and thus remove from the stream) all elements in the stream $S^{12}$ that entered the stream after z did.

A similar consideration has to be incorporated when an $N^{23}$ -strategy δ works below $α \hat{} \infty$ . For simplicity, we may assume that δ has no $R^{1}$ -strategy working above it. The strategy δ also operates a simple Friedberg–Muchnik strategy with the additional requirement that whenever it extracts a witness from $A_{23}$ , it must dump into $A_{12}$ (and thus remove from the stream) all witnesses that were put into the stream after δ defined its witness.

4.4. Strategies, parameters and the tree

We will describe the tree of strategies $T \subseteq {({0, wait, stop} \cup {\infty_{i} ∣ i < ω})}^{< ω}$ (which will be a finite-branching tree). We start with a priority ordering of all requirements of order type ω. To define the tree, we will make use of two other sets defined inductively as we move down the tree. We have a set $M_{σ}$ of nodes $≺ σ$ that have been killed, and a list $Q_{σ}$ of requirements that need to be assigned (or reassigned) to nodes $⪰ σ$ . The root of the tree will be assigned the highest-priority requirement, and we set $M_{\emptyset} = \emptyset$ and $Q_{\emptyset}$ to consist of all requirements. Suppose that we have assigned a requirement to a node σ in the tree. If this strategy is an $R_{j}^{i}$ -strategy, say, then it has only one immediate successor $σ \hat{} 0$ . We set $Q_{σ \hat{} 0} = Q_{σ} ∖ {R_{j}^{i}}$ and assign to $σ \hat{} 0$ the highest-priority requirement in the list $Q_{σ \hat{} 0}$ . We set $M_{σ \hat{} 0} = M_{σ}$ .

Suppose now that σ is assigned an $N$ -requirement, say, an $N_{e}^{12}$ -requirement. (The case $N_{e}^{23}$ is similar, but now conflicting with $R^{1}$ .) Let $δ_{0} ≺ δ_{1} ≺ \dots ≺ δ_{n}$ be all initial segments of σ to which we have assigned an $R^{3}$ -strategy and which are not in $M_{σ}$ . (We call such $δ_{j}$ alive at σ.) The strategy σ has $n + 3$ immediate successors, $\begin{matrix} σ \hat{} stop <_{L} σ \hat{} \infty_{0} <_{L} σ \hat{} \infty_{1} <_{L} \dots <_{L} σ \hat{} \infty_{n} <_{L} σ \hat{} wait . \end{matrix}$ We set $Q_{σ \hat{} wait} = Q_{σ \hat{} stop} = Q_{σ} ∖ {N_{e}^{12}}$ and assign to each of the nodes $σ \hat{} wait$ and $σ \hat{} stop$ the highest-priority requirement in this list. We also set $M_{σ \hat{} wait} = M_{σ \hat{} stop} = M_{σ}$ . For $i ⩽ n$ , we set $Q_{σ \hat{} \infty_{i}}$ to be $Q_{σ}$ , along with the requirements associated with $δ_{i + 1}, \dots, δ_{n}$ , and σ. We assign to $σ \hat{} \infty_{i}$ the highest-priority requirement in $Q_{σ \hat{} \infty_{i}}$ . We set $M_{σ \hat{} \infty_{i}} = M_{σ} \cup {δ_{i}, δ_{i + 1}, \dots, δ_{n}}$ .

Lemma 4.2.
Let h be an infinite path in the tree of strategies T. Every requirement $Q$ in our priority ordering is assigned to some node $σ ≺ h$ such that for every δ with $σ ≺ δ ≺ h$ , $Q$ is not in $Q_{δ}$ .
Proof.
We prove this statement by induction on the priority ordering of all requirements. Suppose that the statement is true for all requirements of higher priority than the requirement $Q$ , and let $σ^{'} ≺ h$ be least such that no requirement of higher priority than $Q$ enters $Q_{δ}$ where $σ^{'} ⪯ δ ≺ h$ , or is assigned to any such δ. It follows that $Q$ is assigned to some longest $σ ⪯ σ^{'}$ , and we have the following two cases:

Case 1: $Q = R_{j}^{i}$ . Fix the $R^{i}$ -strategies $δ_{0} ≺ δ_{1} \dots ≺ δ_{n} ≺ σ$ that are alive at σ. By our inductive hypothesis, if there is a least strategy $δ ≺ h$ extending σ that puts $Q$ into the list $Q_{δ}$ , then this strategy cannot kill $δ_{l}$ for any $l ⩽ n$ by our inductive assumptions. Thus only σ (and possibly strategies extending σ) are killed by δ, and so δ will be assigned the requirement $Q$ . Now, since no $R^{i}$ -requirement of higher priority than $Q$ will switch from Γ to Δ along h beyond δ, the requirement $Q$ cannot be added to $Q_{δ^{'}}$ for any $δ^{'}$ with $δ ≺ δ^{'} ≺ h$ ; as a consequence, there is also a longest $Q$ -strategy along h.

Case 2: $Q = N_{e}^{i j}$ , and by symmetry assume $i j = 12$ . Fix as usual the $R^{3}$ -strategies $δ_{0} ≺ δ_{1} \dots ≺ δ_{n} ≺ σ$ alive at σ. The strategy σ cannot put $Q$ into the set $Q_{σ \hat{} o}$ unless σ switches the outcome of $δ_{n}$ from Γ to Δ along h (since, by inductive hypothesis, no $δ_{l}$ can be killed along h anymore). But then $Q$ must be assigned to $σ \hat{} o$ and cannot be added to $Q_{δ^{'}}$ for any $δ^{'}$ with $δ ≺ δ^{'} ≺ h$ . □

An $R$ -strategy β has only its operator $Γ_{β}$ as a parameter. Initially (and after every initialization), we set $Γ_{β} = \emptyset$ . We will also refer to $Φ_{β} (A_{12} \oplus A_{23})$ as $X_{β}$ (in the case of an $R^{1}$ -strategy, and proceed similarly in the case of an $R^{3}$ -strategy.)

An $N^{12}$ -strategy α extending $R^{3}$ -strategies $β_{0} ≺ β_{1} ≺ \dots ≺ β_{n}$ still alive at α has a threshold $d_{α}$ , a set of killing points $k_{α}^{0} < \dots < k_{α}^{n}$ , a witness $z_{α}$ , a list of old witnesses $W_{α}$ , each component of which contains a number z, an index $i ⩽ n$ , two finite sets $E_{z}$ and $F_{z}$ , and enumeration operators $Δ_{β_{0}}$ , …, $Δ_{β_{n}}$ . Initially (and after every initialization), all of these parameters are undefined or empty. An $N^{23}$ -strategy γ has the same list of parameters with respect to all $R^{1}$ -strategies that are still alive at γ.

In addition, every strategy has two streams $S^{12}$ and $S^{23}$ . These streams are determined by the predecessor of every strategy. Whenever a strategy is canceled, most of the elements in its stream (except for possibly one element) will be dumped into the corresponding set $A_{12}$ or $A_{23}$ .
4.5. Construction

In our construction, we will build a sequence ${f_{s}}_{s < ω}$ . Each $f_{s}$ is a node of length s on our tree of strategies. Strategies visited at stage $s + 1$ will modify the values of their parameters, as well as the approximations to the sets $A_{12}$ , $A_{23}$ , $A_{1}$ and $A_{3}$ . Since our tree is finitely branching, there is a leftmost path of nodes visited at infinitely many stages, the true path. The intention is that for every requirement $Q$ , there is a strategy along the true path that satisfies $Q$ .

At stage 0, we set $A_{12} = A_{23} = A_{1} = A_{3} = \emptyset$ , and all parameters of all strategies are in initial state (either undefined or empty). All streams are empty.

At stage $s + 1$ , we always start by visiting the root of the tree, namely, $f_{s + 1} ↾ 0 = \emptyset$ . We add to the streams $S_{\emptyset}^{12}$ and $S_{\emptyset}^{23}$ of the root the element s. Suppose we have built $f_{s + 1} ↾ k$ along with its streams $S_{f_{s + 1} ↾ k}^{12}$ and $S_{f_{s + 1} ↾ k}^{23}$ . If we have added a new number to $S^{12}$ , then we denote it by $n^{12}$ . If we have added a new number to $S^{23}$ , then we denote it by $n^{23}$ . If $k = s + 1$ , then we are done with the construction of $f_{s + 1}$ : We initialize all strategies $δ > f_{s + 1}$ , dump their streams into $A_{12}$ and $A_{23}$ , respectively, empty their streams (i.e., set $S_{δ}^{12} = S_{δ}^{23} = \emptyset$ ), and move on to the next stage.

Otherwise, we have four cases depending on the requirement assigned to $f_{s + 1} ↾ k$ :

$f_{s + 1} ↾ k$ is an $R_{j}^{3}$ -strategy β: The strategy scans all $x ⩽ s$ .

If $x \in Y_{β} ∖ Γ_{β} (A_{3} \oplus A_{23})$ , then the strategy picks a fresh marker $a_{3} (x)$ and enumerates it into $A_{3}$ . Then it defines $K_{β}^{x}$ as the finite set of all β-killing points that belong to an $N^{12}$ -strategy $α ≻ β$ with current threshold $d_{α} ⩽ x$ . (Note that this is a finite set as there are currently only finitely many strategies that are not in initial state.) The strategy then enumerates into $Γ_{β}$ the axiom $⟨ x, ({a_{3} (x)} \cup K_{β}^{x}) \oplus A_{23} ↾ s ⟩$ .

If $x \in Γ_{β} (A_{3} \oplus A_{23}) ∖ Y_{β}$ , then the strategy extracts from $A_{3}$ all markers $a_{3} (x)$ that are in some valid axiom for x in $Γ_{β}$ .

Once the scan is over, the strategy defines the stream

S_{β \hat{} 0}^{12}

by adding to its previous value the number

n^{12}

and, similarly, the stream

S_{β \hat{} 0}^{23}

by adding to it the number

n^{23}

(if they exist). Then the strategy ends the substage with outcome 0.

$f_{s + 1} ↾ k$ is an $R_{j}^{1}$ -strategy. This case is dealt with analogously to the previous case.

$f_{s + 1} ↾ k$ is an $N_{e}^{12}$ -strategy α. Fix $β_{0} ≺ β_{1} ≺ \dots ≺ β_{n} ≺ α$ to be the $R^{3}$ -strategies alive at α. Let $K_{α}$ be the greatest lower bound of the set of all killing points $k_{γ}^{i}$ , where γ is an $N^{12}$ -strategy and $α ⪰ γ \hat{} \infty_{i}$ . Let $R^{12}$ and $R^{23}$ be the sets of witnesses currently used by higher-priority $N^{12}$ - and $N^{23}$ -strategies, respectively. Similarly, the sets $P_{12}^{i}$ and $P_{23}^{i}$ consist of the current witnesses of $N^{12}$ - and $N^{23}$ -strategies extending outcome $\infty_{i}$ .

If this is the first time that α is visited after initialization, then define the threshold $d_{α}$ to be fresh and large and the killing points $k_{α}^{0} < \dots < k_{α}^{n}$ as fresh numbers. Enumerate every killing point into $A_{3}$ . Then go to the first case which applies:

If $Γ_{β_{i}} (A_{3} \oplus A_{23}) ↾ d_{α}$ has changed since we last visited α, then cancel $z_{α}$ , $W_{α}$ and $Δ_{β_{i}}$ for every $i ⩽ n$ . Extract the killing points $k_{α}^{j}$ where $j ⩾ i$ from $A_{3}$ . Define new values for these killing points and enumerate them into $A_{3}$ . Initialize all strategies of lower priority than α. Dump the streams $S_{α}^{12}$ and $S_{α}^{23}$ into $A_{12}$ and $A_{23}$ , respectively. Set $S_{α \hat{} o}^{12} = S_{α \hat{} o}^{23} = \emptyset$ for every possible outcome o of α and end the substage with outcome $wait$ .

If the previous time when we visited α, it had outcome $stop$ , and α has not been initialized since, then let the outcome again be $stop$ . Define $S_{α \hat{} stop}^{12}$ and $S_{α \hat{} stop}^{23}$ by adding to them the number $n^{12}$ and $n^{23}$ , respectively (if they exist).

Scan the list of old witnesses $W_{α}$ . For each entry $⟨ z, i_{z}, E_{z}, F_{z} ⟩$ such that z has not yet been dumped into $A_{12}$ , check to see whether the number $i_{z}$ can be decreased: Find the least $j_{z}$ such that for every $i ⩾ j_{z}$ , if we enumerate back into $A_{3}$ the set $E_{z}$ , into $A_{12}$ every number $x \neq z$ such that $x ⩽ s$ and $x \notin R^{12} \cup ⋃_{j < j_{z}} P_{12}^{j}$ , and into $A_{23}$ every number $x ⩽ s$ that is not in the set $R^{23} \cup ⋃_{j < j_{z}} P_{23}^{j}$ , then $β_{i}$ will not be forced to extract from $A_{3}$ any number in $E_{z}$ during $Γ_{β_{i}}$ -correction. (In this case, we say that z is $Γ_{β_{i}}$ -cleared for $i ⩾ j_{z}$ .) If there are no witnesses with $j_{z} ⩽ i_{z}$ , then move on to step (d). Otherwise, among all witnesses with $j_{z} ⩽ i_{z}$ , pick the one with least $j_{z}$ , and among these the least z. Enumerate $E_{z}$ into $A_{3}$ , dump into $A_{12}$ every number $x \neq z$ such that $x ⩽ s$ and $x \notin R^{12} \cup ⋃_{j < j_{z}} P_{12}^{j}$ , and into $A_{23}$ every number $x ⩽ s$ such that $x \notin R^{23} \cup ⋃_{j < j_{z}} P_{23}^{j}$ . If $j_{z} = 0$ , then set $z_{α} = z$ , extract it from $A_{12}$ and end the substage with outcome $stop$ . Set $S_{α \hat{} o}^{12} = S_{α \hat{} o}^{23} = \emptyset$ for every possible outcome o of α and dump the elements that were in each stream into $A_{12}$ and $A_{23}$ , respectively.

Otherwise, if $j_{z} > 0$ , then set $i_{z} = j_{z} - 1$ . Let $F_{z} \subseteq Y_{β_{i_{z}}}$ be the set such that $z \in A_{12}$ if and only if $F_{z} \subseteq Y_{β_{i_{z}}}$ . Enumerate into $Δ_{β_{i_{z}}}$ the axiom $⟨ z, F_{z} ⟩$ . Update the record in $W_{α}$ to include $⟨ z, i_{z}, E_{z}, F_{z} ⟩$ . Extract the killing points $k_{α}^{j}$ where $j ⩾ i_{z}$ from $A_{3}$ , and end the substage with outcome $\infty_{i_{z}}$ . We set the streams $S_{α \hat{} o}^{12} = S_{α \hat{} o}^{23} = \emptyset$ for every outcome o of α that is to the right of $\infty_{i_{z}}$ and dump all elements that were in those streams except z into $A_{12}$ and $A_{23}$ , respectively. Dump $n^{12}$ into $A_{12}$ (if it exists). We leave $S_{α \hat{} o}^{12}$ and $S_{α \hat{} o}^{23}$ unchanged for every outcome o of α that is to the left of $\infty_{i_{z}}$ . We update $S_{α \hat{} \infty_{i_{z}}}^{12}$ by adding the number z to it, and $S_{α \hat{} \infty_{i_{z}}}^{23}$ by adding the number $n^{23}$ (if it exists) to it.

If no current witness is selected and $n^{12}$ exists and is larger than the current witness of every $N$ -strategy γ with $γ \hat{} wait ⪯ α$ or $γ \hat{} stop ⪯ α$ , then define $z_{α} = n^{12}$ and enumerate it into $A_{12}$ . Otherwise (if $n^{12}$ is defined but too small), dump $n^{12}$ into $A_{12}$ . End the substage with outcome $wait$ , leaving all streams of immediate successors of α unchanged.

If $z_{α} \notin Θ_{α} (A_{3} \oplus A_{23})$ or if $z_{α} \in Θ_{α} (A_{3} \oplus A_{23})$ but for every valid axiom $⟨ z_{α}, E \oplus D ⟩ \in Θ_{α}$ , we have that $max (E) ⩾ K_{α}$ , then end the substage with outcome $wait$ . Add $n^{12}$ into $S_{α \hat{} wait}^{12}$ and $n^{23}$ into $S_{α \hat{} wait}^{23}$ (if they exist). Leave all other streams of immediate successors of α unchanged.

If $z_{α} \in Θ_{α} (A_{3} \oplus A_{23})$ via an axiom $⟨ z_{α}, E \oplus D ⟩$ with $max (E) < K_{α}$ , then we add $⟨ z_{α}, n + 1, E, \emptyset ⟩$ to $W_{α}$ and go back to step (c). (Note that the current outcome will not be $wait$ , since in step (c), we are guaranteed to find some witness $j_{z} ⩽ n + 1$ .) We also cancel the value of the current witness so that at the next visit, if α passes through steps (a), (b) and (c), then it will go to step (d) and select a new value of the witness.

$f_{s + 1} ↾ k$ is an $N_{e}^{23}$ -strategy. This case is dealt with analogously to the previous case.

4.6. Verification

As anticipated, we have an infinite true path f of strategies on the tree consisting of the leftmost nodes visited at infinitely many stages. Our intention is to prove that nodes along this path satisfy their requirements. In order to prove that nodes on this path are initialized only finitely often, we must consider an $N$ -strategy on the true path and think about how many times it can be restarted, as that is the only reason, other than just visiting a node to the left of a strategy, that causes the initialization of strategies. We will prove, in Lemma 4.4, that for every $R^{3}$ -strategy $β ≺ f$ , the set $Γ_{β} (A_{3} \oplus A_{23})$ is $Δ_{2}^{0}$ , and similarly, for every $R^{1}$ -strategy $β^{'} ≺ f$ , the set $Γ_{β^{'}} (A_{1} \oplus A_{12})$ is $Δ_{2}^{0}$ . Throughout this proof, we will phrase various interactions between strategies for the pairs $R^{3}$ and $N^{12}$ . We note that the relationship between $R^{1}$ and $N^{23}$ is symmetric.

First, we point out a technical fact about streams that will be useful in the rest of the proof.

Lemma 4.3.

If n enters a stream of a strategy δ at stage s and δ was last visited or initialized at stage $s^{-}$ , then $n ⩾ s^{-}$ and n is larger than all previous elements of either stream of δ.

Proof.

The proof is an easy induction on the construction. The root is never initialized, and at stage $s + 1$ , $n_{\emptyset}^{12} = n_{\emptyset}^{23} = s$ , which is the last time the root was visited.

Suppose the statement is true about δ. If δ adds $n^{12}$ and $n^{23}$ to the stream of its immediate successor, then the statement clearly follows by induction, as we cannot initialize an immediate successor of δ without either visiting or initializing δ. So suppose that δ is an $N^{12}$ -strategy, say, and δ adds a witness z to the stream of $δ \hat{} \infty_{i}$ , as that is the only other case. In that case, the witness z was defined after $δ \hat{} \infty_{i}$ was last visited or initialized at stage t, as whenever we initialize or visit $δ \hat{} \infty_{i}$ , we initialize and empty the stream of all strategies $δ \hat{} \infty_{j}$ where $j > i$ . At the stage when z was defined, it was defined as $n_{δ}^{12}$ , which by induction is greater than or equal to the previous stage when δ was visited, and hence greater than or equal to t, and larger than any element in the stream of $δ \hat{} \infty_{i}$ . □

Lemma 4.4.

Let $β ≺ f$ be an $R^{3}$ -strategy. Suppose that α is an $N^{12}$ -strategy such that $β ≺ α ≺ f$ and β is alive at α. Let $d_{α}$ be a threshold of α. Then there is a stage s such that after stage s, the strategy β does not modify the set $Γ_{β} (A_{3} \oplus A_{23})$ below the threshold $d_{α}$ . Thus, in particular, if β is never killed along f then the set $Γ_{β} (A_{3} \oplus A_{23})$ is $Δ_{2}^{0}$ .

Proof.

We prove this theorem by induction on the priority of β and α. So towards a contradiction, suppose that the statement is false for a pair of strategies $β ≺ α ≺ f$ , and take the pair where α has highest priority. It follows from our choice of α that there is a least stage $s_{α}$ such that after stage $s_{α}$ , the strategy α (and hence β as well) is not initialized and never again changes the value of its threshold $d_{α}$ . At stage $s_{α}$ , the strategy α picks its killing points as fresh numbers, and hence they do not interfere with any axiom for any number $n ⩽ s_{α}$ in $Γ_{β}$ . After stage $s_{α}$ , every time $Γ_{β} (A_{3} \oplus A_{23})$ changes on some number $n ⩽ s_{α}$ , the strategy α is restarted. It chooses all parameters anew and initializes all lower-priority strategies. This means that if β enumerated a new axiom into $Γ_{β}$ for some $n ⩽ s_{α}$ such that $n \in Ψ_{β} (A_{12} \oplus A_{23})$ , then:

This axiom cannot be invalidated by any strategy γ of equal or lower priority than α, as $N^{12}$ -strategies are initialized or restarted and hence pick their killing points as fresh numbers larger than $a_{3} (n)$ and have thresholds larger than n (hence none of their killing points will be included by β in this axiom). $N^{23}$ -strategies have to pick their witnesses anew, from fresh streams, as their streams are emptied at the current stage. Hence these witnesses will be larger than the current stage and will not be included in the $A_{23}$ -portion of the axiom for n.

The axiom that made n enter $Ψ_{β} (A_{12} \oplus A_{23})$ uses (by our convention) only numbers smaller than the current stage and hence it will not be invalidated by any strategy of equal or lower priority than α, as these strategies are initialized and their streams are emptied. By Lemma 4.3, their streams will contain only numbers larger than the current stage, from which they will pick their witnesses.

No strategy of higher priority than α can invalidate either of these axioms, either: A higher-priority strategy extracts from

A_{12}

A_{23}

only at stages at which it, for the first time after initialization, has its leftmost outcome

stop

, which by our choice of

s_{α}

must happen before stage

s_{α}

. Similarly, after stage

s_{α}

, higher-priority strategies extract killing points only associated with

R

-strategies that they end up killing, and since β is alive at α, this cannot be β. Of course, all

A_{3}

-markers are different, so

R^{3}

-strategies do not interfere with each other.

It only takes finitely many stages for any number $n ⩽ d_{α}$ that ever enters $Ψ_{β} (A_{12} \oplus A_{23})$ to enter $Ψ_{β} (A_{12} \oplus A_{23})$ permanently, and hence after that stage, β will not need to modify $Γ_{β} (A_{3} \oplus A_{23})$ ever again. □

The lemma above has two easy but significant corollaries. The first corollary was already anticipated by us.

Corollary 4.5.

Every strategy along the true path is initialized at most finitely often. □

The second corollary gives us the satisfaction of $R$ -requirements in one case.

Corollary 4.6.

If $β ≺ f$ is an $R^{3}$ -strategy that is alive at every successor of β along the true path, then $Γ_{β} (A_{3} \oplus A_{23}) = Ψ_{β} (A_{12} \oplus A_{23})$ . The analogous statement for $R^{1}$ -strategies holds as well.

Proof.

Fix an $R^{3}$ -strategy $β ≺ f$ . Consider the $N^{12}$ -strategies $β ≺ α_{0} ≺ α_{1} ≺ \dots ≺ α_{n} ≺ \dots ≺ f$ along the true path. The sequence ${d_{α_{i}}}_{i < ω}$ of the final values of their thresholds, attained at the first true stage after the corresponding strategy stops being initialized, is an unbounded increasing sequence. By Lemma 4.4, for every i, there is a stage $s_{i}$ such that at all $t ⩾ s_{i}$ , the strategy β does not modify $Γ_{β} (A_{3} \oplus A_{23})$ on numbers less than $d_{α_{i}}$ , and hence, by β’s design, $Γ_{β} (A_{3} \oplus A_{23}) ↾ d_{α_{i}} = Ψ_{β} (A_{12} \oplus A_{23}) ↾ d_{α_{i}}$ at all stages $t ⩾ s_{i}$ . Furthermore, the proof of Lemma 4.4 actually gives us more: If $n ⩽ d_{α_{i}}$ is in $Ψ_{β} (A_{12} \oplus A_{23})$ at any β-true stage after $α_{i}$ selects its last threshold $d_{α_{i}}$ , then $n \in Γ_{β} (A_{3} \oplus A_{23}) \cap Ψ_{β} (A_{12} \oplus A_{23})$ . This gives us immediately that $Γ_{β} (A_{3} \oplus A_{23}) ↾ d_{α_{i}} = Ψ_{β} (A_{12} \oplus A_{23}) ↾ d_{α_{i}}$ and, by the unboundedness of ${d_{α_{i}}}_{i < ω}$ , the fact that $Γ_{β} (A_{3} \oplus A_{23}) = Ψ_{β} (A_{12} \oplus A_{23})$ . □

We next concentrate on the $N$ -requirements. To prove that each is eventually satisfied, we will first show that once a number is $Γ_{i}$ -cleared, it will remain $Γ_{i}$ -cleared at all future stages.

Lemma 4.7.

Fix an $N^{12}$ -strategy $α ≺ f$ below $R^{3}$ -strategies $β_{0} ≺ \dots ≺ β_{n}$ alive at α. If α moves a witness z from $S_{\infty_{j}}^{12}$ to $S_{\infty_{i}}^{12}$ , where $i < j$ , at a stage after α’s last initialization, then at any future stage, if z is extracted from $A_{12}$ and $E_{z}$ is enumerated back into $A_{3}$ , the strategy $β_{j}$ will not change $A_{3}$ to cause z to be extracted from $Γ_{β_{j}} (A_{3} \oplus A_{23})$ .

Proof.

Suppose that at stage s, the strategy α moves z from $S_{\infty_{j}}^{12}$ to $S_{\infty_{i}}^{12}$ , where $i < j$ . At this stage, it dumps into $A_{12}$ all numbers $x ⩽ s$ such that $x \notin {z} \cup R^{12} \cup ⋃_{i^{'} ⩽ i} P_{12}^{i^{'}}$ , and into $A_{23}$ all numbers $x ⩽ s$ such that $x \notin R^{23} \cup ⋃_{i^{'} ⩽ i} P_{23}^{i^{'}}$ . At stage s, we see that under these circumstances, the extraction of z from $A_{12}$ will not cause any number y that is currently in $Ψ_{β_{j}} (A_{12} \oplus A_{23})$ and that has an $A_{3}$ -marker $a_{3} (y) \in E_{z}$ to leave the set $Ψ_{β_{j}} (A_{12} \oplus A_{23})$ . Assuming that $(R^{12} \cup ⋃_{i^{'} ⩽ i} P_{12}^{i^{'}}) \cap A_{12}$ as seen at the current stage s remains a subset of $A_{12}$ , and that $(R^{23} \cup ⋃_{i^{'} ⩽ i} P_{23}^{i^{'}}) \cap A_{23}$ as seen at stage s remains a subset of $A_{23}$ , this will be true at future stages as well, as every strategy to the right of $α \hat{} \infty_{i}$ is initialized and will select its future witnesses from its stream that is currently empty and will by Lemma 4.3 in the future only have elements larger than any number mentioned before stage s, hence not be included in any axiom in $Ψ_{β_{j}}$ valid at stage s.

The only potential problem is that some strategy γ might, at a stage t, extract from $A_{12}$ a number y that is in the set $(R^{12} \cup ⋃_{i^{'} ⩽ i} P_{12}^{i^{'}}) \cap A_{12}$ at stage s, or from $A_{23}$ a number y that is in the set $(R^{23} \cup ⋃_{i^{'} ⩽ i} P_{23}^{i^{'}}) \cap A_{23}$ at stage s.

First note that if $y \in R^{12} \cup R^{23}$ , then y is the current witness of an $N$ -strategy $δ ≺ α$ . Since δ has no witness at stages when it has an infinite outcome, and its current witness is not in $A_{12}$ if it has outcome $stop$ , it follows that $δ \hat{} wait ⪯ α$ . This means that y remains the current witness of δ at all future stages and never enters another stream. No other strategy has access to it in order to extract it at stage t.

Suppose that $y \in P_{12}^{i^{'}}$ for $i^{'} ⩽ i$ . Let $δ ⪰ α \hat{} \infty_{i^{'}}$ be the strategy with witness y at stage s. Let γ be the strategy that extracts y at stage t. Once again, γ cannot have higher priority than α, or else α would be initialized. It follows that $γ = α$ , or else $γ ⪰ α \hat{} \infty_{k}$ , where $k ⩽ i^{'}$ , as all other strategies of lower priority than α are initialized at the stage when y was assigned to δ as a witness and thus have streams consisting of elements larger than y by Lemma 4.3. If $γ = α$ , then at stage t, the strategy α dumps all elements less than t that are not in ${y} \cup R^{12} \cup R^{23}$ into $A_{12}$ and $A_{23}$ , respectively, in particular z will be dumped. If $γ ⪰ α \hat{} \infty_{k}$ and $k ⩽ i$ , then consider the stage r at which y entered the stream of $α \hat{} \infty_{k}$ . Since at stage s, the number y is already in the stream of $α \hat{} \infty_{i^{'}}$ , and whenever a number switches streams, all streams associated with strategies to the right are dumped, we have that at stage r, the number z is dumped (z cannot already be in a stream to the left of or equal to $α \hat{} \infty_{k}$ at stage r, or else y would have been dumped before stage r). □

Lemma 4.8.

Every $N$ -requirement is satisfied.

Proof.

By symmetry, fix an $N_{e}^{12}$ -requirement, say. By Lemma 4.2, there is a strategy α along the true path that is assigned $N_{e}^{12}$ and such that no strategy σ extending α along the path f has $N_{e}^{12} \in Q_{σ}$ . It follows that $α \hat{} wait ≺ f$ or $α \hat{} stop ≺ f$ .

Let $s_{α}$ be the first stage after which α is not initialized. Recall that the number $K_{α}$ is defined as the greatest lower bound of the set of all killing points $k_{γ}^{i}$ , where γ is an $N^{12}$ -strategy and $α ⪰ γ \hat{} \infty_{i}$ . Every time that α is visited, this number has a larger value than at the previous visit. Furthermore, no $N$ -strategy of higher priority than α modifies $A_{3}$ on numbers $x ⩽ K_{α}$ . This is because when such an $N$ -strategy γ such that $γ \hat{} \infty_{i} ⪯ α$ has outcome $\infty_{i}$ , it extracts from $A_{3}$ all killing points $k_{γ}^{j}$ , where $j ⩾ i$ , and then it redefines them as fresh numbers. The strategy γ cannot extract any smaller killing point without initializing α.

So $A_{3} ↾ K_{α}$ can only be modified by an $R$ -strategy β above α. We note that such a strategy is necessarily alive at α. Indeed, if β is not alive above at α, then it is killed by a strategy γ such that $γ \hat{} \infty_{i} ⪯ α$ and β is γ’s j-th $R^{3}$ -strategy, where $j ⩾ i$ . Every time that γ has outcome $\infty_{i}$ , it extracts its j-th killing point from $A_{3}$ , thereby invalidating all axioms in $Γ_{β}$ for numbers $x ⩾ d_{γ}$ . After stage $s_{α}$ , the strategy β does not modify $Γ_{β} (A_{3} \oplus A_{23})$ on any number $x ⩽ d_{γ}$ , hence if it sees a valid axiom for some x that needs to be made invalid, then $x > d_{γ}$ . This axiom has marker $a_{3} (x) > k_{γ}^{j} ⩾ K_{α}$ .

If $α \hat{} wait ≺ f$ , then let $s ⩾ s_{α}$ be such that α has outcome $wait$ at every stage $t ⩾ s$ . After stage s, the strategy α will select its final witness $z_{α}$ . It follows from the construction that $z_{α}$ never enters $Θ_{α} (A_{3} \oplus A_{23})$ with an axiom that does not use any numbers larger than $K_{α}$ . Since the values of $K_{α}$ at α-true stages form an unbounded sequence, it follows that every axiom we ever see for $z_{α}$ in $Θ_{α} (A_{3} \oplus A_{23})$ is invalid at infinitely many stages. Hence $z_{α} \notin Θ_{α} (A_{3} \oplus A_{23})$ . As no strategy other than α can extract $z_{α}$ from $A_{12}$ , and $z_{α}$ is enumerated into $A_{12}$ at the stage when it is defined, it follows that $z_{α} \in A_{12} ∖ Θ_{α} (A_{3} \oplus A_{23})$ .

If, on the other hand, $α \hat{} stop ≺ f$ , then there is a stage $s ⩾ s_{α}$ such that α has outcome $stop$ for the first time at stage s. At this stage, α has found a witness z that is cleared by all higher priority $R^{3}$ -strategies that are alive at α. Note that $max (E_{z}) < K_{α}$ , and by Lemma 4.7, no strategy β that is alive at α will extract a marker from $A_{3}$ that is in $E_{z}$ . Every number that was in $A_{23}$ when the axiom for z in $Θ_{α}$ was found is dumped into $A_{23}$ at stage s (only elements that are in $R^{23}$ are preserved; however, they cannot have been in $R^{23}$ when z was realized and not be in $R^{23}$ later unless α is initialized). It follows that $z \in Θ_{α} (A_{3} \oplus A_{23}) ∖ A_{12}$ . □

The final lemma that we present handles the case when an $R$ -requirement is satisfied by its backup strategy, which completes the proof.

Lemma 4.9.

Let α be an $N^{12}$ -strategy below the $R^{3}$ -strategies $β_{0} ≺ \dots ≺ β_{n} ≺ α$ alive at α. If $α \hat{} \infty_{i} ≺ f$ , then $A_{12} ⩽_{e} Y_{β_{i}}$ . (Of course, a symmetric result holds for $N^{23}$ -strategies below $R^{1}$ -strategies.)

Proof.

Let $s_{α_{i}}$ be a stage such that $α \hat{} \infty_{i}$ is not initialized after stage $s_{α_{i}}$ . After this stage, the set $R_{α}^{12}$ does not change. We prove that if $x ⩾ s_{α}$ is an element that is never dumped into $A_{12}$ , then either $x \in R_{α}^{12}$ or $x \in A_{12}$ if and only if $x \in Δ_{β_{i}} (Y_{β_{i}})$ .

Fix x and suppose that x is never dumped into $A_{12}$ and that $x \notin R_{α}^{12}$ . Fix the least witness z of α such that $z ⩾ x$ . Consider the stage at which z is realized and enters one of the streams of α’s immediate successors. If $z > x$ , then at that stage, x would be dumped into $A_{12}$ . So suppose that $z = x$ . Now consider the next stage at which α has outcome $\infty_{i}$ . At that stage, some element $z^{'}$ enters the stream $S_{α \hat{} \infty_{i}}$ , and by our choice of $s_{α_{i}}$ , we know that at this stage, x is in some stream $S_{α \hat{} \infty_{j}}$ where $j ⩾ i$ . If $x \neq z^{'}$ , then x would be dumped into $A_{12}$ at this stage, so suppose that $x = z^{'}$ and x enters the stream $S_{α \hat{} \infty_{i}}$ at stage s. Then at this stage, we add an axiom $⟨ x, F_{x} ⟩$ into $Δ_{β_{i}}$ for x, where $F_{x}$ is such that under the current circumstances at stage s, we have that $x \in A_{12}$ if and only if $F_{x} \subseteq Y_{β_{i}}$ . As in the proof of Lemma 4.7, if some number that is in the set $(R^{12} \cup ⋃_{j ⩽ i} P_{12}^{j}) \cap A_{12}$ at stage s is extracted from $A_{12}$ or a number that is in the set $(R^{23} \cup ⋃_{j ⩽ i} P_{23}^{j}) \cap A_{23}$ at stage s is extracted from $A_{23}$ , then x is dumped into $A_{12}$ . So suppose that neither of these ever happens. Then clearly, if $x \in A_{12}$ , then $F_{x} \subseteq Y_{β_{i}}$ , as all strategies of lower priority than $α \hat{} \infty_{i}$ are initialized at stage s. If at any stage $t > s$ , we visit α and notice that $F_{x} \subseteq Y_{β_{i}}$ even if $x \notin A_{12}$ , then the strategy α will move x to a smaller stream and initialize $α \hat{} \infty_{i}$ , contrary to our assumptions. □

Putting Corollary 4.6 and Lemma 4.9 together, we conclude the following

Corollary 4.10.

Every $R$ -requirement is satisfied.

Proof.

Fix an $R_{e}^{3}$ -requirement, say. By Lemma 4.2, let β be the longest $R_{e}^{3}$ -strategy along f. If β is not switched from Γ to Δ by any strategy extending β along f, then by Corollary 4.6, $R_{e}^{3}$ is satisfied. If $β ≺ α \hat{} \infty_{i} ≺ f$ and α switches β from Γ to Δ, then β is α’s i-th live $R^{3}$ -strategy. By Lemma 4.9, $A_{12} ⩽_{e} Y_{β}$ , and hence $R_{e}^{3}$ is once again satisfied. □

This concludes the proof of Theorem 4.1.

Footnotes

Acknowledgements

The second author was partially supported by AMS-Simons Foundation Collaboration Grant 626304. The third author was supported by MOE grant RG23/19. The fourth author was supported by NSF grants DMS-1762648 and DMS-2053848 and by the grant FNI-SU80-10-128/16.04.2020. All the authors thank the two referees for their helpful comments.

References

Ahmad, Some results on the structure of the

Σ_{2}^{0}

enumeration degrees, PhD thesis, Simon Fraser University, Canada, 1989.

Ahmad and

A.H.

Lachlan, Some special pairs of

Σ_{2}

e-degrees, MLQ Math. Log. Q. 44(4) (1998), 431–449. doi:10.1002/malq.19980440402.

S.B.

Cooper, Partial degrees and the density problem. II. The enumeration degrees of the

Σ_{2}

sets are dense, J. Symbolic Logic 49(2) (1984), 503–513. doi:10.2307/2274181.

Ganchev and

Soskova, Interpreting true arithmetic in the local structure of the enumeration degrees, J. Symbolic Logic 77(4) (2012), 1184–1194. doi:10.2178/jsl.7704070.

T.F.

Kent, The

Π_{3}

-theory of the

Σ_{2}^{0}

-enumeration degrees is undecidable, J. Symbolic Logic 71(4) (2006), 1284–1302. doi:10.2178/jsl/1164060455.

Lempp,

Lerman and

Solomon, Embedding finite lattices into the computably enumerable degrees – A status survey, in: Logic Colloquium ’02 , Lect. Notes Log., Vol. 27, Assoc. Symbol. Logic, La Jolla, CA, 2006, pp. 206–229.

Lempp,

Nies and

T.A.

Slaman, The

Π_{3}

-theory of the computably enumerable Turing degrees is undecidable, Trans. Amer. Math. Soc. 350(7) (1998), 2719–2736. doi:10.1090/S0002-9947-98-01800-5.

Lempp,

T.A.

Slaman and

Sorbi, On extensions of embeddings into the enumeration degrees of the

Σ_{2}^{0}

-sets, J. Math. Log. 5(2) (2005), 247–298. doi:10.1142/S0219061305000432.

Lempp,

T.A.

Slaman and

M.I.

Soskova, Fragments of the theory of the enumeration degrees, Advances in Mathematics 383 (2021), 107686. doi:10.1016/j.aim.2021.107686.

10.

Lempp and

Sorbi, Embedding finite lattices into the

Σ_{2}^{0}

enumeration degrees, J. Symbolic Logic 67(1) (2002), 69–90. doi:10.2178/jsl/1190150030.

11.

Nies,

R.A.

Shore and

T.A.

Slaman, Interpretability and definability in the recursively enumerable degrees, Proc. London Math. Soc. (3) 77(2) (1998), 241–291. doi:10.1112/S002461159800046X.

12.

G.E.

Sacks, On the degrees less than

0^{'}

, Ann. of Math. (2) 77 (1963), 211–231. doi:10.2307/1970214.

13.

T.A.

Slaman and

W.H.

Woodin, Definability in the enumeration degrees, Arch. Math. Logic 36(4–5) (1997), 255–267.

14.

M.I.

Soskova, The theory of the enumeration degrees, definability, and automorphisms, in: Contemporary Logic and Computing , Landsc. Log, Vol. 1, Coll. Publ., London, 2020, pp. 706–730.

Extensions of two constructions of Ahmad

Abstract

Keywords

1. Introduction

Theorem 2.1 (Ahmad [1] (see Ahmad and Lachlan [2, Corollary 3.2])).

2.1. Requirements

2.2. Tree of strategies

2.3. Construction

2.3.1. S Δ 1

2.3.2. S Γ 1 , Δ 0

2.3.3. R Γ 1

2.3.4. R Γ 1 , Γ 0

2.4. Verification

Theorem 3.1. There is no Ahmad triple in the Σ 2 0 -enumeration degrees, i.e., there are no Σ 2 0 -degrees a 0 , a 1 , and a 2 such that a 0 ≰ a 1 but every enumeration degree x 0 < a 0 is ⩽ a 1 , and such that a 1 ≰ a 2 but every enumeration degree x 1 < a 1 is ⩽ a 2 . 3.1. Requirements

3.2. Overview

3.3. Tree of strategies

3.4. Construction

3.4.1. S Δ 0 , S Γ 0 , Δ 1 , S Γ 0 , Γ 1 , Δ 2

3.4.2. R Γ 0 , R Γ 0 , Γ 1

3.4.3. R Γ 0 , Γ 1 , Γ 2

3.4.4. Backup R Γ 0 , Γ 1 , Γ 2

3.5. Verification

4.2. Naive description of the strategies

4.3. An N -strategy working below a single R -strategy

4.4. Strategies, parameters and the tree

4.6. Verification

Footnotes

Acknowledgements

References

2.3.1. $S_{Δ_{1}}$

2.3.2. $S_{Γ_{1}, Δ_{0}}$

2.3.3. $R_{Γ_{1}}$

2.3.4. $R_{Γ_{1}, Γ_{0}}$

3.4.1. $S_{Δ_{0}}$ , $S_{Γ_{0}, Δ_{1}}$ , $S_{Γ_{0}, Γ_{1}, Δ_{2}}$

3.4.2. $R_{Γ_{0}}$ , $R_{Γ_{0}, Γ_{1}}$

3.4.3. $R_{Γ_{0}, Γ_{1}, Γ_{2}}$

3.4.4. Backup $R_{Γ_{0}, Γ_{1}, Γ_{2}}$

4.3. An $N$ -strategy working below a single $R$ -strategy