Pseudojump inversion in special r. b. Π_{1}^{0} classes

Hayden R. Jananthan Department of Mathematics Vanderbilt University Nashville, TN 37203, USA https://my.vanderbilt.edu/haydenjananthan hayden.r.jananthan@vanderbilt.edu

Stephen G. Simpson Department of Mathematics Vanderbilt University Nashville, TN 37203, USA http://www.math.psu.edu/simpson sgslogic@gmail.com

First draft: June 28, 2019 This draft: February 21, 2020

Abstract

The Jump Inversion Theorem says that for every real A ≥_{T} 0′ there is a real B such that A ≡_{T} B′ ≡_{T} B ⊕0′. A known refinement of this theorem says that we can choose B to be a member of any special Π_{1}^{0} subclass of {0, 1}^{ℕ}. We now consider the possibility of analogous refinements of two other well-known theorems: the Join Theorem – for all reals A and Z such that A ≥_{T} Z ⊕ 0′ and Z >_{T} 0, there is a real B such that A ≡_{T} B′ ≡_{T} B ⊕ 0′ ≡_{T} B ⊕ Z – and the Pseudojump Inversion Theorem – for all reals A ≥_{T} 0′ and every e ∈ ℕ, there is a real B such that A ≡_{T} B ⊕ W_{e}^{B} ≡_{T} B ⊕ 0′. We show that in these theorems, B can be found in some special Π_{1}^{0} subclasses of {0, 1}^{ℕ} but not in others.

Contents

1 Introduction  2
2 The Join Theorem and the Pseudojump Inversion Theorem  5
3 Completions of Peano Arithmetic  7
4 Turing degree isomorphism  10
5 Π_{1}^{0} classes of positive measure  12
6 Π_{1}^{0} classes constructed by priority arguments  13

1 Introduction

We begin with a well-known theorem.

Theorem 1.1 (Jump Inversion Theorem, due to Friedberg, see [11, Theorem 13.3.IX]). Given a real A ≥_{T} 0′ we can find a real B such that A ≡_{T} B′ ≡_{T} B ⊕ 0′.

Here 0′ denotes the Halting Problem, B′ denotes the Turing jump of B, and ≡_{T} denotes Turing equivalence. There are two important related theorems, which read as follows.

Theorem 1.2 (Join Theorem, due to Posner and Robinson [10, Theorem 1], see also [3, Theorem 2.1]). Given reals A and Z such that A ≥_{T} Z ⊕ 0′ and Z >_{T} 0, we can find a real B such that A ≡_{T} B′ ≡_{T} B ⊕ 0′ ≡_{T} B ⊕ Z.

Theorem 1.3 (Pseudojump Inversion Theorem, due to Jockusch and Shore [3, Theorem 2.1]). Given a real A ≥_{T} 0′ and an integer e ∈ ℕ, we can find a real B such that A ≡_{T} J_{e}(B) ≡_{T} B ⊕ 0′.

Here J_{e} denotes the eth pseudojump operator, defined by J_{e}(B) = B ⊕ W_{e}^{B} where ⟨W_{e}^{B} | e ∈ ℕ⟩ is a fixed standard recursive enumeration of the B-recursively enumerable subsets of ℕ.

Our results in this paper concern special Π_{1}^{0} classes. Following [4] we define a special Π_{1}^{0} class to be a nonempty Π_{1}^{0} subset of ℕ^{ℕ} with no recursive elements. Here ℕ^{ℕ} is the Baire space, but as in [4, 5] we focus on special Π_{1}^{0} subclasses of {0, 1}^{ℕ}, the Cantor space. On the other hand, because of [13, Theorem 4.10] our results concerning special Π_{1}^{0} subclasses of {0, 1}^{ℕ} will also apply to recursively bounded special Π_{1}^{0} subclasses of ℕ^{ℕ}. Following [5] we use “r. b.” as an abbreviation for “recursively bounded.”

We now recall another known theorem, which says that we can find the B for Theorem 1.1 in any special Π_{1}^{0} subclass of the Cantor space.

Theorem 1.4 (due to Jockusch and Soare [5, just after the proof of Theorem 2.1]). Let P be a special Π_{1}^{0} subclass of {0, 1}^{ℕ}. Given a real A ≥_{T} 0′, we can find a real B ∈ P such that A ≡_{T} B′ ≡_{T} B ⊕ 0′.

This refinement of Theorem 1.1 suggests a question as to the existence or nonexistence of analogous refinements of Theorems 1.2 and 1.3. In order to state our results concerning this question, we make the following definition.

Definition 1.5. Let P ⊆ ℕ^{ℕ} be a subclass of the Baire space.

1. P has the Join Property if for all reals A and Z such that A ≥_{T} Z ⊕ 0′ and Z >_{T} 0, there exists B ∈ P such that A ≡_{T} B′ ≡_{T} B ⊕ 0′ ≡_{T} B ⊕ Z.

2. P has the Pseudojump Inversion Property if for all reals A ≥_{T} 0′ and all e ∈ ℕ, there exists B ∈ P such that A ≡_{T} J_{e}(B) ≡_{T} B ⊕ 0′.

The question that we are asking is, which special Π_{1}^{0} subclasses of the Cantor space {0, 1}^{ℕ} have one or both of the properties in Definition 1.5? The purpose of this paper is to present some partial results in this direction, as follows. Let CPA be the special Π_{1}^{0} subclass of {0, 1}^{ℕ} consisting of all complete, consistent extensions of Peano Arithmetic. We show that CPA has both the Join Property and the Pseudojump Inversion Property. More generally, we show that any special Π_{1}^{0} class which is Turing degree isomorphic to CPA has both of these properties. For example, this holds for the Π_{1}^{0} class CZF consisting of all complete, consistent extensions of Zermelo-Fraenkel Set Theory (assuming that CZF is nonempty), and for the Π_{1}^{0} class DNR_{2} consisting of all {0, 1}-valued diagonally nonrecursive functions. On the other hand, let P be a special Π_{1}^{0} subclass of {0, 1}^{ℕ} which is of positive measure. Citing a theorem of Nies and an observation of Patrick Lutz, we note that P need not have the Join Property, but P and indeed any special Π_{1}^{0} class which is Turing degree isomorphic to P has the Pseudojump Inversion Property. Finally, we construct a special Π_{1}^{0} subclass of {0, 1}^{ℕ} which has neither the Join Property nor the Pseudojump Inversion Property. We do not know whether there exists a special Π_{1}^{0} subclass of {0, 1}^{ℕ} which has the Join Property but not the Pseudojump Inversion Property.

Here is an outline of the paper. In §2 we present the classical proofs of Theorems 1.2 and 1.3. In §3 we use the Gödel-Rosser Incompleteness Theorem [8] to prove that CPA has the Join Property and the Pseudojump Inversion Property. In §4 we present some results about Turing degree isomorphism of Π_{1}^{0} classes, and we apply these results to show that any Π_{1}^{0} class which is Turing degree isomorphic to CPA has the Join Property and the Pseudojump Inversion Property. In §5 we show that special Π_{1}^{0} classes consisting of Martin-Löf random reals have the Pseudojump Inversion Property but not the Join Property. In §6 we use a priority argument to construct a special Π_{1}^{0} subclass Q ⊆ {0, 1}^{ℕ} which has neither the Join Property nor the Pseudojump Inversion Property.

Remark 1.6. The lattice E_{w} of all Muchnik degrees of nonempty Π_{1}^{0} subclasses of {0, 1}^{ℕ} is of great interest; see for instance the references in [19]. Therefore, it is natural to ask about Muchnik degrees in E_{w} corresponding to the properties in Definition 1.5. Our results in this paper shed some light on this question. First, it is known [13, Theorem 6.8] that any Π_{1}^{0} subclass of {0, 1}^{ℕ} which is Muchnik equivalent to CPA – i.e., of Muchnik degree 1, where 1 denotes the top degree in E_{w} – is Turing degree isomorphic to CPA. Therefore, our results in §4 below imply that all Π_{1}^{0} classes of Muchnik degree 1 have both of the properties in Definition 1.5. Second, it is easy to see that each degree in E_{w} contains a Π_{1}^{0} subclass of {0, 1}^{ℕ} which includes CPA and hence again has both properties. On the other hand, by §5 below we have a nonzero degree r ∈ E_{w} containing a special Π_{1}^{0} subclass of {0, 1}^{ℕ} which has one property but not the other. Moreover, in §6 below we construct a nonzero degree in E_{w} containing a special Π_{1}^{0} subclass of {0, 1}^{ℕ} which does not have either property.

In the remainder of this section, we fix some notation and terminology. We write f : ⊆A → B to mean that f is a partial function from A to B,

