Topics in Logic and Foundations: Spring 2005

Stephen G. Simpson

Copyright \begin{matrix}c \\ ◯ \end{matrix} 2005

First Draft: April 29, 2005

This Draft: November 1, 2005

The latest version is available at

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

Please send corrections to <simpson@math.psu.edu>.

This is a set of lecture notes from a 15-week graduate course at the Pennsylvania State University taught as Math 574 by Stephen G. Simpson in Spring 2005. The course was intended for students already familiar with the basics of mathematical logic. The course covered some topics which are important in contemporary mathematical logic and foundations but usually omitted from introductory courses.

These notes were typeset by the students in the course: John Ethier, Esteban Gomez-Riviere, David King, Carl Mummert, Michael Rowell, Chenying Wang. In addition, the notes were revised and polished by Stephen Simpson.

Contents

Contents 1

1 Unsolvability of Hilbert’s Tenth Problem 3 1.1 Hilbert’s Tenth Problem . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Σ_{1} Relations and Functions . . . . . . . . . . . . . . . . . . . . . 5 1.3 Diophantine Relations and Functions . . . . . . . . . . . . . . . . 7 1.4 Bounded Universal Quantification . . . . . . . . . . . . . . . . . 9 1.5 The Pell Equation . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.2 Divisibility Properties of y_{n} . . . . . . . . . . . . . . . . . 14 1.5.3 Congruence Properties of x_{n} . . . . . . . . . . . . . . . . 15 1.5.4 Diophantine Definability of x_{n} and y_{n} . . . . . . . . . . . 16

1.6 Proof of the Main Lemma . . . . . . . . . . . . . . . . . . . . . . 17

2 Unsolvability of the Word Problem for Groups 21 2.1 Finitely Presented Semigroups . . . . . . . . . . . . . . . . . . . 21 2.2 The Boone Group . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3 HNN Extensions and Britton’s Lemma . . . . . . . . . . . . . . . 30 2.4 Free Products With Amalgamation . . . . . . . . . . . . . . . . . 32 2.5 Proof of 3 ⇒ 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.6 Proof of Britton’s Lemma . . . . . . . . . . . . . . . . . . . . . . 36 2.7 Proof of 2 ⇒ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.8 Some Refinements . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.9 Unsolvability of the Triviality Problem . . . . . . . . . . . . . . . 41

3 Recursively Enumerable Sets and Degrees 44 3.1 The Lattice of R.E. Sets . . . . . . . . . . . . . . . . . . . . . . . 44 3.2 Many-One Completeness . . . . . . . . . . . . . . . . . . . . . . . 48 3.3 Creative Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Simple Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.5 Lattice-Theoretic Properties . . . . . . . . . . . . . . . . . . . . . 54 3.6 The Friedberg Splitting Theorem . . . . . . . . . . . . . . . . . . 55 3.7 Maximal Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.8 The Owings Splitting Theorem and its Consequences . . . . . . . 59 3.9 Proof of the Owings Splitting Theorem . . . . . . . . . . . . . . . 62 3.10 Oracle Computations . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.11 Degrees of Unsolvability . . . . . . . . . . . . . . . . . . . . . . . 67 3.12 The Sacks Splitting Theorem and its Consequences . . . . . . . . 69 3.13 Proof of the Sacks Splitting Theorem . . . . . . . . . . . . . . . . 71 3.14 Finite Approximations . . . . . . . . . . . . . . . . . . . . . . . . 73 3.15 Proof of the Binns Splitting Theorem . . . . . . . . . . . . . . . 75 3.16 Some Additional Results . . . . . . . . . . . . . . . . . . . . . . . 77

4 Randomness 78 4.1 Measure-Theoretic Preliminaries . . . . . . . . . . . . . . . . . . 78 4.2 Effective Randomness . . . . . . . . . . . . . . . . . . . . . . . . 80 4.3 Randomness Relative to an Oracle . . . . . . . . . . . . . . . . . 84

Bibliography 87

Chapter 1

Unsolvability of Hilbert’s Tenth Problem

1.1 Hilbert’s Tenth Problem

Definition 1.1.1 (Hilbert’s Tenth Problem). Given a polynomial p with integer coefficients, to decide whether there exist integers w_{1}, …, w_{n} such that p(w_{1}, …, w_{n}) = 0.

Definition 1.1.2. A Diophantine equation is an equation of the form

p(w_{1}, …, w_{n}) = 0

where p(w_{1}, …, w_{n}) is a polynomial with integer coefficients, i.e., coefficients from ℤ. Hilbert’s Tenth Problem is: to find an algorithm for deciding whether a given Diophantine equation has an integer solution, i.e., w_{1}, …, w_{n} ∈ ℤ.

Hilbert proposed this problem in 1900. There was no progress until the 1950s, when M. Davis conjectured that Hilbert’s Tenth Problem is unsolvable, i.e., no such algorithm exists. Davis, Putnam, and J. Robinson made further progress toward this result, and Matiyasevich completed the proof in 1969.

A typical method for showing that a problem P is unsolvable is to reduce the Halting Problem to P. Thus, a solution for P would give a solution to the Halting Problem, and as the Halting Problem is known to be unsolvable, P must then also be unsolvable. This is the method used here. We shall show that the Halting Problem is reducible to Hilbert’s Tenth Problem.

The starting point for our presentation is the undecidability of true firstorder arithmetic, T_{1}. Let the language L_{1} consist of {+, ×, 0, 1, =}, where + and × are binary operations, 0 and 1 are constants, and = is a binary relation. The terms of L_{1} are variables x, y, z, …, the constants 0 and 1, and t_{1} + t_{2}, t_{1} × t_{2} where t_{1}, t_{2} are terms. The formulas of L_{1} are atomic formulas t_{1} = t_{2} where t_{1}, t_{2} are terms, and ¬ A, A ∨ B, A ∧ B, A ⇒ B, A ⇔ B, ∃x A, ∀x A, where A, B are formulas and x is a variable. As usual, a sentence is a formula with no free variables.

Let ℕ = {0, 1, 2, …}, the set of natural numbers. We also use ℕ to denote the structure

(ℕ, +, ×, 0, 1, =),

i.e., the intended model of first-order arithmetic. Formulas of L_{1} may be interpreted as usual in ℕ, and each sentence of L_{1} is either true or false in ℕ. A theorem of Tarski says there is no algorithm to determine the truth value of an L_{1}-sentence in ℕ. T_{1} is the complete theory consisting of all sentences of L_{1} which are true in ℕ. Thus Tarski’s result is that the theory T_{1} is undecidable. Actually, Tarski shows that the Halting Problem H and many other noncomputable sets and functions are definable over ℕ, i.e., definable over T_{1}.

When interpreted in ℕ, terms of L_{1} are equivalent to polynomials with positive integer coefficients. For example, the term (x+y)×((1+1)×z+y) is equivalent over ℕ to 2xz+xy+2yz+y^{2}, which is a polynomial in ℕ[x, y, z]. Atomic formulas of L_{1} are similarly equivalent to Diophantine equations: p(x_{1}, …, x_{n}) = q(x_{1}, …, x_{n}) is equivalent to

p(x_{1}, …, x_{n}) − q(x_{1}, …, x_{n}) = 0,

and this is a typical Diophantine equation. Thus the existential sentence

∃x_{1} ⋯ ∃x_{n} p(x_{1}, …, x_{n}) = q(x_{1}, …, x_{n})

holds in ℕ if and only if the Diophantine equation p(x_{1}, …, x_{n})−q(x_{1}, …, x_{n}) = 0 has at least one solution in ℕ.

Accordingly, we consider a modified form of Hilbert’s Tenth Problem.

Definition 1.1.3 (Modified Hilbert’s Tenth Problem). Given a polynomial p(x_{1}, …, x_{n}) with coefficients from ℤ, to decide whether there exist x_{1}, …, x_{n} ∈ ℕ such that p(x_{1}, …, x_{n}) = 0.

Remark 1.1.4. The Modified Hilbert’s Tenth Problem is equivalent to the original problem. Suppose first that the Modified Hilbert’s Tenth Problem were solvable. Then the Diophantine equation p(w_{1}, …, w_{n}) = 0 has integer solutions if and only if ∃x_{1} ⋯ ∃x_{n} ∈ ℕ such that p(±x_{1}, …, ±x_{n}) = 0, so Hilbert’s Tenth Problem would be solvable. Conversely, if Hilbert’s Tenth Problem were solvable, then p(x_{1}, …, x_{n}) = 0 has natural number solutions if and only if p(t_{1}^{2} +u_{1}^{2} +v_{1}^{2} +w_{1}^{2}, …, t_{n}^{2} +u_{n}^{2} +v_{n}^{2} +w_{n}^{2}) = 0 has integer solutions, so the Modified Hilbert’s Tenth Problem would also be solvable. This relies on Lagrange’s Theorem: every natural number is the sum of four squares.

Note that Tarski’s Theorem and the Modified Hilbert’s Tenth Problem both deal with different kinds of definability over ℕ. We use the proof of Tarski’s Theorem (see our Math 558 notes [14]) as the starting point for our proof of unsolvability of the Modified Hilbert’s Tenth Problem.

1.2 Σ_{1} Relations and Functions

To warm up, we consider yet another kind of definability over ℕ.

Definition 1.2.1 (Δ_{0} formulas). The Δ_{0} formulas of L_{1} are the smallest class of formulas closed under propositional connectives (∧, ∨, ¬, ⇒, ⇔) and bounded quantification (∀x < t, ∃x < t, where t is a term not mentioning x).

Definition 1.2.2 (Δ_{0} relations and functions). A relation R ⊆ ℕ^{k} is Δ_{0} if it is definable by a Δ_{0} formula. A partial function ψ from ℕ^{k} to ℕ is Δ_{0} if graph(ψ) is Δ_{0}.

Example 1.2.3. The “less than” relation x < y is definable by the Δ_{0} formula ∃z < y (x + z + 1 = y).

Remark 1.2.4. The Δ_{0} relations are only a small subclass of the primitive recursive relations. Nevertheless, many interesting relations are Δ_{0}. E.g., a result of Bennett shows that the 3-place exponential relation x^{y} = z is Δ_{0}. We omit the proof.

Definition 1.2.5 (Σ_{1} formulas). A formula G is Σ_{1} it is of the form ∃x F where F is Δ_{0}.

Definition 1.2.6 (Σ_{1} relations and functions). A relation R ⊆ ℕ^{k} is Σ_{1} if it is definable over ℕ by a Σ_{1} formula. A partial function ψ from ℕ^{k} to ℕ is Σ_{1} if graph(ψ) is Σ_{1}.

We shall prove the following theorem.

Theorem 1.2.7. R is Σ_{1} if and only if R is recursively enumerable, i.e., Σ_{1}^{0}. ψ is Σ_{1} if and only if ψ is partial recursive.

The forward direction of the theorem is obvious, as Σ_{1} relations are clearly Σ_{1}^{0}, and Σ_{1} partial functions are clearly partial recursive. (See my Math 558 notes [14].) We must show the converse direction. In particular, we must show that all primitive recursive functions are Σ_{1}.

Lemma 1.2.8. The class of Σ_{1} relations is closed under unbounded existential quantification, logical and, logical or, and bounded quantification.

Proof. Suppose G is Σ_{1}. Then ∃x G is equivalent to ∃x ∃y F, where F is Δ_{0}. This is then equivalent to ∃z ∃x < z ∃y < z F which is Σ_{1}.

If ∃x F and ∃x G are both Σ_{1}, then ∃x F ∧ ∃x G ≡ ∃x ∃y (F ∧ G). F ∧ G is Δ_{0} and so the formula is Σ_{1}. The case for disjunction is similar.

Also, ∃x < t ∃y F ≡ ∃y ∃x < t F and so the class of Σ_{1} relations is closed under bounded existential quantification.

We have ∀x < t ∃y F ≡ ∃z ∀x < t ∃y < z F. The formula ∀x < t ∃y < z F is Δ_{0} and thus the whole formula is Σ_{1} as required. Thus the class of Σ_{1} relations is closed under bounded universal quantification.

To finish the proof of Theorem 1.2.7, we now briefly review Gödel’s β function. The β function is a method of coding arbitrarily long finite sequences of integers in an arithmetically effective way.

Lemma 1.2.9. For all k there exist infinitely many a such that

a + 1, 2a + 1, …, ka + 1

are pairwise relatively prime.

Proof. Let a be any muliple of k!. If ia + 1 and ja + 1 are not relatively prime, 1 ≤ i < j ≤ k, let p be a prime dividing both ia + 1 and ja + 1. In particular p does not divide a. Thus p > k by our choice of a. On the other hand, p divides (ja + 1) − (ia + 1) = (j − i)a, so p divides j − i. This contradicts p > k.

The following is a well known result in number theory. We omit its proof. See the Math 558 notes [14].

Lemma 1.2.10 (Chinese Remainder Theorem). Let m_{1}, …, m_{k} be pairwise relatively prime. Given r_{1}, …, r_{k} such that 0 ≤ r_{i} < m_{i} for i = 1, …, k, we can find r such that r ≡ r_{i} mod m_{i} for all i = 1, …, k.

Definition 1.2.11 (the β function). We define

β(a, r, i) = Rem(r, a · (i + 1) + 1)

where Rem(y, x) is the remainder of y on division by x.

Corollary 1.2.12. Given r_{0}, …, r_{k} ≥ 0, we can find a, r ≥ 0 such that β(a, r, i) = r_{i} for all i = 0, …, k.

Proof. By Lemma 1.2.9 above, let a be such that a+1, 2a+1, …, (k+1)a+1 are pairwise relatively prime, and a > max(r_{0}, …, r_{n}). By the Chinese Remainder Theorem, we can find r such that r ≡ r_{i} mod a(i + 1) + 1 for i = 0, …, k. Thus β(a, r, i) = r_{i} for i = 0, …, k.

Lemma 1.2.13. The β function is Σ_{1}.

Proof. It suffices to show that Rem is Σ_{1}. We have

Rem(y, x) = r ⟺ r < x ∧ ∃q < y (y = qx + r) .

Thus Rem and the β function are Δ_{0}, hence Σ_{1}.

Lemma 1.2.14. All primitive recursive functions are Σ_{1}.

Proof. Z(x) = 0 is Σ_{1} via y = 0.

S(x) = x + 1 is Σ_{1} via y = x + 1.

P_{ki}(x_{1}, …, x_{n}) = x_{i} is Σ_{1} via y = x_{i}.

Given f(x_{1}, …, x_{n}) = h(g_{1}(x_{1}, …, x_{n}), …, g_{m}(x_{1}, …, x_{n}))), where h, g_{1}, …, g_{m} are Σ_{1}, we have that f is Σ_{1}, because

y = f(x_{1}, …, x_{n}) ⟺ ∃z_{1} ⋯ ∃z_{m} (y = h(z_{1}, …, z_{m})) ∧ ⋀_{i=1}^{m} z_{i} = g_{i}(x_{1}, …, x_{n})) .

Thus the class of Σ_{1} functions is closed under composition.

Given f(x_{1}, …, x_{n}) defined by

f(0, x_{1}, …, x_{n}) = g(x_{1}, …, x_{n})
f((x + 1, x_{1}, …, x_{n}) = h(x, f(x, x_{1}, …, x_{n}), x_{1}, …, x_{n})

where g, h are Σ_{1}, f is Σ_{1} because

y = f(x, x_{1}, …, x_{n}) ⟺ ∃⟨y_{0}, y_{1}, …, y_{x}⟩ (y_{0} = g(x_{1}, …, x_{n}) ∧
(∀i < x) y_{i+1} = h(i, y_{i}, x_{1}, …, x_{n}))
⟺ ∃a ∃r (β(a, r, 0) = g(x_{1}, …, x_{n}) ∧ β(a, r, x) = y ∧
(∀i < x) β(a, r, i + 1) = h(i, β(a, r, i), x_{1}, …, x_{n})) .

Thus the class of Σ_{1} functions is closed under primitive recursion.

It now follows that all primitive recursive functions are Σ_{1}.

We can now prove:

Theorem 1.2.15. If ψ : ℕ^{k} ⟶^{P} ℕ is partial recursive, then ψ is Σ_{1}.

Proof. Let e be an index of ψ, i.e., the Gödel number of a program which computes ψ. Then ψ = φ_{e}^{(k)}, i.e., ψ(x_{1}, …, x_{k}) ≃ y ⟺ φ_{e}^{(k)}(x_{1}, …, x_{k}) ≃ y ⟺ ∃n (State(e, x_{1}, …, x_{k}, n))_{0} = 0 ∧ (State(e, x_{1}, …, x_{k}, n))_{k+1} = y), where (State(e, x_{1}, …, x_{k}, n))_{0} and (State(e, x_{1}, …, x_{k}, n))_{k+1} are primitive recursive functions (see Math 558 notes [14]). Thus ψ is Σ_{1}.

The proof of Theorem 1.2.7 is now complete.

Corollary 1.2.16. The Halting Problem H is Σ_{1}.

1.3 Diophantine Relations and Functions

Definition 1.3.1. A relation R ⊆ ℕ^{k} is said to be Diophantine if there exists a polynomial p(x_{1}, …, x_{k}, y_{1}, …, y_{n}) with coefficients from ℤ, such that

R = {⟨x_{1}, …, x_{k}⟩ ∈ ℕ^{k} | ∃y_{1} ⋯ ∃y_{n} p(x_{1}, …, x_{k}, y_{1}, …, y_{n}) = 0} .

Here y_{1}, …, y_{n} range over ℕ. A partial function ψ is said to be Diophantine if graph(ψ) is Diophantine.

The following theorem is due to Matiyasevich 1969. It is known as Matiyasevich’s Theorem, or as the MDRP Theorem (standing for Matiyasevich, Davis, Robinson, Putnam).

Theorem 1.3.2 (MDRP Theorem). R is Diophantine ⟺ R is Σ_{1}. ψ is Diophantine ⟺ ψ is partial recursive.

Corollary 1.3.3. The Halting Problem H = {e | φ_{e}^{(1)}(0) ↓} ⊆ ℕ is Diophantine.

Corollary 1.3.4. Hilbert’s Tenth Problem is unsolvable.

So, our goal now is to prove the MDRP Theorem.

Note that the forward direction of the MDRP Theorem is obvious, as ψ Diophantine implies ψ Σ_{1}, which implies ψ partial recursive. For the converse, we must show that all partial recursive functions are Diophantine.

By Theorem 1.2.7, it suffices to show that all Σ_{1} functions are Diophantine. We begin with the following easy lemma.

Lemma 1.3.5. The binary relation < is Diophantine. The class of Diophantine relations is closed under unbounded existential quantification, logical and, logical or, and bounded existential quantification.

Proof. Clearly < is Diophantine, since x < y ⟺ ∃z (x + z + 1 = y).

If R(x_{1}, …, x_{k}, y) ≡ ∃\overline{z} p(x_{1}, …, x_{k}, y, \overline{z}) = 0 is Diophantine, then so is ∃y R(x_{1}, …, x_{k}, y) ≡ ∃y ∃\overline{z} p(x_{1}, …, x_{k}, y, \overline{z}) = 0, so trivially the class of Diophantine relations is closed under unbounded existential quantification.

Suppose R_{1} = \{⟨x_{1}, …, x_{k}⟩ ∈ ℕ^{k} | ∃\overline{y} p(x_{1}, …, x_{k}, \overline{y}) = 0\} and R_{2} = \{⟨x_{1}, …, x_{k}⟩ ∈ ℕ^{k} | ∃\overline{z} q(x_{1}, …, x_{k}, \overline{z}) = 0\} are both Diophantine. We then have

∃\overline{y} p(x_{1}, …, x_{k}, \overline{y}) = 0 ∧ ∃\overline{z} q(x_{1}, …, x_{k}, \overline{z}) = 0 ⟺
∃\overline{y} ∃\overline{z} (p(x_{1}, …, x_{k}, \overline{y}) = 0 ∧ q(x_{1}, …, x_{k}, \overline{z}) = 0) ⟺
∃\overline{y} ∃\overline{z} (p(x_{1}, …, x_{k}, \overline{y})^{2} + q(x_{1}, …, x_{k}, \overline{z})^{2} = 0)

so R_{1} ∧ R_{2} is Diophantine. Thus the class of Diophantine relations is closed under logical and.

Similarly, for logical or, we have

∃\overline{y} p(x_{1}, …, x_{k}, \overline{y}) = 0 ∨ ∃\overline{z} q(x_{1}, …, x_{k}, \overline{z}) = 0 ⟺
∃\overline{y} ∃\overline{z} (p(x_{1}, …, x_{k}, \overline{y}) = 0 ∨ q(x_{1}, …, x_{k}, \overline{z}) = 0) ⟺
∃\overline{y} ∃\overline{z} p(x_{1}, …, x_{k}, \overline{y}) · q(x_{1}, …, x_{k}, \overline{z}) = 0

so R_{1} ∨ R_{2} is Diophantine. Thus the class of Diophantine relations is closed under logical or.

We also have (∃x < t) ∃\overline{y} p(x, x_{1}, …, x_{n}, \overline{y}) = 0 if and only if ∃x (x < t ∧ ∃\overline{y} p(x, x_{1}, …, x_{n}, \overline{y}) = 0). Thus the class of Diophantine relations is closed under bounded existential quantification.

In addition, we have the following easy lemma.

Lemma 1.3.6. Addition, multiplication, and the functions Quot and Rem given by

y = qx + r, r < x, Quot(y, x) = q, Rem(y, x) = r

as well as the Gödel β function are Diophantine. The class of Diophantine functions is closed under composition.

Proof. Trivially + and · are Diophantine. We have Quot(y, x) = q ⟺ ∃r (r < x ∧ y = qx + r), so Quot is Diophantine, and similarly for Rem. Closure under composition is easy, as in the proof of Lemma 1.2.14. It now follows that β is Diophantine.

By Lemma 1.3.5, to prove the MDRP Theorem, it remains only to show that the class of Diophantine relations is closed under bounded universal quantification. This is the hard part of the proof. Note that bounded universal quantification was crucial in the proof of Lemma 1.2.14.

We shall follow the exposition of Davis [5]. Most of the work is contained in the following lemma.

Lemma 1.3.7 (Main Lemma). The following functions are Diophantine.

1. (n, k) ↦ n^{k}

2. (n, k) ↦ \binom{n}{k}

3. n ↦ n!

4. (a, b, k) ↦ ∏_{i=0}^{k}(a + bi)

The proof of the Main Lemma is difficult, and we postpone it to Section 1.6 below.

1.4 Bounded Universal Quantification

Our goal is to show that if R is Σ_{1} then R is Diophantine. As we have already seen, it suffices to prove that the class of Diophantine relations is closed under bounded universal quantification. Here is a flawed attempt at a proof of this.

Flawed Proof. We attempt to imitate the proof of Lemma 1.2.14 using the idea of coding via Gödel’s β function. Assume that

(∀i)_{1≤i≤k} ∃y_{1} ⋯ ∃y_{n} p(k, i, …, y_{1}, …, y_{n}) = 0.

For each 1 ≤ i ≤ k pick witnesses y_{1}^{(i)}, …, y_{n}^{(i)} such that p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)}) = 0. Let u be an upper bound for k and y_{j}^{(i)}, 1 ≤ i ≤ k, 1 ≤ j ≤ n. Let t be any multiple of u!. By the proof of Lemma 1.2.9, the moduli t + 1, …, kt + 1 are pairwise relatively prime. By the Chinese Remainder Theorem 1.2.10, we can find r_{1}, …, r_{n} such that r_{j} ≡ y_{j}^{(i)} mod it + 1 for all 1 ≤ i ≤ k, 1 ≤ j ≤ n. Hence for 1 ≤ i ≤ k we have

p(k, i, …, r_{1}, …, r_{n}) ≡ 0 mod it + 1.

Form the product ∏_{i=1}^{k}(it + 1) = ct + 1. We have 0 ≡ it + 1 ≡ ct + 1 mod it + 1. Multiplying by c and i respectively, we have 0 ≡ cit + c ≡ cit + i mod it + 1, which implies c ≡ i mod it + 1. It follows that p(k, c, …, r_{1}, …, r_{n}) ≡ 0 mod it + 1 for all i, 1 ≤ i ≤ k. Since the it + 1, 1 ≤ i ≤ k are pairwise relatively prime, we have

p(k, c, …, r_{1}, …, r_{n}) ≡ 0 mod ∏_{i=1}^{k}(it + 1)
≡ 0 mod ct + 1.

The upshot is that we have “packaged” all of our equations for 1 ≤ i ≤ k into one equation. But our problem is that it is only modulo ct + 1.

Conversely, assume t is a multiple of u!, u ≥ k, ct + 1 = ∏_{i=1}^{k}(it + 1) and ∃r_{1} ⋯ ∃r_{n} p(k, c, …, r_{1}, …, r_{n}) ≡ 0 mod ct + 1. As before we have c ≡ i mod it + 1 for each 1 ≤ i ≤ k. Let y_{j}^{(i)} = Rem(r_{j}, it + 1). Then r_{j} ≡ y_{j}^{(i)} mod it + 1, hence p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)}) ≡ 0 mod it + 1. If we knew that

|p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)})| < it + 1,

we could conclude

p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)}) = 0

and we would be finished.

In order to repair this flawed argument, we first present a simple lemma, Lemma 1.4.1. After that, the proof of closure under bounded universal quantification is given by Lemma 1.4.2.

Lemma 1.4.1. Given a polynomial p(k, i, …, y_{1}, …, y_{n}) we can find a polynomial q(k, …, u) such that

1. q(k, …, u) ≥ u

2. q(k, …, u) ≥ k

3. q(k, …, u) ≥ |p(k, i, …, y_{1}, …, y_{n})| for all i ≤ k and y_{1}, …, y_{n} ≤ u.

Proof. Let q(k, …, u) = |p|(k, k, …, u, …, u) + u + k where |p| is just p with all coefficients replaced by their absolute values.

Lemma 1.4.2. (∀i)_{1≤i≤k}∃y_{1} ⋯ ∃y_{n} p(k, i, …, y_{1}, …, y_{n}) = 0 if and only if there exist u, t, c, r_{1}, …, r_{n} such that:

1. t = q(k, …, u)!, 2. ct + 1 = ∏_{i=1}^{k}(it + 1) divides each of ∏_{y=0}^{u}(r_{j} − y), 1 ≤ j ≤ n,

3. p(k, c, …, r_{1}, …, r_{n}) ≡ 0 mod ct + 1.

The point of this lemma is that, by 1.3.7, the right-hand side is Diophantine. Thus we see that the class of Diophantine relations is closed under bounded universal quantification.

Proof. ⇒: As before, we can find u, t, c, r_{1}, …, r_{n} such that

p(k, c, …, r_{1}, …, r_{n}) ≡ 0 mod ct + 1

and r_{j} ≡ y_{j}^{(i)} mod it + 1. Thus it + 1 divides r_{j} − y_{j}^{(i)}. Since y_{j}^{(i)} ≤ u, it + 1 divides ∏_{y=0}^{u}(r_{j} − y). Since it + 1, 1 ≤ i ≤ k are pairwise relatively prime, it follows that ct + 1 divides ∏_{y=0}^{u}(r_{j} − y) for 1 ≤ j ≤ n, as required.

⇐: For each 1 ≤ i ≤ k pick a prime divisor p_{i} of it+1. Since t = q(k, …, u)!, we have p_{i} > q(k, …, u). Let y_{j}^{(i)} = Rem(r_{j}, p_{i}). Note that y_{j}^{(i)} < p_{i}. We claim y_{j}^{(i)} ≤ u. To see this, note that p_{i} divides it+1 which divides ct+1 which divides ∏_{y=0}^{u}(r_{j} − y), hence p_{i} divides r_{j} − y for some y ≤ u. Then y ≡ r_{j} ≡ y_{j}^{(i)} mod

p_{i}. Noting also that y ≤ u ≤ q(k, …, u) < p_{i}, we see that y = y_{j}^{(i)}. Therefore y_{j}^{(i)} ≤ u.

Next we claim that p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)}) = 0 for 1 ≤ i ≤ k. By assumption we have p(k, c, …, r_{1}, …, r_{n}) ≡ 0 mod ct + 1. Recall that ct + 1 = ∏_{i=1}^{k} it + 1 and c ≡ i mod it + 1. Therefore c ≡ i mod p_{i}. Moreover r_{i} ≡ y_{j}^{(i)} mod p_{i}, so

p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)}) ≡ 0 mod ct + 1
≡ 0 mod it + 1
≡ 0 mod p_{i}.

Since y_{1}^{(i)}, …, y_{n}^{(i)} ≤ u, we have |p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)})| ≤ q(k, …, u) < p_{i}. Hence p(k, i, …, y_{1}^{(i)}, …, y_{n}^{(i)}) = 0 and our lemma is proved.

Lemma 1.4.2 shows that the class of Diophantine relations is closed under bounded universal quantification. This completes the proof of the MDRP Theorem 1.3.2, except that it remains to prove the Main Lemma.

1.5 The Pell Equation

The Main Lemma 1.3.7 asserts that the exponential function (n, k) ↦ n^{k} and similar functions are Diophantine. In order to prove this, we need a Diophantine function which is of exponential growth. It turns out that the solutions of a particular Diophantine equation known as Pell’s equation not only grow exponentially but also are convenient in other ways. Following Davis ([5], reprinted in [6, Appendix]), we give a self-contained, elementary presentation of all of the number theory which we shall use.

1.5.1 Basic Properties

We begin with basic properties of the Pell equation. Definition 1.5.1 (the Pell equation). A Pell equation is an equation of the form x^{2} − dy^{2} = 1 where d = a^{2} − 1, a ≥ 2, a ∈ ℕ. Examples 1.5.2.

1. a = 2, x^{2} − 3y^{2} = 1.

2. a = 3, x^{2} − 8y^{2} = 1.

3. a = 4, x^{2} − 15y^{2} = 1. Remark 1.5.3. If (x, y) is any integer solution of the Pell equation, then clearly

(x + y\sqrt{d})(x − y\sqrt{d}) = x^{2} − dy^{2} = 1.

Furthermore, (x, y) is a solution if and only if (|x|, |y|) is a solution, so we may focus on solutions with x, y ≥ 0. In this case we have x+y\sqrt{d} ≥ 1, with equality only if (x, y) = (1, 0). Remark 1.5.4. There are two obvious solutions of the Pell equation, (1, 0) and (a, 1). Moreover, there is an easy way of generating more solutions, as follows. Lemma 1.5.5. If (x, y) and (x′, y′) are integer solutions of the Pell equation, then so is (x′′, y′′) given by

x′′ + y′′\sqrt{d} = (x + y\sqrt{d})(x′ + y′\sqrt{d}).

Proof. Taking conjugates, we have

x′′ − y′′\sqrt{d} = (x − y\sqrt{d})(x′ − y′\sqrt{d}).

Multiplying the two equations, we get

