On Kalimullin pairs

Abstract

We study Kalimullin pairs, a definable class (of pairs) of enumeration degrees that has been used to give first-order definitions of other important classes and relations, including the enumeration jump and the total enumeration degrees. We show that the global definition of Kalimullin pairs is also valid in the local structure of the enumeration degrees, giving a simpler local definition than was previously known. We prove that the typical enumeration degree is not half of a nontrivial Kalimullin pair, both in the sense of category and measure. Using genericity, we show that not all members of nontrivial Kalimullin pairs are half of a maximal Kalimullin pair. Finally, we construct such a set that has no maximal Kalimullin partner, making it qualitatively different from half of a maximal Kalimullin pair.

Keywords

Enumeration reducibility Kalimullin pairs genericity

1. Introduction

One focus of classical computability theory is the investigation of degree structures. These structures arise from reducibilities on the power set $P (ω)$ of the natural numbers: we say that a set A is “reducible” to a set B if there is a way to “compute” membership in A from membership information about B. There are several natural formalizations of this idea, giving different reducibilities. Such a reducibility is always reflexive and transitive and thus induces a preorder on $P (ω)$ . The equivalence classes of sets reducible to each other are usually called “degrees”, and the preorder on the sets induces a partial order on the degrees. Almost always, a degree structure will also be an upper semilattice.

The most commonly studied reducibility is Turing reducibility: a set A is Turing reducible to a set B if there is an algorithm that, on any input x, determines whether $x \in A$ in finitely many steps and making finitely many membership queries to B. A closely related notion is enumeration reducibility: a set A is enumeration reducible to a set B if there is an algorithm to enumerate all elements of A from any enumeration of the elements of B. In a sense, while Turing reducibility uses and produces both positive and negative information about sets, enumeration reducibility uses and produces only positive membership information. Enumeration reducibility, like Turing reducibility, arises naturally in questions from computable algebra and computable model theory. In this paper, however, we are studying the enumeration degrees as an algebraic structure of independent intrinsic interest.

When investigating the properties of a degree structure, a central question is: which degree-invariant relations definable in second-order arithmetic remain first-order definable in the degree structure? For example, consider the structure of the Turing degrees, $D_{T}$ , induced by Turing reducibility. The jump operator, which relates a set of natural numbers to its halting set, is an example of a degree-invariant function. It is a theorem of Shore and Slaman [13] that the jump operator is first-order definable in the Turing degrees. This first-order definition relies on the analysis of Slaman and Woodin of the automorphism group of the Turing degrees [14] and goes through an interpretation of a model of second-order arithmetic in the Turing degrees.