i.e., a function with domain ⊆ A and range ⊆ B. For a ∈ A we write f(a)↓ and say that f(a) converges or f(a) is defined, if a ∈ the domain of f. Otherwise we write f(a)↑ and say that f(a) diverges or f(a) is undefined. For a ∈ A and f, g : ⊆A → B, we write f(a) ≃ g(a) to mean that either (f(a)↓ and g(a)↓ and f(a) = g(a)) or (f(a)↑ and g(a)↑). We write f(a)↓ = b to mean that f(a)↓ and f(a) = b.

The set of all natural numbers is ℕ = {0, 1, 2, …}. For any set A let A^{ℕ} denote the set of all sequences X : ℕ → A. Thus ℕ^{ℕ} and {0, 1}^{ℕ} are the Baire space and the Cantor space respectively. The points X ∈ ℕ^{ℕ} or X ∈ {0, 1}^{ℕ} are sometimes called reals. We sometimes identify {0, 1}^{ℕ} with the powerset of ℕ in the usual manner. For X, Y ∈ A^{ℕ} the join X ⊕ Y ∈ A^{ℕ} is given by (X ⊕ Y)(2n) = X(n), (X ⊕ Y)(2n + 1) = Y (n), and for P, Q ⊆ A^{ℕ} we write P × Q = {X ⊕ Y | X ∈ P and Y ∈ Q}. Note in particular that P × Q ⊆ ℕ^{ℕ} whenever P, Q ⊆ ℕ^{ℕ}, and P × Q ⊆ {0, 1}^{ℕ} whenever P, Q ⊆ {0, 1}^{ℕ}.

For any set A let A^{∗} be the set of strings, i.e., finite sequences, of elements of A. For a_{0}, …, a_{m−1} ∈ A we let ⟨a_{0}, …, a_{m−1}⟩ denote the string σ ∈ A^{∗} of length m given by σ(i) = a_{i} for all i < m. In this case we write |σ| = m, and for each k ≤ m we write σ↾k = ⟨a_{0}, …, a_{k−1}⟩. We also write A^{m} = {σ ∈ A^{∗} | |σ| = m} and A^{≥m} = {σ ∈ A^{∗} | |σ| ≥ m} and A^{<m} = {σ ∈ A^{∗} | |σ| < m}. For strings σ = ⟨a_{0}, …, a_{m−1}⟩ and τ = ⟨b_{0}, …, b_{n−1}⟩, their concatenation is σ^{⌢}τ = ⟨a_{0}, …, a_{m−1}, b_{0}, …, b_{n−1}⟩. Note that |σ^{⌢}τ| = |σ| + |τ|. We say that σ is an initial segment of τ, or equivalently τ is an extension of σ, written σ ⊆ τ, if τ↾|σ| = σ, i.e., if τ = σ^{⌢}ρ for some string ρ. We write σ ⊂ τ to mean that σ ⊆ τ and σ ≠ τ. We say that σ ∈ A^{∗} is an initial segment of X ∈ A^{ℕ}, or equivalently X is an extension of σ, written σ ⊂ X, if X↾|σ| = σ, i.e., if σ = ⟨X(0), …, X(|σ| − 1)⟩.

Fix a standard recursive enumeration ⟨φ_{e}^{(k)} | e ∈ ℕ⟩ of the k-place partial recursive functions ψ : ⊆ℕ^{k} → ℕ. Here e is called an index of φ_{e}^{(k)}. Likewise, for X ∈ ℕ^{ℕ} we have a standard recursive enumeration ⟨φ_{e}^{(k),X} | e ∈ ℕ⟩ of the k-place partial functions ψ : ⊆ℕ^{k} → ℕ which are partial recursive relative to X. Here e is again called an index of φ_{e}^{(k),X}, while X is called an oracle. We write W_{e}^{X} = {i ∈ ℕ | φ_{e}^{(1),X}(i)↓} and this gives a standard recursive enumeration of the subsets of ℕ which are recursively enumerable relative to X. We also write P_{e} = {X ∈ ℕ^{ℕ} | φ_{e}^{(1),X}(0)↑} and this gives a standard recursive enumeration of the Π_{1}^{0} subclasses of ℕ^{ℕ}.

For X ∈ ℕ^{ℕ} let X′ ∈ ℕ^{ℕ} denote the Turing jump of X. For definiteness we take X′ to be (the characteristic function of) the set

{e ∈ ℕ | 0 ∈ W_{e}^{X}} = {e ∈ ℕ | X ∉ P_{e}}.

For each e ∈ ℕ we have a pseudojump operator J_{e} : ℕ^{ℕ} → ℕ^{ℕ} given by J_{e}(X) = X ⊕ W_{e}^{X}. We write ≤_{T} for Turing reducibility and ≡_{T} for Turing equivalence. We write ≤_{tt} for truth-table reducibility^{1} and ≡_{tt} for truth-table equivalence.

2 The Join Theorem and the Pseudojump Inversion Theorem

In this section we present the classical proofs of the Join Theorem and the Pseudojump Inversion Theorem. Later we shall build on these proofs in order to obtain our refinements.

We begin with the Join Theorem, Theorem 1.2.

Proof of Theorem 1.2. Let A and Z be reals such that A ≥_{T} Z ⊕0′ and Z >_{T} 0. It will suffice to find a real B such that A ≡_{T} B′ ≡_{T} B ⊕ 0′ ≡_{T} B ⊕ Z. We shall construct a sequence of strings σ_{0} ⊂ σ_{1} ⊂ ⋯ ⊂ σ_{j} ⊂ σ_{j+1} ⊂ ⋯ in ℕ^{∗}, and the desired real B ∈ ℕ^{ℕ} will be obtained as the limit ⋃_{j} σ_{j} of this sequence.

Let us regard Z as a subset of ℕ. Since Z is not recursive, at least one of Z and its complement ℕ \ Z is not Σ_{1}^{0}. And then, since Z is Turing equivalent to ℕ \ Z, we may safely assume that ℕ \ Z is not Σ_{1}^{0}.

Stage j = 0. Let σ_{0} = ⟨⟩.

Stage j = 2n + 1. By induction we have σ_{2n}. Define

S_{n} = \{i ∈ ℕ | ∃σ (σ ⊇ σ_{2n}^{⌢}⟨\underbrace{0, …, 0}_{i}, 1⟩ and φ_{n,|σ|}^{(1),σ}(0) ↓)\}

which is Σ_{1}^{0}. Since ℕ \ Z is not Σ_{1}^{0}, there are infinitely many i such that i ∈ Z ⇔ i ∈ S_{n}. Choose the first such i, and use this i to define σ_{2n+1} as follows. If i ∈ Z, then i ∈ S_{n} so let σ_{2n+1} = the least σ ⊇ σ_{2n}^{⌢}⟨\underbrace{0, …, 0}_{i}, 1⟩ such

that φ_{n,|σ|}^{(1),σ}(0) ↓. If i ∉ Z, let σ_{2n+1} = σ_{2n}^{⌢}⟨\underbrace{0, …, 0}_{i}, 1⟩.

Stage j = 2n + 2. Let σ_{2n+2} = σ_{2n}^{⌢}⟨A(n)⟩.

This completes the definition of σ_{j} for all j ∈ ℕ. We now show that B = ⋃_{j} σ_{j} has the desired properties. We begin with the following observations.

1See for instance [11, §§8.3,9.6] and [13, §§4,5].

• If σ_{2n} is known, then the i in stage 2n + 1 can be found recursively in Z ⊕ 0′ (because S_{n} is computable from 0′), or recursively in B (because there is exactly one i such that σ_{2n}^{⌢}⟨\underbrace{0, …, 0}_{i}, 1⟩ ⊂ B). And then, using

this i, σ_{2n+1} can be found recursively in Z (to test whether i ∈ Z), or recursively in 0′ (to test whether i ∈ S_{n}).