x^{′′2} − dy^{′′2} = (x^{2} − dy^{2})(x^{′2} − dy^{′2}) = 1

and our lemma is proved.

We shall now show that all solutions are generated in this way. Definition 1.5.6. For n ≥ 0 we define x_{n}(a) and y_{n}(a) by

x_{n}(a) + y_{n}(a)\sqrt{d} = (a + \sqrt{d})^{n} .

By Lemma 1.5.5, (x_{n}(a), y_{n}(a)) is a solution of Pell’s equation. When a is fixed, we write x_{n} = x_{n}(a) and y_{n} = y_{n}(a). Theorem 1.5.7. All natural number solutions of Pell’s equation are of the form (x_{n}, y_{n}) for some n.

Proof. Otherwise there would be a solution (x, y) with

x_{n} + y_{n}\sqrt{d} < x + y\sqrt{d} < x_{n+1} + y_{n+1}\sqrt{d} .

By the above definition, this becomes

(a + \sqrt{d})^{n} < x + y\sqrt{d} < (a + \sqrt{d})^{n+1}.

Dividing gives

1 < \frac{x + y\sqrt{d}}{x_{n} + y_{n}\sqrt{d}} < a + \sqrt{d}

which simplifies to

1 < (x + y\sqrt{d})(x_{n} − y_{n}\sqrt{d}) < a + \sqrt{d} .

Multiplying the solutions as in Lemma 1.5.5 gives

1 < x′ + y′\sqrt{d} < a + \sqrt{d}.

Taking negative reciprocals, we get

−1 < −x′ + y′\sqrt{d} < −a + \sqrt{d}.

Adding, we get 0 < 2y′\sqrt{d} < 2\sqrt{d}, which implies 0 < y′ < 1, a contradiction.

We now obtain recurrences and explicit formulas for x_{n} and y_{n}. Lemma 1.5.8. We have

x_{n±m} = x_{n}x_{m} ± dy_{n}y_{m},
y_{n±m} = x_{m}y_{n} ± x_{n}y_{m}.

Proof. Note that

x_{n±m} + y_{n±m}\sqrt{d} = (a + \sqrt{d})^{n+m}
= (x_{m} ± y_{m}\sqrt{d})(x_{n} ± y_{n}\sqrt{d})
= (x_{n}x_{m} ± dy_{n}y_{m}) + (x_{n}y_{m} ± x_{m}y_{n})\sqrt{d}.

Remark 1.5.9. In the special case m = 1, the previous lemma says

x_{n±1} = ax_{n} ± dy_{n},
y_{n±1} = ay_{n} ± x_{n}.

Adding these expressions for x_{n±1} and y_{n±1} respectively, we get recurrences

x_{n+1} = 2ax_{n} − x_{n−1},
y_{n+1} = 2ay_{n} − y_{n−1}.

Theorem 1.5.10. We have the following explicit formulas:

x_{n} = ⌈\frac{1}{2}(a + \sqrt{d})^{n}⌉ ,

y_{n} = ⌊\frac{1}{2\sqrt{d}}(a + \sqrt{d})^{n}⌋ .

Proof. To get an explicit formula for x_{n}, we solve the recurrence x_{n+1} = 2ax_{n} − x_{n−1}. Setting x_{n} = z^{n} we get z^{n+1} = 2az^{n} − z^{n−1}. Dividing by z^{n−1} we get the quadratic equation z^{2} = 2az − 1 which has solutions z = a ± \sqrt{d}. Thus x_{n} = A(a + \sqrt{d})^{n} + B(a − \sqrt{d})^{n}. Using our initial conditions x_{0} = 1 = A + B and x_{1} = a = A(a + \sqrt{d}) + B(a − \sqrt{d}), we get A = B = 1/2. Thus x_{n} = (1/2)((a + \sqrt{d})^{n} + (a − \sqrt{d})^{n}) = ⌈(1/2)(a + \sqrt{d})^{n}⌉.

Similarly, to get an explicit formula for y_{n}, we have y_{n} = A(a+\sqrt{d})^{n} +B(a− \sqrt{d})^{n}, but this time our initial conditions are y_{0} = 0 = A + B and y_{1} = 1 = A(a + \sqrt{d}) + B(a − \sqrt{d}). These equations yield A = 1/2\sqrt{d} and B = −1/2\sqrt{d}. Thus y_{n} = (1/2\sqrt{d})((a + \sqrt{d})^{n} + (a − \sqrt{d})^{n}) = ⌊(1/2\sqrt{d})(a + \sqrt{d})^{n}⌋.

1.5.2 Divisibility Properties of y_{n}

We now obtain some divisibility properties of y_{n}.

Theorem 1.5.11. GCD(x_{n}, y_{n}) = 1.

Proof. Let p be a prime dividing x_{n} and y_{n}. Then p divides x_{n}^{2} − dy_{n}^{2} = 1, a contradiction.

Lemma 1.5.12. y_{n} | y_{t} if and only if n | t.

Proof. Assume n | t and let t = nk. We prove y_{n} | y_{nk} by induction on k. For k = 0 we have y_{n} | 0 = y_{0}, and for k = 1 we have y_{n} | y_{n}. Now y_{n(k+1)} = y_{nk+n} = x_{n}y_{nk} + x_{nk}y_{n}, and by induction hypothesis y_{n} | y_{nk}, hence y_{n} | y_{n(k+1)}.

Conversely, assume y_{n} | y_{t}. Let t = qn + r with 0 ≤ r < n. We then have y_{t} = y_{qn+r} = x_{r}y_{qn} + x_{qn}y_{r}. Since y_{n} divides y_{qn}, it follows that y_{n} divides x_{qn}y_{r}. But since GCD(y_{qn}, x_{qn}) = 1, we have GCD(y_{n}, x_{qn}) = 1. Thus y_{n} divides y_{r}, but since r < n we have y_{r} < y_{n}. Hence r = 0, so n | t.

Theorem 1.5.13. y_{n}^{2} | y_{t} if and only if ny_{n} | t.

Proof. Note that

x_{nk} + y_{nk}\sqrt{d} = (a + \sqrt{d})^{nk} = (x_{n} + y_{n}\sqrt{d})^{k} = ∑_{i=0}^{k} \binom{k}{i}x_{n}^{k−i}y_{n}^{i}d^{i/2}.

Comparing coefficients of \sqrt{d}, we see that

y_{nk} = ∑_{\begin{matrix}0≤i≤k \\ i odd \end{matrix}} \binom{k}{i}x_{n}^{k−i}y_{n}^{i}d^{(i−1)/2} ≡ kx_{n}^{k−1}y_{n} mod y_{n}^{3}.

Setting k = y_{n}, we see that y_{n}^{2} | y_{nk}, i.e., y_{n}^{2} | y_{ny_{n}}. It follows by Lemma 1.5.12 that y_{n}^{2} | y_{t} for all t divisible by ny_{n}. Conversely, suppose y_{n}^{2} | y_{t}. By Lemma 1.5.12 again, we have n | t, say t = nk, so y_{n}^{2} | y_{nk}. Moreover, we have already seen that y_{nk} ≡ kx_{n}^{k−1}y_{n} mod y_{n}^{3}. It follows that y_{n}^{2} | kx_{n}^{k−1}y_{n}, hence y_{n} | kx_{n}^{k−1}. Since GCD(x_{n}, y_{n}) = 1, it follows that y_{n} | k, hence ny_{n} | nk = t.

Recall that x_{n+1} = 2ax_{n} − x_{n−1} and y_{n+1} = 2ay_{n} − y_{n−1}. We use these recurrences to establish some easy properties of x_{n} and y_{n}, by induction on n.

Theorem 1.5.14. If a ≡ b mod c, then x_{n}(a) ≡ x_{n}(b), y_{n}(a) ≡ y_{n}(b) mod c.

Proof. For n = 0 we have x_{0}(a) = 1 = x_{0}(b) and y_{0}(a) = 0 = y_{0}(b). For n = 1 we have x_{1}(a) = a ≡ b = x_{1}(b) mod c, and y_{1}(a) = 1 = y_{1}(b). Inductively we have x_{n+1}(a) = 2ax_{n}(a) − x_{n−1}(a) ≡ 2ax_{n}(b) − x_{n−1}(b) ≡ x_{n+1}(b) mod c, and similarly y_{n+1}(a) ≡ y_{n+1}(b) mod c.

Theorem 1.5.15. y_{n} ≡ n mod a − 1.

Proof. For n = 0, 1 we have y_{0} = 0, y_{1} = 1. Inductively we have y_{n+1} = 2ay_{n} − y_{n−1} ≡ 2an − (n − 1) = 2(a − 1)n + n + 1 ≡ n + 1 mod a − 1.

Theorem 1.5.16. If n is even, y_{n} is even. If n is odd, y_{n} is odd.

Proof. The initial values y_{0} = 0 and y_{1} = 1 are known. We have y_{n+1} = 2ay_{n} − y_{n−1} ≡ −y_{n−1} ≡ y_{n−1} mod 2, so our result is obvious by induction.

1.5.3 Congruence Properties of x_{n}

We now prove a theorem telling for which i, j, n are x_{i} ≡ x_{j} mod x_{n}.

Lemma 1.5.17. x_{2n±j} ≡ −x_{j} mod x_{n}.

Proof. By Lemma 1.5.8 we have x_{2n±j} = x_{n+(n±j)} = x_{n}x_{n±j} + dy_{n}y_{n±j} = x_{n}x_{n±j} + dy_{n}(y_{n}x_{j} ± x_{n}y_{j}). Continuing modulo x_{n}, we have x_{2n±j} ≡ dy_{n}^{2}x_{j} = (x_{n}^{2} − 1)x_{j} ≡ −x_{j}.

Lemma 1.5.18. x_{4n±j} ≡ x_{j} mod x_{n}.

Proof. By the previous lemma we have x_{4n±j} = x_{2n+(2n±j)} ≡ −x_{2n±j} ≡ −(−x_{j}) = x_{j} mod x_{n}.

Lemma 1.5.19. For all 0 ≤ i < j ≤ 2n we have x_{i} ≢ x_{j} mod x_{n}. The only exception is when a = 2, n = 1, x_{0} ≡ x_{2} mod x_{1}.

Proof. If x_{n} is odd, put q = (x_{n} − 1)/2. Since 2q < x_{n}, the numbers

−q, −q + 1 …, −1, 0, 1, …, q − 1, q

are all pairwise ≢ mod x_{n}. Recalling x_{n} = ax_{n−1} + dy_{n−1}, we have x_{n} ≥ ax_{n−1} ≥ 2x_{n−1}, hence x_{n−1} ≤ x_{n}/2, hence x_{n−1} ≤ q, since x_{n−1} is an integer. It now follows that

−q ≤ −x_{n−1} < ⋯ < −x_{1} < −x_{0} = −1 < 0 < 1 = x_{0} < x_{1} < ⋯ < x_{n−1} ≤ q are pairwise ≢ mod x_{n}. Moreover, Lemma 1.5.17 tells us that x_{n+1} ≡ −x_{n−1}, …, x_{2n−1} ≡ −x_{1}, x_{2n} ≡ −x_{0}, all mod x_{n}, and trivially x_{n} ≡ 0 mod x_{n}. It is now clear that all of x_{0}, x_{1}, …, x_{n−1}, x_{n}, x_{n+1}, …, x_{2n} are pairwise ≢ mod x_{n}.

If x_{n} is even, put q = x_{n}/2. Since 2q ≤ x_{n}, the numbers

−q + 1, −q + 2, …, −1, 0, 1, …, q − 1, q

are all pairwise ≢ mod x_{n}. As before we have x_{n−1} ≤ q, so our result follows as before, unless x_{n−1} = q = x_{n}/2. In this exceptional situation we have 2x_{n−1} = x_{n} = ax_{n−1} + dy_{n−1}, hence a = 2 and y_{n−1} = 0, hence n = 1, x_{1} = a = 2, x_{2} = 2ax_{1} − x_{0} = 8 − 1 = 7 ≡ 1 = x_{0} mod x_{1}.

Lemma 1.5.20. If x_{i} ≡ x_{j} mod x_{n}, where n ≥ 1, 0 < i ≤ n, and 0 ≤ j < 4n, then either j = i or j = 4n − i.

Proof. Case 1: j ≤ 2n. By Lemma 1.5.19, i = j unless the exceptional case occurs. But this implies {i, j} = {0, 2} and n = 1, contradicting our assumptions.

Case 2: 2n < j < 4n. Set j′ = 4n − j. Then 0 < j′ < 2n. By Lemma 1.5.18, x_{j′} ≡ x_{j} mod x_{n}, hence x_{i} = x_{j′} mod x_{n}. By Lemma 1.5.19, i = j′ unless the exceptional case occurs. This cannot happen, because both i and j′ are > 0.

Theorem 1.5.21. If 0 < i ≤ n and x_{i} ≡ x_{j} mod x_{n}, then i = ±j mod 4n.

Proof. Put j = 4nq + r, where 0 ≤ r < 4n. By Lemma 1.5.18, x_{i} ≡ x_{j} ≡ x_{r} mod x_{n}. By Lemma 1.5.20, i = r or i = 4n − r. Thus j ≡ r ≡ ±i mod 4n.

1.5.4 Diophantine Definability of x_{n} and y_{n}

Theorem 1.5.22. The functions (a, k) ↦ x_{k}(a) and (a, k) ↦ y_{k}(a) are Diophantine.

Proof. We show that x = x_{k}(a) and y = y_{k}(a) if and only if there exist b, u, v, s, t and w_{i}, 1 ≤ i ≤ 6, satisfying the following system of equations:

x^{2} + (a^{2} − 1)y^{2} = 1  (1.1)
u^{2} − (a^{2} − 1)v^{2} = 1  (1.2)
s^{2} − (b^{2} − 1)t^{2} = 1  (1.3)
v = w_{1}y^{2}  (1.4)
b = 1 + 4w_{2}y  (1.5)
b = a + w_{3}u  (1.6)
s = x + w_{4}u  (1.7)
t = k + 4w_{5}y  (1.8)
y = k + w_{6}  (1.9)

Note that (1.4)–(1.9) amount to saying y^{2} divides v, b ≡ 1 mod 4y, b ≡ a mod u, s ≡ x mod u, t ≡ k mod 4y, y ≥ k.

⇒: Assume x = x_{k}(a) and y = y_{k}(a). Set n = 2ky, u = x_{n}(a), v = y_{n}(a). Clearly (1.1) and (1.2) hold. Since y_{k}(a) ≥ k, (1.9) holds. By Theorem 1.5.13, y_{k}^{2} divides y_{2ky_{k}} = y_{n}, i.e., y^{2} divides v, so (1.4) is satisfied. By Theorem 1.5.11 we have GCD(u, v) = 1 hence GCD(u, y) = 1. Because n is even, y_{n}(a) = v is even (Theorem 1.5.16), hence u = x_{n}(a) is odd, hence GCD(u, 4y) = 1. By the Chinese Remainder Theorem, we can find b such that b ≡ 1 mod 4y and b ≡ a mod u, so (1.5) and (1.6) are satisfied. Set s = x_{k}(b) and t = y_{k}(b), so (1.3) is satisfied. Since b ≡ a mod u, we have x_{k}(b) ≡ x_{k}(a) mod u, so (1.7) is satisfied. By Theorem 1.5.15, t = y_{k}(b) ≡ k mod b − 1. Since 4y | b − 1, we have t ≡ k mod 4y, so (1.8) is satisfied. Thus all of (1.1)–(1.9) are satisfied.

⇐: Assume (1.1)–(1.9). We want to prove x = x_{k}(a) and y = y_{k}(a). By (1.1)–(1.3) there exist i, j, n such that x = x_{i}(a), y = y_{i}(a), u = x_{n}(a), v = y_{n}(a), s = x_{j}(b), t = y_{j}(b). It remains only to show that i = k.

By (1.6) we have a ≡ b mod x_{n}(a), hence x_{j}(a) ≡ x_{j}(b) mod x_{n}(a). By (1.7) we have x_{i}(a) ≡ x_{j}(b) mod x_{n}(a). Hence x_{i}(a) ≡ x_{j}(a) mod x_{n}(a). By (1.4) we have y_{i}(a)^{2} | y_{n}(a), hence y_{i}(a) ≤ y_{n}(a), hence i ≤ n. By Theorem 1.5.21 it follows that i = ±j mod 4n. By (1.4) we have y_{i}(a)^{2} | y_{n}(a), hence by Theorem 1.5.13 y_{i}(a) | n. Thus i ≡ ±j mod 4y_{i}(a). By (1.5) we have b ≡ 1 mod 4y_{i}(a), i.e., 4y_{i}(a) | b − 1. By Theorem 1.5.15, y_{j}(b) ≡ j mod b − 1, hence y_{j}(b) ≡ j mod 4y_{i}(a). But by (1.8) we also have y_{j}(b) ≡ k mod 4y_{i}(a). Thus i ≡ ±j ≡ ±k mod 4y_{i}(a). By (1.9) we have k ≤ y_{i}(a), and obviously i ≤ y_{i}(a), hence i = k and we are done.

1.6 Proof of the Main Lemma

In this section we use properties of Pell’s equation to prove the Main Lemma 1.3.7. We begin by proving that the exponential function is Diophantine.

Lemma 1.6.1. For n, k ≥ 1 and a ≥ 2 we have

n^{k} ≡ x_{k}(a) − (a − n)y_{k}(a) mod 2an − n^{2} − 1.

Proof. The proof is by induction on k. For the base cases k = 0 and k = 1, we have x_{0} − (a − n)y_{0} = 1 = n^{0} and x_{1} − (a − n)y_{1} = a − (a − n) = n = n^{1}. Assuming our congruence for k − 1 and for k, we derive it for k + 1 using the recurrences x_{k+1} = 2ax_{k} − x_{k−1} and y_{k+1} = 2ay_{k} − y_{k−1}. Namely,

x_{k+1} − (a − n)y_{k+1} = 2a(x_{k} − (a − n)y_{k}) − (x_{k−1} − (a − n)y_{k−1})
≡ 2an^{k} − n^{k−1} = n^{k−1}(2an − 1) mod 2an − n^{2} − 1
≡ n^{k−1}n^{2} = n^{k+1} mod 2an − n^{2} − 1.

Our congruence is now proved for all k.

Lemma 1.6.2. If n^{k} < a, then n^{k} < 2an − n^{2} − 1.

Proof. Set g(z) = 2az − z^{2} − 1 where z is a real variable. We have g(1) = 2a − 2 ≥ a. Moreover, for 1 ≤ z < a we have g′(z) = 2a − 2z > 0, hence g(z) ≥ a. In particular, for 1 ≤ n ≤ n^{k} < a we have g(n) ≥ a > n^{k}.

Theorem 1.6.3. The function (n, k) ↦ n^{k} is Diophantine.

Proof. Set a = x_{k+1}(n + 1). By Theorem 1.5.22 this is a Diophantine function of n and k. By Theorem 1.5.10 we have n^{k} < a. Hence by Lemma 1.6.2 we have n^{k} < 2an − n^{2} − 1. By Lemma 1.6.1 we have n^{k} ≡ x_{k}(a) − (a − n)y_{k}(a) mod 2an − n^{2} − 1 for any a. But then, for this particular a, it follows that n^{k} = the remainder of x_{k}(a)−(a−n)y_{k}(a) on division by 2an−n^{2}−1. It is now clear that (n, k) ↦ n^{k} is Diophantine, since (a, k) ↦ x_{k}(a), y_{k}(a) are Diophantine.

Having shown that the exponential function is Diophantine, we now show that the other functions mentioned in the Main Lemma are Diophantine.

Theorem 1.6.4. The function (n, k) ↦ \binom{n}{k} is Diophantine.

Proof. Given n and k, choose M > 2^{n}. We have

\frac{(M + 1)^{n}}{M^{k}} = ∑_{i=0}^{n} \binom{n}{i}M^{i−k} = q + ϵ

where q = ∑_{i=k}^{n} \binom{n}{i}M^{i−k} is an integer, and

ϵ = ∑_{i=0}^{k−1} \binom{n}{i}M^{i−k} ≤ \frac{1}{M} ∑_{i=0}^{n} \binom{n}{i} = \frac{1}{M} 2^{n} < 1.

Moreover, q ≡ \binom{n}{k} mod M, and \binom{n}{k} < 2^{n} < M. It is now clear that z = \binom{n}{k} if and only if

∃M ∃q [ M > 2^{n} ∧ q = Quot((M + 1)^{n}, M^{k}) ∧ z = Rem(q, M) ] .

Thus (n, k) ↦ \binom{n}{k} is Diophantine.

Lemma 1.6.5. For any M > (2n)^{n+1} we have

n! = Quot (M^{n}, \binom{M}{n}) = ⌊\frac{M^{n}}{\binom{M}{n}}⌋ .

Proof. We have

\frac{M^{n}}{\binom{M}{n}} = \frac{M^{n}n!}{M(M − 1) ⋯ (M − n + 1)}
= \frac{n!}{(1 − \frac{1}{M}) ⋯ (1 − \frac{n−1}{M})}
< \frac{n!}{(1 − \frac{n}{M})^{n}}
= n! (\frac{1}{1 − α})^{n}

where α = n/M. Moreover

\frac{1}{1 − α} = 1 + \frac{α}{1 − α} < 1 + 2α,

hence

(\frac{1}{1 − α})^{n} < (1 + 2α)^{n}
= 1 + ∑_{i=1}^{n} \binom{n}{i}(2α)^{i}
= 1 + 2α ∑_{i=1}^{n} \binom{n}{i}(2α)^{i−1}
< 1 + 2α ∑_{i=0}^{n} \binom{n}{i}
= 1 + (2α)(2^{n}) = 1 + 2^{n+1}α.

Thus

n! ≤ \frac{M^{n}}{\binom{M}{n}} < n! + 1

provided n! 2^{n+1}α < 1, and this follows from n(n!)2^{n+1} < (2n)^{n+1} < M. Theorem 1.6.6. The function n ↦ n! is Diophantine. Proof. By the previous lemma we have

z = n! ⟺ ∃M [ M > (2n)^{n+1} ∧ z = Quot (M^{n}, \binom{M}{n}) ] .

This is Diophantine in view of Theorems 1.6.3 and 1.6.4. Theorem 1.6.7. The function

(a, b, n) ↦ h(a, b, n) = ∏_{i=0}^{n}(a + bi)

is Diophantine. Proof. Given a, b, n, choose M > (a + bn)^{n+1} ≥ h(a, b, n) such that M is relatively prime to b. Then b is invertible mod M, i.e., ∃c (bc ≡ 1 mod M), hence abc ≡ a mod M. It follows that

h(a, b, n) = ∏_{i=0}^{n}(a + bi)

≡ ∏_{i=0}^{n}(abc + bi) mod M

≡ b^{n+1} ∏_{i=0}^{n}(ac + i) mod M

= b^{n+1}\binom{ac + n}{n + 1}(n + 1)! ,

hence h(a, b, n) = the remainder of b^{n+1}\binom{ac+n}{n+1}(n + 1)! on division by M. It is now clear that z = h(a, b, n) if and only if

∃M ∃c [ M > (a + bn)^{n+1} ∧ bc ≡ 1 mod M ∧ z = Rem (b^{n+1}\binom{ac+n}{n+1}(n + 1)!, M) ]

and this is Diophantine in view of Theorems 1.6.3, 1.6.4, 1.6.6.

This completes the proof of the Main Lemma 1.3.7. Therefore, we have now proved the MDRP Theorem 1.3.2 and with it the unsolvability of Hilbert’s Tenth Problem.

Unsolvability of the Word Problem for Groups

This chapter consists mainly of a proof that the word problem for groups is unsolvable. This result is due to P. Novikov 1955 and Boone 1959. Boone’s proof was simplified by Britton 1963. We follow the exposition of Rotman [12, Chapter 12]. Note also that a more streamlined proof has been given by Aanderaa/Cohen [2].

At the end of the chapter we present some related results, including unsolvability of the triviality problem for groups.

2.1 Finitely Presented Semigroups

We shall first prove that the word problem for semigroups is unsolvable. This result is due to Post 1947 and Markov 1947 and is much easier than unsolvability of the word problem for groups.

Definition 2.1.1. A semigroup is a set S together with an associative binary operation · : S × S → S. We consider only semigroups with an identity element, i.e., 1 ∈ S such that s · 1 = 1 · s = s for all s ∈ S.

Example 2.1.2. Let a_{1}, …, a_{n} be a finite alphabet. Let S_{n} be the set of words on a_{1}, …, a_{n}. A word is a finite sequence of letters of the alphabet, W = a_{i_{1}} ⋯ a_{i_{k}}, where 1 ≤ i_{j} ≤ n for 1 ≤ j ≤ k. Here k is the length of W. If k = 0, W is the empty word. Note that S_{n} is a semigroup under concatenation. For example, If U = abaac, V = baba, then UV = abaacbaba. This semigroup

S_{n} = ⟨a_{1}, …, a_{n}⟩

is called the free semigroup on a_{1}, …, a_{n}.

Definition 2.1.3. Let R be a subset of S_{n} × S_{n}. We define an equivalence relation ≈_{R} on S_{n}. For W, W′ ∈ S_{n}, define W ≈_{R} W′ if and only if there exists a finite sequence of words W = W_{0}, W_{1}, …, W_{t} = W′ such that, for each i < t, W_{i} ∼_{R} W_{i+1}, i.e., W_{i} = UXV and W_{i+1} = UY V for some (X, Y) or (Y, X) ∈ R. For W ∈ S_{n} we write [W]_{R} = {W′ ∈ S_{n} | W ≈_{R} W′} = the equivalence class of W modulo ≈_{R}. We put S = S_{n}/≈_{R} = the set of such equivalence classes. This is a semigroup, with the operation · being given by [U]_{R} · [V]_{R} = [UV]_{R}. The identity element is 1 = [ε]_{R} where ε is the empty word. We frequently write W instead of [W]_{R}. Our semigroup S is written as

S = ⟨a_{1}, … a_{n} | R⟩.

Each (X, Y) ∈ R is viewed as a relation X = Y which holds in S.

Example 2.1.4. Let S be the semigroup ⟨a, b | a^{3} = 1, ab = ba⟩. We refer to S as the semigroup with generators a, b and relations a^{3} = 1, ab = ba. Elements of S are words on the alphabet a, b except we can reduce equivalent words, e.g., aababa = aaabba = aaabab = aaaabb = abb. In fact, each word is equivalent to a unique one of the form a^{i}b^{j}, where 0 ≤ i ≤ 2, j ≥ 0. Thus each element of S has a normal form. The multiplication of normal forms is given by a^{i}b^{j}a^{s}b^{t} = a^{k}b^{j+t}, where k = Rem(i + s, 3).

Definition 2.1.5. A finitely presented semigroup is a semigroup of the form ⟨a_{1}, …, a_{n} | R⟩, where a_{1}, …, a_{n} is a finite set of generators and R is a finite set of relations.

Definition 2.1.6. Let S = ⟨a_{1}, …, a_{n} | R⟩ be a finitely presented semigroup. The word problem for S is the problem, given two words W, W′ ∈ S_{n}, to decide whether W = W′ in S, i.e., whether W ≈_{R} W′.

Example 2.1.7. The word problem for ⟨a, b | a^{3} = 1, ab = ba⟩ is solvable, because a^{i}b^{j} = a^{s}b^{t} in S if and only if i ≡ s mod 3, and j = t. In fact, each word on a, b is equivalent to a unique normal form a^{i}b^{j}, 0 ≤ i ≤ 2, j ≥ 0, and two normal forms are equivalent if and only if they are equal.

Remark 2.1.8. In general, the word problem for a finitely presented semigroup S = ⟨A | R⟩ is a recursively enumerable or Σ_{1}^{0} problem. This is because W = W′ in S if and only if ∃t ∃ finite sequence of words W_{0}, W_{1}, …, W_{t} such that

W ≡ W_{0} ∼_{R} W_{1} ∼_{R} ⋯ ∼_{R} W_{t} ≡ W′ .

Theorem 2.1.9 (Post, Markov). We can construct a finitely presented semigroup S such that the word problem for S is unsolvable.

In order to prove this theorem, we shall encode the Halting Problem into the word problem for a particular finitely presented semigroup.

Recall that a k-place partial function ψ is partial recursive if and only if it is computable by some register machine program P. Please refer to the Math 558 notes [14] for the definition of register machine programs.

Let P be a register machine program. Recall that P(x_{1}, …, x_{k}) is the run of P started with x_{1}, …, x_{k} in registers R_{1}, …, R_{k} and all other registers empty.

Lemma 2.1.10. We can find a program P such that, given x ∈ ℕ, it is undecidable whether P(x) halts.

Proof. By the Enumeration Theorem, let P be a program computing the partial recursive function e ↦ φ_{e}^{(1)}(0): that is, P takes a number e, constructs the program with that Gödel number, and then runs the program with input 0. Thus P(e) halts if and only if e ∈ H, where H is the Halting Set. By Turing’s work, H is undecidable, so the Halting Problem for P is undecidable.

Notation 2.1.11. We write

p_{0}, p_{1}, …, p_{i}, …

for the prime numbers 2, 3, 5, 7, 11, . . .. Thus p_{i} is the ith prime, where we start indexing with 0.

Lemma 2.1.12. Given a k-place partial recursive function ψ(x_{1}, …, x_{k}), we can find a 1-place partial recursive function ψ^{∗}(z) such that

ψ^{∗}(p_{1}^{x_{1}} ⋯ p_{k}^{x_{k}}) ≃ p_{k+1}^{ψ(x_{1},...,x_{k})}

for all x_{1}, …, x_{k}, and ψ^{∗}(z) is computable by a register machine program using only two registers, R_{1} and R_{2}.

Proof. Let P be a register machine program which computes ψ. Let

P_{1}, …, P_{k}, P_{k+1}, …, P_{s}

be the registers used in P. We may safely assume that, whenever P(x_{1}, …, x_{k}) halts, it leaves all registers except possibly P_{k+1} empty. Our new program P^{∗} for ψ^{∗} will be constructed so as to simulate P using only two registers, R_{1} and R_{2}. In the new program, R_{1} is used to hold a number z which encodes the contents of P_{1}, …, P_{s} via prime power coding, i.e.,

z = ∏_{i=1}^{s} p_{i}^{z_{i}}

where z_{i} is the content of P_{i}. Then R_{2} is used for scratch work. Each P_{i}^{+} instruction is replaced by a program for z ↦ z · p_{i}. Each P_{i}^{−} instruction is replaced by a program for

