Degrees of Unsolvability

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

June 9, 2009

These notes are a record of my graduate course entitled “Mass Problems” given in Spring 2009 at the Pennsylvania State University. The students in the course are Sankha Basu, Jacob Hendricks, Phil Hudelson, and Noopur Pathak. I am lecturing, the students are taking notes, and I am polishing the notes.

Contents

1 Oracle computations 3 2 Mass problems 5 3 Some basic theorems 7 4 The arithmetical hierarchy 8 5 Mass problems in the arithmetical hierarchy 10 6 Strings and trees 12 7 Genericity 14 8 Turing degrees and the jump operator 15 9 The Cantor space 18 10 Basis Theorems in the Cantor space 19 11 The Low Basis Theorem 22 12 The Hyperimmune-Free Basis Theorem 23 13 The lattice E_{w} 25 14 Some mass problems of degree 1 27 15 Martin-Löf randomness 30 16 Randomness as a mass problem 35 17 The Embedding Lemma 37 18 Consequences of the Embedding Lemma 38 19 1-genericity 40 20 Kolmogorov complexity 42 21 Distinguishing r_{1} from inf(r_{2}, 1) 45 22 Distinguishing d, d_{REC}, and d_{C} 46 23 Bounded limit-recursiveness 52 24 Embedding hyperarithmeticity into E_{w} 56

1 Oracle computations

We use the register machine model of computation. Each register R_{i} contains a natural number r_{i}. There are three types of instructions:

[figure: R_{i}^{+}]

add 1 to r_{i} (increment instruction)

[figure: R_{i}^{−}; e]

if r_{i} = 0 go to e, otherwise subtract 1 from r_{i} (decrement instruction)

[figure: R_{i}^{0}]

if r_{i} = n replace n by g(n) (oracle instruction)

Definition 1.1. An oracle program is a connected flow diagram consisting of

the above instructions plus [figure: start]and [figure: stop] . Each program has

exactly one [figure: start] instruction.

Definition 1.2. A (partial) function ψ :⊆ ℕ^{k} → ℕ is said to be (partial) computable (i.e., (partial) recursive) if there exists a program P (with no oracle instructions) which computes ψ in the sense that for all m_{1}, …, m_{k} ∈ ℕ,

ψ(m_{1}, …, m_{k}) ↓ ⇔ P(m_{1}, …, m_{k}) halts

in which case ψ(m_{1}, …, m_{k}) appears in R_{k+1}. Here P(m_{1}, …, m_{k}) denotes the run of P starting with m_{1}, …, m_{k} in R_{1}, …, R_{k} and all other registers empty.

Example 1.3. The 2-place function f(m_{1}, m_{2}) = m_{1} + m_{2} is computable via the program

[figure: start; R_{1}^{−}; e; R_{2}^{−}; e; stop; R_{3}^{+}; R_{3}^{+}]

Remark 1.4. We assume familiarity with Church’s Thesis for register machine programs. Thus, the functions which are “computable” in an intuitive sense are precisely the functions which are computable by register machine programs.

Definition 1.5. An oracle is a total function g : ℕ → ℕ. The set of all such functions is denoted ℕ^{ℕ}. We sometimes view ℕ^{ℕ} as a topological space. This space is known as the Baire space.

Notation 1.6. We write P^{g}(m_{1}, …, m_{k}) to denote the run of the program P starting with m_{1}, …, m_{k} in R_{1}, …, R_{k} and all other registers empty, using g as the oracle.

Definition 1.7. Given g ∈ ℕ^{ℕ} and k ≥ 1, a partial function ψ^{g} :⊆ ℕ^{k} → ℕ is said to be (partial) g-computable (i.e., computable relative to g) if there exists an oracle program P such that for all m_{1}, …, m_{k} ∈ ℕ,

ψ^{g}(m_{1}, …, m_{k}) ↓ ⇔ P^{g}(m_{1}, …, m_{k}) halts

in which case ψ^{g}(m_{1}, …, m_{k}) appears in R_{k+1}.

Example 1.8. Given g ∈ ℕ^{ℕ}, the partial function

ψ^{g}(m) ≃ least n > m such that g(n) = 0

is partial g-computable via the program

[figure: R_{1}^{+}; R_{2}^{−}; e; R_{1}^{+}; start; R_{1}^{−}; e; R_{3}^{0}; R_{3}^{−}; e; stop; R_{2}^{+}; R_{3}^{+}]

Remark 1.9. In the above definition, we have viewed the oracle g as fixed. An alternative point of view is to regard g as variable, as in the following definition.

Definition 1.10. For k ≥ 0, a partial functional Ψ :⊆ ℕ^{ℕ} × ℕ^{k} → ℕ is said to be (partial) computable, i.e., (partial) recursive, if there exists an oracle program P such that for all g ∈ ℕ^{ℕ} and all m_{1}, …, m_{k} ∈ ℕ,

Ψ(g, m_{1}, …, m_{k}) ↓ ⇔ P^{g}(m_{1}, …, m_{k}) halts

in which case Ψ(g, m_{1}, …, m_{k}) appears in R_{k+1}.

Example 1.11. The partial functional

Ψ(g, m) ≃ least n > m such that g(n) = 0

is computable, by the same program as in Example 1.8.

Remark 1.12. By the special case k = 0 of Definition 1.10, we now know what it means for a partial functional from ℕ^{ℕ} to ℕ to be computable. Likewise, there is an obvious way to define what it means for a partial functional from ℕ^{ℕ} to ℕ^{ℕ} to be computable. More generally, we have the following definition.

Definition 1.13. For k ≥ 0, a partial functional Ψ :⊆ ℕ^{ℕ} × ℕ^{k} → ℕ^{ℕ} is said to be (partial) computable, i.e., (partial) recursive, if there exists an oracle program P such that for all g, h ∈ ℕ^{ℕ} and all m_{1}, …, m_{k} ∈ ℕ,

Ψ(g, m_{1}, …, m_{k}) = h ⇔ ∀m (P^{g}(m_{1}, …, m_{1}, m) halts)

in which case h(m) appears in R_{k+2}.

2 Mass problems

Definition 2.1. Given f, g ∈ ℕ^{ℕ} we say that f is Turing reducible to g, abbreviated f ≤_{T} g, if f is g-computable. Equivalently, there exists a partial recursive functional (in the sense of Definition 1.13 with k = 0) Ψ :⊆ ℕ^{ℕ} → ℕ^{ℕ} such that f = Ψ(g).

Remark 2.2. Some basic facts about ≤_{T} are:

1. f ≤_{T} f.

2. f ≤_{T} g and g ≤_{T} h imply f ≤_{T} h.

Definition 2.3. A mass problem is a set P ⊆ ℕ^{ℕ}.

Definition 2.4. Let P, Q be mass problems. We say that P is weakly reducible to Q, abbreviated P ≤_{w} Q, if for all g ∈ Q there exists f ∈ P such that f ≤_{T} g.

Remark 2.5. By way of motivation, note that a mass problem is identified with its set of solutions. Thus, if P is a mass problem, a “solution” of P is an element of the set P. In these terms, weak reducibility of P to Q has the following natural interpretation: given any solution of Q, we can use it to compute some solution of P.

Remark 2.6. Some basic facts about ≤_{w} are:

1. P ≤_{w} P.

2. P ≤_{w} Q and Q ≤_{w} R imply P ≤_{w} R.

Definition 2.7. The weak degree of P, denoted deg_{w}(P), is the set of mass problems which are equivalent to P with respect to weak reducibility.

Details: We define P ≡_{w} Q if and only if P ≤_{w} Q and Q ≤_{w} P. Note that ≡_{w} is an equivalence relation on the set of all mass problems. Note that the set of all mass problems is just the powerset of ℕ^{ℕ}. For each mass problem P we define deg_{w}(P) to be the equivalence class of P under ≡_{w}. We write

D_{w} = the set of all weak degrees = Powerset(ℕ^{ℕ})/ ≡_{w}.

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

An alternative reducibility notion for mass problems is: Definition 2.8. Let P, Q be mass problems. We say that P is strongly reducible to Q, abbreviated P ≤_{s} Q, if there exists a partial recursive functional Ψ :⊆ ℕ^{ℕ} → ℕ^{ℕ} (in the sense of Definition 1.13 with k = 0) such that Ψ(g) ∈ P for all g ∈ Q. Remark 2.9. Clearly P ≤_{s} Q implies P ≤_{w} Q. To compare these reducibility notions, note that

P ≤_{s} Q ⇔ ∃Ψ (∀g ∈ Q) (Ψ(g) ∈ P)

while

P ≤_{w} Q ⇔ (∀g ∈ Q) ∃Ψ (Ψ(g) ∈ P).

Thus strong reducibility is a “uniform” variant of weak reducibility. Remark 2.10. Some basic facts about ≤_{s} are:

1. P ≤_{s} P.

2. P ≤_{s} Q and Q ≤_{s} R imply P ≤_{s} R. Definition 2.11. The strong degree of P, denoted deg_{s}(P), is the equivalence class of P under the equivalence relation ≡_{s} defined by P ≡_{s} Q if and only if P ≤_{s} Q and Q ≤_{s} P. We write

D_{s} = the set of all strong degrees = Powerset(ℕ^{ℕ})/ ≡_{s}

and D_{s} is partially ordered by letting deg_{s}(P) ≤ deg_{s}(Q) if and only if P ≤_{s} Q. Remark 2.12. An outline of the history of these concepts is as follows.

• Kolmogorov 1932: A “calculus of problems” (non-rigorous) as an interpretation of intuitionistic propositional calculus.

• Medvedev 1955: Defined mass problems, strong reducibility (also known as Medvedev reducibility and Medvedev degrees, or “degrees of difficulty”).

• Muchnik 1963: Defined weak reducibility and weak degrees (also known as Muchnik reducibility and Muchnik degrees).

• Later work by Skvortsova, Sorbi, Terwijn, …. Our principal reason for studying D_{w} and D_{s} is to use them as a tool for classifying unsolvable (that is, algorithmically unsolvable) mathematical problems. This is different from the original intuitionistic motivation of Kolmogorov and Medvedev.

Definition 2.13. A mass problem P is said to be solvable (i.e., algorithmically solvable) if P contains a recursive function. In other words, P ∩ REC ≠ ∅. Equivalently, deg_{w}(P) = 0 = the smallest degree in D_{w} and deg_{s}(P) = 0 = the smallest degree in D_{s}. Otherwise, the mass problem P is said to be unsolvable.

Examples 2.14. Some well-known examples of unsolvable problems are:

1. The Halting Problem

2. The Word Problem for Groups

3. Hilbert’s 10th Problem

4. The Entscheidungsproblem, i.e., the Validity Problem for predicate calculus

5. The problem of finding a completion of first-order arithmetic

3 Some basic theorems

In this section we note that some familiar basic theorems concerning partial recursive functions can be generalized straightforwardly to partial recursive functionals.

Definition 3.1. If P is an oracle program, we define the Gödel number of P, denoted #(P), as follows. View P as a finite sequence of numbered instructions, I_{1}, …, I_{l}, where I_{1} is the initial instruction. Then

#(P) = ∏_{m=1}^{l} p_{m}^{#(I_{m})}

where the Gödel numbers of the instructions are given by

# ([figure: R_{i}^{+}; I_{n}] ) = 3^{i} · 5^{n}

# ([figure: R_{i}^{−}; e; \begin{matrix}I_{n_{0}} \\ I_{n_{1}} \end{matrix}] ) = 2 · 3^{i} · 5^{n_{0}} · 7^{n_{1}}

# ([figure: R_{i}^{0}; I_{n}] ) = 4 · 3^{i} · 5^{n}

Note that the mapping # : {oracle programs} → ℕ is one-to-one.

Definition 3.2. If e = #(P) and k ≥ 0 define Φ_{e}^{(k)}(g, m_{1}, …, m_{k}) ≃ φ_{e}^{(k),g}(m_{1}, …, m_{k}) ≃ the content of R_{k+1} if and when P^{g}(m_{1}, …, m_{k}) halts, otherwise undefined.

Theorem 3.3 (The Enumeration Theorem). For each k ≥ 0, Φ_{e}^{(k)}(g, m_{1}, …, m_{k}) is a partial recursive functional of g, e, m_{1}, …, m_{k}.

Proof. This is a straightforward generalization of the usual non-oracle proof. Define State^{g}(e, m_{1}, …, m_{k}, s) by primitive recursion on s, etc.

Theorem 3.4 (The Parametrization Theorem). Let Ψ :⊆ ℕ^{ℕ} × ℕ^{k+1} → ℕ be a partial recursive functional. Then, we can find a primitive recursive function f : ℕ → ℕ such that

Φ_{f(m)}^{(k)}(g, m_{1}, …, m_{k}) ≃ Ψ(g, m, m_{1}, …, m_{k})

for all g ∈ ℕ^{ℕ} and all m, m_{1}, …, m_{k} ∈ ℕ.

Proof. We sketch the proof. Let P be an oracle program which computes Ψ. Define f(m) = #(P′_{m}) where P′_{m} is P with m hardwired. It can be shown that f is primitive recursive.

Theorem 3.5 (The Recursion Theorem). Let Ψ :⊆ ℕ^{ℕ}×ℕ^{k+1} → ℕ be a partial recursive functional. Then, we can find e ∈ ℕ such that

Φ_{e}^{(k)}(g, m_{1}, …, m_{k}) ≃ Ψ(g, e, m_{1}, …, m_{k})

for all g ∈ ℕ^{ℕ} and all m_{1}, …, m_{k} ∈ ℕ.

Proof. As usual.

4 The arithmetical hierarchy

In this section we generalize the arithmetical hierarchy from predicates on ℕ^{k} to predicates on ℕ^{ℕ} × ℕ^{k}.

Definition 4.1. For k ≥ 0, a predicate R ⊆ ℕ^{ℕ} × ℕ^{k} is said to be recursive (i.e., computable) if its characteristic function χ_{R} : ℕ^{ℕ} × ℕ^{k} → {0, 1} given by