• If σ_{2n+1} is known, then σ_{2n+2} can be found recursively in A (by the definition of σ_{2n+2}), or recursively in B (because σ_{2n+2} = σ_{2n+1}^{⌢}⟨B(|σ_{2n+1}|⟩), hence also recursively in B ⊕ Z or in B ⊕ 0′.

Combining these observations, we see that the entire sequence ⟨σ_{j} | j ∈ ℕ⟩ is ≤_{T} B ⊕ Z, and ≤_{T} B ⊕ 0′, and ≤_{T} A (using the hypothesis Z ⊕ 0′ ≤_{T} A). We also have:

• B ⊕ Z ≤_{T} A, because B = ⋃_{j} σ_{j} ≤_{T} A and by hypothesis Z ≤_{T} A.

• B′ ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩, because n ∈ B′ ⇔ φ_{n,|σ_{2n+1}|}^{(1),σ_{2n+1}}(0) ↓.

• A ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩, because A(n) = σ_{2n+2}(|σ_{2n+1}|) for all n.

Thus A ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩ ≤_{T} B ⊕ Z ≤_{T} A, and B′ ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩ ≤_{T} B ⊕ 0′ ≤_{T} B′, hence A ≡_{T} B′ ≡_{T} B ⊕ 0′ ≡_{T} B ⊕ Z, Q.E.D.

We now turn to Pseudojump Inversion, Theorem 1.3.

Proof of Theorem 1.3. Fix e ∈ ℕ, and let A be a real such that A ≥_{T} 0′. It will suffice to find a real B such that A ≡_{T} J_{e}(B) ≡_{T} B ⊕ 0′. We shall construct a sequence of strings σ_{0} ⊆ σ_{1} ⊆ ⋯ ⊆ σ_{j} ⊆ σ_{j+1} ⊆ ⋯ in ℕ^{∗}, and the desired real B ∈ ℕ^{ℕ} will be obtained as the limit ⋃_{j} σ_{j} of this sequence.

Stage 0. Let σ_{0} = ⟨⟩.

Stage 2n + 1. Let σ_{2n+1} = the least string σ ⊇ σ_{2n} for which n ∈ W_{e,|σ|}^{σ} if such a σ exists. Otherwise let σ_{2n+1} = σ_{2n}.

Stage 2n + 2. Let σ_{2n+2} = σ_{2n+1}^{⌢}⟨A(n)⟩.

We now show that B = ⋃_{j} σ_{j} has the desired properties. We begin with the following observations.

• If σ_{2n} is known, then in stage 2n + 1 the question of whether σ exists can be answered recursively in 0′ (because the question is Σ_{1}^{0}), or recursively in J_{e}(B) (because σ exists if and only if n ∈ W_{e}^{B}), hence also recursively in A (because by hypothesis 0′ ≤_{T} A), or recursively in B ⊕0′. And once the existence or nonexistence of σ is known, σ_{2n+1} can be found recursively.

• If σ_{2n+1} is known, then σ_{2n+2} can be found recursively in A (by the definition of σ_{2n+2}), or recursively in B (because σ_{2n+2} = σ_{2n+1}^{⌢}⟨B(|σ_{2n+1}|⟩), hence also recursively in J_{e}(B) (because B ≤_{T} J_{e}(B)), or in B ⊕ 0′.

Combining these observations, we see that the entire sequence ⟨σ_{j} | j ∈ ℕ⟩ is ≤_{T} J_{e}(B), and ≤_{T} B ⊕ 0′, and ≤_{T} A. We also have:

• B ⊕ 0′ ≤_{T} A, because B = ⋃_{j} σ_{j} ≤_{T} A and by hypothesis 0′ ≤_{T} A.

• J_{e}(B) ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩, because n ∈ W_{e}^{B} if and only if n ∈ W_{e,|σ_{2n+1}|}^{σ_{2n+1}}.

• A ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩, because A(n) = σ_{2n+2}(|σ_{2n+1}|) for all n.

Thus A ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩ ≤_{T} B ⊕ 0′ ≤_{T} A and J_{e}(B) ≤_{T} ⟨σ_{j} | j ∈ ℕ⟩ ≤_{T} J_{e}(B), hence A ≡_{T} J_{e}(B) ≡_{T} B ⊕ 0′, Q.E.D.

3 Completions of Peano Arithmetic

Let PA denote Peano Arithmetic, and let Sent_{PA} denote the set of sentences of the language of PA. An extension of PA is a set T ⊆ Sent_{PA} which includes the axioms of PA and is closed under logical consequence. For any such T, a completion of T is an extension X of PA which includes T and such that for each φ ∈ Sent_{PA} exactly one of the sentences φ and ¬ φ belongs to X. Given an extension T of PA, let Comp_{T} denote the set of all completions of T. By Lindenbaum’s Lemma, Comp_{T} ≠ ∅ if and only if T is consistent.

Fix a primitive recursive Gödel numbering # : φ ↦ #(φ) : Sent_{PA} → ℕ. For convenience we shall assume that # is a one-to-one correspondence between Sent_{PA} and ℕ. This induces a one-to-one correspondence between subsets X of Sent_{PA} and subsets of ℕ, namely X ↦ {#(φ) | φ ∈ X}. And of course subsets of ℕ are identified with their characteristic functions in {0, 1}^{ℕ}. Therefore, letting CPA be the subset of {0, 1}^{ℕ} corresponding to Comp_{PA}, we see that CPA is a special Π_{1}^{0} subclass of {0, 1}^{ℕ}.

The purpose of this section is to prove that CPA has the Join Property and the Pseudojump Inversion Property. The Join Property will follow easily from Theorem 1.2 plus other known results, but for the Pseudojump Inversion Property we shall use a construction involving the Gödel-Rosser Incompleteness Theorem [8].

Definition 3.1 (PA-degrees). By a PA-degree we mean the Turing degree deg_{T}(X) of some X ∈ CPA. A set S of Turing degrees is said to be upwardly closed if for all Turing degrees a and b such that a ≤ b, a ∈ S implies b ∈ S.

Lemma 3.2. The set of all PA-degrees is upwardly closed.

Proof. This result is originally due to Robert M. Solovay. For a proof see [2, Theorem 2.21.3] or [13, Corollary 6.6].

Lemma 3.3. Let P ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class such that {deg_{T}(X) | X ∈ P } is upwardly closed. Then P has the Join Property.

Proof. Let A and Z be reals such that A ≥_{T} Z ⊕ 0′ and Z >_{T} 0. By Theorem 1.2 there exists a real C such that A ≡_{T} C′ ≡_{T} C ⊕ 0′ ≡_{T} C ⊕ Z. By the Low Basis Theorem [5, Theorem 2.1] relativized to C, there exists B_{0} ∈ P such that C′ ≡_{T} (B_{0} ⊕ C)′ ≡_{T} B_{0} ⊕ C ⊕ 0′. Since B_{0} ≤_{T} B_{0} ⊕ C, we can find B ∈ P such that B ≡_{T} B_{0} ⊕ C, hence C′ ≡_{T} B′ ≡_{T} B ⊕ 0′. We now have C′ ≡_{T} C ⊕Z ≤_{T} B ⊕Z ≤_{T} C′ ⊕Z ≡_{T} C′, hence A ≡_{T} C′ ≡_{T} B′ ≡_{T} B ⊕0′ ≡_{T} B ⊕Z, Q.E.D.

Theorem 3.4. CPA has the Join Property.

Proof. This is immediate from Lemmas 3.2 and 3.3.

Next we shall prove that CPA has the Pseudojump Inversion Property. The proof will be presented in terms of completions of recursively axiomatizable theories. An extension T of PA is said to be recursively axiomatizable if there is a recursive set of sentences S ⊆ Sent_{PA} such that T is the closure of S under logical consequence. In this case Comp_{T} is clearly a Π_{1}^{0} subclass of CPA. The converse also holds:

Lemma 3.5. We have an effective one-to-one correspondence T ↦ Comp_{T} between recursively axiomatizable extensions of PA and Π_{1}^{0} subclasses of CPA.

Proof. Given a Π_{1}^{0} class P ⊆ CPA, we shall exhibit a recursively axiomatizable extension T of PA such that Comp_{T} = P. Namely, let T = {φ ∈ Sent_{PA} | X(#(φ)) = 1 for all X ∈ P }. To see that T is closed under logical consequence, it suffices to note that each X ∈ P belongs to CPA and is therefore closed under logical consequence. We also have PA ⊆ T, because P ⊆ CPA. Moreover Comp_{T} = P by Lindenbaum’s Lemma. From the effective compactness of P we see that T is recursively enumerable. Hence T is recursively axiomatizable, and from an index of P as a Π_{1}^{0} class we can compute an index for a recursive axiomatization of T. This completes the proof.

Remark 3.6. The idea of Lemma 3.5 applies much more generally. Given any language L and any L-theory T, an extension of T is any set T̃ ⊆ Sent_{L} which includes T and is closed under logical consequence. Regarding Comp_{T} as a closed set in the product space {0, 1}^{Sent^{L}}, we have a one-to-one correspondence T̃ ↦ CompT̃ between extensions of T and closed subsets of Comp_{T}.

Recall from §1 that ⟨P_{i} | i ∈ ℕ⟩ is a fixed standard recursive enumeration of the Π_{1}^{0} subclasses of {0, 1}^{ℕ}.

Lemma 3.7 (splitting property). There is a primitive recursive function s : ℕ × {0, 1} → ℕ such that for all i ∈ ℕ, if P_{i} is a nonempty Π_{1}^{0} subclass of CPA then P_{s(i,0)} and P_{s(i,1)} are nonempty disjoint Π_{1}^{0} subclasses of P_{i}.

Proof. Lemma 3.5 tell us that, given i ∈ ℕ, we can effectively find a recursively axiomatizable extension T of PA such that Comp_{T} corresponds to P_{i} ∩ CPA. We then apply the Gödel-Rosser Incompleteness Theorem [8] to effectively find a sentence ψ ∈ Sent_{PA} such that if T is consistent, then neither ψ nor ¬ ψ belongs to T. Let T_{1} (respectively T_{0}) be the closure of T ∪ {ψ} (respectively T ∪{¬ ψ}) under logical consequence. Clearly Comp_{T_{1}} and Comp_{T_{0}} are disjoint, and they are nonempty if Comp_{T} is nonempty. Apply Lemma 3.5 to effectively find s(i, 1), s(i, 0) ∈ ℕ such that P_{s(i,1)} and P_{s(i,0)} correspond to Comp_{T_{1}} and Comp_{T_{0}} respectively. This completes the proof.

We shall now use this splitting property to redo Theorem 1.3 within CPA.

Theorem 3.8. CPA has the Pseudojump Inversion Property.

Proof. Fix e ∈ ℕ, and let A ∈ {0, 1}^{ℕ} be a real such that A ≥_{T} 0′. It will suffice to find a real B ∈ CPA such that A ≡_{T} J_{e}(B) ≡_{T} B ⊕ 0′. To find B, we shall construct a sequence of Π_{1}^{0} classes Q_{0} ⊇ Q_{1} ⊇ ⋯ ⊇ Q_{j} ⊇ Q_{j+1} ⊇ ⋯, by induction on j starting with Q_{0} = CPA ⊆ {0, 1}^{ℕ}. The intersection ⋂_{j} Q_{j} will be nonempty, and we shall have B ∈ ⋂_{j} Q_{j}. At the same time, we shall construct a function f : ℕ → ℕ such that Q_{j} = P_{f(j)} for all j.

Fix a primitive recursive splitting function s as in Lemma 3.7.

Stage 0. Fix f(0) ∈ ℕ such that P_{f(0)} = Q_{0} = CPA.

Stage 2n + 1. By induction we have Q_{2n} = P_{f(2n)}. If P_{f(2n)} ∩ {X | n ∉ J_{e}(X)} = ∅ let Q_{2n+1} = P_{f(2n)} and f(2n + 1) = f(2n). Otherwise, let Q_{2n+1} = P_{f(2n)} ∩ {X | n ∉ J_{e}(X)} and choose f(2n + 1) so that P_{f(2n+1)} = P_{f(2n)} ∩ {X | n ∉ J_{e}(X)}. This f(2n + 1) is found primitive recursively from f(2n) and n and e.

Stage 2n + 2. By induction we have Q_{2n+1} = P_{f(2n+1)}. Let f(2n + 2) = s(f(2n + 1), A(n)) and Q_{2n+2} = P_{s(f(2n+1),A(n))}, where s is our splitting function. This f(2n + 2) is found primitive recursively from f(2n + 1) and A(n).

This completes the construction.

By construction each Q_{j} is nonempty, so by compactness of {0, 1}^{ℕ} their intersection ⋂_{j} Q_{j} is nonempty. It remains to show that B ∈ ⋂_{j} Q_{j} has the desired properties. We begin with the following observations.

• If f(2n) is known then f(2n+1) can be found recursively in 0′ (by checking whether the Π_{1}^{0} class P_{f(2n)} ∩ {X | n ∉ J_{e}(X)} is empty or not), or recursively in J_{e}(B) (by checking whether n ∈ J_{e}(B) or not).

• If f(2n + 1) is known then f(2n + 2) can be found recursively in B (by finding the k ∈ {0, 1} such that B ∉ P_{s(f(2n+1),k)}), or recursively in A (by evaluating s(f(2n + 1), A(n))).

Combining these observations, we see that f is ≤_{T} A ⊕ 0′ ≡_{T} A, and ≤_{T} J_{e}(B), and ≤_{T} B ⊕ 0′. Conversely, we also have:

• A ≤_{T} f, because A(n) = i if and only if f(2n + 2) = s(f(2n + 1), i).

• J_{e}(B) ≤_{T} f, because n ∈ J_{e}(B) if and only if f(2n + 1) = f(2n).

• B ⊕ 0′ ≤_{T} f, because B ≤_{T} J_{e}(B) ≤_{T} f and 0′ ≤_{T} A ≤_{T} f.

Thus f ≡_{T} A ≡_{T} J_{e}(B) ≡_{T} B ⊕ 0′ and the proof is complete.

Remark 3.9. We have used the Splitting Lemma 3.7 to prove that CPA has the Pseudojump Inversion Property. Similarly, it would be possible to use the Splittng Lemma to prove directly that CPA has the Join Property. This direct proof would be in contrast to our shorter but indirect proof in Theorem 3.4 above. Note however that a version of the Splitting Lemma is used in our proof of Solovay’s Lemma 3.2; see [13, §6] and [14, §3].

4 Turing degree isomorphism

Definition 4.1 (Turing degree isomorphism). Following [4] we say that P, Q ⊆ ℕ^{ℕ} are Turing degree isomorphic if {deg_{T}(X) | X ∈ P } = {deg_{T}(X) | X ∈ Q}.

The purpose of this section is to prove that the Join Property and the Pseudojump Inversion Property hold for all Π_{1}^{0} subclasses of {0, 1}^{ℕ} which are Turing degree isomorphic to CPA. We also obtain some more general-looking results.

We begin with the Join Property.

Theorem 4.2. Let P ⊆ {0, 1}^{ℕ} be a Π_{1}^{0} class. If P is Turing degree isomorphic to CPA, then P has the Join Property.

Proof. Let A and Z be reals such that A ≥_{T} Z ⊕ 0′ and Z >_{T} 0. By Theorem 3.4 let B ∈ CPA be such that A ≡_{T} B′ ≡_{T} B ⊕ 0′ ≡_{T} B ⊕ Z. Since P is Turing degree isomorphic to CPA, let C ∈ P be such that B ≡_{T} C. Then A′ ≡_{T} C′ ≡_{T} C ⊕ 0′ ≡_{T} C ⊕ Z. Thus P has the Join Property, Q.E.D.

Remark 4.3. More generally, for P, Q ⊆ ℕ^{ℕ} we say that P is Turing degree embeddable into Q if {deg_{T}(X) | X ∈ P } ⊆ {deg_{T}(X) | X ∈ Q}. The proof of Theorem 4.2 shows that if P has the Join Property and is Turing degree embeddable into Q, then Q has the Join Property.

We now turn to Pseudojump Inversion. Unfortunately, we cannot simply imitate the proof of Theorem 4.2. This is because pseudojump operators are not invariant under Turing equivalence, i.e., X ≡_{T} Y typically does not imply J_{e}(X) ≡_{T} J_{e}(Y). Consequently, we do not know whether the Pseudojump Inversion Property is invariant under Turing degree isomorphism of special Π_{1}^{0} subclasses of {0, 1}^{ℕ}. However, we shall settle some interesting special cases of this question. As a first step, consider the following notion, which is a special case of Turing degree isomorphism.

Definition 4.4 (recursive homeomorphism). For P, Q ⊆ ℕ^{ℕ}, a recursive homeomorphism of P onto Q is a one-to-one onto mapping Φ : P → Q such that both Φ and its inverse Φ^{−1} : Q → P are the restrictions of partial recursive functionals to P and Q respectively. We say that P and Q are recursively homeomorphic if there exists a recursive homeomorphism of P onto Q.

Lemma 4.5. Let P, Q ⊆ ℕ^{ℕ} be recursively homeomorphic. If P has the Pseudojump Inversion Property, then so does Q.

Proof. Assume that P has the Pseudojump Inversion Property. We shall prove that Q has the Pseudojump Inversion Property. Given e ∈ ℕ and A ≥_{T} 0′, it will suffice to find C ∈ Q such that A ≡_{T} J_{e}(C) ≡_{T} C ⊕ 0′.

Let Φ : P → Q be a recursive homeomorphism. Let i ∈ ℕ be such that for all X ∈ P and all n ∈ ℕ we have φ_{i}^{X}(n) ≃ φ_{e}^{Φ(X)}(n). Then for all X ∈ P we have W_{i}^{X} = {n ∈ ℕ | φ_{i}^{X}(n) ↓} = {n ∈ ℕ | φ_{e}^{Φ(X)}(n) ↓} = W_{e}^{Φ(X)}. Since P has the Pseudojump Inversion Property, let B ∈ P such that A ≡_{T} J_{i}(B) ≡_{T} B⊕0′. Let C = Φ(B). Because Φ is a recursive homeomorphism, we have B ≡_{T} Φ(B) = C, hence J_{e}(C) = C ⊕ W_{e}^{C} = C ⊕ W_{e}^{Φ(B)} = C ⊕ W_{i}^{B} ≡_{T} B ⊕ W_{i}^{B} = J_{i}(B), hence A ≡_{T} J_{e}(C) ≡_{T} C ⊕ 0′, Q.E.D.

As a bridge from Turing degree isomorphism to recursive homeomorphism, we have the following lemma.

Lemma 4.6. Let P, Q ⊆ {0, 1}^{ℕ} be nonempty Π_{1}^{0} classes. If P is Turing degree embeddable into Q, then there exist nonempty Π_{1}^{0} subclasses P̃ ⊆ P and Q̃ ⊆ Q such that P̃ and Q̃ are recursively homeomorphic.

Proof. We shall draw on some facts about hyperimmune-freeness and truth-table reducibility. For this background, see [11, §§8.3,9.6] and [13, §4].

By the Hyperimmune-Free Basis Theorem [5, Theorem 2.4] (see also [13, Theorem 4.19]), let X_{0} ∈ P be hyperimmune-free. Since P is Turing degree embeddable into Q, let Y_{0} ∈ Q be such that X_{0} ≡_{T} Y_{0}. Then Y_{0} is also hyperimmune-free, and by hyperimmune-freeness there exist truth-table functionals Φ, Ψ : {0, 1}^{ℕ} → {0, 1}^{ℕ} such that Φ(X_{0}) = Y_{0} and Ψ(Y_{0}) = X_{0}. Let P̃ = {X ∈ P | Φ(X) ∈ Q and Ψ(Φ(X)) = X}. Then P̃ is a Π_{1}^{0} subclass of P, and it is nonempty because it contains X_{0}. Moreover Q̃ = {Φ(X) | X ∈ P̃} is also a Π_{1}^{0} subclasss of Q, and we have a recursive homeomorphism Φ↾P̃ of P̃ onto Q̃.

Lemma 4.7. Any nonempty Π_{1}^{0} subclass of CPA is recursively homeomorphic to CPA.

Proof. See [14, §3].

We can now prove the following theorem, which is parallel to Theorem 4.2.

Theorem 4.8. Let P ⊆ {0, 1}^{ℕ} be a Π_{1}^{0} class. If P is Turing degree isomorphic to CPA, then P has the Pseudojump Inversion Property.

Proof. Let P be Turing degree isomorphic to CPA. By Lemma 4.6 there are nonempty recursively homeomorphic Π_{1}^{0} classes P̃ ⊆ P and { \atop CPA} ⊆ CPA. By Lemma 4.7 { \atop CPA} is recursively homeomorphic to CPA. By Theorem 3.8 CPA has the Pseudojump Inversion Property, so by Lemma 4.5 { \atop CPA} and hence P̃ have the Pseudojump Inversion Property. But then, since P̃ ⊆ P, it follows that P has the Pseudojump Inversion Property, Q.E.D.

Next we prove a more general-looking result. Recall from [13, 16, 17, 18, 19] that a nonempty Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} is said to be Muchnik complete if every nonempty Π_{1}^{0} class Q ⊆ {0, 1}^{ℕ} is Muchnik reducible to P, i.e., for all X ∈ P there exists Y ∈ Q such that Y ≤_{T} X.

Lemma 4.9. A Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} is Muchnik complete if and only if it is Turing degree isomorphic to CPA. Moreover, for such a P the set of Turing degrees {deg_{T} (X) | X ∈ P } is upwardly closed.

Proof. See [13, §§3,6].

Theorem 4.10. Let P ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class. If P is Muchnik complete, then P has the Join Property and the Pseudojump Inversion Property.

Proof. This is immediate from Lemma 4.9 and Theorems 4.2 and 4.8.

An even more general-looking result reads as follows.

Theorem 4.11. Let P ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class such that {deg_{T} (Y) | Y ∈ P } is upwardly closed. Then any P_{1} ⊆ ℕ^{ℕ} which includes P has the Join Property and the Pseudojump Inversion Property.

Proof. By Lemma 4.9 CPA is Turing degree embeddable into P. Our result then follows by Remark 4.3 and Theorems 4.2 and 4.8.

5 Π_{1}^{0} classes of positive measure

For σ ∈ {0, 1}^{∗} we write ⟦σ⟧ = {X ∈ {0, 1}^{ℕ} | σ ⊂ X}. Let μ be the fair coin measure on {0, 1}^{ℕ}, defined by letting μ(⟦σ⟧) = 2^{−|σ|} for all σ ∈ {0, 1}^{∗}. This μ is a Borel probability measure on {0, 1}^{ℕ}. A Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} is said to be of positive measure if μ(P) > 0. In this section we note that such a P must have the Pseudojump Inversion Property but need not have the Join Property. We also obtain the same results for Π_{1}^{0} subclasses of {0, 1}^{ℕ} which are Turing degree isomorphic to such a P.

To prove these results we need some basic facts about Martin-Löf randomness and LR-reducibility. We cite our semi-expository papers [13, 15, 17, 18] but one can also consult the treatises of Downey and Hirschfeldt [2] and Nies [9]. Let MLR = {X ∈ {0, 1}^{ℕ} | X is Martin-Löf random}.

Lemma 5.1. A Π_{1}^{0} subclass of {0, 1}^{ℕ} is of positive measure if and only if it includes a nonempty Π_{1}^{0} subclass of MLR.

Proof. This is because MLR ⊆ {0, 1}^{ℕ} is a Σ_{2}^{0} class of full measure. See for instance [13, §8].

Lemma 5.2 (due to Nies [9]). Let P ⊆ {0, 1}^{ℕ} be a Π_{1}^{0} class of positive measure. Then P has the Pseudojump Inversion Property.

Proof. See [9, Theorem 6.3.9] or a simpler proof in [15, Theorem 5.1].

Theorem 5.3. Let P ⊆ {0, 1}^{ℕ} be a Π_{1}^{0} class of positive measure, and let Q ⊆ {0, 1}^{ℕ} be a Π_{1}^{0} class which is Turing degree isomorphic to P. Then Q has the Pseudojump Inversion Property.

Proof. By Lemma 5.1 let P_{0} be a nonempty Π_{1}^{0} subclass of P ∩ MLR. Then P_{0} is Turing degree embeddable in Q, so by Lemma 4.6 we can find nonempty Π_{1}^{0} classes P̃ ⊆ P_{0} and Q̃ ⊆ Q which are recursively homeomorphic. By Lemma 5.1 P̃ is of positive measure, so by Lemma 5.2 P̃ has the Pseudojump Inversion Property. It then follows by Lemma 4.5 that Q̃ and hence Q have the Pseudojump Inversion Property.

Relativizing the notion of Martin-Löf randomness, for any real Y we write MLR^{Y} = {X ∈ {0, 1}^{ℕ} | X is Martin-Löf random relative to Y }. If MLR^{Y} ⊆ MLR^{Z} we say that Z is LR-reducible to Y, abbreviated as Z ≤_{LR} Y. Intuitively this means that Y has at least as much “derandomizing power” as Z. Clearly Z ≤_{T} Y implies Z ≤_{LR} Y, but the converse does not hold:

Lemma 5.4. There exists a nonrecursive real Z such that Z ≤_{LR} 0.

Proof. See [15, Theorem 6.1] or [2, 9].

On the other hand, we have:

Lemma 5.5. If Z ≤_{LR} Y then Z′ ≤_{T} Z ⊕ Y′.

Proof. See [15, Theorem 8.8] or [2, 9].

Lemma 5.6 (Lutz [6]). If Z ≤_{LR} 0 then X ⊕ Z ≤_{LR} X for all X ∈ MLR.

Proof. Assume Z ≤_{LR} 0 and X ∈ MLR. We must prove that MLR^{X} ⊆ MLR^{X⊕Z}. Given X_{1} ∈ MLR^{X}, it follows by Van Lambalgen’s Theorem ([15, Theorem 3.6], see also [2, Corollary 6.9.3]) that X_{1} ⊕ X ∈ MLR. But then X_{1} ⊕ X ∈ MLR^{Z}, so by Van Lambalgen’s Theorem relative to Z we have X_{1} ∈ MLR^{X⊕Z}, Q.E.D.

Theorem 5.7 (Lutz [6]). MLR does not have the Join Property.

Proof. By Lemma 5.4 let Z >_{T} 0 be such that Z ≤_{LR} 0. For any X ∈ MLR we have X ⊕ Z ≤_{LR} X by Lemma 5.6, hence (X ⊕ Z)′ ≤_{T} X′ ⊕ Z by Lemma 5.5. If MLR had the Join Property, there would be an X ∈ MLR such that X′ ≡_{T} X ⊕ Z, hence (X ⊕ Z)′ ≤_{T} X ⊕ Z, a contradiction.

Theorem 5.8 (Lutz [6]). There is a Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} of positive measure which does not have the Join Property.