z ↦ \{ \begin{matrix}z/p_{i} if p_{i} divides z, \\ z otherwise. \end{matrix}

We shall see that this simulation can be performed using only R_{1} and R_{2}. It is then clear that ψ^{∗}(p_{1}^{x_{1}} ⋯ p_{k}^{x_{k}}) ≃ p_{k+1}^{ψ(x_{1},...,x_{k})} for all x_{1}, …, x_{k}.

The details of the simulation are as follows.

We replace [figure: P_{i}^{+}] in P by Figure 2.1 in P^{∗}.

[figure: R_{1}^{−}; e; R_{2}^{−}; e; R_{2}^{+}; R_{1}^{+}; ⋮; R_{2}^{+}]

Figure 2.1: Incrementing P_{i}. The number of R_{2}^{+} instructions is p_{i}.

We replace [figure: P_{i}^{−}; e; A; B] in P by Figure 2.2 in P^{∗}.

We replace  [figure: stop] in P by  [figure: R_{1}^{−}; e; stop; R_{2}^{+}] in P^{∗}.

This completes the proof of Lemma 2.1.12.

Theorem 2.1.13. We can find a program P using only two registers, R_{1} and R_{2}, such that, given x ∈ ℕ, it is undecidable whether P(x) halts. Furthermore, when it halts, R_{1} and R_{2} are empty.

Proof. We begin with the program of Lemma 2.1.10. Using Lemma 2.1.12 we

convert it to a program using only R_{1} and R_{2}. We then replace [figure: stop]

by

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

to clear R_{1} and R_{2} before halting.

[figure: R_{1}^{+}; R_{1}^{−}; e; R_{2}^{−}; e; A; R_{1}^{+}; R_{2}^{+}; R_{1}^{−}; e; R_{1}^{+}; R_{2}^{−}; e; R_{1}^{+}; ⋮; ⋮; B; ⋮; R_{1}^{−}; e; R_{1}^{+}; R_{1}^{+}]

Figure 2.2: Decrementing P_{i}. The number of R_{1}^{−} instructions is p_{i}.

We now construct a semigroup S with unsolvable word problem.

Definition 2.1.14. Let P be a program using only two registers R_{1}, R_{2} as in Theorem 2.1.13. Let I_{1}, …, I_{l} be the instructions of P. As usual, I_{1} is the first instruction executed, and I_{0} is the halt instruction. Our semigroup S will have l+3 generators a, b, q_{0}, q_{1}, …, q_{l}. If R_{1} and R_{2} contain x and y respectively, and if I_{m} is about to be executed, then we represent this state as a word ba^{x}q_{m}a^{y}b. Thus a serves as a counting token, and b serves as an end-of-count marker. For each m = 1, …, l, if I_{m} says “increment R_{1} and go to I_{n_{0}},” we represent this as a production q_{m} → aq_{n_{0}} or as a relation q_{m} = aq_{n_{0}}. If I_{m} says “increment R_{2} and go to I_{n_{0}},” we represent this as a production q_{m} → q_{n_{0}}a or as a relation q_{m} = q_{n_{0}}a. If I_{m} says “if R_{1} is empty go to I_{n_{0}} otherwise decrement R_{1} and go to I_{n_{1}},” we represent this as a pair of productions bq_{m} → bq_{n_{0}}, aq_{m} → q_{n_{1}}, or as a pair of relations bq_{m} = bq_{n_{0}}, aq_{m} = q_{n_{1}}. If I_{m} says “if R_{2} is empty go to I_{n_{0}} otherwise decrement R_{2} and go to I_{n_{1}},” we represent this as a pair of productions q_{m}b → q_{n_{0}}b, q_{m}a → q_{n_{1}}, or as a pair of relations q_{m}b = q_{n_{0}}b, q_{m}a = q_{n_{1}}. Thus the total number of productions or relations is l^{+} +2l^{−}, where l = l^{+} +l^{−} and l^{+} is the number of increment instructions and l^{−} is the number of decrement instructions. Let S be the semigroup described by these generators and relations.

Theorem 2.1.15. P(x) halts if and only if ba^{x}q_{1}b = bq_{0}b in S.

Proof. The “if” part is clear. For the “only if” part, assume that ba^{x}q_{1}b = bq_{0}b in S. This implies that there is a sequence of words ba^{x}q_{1}b = W_{0} = ⋯ = W_{n} = bq_{0}b where each W_{i+1} is obtained from W_{i} by a forward or backward production. We claim that the backward productions can be eliminated. In other words, if there are any backward productions, we can replace the sequence W_{0}, …, W_{n} by a shorter sequence. This is actually obvious, because if there is a backward production then there must be one which is immediately followed by a forward production, and these two must be inverses of each other, because P is deterministic. Thus we see that ba^{x}q_{1}b = bq_{0}b via a sequence of forward productions. This implies that P(x) halts. Our claim is proved.

From the previous theorem, it follows that our semigroup S has unsolvable word problem. This proves Theorem 2.1.9.

2.2 The Boone Group

Definition 2.2.1. A group is a semigroup G such that ∀g ∈ G ∃g^{−1} ∈ G such that gg^{−1} = g^{−1}g = 1.

Notation 2.2.2. Let A be an alphabet. We introduce new letters a^{−1}, a ∈ A, and we write A^{−1} = {a^{−1} | a ∈ A}. We also write (a^{−1})^{−1} = a. A word on A ∪ A^{−1} is said to involve a if it contains an occurrence of a or a^{−1}.

Definition 2.2.3. A group presentation is a semigroup presentation

G = ⟨A ∪ A^{−1} | R⟩

where R includes semigroup relations

aa^{−1} = a^{−1}a = 1,

i.e., aa^{−1} = a^{−1}a = ε, for all a ∈ A, where ε is the empty word. We abbreviate this as

G = ⟨A | R⟩.

Note that G is a group, because for any word a_{i_{1}}^{e_{1}} ⋯ a_{i_{k}}^{e_{k}} on A ∪ A^{−1} we have

(a_{i_{1}}^{e_{1}} ⋯ a_{i_{k}}^{e_{k}})^{−1} = a_{i_{k}}^{−e_{k}} ⋯ a_{i_{1}}^{−e_{1}}.

Definition 2.2.4. A finitely presented group is a group with a finite presentation, i.e., G = ⟨A | R⟩ where A and R are finite.

Definition 2.2.5. Let G be a finitely generated group, and let A be a finite generating set. The word problem for G is the problem, given a word W on A ∪ A^{−1}, to decide whether W = 1 in G.

Remark 2.2.6. If G is a finitely generated group, the degree of unsolvability of the word problem of G is independent of finite set of generators chosen. The same holds for semigroups.

We now exhibit a finitely presented group with unsolvable word problem. To do this, we build upon our construction of a finitely presented semigroup with unsolvable word problem. We use some special features of the earlier construction.

Remark 2.2.7. In Section 2.1 we constructed a finitely presented semigroup S = ⟨A ∪ Q | R⟩ with unsolvable word problem, where

A = {a, b} , Q = {q_{0}, …, q_{l}} .

Recall that the relations of S were of the form

R = {X_{i}q_{m_{i}}Y_{i} = U_{i}q_{n_{i}}V_{i} | i ∈ I}

where X_{i}, Y_{i}, U_{i}, V_{i} are words on A. We showed that, given words X, Y on A, it is undecidable whether Xq_{m}Y = bq_{0}b in S.

We now introduce a new generator q = q_{l+1} into Q, and we introduce a new relation bq_{0}b = q into R. With this trivially modified presentation of the semigroup S, we now have Q = {q, q_{0}, …, q_{l}}. Moreover, given words X, Y on A, it is undecidable whether Xq_{m}Y = q in S.

Notation 2.2.8. If X = a_{i_{1}} ⋯ a_{i_{k}} is a word on A, we write

\overline{X} = a_{i_{1}}^{−1} ⋯ a_{i_{k}}^{−1}.

Note that \overline{X} ≠ X^{−1}. If X and Y are words on A, we write (Xq_{m}Y)^{∗} = \overline{X}q_{m}Y.

We now construct a group with unsolvable word problem.

Definition 2.2.9 (the Boone group). Let

S = ⟨A ∪ Q | X_{i}q_{m_{i}}Y_{i} = U_{i}q_{n_{i}}V_{i}, i ∈ I⟩

be a finitely presented semigroup as in Remark 2.2.7 above. Let G be the group with generators

A ∪ Q ∪ {r_{i} | i ∈ I} ∪ {x, t, k}

and relations

xa = ax^{2}
r_{i}a = axr_{i}x
r_{i}^{−1}\overline{X_{i}}q_{m_{i}}Y_{i}r_{i} = \overline{U_{i}}q_{n_{i}}V_{i}
tx = xt, tr_{i} = r_{i}t
kx = xk, kr_{i} = r_{i}k
k(q^{−1}tq) = (q^{−1}tq)k

for all a ∈ A and i ∈ I. Note that G is a finitely presented group. This particular group is due to Boone.

Theorem 2.2.10 (Boone). Let X and Y be words on A. Put

Σ = (Xq_{m}Y)^{∗} = \overline{X}q_{m}Y.

The following are pairwise equivalent.

1. Xq_{m}Y = q in S.

2. Σ = LqR in G, where L, R are some words on x, x^{−1}, r_{i}, r_{i}^{−1}, i ∈ I.

3. k(Σ^{−1}tΣ) = (Σ^{−1}tΣ)k in G. Corollary 2.2.11. The word problem for the Boone group G is unsolvable. Proof. This is immediate from 1 ⇔ 3 in Boone’s Theorem 2.2.10, plus the known undecidability of Xq_{m}Y = q in S. Theorem 2.2.12 (P. Novikov, Boone). The word problem for groups is unsolvable. Proof. This is immediate from Corollary 2.2.11.

Before starting the proof of Boone’s Theorem 2.2.10, we give an example. Example 2.2.13. Consider the register machine program P which empties R_{1} and halts:

[figure: start; R_{1}^{−}; e; stop] .

The Post semigroup relations for P are:

aq_{1} = q_{1},
bq_{1} = bq_{0},
bq_{0}b = q.

The corresponding Boone group relations are:

r_{1}^{−1}a^{−1}q_{1}r_{1} = q_{1},
r_{2}^{−1}b^{−1}q_{1}r_{2} = b^{−1}q_{0},
r_{3}^{−1}b^{−1}q_{0}br_{3} = q.

In addition, the Boone group has a generator x and relations xa = ax^{2}, xb = bx^{2}, r_{i}a = axr_{i}x, r_{i}b = bxr_{i}x, i = 1, 2, 3. This gives a subgroup G_{3} of the Boone group (see also Lemma 2.3.6 below). The full Boone group is obtained by introducing additional generators t, k and their associated relations.

Consider P(1), the run of P starting with 1 in R_{1}, 0 in R_{2}. In the semigroup we have

baq_{1}b = bq_{1}b = bq_{0}b = q.

Hence in the group we have

q = r_{3}^{−1}b^{−1}q_{0}br_{3}
= r_{3}^{−1}r_{2}^{−1}b^{−1}q_{1}r_{2}br_{3}
= r_{3}^{−1}r_{2}^{−1}b^{−1}q_{1}bxr_{2}xr_{3}
= r_{3}^{−1}r_{2}^{−1}b^{−1}r_{1}^{−1}a^{−1}q_{1}r_{1}bxr_{2}xr_{3}
= \underbrace{r_{3}^{−1}r_{2}^{−1}x^{−1}r_{1}^{−1}x^{−1}}_{L} b^{−1}a^{−1}q_{1}b \underbrace{xr_{1}x^{2}r_{2}xr_{3}}_{R} .

Setting Σ = (baq_{1}b)^{∗} = b^{−1}a^{−1}q_{1}b, we have q = LΣR, where L is a word on x^{−1}, r_{i}^{−1}, i ∈ I, and R is a word on x, r_{i}, i ∈ I. This is an instance of statement 2 of Boone’s Theorem.

We now begin the proof of Boone’s Theorem.

Proof of 1 ⇒ 2 and 2 ⇒ 3. Assume Xq_{m}Y = q in S. Say

Xq_{m}Y = W_{0} = ⋯ = W_{n} = q

where for each ν = 1, …, n there exists i ∈ I such that W_{ν−1} and W_{ν} are of the form P X_{i}q_{m_{i}}Y_{i}Q and P U_{i}q_{n_{i}}V_{i}Q, where P, Q are words on A.

Note that for any word P on A, we have r_{i}P = P R and \overline{P} r_{i}^{−1} = L\overline{P}, where R, L are words on x, x^{−1}, r_{i}, r_{i}^{−1}. Hence in G we have

\overline{P} \overline{U_{i}}q_{n_{i}}V_{i}Q = \overline{P} r_{i}^{−1}\overline{X_{i}}q_{m_{i}}Y_{i}r_{i}Q
= L\overline{P} \overline{X_{i}}q_{m_{i}}Y_{i}QR,

hence W_{ν−1}^{∗} = L_{ν}W_{ν}^{∗}R_{ν} for each ν = 1, ⋯, n. Hence W_{0}^{∗} = LW_{n}^{∗}R where

L = L_{1} ⋯ L_{n}, R = R_{n} ⋯ R_{1}

are words on x, x^{−1}, r_{i}, r_{i}^{−1}, i ∈ I. But W_{0}^{∗} = (Xq_{m}Y)^{∗} = Σ, and W_{n}^{∗} = q^{∗} = q. Thus we have Σ = LqR in G. Now, by the relations of G, we have

k(Σ^{−1}tΣ) = kR^{−1}q^{−1}L^{−1}tLqR
= kR^{−1}q^{−1}tqR
= R^{−1}kq^{−1}tqR
= R^{−1}q^{−1}tqkR
= R^{−1}q^{−1}tqRk
= R^{−1}q^{−1}L^{−1}tLqRk
= (Σ^{−1}tΣ)k .

Thus we have proved 1 ⇒ 2 and 2 ⇒ 3 in Boone’s Theorem.

It remains to prove 3 ⇒ 2 and 2 ⇒ 1.

2.3 HNN Extensions and Britton’s Lemma

In order to finish the proof of Boone’s Theorem, we first study HNN extensions.

Remark 2.3.1. Given a group G, and given p ∈ G, the map G → G given by g ↦ p^{−1}gp is an automorphism of G. Such automorphisms are called inner automorphisms. We shall see that all of the relations used to define the Boone group G describe properties of inner automorphisms.

Theorem 2.3.2 (Higman/Neumann/Neumann). Let G be a group. Let H, K be subgroups of G which are isomorphic to each other. Let ϕ : H ≅ K be a particular isomorphism of H onto K. Then there exists a group G^{∗} ⊇ G and a group element p ∈ G^{∗} such that p^{−1}hp = ϕ(h) for all h ∈ H.

Definition 2.3.3 (HNN extensions). Let G = ⟨A | R⟩ be a group presentation. Let ϕ : H ≅ K be an isomorphism of a subgroup of G onto another subgroup of G. Consider the group presentation G^{∗} = ⟨A^{∗} | R^{∗}⟩ where A^{∗} = A ∪ {p}, and R^{∗} = R ∪ {p^{−1}Xp = ϕ(X)}_{X} where X ranges over a set of words on A ∪ A^{−1} which generate H. We sometimes write this as

G^{∗} = ⟨G, p | p^{−1}Xp = ϕ(X)⟩_{X}.

By the HNN Theorem 2.3.2, the identity map a ↦ a, a ∈ A, gives an embedding of G into G^{∗}. Then G^{∗} is called an HNN extension of G, with stable letter p.

An important special case of an HNN extension is when ϕ is the identity map and H = K, as follows.

Definition 2.3.4 (commuting HNN extensions). Let G = ⟨A | R⟩ be a group. Let H be any subgroup of G. Consider G′ = ⟨A′ | R′⟩ where A′ = A∪{p}, and R′ = R ∪ {p^{−1}Xp = X}_{X} where X ranges over a set of generators of H. Then G′ is called a commuting HNN extension of G, with stable letter p. Thus we have

G′ = ⟨G, p | p^{−1}Xp = X⟩_{X}.

Note also that p^{−1}Xp = X can be written as pX = Xp.

Remark 2.3.5. The Boone group is nothing but a finite sequence of HNN extensions. More precisely, each of the letters in our presentation of the Boone group was introduced as a stable letter for an HNN extension. In particular, the letters t and k in Definition 2.2.9 are stable letters for commuting HNN extensions. We spell all this out in the proof of the following lemma.

Lemma 2.3.6. The Boone group G (see Definition 2.2.9) is obtained as an iterated HNN extension.

Proof. We start with the infinite cyclic group G_{0} = ⟨x⟩. Clearly

G_{1} = ⟨x, a, a ∈ A | a^{−1}xa = x^{2}, a ∈ A⟩

is a multiple HNN extension (see Definition 2.6.2 below) of G_{0} with stable letters a, a ∈ A.

Consider the free product

G_{2} = G_{1} ∗ ⟨q, q_{0}, …, q_{l}⟩

where ⟨q, q_{0}, …, q_{l}⟩ is the free group on q, q_{0}, …, q_{l}. We claim that

G_{3} = ⟨G_{2}, r_{i}, i ∈ I | r_{i}^{−1}axr_{i} = ax^{−1}, r_{i}^{−1}\overline{X_{i}}q_{m_{i}}Y_{i}r_{i} = \overline{U_{i}}q_{n_{i}}V_{i}, a ∈ A, i ∈ I⟩

is a multiple HNN extension of G_{2} with stable letters r_{i}, i ∈ I. To see this, consider the subgroups H_{i} and K_{i} of G_{2} generated by \overline{X_{i}}q_{m_{i}}Y_{i}, ax, a ∈ A, and \overline{U_{i}}q_{n_{i}}V_{i}, ax^{−1}, a ∈ A, respectively. It is not hard to see that H_{i} and K_{i} are free on these generators. Hence there are isomorphisms ϕ_{i} : H_{i} ≅ K_{i} given by ϕ_{i}(\overline{X_{i}}q_{m_{i}}Y_{i}) = \overline{U_{i}}q_{n_{i}}V_{i}, ϕ_{i}(ax) = ax^{−1}, a ∈ A. Thus G_{3} is a multiple HNN extension of G_{2} as claimed.

Next we have

G_{4} = ⟨G_{3}, t | tx = xt, tr_{i} = r_{i}t, i ∈ I⟩

which is a commuting HNN extension of G_{3} with stable letter t. Finally, the Boone group is

G = G_{5} = ⟨G_{4}, k | kx = xk, kr_{i} = r_{i}k, k(q^{−1}tq) = (q^{−1}tq)k, i ∈ I⟩

which is a commuting HNN extension of G_{4} with stable letter k.

Our proof of Boone’s Theorem will be based on a detailed understanding of HNN extensions. A key property is given by Britton’s Lemma, below.

Definition 2.3.7. In an HNN extension, a pinch is a word of the form p^{−1}Xp or pXp^{−1} where X is a word on A ∪ A^{−1} lying in H or K respectively. A word containing no pinches is said to be reduced.

Remark 2.3.8. In an HNN extension, any word is equivalent to a reduced word. This is because the relations of G^{∗} allow us to replace pinches by words not involving p or p^{−1}. Namely, if X is a word on A ∪ A^{−1} lying in H, then p^{−1}Xp = ϕ(X) is equivalent to a word on A ∪ A^{−1} lying in K. Likewise, if X is a word on A ∪ A^{−1} lying in K, then pXp^{−1} = ϕ^{−1}(X) is equivalent to a word on A ∪ A^{−1} lying in H.

Lemma 2.3.9 (Britton’s Lemma). Let W be a word involving p or p^{−1}. If W = 1 in G^{∗}, then W contains a pinch.

The proofs of the HNN Theorem 2.3.2 and Britton’s Lemma 2.3.9 are spread out over Sections 2.4, 2.5, 2.6 below.

2.4 Free Products With Amalgamation

In order to prove the HNN Theorem and Britton’s Lemma, we first introduce free products with amalgamation. The proof of the HNN Theorem is at the end of this section.

Definition 2.4.1 (free product). Let G_{1}, G_{2} be groups, which we assume to be disjoint except for the identity element, 1. The free product G_{1} ∗ G_{2} is the group consisting of all formal products g_{1} ⋯ g_{n} where n ≥ 0, g_{i} ≠ 1, and adjacent g_{i} belong to distinct G_{j}. Note that distinct n-tuples g_{1}, …, g_{n} as above give rise to distinct elements of G_{1} ∗ G_{2}.

Remark 2.4.2. Intuitively, the free product G_{1} ∗ G_{2} is the “largest” group generated by G_{1}∪G_{2}. One way to see this is in terms of generators and relations: if G_{1} = ⟨A_{1} | R_{1}⟩ and G_{2} = ⟨A_{1} | R_{2}⟩, then G_{1} ∗ G_{2} = ⟨A_{1} ∪ A_{2} | R_{1} ∪ R_{2}⟩. Another way to see it is in terms of a universal mapping property:

\xymatrix{ & K \\ G_{1} \ar[r] \ar[ur] & G_{1} ∗ G_{2} \ar@{-->}[u] & G_{2} \ar[l] \ar[ul]}

This means that, given maps from G_{1} and G_{2} to K, a unique map from G_{1} ∗ G_{2} to K is determined.

Example 2.4.3. The free group on n generators may be viewed as a free product

F_{n} = ⟨a_{1}, …, a_{n}⟩ = ⟨a_{1}⟩ ∗ ⋯ ∗ ⟨a_{n}⟩

where ⟨a_{1}⟩, …, ⟨a_{n}⟩ are infinite cyclic groups.

Corollary 2.4.4. G_{1} and G_{2} are subgroups of G_{1} ∗ G_{2}. Moreover, in G_{1} ∗ G_{2} we have G_{1} ∩ G_{2} = 1.

Corollary 2.4.5. For all g_{1}, …, g_{n}, n ≥ 1, g_{i} ≠ 1, with adjacent g_{i} from distinct G_{j}, we have g_{1} ⋯ g_{n} ≠ 1 in G_{1} ∗ G_{2}.

Definition 2.4.6 (free product with amalgamation). Let H be a subgroup embedded in both G_{1} and G_{2} via ι_{1} : H ↪ G_{1} and ι_{2} : H ↪ G_{2}. Define G_{1} ∗_{H} G_{2} = G_{1} ∗ G_{2}/N where N is the normal subgroup of G_{1} ∗ G_{2} generated by ι_{1}(h)ι_{2}(h)^{−1}, h ∈ H. The group G_{1} ∗_{H} G_{2} is called a free product with amalgamation. In terms of generators and relations, if G_{1} = ⟨A_{1} | R_{1}⟩, G_{2} = ⟨A_{2} | R_{2}⟩, and A_{1} ∩ A_{2} = ∅, then

G_{1} ∗_{H} G_{2} = ⟨A_{1}, A_{2} | R_{1}, R_{2}, ι_{1}(X) = ι_{2}(X)}_{X}

where X ranges over a set of generators of H.

Remark 2.4.7. There is a universal mapping property given by the following diagram:

\xymatrix{ & K \\ G_{1} \ar[r] \ar[ur] & G_{1} ∗_{H} G_{2} \ar@{-->}[u] & G_{2} \ar[l] \ar[ul] \\  & H \ar[ul] \ar[ur]}

This means that, given maps from G_{1} and G_{2} to K which induce the same map from H to K, a unique map from G_{1} ∗_{H} G_{2} to K is determined.

Remark 2.4.8. To obtain a concrete description of the elements of G_{1} ∗_{H} G_{2}, assume H ⊆ G_{1} and H ⊆ G_{2}. For each g ∈ G_{j} \ H, j = 1, 2 let \overline{g} ∈ G_{j} \ H be a representative of the coset gH. Note that we have uniquely g = \overline{g}h for some h ∈ H. Then G_{1} ∗_{H} G_{2} is concretely the set of formal products \overline{g_{1}} ⋯ \overline{g_{n}}h, n ≥ 0, where adjacent g_{i} come from distinct G_{j} \ H, and h ∈ H.

Corollary 2.4.9. G_{1} and G_{2} are subgroups of G_{1} ∗_{H} G_{2}, and G_{1} ∩ G_{2} = H.

Proof. The first statement is immediate from Remark 2.4.8. Suppose g_{1} ∈ G_{1} \ H, g_{2} ∈ G_{2} \ H. We have g_{1} = \overline{g_{1}}h_{1}, g_{2} = \overline{g_{2}}h_{2}, and \overline{g_{1}} ≠ \overline{g_{2}}, hence g_{1} ≠ g_{2}.

Corollary 2.4.10. Let n ≥ 1 and let g_{1}, …, g_{n} ∈ G_{j}\H where adjacent g_{i} come from distinct G_{j}. Then in G_{1} ∗_{H} G_{2} we have g_{1} ⋯ g_{n} ∉ H, hence g_{1} ⋯ g_{n} ≠ 1.

Proof. For 1 ≤ i ≤ n we have g_{i} ∉ H, hence g_{i} = \overline{g_{i}}h_{i}, h_{i} ∈ H. We then have

g_{1} ⋯ g_{n} = \overline{g_{1}}h_{1}\overline{g_{2}}h_{2} ⋯ \overline{g_{n}}h_{n}
= \overline{g_{1}}\overline{h_{1}\overline{g_{2}}}h′_{2} ⋯ \overline{g_{n}}h_{n}
⋯
= \overline{g_{1}}\overline{g′_{2}} ⋯ \overline{g′_{n}}h′

which is clearly ∉ H.

We now use a free product with amalgamation to prove the HNN Theorem.

Proof of the HNN Theorem 2.3.2. Let ϕ : H ≅ K with H, K ⊆ G. Let M = G ∗ ⟨u⟩ where u is a new letter. Let P be the subgroup of M generated by G ∪ u^{−1}Hu. Note that P = G ∗ u^{−1}Hu within M, because there can be no equation g_{0}(u^{−1}h_{1}u)g_{1}(u^{−1}h_{2}u) ⋯ g_{n−1}(u^{−1}h_{n}u)g_{n} = 1 with g_{i} ∈ G, h_{i} ∈ H, h_{1} ≠ 1, g_{1} ≠ 1, h_{2} ≠ 1, …, g_{n−1} ≠ 1, h_{n} ≠ 1, n ≥ 1.

Similarly, let N = G ∗ ⟨v⟩ where v is a new letter, and let Q = G ∗ v^{−1}Kv be the subgroup of N generated by G ∪ v^{−1}Kv. Clearly P ≅ Q via θ defined by θ(g) = g, θ(u^{−1}hu) = v^{−1}ϕ(h)v for all g ∈ G, h ∈ H.

Consider the free product with amalgamation G′ = M ∗_{θ} N. Note that G ↪ G′ via g ↦ g. For all h ∈ H we have u^{−1}hu = v^{−1}ϕ(h)v, hence p^{−1}hp = ϕ(h) where p = uv^{−1}. This proves the HNN Theorem.

We still need to prove Britton’s Lemma.

2.5 Proof of 3 ⇒ 2

In this section we prove Britton’s Lemma (Lemma 2.3.9) in the special case of commuting HNN extensions (see Definition 2.3.4). We then use this special case to obtain the implication 3 ⇒ 2 in Boone’s Theorem 2.2.10.

Notation 2.5.1. In the proof of Britton’s Lemma and Boone’s Theorem, we shall frequently write W ≡ W′ for words W and W′, meaning that W and W′ are identical as words. This is in contrast to W = W′ which means merely that W and W′ are equal as elements of some group.

Let G = ⟨A | R⟩ be a group. Let H be a subgroup of G generated by words X_{i}, i ∈ I, on A ∪ A^{−1}. Let t be a new letter, and consider the commuting HNN extension

G′ = ⟨A, t | R, t^{−1}X_{i}t = X_{i}, i ∈ I⟩ .

Lemma 2.5.2. G′ ≅ G∗_{H} (H ×⟨t⟩) via the canonical map a ↦ a, t ↦ t, a ∈ A.

Proof. Let H = ⟨x_{i}, i ∈ I | S⟩ be a presentation of H on generators x_{i} corresponding to X_{i}, i ∈ I. Then G ∗_{H} (H × ⟨t⟩) has the presentation

⟨A, x_{i}, i ∈ I, t | R, S, t^{−1}x_{i}t = x_{i}, X_{i} = x_{i}, i ∈ I⟩.

In this presentation, the relations S are superfluous, so we have

⟨A, x_{i}, i ∈ I, t | R, t^{−1}x_{i}t = x_{i}, X_{i} = x_{i}, i ∈ I⟩.

Now the generators x_{i}, i ∈ I are superfluous, so we have simply

⟨A, t | R, t^{−1}X_{i}t = X_{i}, i ∈ I⟩

which is G′.

Lemma 2.5.3. Let W be a word involving t or t^{−1}. If W = 1 in G′, then W contains a pinch, i.e., a subword of the form t^{−1}Xt or tXt^{−1} where X is a word on A ∪ A^{−1} lying in H.

Proof. If W contains a subword of the form t^{−1}t or tt^{−1}, we are done. Hence we may safely assume

W ≡ W_{0}t^{e_{1}}W_{1}t^{e_{2}}W_{2} ⋯ W_{n−1}t^{e_{n}}W_{n} = 1

where n ≥ 1, e_{i} ≠ 0, W_{i} is a word on A∪A^{−1}, and W_{1}, …, W_{n−1} are nonempty.

We proceed by induction on n. If n = 1 we have W ≡ W_{0}t^{e_{1}}W_{1} = 1 in G′, hence t^{e_{1}} = W_{0}^{−1}W_{1}^{−1} in G′. However, by Lemma 2.5.2 G′ ≅ G∗_{H} (H ×⟨t⟩) is a free product with amalgamation, hence by Corollary 2.4.9 t^{e_{1}} ∈ G ∩ (H × ⟨t⟩) = H, which is clearly impossible.

Assume now that n > 1. Apply Corollary 2.4.10 to the factorization

W ≡ W_{0}(t^{e_{1}})W_{1} ⋯ W_{n−1}(t^{e_{n}})W_{n} = 1.

Clearly t^{e_{1}}, …, t^{e_{n}} ∉ H, hence at least one of W_{0}, W_{1}, …, W_{n} lies in H. If W_{0} ∈ H, replace W_{0}(t^{e_{1}}) by (W_{0}t^{e_{1}}) ∈ H × ⟨t⟩ \ H. If W_{n} ∈ H, replace (t^{e_{n}})W_{n} by (t^{e_{n}}W_{n}) ∈ H × ⟨t⟩ \ H. Applying Corollary 2.4.10 to the resulting factorization, we see that at least one of W_{1}, …, W_{n−1} lies in H. Thus

W ≡ ⋯ t^{e_{i}}W_{i}t^{e_{i+1}} ⋯ = 1

where W_{i} ∈ H, 1 ≤ i ≤ n − 1. If e_{i} and e_{i+1} are of opposite sign, then we have our pinch, so we are done. If e_{i} and e_{i+1} are of the same sign, consider the equivalent word

W′ ≡ ⋯ t^{e_{i}+e_{i+1}}W_{i}W_{i+1} ⋯ = 1.

Since W′ contains one less power of t, it follows by induction that W′ contains a pinch. But then W contains a pinch.

We have now proved the special case of Britton’s Lemma for commuting HNN extensions (Lemma 2.5.3). The reader who is impatient to see the proof of the full Britton’s Lemma may skip to the next section. We now use the special case to prove the implication 3 ⇒ 2 in Boone’s Theorem.

