Extending Cooper’s theorem to Δ 3 0 Turing degrees

Abstract

In 1971 B. Cooper proved that there exists a 2-c.e. Turing degree which doesn’t contain a c.e. set. Thus, he showed that the second level of the Ershov hierarchy is proper. In this paper we investigate proper levels of some extensions of the Ershov hierarchy to higher levels of the arithmetical hierarchy. Thus we contribute to the theory of $Δ_{3}^{0}$ -degrees by extending Cooper’s theorem to some levels of the fine hierarchy within $Δ_{3}^{0}$ -sets.

Keywords

Ershov’s hierarchy fine hierarchy arithmetical hierarchy Turing degrees

1. Introduction

Investigation of Turing degrees of $Δ_{2}^{0}$ -sets is a central topic of the local degree theory. The structure of $Δ_{2}^{0}$ -degrees turned out to be quite rich and complex, and the degree theory for higher levels of the arithmetical hierarchy leads to additional complications. In this paper, we consider some natural questions about Turing degrees of sets from the Ershov hierarchy and its extensions to $Δ_{3}^{0}$ -sets.

The study of Turing degrees in the Ershov hierarchy was initiated by B. Cooper [1] who constructed a difference of two computably enumerable (c.e.) sets not Turing equivalent to any c.e. set. The c.e. sets form the first level $Σ_{1}^{- 1}$ of Ershov’s hierarchy ${Σ_{k}^{- 1}}_{k < ω}$ [2] and the differences of c.e. sets form its second level $Σ_{2}^{- 1}$ . It is known that the natural extension of this hierarchy to the Kleene notation system for the computable ordinals exhausts the class $Δ_{2}^{0}$ [2–4]. It is possible to extend Cooper’s result to all levels of the Ershov hierarchy [1] including the transfinite ones [5,8]. A natural question is the following one: what is the correct extension of these results to higher levels $Δ_{n}^{0}$ , $n > 2$ , of the arithmetical hierarchy?

An obvious extension is obtained by relativizing these results to the nth iteration $\emptyset^{n}$ of the Turing jump starting with the empty set ∅, where $n < ω$ . Thus, we obtain the corresponding results for the relativized Ershov hierarchy ${Σ_{k}^{- 1, \emptyset^{n}}}_{k < ω}$ , the transfinite extension of which exhausts the class $Δ_{n + 2}^{0}$ [8]. As it was shown in [7], the relativized versions of Ershov’s hierarchy are (in contrast to the non-relativized one) coarse and admit many natural refinements which altogether provide a complete hierarchical classification of the arithmetical sets. Ordering the finite levels of all these refinements under inclusion, we obtain a sequence ${Σ_{α}}_{α < ε_{0}}$ , which we call the fine hierarchy (in [10] it was named the universal fine hierarchy of arithmetical sets).