Proof. This is immediate from Theorem 5.7 and Lemma 5.1.

6 Π_{1}^{0} classes constructed by priority arguments

In this section we construct a special Π_{1}^{0} class Q ⊆ {0, 1}^{ℕ} which has neither the Join Property nor the Pseudojump Inversion Property. In addition, this Π_{1}^{0} class Q has some other interesting features, which we also discuss.

We begin by stating a technical theorem which embodies our construction of Q. Recall from §1 that ⟨P_{e}⟩_{e∈ℕ} is a fixed enumeration of all Π_{1}^{0} classes.

Theorem 6.1. There is a nonempty perfect^{2} Π_{1}^{0} class Q ⊆ {0, 1}^{ℕ} with the following properties. For all e, n ∈ ℕ there exists m ∈ ℕ such that for all pairwise distinct τ_{1}, …, τ_{n} ∈ {0, 1}^{∗} with |τ_{1}| = ⋯ = |τ_{n}| ≥ m, the Π_{1}^{0} class

2A topological space is said to be perfect if it has no isolated points, i.e., there is no open set consisting of exactly one point. In particular, a set P ⊆ {0, 1}^{ℕ} is perfect if and only if there is no τ ∈ {0, 1}^{∗} such that P ∩ ⟦τ⟧ = {X} for some X ∈ {0, 1}^{ℕ}.

