Mass Problems

Stephen G. Simpson Department of Mathematics Pennsylvania State University

        http://www.math.psu.edu/simpson/

May 24, 2004

Abstract

A mass problem is a set of Turing oracles. If P and Q are mass problems, we say that P is weakly reducible to Q if every member of Q Turing computes a member of P. Two mass problems are said to be weakly equivalent if each is weakly reducible to the other. A weak degree is an equivalence class under weak reducibility. The weak degrees are partially ordered in the obvious way, by weak reducibility. This partial ordering is easily seen to be a complete distributive lattice. We focus on the countable sublattice obtained by restricting to mass problems of the form P = the set of all paths through T, where T is an infinite computable subtree of the full binary tree. We present natural examples of such mass problems arising from mathematical logic, Martin-Löf randomness, effective immunity, and the Arslanov Completeness Criterion. We also present artificial examples constructed by means of priority arguments.

This is the lecture notes that I prepared for my series of five lectures at the Summer School and Workshop on Proof Theory, Computation and Complexity, held at the Technical University of Dresden, June 23–July 4, 2003. See

    http://www.ki.inf.tu-dresden.de/~guglielm/WPT2/.

Contents

Abstract 1 Contents 2 1 Turing Degrees 2 2 Weak and Strong Degrees 5 3 Trees and Π_{1}^{0} Sets 8 4 Weak and Strong Completeness 12 5 1-Randomness 14 6 The Almost Recursive Basis Theorem 16 7 The Σ_{3}^{0} → Π_{1}^{0} Embedding Theorem 17 8 Embedding the R. E. Turing Degrees 18 9 A Priority Argument 19 References 21

1 Turing Degrees

Definition 1.1. We use ω to denote the set of natural numbers:

ω = {0, 1, 2, …}.

We use ω^{ω} to denote the set of total functions from ω into ω:

ω^{ω} = {f | f : ω → ω}.

We use 2^{ω} to denote the set of total functions from ω into {0, 1}:

2^{ω} = {X | X : ω → {0, 1}}.

The space ω^{ω} with the obvious product topology is called Baire space. Its subspace 2^{ω} is called Cantor space. We use f, g, h, … to denote points of the Baire space, and X, Y, Z, … to denote points of the Cantor space. Remark 1.2. We sometimes identify subsets of ω with their characteristic functions in 2^{ω}. The characteristic function of A ⊆ ω is χ_{A} ∈ 2^{ω} given by