Note that $ε_{0} = sup {ω, ω^{ω}, ω^{ω^{ω}}, \dots}$ is the well known ordinal closely related to the first order arithmetic and we have the equalities $Σ_{1}^{0} = Σ_{1}$ , $Σ_{2}^{0} = Σ_{ω}$ , $Σ_{3}^{0} = Σ_{ω^{ω}}$ , $Σ_{4}^{0} = Σ_{ω^{ω^{ω}}}$ , etc. Furthermore, for each $1 ⩽ k < ω$ we have $Σ_{k}^{- 1} = Σ_{k}$ , $Σ_{k}^{- 1, \emptyset^{'}} = Σ_{ω^{k}}$ , $Σ_{k}^{- 1, \emptyset^{2}} = Σ_{ω^{ω^{k}}}$ , $Σ_{k}^{- 1, \emptyset^{3}} = Σ_{ω^{ω^{ω^{k}}}}$ , etc. Also, for all $α < β < ε_{0}$ we have $Σ_{α} \cup Π_{α} \subseteq Δ_{β} = Σ_{β} \cap Π_{β}$ and $Σ_{α} ⊈ Π_{α}$ .

The fine hierarchy is, in a natural precise sense, the effective finitary version of the Wadge hierarchy for subsets of ω [10]. From results in [6] it follows that the m-degrees of sets complete in the levels of the fine hierarchy are among “natural m-degrees” which were formally defined and associated with the Wadge degrees in [6].

In this paper we discuss the problem of characterization the proper levels of the fine hierarchy with respect to Turing reducibility, i.e. levels which contain sets which are not Turing equivalent to the sets from the lesser levels (recall that any level of the fine hierarchy is proper with respect to m-reducibilty [7]).

First results about characterization of the proper level of the fine hierarchy were obtained in [11], where we showed that all levels $Σ_{λ + 1}$ ( $λ < ε_{0}$ is a limit ordinal) are not proper and that level $Σ_{ω + 2}$ is proper. Therefore, $Σ_{ω + 2}$ is the smallest proper “new” level of the fine hierarchy (i.e. a level distinct from all levels of the Ershov hierarchies relativized to $\emptyset^{n}$ , $n < ω$ ). The remarks above and results in [11] show that the levels $Σ_{α}$ , where $α \in {k + 1, ω^{k}, ω^{ω^{k}}, ω^{ω^{ω^{k}}}, \dots ∣ 1 ⩽ k < ω}$ , are proper. We also showed that any set witnessing the properness of a new level $Σ_{α}$ , $α < ω^{ω}$ , is Turing incomparable with $\emptyset^{'}$ .

Here we continue to study this problem, concentrating on levels of the fine hierarchy contained in $Δ_{3}^{0}$ , i.e. on the levels $Σ_{α}$ , $α < ω^{ω}$ . We show that any level $Σ_{ω + n + 2}$ , $n < ω$ , is proper, extending the main result of [11]; the proof of this result is a modification of the proof in [11]. Also, we prove that level $Σ_{ω + ω}$ contains a set which is not Turing equivalent to any $Δ_{ω + ω}$ -set. The constructions for the both these results can be performed in a uniform way, thus we combine them into one construction. The proofs use $0^{″}$ -priority arguments. In Section 2 we discuss our unified construction explaining intuition for a single strategy, in Section 3 we present the full formal construction, in Section 4 we verify the construction pointing out the differences for the both cases.

We do believe that our results are essential steps (the first result for successor levels, the second one for limit levels) to a complete characterization of proper levels $Σ_{α}$ , where $α < ω^{ω}$ , of the fine hierarchy, although the general case is probably very technical. Our guess is that for such an ordinal α the level $Σ_{α}$ is proper if and only if $α \neq λ + 1$ , where λ is a limit ordinal. We leave open the following question for the higher levels.

Question 1.
Is it true that for each infinite ordinal $α \in ε_{0} ∖ {λ + 1 ∣ λ is limit}$ the level $Σ_{α}$ is proper?

2. Notation and intuition

To understand the proofs below, the reader should have some familiarity with priority constructions on trees and the corresponding terminology. Most of these may be found in R. Soare’s book [12]. We will also use some more recent notation, in particular $Φ_{e}^{A} (x) [s]$ means $Φ_{e, s}^{A_{s}} (x)$ , and $A [s]$ means the approximation of a set $A \subseteq ω$ on stage s (the notion of approximation depends on the nature of A, below we define approximations to $Σ_{2}^{0}$ - and $Π_{2}^{0}$ -sets which are important in our proof). We say that x is enumerated into A (or we put x into A) at stage $s + 1$ if and only if we define $A (x) [s + 1] = 1$ while $A (x) [s] = 0$ ; respectively, an extraction x from A means $A (x) [s + 1] = 0$ while $A (x) [s] = 1$ . If a number x is not explicitly mentioned at stage $s + 1$ , then we mean $A (x) [s + 1] = A (x) [s]$ .

As usual, functionals are denoted by capital Greek letters while the corresponding small letters denote the related $use$ -functions, e.g. $φ (x) [s] = φ^{A} (x) [s]$ denotes the $use$ -function of the computation $Φ_{e}^{A} (x) [s]$ . Recall that a $use$ -function is defined only if the corresponding functional is defined. We often use computations $Φ_{e}^{τ} (x) [s]$ using finite strings $τ \in 2^{< ω}$ of zeroes and ones as oracles, the $use$ -function in this case is $φ (x) [s] = φ^{τ} (x) [s]$ . Without loss of generality we assume that $use$ -functions are non-decreasing on all their arguments (this applies to the values at a given stage of computation as well as to the values in the limit), and that if $φ (x)$ is defined then so are $φ (y)$ for all $y < x$ .

We state the main result of this paper as Theorem 1. Part (A) means that any level $Σ_{ω + n + 2}$ , $n < ω$ , of the fine hierarchy is proper, and Part (B) means that the level $Σ_{ω + ω}$ is proper. As it was mentioned above, the proofs for both parts are quite similar, hence we combine them into a unified proof, emphasizing from time to time specific details for Part (A) and Part (B).

Theorem 1.

For any $n < ω$ there exists a $Σ_{ω + n + 2}$ -set which is not Turing equivalent to any $Σ_{ω + n + 1}$ -set.

There exists a $Σ_{ω + ω}$ -set which is not Turing equivalent to any $Δ_{ω + ω}$ -set.

Part (A) for $n = 0$ was proved in [11], so we have to give a proof for $n > 0$ and for Part (B). The proof of Part (A) is slightly more complicated than that in [11]. The reason is that the proof in [11] used the fact that level $Σ_{ω + 1}$ is not proper, hence it was enough to construct a $Σ_{ω + 2}$ -set not Turing equivalent to any $Σ_{ω}$ -set. Since $Σ_{ω} = Σ_{2}^{0}$ , we had to diagonalize against $Σ_{2}^{0}$ -sets that is technically easier than to diagonalize against $Σ_{ω + 1}$ -sets. The proof of Part (B) is a modification of the proof from [11]. It seems reasonable to use the unified construction and point out the differences for Parts (A) and (B) in the verification. Our proof uses Cooper’s strategy (see [1,5,8]) along with the strategy from [11].

We start with recalling from [2,9,10] the definitions of the involved levels $Σ_{n + 1}^{- 1}$ , $Σ_{ω + n + 1}$ , $Δ_{ω + ω}$ , $Σ_{ω + ω}$ . The level $Σ_{n + 1}^{- 1}$ of the Ershov hierarchy consists of sets $⋃_{i ⩽ j} (W_{2 i + 1} ∖ W_{2 i})$ for $n = 2 j + 1$ , and consists of sets $W_{0} \cup ⋃_{i < j} (W_{2 i + 2} ∖ W_{2 i + 1})$ for $n = 2 j$ , where $W_{0} \subseteq \dots \subseteq W_{n}$ are c.e. sets.

The level $Σ_{ω + n + 1}$ of the fine hierarchy consists of all sets representable in the form $U \cup V \cup W$ where $U \in Σ_{2}^{0}$ , $V \in Π_{2}^{0}$ , and for some c.e. sets $Q_{0}, Q_{1}, W_{0}, \dots, W_{n}$ we have $Q_{0} \cup Q_{1} = W_{0} \subseteq \dots \subseteq W_{n}$ , $Q_{0} \cap Q_{1} = \emptyset$ , $U \subseteq Q_{0}$ , $V \subseteq Q_{1}$ , $W = ⋃_{i ⩽ j} (W_{2 i + 1} ∖ W_{2 i})$ for $n = 2 j + 1$ , and $W = ⋃_{i < j} (W_{2 i + 2} ∖ W_{2 i + 1})$ for $n = 2 j$ (i.e., W is the $Σ_{n + 1}^{- 1}$ -set from the previous paragraph without $W_{0}$ ). Note that $(Q_{0} \cup Q_{1}) \cap W = \emptyset$ .

The level $Σ_{ω + ω}$ (resp. $Δ_{ω + ω}$ ) of the fine hierarchy consists of all sets representable in the form $U \cup V \cup W$ where $U \in Σ_{2}^{0}$ , $V \in Π_{2}^{0}$ , $W \in Σ_{2}^{0}$ (resp. $W \in Δ_{2}^{0}$ ), and for some c.e. sets $Q_{0}$ , $Q_{1}$ we have $Q_{0} \cap Q_{1} = \emptyset$ , $U \subseteq Q_{0}$ , $V \subseteq Q_{1}$ , and $(Q_{0} \cup Q_{1}) \cap W = \emptyset$ . For the sake of uniformity we use below the same letters U, V, W, $Q_{0}$ , $Q_{1}$ for Part (A) and Part (B). For the sake of convenience we assume that $W_{0} = Q_{0} \cup Q_{1}$ holds for Part (B) too.

Using the reduction principle for c.e. sets and the standard numberings of c.e. sets and of $Σ_{2}^{0}$ -sets, we can define a natural computable numbering of all tuples $(U, V, Q_{0}, Q_{1}, W_{0}, \dots, W_{n})$ as above which induces a numbering ${D_{k}}$ of all $Σ_{ω + n + 1}$ -sets (equivalent to the computable principal numbering of $Σ_{ω + n + 1}$ constructed in [7] in a different way). Similarly we can define a computable principal numbering ${D_{k}}$ of all $Σ_{ω + ω}$ -sets.

Since our construction will be fully effective, we have also to define stage-wise approximations of $Σ_{ω + n + 1}$ -sets and of $Σ_{ω + ω}$ -sets. For $Σ_{ω + n + 1}$ -sets, the approximations are induced by the usual approximations for c.e. sets $Q_{0}, Q_{1}, W_{0}, \dots, W_{n}$ (which induce the corresponding approximation of W) and by approximations for $Σ_{2}^{0}$ -sets U and $Π_{2}^{0}$ -sets V used e.g. in [11]. Recall that an arbitrary computable function $f : ω \times ω \to {0, 1}$ may be considered as an approximation to the $Σ_{2}^{0}$ -set $f_{Σ} = {x ∣ \exists t \forall s [s > t \to f (x, s) = 1]}$ , and as an approximation to the $Π_{2}^{0}$ -set $f_{Π} = {x ∣ \forall t \exists s [s > t \land f (x, s) = 1]}$ . We say that f is a Σ-approximation to $f_{Σ} = {lim inf}_{s} f (x, s)$ and a Π-approximation to $f_{Π} = {lim sup}_{s} f (x, s)$ . Clearly, any $Σ_{2}^{0}$ -set (resp. $Π_{2}^{0}$ -set) is a Σ-approximation (resp. Π-approximation) via a suitable computable function. Moreover, there is a computable sequence ${g_{n}}$ of total computable functions $g_{n} : ω \times ω \to {0, 1}$ such that $g_{n}$ is a Σ-approximation of the set $W_{n}^{\emptyset^{'}}$ (here ${W_{n}^{\emptyset^{'}}}$ is the standard numbering of $Σ_{2}^{0}$ -sets). The existence of such a sequence ${g_{n}}$ follows, e.g., from the well known fact that the set ${x ∣ W_{x} finite}$ is $Σ_{2}^{0}$ -complete (here ${W_{n}}$ is the standard numbering of c.e. sets). This induces a Σ-approximations $U [s]$ for U and a Π-approximations $V [s]$ for V. Altogether, we obtain the desired stage-wise approximations for all $Σ_{ω + n + 1}$ -sets. Note that we may assume that the approximations $Q_{0} [s], Q_{1} [s], W_{0} [s], \dots, W_{n} [s]$ satisfy the same inclusions as $Q_{0}, Q_{1}, W_{0}, \dots, W_{n}$ , and $(U \cup V) [s] \subseteq W_{0} [s] = Q_{0} [s] \cup Q_{1} [s]$ .

For $Σ_{ω + ω}$ -sets, the approximations are induced by the same approximations as above for sets U, V, $Q_{0}$ , $Q_{1}$ , and by the approximations for $Σ_{2}^{0}$ -sets $W = g_{Σ}$ induced by the above-mentioned computable functions $g = g_{k}$ .

Thus, Part (A) can be formulated as follows: There exist $A \in Σ_{2}^{0}$ , $B \in Π_{2}^{0}$ , c.e. sets $E_{0}, E_{1}, C_{0}, \dots, C_{n + 1}$ such that $E_{0} \cup E_{1} = C_{0} \subseteq \dots \subseteq C_{n + 1}$ , $E_{0} \cap E_{1} = \emptyset$ , $A \subseteq E_{0}$ , $B \subseteq E_{1}$ , $C = ⋃_{i ⩽ j} (C_{2 i + 1} ∖ C_{2 i})$ for $n + 1 = 2 j + 1$ , and $C = ⋃_{i < j} (C_{2 i + 2} ∖ C_{2 i + 1})$ for $n + 1 = 2 j$ , and the set $A \cup B \cup C$ is not Turing equivalent to any $Σ_{ω + n + 1}$ -set.

The c.e. sets $E_{0}, E_{1}, C_{0}, \dots, C_{n + 1}$ will be constructed by stages, their stage-wise approximations will induce an approximation of C. The set A will be constructed as the Σ-approximation of a computable function $a : ω \times ω \to {0, 1}$ , defined during the construction; hence, $A = a_{Σ}$ and, for convenience, we identify $A (x) [s]$ and $a (x, s)$ . Similarly, $B = b_{Π}$ will be the Π-approximation of a computable function $b : ω \times ω \to {0, 1}$ , and $B (x) [s] = b (x, s)$ . In the construction we use approximations of $Σ_{ω + n + 1}$ -sets described above.

Similarly, Part (B) can be formulated as follows: There exist disjoint c.e. sets $E_{0}$ , $E_{1}$ , $Σ_{2}^{0}$ -set $A \subseteq E_{0}$ , $Π_{2}^{0}$ -set $B \subseteq E_{1}$ , $Σ_{2}^{0}$ -set C such that $(E_{0} \cup E_{1}) \cap C = \emptyset$ and the set $A \cup B \cup C$ is not Turing equivalent to any $Δ_{ω + ω}$ -set D specified as above.

For the proof we construct sets A, B, $E_{0}$ , $E_{1}$ similarly to Part (A) but this time the set C is $Σ_{2}^{0}$ ; hence $A \cup B \cup C$ is a $Σ_{ω + ω}$ -set. The set C is constructed as the Σ-approximation of a computable function $c : ω \times ω \to {0, 1}$ .

To prove the theorem, we work with the series of requirements $\begin{matrix} R_{k} = R_{Φ, Ψ, D} : A \cup B \cup C \neq Φ^{D} \lor D \neq Ψ^{A \cup B \cup C}, \end{matrix}$ where $⟨ Φ, Ψ, D ⟩ = ⟨ Φ_{k}, Ψ_{k}, D_{k} ⟩$ is kth element in a computable enumeration of all triples formed by partial computable functionals $Φ_{k}$ , $Ψ_{k}$ and $Σ_{ω + n + 1}$ -sets $D_{k}$ for Part (A) (resp. $Σ_{ω + ω}$ -sets $D_{k}$ for Part (B)).

Notice that for Part (A) we need satisfy all requirements while for Part (B) it is enough to satisfy only the requirements where the set D is in $Δ_{ω + ω}$ .

Since we have a $0^{″}$ -priority argument involving a tree construction, we describe first a strategy satisfying one isolated requirement $R_{Φ, Ψ, D}$ and analyze the typical difficulties. In parenthesis we give some comments in italic which may ease the intuitive understanding of what is going on. We omit the indices of parameters x, τ, σ whenever they are clear from the context. Recall that $D = U \cup V \cup W$ .
Intuition for a single strategy of a requirement $R_{Φ, Ψ, D}$ .

Choose a “big” witness x.

(“Big” means the least number which was not mentioned in the construction so far.)

Wait for a stage $s_{0}$ and for a string τ of length $< s_{0}$ such that $\begin{matrix} {Φ^{τ} (x) [s_{0}] = (A \cup B \cup C) (x) [s_{0}] = 0} \land {Ψ^{A \cup B \cup C} ↾ | τ | [s_{0}] = τ} \land {\forall z (τ (z) = 1 \to (\exists p ⩽ s_{0} z \in W [p]))} . \end{matrix}$

(Note that, in contrast to [ 11 ], we search for τ with the additional property specified by the last conjunct. It is needed only for Part (A) since we have limited number of changes in the constructed C; however it doesn’t have negative influence for Part (B) which allows us to use the conjunct in the unified construction. Hence, if $Φ^{D} (x) = (A \cup B \cup C) (x) \land Ψ^{A \cup B \cup C} ↾ φ^{D} (x) = D ↾ φ^{D} (x)$ then such a string does exist (in particular, some initial segment D will satisfy the condition). Otherwise, the requirement will be satisfied automatically. Note that, in general, τ does not need to be an initial segment of D.)

Put x into C at the stage $s_{0} + 1$ (recall that this, in particular, means $C (x) [s_{0} + 1] = 1$ and $C (x) [s_{0}] = 0$ ).

(Thus, we have $Φ^{τ} (x) [s_{0}] = 0 = (A \cup B \cup C) (x) [s_{0}]$ and $Ψ^{A \cup B \cup C} ↾ | τ | [s_{0}] = τ$ , but $Φ^{τ} (x) [s_{0} + 1] = 0 \neq 1 = (A \cup B \cup C) (x) [s_{0} + 1]$ . Since possibly $D ↾ | τ | [s_{0}] = D ↾ | τ | = τ$ , we make an attempt of diagonalization by changing $(A \cup B \cup C) (x) [s]$ . This attempt will either succeed with diagonalization or will lead to a new string σ incomparable with τ.)

Wait for a stage $s_{1} > s_{0}$ and search for a string σ of length $< s_{1}$ such that $\begin{matrix} {Φ^{σ} (x) [s_{1}] = (A \cup B \cup C) (x) [s_{1}] = 1} \land {Ψ^{A \cup B \cup C} ↾ | σ | [s_{1}] = σ} \land {\forall z (σ (z) = 1 \to (\exists p ⩽ s_{1} z \in W [p]))} . \end{matrix}$

(A string σ exists by the same reason as τ (otherwise, the requirement is satisfied automatically). Since τ and σ are incomparable, there is the least $z_{0}$ with $τ (z_{0}) \neq σ (z_{0})$ and $\exists p ⩽ s_{1}$ $z_{0} \in W [p]$ (the last condition is crucial for using Cooper’s strategy below). Note that $Ψ^{A \cup B \cup C} (z_{0}) [s_{0}] = τ (z_{0})$ , $Ψ^{A \cup B \cup C} (z_{0}) [s_{1}] = σ (z_{0})$ , and the value $Ψ^{A \cup B \cup C} (z_{0})$ is under our control which opens a possibility of a diagonalization attack against D.)

Let $z_{0}$ be the least number such that $τ (z_{0}) \neq σ (z_{0})$ . There are two alternatives now:
$τ (z_{0}) = 0$ ,

$τ (z_{0}) = 1$ .
In case $C 1$ ) we go to item (6), in case $C 2$ ) we go to item (8).