(Q ∩ ⟦τ_{1}⟧) × ⋯ × (Q ∩ ⟦τ_{n}⟧)

is either disjoint from P_{e} or included in P_{e}. Moreover, this m can be computed from e using an oracle for 0′.

Before proving Theorem 6.1, we spell out some of its consequences which are of more general interest. The next theorem summarizes these features of Q.

Theorem 6.2. Let Q ⊆ {0, 1}^{ℕ} be a nonempty Π_{1}^{0} class as in Theorem 6.1.

1. Q is thin, i.e., for every Π_{1}^{0} subclass P of Q, the complement Q\P is again a Π_{1}^{0} subclass of Q. More generally, for any finite sequence Q_{1}, …, Q_{n} of pairwise disjoint^{3} Π_{1}^{0} subclasses of Q, the Π_{1}^{0} class Q_{1} × ⋯ × Q_{n} is thin.

2. Q is special, i.e., no X ∈ Q is recursive. More generally, the Turing degrees of members of Q are independent, i.e., no X ∈ Q is ≤_{T} the join of any finitely many other members of Q.

3. Every X ∈ Q is of minimal truth-table degree. Consequently, every hyperimmune-free X ∈ Q is of minimal Turing degree.

4. Every finite sequence X_{1}, …, X_{n} ∈ Q is generalized low, i.e., (X_{1} ⊕ ⋯ ⊕ X_{n})′ ≡_{T} X_{1} ⊕ ⋯ ⊕ X_{n} ⊕ 0′.