Proof of 3 ⇒ 2. Recall from the proof of Lemma 2.3.6 that the Boone group G = G_{5} is a commuting HNN extension of G_{4} with stable letter k, namely

G = ⟨G_{4}, k | kx = xk, kr_{i} = r_{i}k, k(q^{−1}tq) = (q^{−1}tq)k, i ∈ I⟩,

where G_{4} is the subgroup of G generated by the generators other than k. Moreover, G_{4} is a commuting HNN extension of G_{3} with stable letter t, namely

G_{4} = ⟨G_{3}, t | tx = xt, tr_{i} = r_{i}t, i ∈ I⟩,

where G_{3} is the subgroup of G_{4} generated by its generators other than t.

Assume 3, i.e., k(Σ^{−1}tΣ) = (Σ^{−1}tΣ)k. By Britton’s Lemma with stable letter k, Σ^{−1}tΣ belongs to the subgroup generated by x, r_{i}, q^{−1}tq, i ∈ I. Thus there is an equation

W ≡ Σ^{−1}tΣR_{0}(q^{−1}t^{e_{1}}q)R_{1} ⋯ R_{n−1}(q^{−1}t^{e_{n}}q)R_{n} = 1

where the R_{j} are (possibly empty) words on x, x^{−1}, r_{i}, r_{i}^{−1}, i ∈ I, and e_{j} = ±1. Choose this equation so that n is as small as possible. By Britton’s Lemma with stable letter t, W contains a pinch t^{e}Xt^{−e} where e = ±1 and X = R for some word R on x, x^{−1}, r_{i}, r_{i}^{−1}, i ∈ I. There are two cases.

Case 1: t^{e} is the first occurrence of t in W. Thus t^{e}Xt^{−e} ≡ tΣR_{0}q^{−1}t^{e_{1}}. Hence e = 1, e_{1} = −1, and X ≡ ΣR_{0}q^{−1}. Since X = R, we have Σ = RqR_{0}^{−1}, which gives us 2 in Boone’s Theorem.

Case 2: t^{e}Xt^{−e} ≡ t^{e_{j}}qR_{j}q^{−1}t^{e_{j+1}} for some j, 1 ≤ j ≤ n − 1. Hence e_{j} = e, e_{j+1} = −e and X ≡ qR_{j}q^{−1}. We then have

q^{−1}t^{e_{j}}qR_{j}q^{−1}t^{e_{j+1}}q = q^{−1}t^{e_{j}}Ct^{e_{j+1}}q
= q^{−1}t^{e_{j}}Rt^{e_{j+1}}q
= q^{−1}Rq
= q^{−1}Xq
= q^{−1}qR_{j}q^{−1}q = R_{j}

so in W we may replace R_{j−1}q^{−1}t^{e_{j}}qR_{j}q^{−1}t^{e_{j+1}}qR_{j+1} by R_{j−1}R_{j}R_{j+1} contradicting minimality of n. This completes the proof of 3 ⇒ 2.

2.6 Proof of Britton’s Lemma

Having proved a special case of Britton’s Lemma, we now use it to prove the full lemma.

Lemma 2.6.1 (Britton’s Lemma). Let

G^{∗} = ⟨G, p | p^{−1}Xp = ϕ(X)⟩_{X}

be an HNN extension of G with stable letter p (see Definition 2.3.3). If W is a word involving p or p^{−1}, and if W = 1 in G^{∗}, then W contains a pinch.

Proof. If W has a subword of the form p^{−1}p or pp^{−1}, we are done. Assume this is not the case, i.e.,

W ≡ W_{0}p^{e_{1}}W_{1} ⋯ W_{n−1}p^{e_{n}}W_{n} = 1

where n ≥ 1, e_{1}, …, e_{n} ≠ 0, W_{0}, …, W_{n} are words on A∪A^{−1}, and W_{1}, …, W_{n−1} are nonempty.

Introduce a new letter t, and form

G^{∗′} = ⟨A, p, t | R, p^{−1}Xp = ϕ(X), t^{−1}Xt = X⟩_{X}

which is a commuting HNN extension of G^{∗} with stable letter t. In G^{∗′} we have (tp)^{−1}X(tp) = p^{−1}t^{−1}Xtp = p^{−1}Xp = ϕ(X), so there is a homomorphism ψ : G^{∗} → G^{∗′} given by a ↦ a, p ↦ tp, a ∈ A. Thus in G^{∗′} we have

W′ = W_{0}(tp)^{e_{1}}W_{1} ⋯ W_{n−1}(tp)^{e_{n}}W_{n} = ψ(W) = 1.

Applying Lemma 2.5.3 to W′, we see that W′ contains a “special pinch,” i.e., a subword of the form t^{−1}Y t or tY t^{−1} where Y is a word on A ∪ A^{−1} ∪ {p} lying in H.

If our special pinch is t^{−1}Y t, then we have e_{i} < 0, e_{i+1} > 0, and Y ≡ W_{i} for some i, 1 ≤ i ≤ n − 1. Since Y lies in H, W_{i} lies in H. Going back to G^{∗}, we see that W has a subword p^{−1}W_{i}p and this is a pinch.

If our special pinch is tY t^{−1}, then we have e_{i} > 0, e_{i+1} < 0, and Y ≡ pW_{i}p^{−1} for some i, 1 ≤ i ≤ n − 1. Since Y lies in H, W_{i} = p^{−1}Y p lies in K. Going back to G^{∗}, we see that W has a subword pW_{i}p^{−1} and this is a pinch.

This completes the proof of Britton’s Lemma.

We shall also need the following generalization.

Definition 2.6.2 (multiple HNN extension). Let G = ⟨A | R⟩ be a group presentation. Assume that we have isomorphisms ϕ_{i} : H_{i} ≅ K_{i}, i ∈ I, where H_{i} and K_{i} are subgroups of G. Consider the group presentation

G^{∗} = ⟨A, p_{i}, i ∈ I | R, p_{i}^{−1}X_{i}p_{i} = ϕ_{i}(X_{i})⟩

where X_{i}, ϕ_{i}(X_{i}) range over generators of H_{i}, K_{i} respectively. We call this a multiple HNN extension with stable letters p_{i}, i ∈ I.

Lemma 2.6.3 (multiple Britton Lemma). Let G^{∗} be a multiple HNN extension of G as above. If W = 1 in G^{∗} and W involves at least one stable letter, then W contains a pinch, i.e., a subword p_{i}^{−1}Xp_{i} or p_{i}Xp_{i}^{−1} where X is a word on A ∪ A^{−1} lying in H_{i} or K_{i} respectively.

Proof. Let p_{1}, …, p_{n} be the stable letters occurring in W. We proceed by induction on n. We may assume that G = G_{0} ⊆ G_{1} ⊆ ⋯ ⊆ G_{n} = G^{∗} where, for each i = 0, …, n − 1, G_{i+1} = ⟨G_{i}, p_{i} | …⟩ is an HNN extension of G_{i} with stable letter p_{i}. By Britton’s Lemma with stable letter p_{n}, W contains a subword p_{n}^{−1}Xp_{n} or p_{n}Xp_{n}^{−1} where X is a word on A, A^{−1}, p_{1}, p_{1}^{−1}, …, p_{n−1}, p_{n−1}^{−1} and X lies in H_{n} or K_{n} respectively. If X does not involve p_{1}, …, p_{n−1}, then we have our pinch. Otherwise, let Z be a word on A ∪ A^{−1} such that X = Z in G_{n−1}. Then XZ^{−1} = 1 in G_{n−1}, so by inductive hypothesis XZ^{−1} contains a pinch. But Z^{−1} is a word on A ∪ A^{−1} only, so X contains a pinch.

2.7 Proof of 2 ⇒ 1

We now complete the proof of Boone’s Theorem 2.2.10.

Proof of 2 ⇒ 1. Assume 2, i.e.,

L\overline{X}q_{m}Y R = q ,

where X and Y are words on A, and L and R are words on x, x^{−1}, r_{i}, r_{i}^{−1}, i ∈ I. Note that our equation takes place in G_{3}, the subgroup of the Boone group generated by A, q, q_{0}, …, q_{l}, x, r_{i}, i ∈ I. Recall also from the proof of Lemma 2.3.6 that G_{3} is a multiple HNN extension of G_{2} with stable letters r_{i}, i ∈ I. Here G_{2} is the subgroup generated by A, q, q_{0}, …, q_{l}, x.

We may safely assume that L, R are freely reduced, i.e., they do not contain subwords of the form x^{−1}x, xx^{−1}, r_{i}^{−1}r_{i}, r_{i}r_{i}^{−1}, i ∈ I. Using this assumption, we have:

Lemma 2.7.1. L and R are {r_{i} | i ∈ I}-reduced.

Proof. Otherwise, L or R contains a pinch of the form r_{i}^{−1}x^{e}r_{i} or r_{i}x^{e}r_{i}^{−1} where e ≠ 0. Thus, it suffices to show that x^{e}, e ≠ 0, cannot belong to the subgroup H_{i} generated by \overline{X_{i}}q_{m_{i}}Y_{i}, ax, a ∈ A, or to the subgroup K_{i} generated by \overline{U_{i}}q_{n_{i}}V_{i}, ax^{−1}, a ∈ A.

In the first case, suppose

W ≡ W_{0}(\overline{X_{i}}q_{m_{i}}Y_{i})^{e_{1}}W_{1} ⋯ W_{n−1}(\overline{X_{i}}q_{m_{i}}Y_{i})^{e_{n−1}}W_{n} = x^{e}

where e_{j} = ±1 and each W_{j} is a (possibly empty) word on ax, (ax)^{−1}, a ∈ A. This takes place in the free product G_{2} = G_{1} ∗ ⟨q, q_{0}, …, q_{l}⟩ where

G_{1} = ⟨x, a, a ∈ A | a^{−1}xa = x^{2}, a ∈ A⟩

(see the proof of Lemma 2.3.6). Therefore, by Corollary 2.4.5, W cannot involve q_{m_{i}}. Hence n = 0 and W ≡ W_{0}. Thus we have

x^{−e}W_{0} ≡ x^{−e}(a_{1}x)^{f_{1}} ⋯ (a_{k}x)^{f_{k}} = 1

where a_{j} ∈ A and f_{j} = ±1. By the multiple Britton Lemma 2.6.3 with stable letters a, a ∈ A, we see that x^{−e}W_{0} contains a pinch of the form a^{−1}x^{n}a or ax^{2n}a^{−1} for some a ∈ A. By inspection of x^{−e}W_{0}, both forms are impossible. Hence W_{0} is empty, hence x^{e} = 1, hence e = 0, a contradiction.

The second case is similar. This proves the lemma.

We continue with the proof of 2 ⇒ 1. We are assuming L\overline{X}q_{m}Y R = q in the Boone group, and we wish to obtain Xq_{m}Y = q in the Post semigroup.

Let N be the number of occurences of r_{i}, r_{i}^{−1}, i ∈ I in L and R. We proceed by induction on N. If N = 0, we have L = x^{s}, R = x^{t}, and our assumption becomes

x^{s}\overline{X}q_{m}Y x^{t} = q.

Since no r_{i} appears, this holds in the free product G_{1} ∗⟨q, q_{0}, …, q_{l}⟩, and clearly x^{s}\overline{X} and Y x^{t} belong to G_{1}. By Corollary 2.4.5, it follows that q_{m} = q and x^{s}\overline{X} = Y x^{t} = 1. Hence s = t = 0 and X and Y are empty, so our conclusion Xq_{m}Y = q in S trivially holds.

Assume now that N > 0. Hence, by the multiple Britton Lemma 2.6.3 with stable letters r_{i}, i ∈ I, there is a pinch in L\overline{X}q_{m}Y R. By Lemma 2.7.1, L and R are {r_{i} | i ∈ I}-reduced, i.e., they individually do not contain a pinch. Hence there must be a pinch which spans L and R. It follows that

L\overline{X}q_{m}Y R ≡ L′r_{i}^{e}x^{s}\overline{X}q_{m}Y x^{t}r_{i}^{−e}R′

where e = ±1, L ≡ L′r_{i}^{e}x^{s}, R ≡ x^{t}r_{i}^{−e}R′, and r_{i}^{e}x^{s}\overline{X}q_{m}Y x^{t}r_{i}^{−e} is a pinch.

If e = −1, then x^{s}\overline{X}q_{m}Y x^{t} lies in the subgroup H_{i} generated by \overline{X_{i}}q_{m_{i}}Y_{i}, ax, a ∈ A. If e = 1, then x^{s}\overline{X}q_{m}Y x^{t} lies in the subgroup K_{i} generated by \overline{U_{i}}q_{n_{i}}V_{i}, ax^{−1}, a ∈ A. Since we are in the free product G_{1} ∗ ⟨q, q_{0}, …, q_{l}⟩, it is clear that m = m_{i}, hence q_{m} = q_{m_{i}}. We consider only the case e = −1, the other case being similar.

Since x^{s}\overline{X}q_{m}Y x^{t} lies in H_{i}, there exists an equation

W ≡ x^{s}\overline{X}q_{m}Y x^{t}W_{0}(\overline{X_{i}}q_{m}Y_{i})^{e_{1}}W_{1} ⋯ W_{n−1}(\overline{X_{i}}q_{m}Y_{i})^{e_{n}}W_{n} = 1

where e_{j} = ±1 and W_{j} is a possibly empty, freely reduced word on ax, (ax)^{−1}, a ∈ A. Choose this equation so that n is as small as possible. Since our equation W = 1 holds in the free product G_{1} ∗ ⟨q_{m}⟩, it follows that 1 + e_{1} + ⋯ + e_{n} = 0 and, by Corollary 2.4.5, each of the words between two consecutive occurrences of q_{m} or q_{m}^{−1} are = 1 in G_{1}. In particular, if e_{j} = 1 and e_{j+1} = −1, then Y_{i}W_{j}Y_{i}^{−1} = 1, and if e_{j} = −1 and e_{j+1} = 1, then \overline{X_{i}} ^{−1}W_{j}\overline{X_{i}} = 1. Either way, W_{j} = 1, hence (\overline{X_{i}}q_{m}Y_{i})^{e_{j}}W_{j}(\overline{X_{i}}q_{m}Y_{i})^{e_{j+1}} = 1 contradicting minimality of n. Therefore, we must have e_{1} = ⋯ = e_{n}. Since 1 + e_{1} + ⋯ + e_{n} = 0, it follows that n = 1 and e_{1} = −1. We now have

W ≡ x^{s}\overline{X}q_{m}Y x^{t}W_{0}(\overline{X_{i}}q_{m}Y_{i})^{−1}W_{1}
≡ x^{s}\overline{X}q_{m}Y x^{t}W_{0}Y_{i}^{−1}q_{m}^{−1}\overline{X_{i}} ^{−1}W_{1} = 1

in the free product G_{1} ∗⟨q_{m}⟩. It follows by Corollary 2.4.5 that Y x^{t}W_{0}Y_{i}^{−1} = 1, hence x^{s}\overline{X} \overline{X_{i}} ^{−1}W_{1} = 1.

Lemma 2.7.2. Y_{i} is an initial segment of Y, and X_{i} is a final segment of X.

Proof. We first show that Y_{i} is an initial segment of Y. Let Y′ ≡ Y_{i}^{−1}Y after cancelling subwords of the form a^{−1}a for all a ∈ A. It suffices to show that the first letter of Y′ is positive (i.e., an element of A, not of A^{−1}). If not, let b^{−1} ∈ A^{−1} be the first letter of Y′, and consider x^{t}W_{0}Y′ = x^{t}W_{0}Y_{i}^{−1}Y = 1. Applying the multiple Britton Lemma with stable letters a, a ∈ A, we see that x^{t}W_{0}Y′ contains a pinch a^{e}Za^{−e}, where e = ±1 and Z lies in ⟨x⟩. Since W_{0} is a freely reduced word on ax, (ax)^{−1}, a ∈ A, our pinch is not contained in x^{t}W_{0}. Hence a^{−e} must be the first letter of Y′. Our pinch is then a^{e}Za^{−e} ≡ bxb^{−1}, hence x belongs to the subgroup of ⟨x⟩ generated by x^{2}, a contradiction.

We have now proved that Y_{i} is an initial segment of Y. The proof that X_{i} is a final segment of X is similar.

By the previous lemma, let Y = Y_{i}Y′ and X = X′X_{i}, where X′ and Y′ are words on A. We then have

W_{0}Y′x^{t} = W_{0}Y Y_{i}^{−1}x^{t} = 1 , x^{s}\overline{X′}W_{1} = x^{s}\overline{X} \overline{X_{i}} ^{−1}W_{1} = 1.

Consider the automorphism ψ of G_{1} given by ψ(a) = a for a ∈ A, and ψ(x) = x^{−1}. In particular, for all a ∈ A we have ψ(ax) = ax^{−1} = r_{i}^{−1}axr_{i}. Since W_{0} and W_{1} are words on ax, (ax)^{−1}, a ∈ A, we have

ψ(W_{0}) = r_{i}^{−1}W_{0}r_{i} , ψ(W_{1}) = r_{i}^{−1}W_{1}r_{i}.

Moreover,

ψ(W_{0}Y′x^{t}) = ψ(W_{0})Y′x^{−t} = 1 , ψ(x^{s}\overline{X′}W_{1}) = x^{−s}\overline{X′}ψ(W_{1}) = 1.

We now have:

q = L\overline{X}q_{m}Y R
= L′r_{i}^{−1}x^{s}\overline{X}q_{m_{i}}Y x^{t}r_{i}R′
= L′r_{i}^{−1}x^{s}\overline{X′} \overline{X_{i}}q_{m_{i}}Y_{i}Y′x^{t}r_{i}R′
= L′r_{i}^{−1}W_{1}^{−1}\overline{X_{i}}q_{m_{i}}Y_{i}W_{0}^{−1}r_{i}R′
= L′ψ(W_{1})^{−1}r_{i}^{−1}\overline{X_{i}}q_{m_{i}}Y_{i}r_{i}ψ(W_{0})^{−1}R′
= L′ψ(W_{1})^{−1}\overline{U_{i}}q_{n_{i}}V_{i}ψ(W_{0})^{−1}R′
= L′x^{−s}\overline{X′} \overline{U_{i}}q_{n_{i}}V_{i}Y′x^{−t}R′.

Note that L′x^{−s} and x^{−t}R′ are words on x, x^{−1}, r_{i}, r_{i}^{−1}, i ∈ I with N − 2 occurrences of r_{i}, r_{i}^{−1}, i ∈ I. Hence, by induction hypothesis, X′U_{i}q_{n_{i}}V_{i}Y′ = q in the semigroup S. Thus Xq_{m}Y = X′X_{i}q_{m_{i}}Y_{i}Y′ = X′U_{i}q_{n_{i}}V_{i}Y′ = q in S, and we have proved 1.

This completes our proof of Boone’s Theorem 2.2.10. Thus we have proved that the word problem for groups is unsolvable.

2.8 Some Refinements

In this section we state without proof some refinements of Theorem 2.2.12 concerning unsolvability of the word problem for groups.

The following result is due to Higman. For a proof, see Aanderaa/Cohen [2] or Rotman [12, Chapter 12] or Shoenfield [13, Appendix].

Theorem 2.8.1 (Higman’s Theorem). Let G = ⟨A | R⟩ be a recursively presented group, i.e., A and R are recursive. Then G is recursively embeddable in a finitely presented group.

This following result is due to C. Miller [8, Corollary 3.9]. The proof uses Higman’s Theorem.

Theorem 2.8.2 (C. Miller). We can construct a finitely presented group G such that G and all nontrivial quotient groups of G have unsolvable word problem.

In another direction, let G = ⟨A | R⟩ be a finitely presented group, and consider the following sets of words on A ∪ A^{−1}.

1. S_{1} = {W | W = 1 in G}.

2. S_{2} = {W | W ≠ 1 in some finite homomorphic image of G}.

Remark 2.8.3. It is easy to see that S_{1} and S_{2} are disjoint and recursively enumerable. Therefore, if S_{1} and S_{2} are complementary (i.e., if G is residually finite), then S_{1} and S_{2} are recursive. To say that S_{1} is recursive means exactly that the word problem for G is solvable.

The following result is due to Slobodskoi [17]. See also Kharlampovich [9].

Theorem 2.8.4 (Slobodskoi). We can construct a finitely presented group G such that both S_{1} and S_{2} are nonrecursive.

The following stronger result has been announced by Aanderaa [1].

Theorem 2.8.5 (Aanderaa). We can construct a finitely presented group G such that S_{1} and S_{2} are recursively inseparable.

2.9 Unsolvability of the Triviality Problem

In this section we consider group-theoretic problems of another kind, concerning not just a single group, but rather a family of groups.

Definition 2.9.1 (triviality problem). The triviality problem for groups is as follows.

Given a finitely presented group G = ⟨A | R⟩, to decide whether G is the trivial group, i.e., G = 1.

Note that this is a Σ_{1}^{0} problem, because A is finite, and G = 1 ⟺ ∀a ∈ A ∃n ∃ finite sequence of words such that a ≡ W_{0} ∼_{R} W_{1} ∼_{R} ⋯ ∼_{R} W_{n} ≡ 1.

We shall show that the triviality problem for groups is unsolvable. This and similar results (see Corollary 2.9.10 below) are due to Adian 1955 and Rabin 1958. It turns out that these results follow fairly easily from the unsolvability of the word problem for groups.

Let G be a fixed, finitely presented group. We reduce the word problem for G to the triviality problem for finite presented groups. The reduction is given by the following definition and lemma.

Definition 2.9.2. Let G = ⟨A | R⟩ be a fixed, finitely presented group. Given a word W on A ∪ A^{−1}, let G′_{W} = ⟨A′ | R′⟩, where A′ = A ∪ {x, y, z}, and R′ consists of R plus the relations

(1)  x^{−1}(W^{−1}y^{−1}W y)x =  z^{−1}yz
(2)  x^{−2}(yxy)x^{2}  =  z^{−2}yz^{2}
(3)  x^{−3}yx^{3}  = z^{−3}(yzy)z^{3}
(4)  x^{−3−i}(ya_{i}y)x^{3+i} = z^{−3−i}yz^{3+i},  1 ≤ i ≤ n,

where A = {a_{1}, …, a_{n}}. Note that G′_{W} is a finitely presented group.

Lemma 2.9.3.

1. If W ≠ 1 in G, then G embeds into G′_{W}.

2. If W = 1 in G, then G′_{W} is trivial.

Proof. Assume first that W ≠ 1 in G. Within the free product G ∗ ⟨x, y⟩, consider the subgroup H generated by y plus the left hand sides of equations (1)–(4). It is straightforward to check that H is free on these generators (use Corollary 2.4.5). Similarly, in the free group ⟨y, z⟩, consider the subgroup K generated by y plus the right hand sides of (1)–(4). Again, K is free on these generators. Thus, there is an obvious isomorphism θ : H ≅ K, and we have

G′_{W} ≅ (G ∗ ⟨x, y⟩) ∗_{θ} ⟨y, z⟩,

i.e., G′_{W} is the free product of G ∗ ⟨x, y⟩ and ⟨y, z⟩ with H and K amalgamated via θ. It follows that G ↪ G ∗ ⟨x, y⟩ ↪ G′_{W}.

Now assume W = 1 in G. Then W^{−1}y^{−1}W y = 1 in G′_{W}, hence by (1) y = 1. Hence by (2) x = 1, by (3) z = 1, and by (4) a_{i} = 1, 1 ≤ i ≤ n. We conclude that G′_{W} = 1.

Theorem 2.9.4 (unsolvability of the triviality problem). The triviality problem for finitely presented groups is unsolvable.

Proof. Let G be a finitely presented group such that word problem for G is unsolvable. Then W = 1 in G if and only if G′_{W} is trivial. Thus the word problem for G reduces to the triviality problem for finitely presented groups. Hence, the latter problem is unsolvable.

Using Theorem 2.9.4, S. Novikov has obtained the following undecidability result in geometry. We state this result without proof.

Theorem 2.9.5 (S. Novikov). Fix n ≥ 5. If M is a finitely presented, compact, connected, n-dimensional manifold without boundary, then it is undecidable whether M is diffeomorphic to the n-sphere, S^{n}. Instead of diffeomorphic, we can say homeomorphic.

Remark 2.9.6. To each finitely presented, connected manifold M is associated a finitely presented group π_{1}(M), the fundamental group of M, consisting of the homotopy classes of closed paths in M. It is well known that the fundamental group of the n-sphere, S^{n}, is trivial. Conversely, there is a theorem of Smale saying that, under certain circumstances, if the fundamental group of an ndimensional manifold M is trivial, then M ≅ S^{n}. Smale’s result is used in the proof of S. Novikov’s result. For an exposition of the proof of S. Novikov’s result, see Nabutovsky [10, Appendix]. Nabutovsky has applied S. Novikov’s result to draw some purely geometrical consequences.

One easily generalizes Theorem 2.9.4 as follows.

Definition 2.9.7. Let P be a property of groups which is invariant under isomorphism. We call P a Markov property if there exist finitely presented groups G_{1}, G_{2} such that (1) G_{1} has property P, (2) for any group H ⊇ G_{2}, H does not have property P.

Examples 2.9.8. Let P = triviality, finiteness, Abelianness, solvability, nilpotence, etc. Each of these properties is a Markov property.

Theorem 2.9.9 (Adian, Rabin). Let P be a Markov property. Given a finitely presented group H, it is undecidable whether H has property P.

Proof. Fix a finitely presented group K with unsolvable word problem. Given a word W in K, form the finitely presented group

H_{W} = G_{1} × (K × G_{2})′_{W} .

If W = 1 in K, then H_{W} = G_{1} has property P. If W ≠ 1 in K, then G_{2} ↪ K×G_{2} ↪ (K×G_{2})′_{W} ↪ H_{W}, so H_{W} does not have property P. Thus, the word problem for K is reducible to the problem of deciding whether a given finitely presented group has property P. Hence, the latter problem is unsolvable.

Corollary 2.9.10. Given a finite presented group H, it is undecidable whether H is trivial, finite, Abelian, solvable, nilpotent, etc.

Recursively Enumerable Sets and Degrees

In this chapter we study the lattice of recursively enumerable sets of natural numbers, under inclusion. We also study the partial ordering of degrees of unsolvability of recursively enumerable sets of natural numbers, under Turing reducibility. A standard reference for these subjects is Soare [18]. A useful supplementary reference is Rogers [11].

3.1 The Lattice of R.E. Sets

The purpose of this section is to introduce the lattice of recursively enumerable sets. We begin by reviewing some basic properties of Σ_{1}^{0} relations on ℕ, the set of natural numbers.

Definition 3.1.1. Recall that R ⊆ ℕ^{k} is recursive if the characteristic function χ_{R} : ℕ^{k} → ℕ, defined by χ_{R}(x_{1}, …, x_{k}) = 1 if R(x_{1}, …, x_{k}) holds, 0 otherwise, is recursive.

Definition 3.1.2. Recall that S ⊆ ℕ^{k} is Σ_{1}^{0} if

S = {⟨x_{1}, …, x_{k}⟩ ∈ ℕ^{k} | ∃y R(x_{1}, …, x_{k}, y)}

where R ⊆ ℕ^{k+1} is recursive.

Remark 3.1.3. In our definition of S being Σ_{1}^{0}, instead of saying that R is recursive, we could say that R is primitive recursive. Also, by Theorem 1.2.7, this is equivalent to S being Σ_{1}, i.e., we can say that R is Δ_{0}. Moreover, by Matiyasevich’s Theorem 1.3.2, this is equivalent to S being Diophantine. However, we shall not make use of these results.

Proposition 3.1.4. S is recursive ⟺ S is Δ_{1}^{0}, i.e., S and ¬ S are Σ_{1}^{0}.

Proof. The ⟹ direction is trivial. For the ⟸ direction, assume that S is Δ_{1}^{0}, say

S(x_{1}, …, x_{k}) ≡ ∃y R_{1}(x_{1}, …, x_{k}, y), ¬ S(x_{1}, …, x_{k}) ≡ ∃y R_{2}(x_{1}, …, x_{k}, y).

Let f(x_{1}, …, x_{k}) = the least y such that R_{1}(x_{1}, …, x_{k}, y) ∨ R_{2}(x_{1}, …, x_{k}, y). Then f is a recursive function, and S(x_{1}, …, x_{k}) ≡ R_{1}(x_{1}, …, x_{k}, f(x_{1}, …, x_{k})), hence S is recursive.

Proposition 3.1.5. If S_{1}, S_{2} ⊆ ℕ^{k} are Σ_{1}^{0}, then so are S_{1} ∪ S_{2} and S_{1} ∩ S_{2}.

Proof. Let S_{i}(x_{1}, …, x_{k}) ≡ ∃y R_{i}(x_{1}, …, x_{k}, y), i = 1, 2, where R_{1}, R_{2} are recursive. We have

(S_{1} ∪ S_{2})(x_{1}, …, x_{k}) ≡ ∃y (R_{1}(x_{1}, …, x_{k}, y) ∨ R_{2}(x_{1}, …, x_{k}, y))

and

(S_{1} ∩ S_{2})(x_{1}, …, x_{k}) ≡ ∃y (R_{1}(x_{1}, …, x_{k}, (y)_{1}) ∧ R_{2}(x_{1}, …, x_{k}, (y)_{2}))

so S_{1} ∪ S_{2} and S_{1} ∩ S_{2} are Σ_{1}^{0}.

The next proposition is known as the Σ_{1}^{0} Uniformization Principle.

Proposition 3.1.6. Let S ⊆ ℕ^{k+1} be Σ_{1}^{0}. Then there is a partial recursive function ψ : ℕ^{k} ⟶^{P} ℕ such that

1. ψ(x_{1}, …, x_{k}) ↓ ⟺ ∃y S(x_{1}, …, x_{k}, y),

2. ψ(x_{1}, …, x_{k}) ↓ ⟹ S(x_{1}, …, x_{k}, ψ(x_{1}, …, x_{k})).

Proof. Let S(x_{1}, …, x_{k}, y) ≡ ∃z R(x_{1}, …, x_{k}, y, z) where R is recursive. Put θ(x_{1}, …, x_{k}) ≃ the least w such that R(x_{1}, …, x_{k}, (w)_{0}, (w)_{1}). Note that θ is a partial recursive function. Put ψ(x_{1}, …, x_{k}) ≃ (θ(x_{1}, …, x_{k}))_{0}.

Proposition 3.1.7. ψ : ℕ^{k} ⟶^{P} ℕ is partial recursive ⟺ graph(ψ) is Σ_{1}^{0}.

Proof. ⟸: If the graph of ψ is Σ_{1}^{0}, let S = graph(ψ), and apply the previous lemma to conclude that ψ is partial recursive.

⟹: If ψ is partial recursive, let P be a program which computes ψ. Then ψ(x_{1}, …, x_{k}) ≃ φ_{e}^{(k)}(x_{1}, …, x_{k}) where e = #(P). Thus ψ(x_{1}, …, x_{k}) ≃ y if and only if