(Since we need diagonalize against $Σ_{n + 1}^{- 1}$ - or $Δ_{2}^{0}$ -set W (before $z_{0}$ enters $W_{0} = Q_{0} \cup Q_{1}$ ) we want to get $W (z_{0}) \neq Φ^{A \cup B \cup C} (z_{0})$ (if $z_{0}$ doesn’t enter $W_{0} = Q_{0} \cup Q_{1}$ ). Now we are in a position to use Cooper’s strategy for Ershov’s hierarchy (see e.g. [ 1 , 5 ] or [ 8 ]) consisting in waiting for a moment when $z_{0}$ changes its position in W and then changing the position of x in C (note also that it can happen infinitely often for Part (B)). This strategy either diagonalizes our requirement or forces $z_{0}$ to enter $W_{0} = Q_{0} \cup Q_{1}$ (before x enters $C_{0} = E_{0} \cup E_{1}$ ) or forces W to be non- $Δ_{2}^{0}$ . Note that for each stage s it holds $(A \cup B \cup C) (x) [s] = 0 \leftrightarrow Ψ^{A \cup B \cup C} (z_{0}) [s] = τ (z_{0})$ .)

(For Part (A): Assume that $z_{0}$ will not enter $W_{0} = Q_{0} \cup Q_{1}$ . If $τ (z_{0}) = 0$ then $C (x)$ made one change and $W (z_{0})$ could make zero changes (up to stage $s_{1}$ ). If $τ (z_{0}) = 1$ then $z_{0}$ entered W at some stage before $s_{0}$ (due to the last conjunct of item (2)), hence $C (x)$ made one change and $W (z_{0})$ made at least one change (up to stage $s_{1}$ ). Items (6)–(9) show that each change of $W (z_{0})$ is accompanied by a change of $C (x)$ , moreover these changes provides a temporary diagonalization $D (z_{0}) [s] = W (z_{0}) [s] \neq Ψ^{A \cup B \cup C} (z_{0}) [s]$ which forces an additional change of $W (z_{0})$ . Hence, we can keep C as $(n + 2)$ -c.e. set when W is $(n + 1)$ -c.e. set, and it is enough to win.)

(For Part (B): Assume that $z_{0}$ will never enter $W_{0} = Q_{0} \cup Q_{1}$ . If W is $Δ_{2}^{0}$ and $W (z_{0})$ changes only finitely often then the diagonalization will be achieved via an additional change of $(A \cup B \cup C) (x) = C (x)$ . Hence, either we win or $W (z_{0})$ shall try to do one more change. However, if W is not $Δ_{2}^{0}$ and $W (z_{0})$ can change infinitely often then we don’t need satisfy our requirement and we can keep C as $Σ_{2}^{0}$ .)