Proof. We prove parts 1 through 4 in that order.

1. To see that Q is thin, let P be a Π_{1}^{0} subclass of Q. Fix e ∈ ℕ such that P = P_{e}, and let m be as in Theorem 6.1. Then for each τ ∈ {0, 1}^{m} the Π_{1}^{0} class Q ∩ ⟦τ⟧ is either disjoint from P or included in P. Hence Q \ P = ⋃_{τ} (Q ∩ ⟦τ⟧) where the union is taken over all τ ∈ {0, 1}^{m} such that Q ∩ ⟦τ⟧ is disjoint from P. Thus Q \ P is is a union of finitely many Π_{1}^{0} classes, so it too is a Π_{1}^{0} class.

For the generalization, let P be a Π_{1}^{0} subclass of Q_{1} × ⋯ × Q_{n} where Q_{1}, …, Q_{n} are pairwise disjoint Π_{1}^{0} subclasses of Q. Fix e ∈ ℕ such that P = P_{e}, and let m be as in Theorem 6.1. We then have

(Q_{1} × ⋯ × Q_{n}) \ P = ⋃_{τ_{1},...,τ_{n}}((Q_{1} ∩ ⟦τ_{1}⟧) × ⋯ × (Q_{n} ∩ ⟦τ_{n}⟧))

where the union is taken over all pairwise distinct sequences τ_{1}, …, τ_{n} ∈ {0, 1}^{m} such that (Q_{1}∩⟦τ_{1}⟧)×⋯×(Q_{n}∩⟦τ_{n}⟧) is disjoint from P. Thus (Q_{1}×⋯×Q_{n})\P is a union of finitely many Π_{1}^{0} classes, so it too is a Π_{1}^{0} class, Q.E.D.

2. Assume for a contradiction that X ∈ Q is recursive. Fix e ∈ ℕ such that P_{e} = {X}, let m ∈ ℕ be as in Theorem 6.1, and let τ = X↾m. Clearly X ∈ Q ∩ ⟦τ⟧, hence Q ∩ ⟦τ⟧ is not disjoint from P_{e}, hence Q ∩ ⟦τ⟧ is included in P_{e}, hence X is the unique member of Q ∩ ⟦τ⟧. Thus X is an isolated point of Q, contradicting the fact that Q is perfect.

For the generalization, it will suffice to show that X ≰_{T} X_{1} ⊕⋯⊕X_{n} for all pairwise distinct X, X_{1}, …, X_{n} ∈ Q. Let Ψ : ⊆{0, 1}^{ℕ} → {0, 1}^{ℕ} be a partial recursive functional, and assume for a contradiction that X = Ψ(X_{1} ⊕⋯⊕X_{n}). Let e ∈ ℕ be such that P_{e} = {Y ⊕ Y_{1} ⊕ ⋯ ⊕ Y_{n} | ∀i ∀j (if Ψ(Y_{1} ⊕ ⋯ ⊕ Y_{n})(i)↓ = j then Y (i) = j)}.

3The hypothesis of pairwise disjointness is essential. For instance, if P = {X ⊕X | X ∈ Q} then (Q × Q) \ P is not Π_{1}^{0}, so Q × Q is not thin.

Let m be as in Theorem 6.1 and sufficiently large so that τ = X↾m, τ_{1} = X_{1}↾m, …, τ_{n} = X_{n}↾m are pairwise distinct. The Π_{1}^{0} class

(Q ∩ ⟦τ⟧) × (Q ∩ ⟦τ_{1}⟧) × ⋯ × (Q ∩ ⟦τ_{n}⟧)

contains X ⊕ X_{1} ⊕ ⋯ ⊕ X_{n} and is therefore not disjoint from P_{e}, so it is included in P_{e}. In particular, for all Y ∈ Q ∩ ⟦τ⟧ and all i ∈ ℕ we have Ψ(X_{1} ⊕ ⋯ ⊕ X_{n})(i)↓ = X(i) = Y (i), hence X = Y. Thus Q ∩ ⟦τ⟧ = {X}, so again X is an isolated point of Q, contradicting the fact that Q is perfect.

3. Let X ∈ Q be given. We have already seen that X is not recursive. To prove that X is of miminal truth-table degree, it remains to show that X ≤_{tt} Ψ(X) for any truth-table functional Ψ such that Ψ(X) is not recursive. Given such a functional Ψ, let e be such that

P_{e} = {X_{0} ⊕ X_{1} ∈ Q × Q | Ψ(X_{0}) = Ψ(X_{1})}.

By Theorem 6.1 let m be such that for all τ ∈ {0, 1}^{≥m} the Π_{1}^{0} class (Q ∩ ⟦τ^{⌢}⟨0⟩⟧) × (Q ∩ ⟦τ^{⌢}⟨1⟩⟧) is either disjoint from P_{e} or included in P_{e}. If it is disjoint from P_{e}, let us say that τ is splitting.

Case 1: For all sufficiently large τ ⊂ X, τ is splitting. Then for all sufficiently large τ ⊂ X and all X_{0} ∈ Q ∩ ⟦τ^{⌢}⟨0⟩⟧ and X_{1} ∈ Q ∩ ⟦τ^{⌢}⟨1⟩⟧, we have Ψ(X_{0}) ≠ Ψ(X_{1}). In particular we have Ψ(X) ≠ Ψ(Y) for all Y ∈ Q ∩ ⟦τ⟧ such that X ≠ Y. From this it follows that X is truth-table reducible to Ψ(X).

Case 2: There are arbitrarily large τ ⊂ X such that τ is not splitting. Let τ ⊂ X be non-splitting with |τ| ≥ m. Then Q ∩ ⟦τ^{⌢}⟨0⟩⟧ and Q ∩ ⟦τ^{⌢}⟨1⟩⟧ are nonempty, and for all X_{0} ∈ Q ∩ ⟦τ^{⌢}⟨0⟩⟧ and X_{1} ∈ Q ∩ ⟦τ^{⌢}⟨1⟩⟧ we have Ψ(X_{0}) = Ψ(X_{1}). In particular, letting i, j ∈ {0, 1} be such that X ∈ Q∩⟦τ^{⌢}⟨i⟩⟧ and i + j = 1, we have Ψ(X) = Ψ(Y) for all Y ∈ Q ∩ ⟦τ^{⌢}⟨j⟩⟧. From this it follows that Ψ(X) is recursive, Q.E.D.

A general property of hyperimmune-free reals X is that the Turing degrees ≤ deg_{T}(X) are the same as the truth-table degrees ≤ deg_{tt}(X). Since every X ∈ Q is of minimal truth-table degree, it follows that every hyperimmune-free X ∈ Q is of minimal Turing degree.

