The jump hierarchy in the enumeration degrees

Abstract

We show that all levels of the jump hierarchy are first order definable in the local structure of the enumeration degrees.

Keywords

Enumeration degrees definability jump classes

1. Introduction

Definability in degree structures has been a main theme in degree theory for many years. One of the first nontrivial examples is in the global structure of the Turing degrees $D_{T}$ : Jockusch and Shore [16] proved that the class of arithmetical sets is first order definable. There is an intimate relationship between the structure of the Turing degrees and second order arithmetic. Turing reducibility is an arithmetically definable relation on sets of natural numbers, thus every definable relation on $D_{T}$ is induced by a degree invariant relation on sets definable in second order arithmetic. The next breakthrough was by Slaman and Woodin [30] (see also [31]), who showed that if $R$ is such a relation then it is definable with parameters in $D_{T}$ . Their proof is intricate and goes through many steps. It uses powerful methods, such as forcing in set theory, and a coding of countable relations in $D_{T}$ via parameters, and so the definitions of these relations become quite complex. Nevertheless, this work reveals a lot about the structure of the Turing degrees and suggests a conjecture, the biinterpretability conjecture of Slaman and Woodin,1

¹
Also sometimes attributed to Harrington.

that if true would give a full characterization of the structure of the Turing degrees. Slaman and Woodin [31] proved that this conjecture is equivalent to rigidity of the structure, the statement that

D_{T}

has no nontrivial automorphisms, and to a precise characterization of the definable relations in

D_{T}

: the ones induced by a degree invariant relation on sets definable in second order arithmetic. The rigidity of the structure of the Turing degrees remains the main open question in degree theory. Many have ventured to attack it, the most significant effort being that by Barry Cooper [9], who believed that he had found a way to construct an example of a nontrivial automorphism. Unfortunately, he never completed his proof or managed to convey his ideas to the rest of the community in a convincing way, and so in recent years Cooper talked about this problem as still open and continued to make plans to work on it until his last days. Another consequence of the Slaman and Woodin’s analysis was the definability of the double jump operator. Based on this Shore and Slaman [27] were able to prove the definability of the jump operation in the Turing degrees.