Wait for a stage $s_{2} > s_{1}$ such that $W_{0} (z_{0}) [s_{2}] = 1$ or $W (z_{0}) [s_{2}] = σ (z_{0}) = 1$ . At this stage, if the left disjunct is true then go to item (10), if the left disjunct is false and the right disjunct is true then extract x from C and go to item (7).

(Hence, if $W (z_{0})$ will not change later then we have $D (z_{0}) = D (z_{0}) [s_{2}] = W (z_{0}) [s_{2}] = 1 \neq 0 = τ (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{2} + 1] = Ψ^{A \cup B \cup C} (z_{0})$ and the requirement is satisfied.)

(Note also that in case of infinite alternation between (6) and (7) we have that W is not $Δ_{2}^{0}$ , thus $D = U \cup V \cup W$ is not $Δ_{ω + ω}$ .)

Wait for a stage $s_{3} > s_{2}$ such that $W_{0} (z_{0}) [s_{3}] = 1$ or $W (z_{0}) [s_{3}] = τ (z_{0}) = 0$ . At this stage, if the left disjunct is true then go to item (10), if the left disjunct is false and the right disjunct is true then put x into C and go to item (6), with $s_{1}$ renamed to $s_{3}$ .

(Hence, if $W (z_{0})$ will not change later then we have $D (z_{0}) = D (z_{0}) [s_{3}] = W (z_{0}) [s_{3}] = 0 \neq 1 = σ (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{3} + 1] = Ψ^{A \cup B \cup C} (z_{0})$ and the requirement is satisfied.)

Wait for a stage $s_{4} > s_{1}$ such that $W_{0} (z_{0}) [s_{4}] = 1$ or $W (z_{0}) [s_{4}] = τ (z_{0}) = 1$ . At this stage, if the left disjunct is true then go to item (10), if the left disjunct is false and the right disjunct is true then extract x from C and go to item (9).

(Note also that in case of infinite alternation between (8) and (9) we have that W is not $Δ_{2}^{0}$ .)

Wait for a stage $s_{5} > s_{4}$ such that $W_{0} (z_{0}) [s_{5}] = 1$ or $W (z_{0}) [s_{5}] = σ (z_{0}) = 0$ . At this stage, if the left disjunct is true then go to item (10), if the left disjunct is false and the right disjunct is true then put x into C and go to item (8), with $s_{1}$ renamed to $s_{5}$ .

Assume it happened at stage $s_{6}$ . Since $W_{0} [s_{6}] = Q_{0} [s_{6}] \cup Q_{1} [s_{6}]$ there are now four alternatives which determine the further behavior of our strategy:
$τ (z_{0}) = 1$ and $z_{0} \in Q_{0} [s_{6}]$ ,

$τ (z_{0}) = 0$ and $z_{0} \in Q_{0} [s_{6}]$ ,

$τ (z_{0}) = 1$ and $z_{0} \in Q_{1} [s_{6}]$ ,

$τ (z_{0}) = 0$ and $z_{0} \in Q_{1} [s_{6}]$ .
In case $A 1$ ) we put x into $E_{0}$ and go to item (11) below, then further attacks will be made via A (note that here $D (z_{0}) = U (z_{0})$ ).

In case $B 1$ ) we put x into $E_{1}$ and go to item (13) below, then further attacks will be made via B (note that here $D (z_{0}) = U (z_{0})$ too).

In case $B 2$ ) we put x into $E_{1}$ and go to item (15) below, then further attacks will be made via B (note that here $D (z_{0}) = V (z_{0})$ ).

In case $A 2$ ) we put x into $E_{0}$ and go to item (17) below, then further attacks will be made via A (note that here $D (z_{0}) = V (z_{0})$ too).

(Furthermore, since the $Σ_{2}^{0}$ -set A and $Π_{2}^{0}$ -set B are at our disposal, it is possible to define $(A \cup B \cup C) (x)$ either as a Σ-approximation or as a Π-approximation. Consequently, in the first case this leads to $Ψ^{A \cup B \cup C} (z_{0}) = τ (z_{0})$ , while in the second case to $Ψ^{A \cup B \cup C} (z_{0}) = σ (z_{0})$ . Thus, expecting an infinite confrontation with D and having τ and σ at our disposal, we can choose the correct option of the attack which in the limit yields $Ψ^{A \cup B \cup C} (z_{0}) = 1 \neq 0 = D (z_{0})$ . If $D (z_{0}) [s]$ changes infinitely often then (in cases $A 1$ ) and $B 1$ )) $z_{0} \notin D$ . Then in case $τ (z_{0}) = 0$ the attack is via B, so $x \in A \cup B \cup C$ and $Ψ^{A \cup B \cup C} (z_{0}) = σ (z_{0}) = 1 \neq 0 = D (z_{0})$ . In case $τ (z_{0}) = 1$ the attack is via A, so $x \notin A \cup B \cup C$ and $Ψ^{A \cup B \cup C} (z_{0}) = τ (z_{0}) = 1 \neq 0 = D (z_{0})$ , and the requirement is satisfied as well. The cases $B 2$ ), $A 2$ ) are treated similarly.)

Wait for a stage $s_{7} > s_{6}$ such that $\forall t \in (s_{6}, s_{7}]$ $D (z_{0}) [t] = 1$ . At this stage, put x into A and go to item (12).

(Here our goal is to force the approximation $D (z_{0})$ to coincide with $τ (z_{0}) = 1$ (otherwise, diagonalization will occur automatically). Since $x \notin (A \cup B \cup C) [s_{7}]$ , we have $Ψ^{A \cup B \cup C} (z_{0}) [s_{7}] = τ (z_{0})$ . Thus, if for some $t \in (s_{6}, s_{7}]$ we found $D (z_{0}) [t] = 0$ , there is a suspicion that in the limit we have $D (z_{0}) = 0$ and we already have the diagonalization. If we suspect that $D (z_{0}) = 1$ then we have to continue the diagonalization attempts. For the formal construction we note that the existence or non-existence of stage t will be important because we will deal with the strategy $R_{Φ, Ψ, D}$ not on all stages but the approximations should be traced at intermediate stages too.)

(Recall that, in (11) and (12) we have $D (z_{0}) = U (z_{0})$ , and U is $Σ_{2}^{0}$ .)

Wait for a stage $s_{8} > s_{7}$ such that $\exists t \in (s_{7}, s_{8}]$ $D (z_{0}) [t] = 0$ . At this stage, remove x from A and go to item (11), with $s_{6}$ renamed to $s_{8}$ .

(Respectively, here we have $Ψ^{A \cup B \cup C} (z_{0}) [s_{8}] = σ (z_{0}) = 0$ , so for the future attacks $D (z_{0})$ should coincide in the Σ-limit with 0 (otherwise, diagonalization is automatic). Recall that, in case of the infinite alternation of items (11) and (12), we have $Ψ^{A \cup B \cup C} (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{0}] = τ (z_{0}) = 1 \neq 0 = D (z_{0})$ , i.e. the requirement will be satisfied.)

Wait for a stage $s_{9} > s_{6}$ such that $\exists t \in (s_{6}, s_{9}]$ $D (z_{0}) [t] = 0$ . At this stage, put x into B and go to item (14).

(Here our goal is to force the approximation $D (z_{0})$ to coincide with $τ (z_{0}) = 0$ . Since $x \notin (A \cup B \cup C) [s_{9}]$ , we have $Ψ^{A \cup B \cup C} (z_{0}) [s_{9}] = τ (z_{0})$ . Thus, if for all $t \in (s_{6}, s_{9}]$ we have $D (z_{0}) [t] = 1$ , then there is a suspicion that in the limit we have $D (z_{0}) = 1$ , hence the diagonalization already holds. If we suspect that $D (z_{0}) = 0$ , then we have to continue the diagonalization attempts via changing $B (x)$ .)

(Recall that, in (13) and (14) we have $D (z_{0}) = U (z_{0})$ , and U is $Σ_{2}^{0}$ .)

Wait for a stage $s_{10} > s_{9}$ such that $\forall t \in (s_{9}, s_{10}]$ $D (z_{0}) [t] = 1$ . At this stage, remove x from B and go to item (13), with $s_{6}$ renamed to $s_{10}$ .

(Respectively, here we have $Ψ^{A \cup B \cup C} (z_{0}) [s_{10}] = σ (z_{0}) = 0$ , so for the future attacks $D (z_{0})$ should look like 0 in the Σ-limit (otherwise, diagonalization is automatic). Recall that, in case of infinite alternation between (14) and (15), we have $Ψ^{A \cup B \cup C} (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{1}] = σ (z_{0}) = 1 \neq 0 = D (z_{0})$ , i.e. the requirement is satisfied.)