4. Up until now we have not used the “moreover” clause of Theorem 6.1, but now we shall use it. We may safely assume that X_{1}, …, X_{n} ∈ Q are pairwise distinct. Recall that we have defined the Turing jump X′ ∈ {0, 1}^{ℕ} of X ∈ {0, 1}^{ℕ} to be (the characteristic function of) the set {e ∈ ℕ | X ∉ P_{e}}. To compute (X_{1} ⊕ ⋯ ⊕ X_{n})′ we proceed as follows. First we use our oracle for X_{1} ⊕ ⋯ ⊕ X_{n} to find l ∈ ℕ such that X_{1}↾l, …, X_{n}↾l are pairwise distinct. Then, given e ∈ ℕ, we use our oracle for 0′ to compute m ≥ l as in Theorem 6.1. Letting τ_{i} = X_{i}↾m for i = 1, …, n, we know that the Π_{1}^{0} class (Q ∩ ⟦τ_{1}⟧) × ⋯ × (Q ∩ ⟦τ_{n}⟧) is either disjoint from P_{e} or included in P_{e}. Using our oracle for 0′ again, we can decide whether this Π_{1}^{0} class is disjoint from P_{e} or not. The answer to this question tells us whether e ∈ (X_{1} ⊕ ⋯ ⊕ X_{n})′ or not. Thus (X_{1} ⊕ ⋯ ⊕ X_{n})′ is computable from X_{1} ⊕ ⋯ ⊕ X_{n} ⊕ 0′, Q.E.D.

Remark 6.3. A plausible generalization of part 3 of Theorem 6.2 would say that for every pairwise distinct finite sequence X_{1}, …, X_{n} ∈ Q, the tt-degrees ≤ deg_{tt}(X_{1} ⊕ ⋯ ⊕ X_{n}) should form a lattice isomorphic to the powerset of {1, …, n}. From this it would follow that the same holds for Turing degrees, provided X_{1} ⊕ ⋯ ⊕ X_{n} is hyperimmune-free.

Theorem 6.4. The special Π_{1}^{0} class Q ⊆ {0, 1}^{ℕ} of Theorem 6.1 has neither the Join Property nor the Pseudojump Inversion Property.

Proof. We rely mainly on part 4 of Theorem 6.2. To see that the Join Property fails for Q, fix Z ∈ Q. Then Z >_{T} 0 but for all B ∈ Q we have (B ⊕ Z)′ ≡_{T} B ⊕ Z ⊕ 0′, hence 0′ ≰_{T} B ⊕ Z. To see that Pseudojump Inversion fails for Q, consider a pseudojump operator J_{e} with the property^{4} that X <_{T} J_{e}(X) and (J_{e}(X))′ ≡_{T} X′ for all X ∈ ℕ^{ℕ}. Then for all B ∈ Q we have (J_{e}(B))′ ≡_{T} B′ ≡_{T} B ⊕ 0′, hence 0′ ≰_{T} J_{e}(B).

The rest of this section is devoted to the proof of Theorem 6.1. We use a priority construction in the vein of Martin/Pour-El [7] and Jockusch/Soare [5, Theorem 4.7].

Our construction will be presented in terms of treemaps. A treemap is a mapping T : {0, 1}^{∗} → {0, 1}^{∗} such that T (σ^{⌢}⟨i⟩) ⊇ T (σ)^{⌢}⟨i⟩ for all σ ∈ {0, 1}^{∗} and all i ∈ {0, 1}. Note that for any treemap T and σ, ρ ∈ {0, 1}^{∗} we have σ ⊂ ρ if and only if T (σ) ⊂ T (ρ). Note also that there is a one-to-one correspondence between treemaps T and nonempty perfect closed subsets of {0, 1}^{ℕ}, given by T ↦ [T] = {T (X) | X ∈ {0, 1}^{ℕ}} where T (X) = ⋃_{n∈ℕ} T (X↾n).

Recall that any Π_{1}^{0} class P ⊆ {0, 1}^{ℕ} is closed. Therefore, if P is also nonempty and perfect, there is a unique treemap T_{P} such that P = [T_{P}].

Lemma 6.5. Let P ⊆ {0, 1}^{ℕ} be a nonempty perfect Π_{1}^{0} class. Then, the treemap T = T_{P} corresponding to P is computable using 0′ as an oracle.

Proof. Given τ ∈ {0, 1}^{∗} we can use our oracle for 0′ to decide whether P ∩ ⟦τ⟧ is empty or not. Thus, if already know T (σ) for some σ ∈ {0, 1}^{∗}, we can then compute T (σ^{⌢}⟨i⟩) for i ∈ {0, 1}, because T (σ^{⌢}⟨i⟩) is the smallest τ ⊇ T (σ)^{⌢}⟨i⟩ such that P ∩ ⟦τ^{⌢}⟨j⟩⟧ is nonempty for all j ∈ {0, 1}. Thus T ≤_{T} 0′, Q.E.D.

In our proof of Theorem 6.1, the treemap T = T_{Q} corresponding to Q will be uniform, in the sense that |T (σ)| will depend only on |σ|. This feature of T will be for convenience only, but T will also have another key property, which reads as follows. For all e, l, n ∈ ℕ with e ≤ l and n ≤ 2^{l} and all pairwise distinct σ_{1}, …, σ_{n} ∈ {0, 1}^{l}, either ⟦T (σ_{1})⟧ × ⋯ × ⟦T (σ_{n})⟧ ∩ P_{e} = ∅ or (Q ∩ ⟦T (σ_{1})⟧) × ⋯ × (Q ∩ ⟦T (σ_{n})⟧) ⊆ P_{e}. Thus by Lemma 6.5 the “moreover” clause of Theorem 6.1 will hold with m = m_{e} = |T (σ)| for all σ ∈ {0, 1}^{e}.

4The existence of such pseudojump operators is well known [20, §VII.1]. One way to obtain such an operator is to combine part 4 of Theorem 6.2 with the R. E. Basis Theorem [4, Theorem 3] to get an e ∈ ℕ such that 0 <_{T} W_{e} and (W_{e})′ ≡_{T} 0′. The desired operator J_{e} is then obtained by uniform relativization to an arbitrary Turing oracle X.

Proof of Theorem 6.1. We shall construct T = T_{Q} as the limit T = lim_{s} T_{s} of a recursive sequence of recursive uniform treemaps T_{s}, s ∈ ℕ. This will be a pointwise limit as s → ∞, in the sense that for each σ ∈ {0, 1}^{∗} we shall have T (σ) = T_{s}(σ) for all sufficiently large s. Also, the treemaps T_{s} will be nested, in the sense that for all s ∈ ℕ and all σ ∈ {0, 1}^{∗} there will be a ρ ∈ {0, 1}^{∗} such that T_{s+1}(σ) = T_{s}(ρ). From this it follows that [T_{s+1}] ⊆ [T_{s}] for all s, and that [T] = ⋂_{s}[T_{s}]. Thus Q = [T] will be a nonempty perfect Π_{1}^{0} subclass of {0, 1}^{ℕ}.

In presenting our construction of T = lim_{s} T_{s}, we shall use the notation

P_{e,s} = {X ∈ {0, 1}^{ℕ} | φ_{e,s}^{(1),X↾s}(0) ↑}.

Note that P_{e,s} = ⋃_{τ} ⟦τ⟧ where the union is taken over a finite subset of {0, 1}^{s}. Note also that P_{e,s+1} ⊆ P_{e,s} for all s ∈ ℕ, and that

P_{e} = {X ∈ {0, 1}^{ℕ} | φ_{e}^{(1),X}(0) ↑} = ⋂_{s} P_{e,s}.

We now offer a preliminary account of the construction and proof. To each e, l, n ∈ ℕ with e ≤ l and n ≤ 2^{l} and each pairwise distinct sequence σ_{1}, …, σ_{n} ∈ {0, 1}^{l}, we associate a requirement R(e, σ_{1}, …, σ_{n}) at level l. Intuitively, the purpose of this requirement is to insure that (⟦T (σ_{1})⟧ × ⋯ × ⟦T (σ_{n})⟧) ∩ P_{e} = ∅ “if possible.” The strategy here will be to attempt to arrange that (⟦T_{s}(σ_{1})⟧ × ⋯×⟦T_{s}(σ_{n})⟧)∩P_{e,s} = ∅ for all sufficiently large s, “if possible.” We shall argue that if this attempt fails, then (Q ∩ ⟦T_{s}(σ_{1})⟧) × ⋯ × (Q ∩ ⟦T_{s}(σ_{n})⟧) ⊆ P_{e,s} for all sufficiently large s, hence (Q ∩ ⟦T (σ_{1})⟧) × ⋯ × (Q ∩ ⟦T (σ_{n})⟧) ⊆ P_{e}.

We now give the detailed construction of T_{s} for all s ∈ ℕ. Begin by fixing a recursive linear ordering of all of the requirements, called the priority ordering. Arrange this ordering so that for each l ∈ ℕ, all requirements at level l are of lower priority than all requirements at level < l. The idea here is that requirements at level l can be “injured” by requirements at level < l but will never be “injured” by requirements at level ≥ l. Note that for each l there are only finitely many requirements at level ≤ l. We proceed by induction on s.