In parallel, the local structure of the Turing degrees $D_{T} (⩽ 0_{T}^{'})$ consisting of the $Δ_{2}^{0}$ Turing degrees was being investigated. In the local structure one cannot talk about a jump operation, but one can consider the following jump classes:

Definition 1.

Let $a ⩽_{e} 0^{'}$ and $n \in N$ be such that $n ⩾ 1$ .

The degree a is ${low}_{n}$ if $a^{(n)} = 0^{(n)}$ .

The degree a is ${high}_{n}$ if $a^{(n)} = 0^{(n + 1)}$ .

The jump hierarchy, also known as the high/low hierarchy, was introduced independently by Cooper [5], Sacks [22], and Soare [32].2

See Odifreddi [20]. We note that the notions of a low and high degree were known and used much earlier.

Shore [25,26] showed that all jump classes except for low₁ are first order definable. The methods used in his work go through a coding of first order arithmetic. The first order definability of the class of the low₁ degrees remains a major open question in local degree theory. Later, Slaman and Soskova [28] showed that

D_{T} (⩽ 0_{T}^{'})

relates to first order arithmetic in much the same way as the Turing degrees relate to second order arithmetic: all relations on

D_{T} (⩽ 0_{T}^{'})

that are induced by relations on

Δ_{2}^{0}

indices, invariant under Turing equivalence and definable in first order arithmetic, are definable in

D_{T} (⩽ 0_{T}^{'})

with parameters. Furthermore, the rigidity of the structure is equivalent to its own biinterpretability with first order arithmetic and the definability of all relations in the form described above.

The structure of the enumeration degrees $D_{e}$ remained outside the focus of most degree theorists in this period. Initial work was done by Friedberg and Rogers [11], Medvedev [19], Case [4], Selman [24] and Rozinas [21], establishing that the structure has interesting properties: the Turing degrees embed into it as the proper substructure of the total enumeration degrees, which forms an automorphism base for $D_{e}$ . In 1982 Barry Cooper became interested in the problem of density in the enumeration degrees. Gutteridge [15] had claimed that the structure of the enumeration degrees is dense, however his proof had an error and so his idea was never published. Cooper [6], who had been working mostly on properties of minimal Turing degrees until then, saw that Gutteridge’s idea can still be used to show that the structure of the enumeration degrees does not have any minimal elements. In a follow up paper [7], he introduced the local structure of the enumeration degrees $D_{e} (⩽ 0_{e}^{'})$ , consisting of all $Σ_{2}^{0}$ enumeration degrees and proved that it is dense. This marked the beginning of his long list of contributions to the development of enumeration degree theory. His 1990 survey paper [8], which still serves as the main reference for results on this topic, contained a series of intersting open questions that attracted many other researchers, most of whom became his collaborators. In one such collaboration Arslanov, Cooper and Kalimullin [1] investigated the properties of semi-computable sets and their enumeration degrees. This work lead Kalimullin [17] to a major discovery: he introduced what are now known as Kalimullin pairs ( $K$ -pairs) as a generalization of semi-computable sets and showed that they induce a class with a natural first order definition. A pair of enumeration degrees $a, b$ form a $K$ -pair if and only if they satisfy: $\begin{matrix} (\forall x) [(a \lor x) \land (b \lor x) = x] . \end{matrix}$ The definability of $K$ -pairs unlocked the natural definability of many other important classes of enumeration degrees. Kalimullin [17] showed that the enumeration jump is first order definable. Ganchev and Soskova focused on Kalimullin pairs in the local theory of the enumeration degrees. They showed in [13] that $K$ -pairs are also locally definable.3

Cai, Lempp, Miller and Soskova [3] later gave a simpler first order definition.

Using

K

-pairs they further showed in [14] that the total enumeration degrees below

0_{e}^{'}

and the low₁ enumeration degrees are first order definable. This put the local structures of the Turing and the enumeration degrees in a strange juxtaposition: the only jump class not known to be definable in the first structure was the only one known to be definable in the other.

Global definability in the enumeration degrees is connected to its rigidity, in the same manner that we already described for the Turing degrees (see [34]). Cai, Ganchev, Lempp, Miller and Soskova [2] extended the ideas from [14] to give an explanation of this phenomenon. They showed that the total enumeration degrees are first order definable in $D_{e}$ . This gives a strong relationship between the automorphism problems of $D_{e}$ and $D_{T}$ : the total enumeration degrees are now a definable automorphism base for the structure of the enumeration degrees, and so the rigidity of $D_{T}$ would implies the rigidity of $D_{e}$ . Soskova and Slaman [29] used methods from [28] and the results from [2] to show another relationship: the rigidity of any local structure – the structure of the c.e. degrees, $D_{T} (⩽ 0_{T}^{'})$ , and $D_{e} (⩽ 0_{e}^{'})$ , implies the rigidity of $D_{e}$ . This brings back the focus from global to local definability. In this article we give one further piece of this grand puzzle, we show that every jump class is first order definable in $D_{e} (⩽ 0_{e}^{'})$ .

2. Preliminaries

Enumeration reducibility, introduced by Friedberg and Rogers [11], is a positive reducibility between sets of natural numbers. Intuitively $A ⩽_{e} B$ if and only if every enumeration of B can be effectively transformed into an enumeration of A. Formally this can be expressed as follows:

Definition 2.
A set A is enumeration reducible ( $⩽_{e}$ ) to a set B if there is a c.e. set Φ such that: $\begin{matrix} A = Φ (B) = {n ∣ \exists u (⟨ n, u ⟩ \in Φ & D_{u} \subseteq B)}, \end{matrix}$ where $D_{u}$ denotes the finite set with code u under the standard coding of finite sets. We will refer to the c.e. set Φ as an enumeration operator.

A set A is enumeration equivalent ( $\equiv_{e}$ ) to a set B if $A ⩽_{e} B$ and $B ⩽_{e} A$ . The equivalence class of A with respect to the relation $\equiv_{e}$ is the enumeration degree $d_{e} (A)$ of A. The structure of the enumeration degrees $⟨ D_{e}, ⩽ ⟩$ is the class of all enumeration degrees with relation ⩽ defined by $d_{e} (A) ⩽ d_{e} (B)$ if and only if $A ⩽_{e} B$ . It has a least element $0_{e}$ , the set of all c.e. sets, and a least upper bound operation $d_{e} (A) \lor d_{e} (B) = d_{e} (A \oplus B)$ .

The enumeration jump of a set A is defined by Cooper [6].
Definition 3.
The enumeration jump of a set A is denoted by $A^{'}$ and is defined as $K_{A} \oplus \overline{K_{A}}$ , where $K_{A} = {⟨ e, x ⟩ ∣ e \in N & x \in Φ_{e} (A)}$ . The enumeration jump of the enumeration degree of a set A is $d_{e} {(A)}^{'} = A^{'}$ .

By iterating the jump operation, we define inductively the nth jump of a degree a for every n: $a^{(0)} = a$ and $a^{(n + 1)} = {(a^{(n)})}^{'}$ .
Definition 4.
A set A is called total if $A \equiv_{e} A \oplus \overline{A}$ . An enumeration degree is called total if it contains a total set.

As noted above, the structure of all total enumeration degrees is an isomorphic copy of the Turing degrees. The map ι, defined by $ι (d_{T} (A)) = d_{e} (A \oplus \overline{A})$ is an embedding of $D_{T}$ in $D_{e}$ , which preserves the order, the least upper bound and the jump operation.

The local structure of the enumeration degrees, denoted by $D_{e} (⩽ 0_{e}^{'})$ , is the substructure with domain consisting of all enumeration degrees which are reducible to $0_{e}^{'}$ . The elements of $D_{e} (⩽ 0_{e}^{'})$ are the enumeration degrees which contain $Σ_{2}^{0}$ sets, or equivalently, which consist entirely of $Σ_{2}^{0}$ sets.
3. Defining jump classes in $D_{e} (⩽ 0_{e}^{'})$

The jump hierarchy for the local structure of the enumeration degrees is defined in the same manner as the one for $D_{T} (⩽ 0_{T}^{'})$ . An enumeration degree is ${low}_{n}$ if its nth jump is as low as possible and ${high}_{n}$ if its nth jump is as high as possible. The results by Shore and by Ganchev and Soskova, outlined in the introduction, can be summarized as follows:

Theorem 1 ([14,25,26]).

The following classes of degrees are first order definable in $D_{e} (⩽ 0_{e}^{'})$ :

The low ₁ enumeration degrees;

The total ${low}_{n}$ degrees for every n;

The total ${high}_{n}$ degrees for every n;

The natural next goal is to use the definability of jump classes restricted to total degrees to show full definability. Selman’s theorem [24] shows that an enumeration degree is determined by the set of total degrees above it: $a ⩽_{e} b$ if and only if $\begin{matrix} {x ∣ x is total and a ⩽ x} \supseteq {x ∣ x is total and b ⩽ x} . \end{matrix}$ Furthermore, Soskov [33] showed that every enumeration degree is bounded by a total enumeration degree with the same jump. When one moves to the local structure, however, Selman’s theorem is no longer true. Cooper and Copestake [10] showed that there are upwards properly $Σ_{2}^{0}$ enumeration degrees, enumeration degrees $a < 0_{e}^{'}$ with no total enumeration degree in the interval $[a, 0_{e}^{'})$ . We do not know if Soskov’s theorem remains true in the local structure. If it does, then we could easily define the jump classes: as ${low}_{n}$ degrees are downwards closed, we would have that a is ${low}_{n}$ if and only if some total $x ⩾ a$ is ${low}_{n}$ , and as ${high}_{n}$ degrees are upwards closed, we would have that a is ${high}_{n}$ if and only if all total $x ⩾ a$ are ${high}_{n}$ . It would also follow that all upwards properly $Σ_{2}^{0}$ enumeration degrees are high₁, which is a separate open question that has turned out difficult to solve.

The idea we use is in the same spirit, if slightly more indirect. We show that every enumeration degree bounds a nonzero enumeration degree for which the property in Soskov’s theorem is true.

Theorem 2.
For every nonzero $Σ_{2}^{0}$ enumeration degree a there are nonzero enumeration degrees b and x such that
$b ⩽ a$ and $b ⩽ x$ ;

x is total and $b^{'} = x^{'}$ .

We combine this theorem with the following result of Ganchev and Sorbi [12].
Theorem 3 ([12]).

For every nonzero $Σ_{2}^{0}$ enumeration degree a there is a nonzero $Σ_{2}^{0}$ enumeration degree $b ⩽ a$ such that for every enumeration degree $y \in (0, b]$ we have that $y^{'} = a^{'}$ .

These two theorems give us the necessary tools to prove our main result.

Theorem 4.
For every natural number $n ⩾ 1$ the class of all ${low}_{n}$ enumeration degrees and the class of all ${high}_{n}$ enumeration degrees is first order definable in $D_{e} (⩽ 0_{e}^{'})$ .
Proof.
A nonzero enumeration degree a is ${low}_{n}$ if and only if for every nonzero enumeration degree $b ⩽ a$ there is a nonzero $c ⩽ b$ and a total enumeration degree $x ⩾ c$ that is ${low}_{n}$ . Indeed, every ${low}_{n}$ enumeration degree satisfies this property, as by Theorem 2 every nonzero $Σ_{2}^{0}$ degree b bounds a nonzero c for which there is a total $x ⩾ c$ with $c^{'} = x^{'}$ . As ${low}_{n}$ degrees are downwards closed, all such degrees c are ${low}_{n}$ and so all such total degrees x are ${low}_{n}$ . On the other hand, if a satisfies this property then let $b ⩽ a$ be the degree from Theorem 3. All degrees in the interval $(0_{e}, b]$ have the same jump as a and one of them is bounded by a total ${low}_{n}$ degree, hence a is ${low}_{n}$ .

A nonzero enumeration degree a is ${high}_{n}$ if and only if there exists an enumeration degree $b ⩽ a$ such that for every nonzero $c ⩽ b$ all total enumeration degrees $x ⩾ c$ are ${high}_{n}$ . If a is ${high}_{n}$ then let $b ⩽ a$ be the degree from Theorem 3. All nonzero degrees c bounded by b are ${high}_{n}$ and so by the upwards closure of the ${high}_{n}$ degrees all total degrees above such degrees c must also be ${high}_{n}$ . If, on the other hand, a satisfies this property as witnessed by b then let $c ⩽ b$ and x be the degrees we get when we apply Theorem 2 to the nonzero enumeration degree b. It follows that c is ${high}_{n}$ and so again by the upwards closure of this class we have that a is ${high}_{n}$ . □

4. Proof of Theorem 2

Let A be a $Σ_{2}^{0}$ set that is not computably enumerable. We must construct sets B and X such that:

B is not computably enumerable;

X is total;

$B ⩽_{e} A$ ;

$B ⩽_{e} X$ ;

$B^{'} \equiv_{e} X^{'}$ .

We will construct X as a $Π_{1}^{0}$ set. As all $Π_{1}^{0}$ sets are total, this ensures (2). We will also construct enumeration operators Γ and Λ so that $Γ (A) = Λ (X) = B$ , ensuring (3) and (4). To satisfy the theorem we must ensure that $Γ (A)$ is not c.e. and that $X^{'} ⩽_{e} Γ {(A)}^{'}$ . By the monotonicity of the enumeration jump this will automatically yield $Γ {(A)}^{'} \equiv_{e} X^{'}$ . The proof uses methods introduced by Sacks [23] in his jump inversion theorem.

Fix a good $Σ_{2}^{0}$ approximation ${A_{s}}_{s < ω}$ to A. Good approximations were introduces by Lachlan and Shore [18] as a generalization of Cooper’s [9] approximations with infinitely many thin stages. A good $Σ_{2}^{0}$ approximation to a set A is a $Σ_{2}^{0}$ approximation with the additional property that for infinitely many s we have that $A_{s} \subseteq A$ . We construct c.e. approximations to the sets Γ and Λ and a $Π_{1}^{0}$ approximation to X, i.e. $X_{0} = N$ , $X_{s}$ is co-finite and $X_{s + 1} \subseteq X_{s}$ for all s.

To ensure that $Γ (A) = Λ (X)$ , we will let other strategies build Γ and use the following method to construct Λ. To every natural number x we dedicate the column $N^{[x]} = {⟨ x, n ⟩ ∣ n \in N}$ . At the beginning of every stage we ensure that $Γ (A) [s] = Λ (X) [s]$ as follows: if $x < s$ is a natural number such that $x \in Γ (A) [s] ∖ Λ (X) [s]$ then we pick a new fresh current marker $λ (x) \in {⟨ x, n ⟩ ∣ n \in N}$ and enumerate $⟨ x, {λ (x)} ⟩$ in Λ. Note that as $λ (x)$ is selected as a fresh number, it belongs to the set $X_{s}$ . If on the other hand x is such that $x \in Λ (X) [s] ∖ Γ (A) [s]$ then we extract the number $λ (x)$ from $X_{s}$ and make $λ (x) ↑$ . If $x \in Γ (A)$ then there is a stage $s_{x}$ such that for all $t > s_{x}$ we will have $x \in Γ (A) [t]$ . Thus we will define a final value for the marker $λ (x)$ and never remove it from X. If on the other hand $x \notin Γ (A)$ then at infinitely many stages s, $x \notin Γ (A) [s]$ and every axiom enumerated in Λ for x is eventually invalidated.

The rest of the construction is on a tree T of strategies. Strategies at levels $3 e$ will work towards satisfying the requirements $W_{e} \neq Γ (A)$ . They will have outcomes of order type $ω + 2$ : $\begin{matrix} 0 <_{L} 1 \dots <_{L} n <_{L} \dots <_{L} \infty <_{L} w . \end{matrix}$ Next at level $3 e + 1$ we have strategies that will allow us to correctly approximate $Γ (A)$ on a finite set of numbers that are used by strategies of higher priority than this one. The outcomes of these strategies have order type ω: $\begin{matrix} 0 <_{L} 1 \dots <_{L} n <_{L} \dots \end{matrix}$ Finally at level $3 e + 2$ we will have strategies that ensure that whether or not $e \in Φ_{e} (X)$ can be determined from the true path, i.e. the leftmost path of nodes visited infinitely often. These strategies have two outcomes: $\begin{matrix} yes <_{L} no . \end{matrix}$

At every stage we construct a finite path $δ [s]$ of length s on the tree T. The path is defined inductively: $δ ↾ 0 [s] = \emptyset$ , the root of the tree. Once we define $δ ↾ n [s]$ , we run this strategy and it determines its outcome $o$ . Then $δ (n + 1) [s] = o$ . At the end of every stage we initialize all strategies on the tree that are of lower priority than δ.

Suppose that α is a strategy working towards $W_{e} \neq Γ (A)$ . The goal of α is to find a witness x such that $W_{e} (x) \neq Γ (A) (x)$ . The strategy will pick a series of witnesses. It will have a list of old witnesses $L_{α} \subseteq W_{e}$ used so far and a current witness $x_{α}$ selected at stage $s_{α}^{x}$ that has not yet appeared in $W_{e}$ . The strategy will also keep a current approximation to the set A, denoted by $U_{α}$ , such that if $U_{α} ⊈ A$ then one of the old witnesses must be out of the set $Γ (A)$ .

When visited the strategy will first check the entries of the list $L_{α}$ in order. If it finds an old witness $y \in L_{α}$ such that for some stage $t \in (s_{α}^{-}, s]$ , where $s_{α}^{-}$ is the previous stage when α was visited, we have that $y \notin Γ (A) [t]$ then the strategy will have outcome $y$ . If α has outcome $y$ infinitely often then $y \in W_{e} ∖ Γ (A)$ and so α is successful. If all witnesses $y \in L_{α}$ have been in $Γ (A) [t]$ at all stages $t \in (s_{α}^{-}, s]$ then the strategy will move on to examine its current witness. If $x_{α} \notin W_{e}$ then the strategy will enumerate in Γ the axiom $⟨ x_{α}, U_{α} \cup ⋂_{t \in (s_{α}^{x}, s]} A_{t} ⟩$ and have outcome $w$ . If α has outcome $w$ at all but finitely many stages then it will follow that $x_{α} \in Γ (A) ∖ W_{e}$ and α is successful as well. Finally if $x_{α} \in W_{e}$ then the strategy will redefine $U_{α}$ as $U_{α} \cup ⋂_{t \in (s_{α}^{x}, s]} A_{t}$ , enumerate one last axiom for $x_{α}$ in Γ: namely $⟨ x_{α}, U_{α} ⟩$ and then enumerate $x_{α}$ in the list $L_{α}$ . It will then define a new fresh value for the current witness $x_{α}$ and set $s_{α}^{x} = s$ . The outcome will be ∞. It will follow from the construction that if the leftmost outcome that α has at infinitely many stages is ∞ then ${U_{α} [s]}_{s < ω}$ is a c.e. approximation to A, contradicting the fact that A is not c.e.

The next type of strategy γ is sitting on a node of length $3 e + 1$ . The goal of this strategy is to approximate the value of $Γ (A)$ on numbers z such that z is currently the witness (old or current) to a strategy $α <_{L} γ$ . So let $M_{γ} [s]$ be the list of all such numbers at a given stage s. Let $s_{γ}^{-}$ again denote the previous stage when γ was visited. Note that $M_{γ}$ is always a finite set. Furthermore, if γ is not initialized between true stages $s_{γ}^{-}$ and s, it follows that $M_{γ} [s_{γ}^{-}] = M_{γ} [s]$ . Suppose that at stage s we have that $M_{γ} = {z_{0} < z_{1} \dots < z_{m - 1}}$ . To every element $z_{i}$ it will assign the value $s (z) \in {0, 1}$ as follows: $s (z_{i}) = 0$ if there is a stage $t \in (s_{γ}^{-}, s]$ such that $z_{i} \notin Γ (A_{t})$ and otherwise $s (z_{i}) = 1$ . Consider the standard ordering of boolean vectors, defined inductively as follows: if $σ_{0} < σ_{1} < \dots σ_{2^{n} - 1}$ is the standard ordering of the boolean vectors of length n then $0 σ_{0} < 0 σ_{1} < \dots 0 σ_{2^{n} - 1} < 1 σ_{0} < 1 σ_{1} < \dots 1 σ_{2^{n} - 1}$ is the standard ordering of the boolean vectors of size $n + 1$ . Suppose that $(s (z_{0}), s (z_{i}), \dots s (z_{m - 1}))$ is the kth boolean vector in this standard ordering. Then γ has outcome $k$ . If γ is on the true path then there is a stage $s_{γ}$ such that γ is not initialized at stages $t ⩾ s_{γ}$ . Hence $M_{γ} [t] = M_{γ} [s_{γ}]$ for all such stages t. We will see that the true outcome of γ will correspond to the correct approximation to $Γ (A) (z)$ for all $z \in M_{γ}$ .

Finally we have strategies β working on nodes of length $3 e + 2$ . At stage s such a strategy will search for an axiom $⟨ e, D ⟩$ in $W_{e} [s]$ such that $D \subseteq X_{s}$ and does not contain any markers $λ (z)$ for a number z that is either:

a witness of a strategy α such that $α \hat{} x ⪯ β$ and $x < z$ ,

an element of $M_{γ}$ with $s (z) = 0$ , for $γ ⪯ β$ .

We call such axioms believable. If there is no such axiom then the outcome is

no

. If there is a believable axiom then the outcome is

yes

We argue that if β is on the true path then its true outcome corresponds to whether or not $e \in W_{e} (X)$ . Suppose that $e \in W_{e} (X)$ . It follows that there is an axiom $⟨ e, D ⟩ \in W_{e}$ such that $D \subseteq X$ . We will show that if z is a number that has the properties described above then $z \notin Γ (A)$ . So any marker $λ (z)$ that is ever defined for z does not belong to X. Hence D does not contain such elements. There will be a stage s when this axiom is enumerated in $W_{e} [s]$ . At the next true stage β will see this axiom and have outcome $yes$ . Suppose now that β has outcome $yes$ at stage s. Then at this stage there is a believable axiom $⟨ e, D ⟩$ in $W_{e} [s]$ . This axiom will remain believable at all further stages as all strategies of lower priority than β will be initialized and hence $e \in W_{e} (X)$ .

To sum up, we have a global strategy constructing Λ and three types of strategies on the tree T.

Strategies of type α have the following parameters: a list of witnesses $L_{α}$ , the stage of the previous visit $s_{α}^{-}$ , a current approximation to the set A denoted by $U_{α}$ , a current witness $x_{α}$ and the stage when it was defined $s_{α}^{x}$ . Initially $L_{α} = U_{α} = \emptyset$ , $s_{α}^{-} = 0$ , $x_{α} ↑$ and $s_{α}^{x} ↑$ . When α is initialized during the construction, all of its witnesses $y \in L_{α} \cup {x_{α}}$ are dumped in $Γ (A)$ , i.e. the axiom $⟨ y, \emptyset ⟩$ is enumerated in Γ, and all of its parameters get initial values.

Strategies of type γ also have a parameter $s_{γ}^{-}$ , initially 0 and a list $M_{γ}$ , initially empty. When γ is initialized its parameters are set to their initial states.

Strategies of type β have no parameters.

Construction

At stage 0 all strategies have initial values, $Γ [0] = Λ [0] = \emptyset$ , $X [0] = N$ .

At stage s all parameters inherit their values from the previous stage, unless explicitly modified during the construction. We start stage s by visiting the global Λ-strategy:

The global Λ-strategy: Scan all $x < s$ in turn:

If $x \in Γ (A) ∖ Λ (X)$ then let $λ (x) \in {⟨ x, n ⟩ ∣ n \in N}$ be a fresh number. Enumerate $⟨ x, {λ (x)} ⟩$ in Λ.

If $x \in Λ (X) ∖ Γ (A)$ then extract the number $λ (x)$ from $X [s + 1]$ and make $λ (x) ↑$ .

Next we build $δ [s]$ . Suppose we have constructed $δ [s] ↾ n$ and $n < s$ . We have three cases depending on n:

Case 1: $n = 3 e$ . Denote $δ [s] ↾ n$ by α and pick the first case which applies.

If α is in initial state, we pick $x_{α}$ to be a fresh number and set $s_{α}^{x} = s$ . Let the outcome be $w$ .

If there is an element $y \in L_{α}$ such that for some stage $t \in (s_{α}^{-}, s]$ we have that $y \notin Γ (A) [t]$ then pick the least such y and let the outcome be $y$ .

If $x_{α} \in W_{e}$ then:

Let $U_{α}$ be the set $U_{α} [s] \cup ⋂_{t \in (s_{α}^{x}, s]} A [t]$ .

Enumerate the axiom $⟨ x_{α}, U_{α} ⟩$ in Γ.

Pick a new fresh value for the witness $x_{α}$ and let $s_{α}^{x} = s$ .

Let the outcome be ∞.

Otherwise enumerate in Γ the axiom $⟨ x_{α}, U_{α} \cup ⋂_{t \in (s_{α}^{x}, s]} A [t] ⟩$ . Let the outcome be $w$ .

Case 2: $n = 3 e + 1$ . Denote $δ [s] ↾ n$ by γ and execute the following two actions.

If γ is in initial state then let $M_{γ}$ be the set of all witnesses z that are currently used by a strategy $α <_{L} γ$ .

Let $M_{γ} = {z_{0} < z_{1} \dots < z_{m - 1}}$ . For all $i < m$ set $s (z_{i}) = 0$ if there is a stage $t \in (s_{γ}^{-}, s]$ such that $z_{i} \notin Γ (A_{t})$ and otherwise set $s (z_{i}) = 1$ . Suppose that the boolean vector $(s (z_{0}), \dots s (z_{m - 1}))$ is the kth vector in the standard ordering of all boolean vectors of length m. Let the outcome be $k$ .

Case 3: $n = 3 e + 2$ . Denote $δ [s] ↾ n$ by β and pick the first case which applies.

If there is an axiom $⟨ e, D ⟩ \in W_{e}$ such that $D \subseteq X [s]$ and does not contain markers $λ (z)$ for z such that

z is a witness of a strategy α such that $α \hat{} x ⪯ β$ and $x < z$ ;

$z \in M_{γ}$ and $s (z) = 0$ , for γ the immediate predecessor of β;

then let the outcome be

yes

Otherwise let the outcome be $no$ .

End of construction

To verify that the construction works we prove the following lemmas

Lemma 1.

There is a true path f in the tree T such that

For all n there are infinitely many stages s such that $f ↾ n ⪯ δ [s]$ .

For all n there is a stage $s_{n}$ such that for all $t > s_{n}$ we have that $f ↾ n ⩽ δ [s]$ .

Proof.

The proof is by induction on n. Suppose that we have constructed $f ↾ n$ and $s_{n}$ . We have three cases:

If $n = 3 e$ then $f ↾ n = α$ . The construction ensures that there is a leftmost outcome visited at infinitely many stages: if α ever has outcome $n$ and n is the kth member of the list $L_{α}$ , then α must have had outcome ∞ at least k many times. We show that in fact this outcome cannot be ∞. Suppose towards a contradiction that there are infinitely many stages $s > s_{n}$ such that α is visited at stage s and has outcome ∞ and that no outcome to the left of ∞ is visited infinitely often. It follows that for every s we have that $U_{α} [s] \subseteq A$ . Indeed, if for some s the set $U_{α} [s] ⊈ A$ then consider the witness x that is enumerated in the list $L_{α}$ at the stage when $U_{α [s]}$ is defined. All axioms $⟨ x, D ⟩$ defined for x in Γ have the property $U_{α} [s] \subseteq D$ . So if $U_{α} [s] ⊈ A$ then $x \notin Γ (A)$ . It follows from the construction that the outcome $x < \infty$ will be visited infinitely often, contrary to our assumptions. We claim that for every natural number z, $z \in A$ if and only if there is an $s > s_{n}$ such that $z \in U_{α} [s]$ . Let $z \in A$ . There is a stage $s_{z}$ such that $x \in A_{t}$ at all stages $t > s_{z}$ . Let $s_{z} < t_{1} < t_{2}$ be two stages such that α has outcome ∞ at these stages. Then $z \in U_{α} [t_{2}]$ . This contradicts that A is not c.e. We are left with two possibilities. If there is a least x such that $x$ is visited infinitely often then let $f (n) = x$ and $s_{n + 1}$ be the stage such at all stages $t > s$ the outcome is greater than or equal to $x$ . Otherwise, there must be a stage $s_{n + 1}$ such that at all stages $t > s_{n + 1}$ we have that $L_{α} [t] = L_{α} [s_{n + 1}] = L_{α}$ , $L_{α} \subseteq Γ (A) [t]$ and $x_{α} [t] = x_{α} [s_{n + 1}] \notin W_{e}$ . In that case we set $f (n) = w$ .

If $n = 3 e + 1$ then $f ↾ n = γ$ . At the first visit after $s_{n}$ we define the final value of $M_{γ}$ . It is a finite set of fixed size, say m. The only possible outcomes for γ at further stages are $0, 1, \dots, 2^{m} - 1$ . There is a leftmost one $o$ from these visited at infinitely many stages. Let $f (n) = o$ and let $s_{n + 1}$ be the first stage after $s_{n}$ such that no outcome to the left of $o$ is visited infinitely often.

If $n = 3 e + 1$ then $f ↾ n = β$ . There are two possible outcomes. If $yes$ is visited infinitely often then $f (n) = yes$ and $s_{n + 1} = s_{n}$ . Otherwise let $s_{n + 1} > s_{n}$ be the stage such that $yes$ is not visited at any stage $t ⩾ s_{n + 1}$ and let $f (n) = no$ . □

Lemma 2.

For every natural number e we have that $W_{e} \neq Γ (A)$ .

Proof.

Consider the strategy α on the true path at level $3 e$ . If the true outcome of α is some natural number $x$ then x has been added to α’s list $L_{α}$ , because $x \in W_{e}$ . At infinitely many stages t, $x \notin Γ (A) [t]$ , hence $x \notin Γ (A)$ . The only other possibility is that α’s true outcome is $w$ . This means that there is a stage s such that at all stages $t > s$ if α is visited at stage t, it has outcome $w$ , the module for α’s actions always ends in case (4). As a consequence $L_{α} [t] = L_{α} [s] \subseteq Γ (A) [t]$ and $U_{α} [s] = U_{α} [t] \subseteq A [t]$ and $x_{α} [s] = x_{α} [t] \notin W_{e} [t]$ . Let r be an α-true stage such that the interval $(s_{α}^{x}, r]$ contains a stage t such that $A_{t} \subseteq A$ . Then the axiom enumerated in Γ for $x_{α}$ at stage r will be a valid axiom and $x_{α} \in Γ (A)$ . □

Lemma 3.

$Λ (X) = Γ (X)$ .

Proof.

The actions of the global strategy ensure that this is true. If $x \notin Γ (A)$ then there are infinitely many stages s such that $x \notin Γ (A) [s]$ . At such stages Λ ensures that $x \notin Λ (X) [s]$ by extracting the marker $λ (x)$ from X. If on the other hand $x \in Γ (A)$ then there is a stage $s_{x}$ such that $x \in Γ (A) [t]$ for all stages $t ⩾ s_{x}$ . No later than at stage $s_{x}$ the strategy Λ ensures that $x \in Λ (X) [s_{x}]$ via the axiom $⟨ x, {λ (x)} ⟩$ . As markers are chosen always from disjoint sets, and Λ is the only strategy that can remove them from X, it follows that $x \in Λ (X)$ □

Lemma 4.

$e \in X^{'}$ if an only if $f (3 e + 2) = yes$ .

Proof.

Let γ and β be the strategies along the true path of length $3 e + 1$ and $3 e + 2$ respectively. After stage $s_{3 e + 1}$ the strategy γ is not injured, hence $M_{γ}$ has a fixed value ${z_{0}, \dots z_{m - 1}}$ . Let $\vec{a} = (a_{0}, \dots a_{m - 1})$ be the boolean vector such that $a_{i} = 1$ if and only if $z_{i} \in Γ (A)$ . We first show that γ’s true outcome corresponds to the position of $\vec{a}$ in the standard ordering. An easy induction on the length of $\vec{a}$ shows that if $\vec{b} < \vec{a}$ and k is the first position where these two vectors differ, then $b_{k} = 0$ and $a_{k} = 1$ . Let s be a stage such that at all stages $t > s$ if $z_{i} \in Γ (A)$ then $z_{i} \in Γ (A) [t]$ . Then at stages $t > s$ the strategy γ will not have outcome corresponding to the position of $\vec{b}$ , where $\vec{b}$ is any vector of smaller position than $\vec{a}$ . The fact that there are infinitely many good stages in the approximation to A guarantees that infinitely often we will see stages t such that for all i if $z_{i} \notin Γ (A)$ then $z_{i} \notin Γ (A) [t]$ , so infinitely often $\vec{a}$ will be the true outcome of γ.

Suppose that z is a witness of a strategy α such that $α \hat{} x ⪯ β$ and $x < z$ . By our previous arguments we know that since $x$ is the true outcome of α it follows that $x \notin Γ (A)$ . Suppose x enters the list $L_{α}$ at stage t. It follows that the axiom $⟨ x, U_{α} [t] ⟩$ was enumerated in Γ at stage t and so $U_{α} [t] ⊈ A$ . The design of our strategy ensures that every axiom $⟨ z, F ⟩$ that we ever enumerate in Γ will have $U_{α} [t] \subseteq F$ . It follows that $z \notin Γ (A)$ .

Suppose that at all β-true stages after $s_{3 e + 2}$ the strategy has outcome $no$ . If at stage $s > s_{3 e + 2}$ the strategy β sees an axiom $⟨ e, D ⟩ \in W_{e} [s]$ such that $D \subseteq X [s]$ then D contains a number $λ (z)$ for a number z of two possible kinds: a witness of some $α ⪯ β$ as described in the previous paragraph or a number $z \in M_{γ}$ with $s (z) = 0$ . In both cases we have argued that $z \notin Γ (A)$ hence $λ (z) \notin X$ . It follows that $D ⊈ X$ . So $W_{e}$ contains no valid axiom for e with respect to the oracle X, hence $e \notin W_{e} (X)$ .

Suppose now that there is a stage $s > s_{3 e + 2}$ such that β has outcome $yes$ . At stage s it has found a believable axiom $⟨ e, D ⟩$ and $D \subseteq X [s]$ . We will show that $D \subseteq X$ and that at all stages $t > s$ the strategy β has outcome $yes$ when visited. First note that if D contains a marker $λ (z)$ for some element z then this marker has been defined before stage s and belongs to a witness defined before stages s. This follows from the way we define new values for parameters: always as fresh numbers. If z is a witness to a higher priority strategy then z is not seen as an obstacle by β. Either it is a witness of $α ⪯ β$ with true outcome $x$ for $x > z$ or it is in $M_{γ}$ and $s (z) = 1$ . As β is not initialized after stage $s_{3 e + 2}$ , it follows that $z \in Γ (A) [t]$ and hence $λ (z) \in X [t]$ at all $t > s_{3 e + 2}$ . If z is a witness to a lower priority strategy then this strategy is in initial state or initialized at stage s. It follows z is dumped in Γ and hence again $z \in Γ (A) [t]$ and hence $λ (z) \in X [t]$ at all $t > s_{3 e + 2}$ . Thus $D \subseteq X$ and, furthermore, the axiom is believable at all further stages, thus β always has outcome $yes$ when visited. □

Lemma 5.

The set $Γ (A) \oplus \emptyset^{'}$ can compute the true path f.

Proof.

The procedure is inductive. Suppose that $Γ (A) \oplus \emptyset^{'}$ can compute $f ↾ n$ and the stages $s_{n}$ from the true path lemma. We have three cases:

If $n = 3 e$ then $f ↾ n = α$ . We run the construction and every time a new witness is selected for α we check using oracle $Γ (A) \oplus \emptyset^{'}$ whether $Γ (A)$ and $W_{e}$ agree on this witness. By Lemma 2 we will eventually find the least witness x such that $Γ (A) (x) \neq W_{e} (x)$ . If $x \notin Γ (A)$ then the true outcome of α is $x$ . Otherwise it is $w$ . Next for each witness $y < x$ defined by α after stage $s_{n}$ we search for a stage $s_{y}$ such that $\emptyset^{'}$ gives a negative answer to the following question: “Does there exists $t > s_{y}$ such that $y \notin Γ (A) [t]$ ?”. We know that for every $y < x$ eventually such a stage will be found. We define $s_{n + 1}$ to be the maximum of all such stages $s_{y}$ .

If $n = 3 e + 1$ then $f ↾ n = γ$ . We run the construction until the first γ-true stage after $s_{n}$ to figure out the final value of $M_{γ} = {z_{0} < \dots < z_{m - 1}}$ . The true outcome corresponds to the position of the vector $(Γ (A) (z_{0}), \dots Γ (A) (z_{m - 1}))$ . To figure out $s_{n + 1}$ we again use $\emptyset^{'}$ to figure out for each $z_{i} \in Γ (A)$ the stage $s_{z_{i}}$ such that $z_{i} \in Γ (A) [t]$ at all $t > s_{z_{i}}$ and take the maximum of all these stages.

If $n = 3 e + 1$ then $f ↾ n = β$ . We use $\emptyset^{'}$ to answer the question: “Is there a stage $s > s_{n}$ such that β is visited and has outcome $yes$ at stage s”. If the answer is positive then $f (n) = yes$ . Otherwise $f (n) = no$ . In both cases $s_{n + 1} = s_{n}$ . □

Corollary 1.

$X^{'} \equiv_{e} Γ {(A)}^{'}$ .

Proof.

The set $X^{'}$ is defined as $K_{X} \oplus \overline{K_{X}}$ , where $K_{X} = {e ∣ e \in W_{e} (X)}$ . We just showed that $K_{X} ⩽_{T} Γ (A) \oplus \emptyset^{'}$ . It is also easy to see that $Γ (A) \oplus \emptyset^{'} ⩽_{T} K_{Γ (A)}$ . So $K_{X} ⩽_{T} K_{Γ (A)}$ and hence $X^{'} = K_{X} \oplus \overline{K_{X}} ⩽_{e} K_{Γ (A)} \oplus \overline{K_{Γ (A)}} = Γ {(A)}^{'}$ .

On the other hand we already saw that $Γ (A) ⩽_{e} X$ , so by monotonicity of the jump operation $Γ {(A)}^{'} ⩽_{e} X^{'}$ . □

Footnotes

Acknowledgements

This research was supported by National Science Fund of Bulgaria, contract DN02/16 from 19.12.2016. The second author was also supported by the L’Oréal-UNESCO program “For women in science”.

References

M.M.

Arslanov,

S.B.

Cooper and

I.S.

Kalimullin, Splitting properties of total enumeration degrees, Algebra Logika42(1) (2003), 3–25, 125. doi:10.1023/A:1022660222520.

Cai,

H.A.

Ganchev,

Lempp,

J.S.

Miller and

M.I.

Soskova, Defining totality in the enumeration degrees, J. Amer. Math. Soc.29 (2016), 1051–1067. doi:10.1090/jams/848.

Cai,

Lempp,

J.S.

Miller and

M.I.

Soskova, On Kalimullin pairs, Computability (2015). doi:10.3233/COM-150046.

J.W.

Case, Enumeration reducibility and partial degrees, PhD thesis, University of Illinois at Urbana-Champaign, 1969.

S.B.

Cooper, Distinguishing the arithmetical hierarchy, Preprint, Berkeley, October 1972.

S.B.

Cooper, Partial degrees and the density problem, J. Symbolic Logic47(4) (1982), 854–859.

S.B.

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

Σ_{2}

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

S.B.

Cooper, Enumeration reducibility, nondeterministic computations and relative computability of partial functions, in: Recursion Theory Week, Oberwolfach, 1989, Lecture Notes in Math., Vol. 1432, Springer, Berlin, 1990, pp. 57–110. doi:10.1007/BFb0086114.

S.B.

Cooper, Upper cones as automorphism bases, Siberian Adv. Math.9(3) (1999), 17–77.

10.

S.B.

Cooper and

C.S.

Copestake, Properly

Σ_{2}

enumeration degrees, Z. Math. Logik Grundlag. Math.34(6) (1988), 491–522. doi:10.1002/malq.19880340603.

11.

R.M.

Friedberg and

RogersJr., Reducibility and completeness for sets of integers, Z. Math. Logik Grundlagen Math.5 (1959), 117–125. doi:10.1002/malq.19590050703.

12.

Ganchev and

Sorbi, Initial segments of the

Σ_{2}^{0}

enumeration degrees, J. Symb. Log.81(1) (2016), 316–325. doi:10.1017/jsl.2014.84.

13.

H.A.

Ganchev and

M.I.

Soskova, Cupping and definability in the local structure of the enumeration degrees, J. Symbolic Logic77(1) (2012), 133–158. doi:10.2178/jsl/1327068696.

14.

H.A.

Ganchev and

M.I.

Soskova, Definability via Kalimullin pairs in the structure of the enumeration degrees, Trans. Amer. Math. Soc.367 (2015), 4873–4893. doi:10.1090/S0002-9947-2014-06157-6.

15.

Gutteridge, Some results on enumeration reducibility, PhD thesis, Simon Fraser University, 1971.

16.

G.C.

JockuschJr. and

R.A.

Shore, Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers, J. Symbolic Logic49(4) (1984), 1205–1236. doi:10.2307/2274273.

17.

I.S.

Kalimullin, Definability of the jump operator in the enumeration degrees, J. Math. Log.3(2) (2003), 257–267. doi:10.1142/S0219061303000285.

18.

A.H.

Lachlan and

R.A.

Shore, The n-rea enumeration degrees are dense, Arch. Math. Logic31(4) (1992), 277–285. doi:10.1007/BF01794984.

19.

Medvedev, Degrees of difficulty of the mass problem, Dok. Akad. Nauk SSSR104 (1955), 501–504.

20.

Odifreddi, Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Vol. 1, Studies in Logic and the Foundations of Mathematics, Vol. 125, North Holland, 1992.

21.

M.G.

Rozinas, The semi-lattice of e-degrees, Recursive functions (Ivanovo), Ivano. Gos. Univ. (1978), 71–84 (in Russian).

22.

G.E.

Sacks, Degrees of Unsolvability, Annals of Mathematics Studies, Princeton University Press, 1963.

23.

G.E.

Sacks, Recursive enumerability and the jump operator, Trans. Amer. Math. Soc.108 (1963), 223–239. doi:10.1090/S0002-9947-1963-0155747-3.

24.

A.L.

Selman, Arithmetical reducibilities I, Z. Math. Logik Grundlag. Math.17 (1971), 335–350. doi:10.1002/malq.19710170139.

25.

R.A.

Shore, Defining jump classes in the degrees below

0^{'}

, Proc. Amer. Math. Soc.104(1) (1988), 287–292.

26.

R.A.

Shore, Biinterpretability up to double jump in the degrees below

0^{'}

, Proc. Amer. Math. Soc.142(1) (2014), 351–360. doi:10.1090/S0002-9939-2013-11719-3.

27.

R.A.

Shore and

T.A.

Slaman, Defining the Turing jump, Math. Res. Lett.6(5–6) (1999), 711–722. doi:10.4310/MRL.1999.v6.n6.a10.

28.

T.A.

Slaman and

M.I.

Soskova, The

Δ_{2}^{0}

Turing degrees: Automorphisms and definability, Trans. Amer. Math. Soc., to appear.

29.

T.A.

Slaman and

M.I.

Soskova, The enumeration degrees: Local and global structural interactions, In press.

30.

T.A.

Slaman and

W.H.

Woodin, Definability in the Turing degrees, Illinois J. Math.30(2) (1986), 320–334.

31.

T.A.

Slaman and

W.H.

Woodin, Definability in degree structures, Preprint, 2005.

32.

R.I.

Soare, Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets, Ann. of Math. (2)100 (1974), 80–120. doi:10.2307/1970842.

33.

I.N.

Soskov, A jump inversion theorem for the enumeration jump, Arch. Math. Logic39(6) (2000), 417–437. doi:10.1007/s001530050156.

34.

M.I.

Soskova, The automorphism group of the enumeration degrees, Ann. Pure Appl. Logic167(10) (2016), 982–999. doi:10.1016/j.apal.2014.01.007.

The jump hierarchy in the enumeration degrees

Abstract

Keywords

1. Introduction

1 Also sometimes attributed to Harrington.

Theorem 1 ([14,25,26]).

Theorem 2. For every nonzero Σ 2 0 enumeration degree a there are nonzero enumeration degrees b and x such that b ⩽ a and b ⩽ x ; x is total and b ′ = x ′ . We combine this theorem with the following result of Ganchev and Sorbi [12]. Theorem 3 ([12]).

Footnotes

Acknowledgements

References

¹
Also sometimes attributed to Harrington.

Theorem 2.
For every nonzero $Σ_{2}^{0}$ enumeration degree a there are nonzero enumeration degrees b and x such that
$b ⩽ a$ and $b ⩽ x$ ;

x is total and $b^{'} = x^{'}$ .

We combine this theorem with the following result of Ganchev and Sorbi [12].
Theorem 3 ([12]).