χ_{A}(n) = \{ \begin{matrix}1 if n ∈ A, \\ 0 if n ∉ A. \end{matrix}

Definition 1.3. For e, m, n ∈ ω and g ∈ ω^{ω}, we write

{e}^{g}(m) = n

to mean that e is the Gödel number of a Turing machine which, if started with input m (on the input tape) and oracle g (on the auxiliary or oracle tape), eventually halts with output n (on the output tape).

Remark 1.4. The idea of using an arbitrary, possibly non-computable member of ω^{ω} as an oracle is due to Turing [44]. See also Rogers [30, Section 9.2].

Definition 1.5. According to Definition 1.3, each e ∈ ω gives rise to a partial recursive functional Φ from ω^{ω} × ω to ω, given by Φ(g, m) ≃ {e}^{g}(m). We may also view Φ as a partial recursive functional from ω^{ω} to ω^{ω}, given by Φ(g)(m) ≃ Φ(g, m) ≃ {e}^{g}(m). In either case we say that e is an index of Φ.

Remark 1.6. Here ≃ denotes strong equality for expressions which may be undefined. Thus E_{1} ≃ E_{2} if and only if E_{1}, E_{2} are both undefined, or both defined and equal. We write E ↓ to mean that E is defined. We write E ↑ to mean that E is undefined.

Definition 1.7. For f, g ∈ ω^{ω}, we say that g Turing computes f, or f is recursive in g, or f is Turing reducible to g, abbreviated f ≤_{T} g, if Φ(g) = f for some partial recursive functional Φ. Thus f ≤_{T} g if and only if there exists e ∈ ω such that {e}^{g}(m) = f(m) for all m ∈ ω. Clearly ≤_{T} is a reflexive, transitive relation on ω^{ω}.

We say that f is Turing equivalent to g, abbreviated f ≡_{T} g, if f ≤_{T} g and g ≤_{T} f. Clearly ≡_{T} is an equivalence relation on ω^{ω}.

Definition 1.8. The Turing degrees, or degrees of unsolvability, are the equivalence classes of members of ω^{ω} under the equivalence relation ≡_{T}. The Turing degree of f ∈ ω^{ω} is denoted deg_{T} (f). We use D_{T} to denote the set of Turing degrees. Thus we have

deg_{T} (f) = {g ∈ ω^{ω} | f ≡_{T} g}

and

D_{T} = ω^{ω}/≡_{T} = {deg_{T} (f) | f ∈ ω^{ω}}.

Definition 1.9. In Definition 1.3, if there is no oracle g, we write simply

{e}(m) = n.

Thus f ∈ ω^{ω} is said to be Turing computable, or recursive, if there exists e ∈ ω such that {e}(m) = f(m) for all m ∈ ω.

Remark 1.10. We partially order D_{T} by putting deg_{T} (f) ≤ deg_{T} (g) if and only if f ≤_{T} g. Under this partial ordering, D_{T} is an upper semilattice, with least upper bound operation given by f ⊕ g ∈ ω^{ω}, where

(f ⊕ g)(2n) = f(n), (f ⊕ g)(2n + 1) = g(n),

for all f, g ∈ ω^{ω}. Moreover D_{T} has a bottom element

0 = deg_{T} (λn.0) = {f ∈ ω^{ω} | f is recursive}.

It can be shown that D_{T} has no top element and is not a lattice.

We now compare the Baire space, ω^{ω}, to the Cantor space, 2^{ω}.

Theorem 1.11. For each f ∈ ω^{ω} there exists X ∈ 2^{ω} such that f ≡_{T} X.

Proof. Let X be the characteristic function of {2^{m}3^{n} | f(m) = n}.

Remark 1.12. In view of Theorem 1.11, the Baire space ω^{ω} and the Cantor space 2^{ω} are identical as to Turing degrees. Thus we may write

D_{T} = 2^{ω}/≡_{T} = {deg_{T} (X) | X ∈ 2^{ω}}.

Remark 1.13. The idea behind Turing reducibility is that each non-recursive (i.e., non-computable) X ∈ 2^{ω} is regarded as an “unsolvable problem”, viz., the problem of computing X. Then Y ≤_{T} X means that “the problem” Y is “reducible” to “the problem” X in the sense that, if there were an oracle for solving X, then, with the help of this oracle, we could solve Y. Thus deg_{T} (X), the Turing degree of X, is a measure of the “unsolvability” of “the problem” X. In particular, the Turing degree 0 corresponds to “solvable problems”, i.e., recursive members of 2^{ω}.

Example 1.14. Turing’s original example of an unsolvable problem is the Halting Problem, i.e., the (characteristic function of the) set

H = {e ∈ ω | {e}(0) ↓}

= {Gödel numbers of Turing machines which eventually halt}.

The Turing degree of the Halting Problem is denoted 0′. Turing’s famous theorem on unsolvability of the Halting Problem amounts to saying that H is nonrecursive, i.e., 0′ > 0.

In addition, it is known that there are infinitely many Turing degrees a in the interval 0 ≤ a ≤ 0′. Moreover, the Turing degrees in this interval do not form a lattice.

Definition 1.15. A set A ⊆ ω is said to be recursively enumerable, abbreviated r. e., if A = {f(m) | m ∈ ω} for some recursive function f : ω → ω. In this case, an index of A is just an index of f. A Turing degree is said to be recursively enumerable if it is the Turing degree of (the characteristic function of) an r. e. subset of ω. The set of r. e. Turing degrees is denoted R_{T}.

Definition 1.16. An r. e. set C ⊆ ω is said to be Turing complete if for every r. e. set A ⊆ ω we have A ≤_{T} C. An r. e. Turing degree is said to be Turing complete if it is the Turing degree of a Turing complete r. e. set.

Remark 1.17. It is known that the halting set H and its Turing degree 0′ are recursively enumerable and Turing complete. Moreover, if a and b are r. e. Turing degrees, then so is their least upper bound, sup(a, b). Thus R_{T} is a countable upper semilattice with a top element, 0′, and a bottom element, 0. It is known that R_{T} is infinite and properly included in the interval 0 ≤ a ≤ 0′ in D_{T}, and is not a lattice.

Remark 1.18. More generally, for any Turing degree a = deg_{T} (X), define a′ = deg_{T} (H^{X}) where H^{X} is (the characteristic function of)

H^{X} = {e | {e}^{X}(0) ↓},

the halting set relative to X. It is known that the Turing jump operator a ↦ a′ is well defined, because X ≤_{T} Y implies H^{X} ≤_{T} H^{Y}. It is known that a′ > a, and that a′ is r. e. relative to a and Turing complete relative to a.

Remark 1.19. The semilattice D_{T} of all Turing degrees, and its subsemilattice R_{T} consisting of the r. e. Turing degrees, have been studied intensively for many years. See Sacks [31], Rogers [30], Lerman [23], Simpson [36] [37], Soare [42].

2 Weak and Strong Degrees

Definition 2.1. A mass problem is a subset of ω^{ω}. We use, P, Q, R, … to denote subsets of ω^{ω}.

Definition 2.2. For P, Q ⊆ ω^{ω}, we say that P is weakly reducible to Q, abbreviated P ≤_{w} Q, if for each g ∈ Q there exists f ∈ P such that f ≤_{T} g. (Recall that ≤_{T} is Turing reducibility.) The notion of weak reducibility was introduced by Muchnik [28] and has sometimes been called Muchnik reducibility. Clearly ≤_{w} is a reflexive, transitive relation on the powerset of ω^{ω}.

Definition 2.3. We say that P, Q ⊆ ω^{ω} are weakly equivalent, or Muchnik equivalent, abbreviated P ≡_{w} Q, if P ≤_{w} Q and Q ≤_{w} P. Clearly ≡_{w} is an equivalence relation on the powerset of ω^{ω}. The equivalence classes are called weak degrees, or Muchnik degrees. The weak degree of P is denoted deg_{w}(P). We use D_{w} to denote the set of weak degrees. Thus we have

deg_{w}(P) = {Q ⊆ ω^{ω} | P ≡_{w} Q}

and

D_{w} = {deg_{w}(P) | P ⊆ ω^{ω}}.

We partially order D_{w} by putting deg_{w}(P) ≤ deg_{w}(Q) if and only if P ≤_{w} Q.

Remark 2.4. The idea behind weak reducibility is that an arbitrary subset of ω^{ω} may be regarded as a “mass problem”, i.e., a problem whose solution is not necessarily unique. If P ⊆ ω^{ω} is viewed a mass problem, the “solutions” of P are just the members of P. A mass problem is regarded as “unsolvable” if it has no recursive solution. Compare Remark 1.13. Viewing P and Q as mass problems, P ≤_{w} Q means that P is “reducible” to Q in the sense that, given any oracle for a solution of Q, we could use this oracle to compute a solution of P. Thus the weak degree of P is a measure of the “difficulty” of P qua mass problem.

Example 2.5. Let T be a consistent, recursively axiomatizable theory. For instance, we may take T = PA = first order Peano Arithmetic, or T = ZF = Zermelo/Fraenkel Set Theory. By a completion of T we mean a maximal consistent theory extending T with the same vocabulary as T. Note that T is incomplete if and only if T has more than one completion. The Gödel Incompleteness Theorem implies that this is the case for T = PA or T = ZF.

We identify sentences with their Gödel numbers in ω. We identify theories as sets of (Gödel numbers of) sentences. Define

P_{T} = {X ∈ 2^{ω} | X is (the characteristic function of) a completion of T }.

We may then view P_{T} as a mass problem, viz., the “problem” of finding a completion of T. The mass problem P_{T} is regarded as “unsolvable” if and only if the theory T has no decidable completion. This is equivalent to saying that T is essentially undecidable, i.e., there is no consistent, decidable theory extending T. By a result of Tarski, this is the case for PA, ZF, and many other theories which arise in the foundations of mathematics.

We now introduce strong reducibility, a variant of weak reducibility.

Definition 2.6. For P, Q ⊆ ω^{ω}, we say that P is strongly reducible to Q, abbreviated P ≤_{s} Q, if there exists a partial recursive functional Φ : Q → P, i.e., a partial recursive functional Φ from ω^{ω} to ω^{ω} such that the domain of definition of Φ includes Q and for all g ∈ Q we have Φ(g) ∈ P. This notion was introduced by Medvedev [27] and has sometimes been called Medvedev reducibility. See also Rogers [30, Section 13.7]. Clearly ≤_{s} is a reflexive, transitive relation on the powerset of ω^{ω}.

Remark 2.7. Thus strong reducibility is a uniform variant of weak reducibility. Note that P ≤_{s} Q implies P ≤_{w} Q, but the converse often fails. Later we shall see an analogy

weak reducibility / strong reducibility =

Turing reducibility / truth table reducibility.

See Remark 3.9 below.

Definition 2.8. We define strong degrees in terms of ≤_{s}, just as weak degrees were defined in terms of ≤_{w} in Definition 2.3.

Explicitly, we say that P, Q ⊆ ω^{ω} are strongly equivalent, or Medvedev equivalent, abbreviated P ≡_{s} Q, if P ≤_{s} Q and Q ≤_{s} P. Clearly ≡_{s} is an equivalence relation on the powerset of ω^{ω}. The equivalence classes are called strong degrees, or Medvedev degrees. The strong degree of P is denoted deg_{s}(P). We use D_{s} to denote the set of strong degrees. Thus we have

deg_{s}(P) = {Q ⊆ ω^{ω} | P ≡_{s} Q}

and

D_{s} = {deg_{s}(P) | P ⊆ ω^{ω}}.

We partially order D_{s} by putting deg_{s}(P) ≤ deg_{s}(Q) if and only if P ≤_{s} Q.

Remark 2.9. We are mainly interested in weak reducibility and weak degrees. We discuss strong reducibility and strong degrees for technical reasons only.

Theorem 2.10. The lattices of weak degrees and strong degrees, D_{w} and D_{s}, are distributive lattices with a bottom element.

Proof. The least upper bound operation for weak or strong reducibility is given by

P × Q = {f ⊕ g | f ∈ P, g ∈ Q}.

The greatest lower bound operation for weak reducibility is given by P ∪Q. The greatest lower bound operation for weak or strong reducibility is given by

P + Q = {⟨0⟩^{⌢}f | f ∈ P } ∪ {⟨1⟩^{⌢}g | g ∈ Q}.

It is straightforward but instructive to check that the weak degrees form a distributive lattice under these operations. Similarly for the strong degrees.

The bottom element of D_{w} is 0 = deg_{w}(ω^{ω}), and similarly for D_{s}. Actually, the 0 of D_{w} and the 0 of D_{s} are identical, namely

0 = {P ⊆ ω^{ω} | P contains a recursive member}.

Theorem 2.11. In both D_{w} and D_{s}, the bottom element 0 is meet irreducible, i.e., it is not the greatest lower bound of two nonzero degrees.

Proof. This is obvious, because P + Q (or P ∪ Q) contains a recursive member if and only if at least one of P and Q contains a recursive member.

Theorem 2.12. D_{T} is canonically embeddable into D_{w} and into D_{s}. The embeddings preserve order and least upper bound, and carry 0 to 0.

Proof. The embedding of D_{T} into D_{w} is given by deg_{T} (X) ↦ deg_{w}({X}), and similarly for D_{s}. Here {X} denotes the singleton set whose unique element is X. We have X ≤_{T} Y if and only if {X} ≤_{w} {Y }, if and only if {X} ≤_{s} {Y }. Moreover, {X} × {Y } = {X ⊕ Y }.

Theorem 2.13. D_{w} is a complete distributive lattice.

Proof. It is straightforward to check that D_{w} under ≤ is canonically isomorphic to the partial ordering of upward closed subsets of D_{T} under reverse inclusion. This is clearly is a complete lattice ordering. The isomorphism is given by deg_{w}(P) ↦ {deg_{T} (g) | P ≤_{w} {g}}.

We now compare the Baire space, ω^{ω}, to the Cantor space, 2^{ω}.

Definition 2.14. P, Q ⊆ ω^{ω} are recursively homeomorphic if there exist oneto-one, onto, partial recursive functionals Φ : P → Q and Φ^{−1} : Q → P.

Theorem 2.15. For each P ⊆ ω^{ω} there exists P^{∗} ⊆ 2^{ω} such that P is recursively homeomorphic to P^{∗}. It follows that P ≡_{s} P^{∗}, hence P ≡_{w} P^{∗}.

Proof. Identifying subsets of ω with their characteristic functions in 2^{ω}, let P^{∗} = {{2^{m}3^{n} | f(m) = n} | f ∈ P }. Compare Theorem 1.11.

Remark 2.16. In view of Theorem 2.15, subsets of 2^{ω} and subsets of ω^{ω} are identical as to their weak and strong degrees. Compare Remark 1.12. Thus we may write

D_{w} = {deg_{w}(P) | P ⊆ 2^{ω}}

and similarly for D_{s}.

Remark 2.17. On the other hand, the spaces 2^{ω} and ω^{ω} are different in some ways. For instance, 2^{ω} is compact while ω^{ω} is not compact. Furthermore, the differences will be important to us. In particular, we shall see that the lattice of weak degrees of nonempty Π_{1}^{0} subsets of 2^{ω} has a top element, but this is not the case for ω^{ω}. See Section 4 below.

Remark 2.18. Our main object of study will be the lattice P_{w} of weak degrees of nonempty Π_{1}^{0} subsets of the Cantor space, 2^{ω}. See Definition 3.7 below. We mention Π_{1}^{0} subsets of ω^{ω} for technical reasons only.

Remark 2.19. Sorbi [43] gives a general survey of the lattices D_{w} and D_{s} of all weak and strong degrees. However, Sorbi does not discuss the sublattices P_{w} and P_{s} of weak and strong degrees of nonempty Π_{1}^{0} subsets of 2^{ω}. The explicit study of P_{w} and P_{s} began only recently, in 1999, with Simpson [38].

3 Trees and Π_{1}^{0} Sets

Definition 3.1. A predicate R ⊆ ω^{ω} × ω is said to be recursive if its characteristic function χ_{R} : ω^{ω} × ω → {0, 1}, given by

χ_{R}(f, n) = \{ \begin{matrix}1 if R(f, n), \\ 0 if ¬ R(f, n), \end{matrix}

is a recursive functional.

Definition 3.2. A set P ⊆ ω^{ω} is said to be Π_{1}^{0} if there is a recursive predicate R ⊆ ω^{ω} × ω such that

P = {f ∈ ω^{ω} | ∀n R(f, n)}.

Example 3.3. Let T be a consistent, recursively axiomatizable theory. As in Example 2.5, let P_{T} be the set of (characteristic functions of) completions of T. It is easy to see that P_{T} is a nonempty Π_{1}^{0} subset of 2^{ω}. Thus weak and strong reducibility can be used to compare such theories.

In more detail, let B(T) be the Lindenbaum algebra of T, i.e., the Boolean algebra of sentences in the vocabulary of T modulo provable equivalence over T. Thus B(T) is a recursively presented Boolean algebra, i.e., the quotient of a free recursive Boolean algebra modulo a recursively enumerable ideal. It can be shown that P_{T} is (recursively homeomorphic to) the Stone space of B(T). Thus we have an effective version of Stone Duality, with nonempty Π_{1}^{0} subsets of 2^{ω} as the Stone spaces. If T_{1} and T_{2} are two such theories, then recursive homomorphisms

h : B(T_{1}) → B(T_{2})

are in canonical one-to-one correspondence with recursive functionals

Φ : P_{T_{2}} → P_{T_{1}}.

In particular, B(T_{1}) is recursively isomorphic to B(T_{2}) if and only if P_{T_{1}} is recursively homeomorphic to P_{T_{2}}.

Remark 3.4. Conversely, one can show that every nonempty Π_{1}^{0} subset of 2^{ω} is recursively homeomorphic to P_{T} for some consistent, recursively axiomatizable theory T. See Theorem 3.18 and Remark 3.19 below.

Remark 3.5. Many other interesting examples of Π_{1}^{0} subsets of 2^{ω} arise from logic, algebra, analysis, geometry, combinatorics, computability theory, etc. There is a large literature on this subject. See for instance Cenzer/Remmel [8] and Simpson [39, Chapter IV and Section VIII.2].

Remark 3.6. If P and Q are Π_{1}^{0} subsets of 2^{ω}, then P × Q, P ∪ Q, P + Q are Π_{1}^{0} subsets of 2^{ω}. Thus the weak degrees of nonempty Π_{1}^{0} subsets of 2^{ω} form a sublattice of the lattice of all weak degrees. Similarly for strong degrees, and similarly for subsets of ω^{ω}.

Definition 3.7. We use P_{w} to denote the set of weak degrees of nonempty Π_{1}^{0} subsets of 2^{ω}. Thus P_{w} is a countable sublattice of D_{w}. Similarly P_{s}, the set of strong degrees of nonempty Π_{1}^{0} subsets of 2^{ω}, is a countable sublattice of D_{s}.

Remark 3.8. The countable distributive lattices P_{w} and P_{s} are known to have a rich structure.

Binns/Simpson [4, 6] have shown that every countable distributive lattice is lattice embeddable in P_{w}. A similar conjecture for P_{s} remains open, although partial results in this direction are known. A special case is Corollary 9.4 below. Binns [4, 5] has shown that for every b > 0 in P_{w} there exist b_{1}, b_{2} < b in P_{w} such that b = sup(b_{1}, b_{2}), and similarly for P_{s}. Cenzer/Hinman [7] have shown that, for all a, b ∈ P_{s} such that a < b, there exists c ∈ P_{s} such that a < c < b. A similar conjecture for P_{w} remains open. Binns [4, 5] has improved the result of Cenzer/Hinman [7] by showing that, for all a, b ∈ P_{s} such that a < b, there exist b_{1}, b_{2} < b in P_{s} such that a < b_{1}, b_{2} and b = sup(b_{1}, b_{2}).

These recent results for P_{w} and P_{s} are proved by means of priority arguments. They invite comparison with the older, known results for r. e. Turing degrees in Sacks [31] and Soare [42].

Remark 3.9. It is known that P_{s} behaves somewhat differently from P_{w}. To bring out one of the differences, let P, Q be Π_{1}^{0} subsets of 2^{ω} with P ≤_{s} Q. Thus we have a recursive functional Φ : Q → P. Using compactness of 2^{ω}, we can find a total recursive functional Φ̂ : 2^{ω} → 2^{ω} which extends Φ, i.e., Φ = the restriction of Φ̂ to Q. Thus, for every Y ∈ Q, Φ(Y) is not only ≤_{T} Y but also ≤_{tt} Y, where ≤_{tt} denotes truth table reducibility. A general discussion of truth table reducibility is in Rogers [30]. See also Simpson [35, Section 3] and the proof of Lemma 6.5 below. Thus we have an analogy

weak reducibility / strong reducibility =

Turing reducibility / truth table reducibility.

In addition, it is known that every nonzero weak degree in P_{w} includes infinitely many distinct strong degrees in P_{s}. See Simpson/Slaman [41].

We now present a useful characterization of Π_{1}^{0} sets, in terms of trees.

Definition 3.10. We use Seq to denote the set of finite sequences of natural numbers. We use ρ, σ, τ, … to denote members of Seq. The length of σ ∈ Seq is denoted lh(σ). The concatenation σ followed by τ is denoted σ^{⌢}τ. Thus lh(σ^{⌢}τ) = lh(σ) + lh(τ). Given f ∈ ω^{ω} and n ∈ ω, we put

f[n] = ⟨f(0), f(1), …, f(n − 1)⟩.

Thus f[n] ∈ Seq and lh(f[n]) = n. We write σ ⊂ f to mean that σ = f[n] for some n. Given τ ∈ Seq and n ≤ lh(τ), we put

τ[n] = ⟨τ(0), τ(1), …, τ(n − 1)⟩.

We write σ ⊆ τ to mean that σ = τ[n] for some n ≤ lh(τ).

Definition 3.11. For e, m, n, t ∈ ω and σ ∈ Seq, we write

{e}_{t}^{σ}(m) = n

to mean that {e}^{f}(m) = n for some (or any) f ∈ ω^{ω} such that f ⊃ σ, via a Turing computation which halts in at most t steps and uses only oracle information from σ. Compare Definition 1.3.

Lemma 3.12. We have:

1. If {e}_{t}^{f[s]}(m) = n and t′ ≥ t and s′ ≥ s, then {e}_{t′}^{f[s′]}(m) = n.

2. {e}^{f}(m) = n if and only if {e}_{t}^{f[s]}(m) = n for some s, t ∈ ω.

3. {e}^{f}(m) = n if and only if {e}_{s}^{f[s]}(m) = n for some s ∈ ω.

4. The relations {e}_{t}^{σ}(m) = n and {e}_{t}^{σ}(m) ↓ are recursive.

Proof. Straightforward.

Definition 3.13. A tree is a set T ⊆ Seq such that, for all τ ∈ T and all n < lh(τ), τ[n] ∈ T. A path through T is a function f ∈ ω^{ω} such that, for all n ∈ ω, f[n] ∈ T.

Theorem 3.14. A set P ⊆ ω^{ω} is Π_{1}^{0} if and only if there exists a recursive tree T ⊆ Seq such that

P = {f ∈ ω^{ω} | f is a path through T }.

Proof. Clearly the set of paths through a recursive tree is Π_{1}^{0}. Conversely, given a Π_{1}^{0} set P = {f | ∀n R(f, n)}, let e be an index of the partial recursive functional Φ(f, m) ≃ least n such that ¬ R(f, n). Then P = {f | Φ(f, 0) ↑} = {f | {e}^{f}(0) ↑}. Putting T = {σ | {e}_{lh(σ)}^{σ}(0) ↑} we see that T is a recursive tree and P = {paths through T }.

Definition 3.15. We use Seq_{2} to denote the set of finite sequences of 0’s and 1’s. Since Seq_{2} ⊆ Seq, the notations introduced in Definitions 3.10 and 3.11 apply.

Definition 3.16. A tree T is said to be bounded if for each n ∈ ω there are only finitely many σ ∈ T such that lh(σ) = n. Note that Seq_{2} is a bounded tree, while Seq is an unbounded tree.

Corollary 3.17. A set P ⊆ 2^{ω} is Π_{1}^{0} if and only if there exists a recursive tree T ⊆ Seq_{2} such that

P = {X ∈ 2^{ω} | X is a path through T }.

Moreover, P is nonempty if and only if T is infinite.

Proof. The first assertion is a special case of Theorem 3.14. The second assertion follows from compactness of 2^{ω}, in the form of König’s Lemma. Namely, a bounded tree has a path if and only if it is infinite.

We now use Corollary 3.17 to obtain the converse of Example 3.3.

Theorem 3.18.

1. If T is a consistent, recursively axiomatizable theory, then P_{T}, the set of completions of T, is a nonempty Π_{1}^{0} subset of 2^{ω}.

2. Conversely, if P is a nonempty Π_{1}^{0} subset of 2^{ω}, we can find a consistent, recursively axiomatizable theory, T, such that P is recursively homeomorphic to P_{T}.

Proof. Part 1 has already been noted in Example 3.3. For part 2, let S be an infinite recursive tree such that P = {paths through S}. We use S to construct a theory T in the propositional calculus with atoms A_{n}, n ∈ ω. Writing A^{1} = A and A^{0} = ¬ A, the axioms of T are all sentences of the form ¬ (A_{0}^{i_{0}} ∧ A_{1}^{i_{1}} ∧ ⋯ ∧ A_{k}^{i_{k}}) where ⟨i_{0}, i_{1}, …, i_{k}⟩ ∈ Seq_{2} \ S. Then P is recursively homeomorphic to P_{T}, via X ↦ the completion of T with axioms A_{n}^{X(n)}, n ∈ ω.

Remark 3.19. Surprisingly, it is known that every Π_{1}^{0} subset of 2^{ω} is recursively homeomorphic to P_{T} for some finitely axiomatizable theory T in the predicate calculus. See Peretyatkin [29].

We now discuss Π_{1}^{0} subsets of ω^{ω} and compare them to Π_{1}^{0} subsets of 2^{ω}.

Definition 3.20. A set P ⊆ ω^{ω} is said to be recursively bounded if there exists a recursive function g ∈ ω^{ω} such that for all f ∈ P, f(n) < g(n) for all n.

Remark 3.21. Clearly any subset of 2^{ω} is recursively bounded, viz., by the constant function λn.2. The next theorem implies that, up to recursive homeomorphism, the study of recursively bounded Π_{1}^{0} subsets of ω^{ω} is equivalent to the study of Π_{1}^{0} subsets of 2^{ω}.

Theorem 3.22. For each recursively bounded Π_{1}^{0} set P ⊆ ω^{ω}, we can find a Π_{1}^{0} set P^{∗} ⊆ 2^{ω} such that P is recursively homeomorphic to P^{∗}. It follows that P ≡_{s} P^{∗}, hence P ≡_{w} P^{∗}.

Proof. Define P^{∗} as in the proof of Theorem 2.15. It is straightforward to show that, if P is Π_{1}^{0} and recursively bounded, then P^{∗} is Π_{1}^{0}.

Remark 3.23. Conversely, if P ⊆ 2^{ω} is Π_{1}^{0}, then for any recursive functional Φ : P → ω^{ω}, the range {Φ(f) | f ∈ P } is Π_{1}^{0} and recursively bounded. This is a consequence of compactness of 2^{ω}.

Remark 3.24. By Theorem 3.22, the weak degrees of recursively bounded Π_{1}^{0} subsets of ω^{ω} belong to P_{w}, and similarly for strong degrees. On the other hand, there are plenty of nonempty Π_{1}^{0} subsets of ω^{ω} whose weak degrees do not belong to P_{w}.

Example 3.25. It is known from hyperarithmetical theory (see Sacks [32, Part A] or Simpson [39, Section VIII.3]) that for any hyperarithmetical X ∈ 2^{ω} there exists a hyperarithmetical g ∈ ω^{ω} such that X ≤_{T} g and the singleton set {g} ⊆ ω^{ω} is Π_{1}^{0}. If g is not recursive, the GKT Basis Theorem (see Simpson [39, Section VIII.2]) implies that deg_{w}({g}) ≰_{w} P for any nonempty Π_{1}^{0} set P ⊆ 2^{ω}.

Example 3.26. Another interesting Π_{1}^{0} subset of ω^{ω} is

DNR = {f ∈ ω^{ω} | ∀n f(n) ≠ {n}(n)},

i.e., the set of f : ω → ω which are diagonally non-recursive. We shall comment more on this later. See Corollary 7.3 and Remark 7.5 below.

4 Weak and Strong Completeness

Definition 4.1. A nonempty Π_{1}^{0} set P ⊆ 2^{ω} is said to be weakly complete, or Muchnik complete, if every nonempty Π_{1}^{0} subset of 2^{ω} is weakly reducible to P.

Definition 4.2. A nonempty Π_{1}^{0} set P ⊆ 2^{ω} is said to be strongly complete, or Medvedev complete, if every nonempty Π_{1}^{0} subset of 2^{ω} is strongly reducible to P.

Remark 4.3. We use 1 to denote the weak degree of any nonempty Π_{1}^{0} subset of 2^{ω} which is weakly complete. Thus 1 is the top element of P_{w}. Similarly for strong degrees and P_{s}.

Example 4.4. The following Π_{1}^{0} subsets of 2^{ω} are known to be strongly complete, hence weakly complete.

1. P = {completions of PA}. Instead of PA we could use any effectively axiomatizable, effectively essentially undecidable theory. This is related to the Gödel/Rosser Theorem. See also Scott/Tennenbaum [33].

2. P = {f ∈ 2^{ω} | f separates A and B}, where A = {n | {n}(n) ≃ 0} and B = {n | {n}(n) ≃ 1}. See Jockusch/Soare [20].

3. We can also give an explicit, recursion-theoretic construction of a Π_{1}^{0} set P with the desired property. Namely, P = ∏_{e=0}^{∞} P_{e}^{+} where P_{e}^{+} is the nonempty Π_{1}^{0} subset of 2^{ω} indexed by e. See Simpson [35, Lemma 3.3].

Theorem 4.5 (Simpson 2000). Any two strongly complete Π_{1}^{0} subsets of 2^{ω} are recursively homeomorphic.

Proof. The proof is by an effective back-and-forth argument, using the Recursion Theorem. See Simpson [35, Section 3]. It is analogous to the proof of Myhill’s result that any two creative, recursively enumerable subsets of ω are recursively isomorphic. Myhill’s result is expounded in Rogers [30].

Corollary 4.6. A nonempty Π_{1}^{0} subset of 2^{ω} is strongly complete if and only if it is recursively homeomorphic to the set of completions of PA.

The proof of Theorem 4.5 also gives the following.

Corollary 4.7. Let P and Q be nonempty Π_{1}^{0} subsets of 2^{ω}. If P is strongly complete, then there is a recursive functional Φ : P → Q which maps P onto Q, i.e., Q = {Φ(f) | f ∈ P }.

Proof. See Simpson [35, Section 3].

The following example shows that strong completeness is not the same as weak completeness.

Example 4.8 (Jockusch 1989). For k ≥ 2 let DNR_{k} be the set of functions f : ω → {1, …, k} which are DNR. It is easy to see that the sets DNR_{k}, k = 2, 3, …, are Π_{1}^{0} and recursively bounded, and that DNR_{2} is strongly complete. Jockusch [19] has shown that the the sets DNR_{k}, k = 2, 3, … are weakly complete but of different strong degrees. Thus we have DNR_{2} ≡_{w} DNR_{3} ≡_{w} … yet DNR_{2} >_{s} DNR_{3} >_{s} . . ..

An interesting relationship between weak and strong reducibility is given by the following theorem.

Theorem 4.9 (Simpson 2001). Let P, Q ⊆ 2^{ω} be nonempty Π_{1}^{0} sets. If P ≤_{w} Q, then there exists a nonempty Π_{1}^{0} set Q′ ⊆ Q such that P ≤_{s} Q′.

Proof. We shall prove this later, as a consequence of the Almost Recursive Basis Theorem. See Theorem 6.6.

Corollary 4.10. If Q ⊆ 2^{ω} is Π_{1}^{0} and weakly complete, then there is a Π_{1}^{0} set Q′ ⊆ Q such that Q′ is strongly complete.

Definition 4.11. P, Q ⊆ ω^{ω} are said to be Turing degree isomorphic if there exists a Turing-degree-preserving one-to-one correspondence between P and Q. Clearly recursive homeomorphism implies Turing degree isomorphism.

Theorem 4.12 (Simpson 2001). Any two weakly complete Π_{1}^{0} subsets of 2^{ω} are Turing degree isomorphic.

Proof. This follows easily from Theorem 4.5 and Corollary 4.10.

Corollary 4.13. A nonempty Π_{1}^{0} subset of 2^{ω} is weakly complete if and only if it is Turing degree isomorphic to the set of completions of PA.

Corollary 4.14. Any two nonempty Π_{1}^{0} subsets of ⋃_{k=0}^{∞} DNR_{k} are Turing degree isomorphic.

Corollary 4.15. If P is weakly complete, then the set of Turing degrees of members of P is upward closed.

Proof. Let P be weakly complete. Put Q = P × 2^{ω}. Clearly Q is weakly complete, and the set of Turing degrees of members of Q is upward closed. By Theorem 4.12, P and Q are Turing degree isomorphic.

Corollary 4.16 (Solovay). The set of Turing degrees of completions of PA is upward closed.

5 1-Randomness

In this section we present an explicit, natural example of a weak degree in P_{w} which is strictly between 0 and 1. Our example is based on Martin-Løf’s theory of randomness.

We use the “fair coin” probability measure on 2^{ω}. Thus for all n ∈ ω we have

μ({X ∈ 2^{ω} | X(n) = 0}) = μ({X ∈ 2^{ω} | X(n) = 1}) = 1/2.

Definition 5.1. An effective null G_{δ} is a set S ⊆ 2^{ω} of the form S = ⋂_{n=0}^{∞} U_{n} where U_{n}, n ∈ ω, is a recursively indexed sequence of Σ_{1}^{0} sets such that μ(U_{n}) < 1/2^{n} for all n.

Definition 5.2. X ∈ 2^{ω} is 1-random if X ∉ S for all effective null G_{δ} sets S. The set of 1-random X ∈ 2^{ω} is denoted R_{1}. Clearly μ(R_{1}) = 1.

Theorem 5.3 (Martin-Løf 1966). The union of all effective null G_{δ} sets is an effective null G_{δ} set.

Proof. This result is due to Martin-Løf [26]. The proof is by a diagonal argument. See also Kučera [22].

Corollary 5.4. 2^{ω} \ R_{1} is an effective null G_{δ} set. Hence R_{1} is Σ_{2}^{0}.

Corollary 5.5. R_{1} = ⋃_{n=0}^{∞} P_{n} where P_{n}, n ∈ ω, is a sequence of Π_{1}^{0} sets.

Theorem 5.6. Let Q ⊆ 2^{ω} be Π_{1}^{0} of measure 0. Then Q is an effective null G_{δ} set.

Proof. Straightforward.

Corollary 5.7. Let Q ⊆ 2^{ω} be Π_{1}^{0}. We have μ(Q) > 0 if and only if Q∩R_{1} ≠ ∅. In this case we actually have Q ∩ R_{1} ⊇ P ≠ ∅, where P is Π_{1}^{0} and μ(P) > 0.

Theorem 5.8 (Kučera 1985). Let Q ⊆ 2^{ω} be Π_{1}^{0} with μ(Q) > 0. Then for all 1-random X ∈ 2^{ω} we have that X^{(k)} ∈ Q for some k ∈ ω. Here X^{(k)}(n) = X(k + n) for all n ∈ ω.

Proof. See Kučera [22]. Let T be a recursive tree such that Q is the set of paths through T. Let T̃ be the set of all τ^{⌢}⟨i⟩ ∈ Seq_{2} such that τ ∈ T and τ^{⌢}⟨i⟩ ∉ T. Let Q^{2} be the set of paths through the tree T^{2} = T ∪ {σ^{⌢}τ | σ ∈ T̃, τ ∈ T }. Note that Q^{2} is Π_{1}^{0} and μ(Q^{2}) = 1 − (1 − μ(Q))^{2}. Define Q^{n} similarly for all n ≥ 1. Since Q^{n} is Π_{1}^{0} and μ(Q^{n}) = 1 − (1 − μ(Q))^{n}, we have that 2^{ω} \ ⋃_{n=1}^{∞} Q^{n} is an effective null G_{δ} set. Hence X ∈ Q^{n} for some n. It follows that X^{(k)} ∈ Q for some k.

Corollary 5.9. Let Q ⊆ 2^{ω} be Π_{1}^{0} with μ(Q) > 0. Then Q ≤_{w} R_{1}.

Corollary 5.10. Let Q be a nonempty Π_{1}^{0} subset of R_{1}. Then Q ≡_{w} R_{1}.

Corollary 5.11. Among all weak degrees of Π_{1}^{0} sets Q ⊆ 2^{ω} with μ(Q) > 0, there is a largest one, and it is the same as the weak degree of R_{1}. Call this weak degree r_{1}.

Theorem 5.12. Let A, B ⊆ ω be recursively inseparable. Then

μ({X ∈ 2^{ω} | ∃Y ≤_{T} X (Y separates A, B)}) = 0.

Proof. Not difficult. See Jockusch/Soare [20].

Corollary 5.13. The weak degree r_{1} = deg_{w}(R_{1}) ∈ P_{w} of Corollary 5.11 is not weakly complete. We have 0 < r_{1} < 1.

Remark 5.14. More generally, for all weak degrees a ∈ D_{w}, if sup(a, r_{1}) ≥ 1 then a ≥ 1. This result is due to Simpson [40].

Remark 5.15. The weak degree r_{1} is the first explicit, natural example of a weak degree in P_{w} strictly between 0 and 1. This is especially interesting because no explicit, natural examples of r. e. Turing degrees strictly between 0 and 0′ are known. See Simpson [38].

6 The Almost Recursive Basis Theorem

Definition 6.1. X is almost recursive (a.k.a., hyperimmune-free) if, for each function f : ω → ω recursive in X, there exists a recursive function g : ω → ω such that f(m) < g(m) for all m ∈ ω.

The following theorem is from Jockusch/Soare [20]. We call it the Almost Recursive Basis Theorem.

Theorem 6.2. Let P be a nonempty Π_{1}^{0} subset of 2^{ω}. Then there exists X ∈ P such that X is almost recursive.

Proof. Define a sequence of nonempty Π_{1}^{0} sets P = P_{0} ⊇ P_{1} ⊇ ⋯ ⊇ P_{n} ⊇ ⋯ as follows. Put P_{0} = P. If ∃m (∃X ∈ P_{n}) {n}^{X}(m) ↑, fix such an m and put P_{n+1} = {X ∈ P_{n} | {n}^{X}(m) ↑}. Otherwise, put P_{n+1} = P_{n}. Clearly there is a unique X ∈ ⋂_{n=0}^{∞} P_{n}. By Remark 3.23, X is almost recursive.

Corollary 6.3. There exists a completion of PA which is almost recursive.

Corollary 6.4. There exists a 1-random X ∈ 2^{ω} which is almost recursive.

Lemma 6.5. Suppose X is almost recursive and X ≥_{T} Y. Then Y is truth table reducible to X. In particular, there exists a total recursive functional Φ : 2^{ω} → 2^{ω} such that Φ(X) = Y.

Proof. Let e be such that Y = {e}^{X}. Define f : ω → ω by f(m) = the least s such that {e}_{s}^{X[s]}(m) ↓. Clearly f ≤_{T} X. Let g : ω → ω be recursive such that f(m) ≤ g(m) for all n. Define a truth table functional Φ : 2^{ω} → 2^{ω} by putting Φ(Z)(m) = {e}_{g(m)}^{Z[g(m)]}(m) if this is defined, and Φ(Z)(m) = 0 otherwise. Clearly Φ(X) = Y.

The following theorem from Simpson [40] provides an interesting relationship between ≤_{w} and ≤_{s}.

Theorem 6.6. Let P, Q ⊆ 2^{ω} be nonempty Π_{1}^{0} sets. If P ≤_{w} Q, then there is a nonempty Π_{1}^{0} set Q′ ⊆ Q such that P ≤_{s} Q′.

Proof. Assume P ≤_{w} Q. By Theorem 6.2 let Y ∈ Q be almost recursive. Let X ∈ P be such that X ≤_{T} Y. By Lemma 6.5 let Φ : 2^{ω} → 2^{ω} be a truth table functional such that Φ(Y) = X. Put Q′ = Q ∩ Φ^{−1}(P). Then Q′ is a nonempty Π_{1}^{0} subset of Q, and P ≤_{s} Q′ via Φ.

Corollary 6.7. Let X be 1-random and almost recursive. Then there is no completion of PA which is ≤_{T} X.

Proof. Otherwise, by the proof of Theorem 6.6, there would be a strongly complete Π_{1}^{0} set Q ⊆ 2^{ω} with μ(Q) > 0. This would contradict Theorem 5.12.

7 The Σ_{3}^{0} → Π_{1}^{0} Embedding Theorem

The next theorem, due to Simpson [40], tells us that the weak degrees of many naturally occurring mass problems belong to P_{w}, even when they do not naturally occur as recursively bounded Π_{1}^{0} sets.

Definition 7.1. A set S ⊆ ω^{ω} is said to be Σ_{3}^{0} if there exists a recursive predicate R ⊆ ω^{ω} × ω^{3} such that

S = {f ∈ ω^{ω} | ∃n_{1} ∀n_{2} ∃n_{3} R(f, n_{1}, n_{2}, n_{3})}.

A set P ⊆ ω^{ω} is said to be Π_{3}^{0} if its complement ω^{ω} \ P is Σ_{3}^{0}. One defines Σ_{k}^{0} and Π_{k}^{0} similarly for all k ≥ 1. See Rogers [30, Chapter 15].

Theorem 7.2. If S ⊆ ω^{ω} is Σ_{3}^{0}, then for all nonempty Π_{1}^{0} sets P ⊆ 2^{ω} we can find a Π_{1}^{0} set Q ⊆ 2^{ω} such that Q ≡_{w} P ∪ S.

Proof. First use a Skolem function technique to reduce to the case where S is a Π_{1}^{0} subset of ω^{ω}. Namely, replace S by the set of all ⟨k⟩^{⌢}(f ⊕ g) ∈ ω^{ω} such that ∀m (g(m) = the least n such that R(f, k, m, n)). Clearly this set is ≡_{w} S and Π_{1}^{0}. After that, let T_{S} be a recursive subtree of Seq such that S is the set of paths through T_{S}. Let T_{P} be a recursive subtree of Seq_{2} such that P is the set of paths through T_{P}. We may assume that, for all τ ∈ T_{S} and n < lh(τ), τ(n) ≥ 2. Define T_{Q} to be the set of sequences ρ ∈ Seq of the form

σ_{0}^{⌢}⟨n_{0}⟩^{⌢}σ_{1}^{⌢}⟨n_{1}⟩^{⌢} ⋯^{⌢}⟨n_{k−1}⟩^{⌢}σ_{k}

where ⟨n_{0}, n_{1}, …, n_{k−1}⟩ ∈ T_{S}, σ_{0}, σ_{1}, …, σ_{k} ∈ T_{P}, and ρ(m) ≤ m + 2 for all m < lh(ρ). Thus T_{Q} is a recursive subtree of Seq. Let Q ⊆ ω^{ω} be the set of paths through T_{Q}. It is not hard to see that Q ≡_{w} P ∪ S. Note that Q is Π_{1}^{0} and recursively bounded. Hence by Theorem 3.22 there is a Π_{1}^{0} set Q^{∗} ⊆ 2^{ω} which is recursively homeomorphic to Q.

Corollary 7.3. There is a Π_{1}^{0} set D ⊆ 2^{ω} such that D ≡_{w} DNR.

Proof. Apply Theorem 7.2 with P = DNR_{2} and S = DNR.

Remark 7.4. Put d = deg_{w}(D) = deg_{w}(DNR). By Kumabe [21] (see also Ambos-Spies/Kjos-Hanssen/Lempp/Slaman [2]) we have

0 < d < r_{1} < 1.

The weak degrees 1, r_{1}, and d correspond to the system WKL_{0} and two of its subsystems which have arisen in the foundations of mathematics. See respectively Simpson [39], Yu/Simpson [45], and Giusto/Simpson [18].

Remark 7.5. Jockusch [19] has shown that the following mass problems are pairwise Turing degree isomorphic, hence weakly equivalent.

1. DNR = {f ∈ ω^{ω} | f is diagonally non-recursive, i.e., ∀e f(e) ≄ {e}(e)}.

2. FPF = {f ∈ ω^{ω} | f is fixed point free, i.e., ∀e ∃m {f(e)}(m) ≄ {e}(m)}.

3. EI = {A ⊆ ω | A is effectively immune}.

This means that A is infinite and, given an index of an r. e. set C ⊆ A, we can effectively find a finite upper bound for the cardinality of C.

4. EBI = {A ⊆ ω | A is effectively bi-immune}.

This means that both A and ω \ A are effectively immune.

Definition 7.6. A member of 2^{ω} is said to be 2-random if it is 1-random relative to 0′, the Turing degree of the Halting Problem. The set of 2-random X ∈ 2^{ω} is denoted R_{2}. We write r_{2} = deg_{w}(R_{2}).

Corollary 7.7. There is a Π_{1}^{0} set R_{2}^{∗} ⊆ 2^{ω} such that R_{2}^{∗} ≡_{w} R_{2} ∪ P, where P = {completions of PA}. Put r_{2}^{∗} = inf(r_{2}, 1) = deg_{w}(R_{2}^{∗}).

Proof. Relativizing Corollary 5.4 we see that R_{2} is a Σ_{3}^{0} subset of 2^{ω}. Our result then follows by Theorem 7.2.

Theorem 7.8. If X is 2-random, then X is not almost recursive.

Proof. Martin [24] has shown that μ({X ∈ 2^{ω} | X is almost recursive}) = 0. Our theorem follows from an analysis of Martin’s proof. See also the exposition of Martin’s result in Dobrinen/Simpson [11].

Theorem 7.9. We have 0 < d < r_{1} < r_{2}^{∗} < 1.

Proof. From Remark 7.4 we have 0 < d < r_{1}, and obviously r_{1} ≤ r_{2}^{∗} ≤ 1. Theorem 5.12 implies that r_{2}^{∗} < 1. The fact that r_{1} < r_{2}^{∗} follows from Corollaries 6.4 and 6.7 and Theorem 7.8.

Remark 7.10. Additional examples of naturally occurring mass problems whose weak degrees belong to P_{w} are in Simpson [40].

8 Embedding the R. E. Turing Degrees

Recall that R_{T} is the upper semilattice of Turing degrees of recursively enumerable subsets of ω, and P_{w} (P_{s}) is the lattice of weak (strong) degrees of nonempty Π_{1}^{0} subsets of 2^{ω}. See Remark 1.17 and Definition 3.7.

In this section we use the Σ_{3}^{0} → Π_{1}^{0} Embedding Theorem 7.2 to embed R_{T} into P_{w}. We do not know whether there exists an embedding of R_{T} into P_{s}.

Theorem 8.1. Let A ∈ 2^{ω} be Δ_{2}^{0}, i.e., deg_{T} (A) ≤_{T} 0′. Then there is a Π_{1}^{0} set P_{A} ⊆ 2^{ω} such that P_{A} ≡_{w} P ∪ {A}, where P = {completions of PA}. We have P_{A⊕B} ≡_{w} P_{A} × P_{B}.

Proof. The first statement follows from Theorem 7.2 since the singleton set {A} is Π_{2}^{0}. The second statement is straightforward.

Theorem 8.2 (Arslanov Completeness Criterion). Let A ⊆ ω be recursively enumerable. If f ∈ DNR and f ≤_{T} A, then A is Turing complete, i.e., deg_{T} (A) = 0′.

Proof. See Soare’s book [42, Section V.5]. Note that we are identifying A ⊆ ω with its characteristic function χ_{A} ∈ 2^{ω}.

Theorem 8.3. Let A, B ⊆ ω be recursively enumerable. Then A ≤_{T} B if and only if P_{A} ≤_{w} P_{B}.

Proof. Obviously A ≤_{T} B implies P_{A} ≤_{w} P_{B}. For the converse, recall that P is strongly complete, hence recursively homeomorphic to DNR_{2}. In particular, for all X ∈ P there is a DNR function f ≤_{T} X. Assume now that P_{A} ≤_{w} P_{B}. In particular we can find X ∈ P ∪ {A} such that X ≤_{T} B. If X ∈ P, then by the Arslanov Completeness Criterion, B is Turing complete, hence A ≤_{T} B. If X ∉ P, then X = A, hence again A ≤_{T} B.

Remark 8.4. Thus our embedding of the r. e. Turing degrees into the weak lattice P_{w} is given by deg_{T} (A) ↦ deg_{w}(P ∪ {A}), where P = {completions of PA}. The embedding is one-to-one, order preserving, least upper bound preserving, and carries 0 to 0 and 0′ to 1.

Remark 8.5. Instead of P = {completions of PA}, we could use any nonempty Π_{1}^{0} set P ⊆ 2^{ω} such that DNR ≤_{w} P. Compare Corollary 7.3. Thus, for any c ∈ P_{w} such that c ≥ d = deg_{w}(DNR), we obtain an embedding of the r. e. Turing degrees into {a ∈ P_{w} | 0 ≤ a ≤ c}. The embbedding is one-to-one, order preserving, least upper bound preserving, and carries 0 to 0 and 0′ to c.

9 A Priority Argument

In this section we sketch the construction of a Π_{1}^{0} set P ⊆ 2^{ω} with several interesting properties. The construction uses a priority argument.

Definition 9.1. A Π_{1}^{0} set P ⊆ 2^{ω} is said to be thin if, for all Π_{1}^{0} sets Q ⊆ P, there is a finite set σ_{1}, …, σ_{n} ∈ Seq_{2} such that

Q = {X ∈ P | σ_{1} ⊂ X ∨ ⋯ ∨ σ_{n} ⊂ X}.

This is equivalent to saying that, for all Π_{1}^{0} sets Q ⊆ P, P \ Q is Π_{1}^{0}. See also references [25, 12, 13, 9].

Definition 9.2. A family of Turing degrees {a_{i} | i ∈ I} is said to be independent if for all finite {i_{0}, i_{1}, …, i_{n}} ⊆ I, a_{i_{0}} ≤ sup(a_{i_{1}}, …, a_{i_{n}}) implies i_{0} ∈ {i_{1}, …, i_{n}}.

Theorem 9.3. We can construct a Π_{1}^{0} set P ⊆ 2^{ω} with the following properties:

1. P is thin and of cardinality 2^{ℵ_{0}}.

2. P has no recursive members.

3. The Turing degrees deg_{T} (X), X ∈ P, are independent.

4. For all X ∈ P, putting a = deg_{T} (X), we have a′ = sup(a, 0′). Here a′ denotes the Turing jump of a.

Furthermore, given a Π_{1}^{0} set Q ⊆ 2^{ω} with no recursive members, we can arrange that no member of P Turing computes a member of Q.

Sketch of proof. We follow Binns/Simpson [6] building on the techniques of Martin/Pour-El [25] and Jockusch/Soare [20, Theorem 4.7].

By a treemap we mean a function h : Seq_{2} → Seq_{2} such that h(σ)^{⌢}⟨i⟩ ⊆ h(σ^{⌢}⟨i⟩) for all σ ∈ Seq_{2}, i ∈ {0, 1}.

Starting with h_{0} = the identity map, we construct a recursive sequence of recursive treemaps h_{s}, s ∈ ω, which are nested in the sense that for all s and all σ ∈ Seq_{2} there exists τ ∈ Seq_{2} such that h_{s+1}(σ) = h_{s}(τ). After presenting the recursive construction, we argue that, for all σ ∈ Seq_{2}, the limit h(σ) = lim_{s} h_{s}(σ) exists and is finite. If follows that h = lim_{s} h_{s} is a treemap, and we define

P = {X ∈ 2^{ω} | ∀n (∃σ of length n) h(σ) ⊂ X}.

Clearly P will be Π_{1}^{0} and of cardinality 2^{ℵ_{0}}.

In order to insure that P is thin, we arrange that for all e ∈ ω and all σ ∈ Seq_{2} of length e, {e}^{h(σ)}(0) ↓ “if possible”. Then for all X ∈ P we have

H^{X} = {e | (∃σ of length e) ({e}_{lh(h(σ))}^{h(σ)}(0) ↓ and h(σ) ⊂ X)},

so H^{X} ≤_{T} H ⊕ X and this gives property 4. Now, given a Π_{1}^{0} set Q ⊆ 2^{ω}, let e be such that Q = {X | {e}^{X}(0) ↑}. (See the proof of Theorem 3.14.) Then

Q = {X ∈ P | (∃σ of length e) ({e}_{lh(h(σ))}^{h(σ)}(0) ↑ and h(σ) ⊂ X)},

and this gives thinness.

The strategy for property 3 is similar. For example, to insure X ≰_{T} Y for all X, Y ∈ P with X ≠ Y, we arrange that for all e and all σ, τ ∈ Seq_{2} of length e with σ ≠ τ, ∃m < lh(h(σ)) ({e}_{lh(h(τ))}^{h(τ)}(m) ↓ ≠ h(σ)(m)) “if possible”.

The final property is obtained by means of a Sacks preservation strategy. See Binns/Simpson [6].

Corollary 9.4. Every finite distributive lattice is lattice embeddable in P_{w} and in P_{s}.

Proof. First note that any finite distributive lattice is lattice embeddable in the free distributive lattice on n generators, for sufficiently large n. Now let P be as in Theorem 9.3, and let P_{1}, …, P_{n} be nonempty, pairwise disjoint, Π_{1}^{0} subsets of P. In view of property 3, the weak or strong degrees of P_{1}, …, P_{n} are independent and hence freely generate a free distributive lattice. Details are in Binns/Simpson [6].

Corollary 9.5. For any b > 0 in P_{w} or P_{s}, every finite distributive lattice is lattice embeddable in the interval 0 ≤ a ≤ b.

Proof. Let Q ⊆ 2^{ω} be Π_{1}^{0} with b = deg_{w}(Q) or deg_{s}(Q) as the case may be. Let P be as in Theorem 9.3 such that no member of P Turing computes a member of Q. Proceed as in the proof of Corollary 9.4, replacing P_{1}, …, P_{n} by P_{1} + Q, …, P_{n} + Q.

Remark 9.6. By Theorem 9.3, let P be a nonempty thin Π_{1}^{0} subset of 2^{ω} with no recursive members. Then P is of measure 0, and in fact, deg_{w}(P) is incomparable with r_{1}. These results are due to Simpson [40].

Remark 9.7. By Theorem 9.3 and Remark 3.19, let T be a consistent, finitely axiomatizable, essentially undecidable theory such that P_{T} is thin. Then any recursively axiomatizable theory extending T with the same vocabulary as T is finitely axiomatizable. Compare Martin/Pour-El [25].

References

[1] K. Ambos-Spies, G. H. Müller, and G. E. Sacks, editors. Recursion Theory Week. Number 1432 in Lecture Notes in Mathematics. Springer-Verlag, 1990. IX + 393 pages.

[2] Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman. Comparing DNR and WWKL. March 2004. Preprint, 10 pages, to appear.

[3] J. Barwise, editor. Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. North-Holland, 1977. XI + 1165 pages.

[4] Stephen Binns. The Medvedev and Muchnik Lattices of Π_{1}^{0} Classes. PhD thesis, Pennsylvania State University, August 2003. V + 80 pages.

[5] Stephen Binns. A splitting theorem for the Medvedev and Muchnik lattices. Mathematical Logic Quarterly, 49:327–335, 2003.

[6] Stephen Binns and Stephen G. Simpson. Embeddings into the Medvedev and Muchnik lattices of Π_{1}^{0} classes. Archive for Mathematical Logic, 43:399– 414, 2004.

[7] Douglas Cenzer and Peter G. Hinman. Density of the Medvedev lattice of Π_{1}^{0} classes. Archive for Mathematical Logic, 42:583–600, 2003.

[8] Douglas Cenzer and Jeffrey B. Remmel. Π_{1}^{0} classes in mathematics. In [15], pages 623–821, 1998.

[9] Peter Cholak, Richard Coles, Rod Downey, and Eberhard Herrmann. Automorphisms of the lattice of Π_{1}^{0} classes; perfect thin classes and ANC degrees. Transactions of the American Mathematical Society, 353(12):4899– 4924, 2001.

[10] S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors. Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Number 224 in London Mathematical Society Lecture Notes. Cambridge University Press, 1996. VII + 347 pages.

[11] Natasha L. Dobrinen and Stephen G. Simpson. Almost everywhere domination. Journal of Symbolic Logic. Preprint, 11 pages, submitted for publication March 2004, accepted for publication May 2004, to appear.

[12] Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob. Array nonrecursive sets and multiple permitting arguments. In [1], pages 141–174, 1990.

[13] Rodney G. Downey, Carl G. Jockusch, Jr., and Michael Stob. Array nonrecursive degrees and genericity. In [10], pages 93–105, 1996.

[14] H.-D. Ebbinghaus, G.H. Müller, and G.E. Sacks, editors. Recursion Theory Week. Number 1141 in Lecture Notes in Mathematics. Springer-Verlag, 1985. IX + 418 pages.

[15] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors. Handbook of Recursive Mathematics. Studies in Logic and the Foundations of Mathematics. North-Holland, 1998. Volumes 1 and 2, XLVI + 1372 pages.

[16] J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors. Logic, Methodology and Philosophy of Science VIII. Studies in Logic and the Foundations of Mathematics. Elsevier, 1989. XVII + 702 pages.

[17] FOM e-mail list. http://www.cs.nyu.edu/mailman/listinfo/fom/,

September 1997 to the present.

[18] Mariagnese Giusto and Stephen G. Simpson. Located sets and reverse mathematics. Journal of Symbolic Logic, 65:1451–1480, 2000.

[19] Carl G. Jockusch, Jr. Degrees of functions with no fixed points. In [16], pages 191–201, 1989.

[20] 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.

[21] Masahiro Kumabe. A fixed point free minimal degree. 1997. Preprint, 48 pages.

[22] Antonín Kučera. Measure, Π_{1}^{0} classes and complete extensions of PA. In [14], pages 245–259, 1985.

[23] Manuel Lerman. Degrees of Unsolvability. Perspectives in Mathematical Logic. Springer-Verlag, 1983. XIII + 307 pages.

[24] Donald A. Martin. Measure, category, and degrees of unsolvability. Unpublished, typewritten, 16 pages, 1967.

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

[26] Per Martin-Løf. The definition of random sequences. Information and Control, 9:602–619, 1966.

[27] Yuri T. Medvedev. Degrees of difficulty of mass problems. Doklady Akademii Nauk SSSR, n.s., 104:501–504, 1955. In Russian.

[28] A. A. Muchnik. On strong and weak reducibilities of algorithmic problems. Sibirskii Matematicheskii Zhurnal, 4:1328–1341, 1963. In Russian.

[29] Mikhail G. Peretyatkin. Finitely Axiomatizable Theories. Siberian School of Algebra and Logic. Consultants Bureau, New York, 1997. XIV + 294 pages.

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

[31] Gerald E. Sacks. Degrees of Unsolvability. Number 55 in Annals of Mathematics Studies. Princeton University Press, 2nd edition, 1966.

[32] Gerald E. Sacks. Higher Recursion Theory. Perspectives in Mathematical Logic. Springer-Verlag, 1990. XV + 344 pages.

[33] Dana S. Scott and Stanley Tennenbaum. On the degrees of complete extensions of arithmetic (abstract). Notices of the American Mathematical Society, 7:242–243, 1960.

[34] S. G. Simpson, editor. Reverse Mathematics 2001. Lecture Notes in Logic. Association for Symbolic Logic, 2004. To appear.

[35] Stephen G. Simpson. Π_{1}^{0} sets and models of WKL_{0}. In [34]. Preprint, April 2000, 29 pages, to appear.

[36] Stephen G. Simpson. Degrees of unsolvability: a survey of results. In [3], pages 631–652, 1977.

[37] Stephen G. Simpson. First order theory of the degrees of recursive unsolvability. Annals of Mathematics, 105:121–139, 1977.

[38] Stephen G. Simpson. FOM: natural r.e. degrees; Pi01 classes. FOM e-mail list [17], August 13, 1999.

[39] Stephen G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, 1999. XIV + 445 pages.

[40] Stephen G. Simpson. Some Muchnik degrees of Π_{1}^{0} subsets of 2^{ω}. June 2001. Preprint, 7 pages, in preparation.

[41] Stephen G. Simpson and Theodore A. Slaman. Medvedev degrees of Π_{1}^{0} subsets of 2^{ω}. July 2001. Preprint, 4 pages, in preparation.

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

[43] Andrea Sorbi. The Medvedev lattice of degrees of difficulty. In [10], pages 289–312, 1996.

[44] Alan M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230–265, 1936.

[45] Xiaokang Yu and Stephen G. Simpson. Measure theory and weak König’s lemma. Archive for Mathematical Logic, 30:171–180, 1990.