Wait for a stage $s_{11} > s_{6}$ such that $\exists t \in (s_{6}, s_{11}]$ $D (z_{0}) [t] = 1$ . At this stage, we put x into B and go to item (16).

(Recall that, in (15) and (16) we have $D (z_{0}) = V (z_{0})$ , and V is $Π_{2}^{0}$ . Thus, similarly to the comments for (11)–(14), in case of infinite alternation between (15) and (16) we obtain $Ψ^{A \cup B \cup C} (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{1}] = σ (z_{0}) = 0 \neq 1 = D (z_{0})$ .)

Wait for a stage $s_{12} > s_{11}$ such that $\forall t \in (s_{11}, s_{12}]$ $D (z_{0}) [t] = 0$ . At this stage, remove x from B and go to item (15), with $s_{6}$ renamed to $s_{12}$ .

Wait for a stage $s_{13} > s_{6}$ such that $\forall t \in (s_{6}, s_{13}]$ $D (z_{0}) [t] = 0$ . At this stage, put x into A and go to item (18).

(Recall that, in (17) and (18) we have $D (z_{0}) = V (z_{0})$ , and V is $Π_{2}^{0}$ . Thus, similarly to the comments for (11)–(14), in case of infinite alternation between (17) and (18) we obtain $Ψ^{A \cup B \cup C} (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{0}] = τ (z_{0}) = 0 \neq 1 = D (z_{0})$ .)

Wait for a stage $s_{14} > s_{13}$ such that $\exists t \in (s_{13}, s_{14}]$ $D (z_{0}) [t] = 1$ . At this stage, remove x from A and go to item (17), with $s_{6}$ renamed to $s_{14}$ .

In order to prove the theorem we have to satisfy infinitely many requirements $R_{k}$ in one construction. This causes additional complications since, during the work of a strategy $R_{k}$ , the witnesses of strategies $R_{m}$ ( $m \neq k$ ) could change the set $(A \cup B \cup C) [s]$ infinitely often, which can lead the strategy $R_{k}$ to wrong actions. To overcome these complications we assign to each strategy three types of outcomes which will be used for additional analysis during a priority construction.

Outcome Σ denotes that either $x \in E_{0}$ (which means that there are infinitely many attacks through A, hence we work with a Σ-approximation of A) or there are infinitely many attacks through C (in Part (B) of the theorem which means that the corresponding set W is not $Δ_{2}^{0}$ , hence the requirement is satisfied vacuously).

Outcome Π denotes that $x \in E_{1}$ and there are infinitely many attacks through B, hence we work with a Π-approximation of B.

Outcome $fin$ denotes a diagonalization after finite number of actions.
3. The full construction

In the construction a strategy ρ at stage $s + 1$ has outcome Σ if and only if $A (x) [s + 1] = 1 \neq 0 = A (x) [s]$ or $C (x) [s + 1] = 1 \neq 0 = C (x) [s]$ , which means that the strategies below outcome Σ see the true value of $A (x) = A (x) [s] = 0$ or $C (x) = C (x) [s] = 0$ (if outcome Σ appears infinitely often). Similar argument applies to the Π-outcome: at stage $s + 1$ , a strategy ρ has outcome Π if and only if $B (x) [s + 1] = 0 \neq 1 = B (x) [s]$ . Thus, the strategies at the stage $s + 1$ below this outcome use values $B (x) [s] = 1$ , which in the limit yields $B (x) = 1$ (if outcome Π is visited infinitely often). Note also that after the stage, when x enters $E_{0} \cup E_{1}$ , one of the outcomes (either Σ or Π) will never be visited. Outcome $fin$ at stage $s + 1$ is assigned in all other cases.

The tree of strategies. The tree of strategies is defined as the full 3-branching tree $T = {Σ, Π, fin}^{< ω}$ , where we assume $Σ < Π < fin$ . We identify nodes, finite branches and strategies. We order nodes of the tree in a standard way: $ρ < ρ^{'}$ , if $ρ \subset ρ^{'}$ or there exists $i < | ρ |$ such that $ρ (i) < ρ^{'} (i)$ and $\forall j < i$ $ρ (j) = ρ^{'} (j)$ . A strategy ρ works in order to satisfy the requirement $R_{| ρ |} = R_{Φ, Ψ, D}$ . We say that ρ has higher priority than $ρ^{'}$ if and only if $ρ < ρ^{'}$ .

In the construction we use standard notation and terminology. In particular, if a set or a parameter is not redefined explicitly then it keeps its value. When we initialize a strategy we undefine (cancel) all its parameters (namely, its witness x and its strings τ and σ). “Big” number means the first number not mentioned explicitly in the construction so far (in particular, it is greater than all defined $use$ -functions). Sometimes we omit indices or stages when they are clear from the context. Recall that $D = U \cup V \cup W$ , also we denote $D [s] = U [s] \cup V [s] \cup W [s]$ .

Construction.

Stage $s = 0$ . Define $A [s] = B [s] = C [s] = E_{0} [s] = E_{1} [s] = \emptyset$ .

Stage $s + 1 > 0$ . Given approximations $A [s]$ , $B [s]$ , $C [s]$ , $E_{0} [s]$ , $E_{1} [s]$ , $U [s]$ , $V [s]$ , $W [s]$ , $Q_{0} [s]$ , $Q_{1} [s]$ , $U [s + 1]$ , $V [s + 1]$ , $W [s + 1]$ , $Q_{0} [s + 1]$ , $Q_{1} [s + 1]$ (we consider only elements $⩽ s$ ), we define $A [s + 1]$ , $B [s + 1]$ , $C [s + 1]$ , $E_{0} [s + 1]$ , $E_{1} [s + 1]$ . Recall that $C_{0} [s + 1]$ is defined as $E_{0} [s + 1] \cup E_{1} [s + 1]$ and $W_{0} [s + 1] = Q_{0} [s + 1] \cup Q_{1} [s + 1]$ at each stage. Using substages $0 ⩽ t ⩽ s + 1$ , by induction we build a computable approximation ${TP}_{s + 1}$ of the True Path such that $| {TP}_{s + 1} | = s + 1$ . We define ${TP}_{s + 1, 0} = λ$ (the empty string). At substage $t + 1$ we define ${TP}_{s + 1, t + 1}$ ; after the last substage $s + 1 = t + 1$ we define ${TP}_{s + 1} = {TP}_{s + 1, s + 1}$ and initialize all strategies $η > {TP}_{s + 1}$ .

Substage $t + 1$ . Assume that ${TP}_{s + 1, t} = ρ$ . We need to define ${TP}_{s + 1, t + 1}$ , which is equivalent to defining outcome of ρ at stage $s + 1$ . Consider the following alternative cases. When we find the unique case that holds we do the corresponding action and go to the next substage $t + 2$ .

The witness $x = x_{ρ} [s]$ is not defined.

Define $x_{ρ} [s + 1]$ as “big” number, define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies $η > ρ^{⌢} fin$ .

Case $ρ 1$ fails (i.e., x is defined) and the string $τ_{ρ} [s]$ is not defined.

Define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ . Look for the least (in the lexicographical order) string τ of length $< s$ such that $Φ^{τ} (x) [s] = (A \cup B \cup C) (x) [s] \land Ψ^{A \cup B \cup C} ↾ | τ | [s] = τ \land \forall z (τ (z) = 1 \to (\exists p ⩽ s z \in W [p]))$ . If there is such a string then define $τ_{ρ} [s + 1] = τ$ , enumerate x into C and initialize all strategies $η > ρ^{⌢} fin$ . Otherwise, do nothing.

(This case corresponds to waiting in item (2) and actions in item (3) in the intuitive description.)

Cases $ρ 1$ and $ρ 2$ fail (i.e. x and τ are defined) and the string $σ_{ρ} [s]$ is not defined.

Define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ . Look for the least (in the lexicographical order) string σ of length $< s$ such that $Φ^{σ} (x) [s] = (A \cup B \cup C) (x) [s] \land Ψ^{A \cup B \cup C} ↾ | σ | [s] = σ$ and $\forall z$ $(σ (z) = 1 \to (\exists p ⩽ s z \in W [p]))$ . If there is such a string then initialize all strategies $η > ρ^{⌢} fin$ , define $σ_{ρ} [s + 1] = σ$ and denote by $z_{0}$ the least number z such that $τ (z) \neq σ (z)$ . Otherwise, do nothing.

(This case corresponds to waiting in item (4) and actions in item (5) of the intuitive description.)