∃n ((State(e, x_{1}, …, x_{k}, n))_{0} = 0 ∧ (State(e, x_{1}, …, x_{k}, n))_{k+1} = y)

where the State function is primitive recursive. (See the Math 558 notes [14].) Thus graph(ψ) is Σ_{1}^{0}.

Proposition 3.1.8. S ⊆ ℕ^{k} is Σ_{1}^{0} if and only if S = domain(ψ) for some partial recursive function ψ : ℕ^{k} ⟶^{P} ℕ.

Proof. If S is Σ_{1}^{0}, say S(x_{1}, …, x_{k}) ≡ ∃y R(x_{1}, …, x_{k}, y) where R is recursive, then we may take ψ(x_{1}, …, x_{k}) ≃ the least y such that R(x_{1}, …, x_{k}, y), and clearly this is partial recursive. Conversely, if ψ is partial recursive, say ψ = φ_{e}^{(k)}, then the domain of ψ is {⟨x_{1}, …, x_{k}⟩ ∈ ℕ^{k} | ∃n (State(e, x_{1}, …, x_{k}, n))_{0} = 0} which is clearly Σ_{1}^{0}.

The next proposition is known as the Σ_{1}^{0} Reduction Principle.

Proposition 3.1.9. If S_{1}, S_{2} ⊆ ℕ^{k} are Σ_{1}^{0}, then we can find Σ_{1}^{0} sets S′_{1}, S′_{2} ⊆ ℕ^{k} such that S′_{1} ⊆ S_{1}, S′_{2} ⊆ S_{2}, S′_{1} ∪ S′_{2} = S_{1} ∪ S_{2}, and S′_{1} ∩ S′_{2} = ∅.

Proof. Since S_{1} and S_{2} are Σ_{1}^{0}, we can express them as

S_{1}(x_{1}, ⋯, x_{k}) ≡ ∃y R_{1}(x_{1}, …, x_{k}, y), S_{2}(x_{1}, …, x_{k}) ≡ ∃y R_{2}(x_{1}, ⋯, x_{k}, z)

where R_{1}, R_{2} are recursive. Define S′_{1} and S′_{2} by

S′_{1}(x_{1}, …, x_{k}) ≡ ∃y [ R_{1}(x_{1}, …, x_{k}, y) ∧ ¬ ∃z < y R_{2}(x_{1}, …, x_{k}, z) ] ,
S′_{2}(x_{1}, …, x_{k}) ≡ ∃y [ R_{2}(x_{1}, ⋯, x_{k}, z) ∧ ¬ ∃z ≤ y R_{1}(x_{1}, …, x_{k}, z) ] .

Clearly this works. Note the similarity to the proof of Rosser’s Theorem.

Corollary 3.1.10. If P_{1}, P_{2} ⊆ ℕ^{k} are Π_{1}^{0}, and if P_{1} ∩ P_{2} = ∅, then there is a recursive R ⊆ ℕ^{k} such that P_{1} ⊆ R and P_{2} ∩ R = ∅.

Proof. Let S_{1} = ℕ^{k} \ P_{1}, S_{2} = ℕ^{k} \ P_{2}, and apply the Reduction Principle 3.1.9. Then S′_{1} ∪ S′_{2} = S_{1} ∪ S_{2} = ℕ^{k}, S′_{1} ∩ S′_{2} = ∅, hence by Proposition 3.1.4 S′_{1}, S′_{2} are recursive. Set R = S′_{2}.

Remark 3.1.11. The previous corollary is known as the Π_{1}^{0} Separation Principle. On the other hand, there is no Σ_{1}^{0} Separation Principle, as shown by the next proposition.

Definition 3.1.12. S_{1}, S_{2} ⊆ ℕ^{k} are said to be recursively inseparable if there is no recursive R ⊆ ℕ^{k} such that S_{1} ⊆ R and R ∩ S_{2} = ∅.

Proposition 3.1.13. We can find Σ_{1}^{0} sets B_{1}, B_{2} ⊆ ℕ such that B_{1} ∩ B_{2} = ∅ and B_{1}, B_{2} are recursively inseparable.

Proof. Put B_{i} = {e | φ_{e}^{(1)}(e) ≃ i} for i = 1, 2. Clearly B_{1} ∩ B_{2} = ∅ and B_{1}, B_{2} are Σ_{1}^{0}. If B_{1}, B_{2} were recursively separable, let f : ℕ → {1, 2} be recursive such that f(e) = 2 for all e ∈ B_{1}, and f(e) = 1 for all e ∈ B_{2}. Since f is recursive, f = φ_{e}^{(1)} for some e. If f(e) = 1, then φ_{e}^{(1)}(e) = 1, which implies e ∈ B_{1}, which implies f(e) = 2, a contradiction. The contradiction is similar if we assume f(e) = 2. Thus B_{1}, B_{2} are recursively inseperable.

We now introduce the lattice of recursively enumerable sets.

Definition 3.1.14 (recursively enumerable sets). Let A be a subset of ℕ. We say that A is recursively enumerable, abbreviated r.e., if it is either empty or the range of a recursive function f : ℕ → ℕ.

Theorem 3.1.15. A is recursively enumerable ⟺ A is Σ_{1}^{0}. Moreover, if A is recursively enumerable and infinite, then A is the range of a one-to-one recursive function.

Proof. Let A = range(f) where f : ℕ → ℕ is recursive. Then x ∈ A ⟺ ∃w f(w) = x and this is Σ_{1}^{0}. Now assume that A is infinite and Σ_{1}^{0}, say A = {x | ∃y R(x, y)} where R recursive. Put

B = {2^{x}3^{y} | R(x, y) ∧ ¬ ∃z < y R(x, z)}.

Then B is infinite and recursive. Define π_{B} : ℕ → ℕ by π_{B}(n) = the nth smallest element of B. This is known as the principal function of B. Clearly π_{B} is recursive, since we can obtain it by recursion as π_{B}(0) = least element of B, π_{B}(n + 1) = least w ∈ B such that w > π_{B}(n). Now, let f(n) = (π_{B}(n))_{0}. Clearly f is one-to-one and recursive, and range(f) = A.

The previous theorem says that r.e. sets are the same thing as Σ_{1}^{0} sets. Thus we have the following properties of r.e. sets.

Theorem 3.1.16.

1. Let A_{1}, A_{2} ⊆ ℕ be recursively enumerable. Then we can find recursively enumerable sets A′_{1} ⊆ A_{1}, A′_{2} ⊆ A_{2} such that A′_{1} ∪ A′_{2} = A_{1} ∪ A_{2} and A′_{1} ∩ A′_{2} = ∅.

2. We can find recursively enumerable sets B_{1}, B_{2} ⊆ ℕ such that B_{1} ∩B_{2} = ∅ and B_{1}, B_{2} are recursively inseparable.

Proof. Part 1 is a special case of the Reduction Principle 3.1.9. Part 2 is a restatement of Proposition 3.1.13.

An algebraic context for results of this kind is lattice theory.

Definition 3.1.17 (lattices). A lattice is a partially ordered set L = (L, ≤) in which any two elements have a least upper bound and a greatest lower bound.

Examples 3.1.18. We consider two familiar examples of lattices.

1. Consider the set of positive integers partially ordered by divisibility, i.e., a ≤ b ⟺ a divides b. This is a lattice. The l.u.b. and g.l.b. operations are just LCM and GCD.

2. Let X be a set. The powerset P (X) = {Y | Y ⊆ X} is a lattice under inclusion, i.e., Y ≤ Z ⟺ Y ⊆ Z. The l.u.b. and g.l.b. operations are given by ∪ and ∩.

Definition 3.1.19 (the lattice of r.e. sets). We write

E = {A ⊆ ℕ | A is recursively enumerable}.

By Proposition 3.1.5, E is a lattice under inclusion. The l.u.b. and g.l.b. operations are given by ∪ and ∩. We refer to E as the lattice of r.e. sets.

Definition 3.1.20 (lattice terminology). In an abstract lattice-theoretic context, the lattice operations l.u.b. and g.l.b. may be denoted ∨ and ∧ respectively. If L is any lattice, we say that L is distributive if the laws a ∧ (b ∨ c) = (a∧b)∨(a∧c) and a∨(b∧c) = (a∨b)∧(a∨c) hold. All of the lattices considered in this chapter are distributive.

If a lattice L has a bottom element and a top element, they are denoted 0 and 1 respectively. For example, P (X) and E are lattices with 0 and 1. The lattice of positive integers under divisibility has 0 but no 1.

Let L be a distributive lattice with 0 and 1. An element a ∈ L is said to be complemented within L if there exists b ∈ L (necessarily unique) such that a ∧ b = 0 and a ∨ b = 1. The whole lattice L is said to be complemented if every element of L is complemented within L. For example, the lattice P (X) is complemented. A Boolean algebra is defined to be a complemented distributive lattice. Thus P (X) is a Boolean algebra, but E is not.

Remark 3.1.21. Let A ∈ E be an r.e. set. By Proposition 3.1.4, A is complemented within E if and only if A is recursive. Since nonrecursive r.e. sets exist, it follows that the lattice E is noncomplemented. Theorem 3.1.16 above expresses further lattice-theoretic properties of E.

Remark 3.1.22. Later in this chapter (Sections 3.6 and 3.7), we shall prove the following two theorems of Friedberg, which express yet more lattice-theoretic properties of E. This is the beginning of a large subject.

1. If A ⊆ ℕ is r.e. and not recursive, then we can find nonrecursive r.e. sets B_{1}, B_{2} such that A = B_{1} ∪ B_{2} and B_{1} ∩ B_{2} = ∅. (Furthermore, we can demand that B_{1}, B_{2} are recursively inseparable. According to Rogers [11, Exercise 12.21], this refinement is due to K. Ohashi.)

2. We can find a nonrecursive r.e. set A ⊆ ℕ such for any r.e. set B ⊇ A, either B\A is finite or ℕ\B is finite. Such an r.e. set A is called a maximal r.e. set.

3.2 Many-One Completeness

A useful way to compare the recursion-theoretic complexity of subsets of ℕ, whether recursively enumerable or not, is via many-one reducibility.

Definition 3.2.1 (many-one reducibility). Let A, B ⊆ ℕ. We say that A is many-one reducible to B, abbreviated A ≤_{m} B, if there exists a recursive function f : ℕ → ℕ such that ∀x (x ∈ A ⟺ f(x) ∈ B).

Definition 3.2.2 (m-completeness). An r.e. set C is said to be many-one complete if, for all r.e. sets A, A ≤_{m} C. We sometimes write m-complete as an abbreviation for many-one complete.

Example 3.2.3. The most straightforward example is as follows. Let

C = { 2^{e}3^{x} | φ_{e}^{(1)}(x) ↓ } .

Clearly C is Σ_{1}^{0}, hence r.e. We claim that C is many-one complete. To see this, let A be an r.e. set. By Proposition 3.1.8, let ψ(x) be a partial recursive function such that A = domain(ψ). Let e be an index of ψ, i.e., the Gödel number of a program which computes ψ. (Using a notation to be introduced later, we can write A = W_{e}, i.e., e is an index of A.) For all x ∈ ℕ we have ψ(x) ≃ φ_{e}^{(1)}(x), hence x ∈ A ⟺ ψ(x) ↓ ⟺ φ_{e}^{(1)}(x) ↓ ⟺ 2^{e}3^{x} ∈ C. Thus A ≤_{m} C via the primitive recursive function f(x) = 2^{e}3^{x}. We have now shown that C is m-complete.

In addition, we have the following examples.

Examples 3.2.4. Recall from Math 558 [14] the sets

H = {e ∈ ℕ | φ_{e}^{(1)}(0) ↓} = the halting set

and

K = {e ∈ ℕ | φ_{e}^{(1)}(e) ↓ } = the diagonal halting set .

Clearly H and K are Σ_{1}^{0}, hence r.e.

Proposition 3.2.5. H and K are many-one complete.

Proof. Recall the Parametrization Theorem, which reads as follows. Given a partial recursive function θ(x, y), we can find a primitive recursive function f(x) such that φ_{f(x)}^{(1)}(y) ≃ θ(x, y) for all x, y. (For a proof of the Paramatrization Theorem, see the Math 558 notes [14].) Given an r.e. set A, consider the partial recursive function θ(x, y) ≃ 1 if x ∈ A, undefined otherwise. Apply the Parametrization Theorem to get a primitive recursive function f(x) such that, for any y, φ_{f(x)}^{(1)}(y) ↓ ⟺ x ∈ A. Setting y = 0, we see that x ∈ A ⟺ f(x) ∈ H. Setting y = f(x), we see that x ∈ A ⟺ f(x) ∈ K. Thus A ≤_{m} H and A ≤_{m} K via f.

Examples 3.2.6. In Chapters 1 and 2 we considered several mathematical problems including Hilbert’s Tenth Problem, the Word Problem for groups, and the Triviality Problem for groups. We pointed out that these each of these problems is Σ_{1}^{0}, i.e., recursively enumerable, and we proved that each of them is unsolvable, i.e., nonrecursive. More precisely, we showed how to many-one reduce the halting set H (or any other r.e. set) to each of them, via explicitly specified, primitive recursive functions. In particular, each of these problems is not only unsolvable but also many-one complete.

In a similar vein, one can show that many other well known unsolvable problems such as the Validity Problem for the predicate calculus, the Decision Problem for Z_{1} (= first-order arithmetic), etc., are r.e. and many-one complete. It follows that each of these problems is many-one reducible to any of the others. In this sense, all of these problems are equivalent, i.e., they are all equally unsolvable.

Remark 3.2.7. Later in this chapter (see Sections 3.10–3.16), we shall study the general concept of degrees of unsolvability, due to Turing. From this point of view, the upshot of our examples above is that a great many unsolvable problems including the Halting Problem, Hilbert’s Tenth Problem, the Word Problem for groups, the Validity Problem for predicate calculus, etc., are all of the same degree of unsolvability.

3.3 Creative Sets

In this section we define an interesting class of r.e. sets, the creative sets. We then prove a theorem due to Myhill 1955, which says that an r.e. set is creative if and only if it is many-one complete.

Notation 3.3.1. Let

W_{e} = domain(φ_{e}^{(1)}) = {x ∈ ℕ | φ_{e}^{(1)}(x) ↓ } .

By Proposition 3.1.8, the sequence W_{e}, e = 0, 1, 2, … is an enumeration of all the r.e. sets. We refer to this as the standard enumeration of the r.e. sets. Given an r.e. set A, an index or r.e. index of A is any e ∈ ℕ such that A = W_{e}. Clearly any r.e. set has infinitely many indices.

Definition 3.3.2 (creative sets). An r.e. set C is said to be creative if there exists a partial recursive function ψ(e) such that for all e, if W_{e} ∩ C = ∅, then ψ(e) ↓ and ψ(e) ∉ W_{e} ∪ C. We call ψ a creative function for C.

Proposition 3.3.3. If C is creative, then C is not recursive.

Proof. If C were recursive, then ℕ \ C would be recursively enumerable, say ℕ\C = W_{e}. Then W_{e} ∩C = ∅, hence ψ(x) ↓ and ψ(e) ∉ W_{e} ∪C, a contradiction since W_{e} ∪ C = ℕ.

Remark 3.3.4. We have just proved that creative sets are nonrecursive. In addition, we can say that a creative set C is “effectively nonrecursive.” By this we mean that C is r.e. and nonrecursive and furthermore, the nonrecursiveness holds because of a computable function ψ(e) which effectively provides a witness for the fact that W_{e} is not the complement of C, for all r.e. sets W_{e}.

Example 3.3.5. The diagonal halting set K of Example 3.2.4 is creative. Namely, a creative function for K is the identity function, ψ(e) = e for all e. To see this, note that by definition K = {e | e ∈ W_{e}}. Hence, for all e, if W_{e} ∩ K = ∅, then e ∉ W_{e} and e ∉ K.

Exercise 3.3.6. Show that the r.e. sets C and H of Examples 3.2.3 and 3.2.4 are creative.

Exercise 3.3.7. Consider the set of Gödel numbers of sentences which are provable in the theory Z_{1}, first-order arithmetic, a.k.a., Peano Arithmetic. Show that this set is creative. Instead of Z_{1}, we could use any recursively axiomatizable theory to which Rosser’s Theorem applies.

Theorem 3.3.8. Let A and B be r.e. sets. If A is creative and A ≤_{m} B, then B is creative.

Proof. Assume that A is creative via ψ, and assume that A ≤_{m} B via f. By the Parametrization Theorem, let h(x) be a primitive recursive function such that φ_{h(x)}^{(1)}(y) ≃ φ_{x}^{(1)}(f(y)) for all x, y. It follows that W_{h(e)} = f^{−1}(W_{e}) for all e. Now, if W_{e} ∩ B = ∅, then W_{h(e)} ∩ A = ∅, hence ψ(h(e)) ↓ and ψ(e) ∉ W_{h(e)} ∪ A, hence f(ψ(h(e))) ∉ W_{e} ∪ B. Thus, a creative function for B is given by e ↦ f(ψ(h(e))).

Corollary 3.3.9. Let C be an r.e. set. If C is m-complete, then C is creative.

Proof. We have already seen that creative r.e. sets exist. For example, we have seen that K is creative. If C is m-complete, then K ≤_{m} C, hence by the previous theorem C is creative.

Our next goal is to prove the converse: if C is creative, then C is m-complete.

Lemma 3.3.10. If C is creative, then we can find a total recursive function p(e) which is a creative function for C.

Proof. Let ψ(e) be a creative function for A which is partial recursive. Consider the Σ_{1}^{0} predicate

S(e, x) ≡ ψ(e) ≃ x ∨ W_{e} ∩ C ≠ ∅ .

Clearly ∀e ∃x S(e, x). By Σ_{1}^{0} uniformization (Proposition 3.1.6), we can find a total recursive function p(e) such that ∀e S(e, p(e)) holds. Then p(e) is a total creative function for C.

In order to prove that creative sets are m-complete, we need a mysterious and powerful theorem known as the Recursion Theorem.

Theorem 3.3.11 (Recursion Theorem). Let θ(w, x_{1}, …, x_{k}) be a partial recursive function. Then we can find e such that

φ_{e}^{(k)}(x_{1}, …, x_{k}) ≃ θ(e, x_{1}, …, x_{k})

for all x_{1}, …, x_{k}.

Example 3.3.12. We can find an e such that φ_{e}^{(1)}(x) = e + x for all x. In particular, φ_{e}^{(1)}(0) = e, i.e., e is the Gödel number of a program which outputs e. Thus, there is a program which outputs its own Gödel number.

Actually, we need an even more powerful result, namely a uniform version of the Recursion Theorem. Here “uniform” means “parametrized.”

Theorem 3.3.13 (Uniform Recursion Theorem). Let θ(w, y, x_{1}, …, x_{k}) be a partial recursive function. Then we can find a primitive recursive function h(y) such that

φ_{h(y)}^{(k)}(x_{1}, …, x_{k}) ≃ θ(h(y), y, x_{1}, …, x_{k})

for all y, x_{1}, …, x_{k}.

Example 3.3.14. We can find a primitive recursive function h(y) such that φ_{h(y)}^{(1)}(x) ≃ h(y) + y + x for all y, x.

Remark 3.3.15. The Recursion Theorem follows easily from the Uniform Recursion Theorem, by treating the parameter y as a dummy variable.

Proof of the Uniform Recursion Theorem. We are given a partial recursive function θ(w, y, x_{1}, …, x_{k}). Use the Parametrization Theorem to find a primitive recursive function f(w, y) such that

φ_{f(w,y)}^{(k)}(x_{1}, …, x_{k}) ≃ θ(w, y, x_{1}, …, x_{k})

for all y, x_{1}, …, x_{k}. In the same way, find a primitive recursive function d(z) such that

φ_{d(z)}^{(k)}(x_{1}, …, x_{k}) ≃ φ_{φ_{z}^{(1)}(z)}^{(k)}(x_{1}, …, x_{k})

for all z, x_{1}, …, x_{k}. Here the expression on the right hand side is assumed to be undefined, if φ_{z}^{(1)}(z) is undefined. Finally, let g(y) be a primitive recursive function such that

φ_{g(y)}^{(1)}(z) ≃ f(d(z), y)

for all y, z. We then have

φ_{d(g(y))}^{(k)}(x_{1}, …, x_{k}) ≃ φ_{φ_{g(y)}^{(1)}(g(y))}^{(k)}(x_{1}, …, x_{k})

≃ φ_{f(d(g(y)),y)}^{(k)}(x_{1}, …, x_{k})
≃ θ(d(g(y)), y, x_{1}, …, x_{k})

so we may set h(y) = d(g(y)).

We are now ready to prove the following result of Myhill.

Theorem 3.3.16. An r.e. set is creative if and only if it is many-one complete.

Proof. We have already seen in Corollary 3.3.9 that m-complete sets are creative. It remains to prove that creative sets are m-complete. Let C be a creative set. By Lemma 3.3.10, let p(e) be a total recursive function which is a creative function for C. Let A be any r.e. set. We wish to show that A ≤_{m} C. Consider the partial recursive function θ(w, y, x) ≃ 1 if p(w) = x and y ∈ A, undefined otherwise. By the Uniform Recursion Theorem, let h(y) be a primitive recursive function such that φ_{h(y)}^{(1)}(x) ≃ θ(h(y), y, x) for all y, x. Thus W_{h(y)} = {p(h(y))} if y ∈ A, and W_{h(y)} = ∅ if y ∉ A. For y ∈ A we have p(h(y)) ∈ W_{h(y)}, hence W_{h(y)} ∩ C ≠ ∅, hence p(h(y)) ∈ C. For y ∉ A we have W_{h(y)} = ∅, hence p(h(y)) ∉ C. Thus A ≤_{m} C via the total recursive function f(y) = p(h(y)). This shows that C is m-complete.

Myhill 1955 has also obtained the following result, which says that any two creative sets (or equivalently, m-complete sets) are recursively isomorphic to each other.

Theorem 3.3.17. If C_{1} and C_{2} are creative sets, then there is a total recursive function π : ℕ ⟶^{1-1 onto} ℕ such that π(C_{1}) = C_{2}. Note that π is a recursive permutation of the natural numbers.

Proof. We omit the proof.

Remark 3.3.18. Using Myhill’s results, we see that all of the specific, nonrecursive r.e. sets mentioned in Section 3.2 are not only of the same degree of unsolvability, but also recursively isomorphic to each other.

3.4 Simple Sets

All of the nonrecursive r.e. sets which we have encountered so far are many-one complete, and hence creative. Nevertheless, there exist nonrecursive r.e. sets which are not creative. We now show one method for constructing such sets.

Definition 3.4.1 (simple sets). An r.e. set A is said to be simple if its complement

\overline{A} = ¬ A = ℕ \ A

is infinite yet does not include an infinite r.e. set.

Clearly a simple set cannot be recursive, because by Proposition 3.1.4 the complement of a recursive set is r.e.

Theorem 3.4.2. There exists a simple set.

Proof. Consider the Σ_{1}^{0} relation

S(e, x) ≡ x > 2e and x ∈ W_{e} .

By Σ_{1}^{0} uniformization, let ψ(e) be a partial recursive function which uniformizes S(e, x). In particular, if W_{e} is infinite, then ψ(e) ↓ and ψ(e) > 2e. Let A be the range of ψ. Thus A is an r.e. set which has nonempty intersection with every infinite r.e. set. To prove that A is simple, it remains to show that \overline{A} is infinite. This is so because |A ∩ {0, 1, …, 2x}| ≤ x for all x, which follows from the fact that each element of A ∩ {0, 1, …, 2x} is of the form ψ(e) for some e < x.

Theorem 3.4.3. A creative set is not simple.

Proof. Let C be a creative set, and let p be a creative function for C. By the Parametrization Theorem, let f(e, x) be a primitive recursive function such that that W_{f(e,x)} = W_{e} ∪ {x} for all e, x. Let e_{0} be an index of the empty set, i.e., W_{e_{0}} = ∅. Extend this to a recursive sequence of indices e_{0}, e_{1}, e_{2}, … by putting e_{n+1} = f(e_{n}, p(e_{n})) for all n. By induction we have

W_{e_{n}} = {p(e_{0}), p(e_{1}), …, p(e_{n−1})}

and W_{e_{n}} ∩ C = ∅, hence p(e_{n}) ↓ and p(e_{n}) ∉ W_{e_{n}} ∪ C, for all n. Thus

{p(e_{0}), p(e_{1}), …, p(e_{n}), …}

is an infinite r.e. subset of \overline{C}. Hence C is not simple. Corollary 3.4.4. There exist nonrecursive r.e. sets which are not creative, hence not many-one complete.

3.5 Lattice-Theoretic Properties

Definition 3.5.1. A property of r.e. sets is said to be lattice-theoretic if it is definable over the E, the lattice of r.e. sets. Remark 3.5.2. In the previous definition, we could have used any of the languages {∩, ∪, ⊆} or {∩, ∪} or {⊆} or {∩} or {∪} for E, without changing which properties of r.e. sets are definable over E. This is because

A ⊆ B ≡ A ∪ B = B ≡ A ∩ B = A

and

A ∪ B = the unique C such that ∀D (C ⊆ D ⇔ (A ⊆ D ∧ B ⊆ D))

and

A ∩ B = the unique C such that ∀D (C ⊇ D ⇔ (A ⊇ D ∧ B ⊇ D)) .

Moreover, the top and bottom elements ℕ and ∅ and the equality relation = for the lattice E are definable in any of these languages. Examples 3.5.3. The following properties of r.e. sets are lattice-theoretic.

1. A is recursive ⟺ A is complemented, i.e., ∃B (A ∪ B = ℕ and A ∩ B = ∅).

2. A is finite ⟺ ∀B (A ∩ B is recursive).

3. A is simple ⟺ A nonrecursive and ∀B (B infinite ⇒ A ∩ B ≠ ∅).

4. A and B are recursively inseparable ⟺

¬ ∃R (R recursive ∧ A ⊆ R ∧ R ∩ B = ∅).

Here of course the quantifiers range over E.

The following surprising theorem is due to Harrington. Theorem 3.5.4. An r.e. set A is creative if and only if (∃C ⊇ A) (∀B ⊆ C) (∃R) [ R recursive, R ∩ C nonrecursive, R ∩ A = R ∩ B] where the quantifiers range over E. Thus, the property of being creative is lattice-theoretic. Proof. We omit the proof.

3.6 The Friedberg Splitting Theorem

The purpose of this section is to prove the following splitting theorem, due essentially to Friedberg but with a small refinement due to Ohashi. We have previously stated this result as the first item in Remark 3.1.22.

Theorem 3.6.1. Let A be a nonrecursive r.e. set. Then we can find r.e. sets B_{1}, B_{2} such that A = B_{1} ∪ B_{2}, B_{1} ∩ B_{2} = ∅, and B_{1}, B_{2} are recursively inseparable. It follows that B_{1} and B_{2} are nonrecursive.

Remark 3.6.2. Note that this statement is lattice-theoretic.

In order to present the proof, we first introduce some notation.

Notation 3.6.3 (finite approximation). Recall from the Math 558 notes [14] that φ_{e}^{(1)}(x) ≃ y if and only if

∃n [ (State(e, x, n))_{0} = 0 ∧ (State(e, x, n))_{2} = y] .

We now introduce the finite approximation φ_{e,s}^{(1)}(x) ≃ y if and only if

e, x, y < s ∧ ∃n < s [ (State(e, x, n))_{0} = 0 ∧ (State(e, x, n))_{2} = y] .

Note that the 4-place relation φ_{e,s}^{(1)}(x) ≃ y and the 3-place relation φ_{e,s}^{(1)}(x) ↓ are primitive recursive, and φ_{e,s}^{(1)}(x) ≃ y implies e, x, y < s. Moreover,

φ_{e}^{(1)}(x) ≃ y ⟺ ∃s φ_{e,s}^{(1)}(x) ≃ y ,

and

φ_{e}^{(1)}(x) ↓ ⟺ ∃s φ_{e,s}^{(1)}(x) ↓ .

In addition, there is a monotonicity property:

(φ_{e,s}^{(1)}(x) ≃ y ∧ s < t) ⇒ φ_{e,t}^{(1)}(x) ≃ y .

Recall also Notation 3.3.1, according to which W_{e} = domain(φ_{e}^{(1)}). We now introduce the finite approximation

W_{e,s} = domain(φ_{e,s}^{(1)}) .

Again, the 3-place relation x ∈ W_{e,s} is primitive recursive, and x ∈ W_{e,s} implies x, e < s. Moreover W_{e} = ⋃_{s} W_{e,s}. Also, s < t implies W_{e,s} ⊆ W_{e,t}.

We now prove the Friedberg Splitting Theorem.

Proof of Theorem 3.6.1. We are given a nonrecursive r.e. set, A. Let f : ℕ → ℕ be a one-to-one, total recursive function such that A = range(f). Define A^{s} = {f(0), …, f(s − 1)}. We have A = ⋃_{s} A^{s}. Also s < t implies A^{s} ⊂ A^{t}.

For each e ∈ ℕ and i = 1, 2 there will be a requirement

R_{2e+i} : B_{i} ∩ W_{e} ≠ ∅ “if possible.”

We order these requirements as

R_{1}, R_{2}, …, R_{2e+1}, R_{2e+2}, …

where lowered numbered requirements will receive higher priority.

The construction will consist of a definition of a recursive function

g : ℕ → {1, 2} .

At stage s + 1 we shall define g(s) = 1 or g(s) = 2. We shall then define

B_{1}^{s+1} = {f(n) | n ≤ s, g(n) = 1} , B_{2}^{s+1} = {f(n) | n ≤ s, g(n) = 2} ,

beginning with B_{1}^{0} = B_{2}^{0} = ∅. At the end of the construction we shall define

B_{1} = ⋃_{s} B_{1}^{s} = {f(n) | g(n) = 1} , B_{2} = ⋃_{s} B_{2}^{s} = {f(n) | g(n) = 2} .

Obviously B_{1}, B_{2} will be r.e. sets, because g is recursive. Moreover, this method of construction automatically guarantees that A = B_{1} ∪ B_{2} and B_{1} ∩ B_{2} = ∅.

The details of the construction are as follows.

Stage 0. B_{1}^{0} = B_{2}^{0} = ∅.

Stage s+1. At this stage we define g(s), i.e., we decide whether f(s) goes into B_{1} or into B_{2}. Let e_{s} be the least e such that f(s) ∈ W_{e,s} and either B_{1}^{s} ∩ W_{e,s} = ∅ or B_{2}^{s} ∩ W_{e,s} = ∅. If e_{s} is undefined, or if B_{1}^{s} ∩ W_{e,s} = ∅, then define g(s) = 1, i.e., put f(s) into B_{1}, i.e., B_{1}^{s+1} = B_{1}^{s} ∪ {f(s)}, B_{2}^{s+1} = B_{2}^{s}. Otherwise, define g(s) = 2, i.e., put f(s) into B_{2}, i.e., B_{2}^{s+1} = B_{2}^{s} ∪ {f(s)}, B_{1}^{s+1} = B_{1}^{s}.