χ_{R}(g, m_{1}, …, m_{k}) = \{ \begin{matrix}1 & if R(g, m_{1}, …, m_{k}) \\ 0 & if ¬ R(g, m_{1}, …, m_{k}) \end{matrix}

is recursive (i.e., computable).

Definition 4.2. For k ≥ 0 and n ≥ 1, a predicate S ⊆ ℕ^{ℕ} × ℕ^{k} is said to be Σ_{n}^{0} if it is of the form

S(g, m_{1}, …, m_{k}) ≡ ∃i_{1} ∀i_{2} ⋯ ∃/∀i_{n} R(g, m_{1}, …, m_{k}, i_{1}, …, i_{n})

where R ⊆ ℕ^{ℕ} × ℕ^{k+n} is recursive. Similarly, S is said to be Π_{n}^{0} if it is of the form

S(g, m_{1}, …, m_{k}) ≡ ∀i_{1} ∃i_{2} ⋯ ∃/∀i_{n} R(g, m_{1}, …, m_{k}, i_{1}, …, i_{n})

where R is recursive. We say that S is Δ_{n}^{0} if it is both Σ_{n}^{0} and Π_{n}^{0}.

Definition 4.3. Given f, g ∈ ℕ^{ℕ}, let f ⊕ g ∈ ℕ^{ℕ} be given by

\begin{aligned}(f ⊕ g)(2n) & = & f(n) \\ (f ⊕ g)(2n + 1) & = & g(n). \end{aligned}

We can then define one-to-one mappings (ℕ^{ℕ})^{k} → ℕ^{ℕ} by letting f_{1} ⊕ f_{2} ⊕ ⋯ ⊕ f_{k+1} = f_{1} ⊕(f_{2} ⊕⋯⊕f_{k}). In this way we can extend the arithmetical hierarchy to predicates S ⊆ (ℕ^{ℕ})^{k} × ℕ^{l}. Lemma 4.4. The arithmetical hierarchy has the following closure properties.

1. For n ≥ 1 the class Σ_{n}^{0} is closed under conjunction (∧), disjunction (∨), bounded number quantification (∃n < t, ∀n < t), and existential number quantification (∃n).

2. For n ≥ 1 the class Π_{n}^{0} is closed under conjunction, disjunction, bounded number quantification, and universal number quantification (∀n).

3. For n ≥ 1 the classes Σ_{n}^{0} and Π_{n}^{0} are closed under substitution of total recursive functionals. In detail:

(a) If F : (ℕ^{ℕ})^{k}×ℕ^{l} → ℕ is a total recusive functional in the sense of Definitions 1.10 and 4.3, and if the predicate S(g_{1}, …, g_{k}, m, m_{1}, …, m_{l}) is Σ_{n}^{0}, then the predicate

S(g_{1}, …, g_{k}, F (g_{1}, …, g_{k}, m_{1}, …, m_{l}), m_{1}, …, m_{l})  (1)

is Σ_{n}^{0}.

(b) If F : ℕ^{ℕ} ×ℕ^{k} → ℕ^{ℕ} is a total recusive functional in the sense of Definitions 1.13 and 4.3, and if the predicate S(g_{1}, …, g_{k}, g, m_{1}, …, m_{l}) is Σ_{n}^{0}, then the predicate (1) is Σ_{n}^{0}.

And similarly for Π_{n}^{0}.

4. S is Σ_{n}^{0} if and only if ¬ S is Π_{n}^{0}. Proof. Straightforward, as usual. Exercises 4.5. Let S ⊆ (ℕ^{ℕ})^{k} × ℕ^{l}.

1. Prove that S is Σ_{1}^{0} if and only if S = dom(Ψ) for some partial recursive functional Ψ :⊆ (ℕ^{ℕ})^{k} × ℕ^{l} → ℕ as in Definitions 1.10 and 4.3.

2. Prove that S is Δ_{1}^{0} if and only if S is recursive.

3. Prove that S is Π_{2}^{0} if and only if S = dom(Ψ) for some partial recursive

functional Ψ :⊆ (ℕ^{ℕ})^{k} × ℕ^{l} → ℕ^{ℕ} as in Definitions 1.13 and 4.3. Theorem 4.6. For each k ≥ 0 and n ≥ 1, we can find a universal Σ_{n}^{0} predicate U_{n,k} having the following properties:

1. U_{n,k} ⊆ ℕ^{ℕ} × ℕ^{k+1} and U_{n,k} is Σ_{n}^{0}.

2. Given a Σ_{n}^{0} predicate S ⊆ ℕ^{ℕ} × ℕ^{k}, we can find e ∈ ℕ such that

S(g, m_{1}, …, m_{k}) ≡ U_{n,k}(g, e, m_{1}, …, m_{k})

for all g ∈ ℕ^{ℕ} and all m_{1}, …, m_{k} ∈ ℕ.

Proof. As usual. Namely, U_{1,k}(g, e, m_{1}, …, m_{k}) ≡ Φ_{e}^{(k)}(g, m_{1}, …, m_{k}) ↓ and U_{n+1,k}(g, e, m_{1}, …, m_{k}) ≡ ∃m ¬ U_{n,k+1}(g, e, m_{1}, …, m_{k}, m).

Theorem 4.7. For each n ≥ 1 and k ≥ 0, the universal Σ_{n}^{0} predicate U_{n,k} is not Π_{n}^{0}.

Proof. As usual, by diagonalization.

Corollary 4.8. For each n ≥ 1 we can find a mass problem S_{n} ⊆ ℕ^{ℕ} which is Σ_{n}^{0} but not Π_{n}^{0}.

Proof. For instance S_{n} = {g | U_{n,0}(g^{−}, g(0))} where g^{−}(m) = g(m + 1).

5 Mass problems in the arithmetical hierarchy

In this section we present some initial results and problems concerning the weak and strong degrees of mass problems at various levels of the arithmetical hierarchy.

Theorem 5.1. If S ⊆ ℕ^{ℕ} is nonempty and Σ_{1}^{0}, then deg_{s}(S) = deg_{w}(S) = 0, i.e. S ∩ REC ≠ ∅.

Before proving this theorem, we consider finite sequences.

Definition 5.2. ℕ^{<ℕ} is the set of finite sequences of natural numbers. For g ∈ ℕ^{ℕ} and n ∈ ℕ we write g ↾ n = ⟨g(0), …, g(n − 1)⟩ ∈ ℕ^{<ℕ}. For σ ∈ ℕ^{<ℕ} we write |σ| = length of σ. Note that |g ↾ n| = n.

Remark 5.3 (The Finite Use Principle). If an oracle computation P^{g}(m_{1}, …, m_{k}) halts, it “uses” only a finite amount of information about the oracle g. Hence, for all sufficiently large n and all h ∈ ℕ^{ℕ}, if h ↾ n = g ↾ n then P^{h}(m_{1}, …, m_{k}) halts with the same output.

Proof of Theorem 5.1. Let S ⊆ ℕ^{ℕ} be Σ_{1}^{0}. By Exercise 4.5.1 let Ψ :⊆ ℕ^{ℕ} → ℕ be a partial recursive functional such that S = dom(Ψ). Let P be a program which computes Ψ. For all g we have g ∈ S ⇔ Ψ(g) ↓. Since S ≠ ∅, fix g ∈ S. Since Ψ(g) ↓, P^{g}(0) halts. By the Finite Use Principle, let n be so large that the computation P^{g}(0) uses only oracle information from g ↾ n. Then, for any h ∈ ℕ^{ℕ} such that g ↾ n = h ↾ n, P^{h}(0) also halts. Now let h ∈ ℕ^{ℕ} be a recursive function such that g ↾ n = h ↾ n. For example, we can define h(i) = g(i) for i < n and h(i) = 0 for i ≥ n. Since P^{h}(0) halts, Ψ(h) ↓, so h ∈ S. Hence S ∩ REC ≠ ∅, i.e., S is algorithmically solvable.

Theorem 5.4. We can find a nonempty Π_{1}^{0} set P ⊆ ℕ^{ℕ} such that deg_{w}(P) > 0. Equivalently, deg_{s}(P) > 0.

To prove this theorem, we use the following concept.

Definition 5.5. A function g ∈ ℕ^{ℕ} is called diagonally nonrecusive, abbreviated DNR, if g(m) ≄ φ_{m}^{(1)}(m) for all m. Here of course φ_{e}^{(1)} is the partial recursive function with index e, as in the Enumeration Theorem.

Remark 5.6. Diagonally nonrecursive functions are so called, because they are nonrecursive functions obtained by diagonalization against the recursive functions. To see this, let g ∈ ℕ^{ℕ} be DNR. If g were recursive, let e be an index of g, i.e., g(m) = φ_{e}^{(1)}(m) for all m. Setting m = e we obtain g(e) = φ_{e}^{(1)}(e), a contradiction.

Proof of Theorem 5.4. Let P = DNR = {g ∈ ℕ^{ℕ} | g is diagonally nonrecursive}. To see that DNR is Π_{1}^{0}, note that

g ∈ DNR ≡ ∀n (φ_{m}^{(1)}(m) ↓⇒ φ_{m}^{(1)}(m) ≠ g(m))
≡ ∀m ∀s ((State(m, m, s))_{0} = 0 ⇒ (State(m, m, s))_{2} ≠ g(m))

and this is Π_{1}^{0}, because the State function is primitive recursive. It is also clear that DNR is nonempty and contains only nonrecursive functions. Hence deg_{w}(DNR) > 0.

We now turn to higher levels of the arithmetical hierarchy.

Theorem 5.7. Given a Σ_{3}^{0} set S ⊆ ℕ^{ℕ}, we can find a Π_{1}^{0} set P ⊆ ℕ^{ℕ} such that P ≡_{w} S, i.e., deg_{w}(P) = deg_{w}(S).

Remark 5.8. In fact, P and S will be Turing degree isomorphic. This means that for all f ∈ P there exists g ∈ S such that f ≡_{T} g and vice versa. Note that Turing degree isomorphism implies weak equivalence.

In order to prove the theorem, we use the following notation.

Notation 5.9.

1. For f, g ∈ ℕ^{ℕ} define f ⊕ g ∈ ℕ^{ℕ} by letting (f ⊕ g)(2m) = f(m) and (f ⊕ g)(2m + 1) = g(m) for all m. Note that f ⊕ g “encodes” f and g.

2. For i ∈ ℕ and f ∈ ℕ^{ℕ}, define g = ⟨i⟩^{⌢}f ∈ ℕ^{ℕ} by letting g(0) = i and g(m + 1) = f(m) for all m. Note that ⟨i⟩^{⌢}f “encodes” i and f.

Proof of Theorem 5.7. Since S is Σ_{3}^{0}, let R(g, i, m, n) be a recursive predicate, R ⊆ ℕ^{ℕ} × ℕ^{3}, such that g ∈ S ≡ ∃i ∀m ∃n R(g, k, m, n). Now let

P = {⟨i⟩^{⌢}g ⊕ h | ∀m (h(m) = least n such that R(g, i, m, n))}.

Given g ∈ S, let i ∈ ℕ be such that ∀m ∃n R(g, i, m, n). Define h ∈ ℕ^{ℕ} by h(m) = least n such that R(g, i, m, n). Note that h ≤_{T} g. Thus we have ⟨i⟩^{⌢}g ⊕ h ∈ P and ≡_{T} g. Conversely, every member of P arises in this way, so P is Turing degree isomorphic to S.

Exercise 5.10. Given a Π_{2}^{0} set Q ⊆ ℕ^{ℕ}, find a Π_{1}^{0} set P ⊆ ℕ^{ℕ} such that deg_{s}(P) = deg_{s}(Q). In fact, P and Q are recursively homeomorphic. This means that there are recusive functionals Ψ : Q → P and Ψ^{−1} : P → Q. Note that recursive homeomorphism implies strong equivalence.

Remark 5.11. A possible research problem is to investigate what happens at higher levels of the arithmetical hierarchy. For n ≥ 4, can we find a Σ_{n}^{0} mass problem which is not weakly equivalent to any Σ_{n−1}^{0} mass problem?

Remark 5.12. We now consider the case n = 4. Consider the mass problem

Q = ℕ^{ℕ} \ REC = {g ∈ ℕ^{ℕ} | g is not recursive}.

Clearly Q ≠ ∅ and Q ∩ REC = ∅. Moreover Q is Π_{3}^{0}. To see this, note that

g ∈ REC ≡ ∃e ∀m (φ_{e}^{(1)}(m) ↓= g(m))
≡ ∃e ∀m ∃s ((State(e, m, s))_{0} = 0 ∧ (State(e, m, s))_{2} = g(m))

so REC is Σ_{3}^{0}. Since Q is the complement of REC, Q is Π_{3}^{0}. We shall show that, as a mass problem, Q is not weakly equivalent to any Σ_{3}^{0} mass problem. This will be a consequence of the following theorem.

Theorem 5.13. We can find g ∉ REC with the following property: for any Σ_{3}^{0} set S ⊆ ℕ^{ℕ}, if ∃f (f ≤_{T} g ∧ f ∈ S) then ∃f (f is recursive ∧ f ∈ S).

The proof of this theorem will be presented in terms of strings, trees, and genericity.

6 Strings and trees

Definition 6.1. A string is a finite sequence of natural numbers.

Notation 6.2. We let σ, τ, … denote strings. ℕ^{<ℕ} denotes the set of all strings. |σ| is the length of σ. If σ = ⟨σ(0), σ(1), …, σ(m − 1)⟩ where m = |σ| and τ = ⟨τ(0), τ(1), …, τ(n − 1)⟩ where n = |τ|, then the concatenation of σ and τ is

σ^{⌢}τ = ⟨σ(0), …, σ(m − 1), τ(0), …, τ(n − 1)⟩.

Note that |σ^{⌢}τ| = |σ| + |τ|.

If g ∈ ℕ^{ℕ}, then g ↾ n = ⟨g(0), …, g(n − 1)⟩ ∈ ℕ^{<ℕ}. We write τ ⊂ g if τ = g ↾ |τ|, i.e., τ is an initial segment of g. If n ≤ |τ|, we write τ ↾ n = ⟨τ(0), …, τ(n − 1)⟩. We write σ ⊆ τ if σ = τ ↾ n for some n ≤ |τ|. We write σ ⊂ τ if σ = τ ↾ n for some n < |τ|.

Remark 6.3. If τ_{0} ⊆ τ_{1} ⊆ ⋯ ⊆ τ_{n} ⊆ ⋯ and lim_{n→∞} |τ_{n}| = ∞ then

g = ⋃_{n=0}^{∞} τ_{n} ∈ ℕ^{ℕ}

Thus we can use strings to approximate oracles g ∈ ℕ^{ℕ}.

We now reformulate the finite use principle in terms of strings.

Definition 6.4. Φ_{e,s}^{(k)}(τ, m_{1}, …, m_{k}) ≃ φ_{e,s}^{(k),τ} (m_{1}, …, m_{k}) ≃ n means: e = #(P) for some program P, and P^{g}(m_{1}, …, m_{k}) halts with output n in R_{k+1} in ≤ s steps having used only oracle information from τ ⊂ g.

Remark 6.5. The finite use principle implies that φ_{e}^{(k),g}(m_{1}, …, m_{k}) ≃ n if and only if ∃s (φ_{e,s}^{(k),g↾s}(m_{1}, …, m_{k}) ≃ n).

Remark 6.6. We Gödel number strings with the one-to-one function # : ℕ^{<ℕ} → ℕ defined by #(σ) = ∏_{i<|σ|} p_{i}^{σ(i)+1} where p_{i} is the ith prime number. We frequently identify strings with their Gödel numbers. Thus, the functions σ, τ ↦ σ^{⌢}τ and σ, i ↦ σ(i) and σ ↦ |σ|, etc., are primitive recursive.

Lemma 6.7. The predicates φ_{e,s}^{(k),τ} (m_{1}, …, m_{k}) ≃ n and φ_{e,s}^{(k),τ} (m_{1}, …, m_{k}) ↓ are primitive recursive.

Proof. Routine. One shows that State^{τ} (e, m_{1}, …, m_{k}, s) is a primitive recursive function, etc.

We now consider trees.

Definition 6.8. A tree is a set T ⊆ ℕ^{<ℕ} which is closed under initial segments. This means: if τ ∈ T then σ ∈ T for all σ ⊂ τ. If T is a tree, a path through T is any f ∈ ℕ^{ℕ} such that f ↾ n ∈ T for all n.

Trees are often used to represent Π_{1}^{0} mass problems. Namely, a Π_{1}^{0} mass problem may be viewed as the problem of finding a path through a recursive tree, as explained in the following lemma.

Lemma 6.9. Let P ⊆ ℕ^{ℕ} be Π_{1}^{0}. Then we can find a recursive tree T ⊆ ℕ^{<ℕ} such that P = {f | f is a path through T }.

Proof. Since P is Π_{1}^{0}, we have P = {f ∈ ℕ^{ℕ} | ∀n R(f, n)} where R ⊆ ℕ^{ℕ} × ℕ is a recursive predicate. Define a partial recursive functional Ψ :⊆ ℕ^{ℕ} → ℕ by Ψ(f) ≃ the least n such that ¬ R(f, n). Then P = {f ∈ ℕ^{ℕ} | Ψ(f) ↑}. Let e be an index of Ψ. Then

P = {f ∈ ℕ^{ℕ} | φ_{e}^{(1),f}(0) ↑} = {f ∈ ℕ^{ℕ} | ∀s φ_{e,s}^{(1),f↾s}(0) ↑}

so let T = {σ ∈ ℕ^{<ℕ} | φ_{e,|σ|}^{(1),σ}(0) ↑}. T is recursive, because the predicate

φ_{e,|τ|}^{(k),τ} (m_{1}, …, m_{k}) ↓ is recursive. T is a tree, because if φ_{e,|τ|}^{(k),τ} (m_{1}, …, m_{k}) ↑

and σ ⊆ τ then φ_{e,|σ|}^{(1),σ}(m_{1}, …, m_{k}) ↑. Clearly P = {paths through T }.

For convenience we shall sometimes use the following notation for partial recursive functionals.

Definition 6.10. Φ̂_{e} : ℕ^{<ℕ} → ℕ^{<ℕ} is given by

Φ̂_{e}(τ) = ⟨φ_{e,|τ|}^{(1),τ} (0), …, φ_{e,|τ|}^{(1),τ} (l − 1)⟩

where l = the least m such that φ_{e,|τ|}^{(1),τ} (m) ↑ or m ≥ |τ|.

Remark 6.11. Note that Φ̂_{e} is a primitive recursive function from strings to strings. Moreover Φ̂_{e} is monotonic in the sense that σ ⊆ τ implies Φ̂_{e}(σ) ⊆ Φ̂_{e}(τ). Also, f ≤_{T} g if and only if f = ⋃_{n=0}^{∞} Φ̂_{e}(g ↾ n) for some e. Note also that, in the proof of Lemma 6.9, the tree T can be described more simply as T = T_{e} = {σ | |Φ̂_{e}(σ)| = 0}.

7 Genericity

Definition 7.1. A set of strings D ⊆ ℕ^{<ℕ} is said to be dense if (∀σ ∈ ℕ^{<ℕ}) (∃τ ∈ D) (σ ⊆ τ).

Remark 7.2. There is a standard topology for the Baire space. The basic open sets for this topology are N_{σ} = {f ∈ ℕ^{ℕ} | σ ⊂ f} where σ is a string. Any set of strings A ⊆ ℕ^{<ℕ} “encodes” an open set U_{A} = ⋃_{σ∈A} N_{σ}. All open sets are of this form. A set of strings D is dense (in the sense defined above) if and only if U_{D} is topologically dense in ℕ^{ℕ}.

Definition 7.3. A set of strings D ⊆ ℕ^{<ℕ} is said to be arithmetical if D occurs in the arithmetical hierarchy, i.e., D ∈ Σ_{∞}^{0} = ⋃_{n=1}^{∞} Σ_{n}^{0} (identifying strings with their Gödel numbers).

Definition 7.4. A point g ∈ ℕ^{ℕ} is said to meet D if (∃τ ∈ D) (τ ⊂ g). Equivalently, g ∈ U_{D}.

Definition 7.5. A point g ∈ ℕ^{ℕ} is called generic (i.e., arithmetically generic) if g meets all dense arithmetical sets of strings.

Lemma 7.6. Given a string τ, we can find a generic g such that τ ⊂ g.

Proof. Let D_{n}, n = 0, 1, 2, … be an enumeration of the dense arithmetical sets of strings. Let τ_{0} = τ. Given τ_{n}, let τ_{n+1} be a proper extension of τ_{n}, τ_{n+1} ⊃ τ_{n}, such that τ_{n+1} ∈ D_{n}. Let g = ⋃_{n=0}^{∞} τ_{n}. Clearly g is generic and τ ⊂ g.

Remark 7.7. The previous lemma may be viewed as a consequence of the Baire Category Theorem. The open sets U_{D_{n}}, n = 0, 1, 2, … are topologically dense in ℕ^{ℕ}. The Baire Category Theorem tells us that ⋂_{n=0}^{∞} U_{D_{n}} is topologically dense in ℕ^{ℕ}.

Lemma 7.8. If g ∈ ℕ^{ℕ} is generic, then g is not recursive (in fact, g is not arithmetical).

Proof. Given a recursive or arithmetical function f ∈ ℕ^{ℕ}, let D_{f} = {τ | τ ⊄ f}. Clearly D_{f} is dense. Moreover, since f is arithmetical (recursive), D_{f} is arithmetical (recursive). Hence g meets D_{f}, i.e., g ↾ n ≠ f ↾ n for some n. Hence g ≠ f.

Remark 7.9. Let g be generic. Although g is not computable, we are going to show that g cannot compute a solution of a Π_{1}^{0} mass problem unless the problem already has a computable solution.

Lemma 7.10. Let g ∈ ℕ^{ℕ} be generic, and let S ⊆ ℕ^{ℕ} be Σ_{3}^{0} such that S ∩ REC = ∅. Then S ∩ REC(g) = ∅.

Proof. By Theorem 5.7 we may assume that S is Π_{1}^{0}. By Lemma 6.9 let T ⊆ ℕ^{<ℕ} be a primitive recursive tree such that S consists of all paths through T. Given e we show that Φ̂_{e}(g) is not a path through T. This tells us that g does not compute a path through T.

For each e ∈ ℕ let D_{e} = {τ | ¬ ∃τ′ ⊇ τ such that Φ̂_{e}(τ) ⫋ Φ̂_{e}(τ′) ∈ T }.

We claim that D_{e} is dense, i.e., for all σ there exists τ ⊇ σ such that τ ∈ D_{e}. Suppose this does not hold. Let σ be such that τ ∉ D_{e} for all τ ⊇ σ. Recall that Φ̂_{e} : ℕ^{<ℕ} → ℕ^{<ℕ} is primitive recursive. Form a sequence σ = τ_{0} ⊂ τ_{1} ⊂ ⋯ ⊂ τ_{n} ⊂ τ_{n+1} ⊂ ⋯ such that ∀n (Φ̂_{e}(τ_{n}) ⫋ Φ̂_{e}(τ_{n+1}) ∈ T). This is a computable sequence of strings. Now let h = ⋃_{n=0}^{∞} τ_{n}. Then Φ̂_{e}(h) is a recursive path through T, contradicting the assumption that T has no recursive path. This proves the claim.

Moreover D_{e} is arithmetical (in fact Π_{1}^{0}). Since g is generic, ∃τ ⊂ g such that τ ∈ D_{e}. Hence ¬ ∃τ′ ⊃ τ such that Φ̂_{e}(τ) ⫋ Φ̂_{e}(τ′) ∈ T. In particular Φ̂_{e}(g) is not a path through T.

Theorem 7.11. We can find a nonrecursive g such that for all Σ_{3}^{0} sets S ⊆ ℕ^{ℕ}, S ∩ REC(g) ≠ ∅ implies S ∩ REC ≠ ∅.

Proof. This is immediate from Lemmas 7.6 and 7.8 and 7.10.

Corollary 7.12. For all Σ_{3}^{0} sets S ⊆ ℕ^{ℕ}, if S ∩ REC = ∅ then ∃g ∉ REC such that S ∩ REC(g) = ∅.

Corollary 7.13. Let Q = ℕ^{ℕ} \ REC. Then Q is Π_{3}^{0} and there is no Σ_{3}^{0} set S ⊆ ℕ^{ℕ} such that Q ≡_{w} S.

Proof. A Tarski/Kuratowski computation shows that Q is Π_{3}^{0}. Suppose S is Σ_{3}^{0} and Q ≡_{w} S. Clearly S ∩ REC = ∅. Hence, by the previous corollary, we can find g ∈ Q such that S ∩ REC(g) = ∅. Hence S ≰_{w} Q

8 Turing degrees and the jump operator

Recall that, for f, g ∈ ℕ^{ℕ}, f ≤_{T} g means that f is Turing computable using g as an oracle. We define f ≡_{T} g to mean that f ≤_{T} g, and g ≤_{T} f. Since ≤_{T} is reflexive and transitive, ≡_{T} is reflexive, transitive and symmetric. Thus ≡_{T} is an equivalence relation.

Definition 8.1. For f ∈ ℕ^{ℕ} we write deg_{T} (f) = the Turing degree of f = the equivalence class of f under ≡_{T}. We let D_{T} = the set of all Turing degrees. We partially order D_{T} by letting deg_{T} (f) ≤_{T} deg_{T} (g) if and only if f ≤_{T} g.

Remark 8.2. There are obvious embeddings of D_{T} into D_{w} and D_{s}, namely deg_{T} (f) ↦ deg_{w}({f}) and deg_{T} (f) ↦ deg_{s}({f}). These embeddings are oneto-one and order preserving, because f ≤_{T} g ⇔ {f} ≤_{w} {g} ⇔ {f} ≤_{s} {g}. We shall routinely identify Turing degrees with the corresponding weak and strong degrees under these embeddings.

Remark 8.3. We now mention some easy lattice-theoretical properties of D_{T}, D_{w}, and D_{s}.

1. In D_{w} and D_{s} and D_{T} there is a minimum degree 0 which is the degree of solvable problems.

2. In D_{w} and D_{s} and D_{T} there is a binary least upper bound operation. For a = deg_{w}(P) and b = deg_{w}(Q), the least upper bound of a and b is sup(a, b) = deg_{w}(P × Q) where P × Q = {f ⊕ g | f ∈ P, g ∈ Q}. And similarly for D_{s}. In particular, if a = deg_{T} (f) and b = deg_{T} (g) then sup(a, b) = deg_{T} (f ⊕ g). Moreover, our embeddings preserve the least upper bound operation. Thus D_{w} and D_{s} and D_{T} are upper semilattices.

3. D_{w} and D_{s} have a maximum element: ∞ = deg_{s}(∅) = deg_{w}(∅) = {∅}. However, D_{T} has no maximal element, because given a Turing degree a we can find a Turing degree a′ > a, namely a′ = the Turing jump of a. The Turing jump is explained below.

4. D_{w} and D_{s} are lattices. If a = deg_{w}(P) and b = deg_{w}(Q), the greatest lower bound of a and b in D_{w} is inf(a, b) = deg_{w}(⟨0⟩^{⌢}P ∪ ⟨1⟩^{⌢}Q) where ⟨i⟩^{⌢}P = {⟨i⟩^{⌢}f | f ∈ P }. And this also works for D_{s}.

Alternatively, for a = deg_{w}(P) and b = deg_{w}(Q) we have the simpler characterization inf(a, b) = deg_{w}(P ∪ Q). However, this does not work for D_{s}.

5. It can be shown that D_{T} is not a lattice, i.e., we can find a, b ∈ D_{T} such that there is no greatest lower bound of a and b in D_{T}. Also, we can find Turing degrees a, b, c ∈ D_{T} such that c = inf(a, b) in D_{T} but not in D_{w} or in D_{s}. In fact, if a and b are incomparable Turing degrees, then inf(a, b) in D_{w} or D_{s} can never be a Turing degree.

Exercises 8.4.

1. Show that deg_{w}(P ∪ Q) = inf(deg_{w}(P), deg_{w}(Q)).

2. Given an example where deg_{s}(P ∪ Q) ≠ inf(deg_{s}(P), deg_{s}(Q)).

3. Prove the assertions in previous remark.

Let U_{1,1} be a universal Σ_{1}^{0} predicate. For instance, U_{1,1}(g, e, m) ≡ Φ_{e}^{(1)}(g, e) ↓. This means that for any Σ_{1}^{0} set S ⊆ ℕ^{ℕ} × ℕ we can find an index e such that S(g, m) ≡ U_{1,1}(g, e, m) for all g ∈ ℕ^{ℕ} and all m ∈ ℕ.

Definition 8.5 (the Turing jump). Given g ∈ ℕ^{ℕ}, define g′ ∈ ℕ^{ℕ} as

g′(3^{e}5^{m}) = \{ \begin{matrix}1 & if U_{1,1}(g, e, m) holds, \\ 0 & otherwise. \end{matrix}

In other words, g′ is the characteristic function of the Halting Problem relative to g. We refer to g′ as the Turing jump of g.

Exercises 8.6.

1. Show that g <_{T} g′. In other words g′ ≰_{T} g but g ≤_{T} g′.

2. Show that the Turing jump operator is well defined and ≤_{T} -preserving on Turing degrees. In other words, g ≤_{T} h implies g′ ≤_{T} h′.

3. Given a mass problem P ⊆ ℕ^{ℕ}, we can define the Turing jump of P as P′ = {f′ | f ∈ P }. Clearly P ≤_{w} P′. Show that in fact P ≤_{s} P′.

4. Show that deg_{w}(P)′ = deg_{w}(P′) is well defined. Show that this jump operator on weak degrees is ≤-preserving and extends the Turing jump operator on Turing degrees.

5. Is deg_{s}(P)′ = deg_{s}(P′) well defined?

6. Give an example of a mass problem P such that P ≡_{w} P′.

7. Can you find an example of a mass problem P such that P ≡_{s} P′?

Definition 8.7. If a = deg_{T} (g), we define a′ = deg_{T} (g′). Then a′ is called jump of a. Note that a < a′ for all a ∈ D_{T}.

Remark 8.8. In particular, we have the Turing degrees

0 < 0′ < 0′′ < 0′′ < ⋯ < 0^{(n)} < · · · .  (2)

A famous result known as Post’s Theorem reads as follows:

For n ≥ 1, A ⊆ ℕ is Δ_{n}^{0} if and only if A ≤_{T} 0^{(n−1)}.

Thus we see that the sequence of Turing degrees in (2) is essentially the same as the arithmetical hierarchy of subsets of ℕ.

Here of course we are identifying A with it characteristic function χ_{A}. For A ⊆ ℕ we shall routinely write deg_{T} (A) = deg_{T} (χ_{A}).

A special case of Post’s Theorem says that A is Δ_{2}^{0} if and only if A ≤_{T} 0′ = the Halting Problem.

9 The Cantor space

Definition 9.1. The Cantor space: 2^{ℕ} = {0, 1}^{ℕ} = {X | X : ℕ → {0, 1}}.

Remark 9.2. The Cantor space {0, 1}^{ℕ} is compact, while the Baire space ℕ^{ℕ} is not compact.

Lemma 9.3. For each f ∈ ℕ^{ℕ}, we can find X ∈ {0, 1}^{ℕ} such that f ≡_{T} X.

Proof. We may identify points in {0, 1}^{ℕ} as characteristic functions of subsets of ℕ. Thus {0, 1}^{ℕ} is in one to one correspondence with Powerset(ℕ). Given f ∈ ℕ^{ℕ}, let X = X_{f} = the characteristic function of {3^{m}5^{n} | f(m) = n}. Clearly X_{f} ≡_{T} f.

Lemma 9.4. Let S ⊆ ℕ^{ℕ} be Σ_{n}^{0} where n ≥ 3 or Π_{n}^{0} where n ≥ 2. Then we can find S^{∗} ⊂ {0, 1}^{ℕ} at the same level of the arithmetical hierarchy such that S^{∗} is recursively homeomorphic to S.

Proof. We use the mapping f ↦ X_{f} from the proof of the previous lemma. Let S^{∗} = {X_{f} | f ∈ S}. As an exercise, check that S^{∗} is at the same level of the arithmetical hierarchy as S.

Definition 9.5. The space {0, 1}^{ℕ} = 2^{ℕ} = {X | X : ℕ → {0, 1}} is called the Cantor Space.

Remark 9.6. Obviously 2^{ℕ} ⊆ ℕ^{ℕ}, i.e., the Cantor space is a subspace of the Baire space. A significant difference between these spaces is that 2^{ℕ} is compact while ℕ^{ℕ} is not.

Notation 9.7. We write 2^{<ℕ} = {σ ∈ ℕ^{<ℕ} | σ is 01-valued} = {bitstrings}. For σ ∈ {0, 1}^{<ℕ} let N_{σ} = {X ∈ 2^{ℕ} | σ ∈ X}. The sets N_{σ}, σ ∈ {0, 1}^{<ℕ} form a basis for the topology of 2^{ℕ}. Compactness of 2^{ℕ} may be rephrased as follows:

If 2^{ℕ} = ⋃_{i=0}^{∞} N_{σ_{i}} then ∃n such that 2^{ℕ} = ⋃_{i=0}^{n} N_{σ_{i}}.

We use X, Y, … to denote points in the Cantor Space.

We now prove two important lemmas concerning quantification over the Cantor space. In the next two lemmas, we consider mixed predicates S ⊆ (ℕ^{ℕ})^{k} × (2^{ℕ})^{l} × ℕ^{m}.

Lemma 9.8 (bounding principle). Suppose S(X, i, −) is a Σ_{1}^{0} predicate where X ranges over 2^{ℕ}. Then

∀X ∃i S(X, i, −) ≡ ∃j ∀X (∃i < j) S(X, i, −).

Proof. ⇐: Obvious.

⇒: Let

\begin{aligned}S(X, i, −) & ≡ & Φ_{e}(X, i, −) ↓ \\ & ≡ & ∃s Φ_{e,s}(X ↾ s, i, −) ↓ . \end{aligned}

Then

\begin{aligned}∀X ∃i S(X, i, −) & ≡ & ∀X ∃i ∃s Φ_{e,s}(X ↾ s, i, −) ↓ \\ & ≡ & ∀X ∃i ∃s (i < s ∧ Φ_{e,s}(X ↾ s, i, −) ↓) \end{aligned}

so we have

2^{ℕ} = ⋃{N_{σ} | (∃i < |σ|) Φ_{e,|σ|}(σ, i, −) ↓}.

By compactness, ∃σ_{1}, …, σ_{n} as above such that

2^{ℕ} = ⋃_{k=1}^{n} N_{σ_{k}}

so let j = max_{1≤k≤n} |σ_{k}|. Then ∀X ∃i < j Φ_{e,j}(X ↾ j, i, −), Q.E.D. Lemma 9.9. Suppose S(X, −) be a Σ_{1}^{0} predicate where X ranges over 2^{ℕ}. Then, the predicate ∀X S(X, −) is again Σ_{1}^{0}.

A restatement of this lemma is: The class of Σ_{1}^{0} predicates is closed under universal quantification over the Cantor Space.

This is a useful supplement to the closure properties in Lemma 4.4. Proof. Again, let

\begin{aligned}S(X, −) & ≡ & Φ_{e}(X, −) ↓ \\ & ≡ & ∃s Φ_{e,s}(X ↾ s, −) ↓ . \end{aligned}

Then by the previous lemma we have

∀X S(X, −) ≡ ∀X ∃s Φ_{e,s}(X ↾ s, −) ↓
≡ ∃s ∀X Φ_{e,s}(X ↾ s, −)
≡

∃s \underbrace{∀σ (|σ| = s}_{bdd. quantifier} ⇒ \underbrace{Φ_{e,s}(σ, −) ↓)}_{rec. predicate}
Σ_{1}^{0}

and this completes the proof.

10 Basis Theorems in the Cantor space

Recall g′ = the Turing jump of g = the characteristic function of {3^{e}5^{m} | φ_{e}^{(1),g}(m) ↓}. Hence, for all Σ_{1}^{0,g} sets A ⊆ ℕ we have

A = dom(φ_{e}^{(1),g}) for some e
= W_{e}^{g}.

Hence A ≤_{T} g′ because χ_{A}(m) = g′(3^{e}5^{m}) for all m.

Theorem 10.1 (Kleene Basis Theorem). For all nonempty Π_{1}^{0} sets P ⊆ 2^{ℕ}, we can find X ∈ P such that X ≤_{T} 0′.

Proof. First consider a nonempty Π_{1}^{0} set P ⊆ ℕ^{ℕ}, the Baire space. We can associate with P a canonical tree

T = T_{P} = {f ↾ n | f ∈ P and n ∈ ℕ}.

Clearly T_{P} is a tree and P = {paths through T }. Note however that, in contrast to Lemma 6.9, T is not necessarily recursive. On the other hand, our tree T is tidy, i.e., (∀τ ∈ T) ∃i (τ^{⌢}⟨i⟩ ∈ T). Another name for tidy trees is “trees with no dead ends” meaning that every string in T has a proper extension in T. Because T is tidy, the leftmost path through T can be obtained as g = ⋃_{n=0}^{∞} τ_{n} where τ_{0} = ⟨⟩ (note that ⟨⟩ ∈ T because P is nonempty) and for all n, τ_{n+1} = τ_{n}^{⌢}⟨i_{n}⟩. Here i_{n} = the least i such that τ_{n}^{⌢}⟨i⟩ ∈ T. Clearly g ∈ P and g ≤_{T} T.

Now consider the case of a nonempty Π_{1}^{0} set P ⊆ 2^{ℕ}, the Cantor space. In this case our tidy tree T = T_{P} is Π_{1}^{0}. This is because τ ∈ T_{P} if and only if (∃X ∈ 2^{ℕ}) (X ∈ P ∧ τ ⊂ X) and this is Π_{1}^{0} in view of Lemma 9.9. Since T is a Π_{1}^{0} subset of 2^{<ℕ}, it follows that T ≤_{T} 0′. Hence the leftmost path through T is ≤_{T} 0′. Thus we have ∃X (X ∈ P, X ≤_{T} 0′), Q.E.D.

Corollary 10.2. If c is the weak degree of a nonempty Π_{1}^{0} subset of 2^{ℕ}, then c ≤ 0′.

Later we shall prove the following refinement of the Kleene Basis Theorem.

Theorem 10.3 (Low Basis Theorem). For all nonempty Π_{1}^{0} sets P ⊆ 2^{ℕ}, ∃X ∈ P such that X is low, i.e., X′ ≤_{T} 0′.

Corollary 10.4. If c is the weak degree of a nonempty Π_{1}^{0} subset of 2^{ℕ}, then c′ ≤ 0′.

Remark 10.5. We shall now show that the Kleene Basis Theorem fails badly for the Baire space. Namely, for each n, 0^{(n)} is a Π_{2}^{0} singleton, i.e., {0^{(n)}} is Π_{2}^{0}. Hence, we can find a Π_{1}^{0} singleton g_{n} ∈ ℕ^{ℕ} such that g_{n} ≡_{T} 0^{(n)}.

Consequently, each of the weak degrees 0^{(n)} for n ≥ 0 is the weak degree of a Π_{1}^{0} subset of ℕ^{ℕ}. Hence, by the Kleene Basis Theorem, the weak degrees of Π_{1}^{0} sets in 2^{ℕ} are properly included in the weak degrees of Π_{1}^{0} sets in ℕ^{ℕ}.

On the other hand, it can be shown that for each n ≥ 2 the weak degrees of Π_{n}^{0} sets in 2^{ℕ} are the same as the weak degrees of Π_{n}^{0} sets in ℕ^{ℕ}.

Theorem 10.6. For each n ≥ 0 we can find g_{n} ∈ ℕ^{ℕ} such that g_{n} ≡_{T} 0^{(n)} and g_{n} is a Π_{1}^{0} singleton.

Corollary 10.7. For each n ≥ 0 we can find a Π_{1}^{0} subset of ℕ^{ℕ} whose weak degree is 0^{(n)}.

For the proof of Theorem 10.6 we need several easy lemmas.

Lemma 10.8. The predicate J(g, h) ≡ g′ = h is Π_{2}^{0}.

Proof. We have J(g, h) ≡ ∀e ∀m ∀n (h(3^{e}5^{m}) = 1 if φ_{e}^{(1),g}(m) ↓, h(3^{e}5^{m}) = 0 if φ_{e}^{(1),g} ↑, and h(n) = 0 otherwise). This predicate is Π_{2}^{0} because the predicate φ_{e}^{(1),g}(m) ↓ is Σ_{1}^{0}.

Lemma 10.9. For each n ≥ 0 we can find a Π_{2}^{0} singleton X_{n} ∈ 2^{ℕ} such that X_{n} ≡_{T} 0^{(n)}.

Proof. For g ∈ ℕ^{ℕ} let us write g = (g)_{0} ⊕ (g)_{1} and note that the functionals g ↦ (g)_{0} and g ↦ (g)_{1} are recursive. Let X_{0} = the constant function 0, and for each n let X_{n+1} = X_{n} ⊕ X′_{n}.

We claim that X_{n} is a Π_{2}^{0} singleton, i.e., the singleton set {X_{n}} is Π_{2}^{0}. We prove this by induction on n. The base step n = 0 is trivial. For n + 1 we have Z = X_{n+1} if and only if (Z)_{0} = X_{n} and (Z)′_{0} = (Z)_{1}, i.e., J((Z)_{0}, (Z)_{1}). By inductive hypothesis the predicate Z = X_{n} is Π_{2}^{0}, and the previous lemma shows that J(X, Y) is Π_{2}^{0}. Thus, the predicate Z = X_{n+1} is Π_{2}^{0}. This completes the proof.

Lemma 10.10. If Q ⊆ ℕ^{ℕ} is Π_{2}^{0}, we can find a Π_{1}^{0} set P ⊆ ℕ^{ℕ} such that P and Q are recursively homeomorphic.

Proof. If Q = {g | ∀m ∃n R(g, m, n)} where R is recursive, let

P = {g ⊕ h | ∀m (h(m) = least n such that R(g, m, n))}.

Clearly P is Π_{1}^{0}. Moreover, the recursive functionals g ↦ g ⊕ h and g ⊕ h ↦ g provide a recursive homeomorphism between P and Q.

Corollary 10.11. If f is a Π_{2}^{0} singleton, we can find a Π_{1}^{0} singleton g such that f ≡_{T} g.

Proof of Theorem 10.6. We have seen that X_{n} ≡_{T} 0^{(n)} and X_{n} is a Π_{2}^{0} singleton. Hence, let g_{n} ≡_{T} X_{n} be a Π_{1}^{0} singleton. We then have g_{n} ≡_{T} X_{n} ≡_{T} 0^{(n)}, Q.E.D.

Exercises 10.12.

1. Show that if X is a Π_{1}^{0} singleton and X ∈ 2^{ℕ}, then X is recursive.

2. Show that g is a Σ_{3}^{0} singleton ⇔ g is a Π_{2}^{0} singleton.

3. Show that if g is a Π_{2}^{0} singleton and g ≡_{T} h then h is a Π_{2}^{0} singleton. Hence, 0^{(n)} is a Π_{2}^{0} singleton.

4. Define

0^{(ω)} = (the characteristic function of){3^{n}5^{i} | i ∈ 0^{(n)}}
= ⨁_{n=0}^{∞} 0^{(n)}

Show that 0^{(ω)} is a Π_{2}^{0} singleton.

5. Show that TrueSnt_{ℕ} is a Π_{2}^{0} singleton.

6. Show that 0^{(ω)} ≡_{T} TrueSnt_{ℕ}.

7. Show that if f is a Π_{2}^{0} singleton and g ≤_{T} f′ then f ⊕ g is a Π_{2}^{0} singleton.

8. Deduce that if 0^{(n)} ≤_{T} g ≤_{T} 0^{(n+1)} for some n, then g is a Π_{2}^{0} singleton.

9. Show that if g is generic then g is not a Π_{2}^{0} singleton. In fact, g does not belong to any countable Π_{n}^{0} set, for any n.

11 The Low Basis Theorem

In order to prove the Low Basis Theorem, we first develop some standard machinery. Definition 11.1. We define a standard method of indexing Π_{1}^{0} sets in 2^{ℕ}, namely

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

Note that P_{e} is a Π_{1}^{0} subset of 2^{ℕ}. We say that e is an index of P_{e}. Lemma 11.2.

1. P_{e} for e = 0, 1, 2, … is an enumeration of all Π_{1}^{0} subsets of 2^{ℕ}.

2. Given a Π_{1}^{0} predicate Q ⊆ 2^{ℕ} × ℕ^{k}, we can find a primitive recursive function α : ℕ^{k} → ℕ such that X ∈ P_{α(m_{1},...,m_{k})} ≡ Q(X, m_{1}, …, m_{k}) for all X ∈ 2^{ℕ} and all m_{1}, …, m_{k} ∈ ℕ.

3. Given x ∈ 2^{ℕ}, let H^{X} = the Halting Problem relative to X={e | φ_{e}^{(1),X}(0) ↓

} = {e | X ∉ P_{e}}. Then H^{X} ≡_{T} X′, the Turing jump of X. Proof. By the Enumeration Theorem and the Parametrization Theorem, let α̂ : ℕ → ℕ be primitive recursive such that

φ_{α̂(n)}^{(1),X}(0) ≃ φ_{(n)_{0}}^{(k),X}((n)_{1}, …, (n)_{k})

for all X ∈ 2^{ℕ} and n ∈ ℕ. Here we are using the notation p_{i} = the ith prime number, and (n)_{i} = the exponent of p_{i} in n. Thus n = ∏_{i=0}^{∞} p_{i}^{(n)_{i}} for all n ≥ 1.

Since Q is Π_{1}^{0}, let e be such that Q(X, m_{1}, …, m_{k}) ≡ φ_{e}^{(k),X}(m_{1}, …, m_{k}) ↑. Let α(m_{1}, …, m_{k}) = α̂(p_{0}^{e}p_{1}^{m_{1}} ⋯ p_{k}^{m_{k}}). Then X ∈ P_{α(m_{1},...,m_{k})} if and only if φ_{α(m_{1},...,m_{k})}^{(1),X}(0) ↑, i.e., φ_{α̂(p_{0}^{e}p_{1}^{m_{1}} ···p_{k}^{m_{k}})}^{(1),X}(0) ↑, i.e., φ_{e}^{(1),X}(m_{1}, …, m_{k}) ↑, i.e., Q(X, m_{1}, …, m_{k}). This proves part 2. Part 1 is the special case where k = 0.

For part 3, note first that e ∈ H^{X} ≡ X ∉ P_{e} ≡ φ_{e}^{(1),X}(0) ↓≡ 3^{e}5^{0} ∈ X′, so H^{X} ≤_{T} X′. Conversely, 3^{e}5^{m} ∈ X′ ≡ φ_{e}^{(1),X}(m) ↓≡ φ_{α̂(2^{e}3^{m})}^{(1),X}(0) ↓≡ α̂(2^{e}3^{m}) ∈ H^{X}, so X′ ≤_{T} H^{X}.

Remark 11.3. Part 2 of the lemma implies that various set-theoretical operations on Π_{1}^{0} sets are “primitive recursive in terms of the indices.” This important principle is illustrated in the following examples.

Example 11.4. We can find primitive recursive functions u, v, w, … such that P_{u(i,j)} = P_{i}∪P_{j}, P_{v(i,j)} = P_{i}∩P_{j}, P_{w(i,j)} = P_{i}×P_{j} = {X ⊕Y | X ∈ P_{i}, Y ∈ P_{j}}. For example, by part 2 of Lemma 11.2, let v be such that

X ∈ P_{v(i,j)} ≡ X ∈ P_{i} ∧ X ∈ P_{j}

for all X ∈ 2^{ℕ} and i, j ∈ ℕ.

Lemma 11.5. Let E be the set of indices of the empty set, i.e., E = {e | P_{e} = ∅}. Then E ≡_{T} 0′.

Proof. We have e ∈ E ≡ P_{e} = ∅ ≡ ¬ (∃X ∈ 2^{ℕ}) (X ∈ P_{e}), which is Σ_{1}^{0}. Hence, E ≤_{T} 0′. Conversely, 3^{e}5^{m} ∈ 0′ ≡ φ_{e}^{(1)}(m) ↓≡ φ_{e}^{(1),X}(m) ↓≡ φ_{α̂(2^{e}3^{m})}^{(1),X}(0) ↓ for all X. i.e., α̂(2^{e}3^{m}) ∈ E. So 0′ ≤_{T} E.

Theorem 11.6 (Low Basis Theorem). Let Q ⊆ 2^{ℕ} be Π_{1}^{0} and ≠ ∅. Then, we can find Y ∈ Q such that Y′ ≤_{T} 0′, i.e., Y is low.

Example 11.7. Let Q = DNR_{2} = {Y ∈ 2^{ℕ} | ∀n Y (n) ≄ φ_{n}^{(1)}(n)}. Clearly Q is Π_{1}^{0} and ≠ ∅ and has no recursive members. This shows that the Kleene Basis Theorem cannot be improved to say “Y is recursive.”

Proof of Theorem 11.6. Construct a sequence of nonempty Π_{1}^{0} sets. Q = Q_{0} ⊇ Q_{1} ⊇ Q_{2} ⊇ ⋯ ⊇ Q_{n} ⊇ ⋯ by letting Q_{0} = Q, Q_{n+1} = Q_{n} ∩ P_{n} if Q_{n} ∩ P_{n} ≠ ∅, and Q_{n+1} = Q_{n} otherwise. By induction on n, Q_{n} is ≠ ∅ and Π_{1}^{0}. By compactness, ⋂_{n=0}^{∞} Q_{n} ≠ ∅, so let Y ∈ ⋂_{n=0}^{∞} Q_{n}.

We claim that Y is low. To see this, note that the decision about whether n ∈ H^{Y} was made at stage n + 1. (See part 3 of Lemma 11.2.) We shall show that the entire construction is computable using 0′ as an oracle. We shall find a function g(n), g ≤_{T} 0′ such that Q_{n} = P_{g(n)} for all n. We start with g(0) = some e such that Q = P_{e}. We define g(n) inductively by letting g(n + 1) = v(g(n), n) if v(g(n), n) ∉ E, and g(n+1) = g(n) if v(g(n), n) ∈ E. Here v is as in Example 11.4. Clearly g is recursive in E, i.e., g ≤_{T} E ≡_{T} 0′. Moreover, for all n, n ∈ H^{Y} ⇔ v(g(n), n) ∉ E. Thus, Y′ ≡_{T} H^{Y} ≤_{T} g ≤_{T} 0′, i.e., Y is low.

12 The Hyperimmune-Free Basis Theorem

We shall now prove a variant of the Low Basis Theorem known as the Hyperimmune-Free Basis Theorem.

Definition 12.1. For f, g ∈ ℕ^{ℕ}, let us say that f is dominated by g if f(n) < g(n) for all sufficiently large n.

Definition 12.2. The domination ordering is defined as follows. X ≤_{dom} Y if (∀f ≤_{T} X) (∃g ≤_{T} Y) (f is dominated by g). This depends only on the Turing degrees of X and Y.

Definition 12.3. X is hyperimmune-free if X ≤_{dom} 0, i.e., every function which is computable from X is dominated by some computable function.

Theorem 12.4 (Hyperimmune-free Basis Theorem). Given Q ⊆ 2^{ℕ} which is Π_{1}^{0} and ≠ ∅, we can find Y ∈ Q which is hyperimmune-free.

Before proving the theorem, we first prove a standard lemma.

Lemma 12.5 (Σ_{1}^{0} Selection Lemma). Let S(−, m, n) be a mixed predicate, i.e., S ⊆ (ℕ^{ℕ})^{k} × (2^{ℕ})^{l} × ℕ^{i+2}. If S(−, m.n) is Σ_{1}^{0}, we can find a partial recursive functional (or function) Ψ(−, m) such that

1. Ψ(−, m) ↓⇔ ∃n S(−, m, n),

2. Ψ(−, m) ↓⇒ S(−, m, Ψ(−, m))

for all −, m. The functional Ψ is called a selector for S.

Proof. Intuitively, Ψ(−, m) is found by dove-tailing computations. Formally, let S(−, m, n) ≡ ∃j R(−, m, n, j) where R is a recursive predicate, and define Ψ(−, m) = (the least j such that R(−, m, (j)_{1}, (j)_{2}))_{1}. Clearly this works.

Proof of Theorem 12.4. As in the proof of the Low Basis Theorem, we construct a descending sequence Q = Q_{0} ⊇ Q_{1} ⊇ ⋯ ⊇ Q_{e} ⊇ Q_{e+1} ⊇ ⋯ where each Q_{e} is Π_{1}^{0} and ≠ ∅. We then let Y ∈ ⋂_{e=0}^{∞} Q_{e} and argue that Y is hyperimmune-free.

Stage 0. Let Q_{0} = Q.

Stage e + 1. Given Q_{e} which is Π_{1}^{0} and ≠ ∅, we have two cases.

Case 1: ∃m (∃X ∈ Q_{e}) (φ_{e}^{(1),X}(m) ↑).

In this case, choose such an m and let Q_{e+1} = {X ∈ Q_{e} | φ_{e}^{(1),X}(m) ↑}. Case 2: ∀m (∀X ∈ Q_{e}) (φ_{e}^{(1),X}(m) ↓). In this case we have

∀m ∀X ∃i (X ∉ Q_{e} ∨ φ_{e}^{(1),X}(m) ≃ i).

It follows by the Σ_{1}^{0} Bounding Lemma that

∀m ∃n ∀X (∃i < n) (X ∉ Q_{e} ∨ φ_{e}^{(1),X}(m) ≃ i).

Hence, by the Σ_{1}^{0} Selection Lemma 12.5, we can find a recursive function g such that

∀m ∀X (∃i < g(m)) (X ∉ Q_{e} ∨ φ_{e}^{(1),X}(m) ≃ i).

In other words,

(∀X ∈ Q_{e}) ∀m (φ_{e}^{(1),X}(m) ↓< g(m))

so in this case we let Q_{e+1} = Q_{e}.

To summarize, in case 1 φ_{e}^{(1),X}(m) is not total, and in case 2 φ_{e}^{(1),X}(m) is total and dominated by a recursive function g(m). Thus Y is hyperimmunefree.

Remark 12.6. We cannot combine the Kleene (or Low) Basis Theorem and the Hyperimmune-Free Basis Theorem into one theorem. In fact, the following exercise implies that if 0 <_{T} X ≤_{T} 0′ then X is not hyperimmune-free.

Exercise 12.7. Show that if X is hyperimmune-free and not recursive, then X is not a Π_{2}^{0} singleton. Hence X ≰_{T} 0′.

Here is a corollary of the Low Basis Theorem.

Corollary 12.8. If Q ⊆ 2^{ℕ} is Π_{1}^{0} and ≠ ∅, then deg_{w}(Q) < 0′.

Proof. By the Low Basis Theorem, there is a Y ∈ Q such that Y <_{T} 0′ and the corollary follows.

13 The lattice E_{w}

From now on we are going to focus on the lattice of weak degrees of nonempty Π_{1}^{0} sets in Cantor space:

E_{w} = {deg_{w}(P) | P ⊆ 2^{ℕ}, Π_{1}^{0}, ≠ ∅}.

Example 13.1. DNR_{2} = {X ∈ 2^{ℕ} | X is DNR} is Π_{1}^{0}, ≠ ∅ and deg_{w}(DNR_{2}) > 0.

This example shows that E_{w} is nontrivial. Note also that E_{w} is the simplest nontrivial class of weak degrees with respect to the arithmetical hierarchy.

Remark 13.2. Some obvious facts about E_{w} are:

1. 0 = deg(2^{ℕ}) ∈ E_{w}.

2. E_{w} contains degrees greater than 0.

3. E_{w} is a countable lattice.

We shall now show that E_{w} has a top degree.

Theorem 13.3. E_{w} has a top degree, denoted 1.

Proof. We use our standard enumeration of all Π_{1}^{0} subsets of 2^{ℕ}:

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

For Y ∈ 2^{ℕ} let (Y)_{e} ∈ 2^{ℕ} be defined by (Y)_{e}(m) = Y (3^{e}5^{m}). The naive idea of the proof will be to define

P = ∏_{e=0}^{∞} P_{e} = {Y | ∀e (Y)_{e} ∈ P_{e}}.

and note that P_{e} ≤_{s} P via Y ↦ (Y)_{e}. This naive idea doesn’t work, because P_{e} = ∅ for some e, hence P = ∅, and hence deg_{w}(P) ∉ E_{w}. We shall modify this construction to use only nonempty Π_{1}^{0} sets.

Use the tree representation of Π_{1}^{0} sets: let T_{e} = {τ ∈ 2^{<ℕ} | φ_{e,|τ|}^{(1),τ} (0) ↑}. Note:

1. P_{e} = {paths through T_{e}}.

2. P_{e} = ∅ ⇔ T_{e} is finite (by compactness).

Lemma 13.4 (Weak Konig’s Lemma). If T is a subtree of 2^{<ℕ}, T is infinite ⇔ T has an infinite path.

Proof. ⇐: Trivial

⇒: Suppose T has no infinite path. 2^{ℕ} = ⋃_{τ∉T} N_{τ}. By compactness, let τ_{1}, …, τ_{n} be a finite set of bitstrings such that 2^{ℕ} = ⋃_{i=1}^{n} N_{τ_{i}}. T ⊆ {initial segments of τ_{1}, …, τ_{n}}. Hence T is finite.

For all e let

S_{e} = {τ ∈ T_{e} of maximal length}.

In other words, S_{e} = {τ ∈ T_{e} | ¬ (∃σ ∈ T_{e}) (|σ| = |τ| + 1)}. Let

T_{e}^{+} = T_{e} ∪ \{τ^{⌢}⟨\underbrace{0, …, 0}_{n}⟩ | τ ∈ S_{e}, n ∈ ℕ\}.

Then T_{e}^{+} is an infinite subtree of 2^{<ℕ}. Let

P_{e}^{+} = {paths through T_{e}^{+}}.

Note that P_{e}^{+} ≠ ∅ for all e, and P_{e}^{+} = P_{e} if P_{e} ≠ ∅. Moreover, the P_{e}^{+} for e = 0, 1, 2, … are uniformly Π_{1}^{0} because T_{e}^{+} for e = 0, 1, 2, … are uniformly recursive. Let

P^{+} = ∏_{e=0}^{∞} P_{e}^{+} = {Y ∈ 2^{ℕ} | ∀e (Y)_{e} ∈ P_{e}^{+}}.

Clearly P^{+} is Π_{1}^{0}, and P_{e}^{+} ≤_{s} P^{+} via Y ↦ (Y)_{e}. Thus deg_{w}(P^{+}) is the top degree in E_{w}.

Remark 13.5. Let E_{s} = {strong degrees of nonempty Π_{1}^{0} subsets of 2^{ℕ}}. Then deg_{s}(P^{+}) = the top degree in E_{s}, by the same proof.

In the next section we shall obtain two interesting characterizations of the top degree 1 in E_{w} and E_{s}. Namely:

Theorem 13.6. deg_{w}(DNR_{2}) (respectively deg_{s}(DNR_{2})) is the top degree in E_{w} (respectively E_{s}).

Definition 13.7. Let CPA = {X ∈ 2^{ℕ} | X encodes a complete consistent extension of Peano Arithmetic}.

Theorem 13.8. deg_{w}(CPA) (respectively deg_{s}(CPA)) is the top degree in E_{w} (respectively E_{s}).

14 Some mass problems of degree 1

In this section we present two interesting mass problems of degree 1.

Definition 14.1. Let A, B ⊆ ℕ be recursively enumerable. We say that X ∈ 2^{ℕ} separates A and B if X(n) = 1 for all n ∈ A, and X(n) = 0 for all n ∈ B. We define

Sep(A, B) = {X ∈ 2^{ℕ} | X separates A, B}.

Note that Sep(A, B) is a Π_{1}^{0} subset of 2^{ℕ}: X ∈ Sep(A, B) ≡ ∀n ((n ∈ A ⇒ X(n) = 1) ∧ (n ∈ B ⇒ X(n) = 0)). Viewed as mass problems, Π_{1}^{0} subsets of 2^{ℕ} of this form are called separation problems.

Lemma 14.2. Let Q ⊆ 2^{ℕ} be nonempty Π_{1}^{0}. Then, we can find disjoint recursively enumerable sets A, B ⊆ ℕ such that Q ≤_{s} Sep(A, B).

In other words, every Π_{1}^{0} mass problem in the Cantor space is strongly reducible to a separation problem.

Proof. Consider the predicate

S(σ, i) ≡ σ ∈ 2^{<ℕ} ∧ i < 2 ∧ N_{σ^{⌢}⟨i⟩} ∩ Q = ∅.

By Lemma 9.9 this predicate is Σ_{1}^{0}. By the Σ_{1}^{0} Selection Lemma 12.5 let ψ(σ) be a partial recursive function which is a selector for this predicate. For i = 0, 1 let A_{i} = {σ ∈ 2^{<ℕ} | ψ(σ) ≃ i}. Clearly A_{0} and A_{1} are disjoint and Σ_{1}^{0}, i.e., recursively enumerable. We shall prove that Q ≤_{s} Sep(A_{0}, A_{1}).

First, suppose σ ∈ 2^{<ℕ} is such that N_{σ} ∩ Q ≠ ∅. We claim that N_{σ^{⌢}⟨X(σ)⟩} ∩ Q ≠ ∅ for all X ∈ Sep(A_{0}, A_{1}). To see this, note first that N_{σ^{⌢}⟨i⟩} ∩ Q ≠ ∅ for at least one of i = 0, 1. If N_{σ^{⌢}⟨0⟩} ∩ Q = ∅, it follows that N_{σ^{⌢}⟨1⟩} ∩ Q ≠ ∅, hence S(σ, 0) ∧ ¬ S(σ, 1), hence ψ(σ) = 0, hence σ ∈ A_{0}, hence X(σ) = 1, hence N_{σ^{⌢}⟨X(σ)⟩} ∩ Q ≠ ∅. Similarly, if N_{σ^{⌢}⟨1⟩} ∩ Q = ∅, it follows that N_{σ^{⌢}⟨0⟩} ∩ Q ≠ ∅, hence S(σ, 1) ∧ ¬ S(σ, 0), hence ψ(σ) = 1, hence σ ∈ A_{1}, hence X(σ) = 0, hence N_{σ^{⌢}⟨X(σ)⟩} ∩ Q ≠ ∅. This proves our claim.

Consider the recursive functional Ψ : Sep(A_{0}, A_{1}) → 2^{ℕ} defined by Ψ(X) = Y where Y (n) = X(Y ↾ n) for all n. By the previous claim plus induction on n starting with N_{⟨⟩} ∩ Q ≠ ∅, we have N_{Y ↾n} ∩ Q ≠ ∅ for all n and all X ∈ Sep(A_{0}, A_{1}). Since Q is closed, it follows that Y ∈ Q. Thus Ψ : Sep(A_{0}, A_{1}) → Q and Q ≤_{s} Sep(A_{0}, A_{1}), Q.E.D.

Remark 14.3. Recall that DNR_{2} is the set of X ∈ 2^{ℕ} such that X is diagonally nonrecursive. Note that DNR_{2} may be viewed as a separation problem, namely DNR_{2} = Sep(K_{0}, K_{1}) where K_{i} = {m | φ_{m}^{(1)}(m) ≃ i}. The following lemma says that Sep(K_{0}, K_{1}) is a “universal separation problem.”

Lemma 14.4. If A, B are recursively enumerable and A∩B = ∅, then Sep(A, B) ≤_{s} Sep(K_{0}, K_{1}).

Proof. Consider the partial recursive function

ψ(m) ≃ \{ \begin{matrix}0 & if m ∈ A, \\ 1 & if m ∈ B. \end{matrix}

By the Parametrization Theorem, let α be a primitive recursive function such that φ_{α(m)}^{(1)}(n) ≃ ψ(m) for all m, n. Then

m ∈ A ⇔ ψ(m) = 0 ⇔ φ_{α(m)}^{(1)}(α(m)) = 0 ⇔ α(m) ∈ K_{0}

and

m ∈ B ⇔ ψ(m) = 1 ⇔ φ_{α(m)}^{(1)}(α(m)) = 1 ⇔ α(m) ∈ K_{1}

so X ∈ Sep(K_{0}, K_{1}) implies X∘α ∈ Sep(A, B). Thus Sep(A, B) ≤_{s} Sep(K_{0}, K_{1}) via the recursive functional X ↦ X ∘ α. Lemma 14.5. For any nonempty Π_{1}^{0} set Q ⊆ 2^{ℕ} we have Q ≤_{s} DNR_{2}. Proof. By Lemma 14.2 we have Q ≤_{s} Sep(A, B) where A, B are disjoint and recursively enumerable. By Remark 14.3 and Lemma 14.4 we have Sep(A, B) ≤_{s} DNR_{2}. It now follows that Q ≤_{s} DNR_{2}, Q.E.D. Theorem 14.6. deg_{w}(DNR_{2}) = 1 in E_{w}. In fact, deg_{s}(DNR_{2}) = 1 in E_{s}. Proof. Clearly DNR_{2} is a nonempty Π_{1}^{0} subset of 2^{ℕ}. Then, Lemma 14.5 implies that deg_{w}(DNR_{2}) = 1 in E_{w} and deg_{s}(DNR_{2}) = 1 in E_{s}. Remark 14.7. Let Q ⊆ 2^{ℕ} be nonempty Π_{1}^{0}. We have the following additional results, which will not be proved here.

1. We can find a recursive functional Ψ : DNR_{2} → Q which is onto Q.

2. If deg_{s}(Q) = 1 in E_{s} then Q is recursively homeomorphic to DNR_{2}.

3. If deg_{w}(Q) = 1 in E_{w} then Q is Turing degree isomorphic to DNR_{2}. Results 1 and 2 are due to Simpson 2000, while result 3 is due to Simpson 2004.

We now turn to the study of mass problems associated with theories in the predicate calculus. Definition 14.8. Let L be a recursive language, and assume a standard Gödel numbering # : {L-sentences} → ℕ. If T is an L-theory, let Thm_{T} be the set of Gödel numbers of theorems of T. In other words,

Thm_{T} = {#(B) | B is an L-sentence and T ⊢ B}.

We say that T is decidable if Thm_{T} is recursive.

Let S be a consistent L-theory. A completion of S is a complete, consistent L-theory T such that T ⊇ S. Define

Cmp_{S} = {Thm_{T} | T is a completion of S}.

By Lindenbaum’s Lemma, we have Cmp_{S} ≠ ∅. We sometimes identify Thm_{T} with its characteristic function. With this identification, we have Cmp_{S} ⊆ 2^{ℕ}. It can be shown that Cmp_{S} is a closed subset of 2^{ℕ}.

Lemma 14.9. Let L and S be as in Definition 14.8. If S is consistent and recursively axiomatizable, Cmp_{S} is a nonempty Π_{1}^{0} subset of 2^{ℕ}.

Proof. For X ∈ 2^{ℕ} we have X ∈ Cmp_{S} if and only if

(∀L-sentences B) (X(#(B)) = 1 ⇔ X(#(¬ B) = 0)

and

(∀L-sentences B) (if B is an axiom of S then X(#(B)) = 1)

and …. The details are left to the reader.

Exercise 14.10. Given a nonempty Π_{1}^{0} set Q ⊆ 2^{ℕ}, construct a consistent, recursively axiomatizable theory S such that Cmp_{S} is recursively homeomorphic to Q.

Remark 14.11. Exercise 14.10 is rather easy. A more difficult result due to Hanf and Peretyatkin says that, in Exercise 14.10, S can be chosen to be finitely axiomatizable.

Definition 14.12. Recall that PA is Peano Arithmetic, a.k.a., Z_{1}, a.k.a., firstorder arithmetic. The language of PA is L_{Q} = {+, ·, 0, S, =} where Q is Robinson’s weak theory of arithmetic. We have PA = Q + the induction scheme consisting of the universal closure of

(A[x/0] ∧ ∀x (A ⇒ A[x/Sx])) ⇒ ∀x A

where A ranges over L_{Q}-formulas. Let CPA = Cmp_{PA}.

Remark 14.13. Viewed as a mass problem, CPA is the problem of finding a completion of PA. A motivation for considering this problem is the Gödel Incompleteness Theorem, which says that PA itself is incomplete. Recall also the theorems of Gödel, Tarski, and Rosser which say that PA has no decidable completion. In other words, viewed as a mass problem, CPA is unsolvable, i.e., deg_{w}(CPA) > 0. We shall now improve this result by showing that deg_{w}(CPA) = 1.

Lemma 14.14. CPA is a nonempty Π_{1}^{0} subset of 2^{ℕ}.

Proof. This is a special case of Lemma 14.9 since PA is consistent and recursively axiomatizable.

Lemma 14.15. DNR_{2} ≤_{s} CPA.

Proof. Recall that DNR_{2} = Sep(K_{0}, K_{1}). For i = 0, 1 let A_{i} be a Σ_{1} formula which defines K_{i} over the standard model (ℕ, +, ·, 0, S, =). It is well known that every true Σ_{1} sentence is provable in PA. Thus K_{i} = \{m ∈ ℕ | PA ⊢ A_{i}[x/\underline{m}]\} for i = 0, 1. Let us also assume that PA ⊢ ¬ (A_{0}[x/\underline{m}] ∧ A_{1}[x/\underline{m}]) for each m ∈ ℕ. Since K_{0} ∩ K_{1} = ∅, it is straightforward to choose the formulas A_{0} and A_{1} to have this additional property.

Given X ∈ CPA, let X = Thm_{T} where T is a completion of PA. Define Ψ(X) = Y where Y is the characteristic function of \{m ∈ ℕ | PA ⊢ A_{0}[x/\underline{m}]\}. Clearly Y ∈ Sep(K_{0}, K_{1}). Moreover Ψ : CPA → Sep(K_{0}, K_{1}) is a recursive functional, so Sep(K_{0}, K_{1}) ≤_{s} CPA. This completes the proof.

Lemma 14.16. For any nonempty Π_{1}^{0} set Q ⊆ 2^{ℕ} we have Q ≤_{s} CPA.

Proof. By Lemmas 14.5 and 14.15 we have Q ≤_{s} DNR_{2} and DNR_{2} ≤_{s} CPA. It follows that Q ≤_{s} CPA, Q.E.D.

Theorem 14.17. deg_{w}(CPA) = 1 ∈ E_{w}. In fact, deg_{s}(CPA) = 1 ∈ E_{s}.

Proof. By Lemma 14.9 CPA is a nonempty Π_{1}^{0} subset of 2^{ℕ}. Hence deg_{w}(CPA) ∈ E_{w} and deg_{s}(CPA) ∈ E_{s}. It now follows by Lemma 14.16 that deg_{w}(CPA) = 1 ∈ E_{w} and deg_{s}(CPA) = 1 ∈ E_{s}.

Remark 14.18. Using the Rosser trick, one can modify the proof and replace PA by any consistent, recursively axiomatizable theory S ⊇ Q. Thus deg_{w}(Cmp_{S}) = 1 ∈ E_{w} and deg_{s}(Cmp_{S}) = 1 ∈ E_{s} for all such S. In particular, the problem of finding a completion of S is of the same degree of unsolvability no matter whether S is Q, Z_{1}, Z_{2}, ZFC, etc.

Remark 14.19. In the literature, Turing degrees of the form deg_{T} (X) where X ∈ CPA are sometimes called PA-degrees. However, by Remark 14.18 they could equally well be called Q-degrees, or Z_{2}-degrees, or ZFC-degrees, etc.

15 Martin-Löf randomness

We now present Martin-Löf’s rigorous definition of what it means for a point X ∈ 2^{ℕ} to be random. Compare Turing’s rigorous definition of what it means for a function to be computable. Although Martin-Löf’s concept of randomness is not as compelling as Turing’s concept of computability, it is a good attempt. The Martin-Löf concept has many nice properties which make it reasonably convincing as a rigorous explanation of randomness.

Notation 15.1. For σ ∈ 2^{<ℕ} = {bitstrings} we write

N_{σ} = {X ∈ 2^{ℕ} | σ ⊂ X}.

The “fair coin” probability measure on 2^{ℕ} is defined by

μ(N_{σ}) = \frac{1}{2^{|σ|}} .

Definition 15.2. A set S ⊆ 2^{<ℕ} is said to be prefix-free if there are no σ, τ ∈ S such that σ ⊂ τ. If S is prefix-free, we clearly have

μ ( ⋃_{σ∈S} N_{σ}) = ∑_{σ∈S} \frac{1}{2^{|σ|}} .

Given a Σ_{1}^{0} set U ⊆ 2^{ℕ}, let e be an index for U, i.e.,

U = U_{e} = {X ∈ 2^{ℕ} | φ_{e}^{(1),X}(0) ↓}.

Let S = S_{e} = {σ ∈ 2^{<ℕ} | φ_{e,|σ|}^{(1),σ}(0) ↓ and there is no ρ ⊂ σ such that φ_{e,|ρ|}^{(1),ρ}(0) ↓}. Then U = ⋃_{σ∈S} N_{σ} and S is prefix-free and primitive recursive (uniformly in e), and

μ(U) = ∑_{σ∈S} \frac{1}{2^{|σ|}} .

Note that the real number μ(U) is left recursively enumerable, i.e., it is the limit of a non-decreasing recursive sequence of rational numbers. Let

U_{s} = U_{e,s} = {X ∈ 2^{ℕ} | φ_{e,s}^{(1),X↾s}(0) ↓}.

Then U_{e} = ⋃_{s=0}^{∞} U_{e,s} and μ(U_{e,s}) is a rational number and the predicates μ(U_{e,s}) = r, μ(U_{e,s}) < r are primitive recursive, and

U_{e,0} ⊆ U_{e,1} ⊆ ⋯ ⊆ U_{e,s} ⊆ U_{e,s+1} ⊆ ⋯

and μ(U_{e}) = lim_{s} μ(U_{e,s}).

Recall some measure-theoretic facts:

• μ is countably additive, etc.

• μ is regular. This means: if S ⊆ 2^{ℕ} is measurable, then

μ(S) = inf{μ(U) | U open,U ⊇ S}.

In particular, if μ(S) = 0 then there is a sequence of open sets V_{n} ⊆ 2^{ℕ} such that S ⊆ V_{n} and μ(V_{n}) ≤ 1/2^{n} for all n.

Recall also: A set U ⊆ 2^{ℕ} is open ⇔ U is Σ_{1}^{0,g} for some oracle g. Thus we think of Σ_{1}^{0} sets U ⊆ 2^{ℕ} as “effectively open” sets.

Definition 15.3. We say that S ⊆ 2^{ℕ} is effectively null (i.e., effectively of measure 0) if we can find a uniformly Σ_{1}^{0} sequence of sets V_{n} ⊆ 2^{ℕ}, n ∈ ℕ such that S ⊆ ⋂_{n=0}^{∞} V_{n} and μ(V_{n}) ≤ 1/2^{n} for all n.

Definition 15.4 (Martin-Löf, 1966). X ∈ 2^{ℕ} is random if X does not belong to any effectively null set.

A test for randomness is a uniformly Σ_{1}^{0} sequence of sets V_{n} ⊆ 2^{ℕ}, n = 0, 1, 2, …, such that μ(V_{n}) = 1/2^{n} for all n. We say that X passes the test if X ∉ ⋂_{n=0}^{∞} V_{n}. Thus, X is random ⇔ X passes all tests for randomness. Let

R_{1} = {X ∈ 2^{ℕ} | X is random}.

Lemma 15.5. μ(R_{1}) = 1. Hence, random points exist.

Proof. There are only countably many tests for randomness. For each such test, we have μ(⋂_{n=0}^{∞} V_{n}) = 0 because μ(V_{n}) ≤ 1/2^{n}. Hence, by countable additivity, μ(R_{1}) = 1.

Lemma 15.6. If X is random, X is not recursive.

Proof. Let A ∈ 2^{ℕ} be recursive. Let V_{n} = N_{A↾n}. Clearly V_{n} is uniformly Σ_{1}^{0} and μ(V_{n}) = 1/2^{n}, hence the V_{n}’s form a Martin-Löf test, hence X ∉ ⋂_{n} V_{n}, i.e., X passes the test. Hence ∃n (X ↾ n ≠ A ↾ n), i.e., X ≠ A.

Exercise 15.7. Let X ∈ 2^{ℕ} be random. Prove that if P ⊆ 2^{ℕ} is Π_{1}^{0} of measure 0, then X ∉ P. In other words, X does not belong to any Π_{1}^{0} set of measure 0. An X with this property is called weakly random.

Exercises 15.8. Let X ∈ 2^{ℕ} be random. Then:

1. X obeys the Strong Law of Large Numbers, i.e.,

lim_{n→∞} \frac{∑_{i=0}^{n−1} X(i)}{n} = \frac{1}{2}.

2. Furthermore, we can obtain bounds on the rate of convergence, e.g.,

|\frac{∑_{i=0}^{n−1} X(i)}{n} − \frac{1}{2}| < \sqrt{\frac{log n}{n}}

for all but finitely many n.

3. X obeys the Law of the Iterated Logarithm:

lim sup_{n→∞} \frac{|\frac{∑_{i=0}^{n−1} X(i)}{n} − \frac{1}{2}|}{\sqrt{\frac{n}{2} log log n}} = 1.

A typical consequence of this is that

\frac{∑_{i=0}^{n−1} X(i)}{n}

is > 1/2 for infinitely many n and < 1/2 for infinitely many n.

The idea here is, any “reasonable” statistical property which holds for almost all X ∈ 2^{ℕ} holds for all random X. This is because each “reasonable” statistical property is embodied by a Martin-Löf test.

An important theorem concerning randomness is the following.

Lemma 15.9 (Martin-Löf). We can find a universal test for randomness.

This means: there is a uniformly Σ_{1}^{0} sequence of sets U_{n} ⊆ 2^{ℕ} such that μ(U_{n}) ≤ 1/2^{n} for all n, and if V_{n}, n ∈ ℕ is any other such sequence, then ⋂_{n=0}^{∞} V_{n} ⊆ ⋂_{n=0}^{∞} U_{n}.

In other words, the union of all effectively null sets is an effectively null set.

Proof. Let V_{i}, i ∈ ℕ be a standard uniform enumeration of all Σ_{1}^{0} subsets of 2^{ℕ}:

V_{i} = {X ∈ 2^{ℕ} | φ_{i}^{(1),X}(0) ↓}

Note that V_{i} = 2^{ℕ} \ P_{i} where P_{i} is our standard enumeration of the Π_{1}^{0} subsets of 2^{ℕ}. Let V_{i,s} = “the part of V_{i} which is enumerated by stage s,” i.e.,

V_{i,s} = {X ∈ 2^{ℕ} | φ_{i,s}^{(1),X↾s}(0) ↓}.

Note that V_{i,s} is uniformly Σ_{1}^{0} and

V_{i,0} ⊆ V_{i,1} ⊆ ⋯ ⊆ V_{i,s} ⊆ ⋯

and V_{i} = ⋃_{s=0}^{∞} V_{i,s}. Moreover μ(V_{i,s}) is a rational number and is primitive recursive as a function of i and s.

Given a rational number r, let

V_{i}[r] = “V_{i} enumerated so long as its measure is ≤ r”
= ⋃_{μ(V_{i,s})≤r} V_{i,s}

= \{X ∈ 2^{ℕ} | ∃s (\underbrace{μ(V_{i,s}) ≤ r}_{recursive} ∧ \underbrace{X ∈ V_{i,s}}_{recursive})\}.

Note the following properties:

1. V_{i}[r] is uniformly Σ_{1}^{0}.

2. V_{i}[r] ⊆ V_{i}.

3. μ(V_{i}[r]) ≤ r.

4. If μ(V_{i}) ≤ r then V_{i}[r] = V_{i}.

Now, given e, n ∈ ℕ, let

Ũ_{e,n} = \{ \begin{matrix}V_{i}[1/2^{n}] & if φ_{e}^{(1)}(n) ≃ i, \\ ∅ & if φ_{e}^{(1)}(n) ↑ . \end{matrix}

Clearly the sets Ũ_{e,n} are uniformly Σ_{1}^{0} and μ(Ũ_{e,n}) ≤ 1/2^{n}. Thus Ũ_{e,n} for n = 0, 1, 2, … is a Martin-Löf test.

Furthermore, we claim that every Martin-Löf test arises in this way.

To prove this claim, let W_{n}, n = 0, 1, 2, …, be an arbitrary Martin-Löf test. Thus W_{n} is uniformly Σ_{1}^{0} and μ(W_{n}) ≤ 1/2^{n}. Since W_{n} is uniformly Σ_{1}^{0}, let Ψ be a partial recursive functional such that X ∈ W_{n} ≡ Ψ(X, n) ↓. By the Parametrization Theorem, let α(n) be a primitive recursive function such that φ_{α(n)}^{(1),X}(0) ≃ Ψ(X, n). Then X ∈ V_{α(n)} ≡ φ_{α(n)}^{(1),X}(0) ↓≡ Ψ(X, n) ↓≡ X ∈ W_{n}.

Thus V_{α(n)} = W_{n} for all n. Now let e be an index of α, i.e., φ_{e}^{(1)}(n) ≃ α(n) for all n. Then for all n we have V_{α(n)} = W_{n}, hence μ(V_{α(n)}) ≤ 1/2^{n}, hence Ũ_{e,n} = V_{α(n)}[1/2^{n}] = V_{α(n)} = W_{n}. This proves the claim.

Finally let

U_{n} = ⋃_{e} Ũ_{e,e+n+1}.

Note U_{n} is uniformly Σ_{1}^{0} and

μ(U_{n}) ≤ ∑_{e=0}^{∞} μ(Ũ_{e,e+n+1}) ≤ ∑_{e=0}^{∞} \frac{1}{2^{e+n+1}} = \frac{1}{2^{n}}

so the U_{n}’s form a Martin-Löf test. Furthermore, for an arbitrary Martin-Löf test Ũ_{e,n} we have

⋂_{n} Ũ_{e,n} ⊆ ⋂_{n} U_{n}

To see this, note that if X ∈ ⋂_{n} Ũ_{e,n} then for all n we have X ∈ Ũ_{e,e+n+1}, hence X ∈ U_{n}, so X ∈ ⋂_{n} U_{n}. Thus U_{n}, n = 0, 1, 2, … is a universal Martin-Löf test, Q.E.D.

Theorem 15.10. R_{1} = {X ∈ 2^{ℕ} | X is random} is Σ_{2}^{0} of measure 1.

Proof. Let U_{n}, n ∈ ℕ, be a universal Martin-Löf test. Then

R_{1} = 2^{ℕ} \ ⋂_{n=0}^{∞} U_{n}.

Since U_{n} is uniformly Σ_{1}^{0}, R_{1} is Σ_{2}^{0}. Since μ(U_{n}) ≤ 1/2^{n}, μ(R_{1}) = 1.

Theorem 15.11. We can find a Π_{1}^{0} set P ⊆ 2^{ℕ}, P ≠ ∅, consisting entirely of random points in 2^{ℕ}. In other words, P ⊆ R_{1}.

Proof. Fix n and let P = 2^{ℕ} \U_{n}. Then μ(P) ≥ 1−1/2^{n} and P ∩U_{n} = ∅, hence P ∩ ⋂_{n} U_{n} = ∅, hence P ⊆ R_{1}.

Corollary 15.12. We can find random points in 2^{ℕ} which are low, and hyperimmunefree, but not both.

Proof. To find low points, apply the Low Basis Theorem. To find hyperimmunefree points, apply the Hyperimmune-Free Basis Theorem. Recall also that Low ∩ HIF = REC and R_{1} ∩ REC = ∅ so we cannot find X ∈ R_{1} which is both low and hyperimmune-free.

16 Randomness as a mass problem

Theorem 16.1. There is a Π_{1}^{0} set P ⊆ 2^{ℕ} such that P ≡_{w} R_{1}.

To prove this, we use the following lemma.

Lemma 16.2. If S ⊆ 2^{ℕ} is Σ_{2}^{0}, we can find a Π_{1}^{0} set Q ⊆ 2^{ℕ} such that Q ≡_{w} S. (In fact, Q is Turing degree isomorphic to S.)

Proof. Since S is Σ_{2}^{0}, we have S = {X | ∃n ∀m R(m, n, X)} where R is recursive. Let Q_{n} = {X ∈ 2^{ℕ} | ∀m R(m, n, X)}. Thus S = ⋃_{n∈ℕ} Q_{n} and Q_{n} is uniformly Π_{1}^{0}. Let T_{n} be a recursive tree such that Q_{n} = {paths through T_{n}}. Note that T_{n} is uniformly recursive.

We may safely assume that T_{0} has paths but no recursive paths. Let

T̃_{0} = {σ^{⌢}⟨i⟩ | σ ∈ T_{0}, σ^{⌢}⟨i⟩ ∉ T_{0}, i ∈ {0, 1}}.

Since T_{0} has paths but no recursive paths, T̃_{0} is infinite. Note that the strings in T̃_{0} are pairwise incompatible. Let T̃_{0} = {τ_{n} | n ∈ ℕ} and let

T^{∗} = {τ_{n}^{⌢}τ | n ∈ ℕ, τ ∈ T_{n}}.

Then T^{∗} is a recursive tree ⊆ 2^{<ℕ}. Let Q^{∗} = {paths through T^{∗}}.

We claim that Q^{∗} is Turing degree isomorphic to S. If X ∈ S, then X ∈ Q_{n} for some n, and then τ_{n}^{⌢}X ∈ Q^{∗}. Conversely, if Y ∈ Q^{∗}, there are two cases. First, if Y is a path through T_{0}, then Y ∈ Q_{0}. Second, if Y is not a path through T_{0}, then τ ⊂ X for some τ ∈ T̃_{0}. Letting n be such that τ = τ_{n}, we have Y = τ_{n}^{⌢}X where X ∈ Q_{n}. This proves the claim.

Proof of Theorem 16.1. Since R_{1} is Σ_{2}^{0}, let P be Σ_{1}^{0} such that P ≡_{w} R_{1}.

Definition 16.3. r_{1} = deg_{w}(R_{1}).

Corollary 16.4. r_{1} ∈ E_{w}.

Remark 16.5. It can be shown that deg_{s}(R_{1}) ∉ E_{s}, i.e., there is no Π_{1}^{0} set P ⊆ 2^{ℕ} such that R_{1} ≡_{s} P. This result will not be proved here.

Since r_{1} ∈ E_{w} and 1 is the top degree in E_{w}, we clearly have r_{1} ≤ 1. We shall now prove that r_{1} < 1. In order to prove this, we return to the idea of separation problems.

Lemma 16.6. If A, B ⊆ ℕ are recursively inseparable, the Turing upward closure of Sep(A, B) is of measure 0. In other words,

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

In order to prove this lemma, we first note the following consequence of measure-theoretic regularity.

Lemma 16.7. Let S ⊆ 2^{ℕ} be measurable, and let ϵ > 0. Then, we can find a finite set of bitstrings σ_{1}, …, σ_{k} such that μ(S △⋃_{i=1}^{k} N_{σ_{i}}) < ϵ. Here △ denotes symmetric difference.

Remark 16.8. Sets of the form ⋃_{i=1}^{k} N_{σ_{i}} are exactly the clopen sets in 2^{ℕ}.

Proof. By regularity let U be an open set such that S ⊆ U and μ(U \ S) < ϵ/2. Let U = ⋃_{i=1}^{∞} N_{σ_{i}}. By countable additivity let k be such that μ(U \⋃_{i=1}^{k} N_{σ_{i}}) < ϵ/2. Then μ(S △ ⋃_{i=1}^{l} N_{σ_{i}}) < ϵ, Q.E.D.

Proof of Lemma 16.6. Suppose this set is of measure > 0. By countable additivity, let e be such that

μ({Y ∈ 2^{ℕ} | Φ_{e}(Y) ∈ 2^{ℕ} separates A, B}) > 0.

Let S_{e} = {Y ∈ 2^{ℕ} | Φ_{e}(Y) ∈ 2^{ℕ} separates A, B}. By the previous lemma, let σ_{1}, …, σ_{k} be such that μ(S_{e} △ U) < μ(U)/4 where U = ⋃_{i=1}^{k} N_{σ_{i}}. Clearly, μ({Y ∈ U | Φ_{e}(Y) separates A, B}) > 3μ(U)/4. Consider the predicate R(n, i) ≡ μ({Y ∈ 2^{ℕ} | Φ_{e}(Y, n) ≃ i}) > μ(U)/4. Clearly we have ∀n ∃i R(n, i). Moreover R(n, i) is Σ_{1}^{0} since R(n, i) ≡ ∃⟨τ_{1}, …, τ_{l}⟩ (μ(⋃_{j=1}^{l} N_{τ_{j}}) > μ(U)/4 and N_{τ_{j}} ⊆ U and Φ_{e}(τ_{j}) ↓≃ i for all j = 1, …, l) which is clearly Σ_{1}^{0}. By Σ_{1}^{0} selection, let X ∈ 2^{ℕ} be a recursive selector for R, i.e., X is recursive and ∀n R(n, X(n)). Then X separates A, B. This is a contradiction since A and B are recursively inseparable.

Corollary 16.9. If g ∈ ℕ^{ℕ} is nonrecursive, then μ({X ∈ 2^{ℕ} | g ≤_{T} X}) = 0.

Proof. Let A ⊂ ℕ such that A ≡_{T} g. Let B = ℕ \ A. Clearly A, B are recursively inseparable. g ≤_{T} Y ⇔ A ≤_{T} Y ⇔ (∃X ≤_{T} Y)(X separates A, B). So the corollary follows by the lemma above.

Theorem 16.10. 0 < r_{1} < 1 in E_{w}.

Proof. Since X is random ⇒ X is not recursive,

r_{1} = deg_{w}({X | X is random}) > 0.

Since R_{1} ≡_{w} P for a Π_{1}^{0} set P ⊂ 2^{ℕ}, we know r_{1} ∈ E_{w}, hence r_{1} ≤ 1. It remains to show that r_{1} < 1. Recall 1 = deg_{w}(DNR_{2}) and DNR_{2} = Sep(K_{0}, K_{1}) where K_{0} and K_{1} are recursively inseparable. By our lemma, μ({Y | (∃X ≤_{T} Y) (X separates K_{0}, K_{1})}) = 0. Since μ(R_{1}) = 1, we can find Y ∈ R_{1} such that ¬ (∃X ≤_{T} Y) (X separates K_{0}, K_{1}). Hence Sep(K_{0}, K_{1}) ≰_{w} R_{1}, i.e., 1 ≰_{w} r_{1} in E_{w}.

Remark 16.11. r_{1} can be characterized as the maximum weak degree of a Π_{1}^{0} subset of 2^{ℕ} of positive measure.

Remark 16.12. As a consequence of Remark 14.7 we have the following result due to Simpson 2004:

Let P ⊆ 2^{ℕ} be Π_{1}^{0} and ≠ ∅. If {deg_{T} (X) | X ∈ P } ⊆ {deg_{T} (X) | X ∈ DNR_{2}}, then P is Turing degree isomorphic to DNR_{2}.

Moreover, Kent/Lewis 2008 have proved a similar result with DNR_{2} replaced by R_{1}. A possible research problem is to find other Π_{1}^{0} subsets of 2^{ℕ} for which a similar result holds.

17 The Embedding Lemma

Many other examples of interesting degrees in E_{w} depend on the following lemma.

Lemma 17.1 (The Embedding Lemma). Let P ⊆ 2^{ℕ} be Π_{1}^{0} and ≠ ∅. Let S ⊆ ℕ^{ℕ} be Σ_{3}^{0}. Then, we can find Q ⊆ 2^{ℕ} which is Π_{1}^{0} and ≠ ∅ such that Q ≡_{w} P ∪ S. (In fact, Q is Turing degree isomorphic to P ∪ S.)

Proof. Let U ⊆ 2^{<ℕ} be a recursive tree such that P = {paths through U}. Since P ≠ ∅, U contains bitstrings of arbitrary length. For each n ∈ ℕ let us recursively designate one bitstring σ ∈ U with |σ| = n as canonical.^{1}

Recall Theorem 5.7: given a Σ_{3}^{0} subset of ℕ^{ℕ}, we can find a Π_{1}^{0} subset of ℕ^{ℕ} which is Turing degree isomorphic to the given set. Thus, we may safely assume that our Σ_{3}^{0} set S ⊆ ℕ^{ℕ} is actually Π_{1}^{0}. Let V ⊆ ℕ^{<ℕ} be a recursive tree such that S = {paths through V }. We may safely assume that ⟨⟩ ∈ V.

Let W ⊆ 3^{<ℕ} be the recursive tree consisting of all {0, 1, 2}-valued strings of the form

σ_{0}^{⌢}⟨2⟩^{⌢}σ_{1}^{⌢}⟨2⟩^{⌢} ⋯^{⌢}σ_{n−1}^{⌢}⟨2⟩^{⌢}σ_{n}

where

1. for each i ≤ n, σ_{i} ∈ U,

2. for each i < n, σ_{i} is canonical,

3. the string ⟨|σ_{0}|, |σ_{1}|, …, |σ_{n−1}|⟩ belongs to V.

Let Q = {paths through W }. Clearly Q ⊆ 3^{ℕ} is Π_{1}^{0}.

We claim that Q ≡_{w} S ∪ P. In fact, we shall show that Q is Turing degree isomorphic to S ∪ P.

First note that U ⊆ W. (This is the special case of conditions 1 and 2 where n = 0.) Hence P ⊆ Q. Given g ∈ S, consider

h = σ_{0}^{⌢}⟨2⟩^{⌢}σ_{1}^{⌢}⟨2⟩^{⌢} ⋯^{⌢}σ_{n}^{⌢}⟨2⟩^{⌢} ⋯  (3)

where σ_{n} is the canonical bitstring of length g(n). Clearly h belongs to Q and is ≡_{T} g. We have now shown that every member of P ∪ S is Turing equivalent to a member of Q.

Conversely, given h ∈ Q, we have two cases.

Case 1: h(j) = 2 for infinitely many j. Since h is a path through W, h is of the form (3) where each σ_{n} is canonical. Letting g(n) = |σ_{n}| for all n, it is clear that g belongs to S and is and ≡_{T} h.

Case 2: h(j) = 2 for only finitely many j. Then h is of the form

h = σ_{0}^{⌢}⟨2⟩^{⌢}σ_{1}^{⌢}⟨2⟩^{⌢} ⋯^{⌢}σ_{n−1}^{⌢}⟨2⟩^{⌢}X

1For instance, we could designate as canonical the lexicographically leftmost string in U of length n, for each n.

where σ_{0}, σ_{1}, …, σ_{n−1} are bitstrings and X ∈ 2^{ℕ}. Since h is a path through W, we have X ↾ m ∈ U for all m, i.e., X is a path through U. Thus X ∈ P, and clearly X is Turing equivalent to h.

We have now shown that every member of Q is Turing equivalent to a member of S ∪ P. This completes the proof of the Embedding Lemma.

Corollary 17.2. If s = deg_{w}(S) where S is Σ_{3}^{0}, then inf(s, 1) ∈ E_{w}.

Proof. Let P ⊆ 2^{ℕ} be Π_{1}^{0} and ≠ ∅ with deg_{w}(P) = 1. By the Embedding Lemma, let Q ≡_{w} S ∪ P where Q ⊆ 2^{ℕ} is Π_{1}^{0} and ≠ ∅. Then clearly inf(s, 1) = deg_{w}(S ∪ P) = deg_{w}(Q) ∈ E_{w}.

18 Consequences of the Embedding Lemma

Corollary 17.2 is useful in showing that various interesting weak degrees belong to E_{w}. In this section we give several examples of this.

Our first example involves randomness relative to the Halting Problem.

Example 18.1. Let r_{2} = deg_{w}(R_{2}) where R_{2} = {X ∈ 2^{ℕ} | X is 2-random}. Here 2-random means random relative to 0′. We can use the Embedding Lemma to show that inf(r_{2}, 1) ∈ E_{w}.

Details:

Definition 18.2. If g is any oracle, g ∈ ℕ^{ℕ}, we say that X is g-random (i.e., random relative to g) if X ∉ ⋂_{n=0}^{∞} U_{n}^{g} for any uniformly Σ_{1}^{0,g} sequence of sets U_{n}^{g}, n = 0, 1, 2, … with μ(U_{n}^{g}) ≤ 1/2^{n}.

Lemma 18.3. There is a universal test for g-randomness, uniformly in g. In other words, we can find U_{n}^{g} as above such that

R_{1}^{g} = {X ∈ 2^{ℕ} | X is g-random} = 2^{ℕ} \ ⋂_{n=0}^{∞} U_{n}^{g}

and the predicate U(X, n, g) ≡ X ∈ U_{n}^{g} is Σ_{1}^{0}.

Proof. This is a straightforward relativization of Lemma 15.9.

Corollary 18.4. R_{1}^{g} is Σ_{2}^{0,g}, uniformly in g, and μ(R_{1}^{g}) = 1.

We then have R_{2} = R_{1}^{0′} = {X ∈ 2^{ℕ} | X is 0′-random}.

Corollary 18.5. R_{2} is Σ_{2}^{0,0′}, hence Σ_{3}^{0}.

Proof. In fact, any predicate which is Σ_{2}^{0,0′} is Σ_{3}^{0}. This is easily seen by a Tarski/Kuratowski computation.

Theorem 18.6. We have inf(r_{2}, 1) ∈ E_{w} and r_{1} ≤ inf(r_{2}, 1) < 1.

Later we will show that r_{1} < inf(r_{2}, 1).

Proof. Since R_{2} is Σ_{3}^{0}, we have inf(r_{2}, 1) ∈ E_{w} by the Embedding Lemma. Trivially inf(r_{2}, 1) ≤ 1. Since μ(R_{2}) = 1, it follows by Lemma 16.6 that we can find X ∈ R_{2} such that ¬ (∃Y ≤_{T} X) (Y separates K_{0}, K_{1}). Thus 1 ≰ r_{2}, hence inf(r_{2}, 1) < 1.

Our second example involves diagonal nonrecursiveness.

Example 18.7. Let d = deg_{w}(DNR) where DNR = {g ∈ ℕ^{ℕ} | g is diagonally non-recursive } = {g ∈ ℕ^{ℕ} | ∀n (g(n) ≄ φ_{n}^{(1)}(n))}. We can use the Embedding Lemma to show that d ∈ E_{w}.

Details:

Theorem 18.8. d ∈ E_{w}.

Proof. DNR is Π_{1}^{0}, hence Σ_{3}^{0}, so by Corollary 17.2 we have inf(d, 1) ∈ E_{w}. However, d ≤ 1 because 1 = deg_{w}(DNR_{2}) and DNR_{2} ⊂ DNR. We now see that d = inf(d, 1) ∈ E_{w}.

Theorem 18.9. 0 < d ≤ r_{1}.

Later we shall prove that d < r_{1}.

Proof. Obviously 0 < d, because DNR ∩ REC = ∅. It remains to prove that d ≤ r_{1}, i.e., DNR ≤_{w} R_{1}. Consider the total recursive functional Φ : 2^{ℕ} → ℕ^{ℕ} defined by

\begin{aligned}Φ(X)(n) & = & X(0) + 2X(1) + 4X(2) + ⋯ + 2^{n−1}X(n − 1) \\ & = & ∑_{i=0}^{n−1} X(i) 2^{i}. \end{aligned}

Let U_{n} = {X ∈ 2^{ℕ} | Φ(X)(n) ≃ φ_{n}^{(1)}(n)}. Clearly μ(U_{n}) ≤ 1/2^{n}. Letting V_{n} = ⋃_{k=n+1}^{∞} U_{k} we see that μ(V_{n}) ≤ ∑_{k=n+1}^{∞} μ(U_{k}) ≤ ∑_{k=n+1}^{∞} 1/2^{k} = 1/2^{n}. Moreover V_{n} is uniformly Σ_{1}^{0}, so V_{n}, n = 0, 1, 2, … is a Martin-Löf test. If X is random, we have X ∉ V_{n} for some n, hence Φ(X)(k) ≄ φ_{k}^{(1)}(k) for all k ≥ n+1. Hence we can find g ∈ DNR such that g(k) = Φ(X)(k) for all k ≥ n+1. Clearly g ≤_{T} X. Thus DNR ≤_{w} R_{1}.

Exercise 18.10. We have shown that DNR ≤_{w} R_{1}. Show that DNR ≰_{s} R_{1}.

Here is a third example.

Example 18.11. Define

DNR_{REC} = {recursively bounded, diagonally nonrecursive functions}.

Thus DNR_{REC} = {g ∈ DNR | g is dominated by a recursive function}. Define d_{REC} = deg_{w}(DNR_{REC}). We can use the Embedding Lemma to show that d_{REC} ∈ E_{w}.

Details:

Theorem 18.12. d_{REC} ∈ E_{w} and d ≤ d_{REC} ≤ r_{1}.

Proof. We have

g ∈ DNR_{REC} ≡ ∃e ∀n (φ_{n}^{(1)}(n) ≄ g(n) ∧ ∃j (φ_{e}^{(1)}(n) ≃ j ∧ g(n) < j))

and a Tarski/Kuratowski computation shows that DNR_{REC} is Σ_{3}^{0}. Moreover, by Corollary 17.2 and Theorem 14.6 we have

deg_{w}(DNR_{REC}) = deg_{w}(DNR_{REC} ∪ DNR_{2}) = inf(d_{REC}, 1) ∈ E_{w}

since DNR_{REC} ⊆ DNR. Thus d ≤ d_{REC} ≤ 1. Moreover, our proof that d ≤ r_{1} actually shows that d_{REC} ≤ r_{1}. Namely, we showed that if X is 1-random then Φ(X)(n) ≄ φ_{n}^{(1)}(n) for all but finitely many n, but clearly Φ(X)(n) = ∑_{i=0}^{n} X(i)2^{i} is recursively bounded, in fact it is bounded by 2^{n}.

Later we shall prove that d < d_{REC} < r_{1}.

19 1-genericity

Definition 19.1. A function g ∈ ℕ^{ℕ} is said to be n-generic if for all Σ_{n}^{0} sets A ⊆ ℕ^{<ℕ} we can find σ ⊂ g such that either σ ∈ A or ¬ ∃τ (σ ⊆ τ ∧ τ ∈ A).

Remark 19.2. Note that g is generic in the sense of Section 7 if and only if it is n-generic for all n.

Proof. ⇒: Assume that g is generic in the sense of Section 7. Given a Σ_{n}^{0} set of strings A, let D_{A} = {ρ ∈ ℕ^{<ℕ} | (∃σ ∈ A) (σ ⊆ ρ ∨ ∄σ (σ ⊇ ρ ∧ σ ∈ A)}. Note that D_{A} is arithmetical, in fact Δ_{n+1}^{0}. Moreover D_{A} is dense: Given σ, if ¬ ∃τ(τ ⊇ σ, τ ∈ A) then σ ∈ D_{A}, otherwise we can find τ ⊇ σ such that τ ∈ A and then τ ∈ D_{A}. Now, since g is generic, g meets D_{A}, i.e., (∃σ ⊂ g) (σ ∈ D_{A}). Thus g is n-generic.

⇐: Trivial.

Definition 19.3. g is weakly n-generic if for all dense Σ_{n}^{0} sets D ⊆ ℕ^{<ℕ} there exists σ ⊂ g such that σ ∈ D.

Remark 19.4. Note that D_{A} = A if and only if A is dense. Thus weakly n + 1-generic implies n-generic which implies weakly n-generic. The converse implications do not hold in general.

Lemma 19.5. If g is 1-generic, then g is generalized low, i.e., g′ ≡_{T} g ⊕ 0′,

Proof. It suffices to show that g′ ≤_{T} g ⊕ 0′. Trivially e ∈ g′ ≡ φ_{e}^{(1),g}(0) ↓≡ (∃σ ⊂ g) (φ_{e,|σ|}^{(1),σ}(0) ↓) which is Σ_{1}^{0,g}. Let A_{e} = {σ | φ_{e,|σ|}^{(1),σ}(0) ↓} and let D_{e} = D_{A_{e}} = {σ | σ ∈ A_{e} ∨ ¬ (∃τ ⊇ σ) (τ ∈ A_{e})}. Clearly A_{e} is Σ_{1}^{0} (it is actually recursive). Therefore, because g is 1-generic, (∃σ ⊂ g) (σ ∈ D_{e}). Thus we have e ∉ g′ ≡ (∃σ ⊂ g) ¬ (∃τ ⊇ σ) (τ ∈ A_{e}) which is Σ_{1}^{0,g⊕0′}. Thus g′ is Δ_{1}^{0,g⊕0′}, i.e., g′ ≤_{T} g ⊕ 0′, Q.E.D.

Exercise 19.6. Generalize the previous lemma as follows. If g is n-generic then g^{(n)} ≡_{T} g ⊕ 0^{(n)}.

Theorem 19.7. If h ≥_{T} 0′ we can find a 1-generic g such that g′ ≡_{T} h.

Proof. We shall construct an increasing sequence of strings

τ_{0} ⊂ τ_{1} ⊂ ⋯ ⊂ τ_{n} ⊂ τ_{n+1} ⊂ ⋯

and we shall define g = ⋃_{n=0}^{∞} τ_{n}.

Stage 0. Begin with τ_{0} = ⟨⟩, the empty string.

Stage n + 1. Given τ_{n}, ask the oracle 0′ whether (Case 1) there exists τ ⊇ τ_{n}^{⌢}⟨h(n)⟩ such that φ_{n,|τ|}^{(1),τ}(0) ↓. If so, let τ_{n+1} = the least such τ. Otherwise (Case 2) let τ_{n+1} = τ_{n}^{⌢}⟨h(n)⟩.

We claim that g is 1-generic. Given a Σ_{1}^{0} set A ⊆ ℕ^{<ℕ}, let n be such that φ_{n}^{(1),g}(0) ↓≡ (∃σ ⊂ g) (σ ∈ A) for all g. We know that τ_{n}^{⌢}⟨h(n)⟩ ⊆ τ_{n+1} ⊂ g. At stage n, if Case 1 held, φ_{n}^{(1),τ_{n+1}}(0) ↓, hence φ_{n}^{(1),g}(0) ↓, hence (∃σ ⊂ g) (σ ∈ A). If Case 2 held, we have ¬ (∃τ ⊇ τ_{n}^{⌢}⟨h(n)⟩) (φ_{n,|τ|}^{(1),τ}(0) ↓), hence ¬ (∃τ ⊇ τ_{n}^{⌢}⟨h(n)⟩)(τ ∈ A). In either case g satisfies the condition for 1-genericity, thus proving our claim.

We claim that the sequence ⟨τ_{n}⟩_{n∈ℕ} is ≤_{T} h and ≤_{T} g ⊕0′. To see this, note that it is ≤_{T} h because 0′ ≤_{T} h, and it is ≤_{T} g ⊕ 0′ because h(n) = g(|τ_{n}|).

It follows from this claim that h ≡_{T} g ⊕ 0′. Hence by the previous lemma we have h ≡_{T} g′, Q.E.D.

Corollary 19.8 (Friedberg). Given h ≥_{T} 0′ we can find g such that g′ ≡_{T} h. Thus, the range of the Turing jump operator ′ : D_{T} → D_{T} given by a ↦ a′ consists precisely of all Turing degrees b ≥ 0′.

Lemma 19.9. If g ∈ ℕ^{ℕ} is 1-generic, there is no DNR function ≤_{T} g.

Proof. Given e, to show φ_{e}^{(1),g} is not DNR. Let

A = {τ ∈ ℕ^{<ℕ} | ∃n (φ_{e}^{(1),τ} (n) ↓= φ_{n}^{(1)}(n) ↓)}.

Clearly A is Σ_{1}^{0}. Because g is 1-generic, there are two cases.

Case 1: (∃τ ⊂ g) (τ ∈ A).

Case 2: (∃σ ⊂ g) ¬ (∃τ ⊇ σ) (τ ∈ A).

In Case 1 we have τ ⊂ g, hence φ_{e}^{(1),g}(n) ↓= φ_{n}^{(1)}(n) ↓, hence φ_{e}^{(1),g} is not DNR. In Case 2 we have σ ⊂ g and there is no τ ⊇ σ such that τ ∈ A. Define a partial recursive function θ(m) as follows. Given m, search for τ ⊇ σ such that φ_{e}^{(1),τ} (m) ↓. If we find such a τ let θ(m) = φ_{e}^{(1),τ} (m), otherwise θ(n) ↑. Now let n be an index of θ, i.e., φ_{n}^{(1)}(m) ≃ θ(m) for all m.

We claim that φ_{e}^{(1),τ} (n) ↑ for all τ ⊇ σ. Otherwise, let τ ⊇ σ be such that φ_{e}^{(1),τ} (n) ↓= θ(n) ↓. Such a τ would exist by definition of θ. Then φ_{e}^{(1),τ} (n) ↓= θ(n) ↓= φ_{n}^{(1)}(n) ↓ since n is an index of θ. Hence τ ∈ A contradicting the case hypothesis. This proves the claim.

Since σ ⊂ g, our claim implies that φ_{e}^{(1),g}(n) ↑. Hence φ_{e}^{(1),g} is not DNR. This completes the proof.

Combining Theorem 19.7 and Lemma 19.9 we get:

Theorem 19.10. Given B ≥_{T} 0′ we can find A such that A′ ≡_{T} B and there is no DNR function ≤_{T} A.

20 Kolmogorov complexity

Given a bitstring τ ∈ 2^{<ℕ}, we would like to measure the “intrinsic complexity” or “amount of information” which is inherent in τ. Roughly speaking, the “complexity” of τ will be the length of the shortest description of τ. However, in view of Berry’s Paradox, we need to restrict the allowable descriptions. Berry’s Paradox refers to “the least n such that n cannot be described in < 10^{6} bits.” We shall consider only the following kind of description.

Definition 20.1. A description of τ is a program which outputs τ.

Definition 20.2. A machine is a partial recursive function M :⊆ 2^{<ℕ} → 2^{<ℕ} (from bitstrings to bitstrings). A machine U is said to be universal if for all machines M we can find a fixed bitstring ρ (depending on M) such that M(σ) ≃ U(ρ^{⌢}σ) for all σ.

Definition 20.3 (Kolmogorov). Fix a universal machine U. Given a bitstring τ, we define C(τ) = min{|σ| | U(σ) ≃ τ} = the complexity of τ = the minimum number of bits needed to describe τ via U.

Remark 20.4. Note that C(τ) is not computable as a function of τ. However, C(τ) ↓ for all τ. The following lemma says that C(τ) is well-defined up to ±O(1). Thus C(τ) depends only slightly on our choice of a universal machine.

Lemma 20.5. Let U_{1} and U_{2} be universal machines and define C_{i}(τ) = min{|σ| | U_{i}(σ) ≃ τ} for i = 1, 2. Then |C_{1}(τ) − C_{2}(τ)| ≤ O(1). In other words, we can find a constant k depending only on U_{1} and U_{2} such that |C_{1}(τ) − C_{2}(τ)| ≤ k for all τ.

Proof. Since U_{2} is universal, let ρ_{1} be such that U_{1}(σ) ≃ U_{2}(ρ^{⌢}σ) for all σ. We claim that C_{2}(τ) ≤ C_{1}(τ)+|ρ_{1}| for all τ. To see this, let σ be of minimum length such that U_{1}(σ) = τ. Then |σ| = C_{1}(τ). We have U_{2}(ρ_{1}^{⌢}σ) ≃ U_{1}(σ) ≃ τ, hence C_{2}(τ) ≤ |ρ_{1}^{⌢}σ| = |ρ_{1}| + |σ| = C_{1}(τ) + |ρ_{1}|. Thus we see that C_{2}(τ) − C_{1}(τ) ≤ O(1), namely |ρ_{1}|. Similarly, C_{1}(τ) − C_{2}(τ) ≤ O(1).

Lemma 20.6. For any τ ∈ 2^{<ℕ} we have C(τ) ≤ |τ| + O(1).

Proof. Consider the identity machine, M(σ) = σ. Let ρ be such that M(σ) ≃ U(ρ^{⌢}σ) for all σ. Then M(τ) = U(ρ^{⌢}τ) = τ, so C(τ) ≤ |ρ^{⌢}τ| = |ρ| + |τ| = |τ| + O(1).

Remark 20.7. More generally, if τ is any finite combinatorial object, let

C(τ) = the complexity of τ = min{|σ| | U(σ) ≃ #(τ)}

where U :⊆ 2^{<ℕ} → ℕ is a fixed universal machine. Here #(τ) is the Gödel number of τ. As above we can show that C(τ) is well-defined up to ± O(1).

We now consider complex points in the Cantor space.

Definition 20.8. A point X ∈ 2^{ℕ} is said to be complex if there exists a total recursive function p(n) such that sup p(n) = ∞ and C(X ↾ n) ≥ p(n) for all n. Let COMPLEX = {X ∈ 2^{ℕ} | X is complex}.

Remark 20.9. The following theorem implies that if X is complex then X is nonrecursive. Indeed, complexity may be viewed as a weak form of randomness.

Theorem 20.10 (Kjos-Hanssen/Merkle/Stephan 2006). We have

COMPLEX ≡_{w} DNR_{REC}.

More precisely, COMPLEX is Turing degree isomorphic to DNR_{REC}.

Notation 20.11. Given a total recursive function p such that sup p(n) = ∞, define the inverse function p^{−1} by letting p^{−1}(m) = the least n such that p(n) ≥ m. Note that p^{−1} is again a total recursive function and sup p^{−1}(m) = ∞. Moreover p^{−1} is monotone, i.e., p^{−1}(m) ≤ p^{−1}(m + 1) for all m.

Examples 20.12. If p(n) = 2^{n} then p^{−1}(n) ≈ log_{2} n. If p(n) ≈ log_{2} n then p^{−1}(n) ≈ 2^{n}.

Proof of Theorem 20.10. First, given a complex X ∈ 2^{ℕ}, to find f ∈ DNR_{REC} such that f ≡_{T} X. Let p(n) be a recursive function such that sup p(n) = ∞ and C(X ↾ n) ≥ p(n) for all n. In particular C(X ↾ p^{−1}(m)) ≥ p(p^{−1}(m)) ≥ m for all m. Let

f(m) = #(X ↾ p^{−1}(m)) = ∑_{i<p^{−1}(m)} X(i)2^{i}

and note that f ≡_{T} X and f(m) < 2^{p^{−1}(m)}, a recursive function. We wish to show that f is DNR. By definition of f(m) we have C(f(m)) ≥ m − O(1) for all m. But C(φ_{m}^{(1)}(m)) ≤ C(m) + O(1) ≤ log_{2} m + O(1) < m for all but finitely many m. Thus f(m) ≄ φ_{m}^{(1)}(m) for all but finitely many m. In other words, f is DNR with finitely many exceptions, and this suffices.

Conversely, assume that f ∈ DNR_{REC}, i.e., f is DNR and recursively bounded. Let p(m) be a total recursive function such that f(m) < 2^{p(m)} for all m. Let q(m) = ∑_{j<m} p(j) and define X ∈ 2^{ℕ} by the condition f(m) = ∑_{i<p(m)} X(q(m) + i)2^{i} for all m. Clearly X ≡_{T} f. We shall show that X is complex. By the Parametrization Theorem, let r be a primitive recursive function such that φ_{r(σ)}^{(1)}(m) ≃ ∑_{i<p(m)} U(σ)(q(m) + i)2^{i} for all bitstrings σ. In particular

φ_{r(σ)}^{(1)}(r(σ)) ≃ ∑_{i<p(r(σ))} U(σ)(q(r(σ)) + i)2^{i}

but on the other hand

f(r(σ)) = ∑_{i<p(r(σ))} X(q(r(σ)) + i)2^{i}

and of course φ_{r(σ)}^{(1)}(r(σ)) ≄ f(r(σ)) for all bitstrings σ. Thus U(σ) ≄ X ↾ q(m) whenever σ and m are such that r(σ) < m. It follows that C(X ↾ q(m)) ≥ the least n such that r(σ) ≥ m for some σ of length n. In other words, C(X ↾ q(m)) ≥ s^{−1}(m) where s(n) = max{r(σ) | |σ| = n}. Moreover C(X ↾ q(m)) ≤ C(X ↾ i) + O(1) whenever q(m) ≤ i < q(m + 1), i.e., m = q^{−1}(i + 1) − 1. Thus for all i we have

C(X ↾ i) = C(X ↾ q(q^{−1}(i + 1) − 1)) − O(1) ≥ s^{−1}(q^{−1}(i + 1) − 1) − O(1)

so X is complex, Q.E.D.

Remark 20.13. Define an order function to be a total recursive function p such that p is monotone and lim p(n) = ∞. The proof of Theorem 20.10 shows that X is complex if and only if there exists an order function p such that C(X ↾ n) ≥ p(n) for all n.

Definition 20.14. Define the inverse of an order function p to be p^{−1}(n) = least m such that p(m) ≥ n.

Note that if p is an order function, so is p^{−1}. But their growth rates are very different. If p is fast-growing, then p^{−1} is slow-growing and vice versa.

Theorem 20.15. DNR_{REC} is Turing degree isomorphic to COMPLEX.

Recall that

DNR_{REC} = {f ∈ DNR | ∃ order function p such that ∀n f(n) < p(n)}

and

COMPLEX = {X ∈ 2^{ℕ} | ∃ order function p such that ∀n C(X ↾ n) ≥ p^{−1}(n)}.

Remark 20.16. Theorem 20.10 can be refined as follows. Let C be a “nice” class of recursive functions, e.g., the primitive recursive functions. Define

DNR_{C} = {f ∈ DNR | ∃ order function p ∈ C such that ∀n f(n) < p(n)}

and

COMPLEX_{C} = {X ∈ 2^{ℕ} | ∃ order function p ∈ C such that
∀n C(X ↾ n) ≥ p^{−1}(n)}.

Then DNR_{C} and COMPLEX_{C} are Turing degree isomorphic.

Moreover, we shall see later that if C and C′ are “nice” classes as above and C ⊂ C′ and C′ contains a function which grows much faster than all of the functions in C, then d_{C′} < d_{C}.

21 Distinguishing r_{1} from inf(r_{2}, 1)

We already know that r_{1} ≤ inf(r_{2}, 1). In this section we shall prove that the inequality is strict.

Theorem 21.1 (Stephan). If X ∈ 2^{ℕ} is random and CPA ≤_{w} {X}, then 0′ ≤_{T} X.

Corollary 21.2. r_{1} < inf (r_{2}, 1).

Proof. Let X ∈ R_{1} be <_{T} 0′ (we can find such an X by the Low Basis Theorem). Because X ≤_{T} 0′ there is no 2-random Y ≤_{T} X. Moreover by Stephan’s Theorem we have CPA ≰_{w} {X}. Combining these two observations we have R_{2} ∪ CPA ≰_{w} {X}. Hence inf (r_{2}, 1) ≰ r_{1}. But we already know by Theorem 18.6 that r_{1} ≤ inf(r_{2}, 1). The corollary follows.

In order to prove Stephan’s Theorem, the following lemma will be useful.

Definition 21.3. A set S ⊆ ℕ^{ℕ} is recursively bounded if there exists a recursive function h such that f(n) < h(n) for all f ∈ S and n ∈ ℕ.

Lemma 21.4. If P ⊆ ℕ^{ℕ} is recursively bounded and Π_{1}^{0}, then we can find a Π_{1}^{0} set P^{∗} ⊆ 2^{ℕ} such that P ≡_{s} P^{∗}. In fact, P and P^{∗} are recursively homeomorphic.

Proof. Define a total recursive functional Φ : ℕ^{ℕ} → 2^{ℕ} by

Φ(f) = the characteristic function of the graph of f.

Clearly Φ is injective and Φ^{−1} is partial recursive. Let P^{∗} = {Φ(f) | f ∈ P }. Clearly P is recursively homeomorphic to P^{∗}. We would like to show that P^{∗} is Π_{1}^{0}. To do this, let h be a recursive function which bounds P. Then for all X ∈ 2^{ℕ} we have X ∈ P^{∗} ≡ (∀m (∃i < h(m)) (X(3^{m}5^{i}) = 1 ∧ ∀j (X(3^{m}5^{j}) = 1 ⇒ i = j)) ∧ Φ^{−1}(X) ∈ P. Clearly this is Π_{1}^{0}.

Corollary 21.5. If P ⊆ ℕ^{ℕ} is Π_{1}^{0} and ≠ ∅ and recursively bounded, then P ≤_{s} CPA.

Proof. This is immediate from Lemma 21.4 and Theorem 14.17.

We now prove Stephan’s Theorem.

Proof of Theorem 21.1. We know that 0′ = H = {n | φ_{n}^{(1)}(0) ↓}. Let H_{s} = {n | φ_{n,s}^{(1)}(0) ↓}. Clearly H_{0} ⊆ H_{1} ⊆ ⋯ ⊆ H_{s} ⊆ ⋯ and H = ⋃_{s=0}^{∞} H_{s}. Define a 1-place partial recursive function ψ as follows: Given e and n, search for the least s such that n ∈ H_{s}. If and when s is found, for each i ≤ 2^{n} compute the rational number

r_{e,n,i} = μ{X ∈ 2^{ℕ} | φ_{e,s}^{(1),X}(2^{e}3^{n}) ↓= i}

and define ψ(2^{e}3^{n}) = i < 2^{n} chosen so that r_{e,n,i} < 1/2^{n}. Otherwise ψ(m) ↑. Note that ψ is partial recursive and that ψ(2^{e}3^{n}) ↓⇔ n ∈ H.

We claim that if X is random and X ≥_{T} a total extension of ψ, then X ≥_{T} 0′. To prove the claim, let

V_{e,n} = {X ∈ 2^{ℕ} | ∃s (n ∈ H_{s} \ H_{s−1} ∧ φ_{e,s}^{(1),X}(2^{e}3^{n}) ≃ ψ(2^{e}3^{n}))}.

Note that if n ∈ H then μ(V_{e,n}) = r_{e,n,ψ(2^{e}3^{n})} ≤ 1/2^{n}. Moreover V_{e,n} is uniformly Σ_{1}^{0} and thus the sets V_{e,n}, n ∈ ℕ form a test for randomness. Now suppose X is random and X ≥_{T} a total extension of ψ. Let e be such that φ_{e}^{(1),X} is total and extends ψ. Define f(n) = least s such that φ_{e,s}^{(1),X}(2^{e}3^{n}) ↓. Since φ_{e}^{(1),X} is total, f is total and f ≤_{T} X. Since X is random, X ∈ V_{e,n} for only finitely many n. Hence, for all but finitely many n, n ∈ H_{s} \ H_{s−1} implies φ_{e,s}^{(1), X}(2^{e}3^{n}) ≄ ψ(2^{e}3^{n}), hence φ_{e,s}^{(1), X}(2^{e}3^{n}) ↑, hence s < f(n). Thus, for all but finitely many n, n ∈ H implies n ∈ H_{f(n)}. Thus H ≤_{T} f ≤_{T} X and our claim is proved.

Let P = {g ∈ ℕ^{ℕ} | g is a total extension of ψ and ∀m g(m) < 2^{m}}. Since ψ(m) < 2^{m} whenever ψ(m) ↓, we see that P ≠ ∅. Since P is a recursively bounded nonempty Π_{1}^{0} set, it follows by Corollary 21.5 that P ≤_{s} CPA.

Finally, let X be random such that CPA ≤_{w} {X}. Since CPA ≤_{w} {X}, we have P ≤_{w} {X}. Since X is random, our claim above implies that X ≥_{T} 0′, Q.E.D.

Remark 21.6. Another theorem, the Kučera/Gács Theorem, says that every Turing degree ≥ 0′ is random, i.e., it contains a random X. Combining this with Stephan’s Theorem, we see see that a random Turing degree is a PA-degree if and only if it is ≥ 0′.

22 Distinguishing d, d_{REC}, and d_{C}

The weak degrees d = deg_{w}(DNR) and d_{REC} = deg_{w}(DNR_{REC}), and d_{C} = deg_{w}(DNR_{C}) have been introduced previously in Sections 18 and 20. Here DNR is the class of diagonally recursive functions, DNR_{REC} is the class of recursively bounded DNR functions, and DNR_{C} is the class of C-bounded DNR functions where C is a “nice” subclass of REC such as the primitive recursive functions.

The purpose of this section is to locate these degrees within E_{w} by proving the inequalities

0 < d < d_{REC} < d_{C} < r_{1}.  (4)

See also Remark 22.18 below.

We begin with the following theorem.

Definition 22.1. Given a total recursive function p(n), let

DNR_{p} = {p-bounded DNR functions}
= {f ∈ ℕ^{ℕ} | ∀n (f(n) < p(n) ∧ f(n) ≄ φ_{n}^{(1)}(n))}.

Theorem 22.2. For all recursive functions p, DNR <_{w} DNR_{p}.

Proof of Theorem 22.2, Preliminary Outline. Given a recursive function p, we shall define an increasing sequence of strings

τ_{0} ⊂ τ_{1} ⊂ ⋯ ⊂ τ_{e} ⊂ τ_{e+1} ⊂ ⋯

such that g = ⋃_{e=0}^{∞} τ_{e} is DNR and DNR_{p} ≰_{w} {g}. Clearly this will suffice to prove the theorem. We may safely assume that p(n) > 0 for all n.

We begin the construction at stage 0 with τ_{0} = ⟨⟩ = the empty string. At stage e + 1 we define τ_{e+1} ⊃ τ_{e} so as to address the eth requirement, φ_{e}^{(1),g} ∉ DNR_{p}. Note that there are three possible methods of satisfying this requirement:

1. φ_{e}^{(1),g}(n) ↑ for some n.

2. φ_{e}^{(1),g}(n) ↓= φ_{n}^{(1)}(n) for some n.

3. φ_{e}^{(1),g}(n) ↓≥ p(n) for some n.

If we can find a string τ ⊃ τ_{e} such that φ_{e}^{(1),τ} (n) ↓= φ_{n}^{(1)}(n) or φ_{e}^{(1),τ} (n) ↓≥ p(n) for some n, then we can let τ_{e+1} = τ and this will satisfy the eth requirement by method 2 or method 3 respectively. Otherwise we will have to resort to method 1, which means paying attention to this requirement for the rest of the construction.

In parallel with the definition of τ_{0} ⊂ τ_{1} ⊂ ⋯ ⊂ τ_{e} ⊂ τ_{e+1} ⊂ ⋯, we shall define finite sets of ordered pairs

F_{0} ⊆ F_{1} ⊆ ⋯ ⊆ F_{e} ⊆ F_{e+1} ⊆ ⋯

where each pair ⟨i, n⟩ ∈ F_{e} represents a commitment to insure that φ_{i}^{(1),g}(n) ↑. In this way the ith requirement will be satisfied via method 1. The details of how to fulfill these commitments are the heart of the proof.

Associated with the finite set F_{e} will be the set

A_{e} = ⋃_{\begin{matrix}⟨i,n⟩∈F_{e} \\ j<p(n) \end{matrix}}A_{i,n,j} where A_{i,n,j} = \{τ | φ_{i}^{(1),τ} (n) ≃ j\}.

In order to fulfill the commitments embodied in F_{e}, we shall arrange that A_{e} is in certain sense “small” above τ_{e}. The appropriate concept of “smallness” is in Definitions 22.4 and 22.6 below.

The remaining details of the proof will be presented below.

We now develop some combinatorial machinery which is needed for the proof.

Notation 22.3. If ρ is a string and T is a finite set of strings, we write

[ρ, T] = {σ | (∃τ ∈ T) (ρ ⊆ σ ⊆ τ)}.

Definition 22.4. Let ρ and T be as above, and let k be a positive integer. We say that T is k-good above ρ if ρ ∈ [ρ, T] and for all σ ∈ [ρ, T] either {i | σ^{⌢}⟨i⟩ ∈ [ρ, T]} = ∅ or |{i | σ^{⌢}⟨i⟩ ∈ [ρ, T]}| > k.

Remark 22.5. A set [ρ, T] as in Definition 22.4 is sometimes called a k-bushy tree. The method of bushy trees is due to Kumabe.

Definition 22.6. Let C be a set of strings. If some finite set T ⊆ C is k-good above ρ, we say that C is k-large above ρ. Otherwise we say that C is k-small above ρ.

Remark 22.7. Every superset of a set which is k-large above ρ is k-large above ρ. Every subset of a set which is k-small above ρ is k-small above ρ. Every set which contains ρ is k-large above ρ for all k.

Lemma 22.8. If C is k-small above ρ and D is k-large above ρ, then C is k-small above some τ ∈ D.

Proof. Since D is k-large above ρ, let T ⊆ D be k-good above ρ. We claim that C is k-small above some τ ∈ T. Otherwise, for each τ ∈ T let S_{τ} ⊆ C be k-good above τ. Then clearly ⋃_{τ∈T} S_{τ} is k-good above ρ. Hence C is k-large above ρ. This contradiction proves the lemma.

Lemma 22.9. If each of C_{1}, …, C_{l} is k-small above ρ, then C_{1} ∪ ⋯ ∪ C_{l} is kl-small above ρ.

Proof. Suppose C_{1} ∪⋯∪C_{l} is kl-large above ρ. Let T ⊆ C_{1} ∪⋯∪C_{l} be kl-good above ρ. For each σ ∈ [ρ, T] define f(σ) ∈ {1, …, l} by downward induction on the length of σ. If {i | σ^{⌢}⟨i⟩ ∈ [ρ, T]} = ∅ define f(σ) = the least j such that σ ∈ C_{j}. If |{i | σ^{⌢}⟨i⟩ ∈ [ρ, T]}| > kl define f(σ) = the least j such that |{i | f(σ^{⌢}⟨i⟩) = j}| > k. Finally, letting j = f(ρ), it is clear that C_{j} is k-large above ρ. This contradiction completes the proof.

Exercise 22.10. Prove that if C_{j} is k_{j}-small above ρ for each j = 1, …, l, then ⋃_{j=1}^{l} C_{j} is ∑_{j=1}^{l} k_{j}-small above ρ.

We now return to the proof of Theorem 22.2.

Proof of Theorem 22.2. We continue to use the notations τ_{e}, F_{e}, A_{e} and A_{i,n,j} as in our preliminary outline above. At stage e we shall define F_{e} and τ_{e} and a positive integer k_{e} such that A_{e} is k_{e}-small above τ_{e}.

Stage 0. Let F_{0} = ∅ and τ_{0} = ⟨⟩ and k_{0} = 1. Note that A_{0} is k_{0}-small above τ_{0} (because A_{0} = ∅).

Stage e+1. Assume inductively that F_{e} and τ_{e} and k_{e} have been defined and that A_{e} is k_{e}-small above τ_{e}. Consider a partial recursive function θ_{e}(n) ≃ θ(n) defined as follows. Given n, search for a j < p(n) such that A_{e,n,j} is k_{e}-large above τ_{e}. We can perform this search effectively, because p(n) is a recursive function and the sets A_{e,n,j} are uniformly Σ_{1}^{0}. If such a j is found, let θ(n) ≃ j.

Otherwise let θ(n) ↑. By the Recursion Theorem, let n = n_{e} be such that φ_{n}^{(1)}(n) ≃ θ(n). With this n we consider two cases.

Case 1: θ(n) ↓. Since A_{e} is k_{e}-small above τ_{e} and A_{e,n,θ(n)} is k_{e}-large above τ_{e}, apply Lemma 22.8 to find τ′_{e} ⊇ τ_{e} such that τ′_{e} ∈ A_{e,n,θ(n)} and A_{e} is k_{e}-small above τ′_{e}. Let F_{e+1} = F_{e} and k_{e+1} = k_{e} and note that A_{e+1} = A_{e} is k_{e+1}- small above τ′_{e}. Since τ′_{e} ∈ A_{e,n,θ(n)} we have φ_{e}^{(1),τ′_{e}}(n) ↓≃ θ(n) ≃ φ_{n}^{(1)}(n) thus satisfying the eth requirement via method 2.

Case 2: θ(n) ↑. In this case let F_{e+1} = F_{e} ∪{⟨e, n⟩} and k_{e+1} = k_{e}(p(n)+1). Since A_{e} and A_{e,n,j} for each j < p(n) are k_{e}-small above τ_{e}, it follows by Lemma 22.9 that

A_{e+1} = A_{e} ∪ ⋃_{j<p(n)} A_{e,n,j}

is k_{e+1}-small above τ_{e}. Let τ′_{e} = τ_{e}.

Note that in either case we have τ_{e} ⊆ τ′_{e} and A_{e+1} is k_{e+1}-small above τ′_{e}. Let T = T_{e} = {τ′_{e}^{⌢}⟨i⟩ | i ≤ k_{e+1}}. Clearly T is k_{e+1}-large above τ′_{e}, so by Lemma 22.8 let τ_{e+1} ∈ T be such that A_{e+1} is k_{e+1}-small above τ_{e+1}. Thus τ_{e} ⊆ τ′_{e} ⊂ τ_{e+1}. Since this holds for all e we have g = ⋃_{e=0}^{∞} τ_{e} = ⋃_{e=0}^{∞} τ′_{e} ∈ ℕ^{ℕ}.

We claim that DNR_{p} ≰_{w} {g}. To see this, it suffices to show that the eth requirement φ_{e}^{(1),g} ∉ DNR_{p} is satisfied for all e. Fix e and let n = n_{e}. If Case 1 holds at stage e + 1, then we have already seen that the eth requirement is satisfied via method 2. If Case 2 holds at stage e + 1, then ⟨e, n⟩ ∈ F_{e+1}, hence by construction ⟨e, n⟩ ∈ F_{i} for all i ≥ e + 1, hence ⋃_{j<p(n)} A_{e,n,j} ⊆ A_{i} is k_{i}-

small above τ_{i}, hence τ_{i} ∉ ⋃_{j<p(n)} A_{e,n,j}. Thus φ_{e}^{(1),g}(n) ↑ or ≥ p(n) so the eth requirement is satisfied via method 1 or 3. This proves our claim.

To finish the proof of Theorem 22.2, it remains to prove that g is DNR. To this end, consider the set of “non-DNR strings,” i.e.,

B = {τ ∈ ℕ^{<ℕ} | (∃n < |τ|) (τ(n) ≃ φ_{n}^{(1)}(n))}.

We claim that B is 1-small above ⟨⟩. To see this, let T be 1-good above ⟨⟩. We shall construct an increasing sequence of strings σ_{n} ∈ [⟨⟩, T] \ B, n = 0, 1, 2, … with |σ_{n}| = n. Clearly ⟨⟩ ∉ B so we can start with σ_{0} = ⟨⟩. Given σ_{n} ∈ [⟨⟩, T] \ B, if σ_{n} ∉ T there are at least two integers i such that σ_{n}^{⌢}⟨i⟩ ∈ [⟨⟩, T] so choose i ≄ φ_{n}^{(1)}(n). Then clearly σ_{n+1} = σ_{n}^{⌢}⟨i⟩ ∉ B. Eventually for some n we have σ_{n} ∈ T \ B, so T ⊈ B. This proves our claim.

Finally we are ready to prove that g is DNR. Consider the partial recursive functional Ψ :⊆ ℕ^{ℕ} → ℕ^{ℕ} given by

Ψ(g)(n) ≃ \{ \begin{matrix}0 & if g ∉ DNR, \\ ↑ & if g ∈ DNR. \end{matrix}

We may safely assume that 0 is an index of Ψ. (Here we are deviating from the standard indexing of partial recursive functionals, but this deviation is harmless.) Thus for all n and j we have A_{0,n,j} ⊆ B. Recall that F_{0} = ∅ and τ_{0} = ⟨⟩ and k_{0} = 1. Since B is k_{0}-small above τ_{0}, so are A_{0,n,j} for all n and j. Thus at stage 1 we have θ_{0}(n_{0}) ↑, i.e., Case 2 holds. Hence the 0th requirement is satisfied via method 1 or 3. But then since 0 < p(n) we must have φ_{0}^{(1),g}(n) ↑, i.e., g ∈ DNR. This completes the proof of Theorem 22.2.

We now improve Theorem 22.2 as follows.

Definition 22.11. Let p and q be 1-place recursive functions. We say that q is primitive recursive relative to p if q belongs to the smallest class of functions which contains the initial functions and p and is closed under composition and primitive recursion.

Theorem 22.12. Given a total recursive function p, we can find a total recursive function q such that DNR_{q} <_{w} DNR_{p}. Moreover, we can take q to be primitive recursive relative to p.

Proof. Given a total recursive function q, define a string τ to be q-bounded if τ(m) < q(m) for all m < |τ|. The idea of the proof is to let q be sufficiently fast-growing so that the construction for Theorem 22.2 can be carried out using q-bounded strings instead of arbitrary strings. Accordingly, we modify the definition of A_{i,n,j} as follows:

A_{i,n,j} = {τ | φ_{i}^{(1),τ} (n) ≃ j ∧ τ is q-bounded}.

Apart from this change, the construction is exactly as before.

The only difficulty occurs in the transition from τ′_{e} to τ_{e+1}. In order to know that all of the strings in T_{e} = {τ′_{e}^{⌢}⟨i⟩ | i ≤ k_{e+1}} are q-bounded, we need to define q so as to insure that k_{e+1} < q(|τ′_{e}|).

Given m, we wish to define q(m). By the Recursion Theorem we may safely assume that we already know an index of the recursive function q. By the Uniform Recursion Theorem, we know that n_{e} (= the n chosen in stage e + 1) is primitive recursive as a function of F_{e}, τ_{e}, k_{e}. From this it follows that F_{e+1} and k_{e+1} can be found primitive recursively from the finite sequences τ_{0}, τ′_{0}, τ_{1}, τ′_{1}, …, τ_{e}, τ′_{e} and a_{0}, a_{1}, …, a_{e} where

a_{e} = \{ \begin{matrix}1 & if θ_{e}(n_{e}) ↓ \\ 2 & if θ_{e}(n_{e}) ↑ . \end{matrix}

Namely we have F_{0} = ⟨⟩, k_{0} = 1, F_{i+1} = F_{i} and k_{i+1} = k_{i} if a_{i} = 1, F_{i+1} = F_{i} ∪ {⟨i, n⟩} and k_{i+1} = k_{i}(p(n_{i}) + 1) if a_{i} = 2. Let us indicate this dependence as

k_{e+1} = f(#(⟨τ_{0}, τ′_{0}, …, τ_{e}, τ′_{e}⟩), #(⟨a_{0}, …, a_{e}⟩))

where f is a primitive recursive function. Then we let

q(m) = max f(#(⟨τ_{0}, τ′_{0}, …, τ_{e}, τ′_{e}⟩), #(⟨a_{0}, …, a_{e}⟩))

where τ_{0}, τ′_{0}, …, τ_{e}, τ′_{e} and a_{0}, …, a_{e} range over all finite sequences such that

τ_{0} ⊆ τ′_{0} ⊂ τ_{1} ⊆ τ′_{1} ⊂ ⋯ ⊂ τ_{e} ⊆ τ′_{e}

and a_{0}, a_{1}, …, a_{e} ∈ {1, 2} and τ′_{e} is q-bounded and |τ′_{e}| = m. Clearly q is primitive recursive and the construction works.

Definition 22.13. If C is a “nice” class of recursive functions, we define d_{C} = deg_{w}(DNR_{C}), where

DNR_{C} = ⋃_{p∈C} DNR_{p} = {C-bounded DNR functions}.

Note that Corollary 17.2 implies that DNR_{C} is Σ_{3}^{0}, hence inf(d_{C}, 1) ∈ E_{w}.

Examples 22.14. The following classes are considered “nice”.

C = {primitive recursive functions},

C = ER = {elementary recursive functions},

C = PTIME = {polynomial-time computable functions},

C = EXPTIME = {exponential-time computable functions},

and other computational complexity classes as defined in resource-bounded computational complexity. Also, for each ordinal α ≤ ϵ_{0} there is a “nice” class of recursive functions C_{α} consisting of the functions at level ≤ α of the Wainer hierarchy. In particular C_{0} is the class of primitive recursive functions, C_{1} is the class of functions which are primitive recursive in the Ackermann function, and C_{ϵ_{0}} is the class of recursive functions which are provably total in PA.

Corollary 22.15. Given a “nice” class of recursive functions C, we can find a recursive function q such that DNR_{q} <_{w} DNR_{C}.

Proof. We have not defined precisely what we mean by saying that a class of recursive functions C ⊆ REC is “nice”. However, one of our requirements for niceness is that the class C should be recursively enumerable. This means that there is an enumeration C = {p_{i} | i ∈ ℕ} such that p_{i}(n) is recursive as a function of i and n.

If C is “nice” in this sense, consider the recursive function

p(n) = max(2, p_{0}(0), p_{1}(1), …, p_{n}(n)).

We claim that DNR_{p} ≤_{w} DNR_{C}. To see this, consider a C-bounded DNR function g ∈ DNR_{C}. Let i be such that g(n) < p_{i}(n) for all n. Then g(n) < p(n) for all n ≥ i. Since p(n) ≥ 2 for all n, we can easily find a p-bounded DNR function f such that f(n) = g(n) for all n ≥ i. Then f ≤_{T} g and our claim is proved. Now apply Theorem 22.12 to obtain a recursive function q such that DNR_{q} <_{w} DNR_{p}. Then DNR_{q} <_{w} DNR_{C} and we have our corollary.

Remark 22.16. One can consider the following research problems.

1. Refine Theorem 22.12 to calculate better estimates for q given p. The idea here is that, as n goes to infinity, the growth rate of q(n) should be only slightly faster than the growth rate of p(n).

2. Redo the proofs and calculations for Theorem 22.12 and Corollary 22.15 in terms of Kolmogorov complexity. The close relationship between recursively bounded DNR functions and Kolmogorov complexity has been noted earlier, in Theorem 20.10 and Remark 20.16.

We now end this section by improving Theorem 22.2 in another direction.

Theorem 22.17. DNR <_{w} DNR_{REC}.

Proof. It suffices to construct a DNR function g such that DNR_{REC} ≰_{w} {g}. Let p_{s}, e_{s}, s = 0, 1, 2, … be a (non-uniform) enumeration of REC × ℕ, i.e., all ordered pairs p, e such that p is a total recursive function and e ∈ ℕ. We proceed as in the proof of Theorem 22.2 by defining τ_{0} ⊂ τ_{1} ⊂ ⋯ τ_{s} ⊂ τ_{s+1} ⊂ ⋯ and F_{0} ⊆ F_{1} ⊆ ⋯ ⊆ F_{s} ⊆ F_{s+1} ⊆ ⋯ and k_{0} ≤ k_{1} ≤ ⋯ ≤ k_{s} ≤ k_{s+1} ≤ ⋯ and g = ⋃_{s=0}^{∞} τ_{s}. At stage s + 1 we address the sth requirement, φ_{e_{s}}^{(1),g} ∉ DNR_{p_{s}}. Associated with F_{s} is the set

A_{s} = ⋃_{\begin{matrix}⟨r,n⟩∈F_{s} \\ j<p_{r}(n) \end{matrix}}A_{e_{r},n,j} where A_{e,n,j} = \{τ | φ_{e}^{(1),τ} (n) ≃ j\}.

Our inductive hypothesis says that A_{s} is k_{s}-small above τ_{s}. The remaining details are as in the proof of Theorem 22.2.

Remark 22.18. Note that the inequalities in (4) on page 46 follow immediately from Theorems 18.12 and 22.2 and 22.17 and Corollary 22.15.

23 Bounded limit-recursiveness

Definition 23.1. A function g : ℕ → ℕ is said to be limit-recursive if there exists a recursive function g̃: ℕ^{2} → ℕ such that g(n) = lim_{s} g̃(n, s) for all n.

Remark 23.2. Here g̃ is called an approximating function. Think of g̃(n, s), s = 0, 1, 2, … as a sequence of guesses for the true value of g(n) such that eventually these guesses are correct.

Theorem 23.3 (The Limit Lemma). g ≤_{T} 0′ ⇔ g is limit-recursive.

Proof. ⇒: Consider the predicate P (n, t) ≡ (∀s ≥ t) (g̃(n, s) = g̃(n, s + 1)). Let f(n) = the least t such that P (n, t) holds. Clearly f ≤_{T} P ≤_{T} 0′. But g(n) = g̃(n, f(n)), hence g ≤_{T} 0′, Q.E.D.

(⇐) Assume g ≤ 0′, say g(n) = φ_{e}^{(1),0′}(n) for all n. Define g̃(n, s) = φ_{e,s}^{(1),0′_{s}↾s}(n) if this is defined, and 0 otherwise, where

0′_{s} = H_{s} = {i | φ_{i,s}^{(1)}(0) ↓}.

Thus g̃(n, s) is recursive, and clearly g(n) = lim_{s} g̃(n, s).

By relativizing we obtain the following.

Theorem 23.4. For any oracle X we have g ≤_{T} X′ ⇔ g is limit-recursive in X, i.e., g(n) = lim g̃(n, s) where g̃ is X-recursive.

We now consider a variant of limit-recursiveness in X.

Definition 23.5. We say that g is boundedly limit-recursive in X if there exists an X-recursive function g̃(n, s) and a recursive function ĝ(n) such that g(n) = lim g̃(n, s) and |{s | g̃(n, s) ≠ g̃(n, s + 1)}| < ĝ(n) for all n. Here ĝ is called a bounding function.

Remark 23.6. The previous definition is not a straightforward relativization to X. This is because the bounding function ĝ is assumed to be recursive (not only X-recursive).

Definition 23.7. We write

BLR(X) = {g ∈ ℕ^{ℕ} | g is boundedly limit-recursive in X}.

Exercise 23.8. For A ⊆ ℕ prove that χ_{A} ∈ BLR(X) with a constant bounding function ⇔ A is a Boolean combination of sets which are Σ_{1}^{0,X}.

Remark 23.9. Note that g ≤_{T} X implies g ∈ BLR(X) which implies that g is limit-recursive relative to X. The converses do not hold. By the Limit Lemma, we may rewrite this as

REC(X) ⊆ BLR(X) ⊆ REC(X′).

The converse inclusions do not hold.

The following lemma makes this relationship more precise.

Lemma 23.10. g ∈ BLR(X) ⇔ g ≤_{T} X′ with recursively bounded use of X′ and unbounded use of X.

Proof. ⇐: Assume g ≤_{T} X′ with recursively bounded use of X′ and (possibly) unbounded use of X. In other words, g(n) = φ_{e}^{(2),X}(X′ ↾ b(n), n), where b(n) is a total recursive function. Let g̃(n, s) = φ_{e,s}^{(2),X↾s}(X′_{s} ↾ b(n), n) if ↓ and 0 otherwise. Clearly g̃ ≤_{T} X and g(n) = lim g̃(n, s). Moreover |{s | g̃(n, s) ≠ g̃(n, s + 1)}| ≤ 2b(n) + 1. So g ∈ BLR(X) via ĝ(n) = 2b(n) + 2.

⇒: Assume g ∈ BLR(X) via g̃ and ĝ. We describe a method of computing g(n) using an oracle for X′. For each i < ĝ(n) ask the X′-oracle whether |{s | g̃(n, s) ≠ g̃(n, s + 1)}| > i. From the answers to these questions, we can immediately read off

k(n) = |{s | g̃(n, s) ≠ g̃(n, s + 1)}|

and then g(n) = g̃(n, t(n)) where t(n) = the least t such that |{s < t | g̃(n, s) ≠ g̃(n, s+1)}| = k(n). Note that we have used X′ only to compute k(n), and thus our use of X′ was bounded by b(n) = max{α(n, i) | i < ĝ(n))} where α(n, i) is a fixed primitive recursive function. Since ĝ is recursive, so is b(n).

Remark 23.11. We shall be interested in the binary relation of BLR-reducibility defined by X ≤_{BLR} Y if and only if BLR(X) ⊆ BLR(Y). Obviously X ≤_{T} Y implies X ≤_{BLR} Y which implies X′ ≤_{T} Y′. The converse implications do not hold. We need the following technical lemma concerning BLR-reducibility.

Lemma 23.12. The following are pairwise equivalent.

1. BLR(X) ⊆ BLR(Y).

2. Given a partial X-recursive function ψ(n), we have g ∈ BLR(Y) where

g(n) = \{ \begin{matrix}ψ(n) + 1 & if ψ(n) ↓, \\ 0 & otherwise. \end{matrix}

3. We can find h ∈ BLR(Y) such that ∀n (φ_{n}^{(1),X}(n) ↓⇒ h(n) = φ_{n}^{(1),X}(n)).

Proof. 1 ⇒ 2 is easy. Let e be an index for ψ, i.e., ψ(n) ≃ φ_{e}^{(1),X}(n) for all n. Let

g̃(n, s) = \{ \begin{matrix}φ_{e,s}^{(1),X↾s}(n) + 1 & if ↓, \\ 0 & if ↑, \end{matrix}

and let ĝ(n) = 2 for all n. Clearly g ∈ BLR(X) via g̃ and ĝ. Hence g ∈ BLR(Y) in view of 1.

2 ⇒ 3 is trivial. Namely, apply 2 to the function ψ(n) ≃ φ_{n}^{(1),X}(n) to get g(n), and then let h(n) = g(n) · − 1.

3 ⇒ 2: As before, let e be an index of ψ. Let θ(n) ≃ the least σ ⊂ X such that φ_{e,|σ|}^{(1),σ}(n) ↓. Clearly θ(n) is partial X-recursive. Let h be as in 3. By the Parametrization Theorem let p(n) be primitive recursive such that θ(n) ≃ φ_{p(n)}^{(1),X}(p(n)). Let

g(n) ≃ \{ \begin{matrix}φ_{e,|h(p(n))|}^{(1),h(p(n))}(n) + 1 & if ↓ \\ 0 & otherwise \end{matrix}

Then g satisfies 2.

2 ⇒ 1: Given f ∈ BLR(X), to show f ∈ BLR(Y). For all n and all i ≤ f̂(n) + 1, let ψ_{i}(n) ≃ the ith successive value of f̃(n, s) as s → ∞. The functions ψ_{i}(n) are uniformly partial X-recursive. By 2 the functions

g_{i}(n) = \{ \begin{matrix}ψ_{i}(n) + 1 & if ψ_{i}(n) ↓, \\ 0 & otherwise \end{matrix}

are uniformly BLR(Y). Let ĝ_{i}(n) be the uniformly recursive bounding functions for g_{i}(n). Let g(n) = g_{i}(n) − 1 for the least i such that g_{i+1}(n) = 0. Clearly f = g ∈ BLR(Y) via the recursive bounding function

ĝ(n) = ∑_{i<f̂(n)} ĝ_{i}(n).

This completes the proof.

Theorem 23.13. The binary relation ≤_{BLR} is Σ_{3}^{0}. Proof. By Lemma 23.12 we have

X ≤_{BLR} Y ≡ (∃h ∈ BLR(Y)) ∀n (φ_{n}^{(1),X}(n) ↓⇒ h(n) = φ_{n}^{(1),X}(n)). Stating this in terms of h̃ and ĥ we have

\begin{matrix}∀n (|\{s | h̃(n, s) ≠ h̃(n, s + 1)\}| < ĥ(n) \\ ∧ (φ_{n}^{(1),X}(n) ↓⇒ ∀s (∃t > s) h̃(n, t) = φ_{n}^{(1),X}(n))). \end{matrix}

In terms of indices for h̃ and ĥ this becomes

∃ẽ ∃ê ∀n (φ(1) ; ê(n) ↓ ∧ ∀s φ(2),Y ; ẽ (n, s) ↓

∧ ∀F (∀s ∈ F) (φ(2),Y ; ẽ (n, s) ≠ φ(2),Y ; ẽ (n, s + 1) ⇒ |F | < φ(1) ; ê(n))

∧ (φ_{n}^{(1),X}(n) ↓⇒ ∀s (∃t > s) (φ(2),Y ; ẽ (n, t) ↓= φ_{n}^{(1),X}(n)))

and a Tarski/Kuratowski computation shows that this is Σ_{3}^{0}. Definition 23.14. Let S be a set of oracles. We define

S^{∗} = {Y | ∃X (X ∈ S ∧ X ≤_{BLR} Y)} = the BLR-upward closure of S. Theorem 23.15. If S is Σ_{3}^{0}, then so is S^{∗}. Proof. By Theorem 5.7 we may assume that S = P is a Π_{1}^{0} subset of ℕ^{ℕ}. We have Y ∈ P^{∗} ≡ (∃f ∈ P) (∃g ∈ BLR(Y)) ∀i (g(2i) = f(i) ∧ ∀n (φ_{n}^{(1),f}(n) ↓⇒ g(2n + 1) = φ_{n}^{(1),f}(n))). The idea here is that g = f ⊕ h where h is a total function extending φ_{n}^{(1),f}(n) as in the previous lemma. A Tarski/Kuratowski computation shows that P^{∗} is Σ_{3}^{0}. Remark 23.16. Clearly S_{1} ≤_{w} S_{2} implies S_{1}^{∗} ≤_{w} S_{2}^{∗}. This is trivial, because ≤_{T} implies ≤_{BLR}. Definition 23.17. If s = deg_{w}(S) let s^{∗} = deg_{w}(S^{∗}). Remark 23.18. The previous remark shows that s^{∗} is well defined. Moreover s_{1} ≤ s_{2} implies s_{1}^{∗} ≤ s_{2}^{∗}. We also have s^{∗∗} = s^{∗} ≤ s and inf(s_{1}, s_{2})^{∗} = inf(s_{1}^{∗}, s_{2}^{∗}). Remark 23.19. From Theorem 23.15 plus the Embedding Lemma, we know that s ∈ E_{w} implies s^{∗} ∈ E_{w}. As a research problem, it would be interesting to investigate degrees in E_{w} such as 1^{∗}, r_{1}^{∗}, inf(r_{2}, 1)^{∗}, d_{REC}^{∗}, d^{∗}, etc. It can be shown that d^{∗} ≠ 0, hence none of the mentioned degrees is 0.

24 Embedding hyperarithmeticity into E_{w}

Definition 24.1. For each α < ω_{1}^{CK} let 0^{(α)} = the αth Turing jump of 0. This is the hyperarithmetical hierarchy. There is a theorem of Spector saying that 0^{(α)} is well defined up to Turing degree. In particular we have the initial segment 0, 0′, 0′′, …, 0^{(n)}, 0^{(n+1)}, … for n ∈ ℕ. By Post’s Theorem, a set A ⊆ ℕ is Δ_{n+1}^{0} if and only if it is ≤_{T} 0^{(n)}, so this is equivalent to the arithmetical hierarchy. In fact, A is Σ_{n+1}^{0} if and only if A is Σ_{1}^{0,0^{(n)}}.

Lemma 24.2. 0^{(α)} is a Π_{2}^{0} singleton.

Proof. We omit the proof, but see Theorem 10.6.

Remark 24.3. It follows that {0^{(α)}} is Σ_{3}^{0}. Let h_{α} = deg_{w}({0^{(α)}}). Then h_{α}^{∗} = deg_{w}({X | 0^{(α)} ≤_{BLR} X}). By Theorem 23.15 plus the Embedding Lemma we have inf(h_{α}^{∗}, 1) ∈ E_{w}. We shall prove that inf(h_{α}^{∗}, 1) < inf(h_{β}^{∗}, 1) for all α < β < ω_{1}^{CK}. Thus we shall have an embedding of the hyperarithmetical hierarchy into E_{w}.

Lemma 24.4. Given a Turing oracle X, we can find a 1-generic g ∈ ℕ^{ℕ} such that BLR(X) = BLR(g), i.e., X ≡_{BLR} g.

Proof. This is similar to the proof of the Friedberg Jump Theorem. Recall that g is 1-generic if for each n either φ_{n}^{(1),g}(0) ↓ or (∃σ ⊂ g) (∀τ ⊇ σ) φ_{n}^{(1),τ} (0) ↑.

Given X, define h(n) = φ_{n}^{(1),X}(n) + 1 if φ_{n}^{(1),X}(n) ↓, 0 if φ_{n}^{(1),X}(n) ↑. Recall that X ≤_{BLR} Y ⇔ h ∈ BLR(Y). We shall obtain g as g = ⋃_{n=0}^{∞} τ_{n} where τ_{0} ⊂ τ_{1} ⊂ τ_{2} ⊂ ⋯ ⊂ τ_{n} ⊂ τ_{n+1} ⊂ · · ·.

Stage 0: Let τ_{0} = ⟨⟩.

Stage n + 1: Let τ′_{n} = τ_{n}^{⌢}⟨h(n)⟩. Ask the oracle 0′ whether ∃τ ⊇ τ′_{n} such that φ_{n,|τ|}^{(1),τ}(n) ↓. If so, let τ_{n+1} = the least such τ. Otherwise let τ_{n+1} = τ′_{n}.

By construction g = ⋃_{n=1}^{∞} τ_{n} is 1-generic. Moreover, the entire construction (i.e., the sequence of strings τ_{n}, n = 0, 1, 2, …) is boundedly limit-recursive in each of the oracles X and g, with bounding function 4^{n}. Because h(n) = τ_{n+1}(|τ_{n}|) = g(|τ_{n}|) and φ_{n}^{(1),g}(n) ≃ φ_{n,|τ_{n+1}|}^{(1),τ_{n+1}}(n), it follows that BLR(X) = BLR(g), Q.E.D.

Theorem 24.5. For each α < ω_{1}^{CK} we have inf(h_{α}^{∗}, 1) ∈ E_{w}. Moreover, for all α < β < ω_{1}^{CK} we have inf(h_{α}^{∗}, 1) < inf(h_{β}^{∗}, 1), in fact inf(h_{α}^{∗}, d) < inf(h_{β}^{∗}, d).

Proof. Apply the previous lemma to get a 1-generic g such that 0^{(α)} ≡_{BLR} g. Since 0^{(β)} ≰_{BLR} 0^{(α)} we have 0^{(β)} ≰_{BLR} g, i.e., {X | 0^{(β)} ≤_{BLR} X} ≰_{w} {g}. By Lemma 19.9 we also have DNR ≰_{w} {g}. Thus inf(h_{β}^{∗}, d) ≰ h_{α}^{∗}. It follows that inf(h_{α}^{∗}, d) < inf(h_{β}^{∗}, d), Q.E.D.