Cases $ρ 1$ – $ρ 3$ fail (i.e. x, τ, σ are defined) and $z_{0} \notin W_{0} [s] = Q_{0} [s] \cup Q_{1} [s]$ .

Consider subcases.

There hold $τ (z_{0}) = 0$ and $W (z_{0}) [s] = 0$ , and $x \notin C [s]$ .

Put x into C (i.e., define $C (x) [s + 1] = 1$ ) and define ${TP}_{s + 1, t + 1} = ρ^{⌢} Σ$ .

(This case corresponds to item (7) of the intuitive description.)

(Note that here we can consider approximation to W at the current stage, contrary to subcases of $ρ 6$ ; also here it doesn’t matter whether W is $Δ_{2}^{0}$ .)

There hold $τ (z_{0}) = 0$ and $W (z_{0}) [s] = 1$ , and $x \in C [s]$ .

Remove x from C (i.e., define $C (x) [s + 1] = 0$ ), define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies η such that $η > ρ^{⌢} Σ$ and $ρ^{⌢} Σ ⊈ η$ .

(This case corresponds to item (6) of the intuitive description.)

There hold $τ (z_{0}) = 1$ and $W (z_{0}) [s] = 1$ and $x \notin C [s]$ .

Put x into C (i.e., define $C (x) [s + 1] = 1$ ) and define ${TP}_{s + 1, t + 1} = ρ^{⌢} Σ$ .

(This case corresponds to item (9) of the intuitive description.)

(Note that here it suffices to consider approximation to W at the current stage while in subcases of $ρ 6$ we have to deal with approximations at intervals; also here it doesn’t matter whether W is $Δ_{2}^{0}$ or not.)

There hold $τ (z_{0}) = 1$ and $W (z_{0}) [s] = 0$ , and $x \in C [s]$ .

Remove x from C (i.e., define $C (x) [s + 1] = 0$ ), define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies η such that $η > ρ^{⌢} Σ$ and $ρ^{⌢} Σ ⊈ η$ .

(This case corresponds to item (8) of the intuitive description.)

In all other subcases we define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ .

(This case corresponds to waiting in items (6)–(9) of the intuitive description.)

(Basically we follow Cooper’s strategy until $z_{0} \in Q_{0} \cup Q_{1}$ , i.e. wait for a $z_{0} \in W [s]$ ( $z_{0} \notin W [s]$ ) and put x into C (extract x from C) immediately afterwards (initializing at such stages the lower priority strategies); hence, if W is $(n + 1)$ -c.e. then C is $(n + 2)$ -c.e. and we always have an extra change.)

Cases $ρ 1$ – $ρ 4$ fail (i.e. x, τ, σ are defined, $z_{0} \in W_{0} [s]$ ) and $x \notin C_{0} [s]$ .

Define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , initialize the lower strategies. Since $z_{0} \in W_{0} [s]$ , we have $z_{0} \in Q_{0} [s]$ or $z_{0} \in Q_{1} [s]$ . If ( $τ (z_{0}) = 1$ and $z_{0} \in Q_{0} [s]$ ) or ( $τ (z_{0}) = 0$ and $z_{0} \in Q_{1} [s]$ ), put x into $E_{0}$ , otherwise put x into $E_{1}$ (hence $x \in C_{0} [s + 1]$ and $x \notin C [s + 1]$ ).

(This case corresponds to actions in item (10) of the intuitive description, recall that $z_{0}$ exists since τ and σ has to be incomparable.)

Cases $ρ 1$ – $ρ 5$ fail.

Let $s^{-}$ be the previous stage when we visited ρ. Consider subcases.

$\forall t \in (s^{-}, s]$ $D (z_{0}) [t] = 1$ , $τ (z_{0}) = 1$ , $z_{0} \in Q_{0} [s]$ (hence $x \in E_{0} [s]$ ), and $x \notin A [s]$ .

Put x into A (i.e., define $A (x) [s + 1] = 1$ ) and define ${TP}_{s + 1, t + 1} = ρ^{⌢} Σ$ .

(This case corresponds to item (11) of the intuitive description.)

$\exists t \in (s^{-}, s]$ $D (z_{0}) [t] = 0$ , $τ (z_{0}) = 1$ , $z_{0} \in Q_{0} [s]$ , and $x \in A [s]$ .

Remove x from A (i.e., define $A (x) [s + 1] = 0$ ), define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies η such that $η > ρ^{⌢} Σ$ and $ρ^{⌢} Σ ⊈ η$ .

(This case corresponds to item (12) of the intuitive description.)

$\forall t \in (s^{-}, s]$ $D (z_{0}) [t] = 1$ , $τ (z_{0}) = 0$ , $z_{0} \in Q_{0} [s]$ (hence $x \in E_{1} [s]$ ), and $x \in B [s]$ .

Remove x from B (i.e., define $B (x) [s + 1] = 0$ ) and define ${TP}_{s + 1, t + 1} = ρ^{⌢} Π$ .

(This case corresponds to item (13) of the intuitive description.)

$\exists t \in (s^{-}, s]$ $D (z_{0}) [t] = 0$ , $τ (z_{0}) = 0$ , $z_{0} \in Q_{0} [s]$ , and $x \notin B [s]$ .

Put x into B (i.e., define $B (x) [s + 1] = 1$ ), define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies η such that $η > ρ^{⌢} Π$ and $ρ^{⌢} Π ⊈ η$ .

(This case corresponds to item (14) of the intuitive description.)

$\exists t \in (s^{-}, s]$ $D (z_{0}) [t] = 1$ , $τ (z_{0}) = 1$ , $z_{0} \in Q_{1} [s]$ (hence $x \in E_{1} [s]$ ), and $x \notin B [s]$ .

Put x into B (i.e., define $B (x) [s + 1] = 1$ ) and define ${TP}_{s + 1, t + 1} = ρ^{⌢} Π$ .

(This case corresponds to item (15) of the intuitive description.)

$\forall t \in (s^{-}, s]$ $D (z_{0}) [t] = 0$ , $τ (z_{0}) = 1$ , $z_{0} \in Q_{1} [s]$ , and $x \in B [s]$ .

Remove x from B (i.e., define $B (x) [s + 1] = 0$ ), define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies η such that $η > ρ^{⌢} Π$ and $ρ^{⌢} Π ⊈ η$ .

(This case corresponds to item (16) of the intuitive description.)

$\forall t \in (s^{-}, s]$ $D (z_{0}) [t] = 0$ , $τ (z_{0}) = 0$ , $z_{0} \in Q_{1} [s]$ (hence $x \in E_{0} [s]$ ), and $x \notin A [s]$ .

Put x into A (i.e., define $A (x) [s + 1] = 1$ ) and define ${TP}_{s + 1, t + 1} = ρ^{⌢} Σ$ .

(This case corresponds to item (17) of the intuitive description.)

$\exists t \in (s^{-}, s]$ $D (z_{0}) [t] = 1$ , $τ (z_{0}) = 0$ , $z_{0} \in Q_{1} [s]$ , and $x \in A [s]$ .

Remove x from A (i.e., define $A (x) [s + 1] = 0$ ), define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ , and initialize all strategies η such that $η > ρ^{⌢} Σ$ and $ρ^{⌢} Σ ⊈ η$ .

(This case corresponds to item (18) of the intuitive description.)

In the remaining subcases define ${TP}_{s + 1, t + 1} = ρ^{⌢} fin$ and do nothing else.

(This case corresponds to waiting in items (11)–(18) of the intuitive description.)

End of construction.

4. Verification

The proofs of Part (A) and Part (B) are very similar. The main difference is as follows: Part (B) (in contrast to Part (A)) must take into account a possible infinite alternation of cases $ρ 4.1$ – $ρ 4.2$ or $ρ 4.3$ – $ρ 4.4$ . However, in these cases W is not $Δ_{2}^{0}$ and hence we don’t need to bother about satisfaction of the corresponding requirement $R_{| ρ |}$ . The behavior in this case of such a strategy with outcome Σ with respect to other strategies is similar to its behavior in case $ρ 6$ with Σ-outcome. Now we proceed to the proof.