Note that, by construction, e_{s} takes on each possible value at most twice, so lim_{s} e_{s} = ∞.

We claim that the construction gives r.e. sets B_{1}, B_{2} which are recursively inseparable. To see this, assume for a contradiction that R is a recursive set separating B_{1}, B_{2}. We have B_{1} ⊆ R and B_{2} ∩ R = ∅. Let e and k be such that W_{e} = R and W_{k} = ℕ \ R. Then B_{1} ∩ W_{k} = ∅ and B_{2} ∩ W_{e} = ∅. Hence for all s we have B_{1}^{s} ∩ W_{k,s} = ∅ and B_{2}^{s} ∩ W_{e,s} = ∅. For all sufficiently large s we have e_{s} > e and e_{s} > k, hence by construction f(s) ∉ W_{e,s} ∪ W_{k,s}. Thus, there is a finite set F such that (∀x ∈ A \ F) ∃s (x ∈ A^{s+1} \ (W_{e,s} ∪ W_{k,s})). On the other hand, it is obvious that (∀x ∈ ℕ \ A) ∃s (x ∈ (W_{e,s} ∪ W_{k,s}) \ A^{s+1}). Hence A is recursive, a contradiction. This completes the proof.

3.7 Maximal Sets

Definition 3.7.1 (maximal sets). An r.e. set A ⊆ ℕ is said to be maximal if

1. \overline{A} = ℕ \ A is infinite, yet

2. ∀ r.e. B ⊇ A, either B \ A or ℕ \ B is finite.

Remark 3.7.2. Maximality is a lattice-theoretic property. It is equivalent to A being a maximal element of the lattice E^{∗} = E/{finite sets}.

Remark 3.7.3. If A is maximal, then A is simple. This is easily proved.

The following theorem is due to Friedberg. We have already stated this as item 2 in Remark 3.1.22.

Theorem 3.7.4. There exists a maximal set.

Remark 3.7.5 (movable markers). In our construction of a maximal set A, we shall have A = ⋃_{s} A^{s} where

A^{0} ⊆ A^{1} ⊆ ⋯ ⊆ A^{s} ⊆ ⋯

and each A^{s} is finite. Here A^{0}, A^{1}, …, A^{s}, … will be a recursive sequence of finite sets. We shall write a_{n}^{s} = the nth element of \overline{A^{s}}, i.e.,

\overline{A^{s}} = \{a_{0}^{s} < a_{1}^{s} < ⋯ < a_{n}^{s} < ⋯ \} .

In addition, we shall have a_{n} = lim_{s} a_{n}^{s} = the nth element of \overline{A}, so that

\overline{A} = \{a_{0} < a_{1} < ⋯ < a_{n} < ⋯ \} .

A construction with these general features is known as a movable marker construction. We think of a_{n}^{s} as the position of the nth marker at stage s. Since A^{s} ⊆ A^{s+1}, we have a_{n}^{s+1} = a_{j}^{s} for some j ≥ n. This means that, whenever a marker is moved, it always lands on a position that was previously occupied by another marker. The fact that a_{n} = lim_{s} a_{n}^{s} < ∞ means that the nth marker is moved only finitely many times, and its final position is a_{n}.

Definition 3.7.6 (e-states). We define σ(e, x, s) = the e-state of x at stage s. This is defined by σ(e, x, s) = ⟨k_{0}, k_{1}, …, k_{e}⟩, where k_{i} = 1 if x ∈ W_{i,s}, and k_{i} = 0 otherwise. In addition, we define σ(e, x) = lim_{s} σ(e, x, s) = the final e-state of x.

Remark 3.7.7. The e-states are a bookkeeping device. Our strategy will be to maximize the final e-state of a_{e} with respect to the lexicographic ordering of e-states. This ordering is defined by putting

⟨k_{0}, k_{1}, …, k_{e}⟩ <_{lex} ⟨l_{0}, l_{1}, …, l_{e}⟩

if and only if there exists i ≤ e such that k_{0} = l_{0}, …, k_{i−1} = l_{i−1}, k_{i} < l_{i}.

We now prove Theorem 3.7.4.

Proof. Our construction is as follows.

Stage 0. Put A^{0} = ∅, and a_{e}^{0} = e for all e.

Stage s+1. We have \overline{A^{s}} = \{a_{0}^{s} < a_{1}^{s} < ⋯ < a_{e}^{s} < ⋯ \}. Choose the least e such that σ(e, a_{e}^{s}, s) <_{lex} σ(e, a_{j}^{s}, s) for some j > e. For this e, choose the least such j. Put A^{s+1} = A^{s} ∪ {a_{e}^{s}, a_{e+1}^{s}, …, a_{j−1}^{s}}. If there is no such e, do nothing, i.e., A^{s+1} = A^{s}.

Remark 3.7.8. By construction, a_{i}^{s} ≤ a_{i}^{s+1} for all i. If no e is chosen at stage s + 1, then a_{i}^{s} = a_{i}^{s+1} for all i. If e is chosen at stage s + 1, then a_{i}^{s} = a_{i}^{s+1} for all i < e, and a_{j}^{s} < a_{j}^{s+1} for all j ≥ e, and σ(e, a_{e}^{s}, s) <_{lex} σ(e, a_{e}^{s+1}, s + 1).

Remark 3.7.9. Clearly the construction is primitive recursive, and A = ⋃_{s} A^{s} is an r.e. set. The idea behind the construction is that for each index i we have a requirement

R_{i}: for all e ≥ i, a_{e} ∈ W_{i} “if possible,”

with priority i. Lower numbered requirements receive higher priority, embodied in the lexicographic ordering of e-states.

Lemma 3.7.10. For all e, a_{e} = lim_{s} a_{e}^{s} exists and is finite, i.e., the eth marker moves only finitely many times.

Proof. By induction on e, let s_{1} be such that ∀s > s_{1} ∀i < e (a_{i}^{s} = a_{i}^{s+1}). It follows that ∀s ≥ s_{1} ∀i < e (i was not chosen at stage s+1). Hence, for every s ≥ s_{1}, if a_{e}^{s} < a_{e}^{s+1} then e was chosen at stage s+1, and σ(e, a_{e}^{s}, s) <_{lex} σ(e, a_{e}^{s+1}, s). Since there are only 2^{e+1} e-states, it follows that {s ≥ s_{1} | a_{e}^{s} < a_{e}^{s+1}} is of cardinality < 2^{e+1}. This proves our lemma.

Because of the previous lemma, we now know that

\overline{A} = \{a_{0} < a_{1} < ⋯ < a_{e} < ⋯ \}

is infinite.

Lemma 3.7.11. ¬ ∃e ∃j (e < j ∧ σ(e, a_{e}) <_{lex} σ(e, a_{j})).

Proof. Suppose not, i.e., e < j and σ(e, a_{e}) <_{lex} σ(e, a_{j}). By Lemma 3.7.10, for all sufficiently large s and all i ≤ j we have a_{i}^{s} = a_{i} and σ(e, a_{i}, s) = σ(e, a_{i}). In particular a_{e}^{s} = a_{e} and σ(e, a_{e}^{s}, s) = σ(e, a_{e}) <_{lex} σ(e, a_{j}) = σ(e, a_{j}^{s}, s). Hence some i ≤ e must have been chosen at stage s + 1, hence a_{e}^{s} < a_{e}^{s+1}, and this is a contradiction.

Lemma 3.7.12. ∀e (W_{e} ∩ \overline{A} or \overline{W}_{e} ∩ \overline{A} is finite ).

Proof. By induction on e, we have ∀k < e (W_{k} ∩ \overline{A} or \overline{W}_{k} ∩ \overline{A} is finite), i.e., σ(e−1, a_{i}) = σ(e−1, a_{j}) for all sufficiently large i and j. If W_{e}∩\overline{A} and \overline{W}_{e}∩\overline{A} are both infinite, there exist i and j such that e ≤ i < j and σ(e−1, a_{i}) = σ(e−1, a_{j}) and a_{i} ∉ W_{e} and a_{j} ∈ W_{e}. It follows that σ(i, a_{i}) <_{lex} σ(i, a_{j}), contradicting Lemma 3.7.11.

This completes the proof of Theorem 3.7.4.

3.8 The Owings Splitting Theorem and its Consequences

Remark 3.8.1. Recall from Definition 3.1.20 that a Boolean algebra is a complemented distributive lattice with 0 and 1. We state without proof the following well known algebraic facts.

1. Every distributive lattice with 0 and 1 is a sublattice of a Boolean algebra with the same 0 and 1.

2. Every Boolean algebra is isomorphic to a subalgebra of the Boolean algebra (P (X), ∪, ∩, ∅, X), where X is a set.

3. Every finite Boolean algebra is isomorphic to P ({1, …, n}) for some n, hence is of cardinality 2^{n}.

On the other hand, there are plenty of distributive lattices with 0 and 1 which are not complemented, i.e., not Boolean algebras. Examples are: (1) any linear ordering with a bottom element 0 and a top element 1 and at least one additional element; (2) the lattice of functions [0, 1]^{X} for any nonempty set X. Here [0, 1] is the unit interval in the real line.

Recall that E, the lattice of r.e. sets, is a distributive lattice with 0 and 1. It is not a Boolean algebra, because there exist nonrecursive r.e. sets. The Friedberg Splitting Theorem says:

If A ∈ E is nonrecursive, then there exist nonrecursive B_{1}, B_{2} ∈ E such that B_{1} ∪ B_{2} = A and B_{1} ∩ B_{2} = ∅.

We now consider some closely related lattices.

Definition 3.8.2. We define

E^{∗} = E/{finite sets} .

Like E, E^{∗} is a distributive lattice with 0 and 1 and is not a Boolean algebra. Unlike E, E^{∗} is atomless, i.e.,

∀a ∈ E^{∗} (a > 0 ⇒ ∃b ∈ E^{∗} (a > b > 0)) .

Definition 3.8.3. Let C be a fixed r.e. set. We define

E(C) = {A ∈ E | A ⊇ C} ,

the lattice of r.e. supersets of C. Again, E(C) is a distributive lattice, with 0 = C and 1 = ℕ. Note that there is a lattice homomorphism E → E(C) given by A ↦ A ∪ C. This homomorphism is a retraction. We define

E^{∗}(C) = E(C)/{finite sets} .

This is again a distributive lattice with 0 and 1.

Examples 3.8.4.

1. If C is cofinite, then |E^{∗}(C)| = 1. This is a degenerate case, which we shall ignore.

2. If C is a maximal set, then E(C) = {C ∪F, C ∪(ℕ−F) | F is finite}. Hence E^{∗}(C) = the 2-element Boolean algebra {0, 1}. In fact, this property is equivalent to maximality of C.

3. Let C = C_{1}∩C_{2} where C_{1}, C_{2} are maximal sets such that C_{1}∪C_{2} = ℕ, e.g., \overline{C}_{1} ⊆ \{evens\} and \overline{C}_{2} ⊆ \{odds\}. Then E^{∗}(C) = the 4-element Boolean algebra {0, c_{1}, c_{2}, 1}. Here c_{1} and c_{2} are the equivalence classes of C_{1} and C_{2} modulo finite sets.

4. Similarly let C = C_{1} ∩ ⋯ ∩ C_{n} where C_{i} is maximal and \overline{C}_{i}, i = 1, ⋯ n are pairwise disjoint. Then E^{∗}(C) = the 2^{n}-element Boolean algebra.

5. In the same vein, there exist r.e. sets C such that E^{∗}(C) is an infinite Boolean algebra. This Boolean algebra can be atomless or non-atomless, depending on C.

6. If C is a coinfinite r.e. set which is not simple (e.g., C = ∅, or C creative), then the lattices E(C) and E^{∗}(C) are not Boolean algebras.

Exercise 3.8.5. Show that E(C) is a Boolean algebra if and only if E^{∗}(C) is a Boolean algebra.

Remark 3.8.6. As we have just seen, E(C) and E^{∗}(C) can look quite different from E and E^{∗}. Nevertheless, the Friedberg Splitting Theorem generalizes to E(C). This is the content of the Owings Splitting Theorem, which we now state.

Theorem 3.8.7 (Owings). If A ∈ E(C) is noncomplemented, then there exist noncomplemented B_{1}, B_{2} ∈ E(C) such that A = B_{1} ∪ B_{2} and B_{1} ∩ B_{2} = C.

Remark 3.8.8. Setting C = ∅, we recover the Friedberg Splitting Theorem.

Before proving the Owings Splitting Theorem, we examine its consequences concerning lattice-theoretic properties of E(C) and E^{∗}(C).

Theorem 3.8.9. If E^{∗}(C) is finite, then E^{∗}(C) is a Boolean algebra. Hence |E^{∗}(C)| = 2^{n} and C is the intersection of n maximal sets, for some n.

Proof. Suppose E^{∗}(C) were not a Boolean algebra. It follows that E(C) is not a Boolean algebra. Let A ∈ E(C) be noncomplemented. By the Owings Splitting Theorem, let A = B_{1} ∪ B_{2} where B_{1} ∩ B_{2} = C and B_{1} and B_{2} are noncomplemented. By the Owings Splitting Theorem again, let B_{2} = B_{3} ∪ B_{4}, where B_{3} ∩ B_{4} = C and B_{3} and B_{4} are noncomplemented. Continuing in this fashion, we generate B_{1}, B_{3}, B_{5}, . . .. This is an infinite sequence of noncomplemented elements of E(C), the intersection of any two of which is C. It follows that E^{∗}(C) is infinite. This proves our theorem.

Corollary 3.8.10. |E^{∗}(C)| ≠ 3.

Next we shall use the Owings Splitting Theorem to characterize the r.e. sets C for which E(C) is a Boolean algebra. Recall that this property implies that C is simple. We shall now define a subclass of the simple sets, called the hyperhypersimple sets. This class was first defined by Post.

Definition 3.8.11 (hyperhypersimple sets).

1. An array is a uniformly r.e. sequence of r.e. sets. Thus an array consists of a sequence of Σ_{1}^{0} sets B_{i} ⊆ ℕ, i = 0, 1, 2, …, such that in addition the 2-place relation {⟨x, i⟩ | x ∈ B_{i}} is Σ_{1}^{0}. By the Parametrization Theorem, this is equivalent to saying that B_{i} = W_{f(i)} for all i, where f(i) is some primitive recursive function.

2. An r.e. set C is said to be hyperhypersimple, abbreviated hhsimple, if \overline{C} is infinite and there does not exist an array of pairwise disjoint r.e. sets W_{f(i)}, i = 0, 1, 2, …, such that W_{f(i)} ∩ \overline{C} ≠ ∅ for all i.

Theorem 3.8.12 (Lachlan). E(C) is a Boolean algebra if and only if C is hyperhypersimple.

Proof. In this proof we shall apply a uniform version of the Owings Splitting Theorem. The uniform version reads as follows.

Given an r.e. index of a noncomplemented A ∈ E(C), we can recursively find r.e. indices of noncomplemented B_{1}, B_{2} ∈ E(C) such that B_{1} ∪ B_{2} = A and B_{1} ∩ B_{2} = C.

Assume now that E(C) is not a Boolean algebra. Let A ∈ E(C) be noncomplemented. Repeatedly apply the Owings Splitting Theorem as in the proof of Theorem 3.8.9 to generate an infinite sequence of noncomplemented sets

B_{1}, B_{3}, …, B_{2i+1}, … ∈ E(C) ,

the intersection of any two of which is C. By the uniformity, we may assume that B_{1}, B_{3}, …, B_{2i+1} are uniformly r.e., i.e., they form an array. This is almost what we want, except that these sets are not pairwise disjoint (unless C = ∅). To make them pairwise disjoint, let ψ(x) be a partial recursive function which uniformizes the Σ_{1}^{0} relation S(x, i) ≡ x ∈ B_{2i+1}. By the Parametrization Theorem, let f(i) be a primitive recursive function such that W_{f(i)} = {x | ψ(x) ≃ i} for all i. Then clearly W_{f(i)}, i = 0, 1, 2, …, are pairwise disjoint, and W_{f(i)}∩\overline{C} = B_{2i+1}∩\overline{C} ≠ ∅ for all i. Thus C is not hhsimple.

Conversely, assume that C is not hhsimple. Let W_{f(i)}, i = 0, 1, 2, … be an array of pairwise disjoint r.e. sets such that W_{f(i)} ∩ \overline{C} ≠ ∅ for all i. Set

A = C ∪ ⋃_{i=0}^{∞}(W_{i} ∩ W_{f(i)}) .

Obviously A ∈ E(C). We claim that A is noncomplemented in E(C). Suppose B ∈ E(C) is the complement of A within E(C), i.e., A ∩ B = C and A ∪ B = ℕ. Let e be such that B = W_{e}. Let x ∈ W_{f(e)} ∩ \overline{C}. Since the W_{f(i)}, i = 0, 1, 2, …, are pairwise disjoint, we have x ∈ B ⇔ x ∈ W_{e} ⇔ x ∈ W_{e} ∩ W_{f(e)} ⇔ x ∈ A. This contradiction completes the proof.

Exercises 3.8.13.

1. Show that C is hhsimple if and only if, for all r.e. sets A, \overline{A} ∪ C is r.e.

2. Show that if C_{1} and C_{2} are hhsimple then C_{1} ∩ C_{2} is hhsimple.

3.9 Proof of the Owings Splitting Theorem

In this section we prove Theorem 3.8.7, the Owings Splitting Theorem.

Remark 3.9.1. The general framework for the proof will be the same as for the Friedberg Splitting Theorem. Let A and C be r.e. sets. Let f be a one-to-one recursive function which enumerates A. We write A^{s} = {f(0), …, f(s − 1)}. Similarly, let C^{s} be an enumeration of C. Just as in Section 3.6, we shall recursively decide at stage s + 1 whether to put f(s) into B_{1} or into B_{2}. Thus we shall automatically have B_{1}, B_{2} r.e. and B_{1} ∪ B_{2} = A and B_{1} ∩ B_{2} = ∅.

In order to prove the Owings Splitting Theorem, we shall want to make sure that B_{1} ∪ C and B_{2} ∪ C are noncomplemented in E(C). Note that, for any r.e. sets B and C, B ∪ C is complemented in E(C) if and only if \overline{B} ∪ C is r.e. In other words, there exists e such that W_{e} = \overline{B} ∪C. In particular, W_{e} ∩B \C = ∅. Therefore, our strategy in the construction will be to make W_{e} ∩ B_{i} \ C ≠ ∅ “if possible,” for all e and for i = 1, 2. As in Section 3.6, these requirements will have a priority ordering given by (e′, i′) < (e, i) if and only if 2e′ + i′ < 2e + i.

As part of our construction, in order to mitigate the effect of C, we shall define an auxiliary recursive function h(e, i, s) for all e and for i = 1, 2. This function will somehow control the process.

The details of our construction are as follows.

Stage 0. Let B_{1}^{0} = B_{2}^{0} = ∅. Let h(e, i, 0) = 0 for all e and for i = 1, 2.

Stage s + 1. If ∃x < h(e, i, s) such that x ∈ W_{e,s} ∩ B_{i}^{s} \ C^{s}, let h(e, i, s + 1) = h(e, i, s). Otherwise, let h(e, i, s + 1) = h(e, i, s) + 1. Set y = f(s). Choose the least (e, i) such that y ∈ W_{e,s} and y < h(e, i, s). Put y into B_{i}, i.e., B_{i}^{s+1} = B_{i}^{s} ∪ {y}. If no such (e, i) exists, put y into B_{1}.

By construction, B_{1}, B_{2} are r.e. and A = B_{1} ∪ B_{2} and B_{1} ∩ B_{2} = ∅. Note also that h(e, i, s) ≤ h(e, i, s + 1) for all s.

Definition 3.9.2. Say that (e, i) is good if lim_{s} h(e, i, s) < ∞. Otherwise, say that (e, i) is bad.

Lemma 3.9.3. (e, i) is good ⟺ W_{e} ∩ B_{i} \ C ≠ ∅.

Proof. ⟹: Assume (e, i) is good but W_{e} ∩ B_{i} \ C = ∅, i.e., W_{e} ∩ B_{i} ⊆ C. Since (e, i) is good, let s be so large that h(e, i, t) = h(e, i, s) ∀t > s. Let t > s be so large that ∀x < h(e, i, s) (x ∈ W_{e} ∩ B_{i} ⇒ x ∈ C^{t}). Hence ¬ ∃x < h(e, i, t) (x ∈ W_{e,t} ∩B_{i}^{t} \C^{t}). Therefore h(e, i, t+1) = h(e, i, t)+1 > h(e, i, s), a contradiction.

⟸: Assume (e, i) is bad and W_{e}∩B_{i}\C ≠ ∅. Fix x ∈ W_{e}∩B_{i}\C. Since (e, i) is bad, lim_{s} h(e, i, s) = ∞, hence for all sufficiently large s we have x < h(e, i, s) and x ∈ W_{e,s} ∩ B_{i}^{s} \ C^{s}, hence h(e, i, s + 1) = h(e, i, s), a contradiction.

Lemma 3.9.4. If (e, i) is good, then {s | (e, i) is chosen at stage s + 1} is finite.

Proof. If (e, i) is chosen at stage s + 1, we have y = f(s) < h(e, i, s). Since lim_{s} h(e, i, s) < ∞ and f is one-to-one, this can happen only finitely many times.

Lemma 3.9.5. Suppose (e, i) is bad. If (e, i) is chosen at stage s + 1, then y = f(s) ∈ C.

Proof. Since (e, i) is chosen at stage s + 1, we have y = f(s) ∈ W_{e,s} and y < h(e, i, s) and y ∈ B_{i}^{s+1}. So y ∈ W_{e} ∩B_{i}. Hence, by Lemma 3.9.3, y ∈ C.

Lemma 3.9.6. Assume that A ∪ C is noncomplemented in E(C). Then for i = 1, 2, B_{i} ∪ C is noncomplemented in E(C).

Proof. Suppose that B_{i} ∪ C is complemented in E(C), say W_{e} = \overline{B_{i}} ∪ C. In particular, W_{e} ∩ B_{i} \ C = ∅, hence (e, i) is bad. By Lemma 3.9.4, let s_{1} be so large that, for all s ≥ s_{1} and all good (e′, i′) < (e, i), (e′, i′) is not chosen at stage s + 1. Put

W̃_{e} = {x | ∃s ≥ s_{1} (x ∈ W_{e,s} ∧ x ∉ A^{s} ∧ x < h(e, i, s))} .

Clearly W̃_{e} is r.e.

We claim that W̃_{e} ∪ C is the complement of A ∪ C in E(C).

Suppose first that x ∉ A ∪ C. Since B_{i} ⊆ A, we have \overline{A} ⊆ \overline{B_{i}}, hence x ∈ W_{e}. Since (e, i) is bad, for all sufficiently large s ≥ s_{1} we have x < h(e, i, s), and x ∈ W_{e,s}. Since x ∉ A, x ∉ A^{s}, hence x ∈ W̃_{e}.

Suppose next that y ∈ W̃_{e}∩A. Since y ∈ W̃_{e}, let s ≥ s_{1} be such that y ∈ W_{e,s} and x ∉ A^{s} and y < h(e, i, s). Since y ∈ A and y ∉ A^{s} = {f(0), …, f(s)}, let t > s be such that y = f(t). Clearly y ∈ W_{e,t} and y < h(e, i, t). Hence, by construction, at stage t + 1 some bad (e′, i′) ≤ (e, i) was chosen. Hence, by Lemma 3.9.5, y ∈ C.

We have now proved our claim. Thus A ∪ C is complemented in E(C).

The proof of the Owings Splitting Theorem 3.8.7 is now complete.

Remark 3.9.7. Our construction above is uniform. Therefore, given r.e. indices for A and C, we can use the Parametrization Theorem to primitive recursively find r.e. indices for B_{1} and B_{2}. This extra uniformity was used in the proof of Lachlan’s Theorem 3.8.12.

3.10 Oracle Computations

In this section we discuss oracle computations, i.e., computations where the computing device has the ability to consult an oracle. Intuitively, an oracle is a “black box” which, given a natural number as input, immediately produces a natural number as output. Our formal definitions are as follows.

Definition 3.10.1 (oracles). An oracle is a total function f : ℕ → ℕ. We write ℕ^{ℕ} for the set of all oracles. Note that ℕ^{ℕ} is also known as the Baire space.

Definition 3.10.2. Recall from Math 558 [14] that a register machine program consists of four kinds of instructions: a start instruction

[figure: start],

increment instructions

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

decrement instructions

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

and stop instructions

[figure: stop] .

We now introduce a fifth kind of instruction

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

called an oracle instruction. In the presence of an oracle f, the effect of [figure: R_{i}^{O}]

is to replace the content n of R_{i} by f(n). In other words, if R_{i} contains n

before executing [figure: R_{i}^{O}] , then afterward R_{i} contains f(n). We define an oracle

program to be a register machine program as in Math 558 [14], except that oracle instructions are allowed.

Definition 3.10.3 (oracle computations). Let P be an oracle program, let f be an oracle, and let x_{1}, …, x_{k} ∈ ℕ, where k ≥ 0. We denote by P^{f}(x_{1}, …, x_{k}) the unique run of P using oracle f starting with x_{1}, …, x_{k} in R_{1}, …, R_{k} and all other registers empty. As before, the output of P^{f}(x_{1}, …, x_{k}) is the content of R_{k+1} if and when P^{f}(x_{1}, …, x_{k}) halts. If e = #(P) = the Gödel number of P, we write

φ_{e}^{(k),f}(x_{1}, …, x_{k}) ≃ the output of P^{f}(x_{1}, …, x_{k}) .

We also introduce notations such as

W_{e}^{f} = domain(φ_{e}^{(1),f}) .

Definition 3.10.4 (f-recursive functions, etc.). Let f ∈ ℕ^{ℕ} be a fixed oracle. A partial function ψ : ℕ^{k} ⟶^{P} ℕ is said to be partial f-recursive or partial recursive in f or partial recursive relative to f, if there exists e ∈ ℕ such that ψ(x_{1}, …, x_{k}) ≃ φ_{e}^{(k),f}(x_{1}, …, x_{k}) for all x_{1}, …, x_{k} ∈ ℕ. Similarly, a set A ⊆ ℕ is said to be f-recursively enumerable if and only if A = W_{e}^{f} for some e ∈ ℕ, etc.

Remark 3.10.5. If the oracle f happens to be recursive, then clearly ψ is partial f-recursive ⟺ ψ is partial recursive, A is f-r.e. ⟺ A is r.e., etc. Thus we see that oracle computations are a generalization of ordinary, non-oracle computations.

Remark 3.10.6 (relativization to an oracle). Let f ∈ ℕ^{ℕ} be a fixed oracle. A routine generalization of the Enumeration Theorem from Math 558 [14] asserts that for each f ∈ ℕ^{ℕ} and each k ≥ 0 the partial function

(e, x_{1}, …, x_{k}) ↦ φ_{e}^{(k),f}(x_{1}, …, x_{k})

is partial f-recursive. Similarly, all of our previous results about partial recursive functions, r.e. sets, the arithmetical hierarchy, etc., generalize routinely to partial f-recursive functions, f-r.e. sets, the f-arithmetical hierarchy, etc., where f ∈ ℕ^{ℕ} is an arbitrary oracle. This process of routine generalization, replacing φ_{e}^{(k)} by φ_{e}^{(k),f}, etc., is known as relativization to f.

Definition 3.10.7 (relativized arithmetical hierarchy). Let f ∈ ℕ^{ℕ} be a fixed oracle. For k, n ≥ 1, a relation S ⊆ ℕ^{k} is said to be Σ_{n}^{0,f} if there exists an f-recursive relation R ⊆ ℕ^{k+n} such that

S(x_{1}, …, x_{k}) ≡ ∃y_{1} ∀y_{2} ⋯ y_{n} R(x_{1}, …, x_{k}, y_{1}, y_{2}, …, y_{n})

where there are n alternating quantifiers, and the last quantifier is existential if n is odd, universal if n is even. A relation P ⊆ ℕ^{k} is said to be Π_{n}^{0,f} if ¬ P is Σ_{n}^{0,f}. A relation D ⊆ ℕ^{k} is said to be Δ_{n}^{0,f} if it is both Σ_{n}^{0,f} and Π_{n}^{0,f}. The classes Σ_{n}^{0,f}, Π_{n}^{0,f}, Δ_{n}^{0,f}, n ≥ 1 are known as the f-arithmetical hierarchy. All of the standard results about the arithmetical hierarchy (see Math 558 notes [14]) generalize routinely to the f-arithmetical hierarchy, for each f ∈ ℕ^{ℕ}.

Remark 3.10.8. Instead of viewing f as a fixed oracle, we may choose to view f as a variable ranging over the Baire space ℕ^{ℕ}. In this way, one develops a kind of recursion theory over ℕ^{ℕ}, including a version of the arithmetical hierarchy over ℕ^{ℕ}, etc. The starting point of this theory is the following definition.

Definition 3.10.9 (partial recursive functionals).

1. A partial functional is a partial function Ψ : ℕ^{ℕ} × ℕ^{k} ⟶^{P} ℕ, where k ≥ 0.

2. A partial functional Ψ : ℕ^{ℕ} × ℕ^{k} ⟶^{P} ℕ is said to be partial recursive if it is computable, i.e., if there exists e ∈ ℕ such that

Ψ(f, x_{1}, …, x_{k}) ≃ φ_{e}^{(k),f}(x_{1}, …, x_{k})

for all f ∈ ℕ^{ℕ} and all x_{1}, …, x_{k} ∈ ℕ.

Example 3.10.10. We exhibit an oracle program which computes the partial recursive functional Ψ(f, x) ≃ the least y ≥ x such that f(y) > 0.

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

Letting e be the Gödel number of this program, we have φ_{e}^{(1),f}(x) ≃ Ψ(f, x) for all f ∈ ℕ^{ℕ} and all x ∈ ℕ.

The Enumeration, Parametrization, and Recursion Theorems from Math 558 [14] easily generalize to partial recursive functionals, as follows:

Theorem 3.10.11 (Enumeration Theorem). For each k ≥ 0 we have a partial recursive functional

(f, e, x_{1}, …, x_{k}) ↦ φ_{e}^{(k),f}(x_{1}, …, x_{k}) .

Theorem 3.10.12 (Parametrization Theorem). Given a partial recursive functional Ψ(f, x_{0}, x_{1}, …, x_{k}), we can find a primitive recursive function h(x_{0}) such that

φ_{h(x_{0})}^{(k),f}(x_{1}, …, x_{k}) ≃ Ψ(f, x_{0}, x_{1}, …, x_{k})

for all f ∈ ℕ^{ℕ} and all x_{0}, x_{1}, …, x_{k} ∈ ℕ.