Stage 0. Let T_{0}(ν) = ν for all ν ∈ {0, 1}^{∗}. Clearly T_{0} is a uniform treemap. Stage s + 1. Assume inductively that we have defined a uniform treemap T_{s}.

Our task at this stage is to define T_{s+1}. A requirement R(e, σ_{1}, …, σ_{n}) at level l is said to be requesting attention at stage s if (⟦T_{s}(σ_{1})⟧×⋯×⟦T_{s}(σ_{n})⟧)∩P_{e,s} ≠ ∅ but there exist k ≤ s and ρ_{1}, …, ρ_{n} ∈ {0, 1}^{k} such that ρ_{i} ⊃ σ_{i} for all i = 1, …, n and (⟦T_{s}(ρ_{1})⟧ × ⋯ × ⟦T_{s}(ρ_{n})⟧) ∩ P_{e,s} = ∅. If no requirements are requesting attention, do nothing, i.e., let T_{s+1}(ν) = T_{s}(ν) for all ν ∈ {0, 1}^{∗}. Otherwise, let R_{s} be the requirement of highest priority which is requesting attention. For this requirement only, choose k > l ≥ e and ρ_{1}, …, ρ_{n} as above and define T_{s+1} as follows. For each ν ∈ {0, 1}^{<l} let T_{s+1}(ν) = T_{s}(ν). For each i = 1, …, n let T_{s+1}(σ_{i}) = T_{s}(ρ_{i}). For each σ ∈ {0, 1}^{l} other than σ_{1}, …, σ_{n},

let T_{s+1}(σ) = T_{s}(σ^{⌢}⟨\underbrace{0, …, 0}_{k−l}⟩). For each σ ∈ \{0, 1\}^{l} and each ν ∈ \{0, 1\}^{∗}, let

T_{s+1}(σ^{⌢}ν) = T_{s}(ρ^{⌢}ν) where ρ is such that T_{s+1}(σ) = T_{s}(ρ). Clearly T_{s+1} is a treemap, and it is uniform because T_{s} is uniform and for each σ ∈ {0, 1}^{l} we have T_{s+1}(σ) = T_{s}(ρ) for some ρ ∈ {0, 1}^{k}.

We now have a recursive nested sequence of uniform treemaps T_{s}. As s goes to infinity, consider the history of a single requirement R = R(e, σ_{1}, …, σ_{n}) at level l. Let us say that R is satisfied at stage s if (⟦T_{s}(σ_{1})⟧ × ⋯ × ⟦T_{s}(σ_{n})⟧) ∩ P_{e,s} = ∅, otherwise unsatisfied at stage s. By construction, if R = R_{s} then R is unsatisfied at stage s but becomes satisfied at stage s + 1. And if R is satisfied at stage s, it remains satisfied at stage s + 1 unless R_{s} is at level < l. Let us say that R is injured at stage s if the latter case holds, i.e., if the level of R_{s} is less than the level of R. By induction along the priority ordering, we now see that there are only finitely many stages s at which R is injured, and only finitely many stages s at which R requests attention. This holds for all of the finitely many requirements at level ≤ l, so for all σ ∈ {0, 1}^{l} and all sufficiently large s we have T_{s+1}(σ) = T_{s}(σ). We now have a uniform treemap T defined by T (σ) = lim_{s} T_{s}(σ), so letting Q = [T] = ⋂_{s}[T_{s}] we have a nonempty perfect Π_{1}^{0} class Q ⊆ {0, 1}^{ℕ}.

We claim that for each requirement R at level l as above, either (⟦T (σ_{1})⟧ × ⋯ × ⟦T (σ_{n})⟧) ∩ P_{e} = ∅ or (Q ∩ ⟦T (σ_{1})⟧) × ⋯ × (Q ∩ ⟦T (σ_{n})⟧) ⊆ P_{e}. Suppose not. Then (⟦T (σ_{1})⟧ × ⋯ × ⟦T (σ_{n})⟧) ∩ P_{e} ≠ ∅ and

((Q ∩ ⟦T (σ_{1})⟧) × ⋯ × (Q ∩ ⟦T (σ_{n})⟧)) \ P_{e} ≠ ∅.

For i = 1, …, n fix X_{i} ∈ Q∩⟦T (σ_{i})⟧ so that X_{1}⊕⋯⊕X_{n} ∉ P_{e}. Let m be so large that (⟦X_{1}↾m⟧×⋯×⟦X_{n}↾m⟧)∩P_{e} = ∅. Let k > l and ρ_{1}, …, ρ_{n} ∈ {0, 1}^{k} be such that T (ρ_{i}) ⊂ X_{i} and |T (ρ_{i})| ≥ m for all i = 1, …, n. Thus we have ρ_{i} ⊃ σ_{i} for all i = 1, …, n, and (⟦T (ρ_{1})⟧×⋯×⟦T (ρ_{n})⟧)∩P_{e} = ∅. It follows by compactness that for all sufficiently large s we have (⟦T (ρ_{1})⟧ × ⋯ × ⟦T (ρ_{n})⟧) ∩ P_{e,s} = ∅. And we can also let s be so large that e ≤ l < k ≤ s and T_{s}(σ_{i}) = T (σ_{i}) and T_{s}(ρ_{i}) = T (ρ_{i}) for all i = 1, …, n. So now we see that (⟦T_{s}(σ_{1})⟧×⋯×⟦T_{s}(σ_{n})⟧)∩P_{e,s} ≠ ∅ and (⟦T_{s}(ρ_{1})⟧ × ⋯ × ⟦T_{s}(ρ_{n})⟧) ∩ P_{e,s} = ∅ for all suffiently large s. Thus our requirement R is requesting attention at all sufficiently large stages s. This contradiction proves our claim.

The above claim gives us the principal conclusion of Theorem 6.1. And then, as we have seen, Lemma 6.5 gives us the “moreover” clause with m = m_{e}. The proof of Theorem 6.1 is now complete.

References

[1] A. Beckmann, V. Mitrana, and M. Soskova, editors. Evolving Computability, Proceedings of CiE 2015 (Bucharest). Number 9136 in Lecture Notes in Computer Science. Springer, 2015. XV + 363 pages. 19

[2] Rodney G. Downey and Denis R. Hirschfeldt. Algorithmic Randomness and Complexity. Theory and Applications of Computability. Springer, 2010. XXVIII + 855 pages. 7, 12, 13

[3] Carl G. Jockusch, Jr. and Richard A. Shore. Pseudo-jump operators I: the r.e. case. Transactions of the American Mathematical Society, 275(2):599– 609, 1983. 2 [4] Carl G. Jockusch, Jr. and Robert I. Soare. Degrees of members of Π_{1}^{0}

classes. Pacific Journal of Mathematics, 40:605–616, 1972. 2, 10, 16

[5] Carl G. Jockusch, Jr. and Robert I. Soare. Π_{1}^{0} classes and degrees of theories. Transactions of the American Mathematical Society, 173:35–56, 1972. 2, 3, 7, 11, 16

[6] Patrick Lutz. Private communication, August 9 2019. 13

[7] Donald A. Martin and Marian B. Pour-El. Axiomatizable theories with few axiomatizable extensions. Journal of Symbolic Logic, 35:205–209, 1970. 16

[8] Elliott Mendelson. Introduction to Mathematical Logic. Wadsworth, 3rd edition, 1987. IX + 341 pages. 3, 7, 8

[9] André Nies. Computability and Randomness. Oxford University Press, 2009. XV + 433 pages. 12, 13

[10] David B. Posner and Robert W. Robinson. Degrees joining to 0′. Journal of Symbolic Logic, 46:714–722, 1981. 2

[11] Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. XIX + 482 pages. 2, 5, 11

[12] S. G. Simpson, editor. Reverse Mathematics 2001. Number 21 in Lecture Notes in Logic. Association for Symbolic Logic, 2005. X + 401 pages. 19

[13] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11(1):1–27, 2005. 2, 4, 5, 7, 9, 11, 12

[14] Stephen G. Simpson. Π_{1}^{0} sets and models of WKL_{0}. In [12], pages 352–378, 2005. 9, 11

[15] Stephen G. Simpson. Almost everywhere domination and superhighness. Mathematical Logic Quarterly, 53(4–5):462–482, 2007. 12, 13

[16] Stephen G. Simpson. An extension of the recursively enumerable Turing degrees. Journal of the London Mathematical Society, 75(2):287–297, 2007. 11

[17] Stephen G. Simpson. Mass problems and almost everywhere domination. Mathematical Logic Quarterly, 53:483–492, 2007. 11, 12

[18] Stephen G. Simpson. Mass problems and measure-theoretic regularity. Bulletin of Symbolic Logic, 15:385–409, 2009. 11, 12

[19] Stephen G. Simpson. Degrees of unsolvability: a tutorial. In [1], pages 83–94, 2015. 3, 11

[20] Robert I. Soare. Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag, 1987. XVIII + 437 pages. 16