The structure of the enumeration degrees, $D_{e}$ , is induced by enumeration reducibility. There is a natural embedding of the Turing degrees into the enumeration degrees. The enumeration degrees in the range of this embedding are called total. Enumeration reducibility comes with its own notion of a jump operator, which agrees with the Turing jump operator under the embedding. Kalimullin [10] gave a first-order definition of the jump in the enumeration degrees. His definition is more elementary than the definition of the Turing jump given by Slaman and Woodin; it relies on the existence and definability of a class of pairs of enumeration degrees, which came to be known as Kalimullin pairs. Kalimullin pairs, or $K$ -pairs, turn out to play a central role in definability results in the enumeration degrees. Ganchev and Soskova [5] showed that Kalimullin pairs are also first-order definable in the local structure of the enumeration degrees, $D_{e} (⩽ 0^{'})$ , the substructure of the enumeration degrees bounded by the first enumeration jump of the least degree. They applied this fact in [7] to show that various other classes of degrees are first-order definable in $D_{e} (⩽ 0^{'})$ , including the low enumeration degrees and the total enumeration degrees in $D_{e} (⩽ 0^{'})$ . Building on this work, Cai, Ganchev, Lempp, Miller and Soskova [2] show that the class of total enumeration degrees is definable in $D_{e}$ .

In this article, we examine properties of $K$ -pairs and settle some questions raised through the investigations described above. The original local definition of $K$ -pairs [5] uses Kalimullin’s global definition in combination with a structural property of $D_{e} (⩽ 0^{'})$ which relates to cupping and whose proof is inspired by Harrington’s non-splitting theorem [8]. In Section 3, we show that Kalimullin’s first-order definition is sufficient for the definition of $K$ -pairs in the local structure, thereby lowering the complexity and simplifying the proof of the local definability of $K$ -pairs.

Semi-computable sets were introduced by Jockusch [9] as initial segments of computable linear orders. Their properties in the context of enumeration reducibility were first examined by Arslanov, Cooper and Kalimullin [1]. A semi-computable set and its complement form a $K$ -pair of a particular kind, a maximal $K$ -pair. The proof of the definability of the total enumeration degrees in $D_{e}$ is based on maximal $K$ -pairs. It is shown that, up to enumeration equivalence, every maximal $K$ -pair is of the form ${A, \overline{A}}$ for some semi-computable set A. In Section 4, we produce a nontrivial $K$ -pair such that neither half is enumeration equivalent to a semi-computable set, hence neither half is a member of a maximal $K$ -pair. We do this by building a $K$ -pair consisting of two 1-generic sets and proving that a 1-generic set cannot have the same degree as a semi-computable set. We further investigate the relationship between genericity and $K$ -pairs, showing that if a set is sufficiently generic, it cannot even be part of a nontrivial $K$ -pair. In other words, the collection of sets that are half of a nontrivial $K$ -pair is meager. We finish the section by showing that this collection also has measure zero: no 1-random is half of a nontrivial $K$ -pair.

In Section 5, we distinguish general $K$ -pairs from maximal $K$ -pairs in another way. If a is one member of a $K$ -pair, the set of enumeration degrees that forms a $K$ -pair with a is an ideal. For members of a maximal $K$ -pair, this ideal is principal. It is natural to ask whether this is true for every half of a nontrivial $K$ -pair. We give a negative answer by directly constructing a counterexample.

2. Preliminaries

2.1. Enumeration reducibility

We start with basic definitions and properties of enumeration reducibility and of the enumeration degrees.

Definition 2.1.
A set A is enumeration reducible to a set B (denoted by $A ⩽_{e} 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 canonical index u under the standard coding of finite sets.

We will refer to the c.e. set Φ in the definition above as an enumeration operator. An element $⟨ n, u ⟩ \in Φ$ will be called an axiom for n in Φ. We will often identify finite sets with their canonical indices and write $⟨ n, D_{u} ⟩$ for $⟨ n, u ⟩$ .

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

The enumeration jump of a set A was defined by Cooper [3].
Definition 2.2.
The enumeration jump of a set A is denoted by $J_{e} (A)$ and is defined as $K_{A} \oplus \overline{K_{A}}$ , where $K_{A} = {⟨ e, x ⟩ : x \in Φ_{e} (A)}$ . Here, ${Φ_{e}}_{e < ω}$ is the standard listing of the enumeration operators. The enumeration jump of $d_{e} (A)$ is $d_{e} {(A)}^{'} = d_{e} (J_{e} (A))$ .
Definition 2.3.
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.

It is not difficult to see that a set A is Turing equivalent to a set B if and only if $A \oplus \overline{A}$ is enumeration equivalent to $B \oplus \overline{B}$ . Thus, the map ι, defined by $\begin{matrix} ι (d_{T} (A)) = d_{e} (A \oplus \overline{A}), \end{matrix}$ is an embedding of $D_{T}$ into $D_{e}$ that preserves the order, the least element, and the least upper bound. McEvoy [12] showed that it also preserves the jump operation.

The local structure of the enumeration degrees, denoted by $D_{e} (⩽ 0^{'})$ , is the substructure of all enumeration degrees that are below $0_{e}^{'}$ . The elements of $D_{e} (⩽ 0^{'})$ are the enumeration degrees that contain $Σ_{2}^{0}$ -sets, or equivalently, that consist entirely of $Σ_{2}^{0}$ -sets. Jockusch [9] showed that to every $Σ_{2}^{0}$ -set A, we can associate a uniformly computable sequence of finite sets ${A [s]}_{s < ω}$ , called a good $Σ_{2}^{0}$ -approximation to A, such that
there are infinitely many stages s at which $A [s] \subseteq A$ (we call these good stages), and

$n \in A$ if and only if $n \in A [s]$ at all but finitely many stages s.
We refer to Cooper [4] for a survey of basic results on the structure of the enumeration degrees and to Sorbi [15] for a survey of basic results on the local structure $D_{e} (⩽ 0^{'})$ .
2.2. Kalimullin pairs

The central topic of this paper is Kalimullin pairs; these were introduced by Kalimullin [10] to give a definition of the jump in the enumeration degrees.

Definition 2.4 (Kalimullin [10]).

We call $A, B \subseteq ω$ a Kalimullin pair (or $K$ -pair) if there is a c.e. set $W \subseteq ω \times ω$ such that $A \times B \subseteq W$ and $\overline{A} \times \overline{B} \subseteq \overline{W}$ .

Ganchev and Soskova [5] gave Kalimullin pairs their current name; Kalimullin [10] originally called them e-ideal pairs because of the following property.

Proposition 2.5.
For any set of natural numbers A, the collection of all sets B that form a $K$ -pair with A is downwards closed under enumeration reducibility and closed under the join operation, i.e., it is an ideal in the enumeration degrees.

If A is a c.e. set, then the ideal of its $K$ -partners contains every set of natural numbers. $K$ -pairs with a c.e. member are called trivial and will be of no interest to us. Nontrivial $K$ -pairs have nontrivial properties, as can be seen below.
Proposition 2.6 (Kalimullin [10, Proposition 2.7]).

If A and B form a nontrivial $K$ -pair, then:

$A ⩽_{e} \overline{B}$ and $B ⩽_{e} \overline{A}$ ,

$\overline{A} ⩽_{e} B \oplus J_{e} (\emptyset)$ and $\overline{B} ⩽_{e} A \oplus J_{e} (\emptyset)$ .

Remark 2.1.
The reduction in part (1) of Proposition 2.6 can easily be made explicit. Assume that A and B form a $K$ -pair witnessed by W, and A is not c.e. Then $B = {b : (\exists a) ⟨ a, b ⟩ \in W and a \in \overline{A}}$ . This works even if B is c.e.

It follows from Proposition 2.5 that being a $K$ -pair is a degree-theoretic property: Let us call a pair of enumeration degrees a and b a $K$ -pair if the members of a form $K$ -pairs with the members of b. Kalimullin [10] showed that this is a definable property: $K$ -pairs are minimal pairs relative to every other enumeration degree. Theorem 2.7 (Kalimullin [10, Theorem 2.6]).

A pair of enumeration degree a and b form a $K$ -pair if and only if for every enumeration degree x , $\begin{matrix} (a \lor x) \land (b \lor x) = x . \end{matrix}$

2.3. Semi-computable sets

Semi-computable sets give rise to $K$ -pairs, in fact, to maximal $K$ -pairs, which are central to the definability of the total enumeration degrees.

Definition 2.8 (Jockusch [9]).

A set A is called semi-computable if there is a computable function (called a selector function) $f : ω \times ω \to ω$ such that for any $x, y \in ω$ , $f (x, y) \in {x, y}$ , and if ${x, y} \cap A \neq \emptyset$ then $f (x, y) \in A$ .

Equivalently, A is semi-computable if and only if there is a computable linear ordering on ω such that A is a cut in this linear ordering. We give a particular example of this.

Let $σ <_{L} τ$ denote that σ is lexicographically to the left of τ. Define $σ ⩽ τ$ to mean that $σ ⪯ τ$ or $σ <_{L} τ$ . Note that ⩽ is a computable linear ordering on $2^{< ω}$ . For $A \subseteq ω$ , we write $σ ⩽ A$ to mean that $σ ⩽ A ↾ | σ |$ . Let $L_{A} = {σ : σ ⩽ A}$ . The set $L_{A}$ is an initial segment of $⟨ 2^{< ω}, ⩽ ⟩$ , hence it is semi-computable. As $A \equiv_{T} L_{A}$ , it follows that every Turing degree contains a semi-computable set. Jockusch [9] extended this to show that every Turing degree contains a semi-computable set that is neither c.e. nor co-c.e. In $D_{e}$ , sets of the form $L_{A}$ characterize the enumeration degrees of semi-computable sets:

Proposition 2.9 (Ganchev and Soskova [7]).

If $A \subseteq ω$ is semi-computable, then $A \equiv_{e} L_{A}$ .

If $A \subseteq ω$ is semi-computable, then A and $\overline{A}$ form a $K$ -pair. Thus nontrivial semi-computable sets provide us with examples of nontrivial $K$ -pairs. Taking Proposition 2.6 into account, we see that a semi-computable set and its complement have the following maximality property.

Definition 2.10 (Ganchev and Soskova [7]).

A $K$ -pair of enumeration degrees ${a, b}$ is a maximal $K$ -pair if for every $K$ -pair of enumeration degrees ${c, d}$ , such that $a ⩽ c$ and $b ⩽ d$ , we have that $a = c$ and $b = d$ .

Cai, Ganchev, Lempp, Miller and Soskova [2] show that every maximal $K$ -pair is of the form ${d_{e} (A), d_{e} (\overline{A})}$ for some semi-computable set A. Thus the nonzero total enumeration degrees can be defined as the least upper bounds of maximal $K$ -pairs.

2.4. $K$ -pairs in $D_{e}$ ( $⩽ 0^{'}$ )

$K$ -pairs in the local structure of the enumeration degrees have particularly nice properties. It is immediate from Proposition 2.6 that if ${a, b}$ is a nontrivial $K$ -pair in $D_{e} (⩽ 0^{'})$ , then a and b are $Δ_{2}^{0}$ -enumeration degrees and, in fact, even low enumeration degrees, i.e., $a^{'} = b^{'} = 0_{e}^{'}$ .

The main tool for constructing $K$ -pairs in $D_{e} (⩽ 0^{'})$ is given by the following dynamic characterization:

Lemma 2.11 (Kalimullin [10, Theorem 4.1]).

For $Σ_{2}^{0}$ -sets A and B, the following are equivalent:

A and B form a $K$ -pair.

There are $Σ_{2}^{0}$ -approximations ${A [s]}_{s < ω}$ and ${B [s]}_{s < ω}$ such that $\begin{matrix} (\forall s) [A [s] \subseteq A \lor B [s] \subseteq B] . \end{matrix}$

Since Kalimullin states and proves this only for $Δ_{2}^{0}$ -sets, we include a full proof here:

Proof of Lemma 2.11.
For the forward direction, we may assume that neither A nor B is c.e., or else the result is trivial by using a $Σ_{1}^{0}$ -approximation to A or B, making a fixed disjunct of (2) above always true. So suppose that A and B form a nontrivial $K$ -pair via W. Fix a good $Σ_{2}^{0}$ -approximation ${\hat{A} [s] \oplus \hat{B} [s]}_{s < ω}$ to $A \oplus B$ . We assume furthermore that $\hat{A} [0] = \hat{B} [0] = \emptyset$ . Fix a $Σ_{1}^{0}$ -approximation ${W [s]}_{s < ω}$ to W. From the given approximations to A and B, we construct the desired $Σ_{2}^{0}$ -approximations ${A [s]}_{s < ω}$ and ${B [s]}_{s < ω}$ as follows:

Set $A [0] = \hat{A} [0]$ and $B [0] = \hat{B} [0]$ . Suppose that we have defined $A [s] = \hat{A} [i_{s}]$ and $B [s] = \hat{B} [j_{s}]$ . At stage $s + 1$ , find the greatest pair $⟨ i, j ⟩ ⩽ s$ such that either $i_{s} = i$ and $j_{s} = j$ , or $i_{s} < i$ , $j_{s} < j$ and $\hat{A} [i] \times \hat{B} [j] \subseteq W [s]$ . Let $i_{s + 1} = i$ , $j_{s + 1} = j$ , and set $A [s + 1] = \hat{A} [i_{s + 1}]$ and $B [s + 1] = \hat{B} [j_{s + 1}]$ .

To see that ${A [s]}_{s < ω}$ and ${B [s]}_{s < ω}$ satisfy (2), we argue as follows. For every s, $A [s] \times B [s] \subseteq W [s] \subseteq W$ . As $\overline{A} \times \overline{B} \subseteq \overline{W}$ , it follows that $A [s] \subseteq A$ or $B [s] \subseteq B$ .

We next verify that ${i_{s}}_{s < ω}$ and ${j_{s}}_{s < ω}$ are unbounded; note that by our construction, we only need to show this for the sequence ${i_{s}}_{s < ω}$ . So fix n arbitrary, and fix a good stage $i > n$ for $A \oplus B$ . Then $\hat{A} [i] \times \hat{B} [i] \subseteq A \times B \subseteq W$ , hence there is a sufficiently large stage $s^{}$ such that $\hat{A} [i] \times \hat{B} [i] \subseteq W_{s^{}}$ and so $i_{s^{}} ⩾ i > n$ .

We conclude from this that ${A [s] \oplus B [s]}_{s < ω}$ is a $Σ_{2}^{0}$ -approximation to $A \oplus B$ as follows: Suppose that $x \in A [s] ∖ A$ for cofinitely many s. Then, since $A [s] \subseteq A$ or $B [s] \subseteq B$ for all s, we have $B [s] \subseteq B$ for cofinitely many s, making B c.e. contrary to our hypothesis.

For the opposite direction, fix $Σ_{2}^{0}$ -approximations ${A [s]}_{s < ω}$ to A and ${B [s]}_{s < ω}$ to B such that $\begin{matrix} (\forall s) [A [s] \subseteq A \lor B [s] \subseteq B] . \end{matrix}$ Then A and B form a $K$ -pair witnessed by the c.e. set $W = ⋃_{s < ω} A [s] \times B [s]$ . □

Kalimullin [10] showed that $0_{e}^{'}$ is the largest enumeration degree that can be represented as the least upper bound of a $K$ -triple. A $K$ -triple* is an instance of a $K$ -system, a set of enumeration degrees such that every pair of distinct elements is a nontrivial $K$ -pair. Thus $K$ -systems not below $0_{e}^{'}$ have cardinality at most 2. In contrast, Ganchev and Soskova [6] showed that below every nonzero $Δ_{2}^{0}$ -enumeration degree one can find an infinite countable $K$ -system. $K$ -systems can then be used to code relations into the local structure, as in [6], or to characterize various other classes of enumeration degrees, as in [5]. Of course, all of these results rely essentially on the fact that $K$ -pairs form a definable class in the local structure of the enumeration degrees.
3. A local definition of $K$ -pairs

The first-order definition of $K$ -pairs in the global structure $D_{e}$ is given by a universal formula: $\begin{matrix} φ_{K} (a, b) ⟷ (\forall x) (a \lor x) \land (b \lor x) = x . \end{matrix}$ This allows for the possibility of the existence of fake $K$ -pairs in the local structure, i.e., pairs of sets U and V whose degrees u and v satisfy the formula $φ_{K}$ in the local structure, but do not satisfy it globally. Ganchev and Soskova [5] circumvent this problem by using a more restrictive formula $φ_{LK} = φ_{K} & ψ$ , where ψ contains additional structural requirements. The additional formula ψ raises the complexity of this first-order definition by one quantifier level. We now show that fake $K$ -pairs do not exist in the local structure, and therefore this additional restriction in the local definition of $K$ -pairs is not necessary.

Theorem 3.1.
A pair of $Σ_{2}^{0}$ -sets A and B form a $K$ -pair if and only if for every $x ⩽ 0_{e}^{'}$ , $\begin{matrix} (d_{e} (A) \lor x) \land (d_{e} (B) \lor x) = x . \end{matrix}$
Proof.
Immediate from Theorem 2.7 above and Theorem 3.2 below. □
Theorem 3.2.
If U and V are $Σ_{2}^{0}$ -sets that do not form a $K$ -pair, then there are $Σ_{2}^{0}$ -sets A and Y such that $Y ⩽_{e} A \oplus U$ and $Y ⩽_{e} A \oplus V$ , but $Y ≰_{e} A$ .
Proof.
Let U and V be $Σ_{2}^{0}$ -sets that do not form a $K$ -pair. We will construct a $Σ_{2}^{0}$ -set A and two enumeration operators Γ and Λ so that the following two types of requirements are satisfied:
The global requirement $\begin{matrix} R : Γ (U \oplus A) = Λ (V \oplus A) . \end{matrix}$

For every natural number e, we will have a requirement $\begin{matrix} N_{e} : Φ_{e} (A) \neq Γ (U \oplus A) . \end{matrix}$

The construction will make use of a tree of strategies T. The nodes on the tree are all strings of symbols in the set $O = ω \cup {w}$ , called the set of outcomes. A node α on the tree of length e will be assigned the requirement $N_{e}$ . The outcomes are ordered as follows: $\begin{matrix} 0 < 1 < \dots < n < n + 1 < \dots < w . \end{matrix}$

Fix a good $Σ_{2}^{0}$ -approximation ${U [s] \oplus V [s]}_{s < ω}$ to $U \oplus V$ . The construction will run in stages. At every stage s, we construct approximations to the sets A, Γ and Λ and a finite path $δ [s]$ of length s in the tree of strategies T. Nodes $α ⪯ δ [s]$ will be called activated or visited at stage s, and s will be called an α-true stage. Nodes along $δ [s]$ will be allowed to perform actions following a specific strategy aimed at satisfying their assigned requirement. This is why we will often refer to the nodes in the tree T as strategies. Nodes to the right of $δ [s]$ will be injured at stage s. The intention is that there will be an infinite path of nodes visited at infinitely many stages and injured only finitely many times, called the true path, along which all strategies succeed in satisfying their requirement. In particular, if $w$ is the leftmost outcome visited at infinitely many stages for some strategy α along the true path, then the construction will guarantee that α has outcome $w$ at all but finitely many true stages.

An important technical detail in our proof is the way we construct the set A. We will build a uniformly computable sequence of cofinite sets ${A [s]}_{s < ω}$ that will serve as a $Σ_{2}^{0}$ approximation to A. At the beginning of each stage s, we set $A_{0} [s] = ω$ . Then, during stage s, every proper initial segment of $δ [s]$ of length $n ⩽ s$ is activated and constructs $A_{n + 1} [s]$ by extracting numbers from $A_{n} [s]$ . $A [s] = A_{s} [s]$ will be the resulting set after all strategies have made their extractions. Ultimately, an element x is in A if and only if $x \in A [s]$ at all but finitely many stages. In other words, the only natural numbers x that do not belong to the set A are the ones that get extracted by strategies at infinitely many stages s.

Description of the strategies.

At the beginning of every stage s, we first activate the global $R$ -strategy. The global $R$ -strategy constructs the operators Γ and Λ. Every element x that enters $Γ (U \oplus A)$ or $Λ (V \oplus A)$ at any stage will be the responsibility of one particular $N$ -strategy, say α. If the strategy α decides to use this element, then it will define for it a U-marker $u (x)$ , a V-marker $v (x)$ , and an A-marker $a (x)$ . Initially, all the markers are positive numbers. The strategy α can change them once to $u (x) = 0$ , $v (x) = 0$ , and $a (x)$ to a larger number. At stage s, the $R$ -strategy enumerates axioms for all elements x that have defined markers. The axioms enumerated into the operators Γ and Λ at stage s for x will be $\begin{matrix} ⟨ x, (U [s] ↾ u (x)) \oplus {a (x)} ⟩ and ⟨ x, (V [s] ↾ v (x)) \oplus {a (x)} ⟩ . \end{matrix}$ If $a (x) \in A$ then, as we have a good $Σ_{2}^{0}$ -approximation to $U \oplus V$ , eventually we will enumerate a valid axiom for x into both operators.

After activating the global strategy we start the construction of $δ [s]$ . This finite path is defined inductively – we always start by activating the root of the tree ∅. When a strategy $α = δ [s] ↾ n$ is activated, it performs certain actions as described below and selects an outcome $o$ . If $n = s$ , then the construction of $δ [s] = δ [s] ↾ n$ is complete and the construction proceeds to stage $s + 1$ . Otherwise, $δ [s] ↾ n + 1 = (δ [s] ↾ n) \hat{} o$ .

Every $N$ -strategy α will be equipped with an infinite computable list of witnesses $X_{α} = {x_{0} < x_{1} < \dots}$ so that if $α \neq β$ then $X_{α} \cap X_{β} = \emptyset$ . These witnesses will be used by α in its attempts to diagonalize $Γ (U \oplus A)$ against $Φ_{| α |} (A)$ . Every witness has one of three possible statuses: unused, used and canceled. Consider the first stage $s_{0}$ that the strategy α is visited (after being initialized). At this stage, α will select as its current witness $x_{α}$ the least unused witness $x \in X_{α}$ and declare it used. It will define its markers $u (x_{α})$ , $v (x_{α})$ and $a (x_{α})$ as fresh numbers not seen in the construction so far. This will mean that from the next stage onward the global strategy will be enumerating axioms for $x_{α}$ . Note that $a (x_{α})$ is selected as a fresh number and will remain in the set A as long as no strategy extracts it. The strategy α will wait until $x_{α}$ appears in $Φ_{| α |} (A)$ , and while this is not true, it will have outcome $w$ . If this never happens, then the strategy is successful, as $x_{α} \in Γ (U \oplus A) ∖ Φ_{| α |} (A)$ . If at a stage s an axiom for $x_{α}$ appears in $Φ_{| α |}$ , then the strategy α would like to keep $x_{α} \in Φ_{| α |} (A)$ at all further stages while at the same time extracting it from the set $Γ (U \oplus A)$ . Unfortunately, this is not immediately possible, as extracting the marker $a (x_{α})$ might injure $x_{α} \in Φ_{| α |} (A)$ . In order to resolve this conflict, the strategy will keep $a (x_{α}) \in A$ and try to obtain evidence that $x_{α}$ is not in either $Γ (U \oplus A)$ or $Λ (V \oplus A)$ based on memberships in U and V. The strategy will initiate the construction of a pair of approximations ${U_{n}}_{n < ω}$ and ${V_{n}}_{n < ω}$ , setting the first members of these approximations to $U_{0} = ⋂_{s_{0} ⩽ t ⩽ s} U [t] ↾ u (x_{α})$ and $V_{0} = ⋂_{s_{0} ⩽ t ⩽ s} V [t] ↾ v (x_{α})$ .

If $U_{0} ⊈ U$ and $V_{0} ⊈ V$ , then all axioms for $x_{α}$ enumerated into Γ and Λ until this stage are invalid. It is however possible that only one of these approximations is wrong, making $Γ (U \oplus A)$ and $Λ (V \oplus A)$ differ at $x_{α}$ . To prevent this at the current stage, the strategy sets $u (x_{α}) = v (x_{α}) = 0$ and defines a new fresh value for the marker $a (x_{α})$ , larger than any number used in an axiom in the current approximation to $Φ_{| α |}$ . At all further stages, if it appears that both $U_{0} ⊈ U$ and $V_{0} ⊈ V$ , i.e., the strategy has observed two new stages $s_{1}$ and $s_{2}$ at which $U_{0} ⊈ U [s_{1}]$ and $V_{0} ⊈ V [s_{2}]$ , then α will extract the newly defined $a (x_{α})$ from A, invalidating all axioms for $x_{α}$ and have outcome $0$ . Meanwhile, it will initiate a new cycle with a new witness, the next unused element of $X_{α}$ .

To keep track of cycles the strategy α will have a parameter $C_{α}$ , which lists necessary information about all previous cycles. The nth entry in $C_{α}$ will be $C_{α} [n] = ⟨ x_{n}, a_{n}, U_{n}, V_{n}, o_{n} ⟩$ , where $x_{n}$ is the witness from α’s nth cycle, $a_{n}$ is the value of its first A-marker, $U_{n}$ and $V_{n}$ are the nth members of the approximations to U and V constructed by α, and $o_{n}$ is the previous stage when α had outcome $n$ .

If the strategy α performs finitely many cycles, it must come across a witness x, guaranteeing that $Γ (U \oplus A) \neq Φ_{| α |} (A)$ . If α completes infinitely many cycles, it defines a pair of $Σ_{2}^{0}$ -approximations ${U_{n}}_{n < ω}$ and ${V_{n}}_{n < ω}$ to the sets U and V. As U and V do not form a $K$ -pair, we have by Lemma 2.11 that there must be some least n such that $U_{n} ⊈ U$ and $V_{n} ⊈ V$ . Then the nth cycle will ultimately be successful and $n$ will be the true outcome of α.

Conflicts between a pair of $N$ -strategies.

Suppose that α and β are two strategies on the true path and $α \hat{} n ⪯ β$ , where $n \in ω$ . The strategy β would like to ensure that some finite set D is a subset of A. However, there is the possibility that the higher-priority strategy α prevents this from happening. If at infinitely many stages, α has outcome $m > n$ and the witness $x_{m}$ has marker $a (m)$ which is in the set D, then ultimately $D ⊈ A$ and so β is not successful.

In order to prevent this, every time α has outcome $n$ , it will extract all markers that could possibly be extracted by α during any larger cycle as well, namely the markers $a (x_{m})$ for every $m ⩾ n$ . Extracting only the current marker of a previous witness can lead to an inconsistency between the two constructed operators Γ and Λ. For this reason, α will also extract the initial values of the a-markers $a_{m}$ for $m > n$ , recorded in $C_{α}$ . The way we have set up the approximation to A ensures that this will not injure the activity of α itself. Recall, that at every stage s the set $A [s]$ is the set of all natural numbers minus the elements extracted at stage s. If $n$ is not the true outcome but some $m > n$ is, then $α \hat{} n$ will be visited only finitely many times and the extractions involved will not affect A.

We summarize the fate of the markers $a_{n}$ and $a (x_{n})$ after they are defined by α: If cycle $m < n$ is active, we extract both $a_{n}$ and $a (x_{n})$ from A, causing $x_{n}$ to leave both $Γ (U \oplus A)$ and $Λ (V \oplus A)$ . If cycle n is active, we extract only $a (x_{n})$ from A, causing $x_{n}$ to leave both $Γ (U \oplus A)$ and $Λ (V \oplus A)$ , but letting it remain in $Φ_{| α |} (A)$ . If cycle $m > n$ is active, we leave both $a_{n}$ and $a (x_{n})$ in A, causing $x_{n}$ to remain in both $Γ (U \oplus A)$ and $Λ (V \oplus A)$ .

Finally, with this modification in mind, we note that α will extract more and more numbers every time that it has outcome $n$ . We will ensure that every time α defines a new value for a marker, the value will be larger than the current stage. The lower-priority strategy β can safely assume that no more elements $x < s$ (where s is the current stage) will be extracted by α on further visits, except for the ones currently extracted by α.

Construction.

At stage 0, all strategies and all parameters are in their initial state: set parameters are empty, number parameters are undefined.

At stage $s > 0$ , all parameters inherit their value from the previous stage. We first activate the global $R$ -strategy.

The global $R$ -strategy.

For all $x < s$ such that $a (x)$ , $u (x)$ and $v (x)$ are defined, enumerate into the operator Γ the axiom $⟨ x, (U [s] ↾ u (x)) \oplus {a (x)} ⟩$ and into the operator Λ the axiom $⟨ x, (V [s] ↾ v (x)) \oplus {a (x)} ⟩$ .

Then we start the construction of $δ [s]$ . Set $δ [s] ↾ 0 = \emptyset$ and $A_{0} [s] = ω$ . Suppose that we have constructed $δ [s] ↾ k$ and $A_{k} [s]$ . If $k = s$ , then set $δ [s] = δ [s] ↾ k$ and $A [s] = A_{k} [s]$ . We end this stage by canceling all strategies α such that $δ [s] < α$ (i.e., initializing all nodes to the right of the current path) and proceed to stage $s + 1$ . When an $N$ -strategy α is initialized, we set $C_{α}$ , $x_{α}$ and $s_{α}$ to their initial states. For every element x in $X_{α}$ which has status used, we set its status to canceled, enumerate the axiom $⟨ x, \emptyset ⟩$ into both operators Γ and Λ and make $a (x)$ , $u (x)$ and $v (x)$ undefined.

Otherwise, denote $δ [s] ↾ k$ by α. We activate the strategy α until it produces an outcome $o$ , in which case we move on to the next substage. $A_{k + 1} [s]$ is defined by α and $δ [s] ↾ k + 1 = α \hat{} o$ .

The $N$ -strategy α.

The strategy α first executes the C-module, the module that checks the state of previous cycles. If this module signals that one of the previous cycles seems successful, α ends its activity with the corresponding outcome. Otherwise it carries on to the main module, which runs the newest cycle.

The C-module: Scan all entries of the list $C_{α}$ from first to last until an entry produces an outcome or all entries are scanned.

Scanning $C_{α} [n]$ : Let $C_{α} [n] = ⟨ x_{n}, a_{n}, U_{n}, V_{n}, o_{n} ⟩$ . Search for stages $t_{1}$ and $t_{2}$ such that:
$o_{n} < t_{1} ⩽ s$ and $U_{n} ⊈ U [t_{1}]$ ; and

$o_{n} < t_{2} ⩽ s$ and $V_{n} ⊈ V [t_{2}]$ .

If such stages $t_{1}$ and $t_{2}$ are found then set $o_{n} = s$ . Let $A_{k + 1} [s]$ be the set which is produced by extracting from $A_{k} [s]$ the elements $a (x_{m})$ for every m such that $n ⩽ m < | C_{α} |$ , the elements $a_{m}$ for every m such that $n < m < | C_{α} |$ , and $a (x_{α})$ , the marker of the current witness $x_{α}$ . Let the outcome be $n$ .

Otherwise, move on to the next entry of the list $C_{α}$ .

The main module:
If the witness $x_{α}$ is not defined, then α starts a new cycle. Let $x_{α}$ be the least unused witness from $X_{α}$ . Change the status of $x_{α}$ to used. Set $s_{α} = u (x_{α}) = v (x_{α}) = s$ and let $a (x_{α})$ be a fresh number larger than s and unused in the construction so far. Set $A_{k + 1} [s] = A_{k} [s]$ and let the outcome be $w$ . Otherwise, go to the next step.

If $x_{α} \notin Φ_{| α |} (A_{k} [s] ↾ s)$ then set $A_{k + 1} [s] = A_{k} [s]$ and let the outcome be $w$ . Otherwise, go to the next step.

Let $\hat{U} = ⋂_{s_{α} < t ⩽ s} U [t] ↾ u (x_{α})$ and $\hat{V} = ⋂_{s_{α} < t ⩽ s} V [t] ↾ v (x_{α})$ . Enumerate a new entry in the list $C_{α}$ : $\begin{matrix} ⟨ x_{α}, a (x_{α}), \hat{U}, \hat{V}, s ⟩ . \end{matrix}$ Set $a (x_{α})$ to be a fresh number larger than s. Set $u (x_{α}) = v (x_{α}) = 0$ . Make $x_{α}$ and $s_{α}$ undefined and go to step (1).
Verification.

Towards showing that the true path is infinite, we first show the following property of the construction: Lemma 3.3.
Let α be an $N$ -strategy which, for a least stage s, is not initialized at any stage $t > s$ and which is visited infinitely often. If α has infinitely many cycles, then there is a least n such that α has outcome $n$ at infinitely many stages.
Proof.
Towards a contradiction, suppose that α defines an infinite list $C_{α}$ and for every n, α has outcome $n$ at most finitely many times. After stage s, the list $C_{α}$ is not initialized. From the third and fourth parameters in the entries recorded in this list, we obtain two infinite approximating sequences ${U_{n}}_{n < ω}$ and ${V_{n}}_{n < ω}$ . We will show that these are $Σ_{2}^{0}$ -approximations to U and V, satisfying the $K$ -approximation property: for every n, either $U_{n} \subseteq U$ or $V_{n} \subseteq V$ . As U and V do not form a $K$ -pair, by Lemma 2.11 this is a contradiction.

For every n, let $s_{n} > s$ be the stage at which the values of $U_{n}$ and $V_{n}$ are defined. It follows from step (3) of the main module that for every n, $U_{n + 1} = ⋂_{s_{n} < t ⩽ s_{n + 1}} U [t] ↾ s_{n}$ and $V_{n} = ⋂_{s_{n} < t ⩽ s_{n + 1}} V [t] ↾ s_{n}$ . For $x \in U$ , let $t_{x}$ be a stage such that $t_{x} > x$ and at all stages $t > t_{x}$ , $x \in U [t]$ . For every n such that $s_{n} > t_{x}$ , we have that $x \in U_{n + 1}$ . If $x \notin U$ , then $x \notin U [t]$ whenever t is a good stage (i.e., when $U [t] \subseteq U$ ). Then for every n such that there is a good stage $t \in (s_{n}, s_{n + 1}]$ we have that $x \notin U_{n + 1}$ . As there are infinitely many good stages and the sequence ${s_{n}}_{n < ω}$ is strictly increasing, it follows that there are infinitely many n such that $x \notin U_{n}$ . That ${V_{n}}_{n < ω}$ is a $Σ_{2}^{0}$ -approximation to V is proved similarly.

Let n be a natural number. Let $t_{n}$ be a stage such that the outcomes that α has at stages $t ⩾ t_{n}$ are greater than $n$ . It follows that $o_{n}$ , the last parameter in the list $C_{α} [n]$ which records the previous stage when α had outcome $n$ , has permanent value strictly less than $t_{n}$ . If $U_{n} ⊈ U$ , then there is a stage $t ⩾ t_{n}$ such that $U_{n} ⊈ U [t]$ . As α does not have outcome $n$ after stage $t_{n}$ , it follows that for all $t ⩾ t_{n}$ we have $V_{n} \subseteq V [t]$ and thus $V_{n} \subseteq V$ . □
Corollary 3.4.
There is an infinite path f in the tree of strategies T with the following two properties:
For every k, there are infinitely many stages s such that $f ↾ k ⪯ δ [s]$ .

For every k, there is a least stage $s (k)$ such that $f ↾ k$ is not initialized at any stage $t > s (k)$ .

Proof.
We define the true path inductively. Obviously, $f ↾ 0 = \emptyset$ and $s (0) = 0$ satisfy both properties, as the root of the tree is visited at every stage and never initialized. Suppose we have defined $f ↾ k = α$ and $s (k)$ . If only finitely many values are enumerated into $C_{α}$ at stages $t > s (k)$ , then α has only finitely many possible outcomes at stages $t > s (k)$ . Let $o$ be the leftmost one that is visited infinitely many times. Then $f ↾ (k + 1) = α \hat{} o$ and $s (k + 1) ⩾ s (k)$ is the last stage when α has an outcome that is to the left of $o$ . Otherwise, $C_{α}$ has infinitely many entries, i.e., α has infinitely many cycles, and by Lemma 3.3, there are a leftmost outcome $n$ and a stage $s (k + 1)$ such that $α \hat{} n$ is visited at infinitely many stages, and at any stage $t > s (k + 1)$ , the strategy α does not have an outcome $m <_{L} n$ . In this case, $f ↾ (k + 1) = α \hat{} n$ satisfies both properties. □
Lemma 3.5.
$Γ (U \oplus A) = Λ (V \oplus A)$ .
Proof.
Let x be a natural number. Depending on the status of x as a witness, we have the following cases: Case 1.
The element x is not a witness or does not become a used witness at any stage. In this case, the u-, v- or a-markers for x do not receive a value at any stage and the main strategy does not enumerate any axiom for x. So, in this case, $x \notin Γ (U \oplus A) \cup Λ (V \oplus A)$ .
Case 2.
The element x becomes a used witness, but at some finite stage is canceled. But when it is canceled, the axiom $⟨ x, \emptyset ⟩$ is enumerated into both operators Γ and Λ. In this case, $x \in Γ (U \oplus A) \cap Λ (V \oplus A)$ .
Case 3.
The element x becomes a used witness for an $N$ -strategy α but never enters the list $C_{α}$ and is never canceled. Then the values of its u-, v- and a-markers are defined once at stage s, when α picks x as a current witness, and remain the same at all further stages. At stages $t > s$ , the axioms enumerated into Γ and Λ are $⟨ x, (U [t] ↾ u (x)) \oplus {a (x)} ⟩$ and $⟨ x, (V [t] ↾ v (x)) \oplus {a (x)} ⟩$ , respectively. Thus, if $a (x) \notin A$ , then $x \notin Γ (U \oplus A) \cup Λ (V \oplus A)$ . If $a (x) \in A$ , then let $t_{1} > t$ be a good stage for the approximation to $U \oplus V$ , i.e., $U [t_{1}] \subseteq U$ and $V [t_{1}] \subseteq V$ . Then the axioms $⟨ x, (U [t_{1}] ↾ u (x)) \oplus {a (x)} ⟩ \in Γ [t_{1}]$ and $⟨ x, (V [t_{1}] ↾ v (x)) \oplus {a (x)} ⟩ \in Λ [t_{1}]$ witness the fact that $x \in Γ (U \oplus A) \cap Λ (V \oplus A)$ .
Case 4.
The element x becomes a used witness for an $N$ -strategy α at stage $s_{1}$ , enters list $C_{α}$ at stage $s_{2}$ as part of the nth entry and is never canceled. The u-, v- and a-markers for x have the same values $u_{1}$ , $v_{1}$ , $a_{1}$ at stages $t \in (s_{1}, s_{2}]$ , and values 0, 0, $a_{2}$ with $a_{1} < a_{2}$ at stages $t > s_{2}$ . $C_{α} [n] = ⟨ x, a_{1}, U_{n}, V_{n}, o_{n} ⟩$ , where $U_{n} = ⋂_{s_{1} < t ⩽ s_{2}} U [t] ↾ u_{1}$ and $V_{n} = ⋂_{s_{1} < t ⩽ s_{2}} V [t] ↾ v_{1}$ . The axioms enumerated into Γ are $⟨ x, (U [t] ↾ u_{1}) \oplus {a_{1}} ⟩$ for every $t \in (s_{1}, s_{2}]$ and $⟨ x, \emptyset \oplus {a_{2}} ⟩$ . The axioms enumerated into Λ are $⟨ x, (V [t] ↾ v_{1}) \oplus {a_{1}} ⟩$ for every $t \in (s_{1}, s_{2}]$ and $⟨ x, \emptyset \oplus {a_{2}} ⟩$ . If $a_{2} \in A$ , then $x \in Γ (U \oplus A) \cap Λ (V \oplus A)$ .

So suppose $a_{2} \notin A$ . This means that the strategy α is visited infinitely often and not initialized after stage $s_{1}$ , thus it is on the true path. Furthermore, the true outcome of α is $o ⩽ n$ . If $o < n$ , then every time α has its true outcome $o$ , both $a_{1}$ and $a_{2}$ are extracted from A. Thus $a_{1} \notin A$ , hence $x \notin Γ (U \oplus A) \cup Λ (V \oplus A)$ . Finally, if $o = n$ , then let $t_{1} < t_{2} < \dots < t_{k} < \dots$ be the sequence of stages at which α has outcome $n$ . By construction, these are the consecutive values defined for the parameter $o_{n}$ , the last parameter in the entry $C_{α} [n]$ . For every interval of stages $(t_{k}, t_{k + 1}]$ , there are stages $t^{'}$ and $t^{″}$ in this interval such that $U_{n} ⊈ U [t^{'}]$ and $V_{n} ⊈ V [t^{″}]$ . Thus $U_{n} ⊈ U$ and $V_{n} ⊈ V$ , hence in this case as well, $x \notin Γ (U \oplus A) \cup Λ (V \oplus A)$ . □
Lemma 3.6.
$Γ (A \oplus U) ≰_{e} A$ .
Proof.
For every e, we will show that $Φ_{e} (A) \neq Γ (A \oplus U)$ . Fix a natural number e and let $α = f ↾ e$ be the $N_{e}$ -strategy on the true path. By Corollary 3.4, there is a least stage $s (e)$ such that α is not initialized after stage $s (e)$ . Let $o$ be α’s true outcome. If $o = w$ , then by Lemma 3.3, α has finitely many cycles and there is a last witness $x_{α}$ that never enters the list $C_{α}$ . Hence, at all α-true stages s, $x_{α} \notin Φ_{e} (A [s] ↾ s)$ . By Case 3 from the proof of Lemma 3.5 and the fact that $a (x) \in A$ , we have that $x \in Γ (U \oplus A) ∖ Φ_{e} (A)$ , and hence the strategy is successful.

If $o = n$ , let $s > s (e)$ be the stage at which $C_{α} [n] = ⟨ x_{n}, a_{n}, U_{n}, V_{n}, o_{n} ⟩$ is defined. By Case 4 from the proof of Lemma 3.5, since $a (x_{n}) \notin A$ , we have that $x_{n} \notin Γ (U \oplus A)$ . At stage s, we have that $x_{n} \in Φ_{e} (A_{| α |} [s] ↾ s)$ . Thus we need to show that $A_{| α |} [s] ↾ s \subseteq A$ . The inductive definition of the approximation to the set A that we define during the construction ensures that for every stage t and natural number a we have that $a \notin A [t]$ if and only if there is a strategy along $δ [t]$ that extracts a at stage t. The definition of A from its approximation ensures that $a \notin A$ if and only if $a \notin A [t]$ for infinitely many stages t. It suffices to show that no number $a \in A_{| α |} [s] ↾ s$ is extracted at infinitely many stages. The strategy α does not cause the extraction of any element $a < s$ , as after α stops having outcomes to the left of $n$ , it can only extract markers that are defined after stage s and hence are greater than s. Strategies that are not on the true path are either visited finitely many times or initialized infinitely often and hence do not cause the extraction of any elements from the set A. Strategies extending $α \hat{} n$ are in initial state at stage $s (e) + 1$ and are not visited at stages $t \in (s (e), s]$ , as $C_{α} [n]$ is not defined at these stages. If γ is an $N$ -strategy of higher priority than α that causes an element $a < s$ to be extracted from A, then γ has true outcome $m$ for some $m \in N$ and a is defined before stage s as either an a-marker (past or current) of a witness $x_{k}$ , where $k > m$ , as the second a-marker $a (x_{m}) [s]$ , or $a (x_{γ}) [s]$ . All such markers are extracted at every $γ \hat{} m$ -true stage greater than or equal to s. In particular, as $γ \hat{} m ⪯ α$ and s is an α-true stage, it follows that $a \notin A_{| α |} [s] ↾ s$ . Thus $A_{| α |} [s] ↾ s \subseteq A$ , and hence $x_{n} \in Φ_{e} (A) ∖ Γ (A \oplus U)$ . □

This completes the proof of Theorem 3.2. □

4. Genericity, semi-computability, and $K$ -pairs

We will see that a sufficiently generic set cannot be half of a nontrivial $K$ -pair, hence cannot be enumeration equivalent to a semi-computable set. However, the amount of genericity needed for these two properties is not the same. We will show that a 1-generic set can be half of a nontrivial $K$ -pair, and in fact, both halves can be 1-generic. On the other hand, no 1-generic set is enumeration equivalent to a semi-computable set. These two results are shown in Lemmas 4.3 and 4.2, respectively, and yield the following:

Theorem 4.1.
There is a (nontrivial) $K$ -pair such that neither set in the pair is enumeration equivalent to a semi-computable set.
Proof.
Immediate from Lemmas 4.2 and 4.3, proved below. □
Lemma 4.2.
No 1-generic set is enumeration equivalent to a semi-computable set.
Proof.
Let $X \in 2^{ω}$ be 1-generic. By Proposition 2.9, we must show that X is not enumeration equivalent to an initial segment of $⟨ 2^{< ω}, ⩽ ⟩$ . Let Γ and Δ be enumeration operators and assume that $X = Γ (Δ (X))$ . We will view $Δ (X)$ as a subset of $2^{< ω}$ .

Assume, for a contradiction, that $Δ (X)$ is an initial segment of $2^{< ω}$ . Consider the following c.e. subsets of $2^{< ω}$ : $\begin{array}{rcl} T_{0} = {σ : (\exists ρ) ρ 10 ⪯ σ, | ρ | \in Γ (Δ (σ)) with Γ -use F, \\ (\exists τ) ρ 01 ⪯ τ, | ρ | + 1 \in Γ (Δ (τ)) with Γ -use G, \\ and max (F) ⩾ max (G)}, \\ T_{1} = {τ : (\exists ρ) ρ 01 ⪯ τ, | ρ | + 1 \in Γ (Δ (τ)) with Γ -use G, \\ (\exists σ) ρ 10 ⪯ σ, | ρ | \in Γ (Δ (σ)) with Γ -use F, \\ and max (G) ⩾ max (F)}, \\ T = T_{0} \cup T_{1} . \end{array}$ Here $Δ (σ)$ is shorthand for $Δ ({n < | σ | : σ (n) = 1})$ and F and G are considered as subsets of $2^{< ω}$ ordered lexicographically. We claim that no prefix of X can be in T. To see this, assume first that $σ ≺ X$ is in $T_{0}$ as witnessed by ρ and τ. Then $| ρ | \in Γ (Δ (σ))$ with Γ-use F. In particular, $F \subseteq Δ (σ) \subseteq Δ (X)$ . Also, $| ρ | + 1 \in Γ (Δ (τ))$ with Γ-use G. But $max (F) ⩾ max (G)$ , and we are assuming that $Δ (X)$ is an initial segment of $2^{< ω}$ , so $G \subseteq Δ (X)$ . This means that $| ρ | + 1 \in Γ (Δ (X))$ . But $| ρ | + 1 \notin ρ 10 ⪯ σ ≺ X$ , which is a contradiction. Similarly, no prefix of X is in $T_{1}$ .

Since X is 1-generic, it must have a prefix $ν ≺ X$ that has no extension in T. We will show that this is also impossible. Consider the following c.e. subset of $2^{< ω}$ : $\begin{matrix} S = {ρ 01 : ν ⪯ ρ and (\exists σ) [ρ 10 ⪯ σ and | ρ | \in Γ (Δ (σ))]} . \end{matrix}$ First, we claim that every prefix of X has an extension in S. Let $ν ⪯ μ ≺ X$ . Every 1-generic is infinite and co-infinite, so there is a ρ such that $μ ⪯ ρ$ and $ρ 10 ≺ X$ . Since $X = Γ (Δ (X))$ , we know that $| ρ | \in Γ (Δ (X))$ , so for any sufficiently long σ extending $ρ 10$ , we have $| ρ | \in Γ (Δ (σ))$ . Therefore, we have $μ ≺ ρ 01 \in S$ .

Since X is 1-generic and no prefix of X avoids S, there must be a $ρ 01 \in S$ such that $ρ 01 ≺ X$ . In particular, there is a $σ ⪰ ρ 10$ such that $| ρ | \in Γ (Δ (σ))$ , say, with Γ-use F. We also have $| ρ | + 1 \in X = Γ (Δ (X))$ , so there is a τ extending $ρ 01$ such that $| ρ | + 1 \in Γ (Δ (τ))$ , say with Γ-use G. If $max (F) ⩾ max (G)$ , then $σ \in T_{0}$ . Otherwise, $max (G) > max (F)$ , so $τ \in T_{1}$ . Either way, there is an element of T that extends $ρ ⪰ ν$ , contradicting the choice of ν and completing the proof. □
Lemma 4.3.
There are 1-generic sets A and B that form a $K$ -pair.
Proof.
We construct $Δ_{2}^{0}$ -approximations ${A [s]}_{s < ω}$ and ${B [s]}_{s < ω}$ to sets A and B. To ensure that A and B are 1-generic we meet the standard genericity requirements: For every natural number e, let $G_{2 e}$ express that A meets or avoids the eth c.e. set of finite binary strings, similarly let $G_{2 e + 1}$ express that B meets or avoids the eth c.e. set of finite binary strings. As usual, priority is given to requirements with smaller indices.

To meet the requirement $G_{2 e}$ , we have a natural strategy: When activated for the first time after injury, say at stage $s_{0}$ , it is provided with an initial segment $σ = A [s_{0}] ↾ R_{2 e}$ , restrained by higher-priority strategies. The strategy waits for $τ ⪰ σ$ to enter $W_{e}$ . If no such τ is found, then $G_{2 e}$ is satisfied as witnessed by σ. If at a stage $s_{1} ⩾ s_{0}$ , the strategy sees $τ ⪰ σ$ enter $W_{e} [s_{1}]$ , then it requires attention. If it receives attention at stage $s_{1}$ , then it ensures that τ is an initial segment of A at stage $s_{1}$ and onwards by injuring lower-priority requirements and raising the value of $R_{2 i}$ , for $i > e$ , to a number larger than $| τ |$ .

Now we need to incorporate the $K$ -pair requirements. By Lemma 2.11, it is sufficient to ensure that for every s, either $A [s] \subseteq A$ or $B [s] \subseteq B$ . Making τ an initial segment of $A [s_{1}]$ might require the extraction of a number $a > R_{2 e}$ from the current approximation of A. This means that at all stages t such that $a \in A [t]$ , we will ultimately have that $A [t] ⊈ A$ . Thus we need to ensure that $B [t] \subseteq B$ . To do this, we limit the possible problematic stages t by ensuring that at the initial stage $s_{0}$ , no number larger than $R_{2 e}$ has ever been enumerated into A. Thus all problematic stages t are larger than $s_{0}$ . Then at stage $s_{1}$ , we will “dump” into B all elements that have appeared in B at stages after $s_{0}$ and preserve B up to the largest dumped element by raising the restraint $R_{2 i + 1}$ for $i ⩾ e$ .

This leads us to the following construction. Let $A [0] = B [0] = \emptyset$ and $R_{j} [0] = j$ and $S_{j} [0] = 0$ for all $j < ω$ . Assume we have constructed $A [s]$ , $B [s]$ and for every $j < ω$ , the restraint $R_{j} [s]$ and the stage $S_{j} [s]$ .

We will say that $G_{2 e}$ requires attention at stage $s + 1$ , witnessed by τ, if τ is a finite string in $W_{e} [s]$ that extends $A [s] ↾ R_{2 e} [s]$ . Similarly, $G_{2 e + 1}$ requires attention at stage $s + 1$ if there is a finite binary string $τ \in W_{e} [s]$ that extends $B [s] ↾ R_{2 e + 1} [s]$ . At stage $s + 1$ , pick the highest priority strategy that has not yet been satisfied and that requires attention.

Assume, for concreteness, that it is $G_{2 e}$ and let τ be its least witness. We set $A [s + 1] (n) = τ (n)$ if $n < | τ |$ and $A [s + 1] (n) = 0$ otherwise. We set $B [s + 1] = ⋃_{S_{2 e} < t ⩽ s} B [t]$ . We initialize all lower-priority requirements. We set $R_{j} [s + 1] = max (| τ, B [s + 1] |)$ and $S_{j} = s + 1$ for all $j > 2 e$ and move on to the next stage.

The verification that this construction works is now a routine induction on the priority ordering. □

We finish the section by showing, as claimed above, that a sufficiently generic set cannot be half of a nontrivial $K$ -pair. In fact, weak 2-genericity is sufficient, so Lemma 4.3 is fairly tight.

We recall the definition of weak n-genericity, a notion that was introduced by Kurtz [11]. Call a set $S \subseteq 2^{< ω}$ of strings dense if every $σ \in 2^{< ω}$ has an extension in S. A set $G \in 2^{ω}$ is weakly n-generic if for every dense $Σ_{n}^{0}$ -set $S \subseteq 2^{< ω}$ , there is a $τ \in S$ that is a prefix of G. Kurtz [11] showed that $\begin{matrix} 2 -generic ⟹ weakly 2 -generic ⟹ 1 -generic ⟹ weakly 1 -generic, \end{matrix}$ and that all implications are strict.
Proposition 4.4.
If A is weakly 1-generic and half of a nontrivial $K$ -pair, then A is $Σ_{2}^{0}$ .
Proof.
Assume that A forms a nontrivial $K$ -pair with B witnessed by $W \subseteq ω \times ω$ . We claim that $\begin{matrix} b \in B iff (\exists^{\infty} a) [⟨ a, b ⟩ \in W] . \end{matrix}$ First, assume that $b \in B$ . Since A is weakly 1-generic, there are infinitely many $a \in A$ . For each such a, it is the case that $⟨ a, b ⟩ \in W$ , so $(\exists^{\infty} a) ⟨ a, b ⟩ \in W$ . For the other direction, fix b and assume that $(\exists^{\infty} a) ⟨ a, b ⟩ \in W$ . Consider the following c.e. subset of $2^{< ω}$ : $\begin{matrix} T = {σ : (\exists a < | σ |) [σ (a) = 0 and ⟨ a, b ⟩ \in W]} . \end{matrix}$ By assumption, T is dense and obviously $Σ_{1}^{0}$ , so A has a prefix $σ \in T$ . Therefore, there is an $a \notin A$ such that $⟨ a, b ⟩ \in W$ , which implies that $b \in B$ . This proves the claim, giving us a $Π_{2}^{0}$ -definition of B. But recall that since A and B form a nontrivial $K$ -pair, $A ⩽_{e} \overline{B}$ by Proposition 2.6, so A is $Σ_{2}^{0}$ . □
Corollary 4.5.
No weakly 2-generic set is half of a nontrivial $K$ -pair.
Proof.
By the previous proposition, all that remains is to prove that if $A \in 2^{ω}$ is weakly 2-generic, then it is not $Σ_{2}^{0}$ . This fact is well known and easy to see: If $I \in 2^{ω}$ is an infinite $Σ_{2}^{0}$ -set, then $\begin{matrix} S = {σ : (\exists n < | σ |) [σ (n) = 0 and n \in I]} \end{matrix}$ is a dense $Σ_{2}^{0}$ -subset of $2^{< ω}$ . Hence A has a prefix in S, implying that $I ⊈ A$ . □

Let $H$ be the class consisting of all sets that are half of a nontrivial $K$ -pair. By the previous result, $H$ is meager. It is natural to ask if $H$ is also small in the sense of measure. It is, as the following proposition demonstrates. Recall that a Martin–Löf test is a uniform sequence ${U_{n}}_{n \in ω}$ of $Σ_{1}^{0}$ -classes such that $μ (U_{n}) ⩽ 2^{- n}$ for all $n \in ω$ . (Here μ is the standard Lebesgue measure on Cantor space.) A set $A \in 2^{ω}$ passes the test if $A \notin ⋂_{n \in ω} U_{n}$ . We say that A is 1-random (or Martin–Löf random) if it passes all Martin–Löf tests. Note that the class of 1-random sets has full measure, so the following result shows that $μ (H) = 0$ . Proposition 4.6.
No 1-random set is half of a nontrivial $K$ -pair.
Proof.
Assume that $A \in 2^{ω}$ is 1-random and that A and B form a $K$ -pair as witnessed by W. We will show that B must be c.e.

Consider the family of c.e. sets $F_{b} = {a : ⟨ a, b ⟩ \in W}$ , defined uniformly in $b \in ω$ . If $| F_{b} | ⩾ m$ , let $F_{b, m}$ be the first m elements enumerated into $F_{b}$ and let $V_{b, m} = {X \in 2^{ω} : F_{b, m} \subseteq X}$ . If $| F_{b} | < m$ , let $V_{b, m} = \emptyset$ . For each $n \in ω$ , let $U_{n} = ⋃_{b \in ω} V_{b, n + b + 1}$ . Note that $U_{n}$ is a $Σ_{1}^{0}$ -class, uniformly in n, and $μ (U_{n}) ⩽ \sum_{b \in ω} μ (V_{b, n + b + 1}) ⩽ \sum_{b \in ω} 2^{- n - b - 1} = 2^{- n}$ , hence ${U_{n}}_{n \in ω}$ is a Martin–Löf test. Therefore, there is an n such that $A \notin U_{n}$ .

We claim that $b \in B$ if and only if $| F_{b} | ⩾ n + b + 1$ . Note that this implies that B is c.e., completing the proof. First, assume that $b \in B$ . In this case, $A \times {b} \subseteq W$ , so $A \subseteq F_{b}$ . Since A is 1-random, there are infinitely many $a \in A$ , and hence $F_{b}$ is infinite. Now assume that $b \notin B$ . Since $F_{b} \times {b} \subseteq W$ , it must be the case that $F_{b} \subseteq A$ . This means that if $| F_{b} | ⩾ n + b + 1$ , then $A \in V_{b, n + b + 1} \subseteq U_{n}$ , which contradicts the choice of n. Therefore, $| F_{b} | < n + b + 1$ . □

5. A set without a maximal $K$ -partner

Consider the $K$ -partners of an e-degree a, i.e., ${b : a and b form a K -pair}$ . By Proposition 2.5, this set is an ideal in the enumeration degrees. Assume that a is half of a maximal $K$ -pair, in particular, with $K$ -partner b. Cai et al. [2] proved that there is a (semi-computable) set A such that $a = d_{e} (A)$ and $b = d_{e} (\overline{A})$ . By Proposition 2.6, every $K$ -partner of A is enumeration reducible to $\overline{A}$ , so b is the maximum $K$ -partner for a. In other words, if a is half of a maximal $K$ -pair, then its ideal of $K$ -partners is principal. By Theorem 4.1, we know that there is a nontrivial $K$ -pair that contains no semi-computable sets, hence neither half is part of a maximal $K$ -pair. This still leaves the possibility, however, that every nonzero degree has a principal ideal of $K$ -partners. In this section, we prove that this is not necessarily the case.

Theorem 5.1.

There is a set A that is half of a nontrivial $K$ -pair such that the set ${d_{e} (B) : A and B form a K -pair}$ is not a principal ideal.

Proof.

The rest of this section is devoted to the proof of Theorem 5.1.

List of requirements and priority tree.

We have the following list of requirements; as usual, each requirement corresponds to nodes on a priority tree that are labeled by the requirement. First, we have the usual requirements for making A non-c.e.: $\begin{matrix} P_{j} : A \neq W_{j} . \end{matrix}$ Each $P$ -node has two outcomes: $d$ (diagonalization) and $w$ (wait).

Our other requirements will ensure that there is no maximum $K$ -partner for A. Assuming that we meet all $P_{j}$ -requirements, Remark 2.1 gives us a way to index all possible $K$ -partners for A. Let $B_{e} = {b : (\exists a) [⟨ a, b ⟩ \in W_{e} and a \in \overline{A}]}$ . If A and B form a $K$ -pair witnessed by $W_{e}$ , then $B = B_{e}$ . Therefore, the following requirements guarantee that A has no maximum $K$ -partner: $\begin{matrix} R_{e} : K (A, B_{e}) via W_{e} ⟶ (\exists C) [K (A, C) \land C ≰_{e} B_{e}], \end{matrix}$ where $K (A, B)$ means that A and B form a $K$ -pair. Each $R$ -node has two outcomes: $i$ (infinite) and $w$ (wait). Moreover, below the infinite outcome of an $R_{e}$ -requirement, we have subrequirements ensuring $C ≰_{e} B_{e}$ : $\begin{matrix} R_{e, i} : C \neq Φ_{i} (B_{e}) . \end{matrix}$ Such a subrequirement node also has two outcomes: $d$ (diagonalization) and $w$ (wait). The outcome $d$ involves the most difficult part of the construction.

Note that we do not need a requirement to ensure that A is half of a nontrivial $K$ -pair. Take any e such that $W_{e} = \emptyset$ . Then $B_{e} = \emptyset$ and A and $B_{e}$ form a $K$ -pair witnessed by $W_{e}$ , so $R_{e}$ gives us a $C ≰_{e} \emptyset$ such that A and C form a $K$ -pair.

Construction.

We will construct the set A by a $Δ_{2}$ -approximation, meaning that for every $x \in ω$ , we can change $A (x)$ as many times as we want as long as it eventually settles down. The approximation to A induces an approximation to the set $B_{e}$ : $B_{e} [s] = {b : (\exists a) [⟨ a, b ⟩ \in W_{e} [s] and a \in \overline{A [s]} ↾ s]}$ .

The $P_{j}$ -requirements are handled very naturally: We first pick a fresh number y to witness the diagonalization, put it into A, and wait for y to enter the corresponding c.e. set $W_{j}$ . While we wait, the outcome is $w$ . If x never enters $W_{j}$ , then we satisfy the requirement; if y eventually does enter $W_{j}$ , then we take y out of A and change the outcome to $d$ . In this case, the requirement is also satisfied. So for the remaining part of the construction, let us focus on the $R$ -requirements and their subrequirements.

The $R_{e}$ -nodes service requests made by their substrategies. These requests are explained in detail below. The failure of an $R_{e}$ -node to complete a request would prove that A and $B_{e}$ do not form a $K$ -pair witnessed by $W_{e}$ . When we reach an $R_{e}$ -node α, we check for an active request. If there is no active request at α, then by default we go to outcome $i$ . If there is an active request at α that can be completed, then α completes it and has outcome $i$ ; otherwise α has outcome $w$ .

Below outcome $i$ , we construct a set $C_{α}$ and require that A and $C_{α}$ form a $K$ -pair. We use the same strategy as before (see Lemma 2.11 and the proof of Lemma 4.3), namely, when we remove any element x from $C_{α}$ , we need to add all elements back into A that were in A while x was in $C_{α}$ , and vice versa.

We now consider an $R_{e, i}$ -subrequirement node β below an $R_{e}$ mother node α. It is working to diagonalize $C_{α}$ against $Φ_{i} (B_{e})$ . Naively, we pick a fresh witness x at this node β when it is first visited (after it has been initialized). We initially assume that $x \notin Φ_{i} (B_{e})$ and so put x into $C_{α}$ for diagonalization. In this case, the outcome is $w$ . If we see that x enters $Φ_{i} (B_{e})$ , then we want to take x out of $C_{α}$ and go to outcome $d$ . However, this plan has a very serious flaw. Notice that when we take x out of $C_{α}$ , we need to add some elements back into A. Denote the set of such elements by $R_{x}$ ; it will turn out that these were all removed from A by lower-priority requirements, hence no higher-priority requirement will be injured. The problem is that $B_{e} ⩽_{e} \overline{A}$ , so adding $R_{x}$ to A may affect the use of $x \in Φ_{i} (B_{e})$ and prevent the desired diagonalization.

The solution is as follows. At the moment we see x enter $Φ_{i} (B_{e})$ at β, we remove x from $C_{α}$ , but we do not immediately add $R_{x}$ to A. Instead, we rely on the mother node α to provide permission to add $R_{x}$ to A, which it acquires by exploiting the assumption that A and $B_{e}$ form a $K$ -pair witnessed by $W_{e}$ . Let F be the current use of $x \in Φ_{i} (B_{e})$ . We want to be able to add $R_{x}$ to A without removing F from $B_{e}$ . To do this, we issue the following request to α and end the current stage:

Pick a fresh number m and add it to A.

If ${m} \times F ⊈ W_{e}$ , stay in outcome $w$ of α.

If ${m} \times F \subseteq W_{e}$ , remove m from A and add $R_{x}$ back into A (completing the request and fulfilling the promise implicit in the removal of x from $C_{α}$ ). Continue to outcome $i$ of α.

Note that the removal of m from A ensures (by the definition of

B_{e}

) that

F \subseteq B_{e}

at the end of step (3). As long as m remains out of A, which is preserved with priority α, we have

F \subseteq B_{e}

and thus

x \in Φ_{i} (B_{e})

. Also note that at step (3), no

C_{α}

-change is necessary, as we have not changed

C_{α}

ever since we issued this request.

There are two cases in which an element is extracted from A: a $P_{j}$ -node extracts its diagonalization witness, or an $R_{e}$ strategy completes a request. Both of these actions can affect the requirement that A and $C_{α}$ remain a $K$ -pair for strategies α with higher priority. We prevent this from happening by asking that whenever a sub-requirement node β is initialized, its witness x is dumped back into $C_{α}$ .

The construction combines the above strategies in an infinite-injury priority argument on a tree of strategies in the usual way.

Verification.

First, it is easy to see that there is a leftmost path that is visited infinitely often; call this the true path. We must argue that all strategies along the true path satisfy their requirements.

Consider a $P_{j}$ -strategy γ along the true path. Let y be γ’s last witness. If γ never removes y from A, then it is successful. The strategy is vulnerable to injury only if it removes y from A. The possible danger comes from an $R_{e, i}$ -strategy β that has issued a request to enumerate y back in A in order to remove its own witness x from $C_{α}$ . We argue that this is not possible as follows. If γ has higher priority than β, then β will be visited for the first time after initialization only after y has been removed from A, so there is no stage at which both $y \in A$ and $x \in C_{α}$ . Similarly, if β has higher priority than γ and β ever issues a request, then γ will be visited for the first time after initialization after this request has been issued and x is already removed from $C_{α}$ , thus again there is no stage at which both $y \in A$ and $x \in C_{α}$ .

Let α be an $R_{e}$ -strategy along the true path. If α has true outcome $w$ , then there is an active request, issued after α’s last initialization, that cannot be completed. In other words, there are a number m and a finite set F such that ${m} \times F ⊈ W_{e}$ . The strategy α selected m and enumerated it into A in response to this request. As only α can ever remove this element from A, it follows that $m \in A$ at all future stages. The set F is a subset of $B_{e}$ when the request is made; a set $R_{x} \subseteq \overline{A}$ ensures this. We argue that $R_{x}$ remains a subset of $\overline{A}$ at all future stages. We can assume that $P_{j}$ - or $R_{j, i}$ -strategies of higher priority than α will not act at future stages, or else α is initialized. Similarly $R_{j}$ strategies of higher priority, such that α extends their outcome $w$ never complete their requests. An $R_{j}$ -strategy of higher priority than α, such that α extends its infinite outcome $i$ , can only complete requests issued after α’s request without initializing α. It follows that these requests are issued by strategies of lower priority than α. Thus only strategies of lower priority than α can affect the set A. However, strategies of lower priority than α that are ever active at future stages are visited for the first time (after initialization) after $R_{x} \subseteq \overline{A}$ , and hence will never cause an element from $R_{x}$ to be enumerated back into A. Thus, ${m} \times F \subseteq A \times B_{e}$ , proving that A and $B_{e}$ are not a $K$ -pair witnessed by $W_{e}$ .

If, on the other hand, α has true outcome $i$ , then all requests that α ever receives are eventually completed. Consider the set $C_{α}$ , built below $α \hat{} i$ . We will first show that A and $C_{α}$ form a $K$ -pair. By Lemma 2.11 it is sufficient to show that A and $C_{α}$ have the $K$ -pair approximation property. Suppose x is an element that is not in $C_{α}$ , but was in $C_{α}$ at stages $t \in [s_{0}, s_{x}]$ . It follows that x is a witness that belongs to a strategy β which is not initialized after stage $s_{0}$ . At stage $s_{x}$ , the strategy β issued a request to α that was completed. Thus all elements that were extracted from A at stages in the interval $[s_{0}, s_{x}]$ are enumerated back into A. No other element that appears in A at a stage in the interval $[s_{0}, s_{x}]$ can be extracted from A at further stages, as this would cause the initialization of β.

It remains to be shown that $C_{α} ≰_{e} B_{e}$ , i.e., that all $R_{e, i}$ -subrequirements are satisfied. Let β be an $R_{e, i}$ -node along the true path and x the final diagonalization witness at β. If β never issues a request, then the requirement is satisfied by direct diagonalization: $x \in C_{α} ∖ Φ_{i} (B_{e})$ . If β issues a request, then it removes x from $C_{α}$ , as it has found a finite set F such that $x \in Φ_{i} (F)$ . By assumption, α completes this request by removing from A a number m such that ${m} \times F \subseteq W_{e}$ . An argument similar to the ones above shows that $x \notin C_{α}$ and that $m \in \overline{A}$ (noting also that strategies extending $α \hat{} i$ are not visited at any stage at which $m \in A$ ). Therefore $F \subseteq B_{e}$ and $x \in Φ_{i} (B_{e}) ∖ C_{α}$ .

This completes the proof of Theorem 5.1. □

Footnotes

Acknowledgements

The first author was partially supported by NSF grant DMS-1266214. The second author was partly supported by AMS-Simons Foundation Collaboration Grant 209087. The third author was partially supported by the National Science Foundation under grant DMS-1001847. The fourth author was partially supported by a Marie Curie international outgoing fellowship STRIDE (298471) within the 7th European Community Framework Programme, a BNSF grant No. DMU 03/07/12.12.2011 and NSF Binational grant DMS-1101123.

References

M.M.

Arslanov,

Barry Cooper and

I.S.

Kalimullin, Splitting properties of total enumeration degrees, Algebra and Logic 42 (2003), 1–13.

Cai,

H.A.

Ganchev,

Lempp,

J.S.

Miller and

M.I.

Soskova, Defining totality in the enumeration degrees, Journal of the Amer. Math. Soc. (2015), to appear, available at: http://www.ams.org/cgi-bin/mstrack/accepted_papers/jams.

Barry Cooper, Partial degrees and the density problem. Part 2: The enumeration degrees of the

Σ_{2}

sets are dense, J. Symbolic Logic 49 (1984), 503–513.

Barry Cooper, Enumeration reducibilty, nondeterministic computations and relative computability of partial functions, in: Recursion Theory Week, Oberwolfach 1989,

Ambos-Spies,

Muler and

G.E.

Sacks, eds, Lecture Notes in Mathematics, Vol. 1432, Springer-Verlag, Heidelberg, 1990, pp. 57–110.

H.A.

Ganchev and

M.I.

Soskova, Cupping and definability in the local structure of the enumeration degrees, J. Symbolic Logic 77(1) (2012), 133–158.

H.A.

Ganchev and

M.I.

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

H.A.

Ganchev and

M.I.

Soskova, Definability via Kalimullin pairs in the structure of the enumeration degrees, Trans. Amer. Math. Soc. 367(7) (2015), 4873–4893.

Harrington, Understanding Lachlan’s monster paper, Handwritten notes, 1980.

C.G.

JockuschJr., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436.

10.

I.S.

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

11.

S.A.

Kurtz, Randomness and genericity in the degrees of unsolvability, PhD thesis, University of Illinois at Urbana–Champaign, 1981.

12.

McEvoy, Jumps of quasi-minimal enumeration degrees, J. Symbolic Logic 50 (1985), 839–848.

13.

R.A.

Shore and

T.A.

Slaman, Defining the Turing jump, Math. Res. Lett. 6 (1999), 711–722.

14.

T.A.

Slaman and

W.H.

Woodin, Definability in degree structures, 2005, available at: http://math.berkeley.edu/~slaman/talks/sw.pdf.

15.

Sorbi, The enumeration degrees of the Σ₂⁰ sets, in: Complexity, Logic and Recursion Theory,

Sorbi, ed., Marcel Dekker, New York, 1997, pp. 303–330.

On Kalimullin pairs

Abstract

Keywords

1. Introduction

2. Preliminaries

2.1. Enumeration reducibility

Definition 2.4 (Kalimullin [10]).

2.3. Semi-computable sets

Definition 2.8 (Jockusch [9]).

Proposition 2.9 (Ganchev and Soskova [7]).

Definition 2.10 (Ganchev and Soskova [7]).

2.4. K -pairs in D e ( ⩽ 0 ′ )

Lemma 2.11 (Kalimullin [10, Theorem 4.1]).

Footnotes

Acknowledgements

References

2.4. $K$ -pairs in $D_{e}$ ( $⩽ 0^{'}$ )