Theorem 3.10.13 (Recursion Theorem). Given a partial recursive functional Ψ(f, x_{0}, x_{1}, …, x_{k}), we can find an index e ∈ ℕ such that

φ_{e}^{(k),f}(x_{1}, …, x_{k}) ≃ Ψ(f, e, x_{1}, …, x_{k})

for all f ∈ ℕ^{ℕ} and all x_{1}, …, x_{k} ∈ ℕ.

In this vein we obtain an alternative generalization of the arithmetical hierarchy from Math 558 [14], as follows.

Definition 3.10.14 (arithmetical hierarchy). For k ≥ 0, a relation R ⊆ ℕ^{ℕ} × ℕ^{k} is said to be recursive if its characteristic function χ_{R} : ℕ^{ℕ} × ℕ^{k} → ℕ is recursive. For k ≥ 0 and n ≥ 1, a relation S ⊆ ℕ^{ℕ} × ℕ^{k} is said to be Σ_{n}^{0} if there exists a recursive relation R ⊆ ℕ^{ℕ} × ℕ^{k+n} such that

S(f, x_{1}, …, x_{k}) ≡ ∃y_{1} ∀y_{2} ⋯ y_{n} R(f, x_{1}, …, x_{k}, y_{1}, y_{2}, …, y_{n})

where there are n alternating quantifiers, and the last quantifier is existential if n is odd, universal if n is even. A relation P ⊆ ℕ^{ℕ} × ℕ^{k} is said to be Π_{n}^{0} if ¬ P is Σ_{n}^{0}. A relation D ⊆ ℕ^{ℕ} × ℕ^{k} is said to be Δ_{n}^{0} if it is both Σ_{n}^{0} and Π_{n}^{0}.

3.11 Degrees of Unsolvability

We now introduce Turing degrees, a.k.a., degrees of unsolvability.

Definition 3.11.1 (Turing reducibility). Let f and g be total functions, i.e., f, g ∈ ℕ^{ℕ}. We say that f is Turing reducible to g, abbreviated f ≤_{T} g, if f is computable using g as an oracle, i.e., f is recursive relative to g, i.e., f is g-recursive, i.e.,

∃e ∀x f(x) = φ_{e}^{(1),g}(x) .

Proposition 3.11.2. For f, g, h ∈ ℕ^{ℕ}, we have

1. f ≤_{T} f, and

2. if f ≤_{T} g and g ≤_{T} h, then f ≤_{T} h.

Proof. Straightforward. Note that, if we write

REC(f) = {h ∈ ℕ^{ℕ} | h is f-recursive} ,

then f ≤_{T} g if and only if REC(f) ⊆ REC(g).

Definition 3.11.3. For f, g ∈ ℕ^{ℕ} we say that f is Turing equivalent to g, abbreviated f ≡_{T} g, if f ≤_{T} g and g ≤_{T} f, i.e., REC(f) = REC(g).

Proposition 3.11.4. ≡_{T} is an equivalence relation on ℕ^{ℕ}.

Proof. Immediate from Proposition 3.11.2.

Definition 3.11.5 (Turing degrees). We let D_{T} denote the set of equivalence classes of ℕ^{ℕ} modulo Turing reducibility:

D_{T} = ℕ^{ℕ}/≡_{T} .

Elements of D_{T} are known as Turing degrees or degrees of unsolvability or sometimes just degrees. For any f ∈ ℕ^{ℕ}, the Turing degree of f is

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

We partially order D_{T} by letting deg_{T} (f) ≤ deg_{T} (g) if and only if f ≤_{T} g. Clearly this relation does not depend on the representative chosen from each equivalence class.

The structure of the partial ordering (D_{T} , ≤) has received much scrutiny in hundreds of research papers. In this section we mention only the most basic properties of D_{T}.

Proposition 3.11.6. D_{T} has a least element, 0, which is just the set REC of recursive functions.

Proof. Straightforward, since any recursive function is g-recursive for all g.

Proposition 3.11.7. Every pair of Turing degrees a, b ∈ D_{T} has a least upper bound a ∨ b ∈ D_{T}. Thus (D_{T} , ≤) is an upper semilattice.

Proof. Let a = deg_{T} (f) and b = deg_{T} (g) be given, where f ∈ ℕ^{ℕ} and g ∈ ℕ^{ℕ}. We define a function f ⊕ g ∈ ℕ^{ℕ} by letting (f ⊕ g)(2n) = f(n) and (f ⊕ g)(2n + 1) = g(n) for all n ∈ ℕ. We claim that

deg_{T} (f ⊕ g) = deg_{T} (f) ∨ deg_{T} (g) ,

i.e., deg_{T} (f ⊕ g) is the least upper bound of deg_{T} (f) and deg_{T} (g). Clearly f ≤_{T} f ⊕ g and g ≤_{T} f ⊕ g. For any h ∈ ℕ^{ℕ}, if f ≤_{T} h and g ≤_{T} h, then it is straightforward to show that f ⊕ g ≤_{T} h.

Definition 3.11.8 (Turing degrees of sets). Given a set A ⊆ ℕ, we define deg_{T} (A) = deg_{T} (χ_{A}). In other words, the Turing degree of a set A ⊆ ℕ is defined to be the Turing degree of its characteristic function χ_{A} : ℕ → ℕ. The following proposition shows that there is no loss in considering only Turing degrees of sets, rather than functions.

Proposition 3.11.9. Every Turing degree contains (the characteristic function of) a set.

Proof. Let deg_{T} (f) be an arbitrary Turing degree, where f ∈ ℕ^{ℕ}. It is straightforward to prove that f ≡_{T} χ_{A} where A = G_{f} = {2^{n}3^{m} | f(n) = m}. The proof uses the fact that f is a total function.

Definition 3.11.10. For f ∈ ℕ^{ℕ}, we let f′ = H^{f} be the Halting Problem relative to f, i.e.,

f′ = H^{f} = {e | φ_{e}^{(1),f}(0) ↓} .

We can show that H^{f} is a complete Σ_{1}^{0,f} set, i.e., H^{f} is Σ_{1}^{0,f} and every Σ_{1}^{0,f} set A ⊆ ℕ is ≤_{m} H^{f}. This is the relativization to f of the fact that the Halting Problem H = {e | φ_{e}^{(1)}(0) ↓} is a many-one complete r.e. set.

Proposition 3.11.11. For all f, g ∈ ℕ^{ℕ} we have

1. f <_{T} H^{f}.

2. If f ≤_{T} g then H^{f} ≤_{T} H^{g}.

3. f ≤_{T} g if and only if H^{f} ≤_{m} H^{g}.

4. H^{f} ≡_{T} ¬ H^{f} but H^{f} ≢_{m} ¬ H^{f}.

Proof. Straightforward.

Definition 3.11.12 (the Turing jump). For any Turing degree a = deg_{T} (f) we let a′ = deg_{T} (f′) = deg_{T} (H^{f}). The degree a′ is called the Turing jump of a. By Proposition 3.11.11, f ≡_{T} g implies H^{f} ≡_{T} H^{g}. Thus a′ is well defined for all a ∈ D_{T}. The Turing jump operator J : D_{T} → D_{T} is defined by J(a) = a′.

Lemma 3.11.13. For any Turing degree a we have the strict inequality a < a′. For all a, b ∈ D_{T}, if a ≤ b then a′ ≤ b′.

Proof. This is immediate from Proposition 3.11.11.

Definition 3.11.14. For a ∈ D_{T} we define the iterated Turing jumps of a by induction as follows. Let a^{(0)} = a, and let a^{(n+1)} = (a^{(n)})′ for each n ∈ ℕ. Note that if a = deg_{T} (A) then a^{(n)} = deg_{T} (A^{(n)}), where A^{(0)} = A and A^{(n+1)} = A^{(n)′}.

An interesting relationship between Turing degrees and the arithmetical hierarchy is given by the following theorem due to Post.

Theorem 3.11.15 (Post). For n ≥ 1, a set A ⊆ ℕ is Σ_{n}^{0} if and only if it is r.e. relative to 0^{(n−1)}. More generally, for A, B ⊆ ℕ, A is Σ_{n}^{0,B} if and only if A is r.e. relative to B^{(n−1)}.

Proof. We omit the proof. See my Spring 2004 lecture notes [15].

Corollary 3.11.16. For n ≥ 1, A is Δ_{n}^{0} if and only if A ≤_{T} 0^{(n−1)}. More generally, A is Δ_{n}^{0,B} if and only if A ≤_{T} B^{(n−1)}.

Proof. A is Δ_{n}^{0,B} ⟺ A, ¬ A are Σ_{n}^{0,B} ⟺ A, ¬ A are r.e. relative to B^{(n−1)} ⟺ A is recursive relative to B^{(n−1)}, i.e., A ≤_{T} B^{(n−1)}.

We note the following special case.

Corollary 3.11.17. A ≤_{T} 0′ if and only if A is Δ_{2}^{0}.

3.12 The Sacks Splitting Theorem and its Consequences

A substructure of (D_{T} , ≤) which has received a huge amount of attention is the recursively enumerable Turing degrees.

Definition 3.12.1. Let

E_{T} = {deg_{T} (A) | A is recursively enumerable} .

The elements of E_{T} are called recursively enumerable Turing degrees, or r.e. Turing degrees, or sometimes just r.e. degrees.

The essential structure of E_{T} is given by the following proposition. Proposition 3.12.2.

1. 0, 0′ ∈ E_{T}.

2. 0 is the bottom element of E_{T}.

3. 0′ is the top element of E_{T}.

4. E_{T} is closed under l.u.b. This means that if a, b ∈ E_{T} then a ∨ b ∈ E_{T}. Proof. Statements 1 and 2 are obvious. If A is r.e., then by Proposition 3.2.5 A ≤_{m} H = 0′, hence A ≤_{T} 0′ and this gives statement 3. Alternatively, statement 3 follows from Corollary 3.11.17. For statement 4, note that if A, B ⊆ ℕ are r.e. then so is

A ⊕ B = {2n | n ∈ A} ∪ {2n + 1 | n ∈ B}

and χ_{A⊕B} = χ_{A} ⊕ χ_{B}. Remarks 3.12.3.

1. There are many Turing degrees a such that a ≤ 0′ yet a ∉ E_{T}. Examples are provided by the Kleene/Post construction (see for instance [15]).

2. There are many sets B ⊆ N such that deg_{T} (B) ∈ E_{T} yet B is not r.e. For example, let B be the complement of a nonrecursive r.e. set.

At this moment, we have not yet proved that there exist any r.e. Turing degrees other than 0 and 0′. We shall prove the following theorem, which gives this and much more information concerning the structure of the r.e. degrees. Theorem 3.12.4 (Sacks Splitting Theorem). Let A ⊆ ℕ be a nonrecursive r.e. set. Let C ⊆ ℕ be nonrecursive. There exist r.e. sets B_{1} and B_{2} such that

1. A = B_{1} ∪ B_{2},

2. B_{1} ∩ B_{2} = ∅,

3. B_{1} ≰_{T} B_{2},

4. B_{2} ≰_{T} B_{1},

5. 0 <_{T} B_{1} <_{T} A,

6. 0 <_{T} B_{2} <_{T} A,

7. B_{1} ⊕ B_{2} ≡_{T} A,

8. C ≰_{T} B_{1},

9. C ≰_{T} B_{2}.

Before proving the Sacks Splitting Theorem, we note some of its corollaries. Say that b_{1}, b_{2} ∈ D_{T} are incomparable, and write b_{1} | b_{2}, if b_{1} ≰ b_{2} and b_{2} ≰ b_{1}.

Corollary 3.12.5. For any a ∈ E_{T} with a > 0, there exist b_{1}, b_{2} ∈ E_{T} such that a > b_{1} > 0, a > b_{2} > 0, a = b_{1} ∨ b_{2}, and b_{1} | b_{2}.

Proof. This is an immediate translation of parts 1–7 of the Sacks Splitting Theorem 3.12.4.

Corollary 3.12.6 (Friedberg, Muchnik). There are incomparable r.e. Turing degrees in E_{T}.

Proof. Apply Corollary 3.12.5 with a = 0′.

Corollary 3.12.7. There is an infinite strictly descending sequence of r.e. Turing degrees. There is an infinite set of pairwise incomparable r.e. Turing degrees.

Proof. Start with a_{0} = 0′. By Corollary 3.12.5 find r.e. degrees a_{1}, a_{2} < a_{0} such that a_{1} | a_{2}. By Corollary 3.12.5 again, find r.e. degrees a_{3}, a_{4} < a_{2} such that a_{3} | a_{4}. Continuing in this fashion, we see that a_{0} > a_{2} > a_{4} > ⋯ is an infinite descending sequence of r.e. degrees, while a_{1}, a_{3}, a_{5}, … is an infinite sequence of pairwise incomparable r.e. degrees.

Corollary 3.12.8. For any a > 0 in E_{T}, there exists b in E_{T} such that a > b > 0.

Proof. Apply Corollary 3.12.5 to a.

Corollary 3.12.9 (Friedberg, Muchnik). There exists a recursively enumerable Turing degree a which is intermediate, i.e., 0 < a < 0′. Equivalently, a ≠ 0, 0′.

Remark 3.12.10 (natural examples). The previous corollary is the solution to Post’s Problem (see Rogers [11]). Another interesting and important problem, which remains open, is to find an example of a recursively enumerable Turing degree other than 0 and 0′ which is mathematically natural. The term “mathematically natural” has not been rigorously defined, but we would recognize such an example if we saw one.

3.13 Proof of the Sacks Splitting Theorem

We now turn to the proof of the Sacks Splitting Theorem. We begin by noting that many of the conclusions will follow automatically, if we can only prove that A ≰_{T} B_{1} and A ≰_{T} B_{2}.

Lemma 3.13.1. Let A, B_{1}, B_{2} be r.e. sets such that A = B_{1}∪B_{2} and B_{1}∩B_{2} = ∅. Then A ≡_{T} B_{1} ⊕ B_{2}. Moreover, if A ≰_{T} B_{1} and A ≰_{T} B_{2}, then B_{1} ≰_{T} B_{2} and B_{2} ≰_{T} B_{1}, hence 0 <_{T} B_{1} <_{T} A and 0 <_{T} B_{2} <_{T} A.

Proof. Assume first that A, B_{1}, B_{2} are r.e. with A = B_{1} ∪ B_{2} and B_{1} ∩ B_{2} = ∅. We have n ∈ A ⟺ (n ∈ B_{1} ∨ n ∈ B_{2}), so clearly A ≤_{T} B_{1} ⊕ B_{2}. For the converse, note that

n ∈ B_{1} ⟺ (n ∈ A ∧ n ∉ B_{2}) .

Since ¬ B_{2} is Π_{1}^{0}, it follows that B_{1} is Π_{1}^{0,A}. But B_{1} is Σ_{1}^{0}, hence Σ_{1}^{0,A}, so we actually have that B_{1} is Δ_{1}^{0,A}, i.e., B_{1} is A-recursive, i.e., B_{1} ≤_{T} A. A similar argument shows that B_{2} ≤_{T} A. We now see that B_{1} ⊕ B_{2} ≤_{T} A.

Now assume in addition that A ≰_{T} B_{1} and A ≰_{T} B_{2}. We therefore have B_{1} <_{T} A and B_{2} <_{T} A. Since B_{1} ⊕ B_{2} ≡ A, it follows that B_{1} and B_{2} are Turing incomparable, hence nonrecursive.

We shall obtain the Sacks Splitting Theorem as a consequence of the following theorem of Binns, which is not only more general but also easier to state.

Theorem 3.13.2 (Binns Splitting Theorem). Let P ⊆ ℕ^{ℕ} be Π_{1}^{0} with no recursive members, i.e., P ∩ REC = ∅. Let A be an r.e. set. Then we can find r.e. sets B_{1}, B_{2} such that A = B_{1} ∪ B_{2}, B_{1} ∩ B_{2} = ∅, and there is no f ∈ P such that f ≤_{T} B_{1} or f ≤_{T} B_{2}.

Proof. We postpone the proof to Section 3.15.

Remark 3.13.3. The next lemma shows that the Binns Splitting Theorem implies its own generalization, replacing the Π_{1}^{0} set P ⊆ ℕ^{ℕ} by a Σ_{3}^{0} set S ⊆ ℕ^{ℕ}. However, it fails for Π_{3}^{0} sets. For example, it fails badly for the Π_{3}^{0} set

ℕ^{ℕ} \ REC = {f | f is not recursive},

as shown by the Friedberg Splitting Theorem.

Definition 3.13.4 (weak equivalence).

1. For S ⊆ ℕ^{ℕ}, let Ŝ be the Turing upward closure of S, i.e.,

Ŝ = {g ∈ ℕ^{ℕ} | (∃f ∈ S) (f ≤_{T} g)} .

2. For S_{1}, S_{2} ⊆ ℕ^{ℕ}, we say that S_{1} and S_{2} are weakly equivalent, and write S_{1} ≡_{w} S_{2}, if and only if Ŝ_{1} = Ŝ_{2}.

Lemma 3.13.5. Given a Σ_{3}^{0} set S ⊆ ℕ^{ℕ}, we can find a Π_{1}^{0} set P ⊆ ℕ^{ℕ} such that P ≡_{w} S.

Proof. The proof uses the technique of Skolem functions. Since S is Σ_{3}^{0}, we have

S = {f ∈ ℕ^{ℕ} | ∃k ∀m ∃n R(f, k, m, n)}

where R is recursive. Put

P = {⟨k⟩^{⌢}(f ⊕ g) | ∀m R(f, k, m, g(m))} .

Here ⟨k⟩^{⌢}(f ⊕ g) is our notation for the unique h ∈ ℕ^{ℕ} such that h(0) = k and h(2m + 1) = f(m), and h(2m + 2) = g(m) for all m. Clearly P is Π_{1}^{0}. Moreover, if ⟨k⟩^{⌢}(f ⊕ g) ∈ P, then f ∈ S. Conversely, if f ∈ S, let k be such that ∀m ∃n R(f, k, m, n), and define g by putting g(m) = least n such that R(f, k, m, n). Then g ≤_{T} f, hence ⟨k⟩^{⌢}(f ⊕ g) ≤_{T} f and ∈ P.

Definition 3.13.6 (Π_{2}^{0} singletons). We say that f ∈ ℕ^{ℕ} is a Π_{2}^{0} singleton if the singleton set {f} is Π_{2}^{0}. This is equivalent to {f} being Σ_{3}^{0}.

Lemma 3.13.7. If f ≤_{T} 0′ then f is a Π_{2}^{0} singleton.

Proof. Assume f ≤_{T} 0′. By Corollary 3.11.17 f is Δ_{2}^{0}, i.e., the predicate D(n, m) ≡ f(n) = m is Δ_{2}^{0}. Hence

P = {g ∈ ℕ^{ℕ} | ∀n D(n, g(n))} = {g ∈ ℕ^{ℕ} | g = f} = {f}

is Π_{2}^{0} as a subset of ℕ^{ℕ}, i.e., f is a Π_{2}^{0} singleton.

Proposition 3.13.8. The Binns Splitting Theorem implies the Sacks Splitting Theorem.

Proof. Assume the Binns Splitting Theorem 3.13.2. We deduce the Sacks Splitting Theorem 3.12.4. Let A be a nonrecursive r.e. set, and let C be a nonrecursive set. Because A is r.e., we have A ≤_{T} 0′. If C ≤_{T} 0′ put S = {χ_{A}, χ_{C}}, otherwise put S = {χ_{A}}. By Lemma 3.13.7 S is Σ_{3}^{0}. By Lemma 3.13.5 let P ≡_{w} S be Π_{1}^{0}. Apply the Binns Splitting Theorem to A and P to obtain r.e. sets B_{1}, B_{2} such that B_{1} ∪ B_{2} = A and B_{1} ∩ B_{2} = ∅ and there is no f ∈ P such that f ≤_{T} B_{1} or f ≤_{T} B_{2}. Since P ≡_{w} S and B_{1}, B_{2} ≤_{T} 0′, we have A ≰_{T} B_{1}, A ≰_{T} B_{2}, C ≰_{T} B_{1}, C ≰_{T} B_{2}. The remaining conclusions of the Sacks Splitting Theorem now follow, in view of Lemma 3.13.1.

It remains to prove the Binns Splitting Theorem.

3.14 Finite Approximations

For most proofs involving degrees of unsolvability, it is necessary to consider finite approximations to oracle computations. Intuitively, if an oracle computation φ_{e}^{(1),f}(x) halts, then this computation can only use a finite amount of information from the oracle f, because it only performs a finite number of steps before halting. We state this insight formally as Proposition 3.14.3 below.

Notation 3.14.1 (finite sequences). We let Seq = ℕ^{<ℕ} denote the set of finite sequences of natural numbers. The length of σ ∈ Seq is denoted lh(σ). For f ∈ ℕ^{ℕ} and n ∈ ℕ we write

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

Thus lh(f[n]) = n. We write f ⊃ σ if f extends σ, i.e., if f[n] = σ where n = lh(σ). For σ, τ ∈ Seq we write σ ⊂ τ if σ is an initial segment of τ, i.e., lh(σ) < lh(τ) and σ(i) = τ(i) for all i < lh(σ).

Definition 3.14.2 (finite approximations). For e, s, x, y ∈ ℕ and σ ∈ Seq, we write

φ_{e,s}^{(1),σ}(x) ≃ y

if and only if e, x, y < s and for some (equivalently, all) f ∈ ℕ^{ℕ} extending σ, the oracle computation φ_{e}^{(1),f}(x) halts in fewer than s steps with output y, and during this computation, no oracle information from f is used except the part of f which is in σ. Proposition 3.14.3. We have:

1. φ_{e}^{(1),f}(x) ≃ y if and only if ∃n ∃s φ_{e,s}^{(1),f[n]}(x) ≃ y.

2. φ_{e}^{(1),f}(x) ≃ y if and only if ∃s φ_{e,s}^{(1),f[s]}(x) ≃ y.

3. If s ≤ t and σ ⊆ τ, then φ_{e,s}^{(1),σ}(x) ≃ y implies φ_{e,t}^{(1),τ} (x) ≃ y.

4. The 5-place relation φ_{e,s}^{(1),σ}(x) ≃ y is primitive recursive. Proof. Straightforward. Definition 3.14.4 (use functions).

1. u(f, e, x) = the supremum of all n such that the oracle information f(n) is used in the computation of φ_{e}^{(1),f}(x).

2. u(σ, e, x, s) = the supremum of all n < lh(σ) such that the oracle infor-

mation σ(n) is used in the first s steps of the computation of φ_{e,s}^{(1),σ}(x). Proposition 3.14.5.

1. u(f, e, x) = lim_{s} u(f[s], e, x, s).

2. The 4-place function u(σ, e, x, s) is primitive recursive. Proof. Straightforward. Definition 3.14.6 (trees). A tree is a set T ⊆ Seq such that σ ⊂ τ, τ ∈ T implies σ ∈ T. If T is a tree, a path through T is any f ∈ ℕ^{ℕ} such that f[n] ∈ T for all n. The set of all paths through T is denoted [T]. Proposition 3.14.7. Given a Π_{1}^{0} set P ⊆ ℕ^{ℕ}, we can find a primitive recursive tree T ⊆ Seq such that P = [T]. Proof. Let P ⊆ ℕ^{ℕ} be Π_{1}^{0}. Then P = {f | ∀n R(f, n)} where R is recursive. Let e be an index of χ_{R}, i.e., φ_{e}^{(1),f}(n) = χ_{R}(f, n) for all f ∈ ℕ^{ℕ} and n ∈ ℕ. Define

T = {σ ∈ Seq | ∀n < lh(σ) φ_{e,lh(σ)}^{(1),σ}(n) ≄ 0 } .

Then T is a primitive recursive tree, and P is the set of paths through T.

Notation 3.14.8. For A ⊆ ℕ we write

1. φ_{e}^{(1),A}(x) ≃ φ_{e}^{(1),χ_{A}}(x),

2. u(A, e, x) ≃ u(χ_{A}, e, x).

3. A[n] = χ_{A}[n],

3.15 Proof of the Binns Splitting Theorem

We now restate and prove the Binns Splitting Theorem 3.13.2.

Theorem 3.15.1. Let P ⊆ ℕ^{ℕ} be Π_{1}^{0} with P ∩ REC = ∅. For any r.e. set A we can find r.e. sets B_{1}, B_{2} such that A = B_{1} ∪ B_{2}, B_{1} ∩ B_{2} = ∅, and ¬ ∃f ∈ P (f ≤_{T} B_{1} ∨ f ≤_{T} B_{2}).

Proof. The general framework for the proof is as for the Friedberg Splitting Theorem. Let f be a one-to-one recursive function such that A = range(f). We write A^{s} = {f(0), …, f(s − 1)}. Our construction will be such that at stage s + 1 we have already defined B_{1}^{s} and B_{2}^{s} with A^{s} = B_{1}^{s} ∪ B_{2}^{s} and B_{1}^{s} ∩ B_{2}^{s} = ∅ and at this stage we decide whether to put f(s) into B_{1} or B_{2}.

Our requirements for the Binns Splitting Theorem are

R(e, i) : φ_{e}^{(1),B_{i}} ∉ P .

As usual, we define a priority ordering of the requirements by putting

(e′, i′) < (e, i)

if and only if 2e′+i′ < 2e+i. Our strategy for satisfying R(e, i) will be to preserve computations tending to put φ_{e}^{B_{i}} into P. This may seem counterintuitive, since R(e, i) requires that φ_{e}^{B_{i}} ∉ P. However, by preserving finite approximations to φ_{e}^{B_{i}}, we will eventually force φ_{e}^{B_{i}} to be either recursive or not total, hence ∉ P.

By Proposition 3.14.7 let T be a primitive recursive tree such that P = [T], the set of paths through T. Thus φ_{e}^{B_{i}} ∈ P if and only if ∀x φ_{e}^{(1),B_{i}}(x) ↓ and ∀y ⟨φ_{e}^{B_{i}}(x) | x < y⟩ ∈ T. Note also that if φ_{e}^{(1),B_{i}}(x) ↓ then φ_{e}^{(1),B_{i}}(x) = lim_{s} φ_{e,s}^{(1),B_{i}^{s}[s]}(x) and u(B_{i}, e, x) = lim_{s} u(B_{i}^{s}[s], e, x, s). We define the length function by

l(e, i, s) = sup {y | ∀x < y φ_{e,s}^{(1),B_{i}^{s}[s]}(x) ↓ and ⟨φ_{e,s}^{(1),B_{i}^{s}[s]}(x) | x < y⟩ ∈ T } .

We define the restraint function by

r(e, i, s) = sup {u(B_{i}^{s}[s], e, x, s) | x ≤ l(e, i, s) and φ_{e,s}^{(1),B_{i}^{s}[s]}(x) ↓} .

Roughly speaking, the length function l(e, i, s) measures the amount of agreement between φ_{e,s}^{(1),B_{i}^{s}[s]} and the tree T, while the restraint function r(e, i, s) tells us how much oracle information needs to be preserved, in order to keep this agreement, for the sake of requirement R(e, i).

Our construction is as follows.

Stage 0: B_{1}^{0} = B_{2}^{0} = ∅.

Stage s + 1: Let x = f(s). Choose the least (e, i) such that x ≤ r(e, i, s). If i = 1 or (e, i) is undefined, enumerate x into B_{2}. If i = 2, enumerate x into B_{1}.

This completes the construction.

The injury set I(e, i) is defined by

I(e, i) = {s + 1 | f(s) ∈ B_{i}^{s+1} \ B_{i}^{s} and f(s) ≤ r(e, i, s)} .

This is the set of stages at which R(e, i) is injured. By construction, if s + 1 ∈ I(e, i) then some (e′, i′) < (e, i) was chosen at stage s + 1. In other words, a requirement can be injured only for the sake of requirements of higher priority.

Lemma 3.15.2. The following hold for all e, i.

1. I(e, i) is finite.

2. φ_{e}^{(1),B_{i}} ∉ P.

3. r(e, i) = lim_{s} r(e, i, s) exists and is finite.

Proof. We prove 1, 2, and 3 by simultaneous induction on (e, i). Assume that 1, 2, and 3 hold for all (e′, i′) < (e, i). Put r = max{r(e′, i′) | (e′, i′) < (e, i)}. Let s_{1} be such that A^{s}[r+1] = A[r+1] and r(e′, i′, s) = r(e′, i′) for all (e′, i′) < (e, i) and s ≥ s_{1}. Then by construction I(e, i) ⊆ {0, …, s_{1} + 1}, so this injury set is finite. This proves 1.

To prove 2, assume for a contradiction that φ_{e}^{(1),B_{i}} ∈ P. Then, given y, we can effectively find s > s_{1} such that ∀x ≤ y φ_{e,s}^{(1),B_{i}^{s}[s]}(x) ↓ and

⟨φ_{e,s}^{(1),B_{i}^{s}[s]}(x) | x ≤ y⟩ ∈ T .

For all such s we have y ≤ l(e, i, s), hence u(B_{i}^{s}[s], e, y, s) ≤ r(e, i, s). More-

over s + 1 ∉ I(e, i), hence by construction φ_{e,s+1}^{(1),B_{i}^{s+1}[s+1]}(y) = φ_{e,s}^{(1),B_{i}^{s}[s]}(y). It

follows that φ_{e}^{(1),B_{i}}(y) = φ_{e,s}^{(1),B_{i}^{s}[s]}(y) for all such s. Thus φ_{e}^{(1),B_{i}} is recursive, contradicting our assumption that P ∩ REC = ∅. This proves 2.

To prove 3, consider the least y such that either φ_{e}^{(1),B_{i}}(y) ↑ or

⟨φ_{e}^{(1),B_{i}}(x) | x ≤ y⟩ ∉ T .

Choose s_{2} > s_{1} such that φ_{e,s}^{(1),B_{i}^{s}[s]}(x) ↓= φ_{e}^{(1),B_{i}}(x) for all x < y and all s ≥ s_{2}. Note that for all s ≥ s_{2} we have

⟨φ_{e,s}^{(1),B_{i}^{s}}(x) | x < y⟩ = ⟨φ_{e}^{(1),B_{i}}(x) | x < y⟩ ∈ T ,

hence l(e, i, s) ≥ y and r(e, i, s) ≥ u(B_{i}^{s}[s], e, x, s) for all x < y.

Case 1: φ_{e,s}^{(1),B_{i}^{s}[s]}(y) ↑ for all s ≥ s_{2}. Then for all s ≥ s_{2} we have l(e, i, s) = y and r(e, i, s + 1) = r(e, i, s).

Case 2: φ_{e,s}^{(1),B_{i}^{s}[s]}(y) ↓ for some s ≥ s_{2}. Then for any such s we have

r(e, i, s) ≥ u(B_{i}^{s}[s], e, y, s) ,

hence by construction φ_{e,s+1}^{(1),B_{i}^{s+1}[s+1]}(y) = φ_{e,s}^{(1),B_{i}^{s}[s]}(y). It follows that for all