We define the true path $TP$ as the leftmost visited infinitely often branch of the tree of strategies, i.e. $TP = {lim inf}_{s} {TP}_{s}$ . It clearly exists since $| {TP}_{s} | = s$ for each $s \in ω$ , and the tree of strategies is finitely branching. To prove the theorem, it suffices to show that any requirement $R_{| ρ |}$ is satisfied by the corresponding strategy $ρ \in TP$ on the true path (for Part (B) we also ask $D_{| ρ |}$ to be $Δ_{ω + ω}$ in order to satisfy ρ). By the definition of the true path, there is a stage $s_{0}$ such that ${TP}_{s} > ρ$ for all $s > s_{0}$ . Let $ρ = ξ^{⌢} outcome$ where $outcome \in {Σ, Π, fin}$ (for the empty string the proof is a simplified version of the proof for non-empty string ρ given below). First we show that ρ is initialized only finitely many times (note that the empty string is never initialized). Assume by induction that ξ is not initialized after some stage $s_{1}^{'} > s_{0}$ , then all substrings of ξ are not initialized after $s_{1}^{'}$ . After $s_{1}^{'}$ , an initialization of ρ may happen only because of ξ, so consider the possible values of $outcome$ .

Note that, because of cases $ρ 1$ – $ρ 3$ , at most three initializations may happen (whatever $outcome$ is), i.e., after some stage $> s_{1}^{'}$ we always have cases $ρ 4$ – $ρ 6$ . Furthermore, if $outcome = Σ$ or $outcome = Π$ , then ρ is not initialized. If $outcome = fin$ then initialization may happen only because of cases $ρ 4.2$ , $ρ 4.4$ , $ρ 6.2$ , $ρ 6.4$ , $ρ 6.6$ , $ρ 6.8$ but these cases must alternate with cases $ρ 4.1$ , $ρ 4.3$ , $ρ 6.1$ , $ρ 6.3$ , $ρ 6.5$ , $ρ 6.7$ , respectively. Thus, if ρ were initialized infinitely often this alternation should also happen infinitely often, but then $outcome \neq fin$ – a contradiction. Thus, initializations can happen only finitely many times, and after stage $s_{0}$ , initializations via cases $ρ 4.2$ or $ρ 4.4$ can happen only finitely many times (for Part (A) we can bound them by $n + 1$ ). Also initializations via cases $ρ 6.2$ , $ρ 6.4$ , $ρ 6.6$ , $ρ 6.8$ can happen only finitely many times. Therefore, there is a stage $s_{1} > s_{1}^{'} > s_{0}$ , after which ρ is not initialized. Let x be the witness of ρ at stage $s_{1}$ .

Now we proceed to the satisfaction of $R_{| ρ |}$ . For a contradiction, assume that requirement $R_{| ρ |} = R_{Φ, Ψ, D}$ is not satisfied, i.e. $A \cup B \cup C = Φ^{D} \land D = Ψ^{A \cup B \cup C}$ . Then $Φ^{D} (x) = (A \cup B \cup C) (x)$ and $D ↾ φ^{D} (x) = Ψ^{A \cup B \cup C} ↾ φ^{D} (x)$ . For Part (B) assume also that D is $Δ_{ω + ω}$ , hence W is $Δ_{2}^{0}$ .

We claim that items $ρ 2$ and $ρ 3$ of the constructions will be achieved. Let τ be the least initial segment of D satisfying (with D replaced by τ) the conditions of the previous paragraph. We will show that ρ will be visited at some stage $s + 1 > s_{1}$ such that $s + 1 > | τ |$ and $(A \cup B \cup C) ↾ ψ (φ (x)) = (A \cup B \cup C) [s] ↾ ψ (φ (x))$ ; then $τ_{ρ}$ will be defined up to this stage.

Let $x_{1} < x_{2} < \dots < x_{n} < x < y_{1} < \dots < y_{k}$ (for some $n, k ⩾ 0$ ; if $n = 0$ or $k = 0$ then the list of corresponding witnesses is empty) be all witnesses of all requirements such that $y_{k} < ψ (φ (x))$ (note that the equation $ψ (φ (x)) = ψ^{A \cup B \cup C} (φ^{D} (x)) = ψ^{A \cup B \cup C} (φ^{τ} (x))$ uses the true values of A, B, C, D and does not depend on stages). Let, among these witnesses, the numbers $u_{1} < \dots < u_{m}$ , $m ⩾ 0$ be all canceled witnesses. Let $s_{2} > s_{1}$ be a stage such that $s_{2} > | τ |$ (hence, after the stage $s_{2}$ the string τ will be among those searched ones by the procedure of the case $ρ 2$ ) and for all $u_{i}$ and $t ⩾ s_{2}$ we have $(A \cup B \cup C) (u_{i}) [t] = (A \cup B \cup C) (u_{i})$ . In other words, these witnesses make no influence on the computations which the strategy ρ depends on, so without loss of generality we assume that all witnesses $x_{i}$ and $y_{j}$ are not initialized.

Now we show that witnesses $x_{i}$ also make no influence on computations of strategy ρ. Indeed, let $x_{i}$ be the witness of strategy $ξ_{i} \subset ρ$ . If $ξ_{i}^{⌢} fin \subseteq ρ$ then at stages $t + 1 > s_{2}$ related to ρ we have $(A \cup B \cup C) (x_{i}) [t] = (A \cup B \cup C) (x_{i})$ , because otherwise $ξ_{i}$ should initialize strategy ρ. If $ξ_{i}^{⌢} Σ \subseteq ρ$ then at any stage $t + 1 > s_{2}$ related to ρ we also visit $ξ_{i}$ , hence $A (x_{i}) [t] = (A \cup B \cup C) (x_{i}) [t] = (A \cup B \cup C) (x_{i}) = 0$ . In case $ξ_{i}^{⌢} Π \subseteq ρ$ the situation is similar: at any stage $t + 1 > s_{2}$ related to ρ we also visit $ξ_{i}$ , hence $B (x_{i}) [t] = (A \cup B \cup C) (x_{i}) [t] (A \cup B \cup C) (x_{i}) = 1$ . Thus, strategy ρ for its functionals at such stages $t + 1$ sees only true values of the approximations $(A \cup B \cup C) (x_{i})$ .

Now consider the witnesses $y_{i}$ . Without loss of generality we assume that witnesses $y_{i}$ belong to strategies on the true path below ρ and participate in infinite attacks. Indeed, fix a stage $s_{3} > s_{2}$ such that those $y_{j}$ , which attack finitely often, will not attack after $s_{3}$ . Let $y_{i}$ belong to strategy $η_{i}$ whose true outcome is either Σ or Π. Recall that $y_{k}$ is the greatest among such witnesses, hence strategy $η_{k}$ has the smallest priority. Let the node $η_{k}$ be visited at a stage $s_{3}^{'} + 1 > s_{3}$ . Then for all $y_{i}$ we have $(A \cup B \cup C) (y_{i}) [s_{3}^{'}] = (A \cup B \cup C) (y_{i})$ (if a strategy has the true outcome Σ or Π and has at some stage one of these outcomes then its witness has at this stage the true position in $A \cup B \cup C$ ). Consequently, at a stage $s_{4} + 1 > s_{3}^{'}$ the node $η_{k}$ (hence also ρ) is visited and we have $Φ^{τ} (x) [s_{4}] = 0$ and $Ψ^{A \cup B \cup C} | τ | [s_{4}] = τ$ , so the value $τ_{ρ} [s_{4}]$ is defined (note that for the true values $Φ^{D} (x)$ and $Ψ^{A \cup B \cup C} (φ (x))$ there is a stage on which both of them are defined). Also, it will clearly hold that $\forall z (τ (z) = 1 \to (\exists p ⩽ s_{4} z \in W [p]))$ . After this stage strategies with witnesses $y_{i}$ are initialized by the node ρ, and at stages when we visit ρ the oracle will depend only on x. After this stage the string $τ_{ρ}$ does not change.

The argument above also applies to the case $ρ 3$ , so the string $σ_{ρ}$ will also be defined and will not change after some stage $s_{5} > s_{4}$ .

Note that $τ_{ρ}$ and $σ_{ρ}$ are incomparable (otherwise, it would be $Φ^{τ_{ρ}} (x) = Φ^{σ_{ρ}} (x)$ which is false since we put x into $A \cup B \cup C$ after $τ_{ρ}$ is defined). Let $z_{0}$ be the least number with $τ_{ρ} (z_{0}) \neq σ_{ρ} (z_{0})$ . Since in cases $ρ 2$ and $ρ 3$ all strategies above ρ are initialized, we see that $Ψ^{A \cup B \cup C} (z_{0}) [t] = 1$ if and only if $(A \cup B \cup C) (x) [t] = 0$ (in case $τ_{ρ} (z_{0}) = 1$ ), or $Ψ^{A \cup B \cup C} (z_{0}) [t] = 0$ if and only if $(A \cup B \cup C) (x) [t] = 0$ (in case $τ_{ρ} (z_{0}) = 0$ ), where $t + 1 > s_{5}$ are stages at which ρ is visited. By Cooper’s strategy, if W is $Σ_{n + 1}^{- 1}$ (in Part (A)) or $Δ_{2}^{0}$ (in Part (B)) then either the case $ρ 4.5$ holds starting from some stage (since C is allowed to do one more change than W), or there is a stage $s_{5}^{'} > s_{5}$ such that at all later stages related to ρ the case $ρ 6$ holds.

It remains to consider all possible cases. Among the four cases ( $τ (z_{0}) = 1$ and $z_{0} \in Q_{0} [s_{1}]$ ; $τ (z_{0}) = 0$ and $z_{0} \in Q_{0} [s_{1}]$ ; $τ (z_{0}) = 1$ and $z_{0} \in Q_{1} [s_{1}]$ ; $τ (z_{0}) = 0$ and $z_{0} \in Q_{1} [s_{1}]$ ) we consider the first two; the proofs for the remaining ones are similar. Henceforth assume that $z_{0} \in Q_{0} [s_{1}]$ .

Let $z_{0} \in D$ . Since $Q_{0}$ is c.e. and $z_{0} \in Q_{0}$ we have $D (z_{0}) = U (z_{0})$ . Recall that U is $Σ_{2}^{0}$ , thus there is $s_{6} > s_{5}^{'}$ such that for each $s > s_{6}$ we have $z_{0} \in D [s]$ .

Let $x \in E_{1}$ which is equivalent to $τ_{ρ} (z_{0}) = 0$ . It suffices to consider B instead of $A \cup B \cup C$ .

Let $x \notin B$ . Since B is a $Π_{2}^{0}$ -set, starting from some stage $s_{7} > s_{6}$ we have $x \notin B [t]$ for all $t > s_{7}$ . After this stage the case $ρ 6.9$ holds, and the outcome is $fin$ . Then $Ψ^{A \cup B \cup C} (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{7} + 1] = τ_{ρ} (z_{0}) = 0 \neq 1 = D (z_{0})$ and the requirement $R_{| ρ |}$ is satisfied. A contradiction.

Let $x \in B$ . Then, by case $ρ 6.3$ , at some stages after $s_{6}$ the witness x will leave B (if it was there). Witness x will not enter B anymore because $ρ 6.4$ requires that after $s_{6}$ infinitely many zeros will appear as $D (z_{0}) [s]$ , henceforth the case $ρ 6.9$ and outcome $fin$ will hold. Thus, $x \notin B [t]$ for all t larger than some $s_{7} > s_{6}$ which contradicts to $x \in B$ .

Let $x \in E_{0}$ which is equivalent to $τ_{ρ} (z_{0}) = 1$ . It suffices to consider A instead of $A \cup B \cup C$ .

Let $x \notin A$ . By item $ρ 6.1$ , at some stages larger than $s_{6}$ , x will be in A. Moreover, x cannot leave A because it may happen only in case $ρ 6.2$ which requires that after $s_{6}$ the value of $D (z_{0}) [s]$ is equal to zero infinitely often, hence at such stages the case $ρ 6.9$ and outcome $fin$ hold. Thus, $x \in A [t]$ for all t larger than some stage $s_{7} > s_{6}$ , contradicting to $x \notin A$ .

Let $x \in A$ . Since A is $Σ_{2}^{0}$ , starting at some stage $s_{7} > s_{6}$ we have $x \in A [t]$ for all $t > s_{7}$ . Henceforth, the strategy will have case $ρ 6.9$ and outcome $fin$ . Hence, $Ψ^{A \cup B \cup C} (z_{0}) = Ψ^{A \cup B \cup C} (z_{0}) [s_{7} + 1] = σ_{ρ} (z_{0}) = 0 \neq 1 = D (z_{0})$ and requirement $R_{| ρ |}$ is satisfied. A contradiction.

Let $z_{0} \notin D$ . Then for any $t > s_{5}$ there is $s > t$ such that $z_{0} \notin D [s]$ (recall that $D (z_{0}) = U (z_{0})$ and U is $Σ_{2}^{0}$ ).

Let $x \in E_{1}$ which is equivalent to $τ_{ρ} (z_{0}) = 0$ . It suffices to consider B instead of $A \cup B \cup C$ .

Let $x \notin B$ . By the definition of Π-approximations, there is $s_{6} > s_{5}$ such that $x \notin B [t]$ for all $t > s_{6}$ . Moreover, there is a stage $s_{7} > s_{6}$ such that the conditions of item $ρ 6.4$ hold, so x should be put into B. Thus, $x \in B [s_{7} + 1]$ , contradicting the choice of $s_{6}$ .

Let $x \in B$ . Then $Ψ^{A \cup B \cup C} (z_{0}) = σ_{ρ} (z_{0}) = 1 \neq 0 = D (z_{0})$ , and requirement $R_{| ρ |}$ is satisfied. A contradiction.

Let $x \in E_{0}$ which is equivalent to $τ_{ρ} (z_{0}) = 1$ . It suffices to consider A instead of $A \cup B \cup C$ .

Let $x \notin A$ . Then $Ψ^{A \cup B \cup C} (z_{0}) = τ_{ρ} (z_{0}) = 1 \neq 0 = D (z_{0})$ and the requirement $R_{| ρ |}$ is satisfied. A contradiction.

Let $x \in A$ . Since A is $Σ_{2}^{0}$ , there is $s_{6} > s_{5}$ such that $x \in A [t]$ for all $t > s_{6}$ . Moreover, there is a stage $s_{7} > s_{6}$ for which the conditions of item $ρ 6.2$ hold, so x should be removed from A. Thus, $x \notin A [s_{7} + 1]$ contradicting the choice of stage $s_{6}$ .

This completes the proof of the theorem.

Footnotes

Acknowledgements

The first author is grateful to M.M. Arslanov for the invitation and useful discussions. The work was performed during a visit of the first author to Kazan Federal University according to the Russian Government Program of Competitive Growth of Kazan Federal University.

The second author was partially supported by RFBR (research project No. 18-01-00574) and by the research grant of Kazan Federal University. The work was supported by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activity (No. 1.1515.2017/4.6).

References

S.B.

Cooper, Degrees of unsolvability, PhD thesis, Leicester University, Leicester, England, 1971.

Y.L.

Ershov, On a hierarchy of sets, Algebra i Logika7(1) (1968), 47–74(Russian); English translation: Algebra and Logic7 (1968), 23–41.

Y.L.

Ershov, On a hierarchy of sets II, Algebra i Logika7(4) (1968), 15–47(Russian); English translation: Algebra and Logic7 (1968), 212–232.

Y.L.

Ershov, On a hierarchy of sets III, Algebra i Logika9(1) (1970), 34–51(Russian); English translation: Algebra and Logic9 (1970), 20–31. doi:10.1007/BF02219847.

C.G.

Josckush and

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

Kihara and

Montalban, The uniform Martin’s conjecture for many-one degrees, arXiv:1608.05065v1 (17 Aug 2016).

V.L.

Selivanov, Hierarchies of hyperarithmetical sets and functions, Algebra i Logika22(6) (1983), 666–692, (Russian); English translation: Algebra and Logic22 (1983), 473–491.

V.L.

Selivanov, On the Ershov hierarchy, Sibirskii Matematicheskii Zhurnal26 (1985), 134–149(Russian); English translation: Siberian Mathematical Journal26 (1985), 105–116.

V.L.

Selivanov, Fine hierarchies of arithmetical sets and definable index sets, Trudy Instituta Matematiki SO AN SSSR12 (1989), 165–185(Russian); since 2007 journal has English translation Siberian Advances in Mathematics.

10.

V.L.

Selivanov, Fine hierarchies and Boolean terms, Journal of Symbolic Logic60 (1995), 289–317. doi:10.2307/2275522.

11.

V.L.

Selivanov and

M.M.

Yamaleev, On Turing degrees in refinements of the arithmetical hierarchy, Algebra and Logic, accepted.

12.

Soare, Recursively Enumerable Sets and Degrees, Springer, Berlin, 1987.

Extending Cooper’s theorem to Δ 3 0 Turing degrees

Abstract

Keywords

1. Introduction

Question 1. Is it true that for each infinite ordinal α ∈ ε 0 ∖ { λ + 1 ∣ λ is limit } the level Σ α is proper? 2. Notation and intuition

4. Verification

Footnotes

Acknowledgements

References

Question 1.
Is it true that for each infinite ordinal $α \in ε_{0} ∖ {λ + 1 ∣ λ is limit}$ the level $Σ_{α}$ is proper?

2. Notation and intuition