such s we have φ_{e}^{(1),B_{i}}(y) = φ_{e,s}^{(1),B_{i}^{s}[s]}(y), hence

⟨φ_{e,s}^{(1),B_{i}^{s}[s]}(x) | x ≤ y⟩ ∉ T ,

hence again l(e, i, s) = y and r(e, i, s + 1) = r(e, i, s).

In either case we have r(e, i, s+1) = r(e, i, s) for all sufficiently large s. Thus 3 holds, and our lemma is proved.

This completes the proof of the Binns Splitting Theorem.

Exercise 3.15.3. A Turing degree b is said to be low if b′ = 0′. Prove that the r.e. Turing degrees b_{1} = deg_{T} (B_{1}) and b_{2} = deg_{T} (B_{2}) constructed in the proof of the Binns Splitting Theorem 3.15.1 are low.

3.16 Some Additional Results

In this section we mention some additional results and problems concerning r.e. Turing degrees.

More to come ......

Randomness

It seems appropriate to call an infinite sequence of 0’s and 1’s “random” if it is the result of an infinite sequence of independent coin tosses using a fair or unbiased coin. The purpose of this chapter is to define and discuss a mathematically rigorous, recursion-theoretic concept of randomness which corresponds to this intuitive, non-mathematical notion. References for this material are Downey/Hirschfeldt [7] and Simpson [16].

4.1 Measure-Theoretic Preliminaries

In this section we present the measure-theoretic background material which we shall need.

Definition 4.1.1 (the Cantor space).

1. The Cantor space is the set

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

Note that each X ∈ 2^{ℕ} is an infinite sequence of 0’s and 1’s, namely X = ⟨X(0), X(1), …, X(n), …⟩.

2. We write Seq_{2} = 2^{<ℕ} = the set of finite sequences of 0’s and 1’s. According to our Notation 3.14.1, for all σ ∈ Seq_{2} and X ∈ 2^{ℕ} we have X ⊃ σ if and only if X[lh(σ)] = σ. For σ ∈ Seq_{2} we put

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

We view the Cantor space 2^{ℕ} as a topological space with basic open sets N_{σ}, σ ∈ Seq_{2}. Thus U ⊆ 2^{ℕ} is said to be open if there exists G ⊆ Seq_{2} such that U = ⋃_{σ∈G} N_{σ}.

Remark 4.1.2. It is easy to see that the above-defined topology on the Cantor space is the same as the product topology on 2^{ℕ} = ∏_{n∈ℕ}{0, 1}, where the twopoint space {0, 1} has the discrete topology. Therefore, by Tychonoff’s Theorem, 2^{ℕ} is compact.

Remark 4.1.3. The points of 2^{ℕ} are just the infinite sequences of 0’s and 1’s. Eventually we are going to define what it means for a point of 2^{ℕ} to be random. The standard method of formalizing informal notions such as independence and probability is by means of measure theory, as we shall now explain.

Definition 4.1.4 (probability measures). Let I be a nonempty set. A σalgebra on I is a set S ⊆ P (I), the powerset of I, such that ∅ ∈ S and I ∈ S and S is closed under the operations of countable union, countable intersection, and complementation. A probability measure on I is a function μ : S → [0, 1], where S is a σ-algebra on I, such that μ(∅) = 0 and μ(I) = 1 and

μ( ⋃_{n=1}^{∞} S_{n}) = ∑_{n=1}^{∞} μ(S_{n})

for all sequences of pairwise disjoint sets S_{1}, S_{2}, … ∈ S. This last property is known as countable additivity. A probability space is an ordered triple (I, S, μ) as above. For S ∈ S, the measure of S is the real number μ(S).

Remark 4.1.5. Let (I, S, μ) be a probability space. A set S ⊆ I such that S ∈ S is called an event. For S ∈ S, the measure of S is thought of as the probability of the event S, i.e., the likelihood that a “random” or “randomly chosen” element of I will belong to S. Note that we have not yet rigorously defined the concept “random.”

Definition 4.1.6 (Borel sets, regularity).

1. Let I be a topological space. The Borel sets of I are the smallest σ-algebra on I containing the open sets of I. A Borel probability measure on I is a probability measure μ on I such that the domain of μ consists of the Borel sets of I.

2. Let (I, S, μ) be a probability space such that I is also a topological space, and S includes the Borel sets of I. We say that μ is regular (with respect to the given topology on I) if, for all S ∈ S,

μ(S) = inf{μ(U) | S ⊆ U and U is open} .

Theorem 4.1.7 (the fair coin measure). There exists a Borel probability measure μ on 2^{ℕ} such that, for all σ ∈ Seq_{2}, μ(N_{σ}) = 1/2^{lh(σ)}. Note that μ is unique with these properties. We refer to μ as the fair coin measure on 2^{ℕ}, because it arises by viewing X ∈ 2^{ℕ} as the result of a sequence of independent tosses of a fair coin. It can be shown that μ is regular.

Proof. We omit the proof. See any measure theory textbook.

Definition 4.1.8 (null sets). In any probability space, a null set is any subset of a set of measure 0. Thus T ⊆ I is null if and only if T ⊆ S for some S ∈ S such that μ(S) = 0. Note also that, if μ is regular, then T is null if and only if ∀ϵ > 0 ∃ open set U such that T ⊆ U and μ(U) ≤ ϵ. Equivalently, T ⊆ ⋂_{n} U_{n} where each U_{n} is open and μ(U_{n}) ≤ 1/2^{n}.

4.2 Effective Randomness

In this section we define what it means for a point X ∈ 2^{ℕ} to be “effectively random.” In this context, “effectively” means “recursion-theoretically.”

We first consider what it means for a subset of 2^{ℕ} to be “effectively open.” From now on, let μ be the fair coin measure on 2^{ℕ}.

Definition 4.2.1. A set U ⊆ 2^{ℕ} is said to be Σ_{1}^{0} if U = {X ∈ 2^{ℕ} | ∃k R(X, k)} where R is recursive. A sequence of sets U_{n} ⊆ 2^{ℕ}, n ∈ ℕ, is said to be uniformly Σ_{1}^{0} if U_{n} = {X ∈ 2^{ℕ} | ∃k R(X, k, n)} for some fixed recursive predicate R.

Proposition 4.2.2 (effective openness). U ⊆ 2^{ℕ} is Σ_{1}^{0} if and only if U is effectively open, i.e., U = ⋃_{σ∈G} N_{σ} for some recursively enumerable G ⊆ Seq_{2}. Moreover, we may assume that G is primitive recursive and pairwise incompatible, i.e., there are no σ, τ ∈ G such that σ ⊂ τ. A similar result holds for uniformly Σ_{1}^{0} sequences of sets of U_{n} ⊆ 2^{ℕ}, n ∈ ℕ.

Proof. Assume that U is Σ_{1}^{0}, say U = {X ∈ 2^{ℕ} | ∃k R(X, k)} where R is recursive. Let e be such that φ_{e}^{(1),X}(0) ≃ least k such that R(X, k). Then

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

A e with this last property is called an index of U, or a Σ_{1}^{0} index of U. Thus we have a uniform Σ_{1}^{0} indexing of all Σ_{1}^{0} subsets of 2^{ℕ}.

We now use the idea of finite approximations from Section 3.14. Given an index e of U ⊆ 2^{ℕ}, define G ⊆ Seq_{2} by

G = G_{e} = {σ ∈ Seq_{2} | φ_{e}^{(1),σ}(0) ↓ ∧ ¬ ∃τ ⊂ σ φ_{e}^{(1),τ} (0) ↓ } .

Then U = ⋃_{σ∈G} N_{σ} and G is primitive recursive and pairwise incompatible. Conversely, if U = ⋃_{σ∈G} N_{σ} where G is r.e., then clearly U is Σ_{1}^{0}. The uniform version is proved similarly.

Remark 4.2.3. As usual, we relativize as follows. Given an oracle f ∈ ℕ^{ℕ}, we say that U ⊆ 2^{ℕ} is Σ_{1}^{0,f} if U = {X ∈ 2^{ℕ} | ∃k R(f ⊕ X, k)} where R is recursive. It can be shown that U ⊆ 2^{ℕ} is open if and only if U is Σ_{1}^{0,f} for some f. Thus we see a close analogy between open sets and r.e. sets. This analogy can be pushed much farther.

The following is a recursion-theoretic analog of Definition 4.1.8.

Definition 4.2.4 (effectively null sets). A set T ⊆ 2^{ℕ} is said to be effectively null if there exists a uniformly Σ_{1}^{0} sequence of sets U_{n} ⊆ 2^{ℕ}, n ∈ ℕ, such that T ⊆ ⋂_{n} U_{n} and μ(U_{n}) ≤ 1/2^{n} for all n.

We are now ready to define our concept of recursion-theoretic randomness.

Definition 4.2.5 (randomness). A point X ∈ 2^{ℕ} is said to be effectively random, or just random, if X does not belong to any effectively null set. An equivalent condition is that the singleton set {X} is not effectively null.

Corollary 4.2.6. μ({X ∈ 2^{ℕ} | X is random}) = 1.

Proof. There are only countably many effectively null sets. By countable additivity, their union is null. The corollary is a restatement of this.

Remark 4.2.7. The great mathematician Kolmogorov invented probability theory. He also invented a theory of algorithmic randomness, known as Kolmogorov complexity. Our concept of randomness was originally formulated in 1966 by Martin-Löf, a former Ph. D. student of Kolmogorov. It can be shown that this concept of randomness is closely related to Kolmogorov complexity.

Proposition 4.2.8. If X ∈ 2^{ℕ} is recursive, then X is not random.

Proof. If X is recursive, then the sets U_{n} = N_{X[n]} are uniformly Σ_{1}^{0} of measure 1/2^{n}. Hence {X} = ⋂_{n} U_{n} is effectively null, hence X is not random.

Proposition 4.2.9. If a Π_{1}^{0} set P ⊆ 2^{ℕ} is of measure 0, then it is effectively null. It follows that no X ∈ P is random.

Proof. Let e be a Σ_{1}^{0} index of 2^{ℕ} \ P. Then P = {X ∈ 2^{ℕ} | φ_{e}^{(1),X}(0) ↑}. Put V_{s} = {X ∈ 2^{ℕ} | φ_{e,s}^{(1),X[s]}(0) ↑ }. Clearly the sets V_{s}, s ∈ ℕ are uniformly Σ_{1}^{0}, and V_{0} ⊇ V_{1} ⊇ ⋯ ⊇ V_{s} ⊇ ⋯ and P = ⋂_{s} V_{s}. Hence by countable additivity lim_{s} μ(V_{s}) = μ(P) = 0. The function s ↦ μ(V_{s}) is primitive recursive, so let h(n) = the least s > n such that μ(V_{s}) ≤ 1/2^{n}. Then h is recursive, hence the sets U_{n} = V_{h(n)}, n ∈ ℕ, are uniformly Σ_{1}^{0}. Moreover μ(U_{n}) ≤ 1/2^{n} and P = ⋂_{n} U_{n}, so P is effectively null.

Remark 4.2.10. Let us say that X ∈ 2^{ℕ} is weakly random if X does not belong to any Π_{1}^{0} subset of 2^{ℕ} of measure 0. We have just shown that if X is random then X is weakly random. The converse does not hold. For example, any Cohen generic X ∈ 2^{ℕ} is weakly random but not random.

We pause to mention the following useful property of random sequences. Note that this property is in fact equivalent to randomness.

Theorem 4.2.11 (Solovay). Assume that A ∈ 2^{ℕ} is random. If U_{n} ⊆ 2^{ℕ}, n ∈ ℕ, are uniformly Σ_{1}^{0} such that

∑_{n=0}^{∞} μ(U_{n}) < ∞ ,

then {n ∈ ℕ | A ∈ U_{n}} is finite.

Proof. Let c be such that ∑_{n=0}^{∞} μ(U_{n}) ≤ c < ∞. For each k ≥ 1 put

W_{k} = {X ∈ 2^{ℕ} | ∃^{≥k} n (X ∈ U_{n})} .

Note that the sets W_{k}, k ≥ 1, are uniformly Σ_{1}^{0}. We claim that μ(W_{k}) ≤ c/k. To see this, write

W_{k,s} = {X ∈ 2^{ℕ} | (∃^{≥k} n ≤ s) (X ∈ U_{n})}

and note that W_{k} = ⋃_{s} W_{k,s}. We have

c ≥ ∑_{n=0}^{∞} μ(U_{n}) ≥ ∑_{n=0}^{s} μ(U_{n})

= ∑_{n=0}^{s} ∫_{X} U_{n}(X) dX = ∫_{X} ∑_{n=0}^{s} U_{n}(X) dX

≥ ∫_{X} k W_{k,s}(X) dX = k μ(W_{k,s})

so μ(W_{k,s}) ≤ c/k. It follows that μ(W_{k}) = sup_{s} μ(W_{k,s}) ≤ c/k as claimed. Let h be primitive recursive such that h(n) ≥ 2^{n}c for all n. Then W_{h(n)} is uniformly Σ_{1}^{0} of measure ≤ 1/2^{n}. Since A is random, we have A ∉ ⋂_{n} W_{h(n)} = ⋂_{k} W_{k}, so A ∉ W_{k} for some k, i.e., ∃^{<k} n A ∈ U_{n}. Thus {n | A ∈ U_{n}} is finite.

We end this section with the following interesting result.

Theorem 4.2.12 (Martin-Löf). The union of all effectively null sets is effectively null.

Corollary 4.2.13. We can write {X ∈ 2^{ℕ} | X is not random} = ⋂_{n} U_{n} where U_{n} is uniformly Σ_{1}^{0} and μ(U_{n}) ≤ 1/2^{n} for all n.

Proof. Put S = {X ∈ 2^{ℕ} | X is not random}. By the definition of randomness, S is the union of all effectively null sets. It follows by Theorem 4.2.12 that S itself is effectively null. Thus S ⊆ ⋂_{n} U_{n} where U_{n} is uniformly Σ_{1}^{0} and μ(U_{n}) ≤ 1/2^{n} for all n. But clearly ⋂_{n} U_{n} itself is effectively null, hence S = ⋂_{n} U_{n}.

Remark 4.2.14 (tests for randomness, effectively null G_{δ} sets). The following terminology is sometimes used. Define a test or test for randomness to be an effectively null G_{δ} set, i.e., a set of the form ⋂_{n} U_{n} where U_{n} is uniformly Σ_{1}^{0} and μ(U_{n}) ≤ 1/2^{n} for all n. We say that X ∈ 2^{ℕ} passes the test if X ∉ ⋂_{n} U_{n}. By the definition of randomness, X is random if and only if X passes all tests. Corollary 4.2.13 tells us that there is a universal test, i.e., a test such that if X passes that test then it passes all tests and is therefore random.

We may reformulate Corollary 4.2.13 by saying that the set {X ∈ 2^{ℕ} | X is not random} is effectively null G_{δ}. Moreover, it is the largest effectively null G_{δ} set, which is the same as the largest effectively null set.

Corollary 4.2.15. {X ∈ 2^{ℕ} | X is random} is Σ_{2}^{0}.

Proof. By the definition of the arithmetical hierarchy, S ⊆ 2^{ℕ} is Π_{2}^{0} if and only if S = ⋂_{n} U_{n} where U_{n} is uniformly Σ_{1}^{0}. In particular, by Corollary 4.2.13, {X ∈ 2^{ℕ} | X is not random} is Π_{2}^{0}, hence {X ∈ 2^{ℕ} | X is random} is Σ_{2}^{0}.

Corollary 4.2.16. For all ϵ > 0 we can find a Π_{1}^{0} set P ⊆ 2^{ℕ} such that ∀X (X ∈ P ⇒ X is random) and μ(P) > 1 − ϵ.

Proof. Put P = 2^{ℕ} \ U_{n}, where U_{n} is as in Corollary 4.2.13, and ϵ > 1/2^{n}.

Remark 4.2.17. We cannot improve Corollary 4.2.16 to say that there exists a Π_{1}^{0} set P ⊆ 2^{ℕ} such that ∀X (X ∈ P ⇒ X is random) and μ(P) = 1. This is obvious, because any nonempty Σ_{1}^{0} subset of 2^{ℕ} is of positive measure.

We now prove Martin-Löf’s Theorem 4.2.12.

Notation 4.2.18 (the tilde notation). Recall from the proof of Proposition 4.2.2 that for every Σ_{1}^{0} set U ⊆ 2^{ℕ} there exists an index e such that

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

Moreover, the sets U_{e} for all e ∈ ℕ are uniformly Σ_{1}^{0}. We put

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

and note that U_{e} = ⋃_{s} U_{e,s} and U_{e,0} ⊆ U_{e,1} ⊆ ⋯ ⊆ U_{e,s} ⊆ · · ·. Note also that μ(U_{e,s}) is a rational number, and the function (e, s) ↦ μ(U_{e,s}) is primitive recursive. Now, given an index e and a rational number r, define

Ũ = Ũ_{r} = Ũ_{e,r} = {X | ∃s (X ∈ U_{e,s} ∧ μ(U_{e,s}) ≤ r)} .

Note that Ũ_{e,r} is uniformly Σ_{1}^{0} for all e ∈ ℕ and all rational r. The following properties of Ũ_{e,r} are easily verified.

1. Ũ_{e,r} ⊆ U_{e}.

2. μ \binom{}{U_{e,r}} ≤ r.

3. If μ(U_{e}) ≤ r then Ũ_{e,r} = U_{e}.

We may describe Ũ_{e,r} as “U_{e} enumerated so long as its measure is ≤ r,” or “the Σ_{1}^{0} subset of 2^{ℕ} with index e, enumerated so long as its measure is ≤ r.”

Proof of Theorem 4.2.12. Define Σ_{1}^{0} sets V_{e} ⊆ 2^{ℕ}, e ∈ ℕ, as follows. Given e, compute φ_{e}^{(1)}(e). If φ_{e}^{(1)}(e) ↑, let V_{e} = ∅. If φ_{e}^{(1)}(e) ≃ i, let V_{e} = the Σ_{1}^{0} subset of 2^{ℕ} with index i enumerated so long as its measure is ≤ 1/2^{e}. Note that V_{e} is uniformly Σ_{1}^{0} and μ(V_{e}) ≤ 1/2^{e}. Define S = ⋂_{n} U_{n} where U_{n} = ⋃_{e=n+1}^{∞} V_{e}. Note that U_{n} is uniformly Σ_{1}^{0}. Moreover, μ(U_{n}) ≤ ∑_{e=n+1}^{∞} μ(V_{e}) ≤ ∑_{e=n+1}^{∞} 1/2^{e} = 1/2^{n}, so S is effectively null. We claim that S ⊇ T for all effectively null sets T. To see this, suppose T is effectively null, say T ⊆ ⋂_{n} W_{n} where W_{n} ⊆ 2^{ℕ} is uniformly Σ_{1}^{0} and μ(W_{n}) ≤ 1/2^{n}. By the Parametrization Theorem, let h be a primitive recursive function such that, for all n, h(n) is a Σ_{1}^{0} index of W_{n}. Let e be an index of h qua recursive function, i.e., let e be such that φ_{e}^{(1)}(n) ≃ h(n) for all n. Then φ_{e}^{(1)}(e) ≃ h(e) is a Σ_{1}^{0} index of W_{e}. Since μ(W_{e}) ≤ 1/2^{e}, it follows that V_{e} = W_{e}, hence T ⊆ V_{e}. Since h has infinitely many indices qua recursive function, we see that T ⊆ V_{e} for infinitely many e. It follows that T ⊆ U_{n} for all n, i.e., T ⊆ S. This completes the proof.

4.3 Randomness Relative to an Oracle

In this section we relativize our concept of randomness to a Turing oracle, and we prove some theorems concerning the relativized concept.

Definition 4.3.1. Let f ∈ ℕ^{ℕ} be an oracle. We say that A ∈ 2^{ℕ} is f-random, or random over f, or random relative to f, if there is no uniformly Σ_{1}^{0,f} sequence of sets U_{n}^{f} ⊆ 2^{ℕ}, n ∈ ℕ, such that A ∈ ⋂_{n} U_{n}^{f} and μ(U_{n}^{f}) ≤ 1/2^{n} for all n.

Remark 4.3.2. Recall that if A is recursive then A is not random. This relativizes to the following statement: if A ≤_{T} f then A is not f-random.

Notation 4.3.3. For A, B ∈ 2^{ℕ} recall that A ⊕ B ∈ 2^{ℕ} is defined by

(A ⊕ B)(2n) = A(n) , (A ⊕ B)(2n + 1) = B(n) ,

for all n. Thus 2^{ℕ} × 2^{ℕ} ≅ 2^{ℕ} via the mapping (A, B) ↦ A ⊕ B.

Theorem 4.3.4. If A ⊕ B is random, then A is random over B, and B is random over A.

Proof. Suppose B is not random over A, say B ∈ ⋂_{n} V_{n}^{A} where V_{n}^{A} is uniformly Σ_{1}^{0,A} of measure ≤ 1/2^{n}. For an arbitrary X ∈ 2^{ℕ}, let V_{n}^{X} be V_{n}^{A} with A replaced by X. (More precisely, let V_{n}^{X} be the Σ_{1}^{0,X} set with Σ_{1}^{0,X} index h(n) where h is a fixed primitive recursive function such that V_{n}^{A} is the Σ_{1}^{0,A} set with Σ_{1}^{0,A} index h(n).) Define

W_{n} = {X ⊕ Y | X ∈ 2^{ℕ} and Y ∈ Ṽ_{n}^{X}}

where Ṽ_{n}^{X} is V_{n}^{X} enumerated so long as its measure is ≤ 1/2^{n}. (See our Notation 4.2.18.) Note that W_{n} is uniformly Σ_{1}^{0}. By Fubini’s Theorem, μ(W_{n}) ≤ 1/2^{n}. Since Ṽ_{n}^{A} = V_{n}^{A} and B ∈ V_{n}^{A}, it follows that A ⊕ B ∈ W_{n} for all n. Thus A ⊕ B is not random. We have now proved that if A ⊕ B is random then B is random over A. The proof that A is random over B is similar.

Corollary 4.3.5. If A ⊕ B is random, then A ≰_{T} B and B ≰_{T} A.

Corollary 4.3.6. If A ⊕ B is random, then A and B are random.

The preceding theorem has a converse due to van Lambalgen 1987.

Theorem 4.3.7 (van Lambalgen). If A is random, and if B is random over A, then A ⊕ B is random.

Proof. Suppose A⊕B is not random, say A⊕B ∈ ⋂_{n} W_{n} where W_{n} is uniformly Σ_{1}^{0} and μ(W_{n}) ≤ 1/2^{n}. By passing to a subsequence, we may assume that μ(W_{n}) ≤ 1/2^{2n}. For all X ∈ 2^{ℕ} and n ∈ ℕ put

V_{n}^{X} = {Y ∈ 2^{ℕ} | X ⊕ Y ∈ W_{n}}

and note that V_{n}^{X} is uniformly Σ_{1}^{0,X}. For all n ∈ ℕ put

U_{n} = \{X ∈ 2^{ℕ} | μ(V_{n}^{X}) > \frac{1}{2^{n}} \}

and note that U_{n} is uniformly Σ_{1}^{0}. By Fubini’s Theorem we have

μ(W_{n}) = ∫_{X} ∫_{Y} W_{n}(X ⊕ Y) dY dX = ∫_{X} ∫_{Y} V_{n}^{X}(Y) dY dX

≥ ∫_{X} U_{n}(X) V_{n}^{X}(Y) dY dX ≥ ∫_{X} U_{n}(X) \frac{1}{2^{n}} dX

= \frac{1}{2^{n}} ∫_{X} U_{n}(X) dX = \frac{1}{2^{n}} μ(U_{n}) ,

hence μ(U_{n}) ≤ 2^{n}μ(W_{n}) ≤ 2^{n}/2^{2n} = 1/2^{n}. Since μ(U_{n}) ≤ 1/2^{n} and A is random, it follows by Solovay’s Theorem 4.2.11 that {n | A ∈ U_{n}} is finite. Thus μ(V_{n}^{A}) ≤ 1/2^{n} for all but finitely many n. Moreover V_{n}^{A} is uniformly Σ_{1}^{0,A} and B ∈ ⋂_{n} V_{n}^{A}. Thus B is not random over A. This proves the theorem.

The following result is due to Joseph Miller 2004.

Theorem 4.3.8 (J. Miller). Assume that A is random, A ≤_{T} B, and B is random over C. Then A is random over C.

Proof. Fix e such that A = φ_{e}^{(1),B}. For each σ ∈ Seq_{2} put

V_{σ} = {Y ∈ 2^{ℕ} | σ ⊆ φ_{e}^{(1),Y} } .

Note that B ∈ V_{A[n]} for all n. Moreover, V_{σ} is uniformly Σ_{1}^{0}, and σ | τ ⇒ V_{σ} ∩ V_{τ} = ∅.

Lemma 4.3.9. There is a constant c such that μ(V_{A[n]}) ≤ c/2^{n} for all n.

Proof. For each rational number c put

U_{c} = \{X ∈ 2^{ℕ} | ∃n μ(V_{X[n]}) > \frac{c}{2^{n}} \} .

Note that U_{c} is uniformly Σ_{1}^{0}. Let G_{c} be the set of σ ∈ Seq_{2} such that μ(V_{σ}) > c/2^{lh(σ)} and σ is minimal with this property. Thus U_{c} = ⋃_{σ∈G_{c}} N_{σ}. Since G_{c} is pairwise incompatible, the sets V_{σ}, σ ∈ G_{c}, are pairwise disjoint. We have μ(U_{c}) = ∑_{σ∈G_{c}} 1/2^{lh(σ)}, hence

1 = μ(2^{ℕ}) ≥ μ( ⋃_{σ∈G_{c}} V_{σ}) = ∑_{σ∈G_{c}} μ(V_{σ}) ≥ ∑_{σ∈G_{c}} \frac{c}{2^{lh(σ)}} = c μ(U_{c}) .

Thus μ(U_{c}) ≤ 1/c for all c. In particular, μ(U_{2^{n}}) ≤ 1/2^{n} for all n. Since A is random, it follows that A ∉ U_{2^{n}} for some n, hence A ∉ U_{c} for some c. The lemma follows.

Let c be a rational number as in the lemma. Let Ṽ_{σ} = V_{σ} enumerated so long as its measure is ≤ c/2^{lh(σ)}. Then Ṽ_{σ} is uniformly Σ_{1}^{0} of measure ≤ c/2^{lh(σ)}. By the lemma we have Ṽ_{A[n]} = V_{A[n]} for all n.

Now suppose A is not random over C, say A ∈ ⋂_{i} U_{i}^{C} where U_{i}^{C} is uniformly Σ_{1}^{0} and μ(U_{i}^{C}) ≤ 1/2^{i}. As in the proof of Proposition 4.2.2, let G_{i}^{C} ⊆ Seq_{2} be uniformly Σ_{1}^{0,C} and pairwise incompatible such that U_{i}^{C} = ⋃_{σ∈G_{i}^{C}} N_{σ}. Put

W_{i}^{C} = ⋃_{σ∈G_{i}^{C}} Ṽ_{σ}. Then W_{i}^{C} is uniformly Σ_{1}^{0,C} and

μ(W_{i}^{C}) = ∑_{σ∈G_{i}^{C}} μ(Ṽ_{σ}) ≤ ∑_{σ∈G_{i}^{C}} \frac{c}{2^{lh(σ)}} = c μ(U_{i}^{C}) ≤ \frac{c}{2^{i}} .

Moreover, since A ∈ U_{i}^{C} and B ∈ V_{A[n]} = Ṽ_{A[n]} for all n, we have B ∈ W_{i}^{C} for all i. Thus B is not random over C. This proves the theorem.

Definition 4.3.10 (n-randomness). For n ≥ 1, A ∈ 2^{ℕ} is said to be n-random if A is random relative to 0^{(n−1)}. Thus 1-randomness is just randomness, while 2-randomness is randomness relative to the Halting Problem, etc.

Corollary 4.3.11. Assume A is random, A ≤_{T} B, and B is n-random. Then A is n-random.

Proof. This is a special case of Theorem 4.3.8.

Definition 4.3.12. A ∈ 2^{ℕ} is said to be arithmetically random if A is n-random for all n ≥ 1.

Corollary 4.3.13. If A is random, A ≤_{T} B, and B is arithmetically random, then A is arithmetically random.

Bibliography

[1] Stål Aanderaa. A Trachtenbrot inseparability theorem for groups (abstract). Bulletin of Symbolic Logic, 1:117, 1995.

[2] Stål Aanderaa and Daniel E. Cohen. Modular machines I, II. In [3], pages 1–18, 19–28, 1980.

[3] S. I. Adian, W. W. Boone, and G. Higman, editors. Word Problems II: The Oxford Book. Studies in Logic and the Foundations of Mathematics. North-Holland, 1980. X + 578 pages.

[4] G. Baumslag and C. F. Miller, editors. Algorithms and Classification in Combinatorial Group Theory. Mathematical Sciences Research Institute Publications. Springer-Verlag, 1992. VII + 232 pages.

[5] Martin Davis. Hilbert’s Tenth Problem is unsolvable. American Mathematical Monthly, 80:233–269, 1973.

[6] Martin Davis. Computability and Unsolvability. Dover Publications, New York, 1982. XXV + 248 pages.

[7] Rodney G. Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity. 2004. Preprint, May 22, 2004, 305 pages, in preparation.

[8] Charles F. Miller III. Decision problems for groups: survey and reflections. In [4], pages 1–59, 1992.

[9] O. G. Kharlampovich. The universal theory of the class of finite nilpotent groups is undecidable. Mathematical Notes, 33:254–263, 1983. The original Russian version appeared in Mat. Zametki 33, 1983, pp. 499–516.

[10] Alexander Nabutovsky. Einstein structures: existence versus uniqueness. Geometric and Functional Analysis, 5:76–91, 1995.

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

[12] Joseph J. Rotman. The Theory of Groups. Allyn and Bacon, second edition, 1973. X + 342 pages.

[13] Joseph R. Shoenfield. Mathematical Logic. Addison–Wesley, 1967. VII + 344 pages.

[14] Stephen G. Simpson. Foundations of Mathematics. Unpublished lecture notes, Department of Mathematics, Pennsylvania State University, 86 pages, 1995–2004.

[15] Stephen G. Simpson. Topics in Mathematical Logic: Spring 2004. Unpublished lecture notes, Department of Mathematics, Pennsylvania State University, 105 pages, 2004.

[16] Stephen G. Simpson. Mass problems and randomness. Bulletin of Symbolic Logic, 11:1–27, 2005.

[17] A. M. Slobodskoi. Undecidability of the universal theory of finite groups. Algebra and Logic, 20:139–156, 1981. The original Russian version appeared in Algebra i Logika 20, 1981, pp. 207–230, 251.

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