Implicit definability in arithmetic^{∗}

Stephen G. Simpson Department of Mathematics Pennsylvania State University University Park, PA 16802, USA http://www.math.psu.edu/simpson simpson@math.psu.edu

First draft: November 8, 2012 This draft: July 31, 2016

Published in Notre Dame Journal of Formal Logic, 57, 2016, 329–339.

Abstract

We consider implicit definability over the natural number system ℕ, +, ×, =. We present a new proof of two theorems of Leo Harrington. The first theorem says that there exist implicitly definable subsets of ℕ which are not explicitly definable from each other. The second theorem says that there exists a subset of ℕ which is not implicitly definable but belongs to a countable, explicitly definable set of subsets of ℕ. Previous proofs of these theorems have used finite- or infinite-injury priority constructions. Our new proof is easier in that it uses only a non-priority oracle construction, adapted from the standard proof of the Friedberg Jump Theorem.

Keywords: arithmetical hierarchy, arithmetical singletons, implicit definability, hyperarithmetical sets, Turing jump.

2010 Mathematics Subject Classification: Primary 03D55, Secondary 03D30, 03D28, 03C40, 03D80.

∗This paper is based on a two-hour tutorial of the same title given February 22–23, 2013 at the Sendai Logic School, Tohoku University, Sendai, Japan. The author is grateful to Professor Kazuyuki Tanaka for organizing the school and inviting him to Sendai. The author’s research is supported by the Eberly College of Science at the Pennsylvania State University, and by Simons Foundation Collaboration Grant 276282.

Contents

Abstract  1
1 Introduction  2
2 Recursion-theoretic background  4
3 A rudimentary version of Harrington’s theorems  5
4 Proof of Harrington’s theorems  9
References  13

1 Introduction

Definitions. Let ℕ = {0, 1, 2, …, n, …} = the set of all natural numbers. Let Pow(ℕ) be the powerset of ℕ, i.e., the set of all subsets of ℕ. A set X ∈ Pow(ℕ) is said to be arithmetical if it is explicitly definable over the natural number system ℕ, +, ×, =. In other words,

X = {n ∈ ℕ | (ℕ, +, ×, =) ⊧ Φ(n)}

for some first-order formula Φ(n) in the language +, ×, =. Given two sets X, Y ∈ Pow(ℕ), we say that X is arithmetical in Y if X is explicitly definable from Y, i.e.,

X = {n ∈ ℕ | (ℕ, +, ×, Y, =) ⊧ Φ(n)}

for some first-order formula Φ(n) in the language +, ×, Y, =. We say that X and Y are arithmetically incomparable if neither is arithmetical in the other. A set of sets S ⊆ Pow(ℕ) is said to be arithmetical if it is explicitly definable, i.e.,

S = {X ∈ Pow(ℕ) | (ℕ, +, ×, X, =) ⊧ Φ}

for some first-order sentence Φ in the language +, ×, X, =. A set X ∈ Pow(ℕ) is called an arithmetical singleton or implicitly arithmetical if the singleton set {X} is arithmetical.

Remark 1. The purpose of this paper is to present a new proof of two theorems of Harrington [6, 7] concerning implicit definability over the natural number system ℕ, +, ×, =. The two theorems read as follows.

1. There exist arithmetical singletons X, Y ∈ Pow(ℕ) which are arithmetically incomparable. (See Theorem 4.4 below.)

2. There exists a set Z ∈ Pow(ℕ) which belongs to a countable arithmetical set of sets S ⊆ Pow(ℕ) but is not an arithmetical singleton. (See Theorem 4.5 below.)

We feel that these two theorems deserve to be better known, because they embody significant insight concerning implicit definability in arithmetic.

Remark 2. Before Harrington’s work, some early theorems concerning implicit definability in arithmetic were as follows.

1. There exists X ∈ Pow(ℕ) which is implicitly arithmetical but not arithmetical. (Namely, let X = 0^{(ω)} = the Tarski truth set for ℕ, +, ×, =. See Rogers [11, Theorems 14-X and 15-XII].)

2. There exist X, Y ∈ Pow(ℕ) such that the pair X ⊕ Y is implicitly arithmetical but neither X nor Y is implicitly arithmetical. (Namely, let X and Y be Cohen generic over ℕ, +, ×, = such that X ⊕ Y and 0^{(ω)} are arithmetical in each other. See Feferman [3] or Rogers [11, Exercise 16-72].)

3. Each arithmetical singleton is arithmetical in 0^{(α)} for some recursive ordinal α, and each such 0^{(α)} is itself an arithmetical singleton. (See for instance Sacks [13, Chapter II].)

4. Every nonempty countable arithmetical set of sets S ⊆ Pow(ℕ) contains an arithmetical singleton. (This result is due to H. Tanaka [15].)

Remark 3. Harrington’s original proof [6] of Theorem 4.4 was based on an infinite-injury priority construction. The same method has been used by Harrington [6] and others to obtain results about ω-REA arithmetical degrees (see M. F. Simpson [14, Chapters 2 and 3] and Odifreddi [10, Chapter XIII]), jump embeddings (see Hinman/Slaman [8]), nonstandard models of arithmetic (see Ash/Knight [1, Chapters 14–19, Theorem 19.19]), and generalized high/low hierarchies (see Montalbán [9]).

Remark 4. Harrington’s original proof [7] of Theorem 4.5 was based on a finite-injury priority construction. The same method has been extended into the transfinite by Harrington [7] and Gerdes [5] to obtain other interesting results. In particular, see Remark 12 below. For an application to effectively Borel equivalence relations, see Fokina/Friedman/Törnquist [4].

Remark 5. Our new proof of Theorems 4.4 and 4.5 does not use a priority construction of any kind. Instead our proof is based on a direct oracle construction, adapted from the standard proof of the Friedberg Jump Theorem. In this sense our proof of Theorems 4.4 and 4.5 is much easier than the proofs in [1, 5, 6, 7, 8, 9, 10, 14]. On the other hand, our proof uses the Recursion Theorem in exactly the same way as Harrington used it. Harrington [6] has referred to this way of using the Recursion Theorem as “the shiny little box which was first opened by Sacks [12].”

Remark 6. Beyond Theorems 4.4 and 4.5, we believe we can extend our non-priority oracle method farther into the transfinite to obtain relatively easy proofs of at least some of the other results of Harrington [7] and Gerdes [5]. However, we reserve that extension for a future paper. In this paper we limit ourselves to providing relatively easy proofs of Theorems 4.4 and 4.5.

Remark 7. The plan of this paper is as follows. In §2 we review some basic recursion-theoretic notions. In §3 we prove a rudimentary version of Theorems 4.4 and 4.5. In §4 we prove Theorems 4.4 and 4.5.

2 Recursion-theoretic background

In this section we review some basic notions from recursion theory which are needed for our proof of Theorems 4.4 and 4.5. A good reference for this material is Rogers [11].

Natural numbers are denoted e, i, j, k, l, m, n, . . .. The set of all natural numbers is denoted ℕ. Instead of working with Pow(ℕ), the set of all subsets X ⊆ ℕ, we work with ℕ^{ℕ}, the set of all functions X : ℕ → ℕ. The space ℕ^{ℕ} with the product topology is known as the Baire space. Points in ℕ^{ℕ} are denoted X, Y, Z, . . .. Subsets of ℕ^{ℕ} are denoted P, Q, . . ..

Recall that a point X ∈ ℕ^{ℕ} or a set P ⊆ ℕ^{ℕ} is arithmetical if and only if it is Π_{n}^{0} for some n ≥ 1. The hierarchy Π_{n}^{0} where n = 1, 2, … is known as the arithmetical hierarchy. See for instance [11, Chapters 14–16]. (It is known [15] that every arithmetical set is in arithmetical one-to-one correspondence with a Π_{1}^{0} set. However, we shall not need this result here.) A Π_{n}^{0} singleton is a point X such that the singleton set {X} is Π_{n}^{0}. Thus X is an arithmetical singleton if and only if it is a Π_{n}^{0} singleton for some n ≥ 1. A ranked point is a point X such that X ∈ P for some countable Π_{1}^{0} set P.

Points in ℕ^{ℕ} may be viewed as Turing oracles. See for instance [11, Chapters 9–13]. Relativizing to a Turing oracle A ∈ ℕ^{ℕ}, a point X ∈ ℕ^{ℕ} or a set P ⊆ ℕ^{ℕ} is said to be Π_{n}^{0,A} if it is Π_{n}^{0} relative to A, and arithmetical in A if it is Π_{n}^{0,A} for some n. In particular, a set P is topologically closed if and only if it is Π_{1}^{0,A} for some A. A point X such that the singleton set {X} is Π_{n}^{0,A} is called a Π_{n}^{0,A} singleton.

For A ∈ ℕ^{ℕ} we write {e}^{A}(i) = j to mean that the eth Turing machine with oracle A and input i halts with output j. We write {e}^{A}(i) ↓ (respectively ↑) to mean that the eth Turing machine with oracle A and input i halts (respectively, does not halt). Thus {e}^{A}(i) ↓ if and only if ∃j ({e}^{A}(i) = j). For A, B ∈ ℕ^{ℕ} we write A ≤_{T} B to mean that A is Turing reducible to B, i.e., ∃e ∀i (A(i) = {e}^{B}(i)). We write A ≡_{T} B to mean that A is Turing equivalent to B, i.e., A ≤_{T} B and B ≤_{T} A. We define A ⊕ B ∈ ℕ^{ℕ} by the equations (A⊕B)(2i) = A(i) and (A⊕B)(2i+1) = B(i). Thus A⊕B ≤_{T} C if and only if A ≤_{T} C and B ≤_{T} C.

For A ∈ ℕ^{ℕ} we write A′ = the Turing jump of A, defined by

A′(e) = \{ \begin{matrix}1 & if \{e\}^{A}(e) ↓ , \\ 0 & if \{e\}^{A}(e) ↑ . \end{matrix}

We write A^{(n)} = the nth Turing jump of A, defined inductively by letting A^{(0)} = A and A^{(n+1)} = (A^{(n)})′ for all n. Recall that A is arithmetical in B if and only if ∃n (A ≤_{T} B^{(n)}). For use in the proof of Theorems 3.5 and 4.5, note that for each n ≥ 1, a set P ⊆ ℕ^{ℕ} is Π_{n}^{0} if and only if ∃e ∀X (X ∈ P ⇔ X^{(n)}(e) = 0). See for instance [11, §14.5].

We write A^{(ω)} = the ωth Turing jump of A, defined by

A^{(ω)}(i) = \{ \begin{matrix}A^{(n)}(e) & if i = 3^{n}5^{e}, \\ 0 & otherwise . \end{matrix}

Thus A^{(ω)} = ⨁_{n} A^{(n)} and A^{(n)} ≤_{T} A^{(ω)} uniformly in n.

Let 0 ∈ ℕ^{ℕ} denote the constant zero function. Thus 0^{(n)} = the nth Turing jump of 0, and 0^{(ω)} = the ωth Turing jump of 0. Note also that X is arithmetical if and only if X ≤_{T} 0^{(n)} for some n.

3 A rudimentary version of Harrington’s theorems

The purpose of this section is to prove a rudimentary version of Harrington’s theorems, with “arithmetical” replaced by Π_{n}^{0} for a fixed n. Our rudimentary versions of Theorems 4.4 and 4.5 are Theorems 3.4 and 3.5 respectively.

Lemma 3.1. Given a Π_{1}^{0,A′} set P we can find a Π_{1}^{0,A} set Q and a homeomorphism F : P ≅ Q such that X ⊕ A ≡_{T} F (X) ⊕ A uniformly for all X ∈ P.

Proof. Since P is a Π_{1}^{0,A′} set, it follows that P is a Π_{2}^{0,A} set, say P = {X | ∀i ∃j R(X, i, j)} where R is an A-recursive predicate. Define F : P ≅ Q = F (P) by letting F (X) = X ⊕X̂ where X̂(i) = the least j such that R(X, i, j) holds. Clearly Q is a Π_{1}^{0,A} set and X ⊕ A ≡_{T} F (X) ⊕ A uniformly for all X ∈ P.

Lemma 3.2. Given a Π_{1}^{0,A′} set P we can find a Π_{1}^{0,A} set Q and a homeomorphism H : P ≅ Q such that X ⊕ A′ ≡_{T} H(X) ⊕ A′ ≡_{T} (H(X) ⊕ A)′ uniformly for all X ∈ P.

In order to prove Lemma 3.2, we first present some general remarks concerning strings, trees, and treemaps.

Notation (strings). Let ℕ^{∗} = ⋃_{l∈ℕ} ℕ^{l} = the set of strings, i.e., finite sequences of natural numbers. For σ = ⟨n_{0}, n_{1}, …, n_{l−1}⟩ ∈ ℕ^{∗} we write σ(i) = n_{i} for all i < |σ| = l = the length of σ. For σ, τ ∈ ℕ^{∗} we write σ^{⌢}τ = the concatenation, σ followed by τ, defined by the conditions |σ^{⌢}τ| = |σ| + |τ|, (σ^{⌢}τ)(i) = σ(i) for all i < |σ|, and (σ^{⌢}τ)(|σ| + i) = τ(i) for all i < |τ|. We write σ ⊆ τ if σ^{⌢}ρ = τ for some ρ. If |σ| ≥ n we write σ↾n = ⟨σ(0), σ(1), …, σ(n − 1)⟩ = the unique ρ ⊆ σ such that |ρ| = n. For X ∈ ℕ^{ℕ} we write X↾n = ⟨X(0), X(1), …, X(n − 1)⟩ = the unique σ ⊂ X such that |σ| = n. If |σ| = |τ| = n we define σ ⊕ τ ∈ ℕ^{∗} by the conditions |σ ⊕ τ| = 2n and (σ ⊕ τ)(2i) = σ(i) and (σ ⊕ τ)(2i + 1) = τ(i) for all i < n.

Definition (trees). A tree is a set T ⊆ ℕ^{∗} such that

∀ρ ∀σ ((ρ ⊆ σ and σ ∈ T) ⇒ ρ ∈ T).

For any tree T we write

[T] = {paths through T } = {X | ∀n (X↾n ∈ T)}.

Remark 8. It is well known (see for instance [11, Chapter 15]) that the following statements are pairwise equivalent.

1. P is a Π_{1}^{0,A} set.

2. P = [T] for some Π_{1}^{0,A} tree T.

3. P = [T] for some A-recursive tree T.

4. P = {X | X ⊕ A ∈ [T]} for some recursive tree T.

Definition (treemaps). Let T be a tree. A treemap is a function F : T → ℕ^{∗} such that

F (σ^{⌢}⟨i⟩) ⊇ F (σ)^{⌢}⟨i⟩

for all σ ∈ T and all i ∈ ℕ such that σ^{⌢}⟨i⟩ ∈ T. We then have another tree

F (T) = {τ | ∃σ (σ ∈ T and τ ⊆ F (σ))}.

Thus P = [T] and F (P) = [F (T)] are closed sets in the Baire space, and we have a homeomorphism F : P ≅ F (P) defined by F (X) = ⋃_{n∈ℕ} F (X↾n) for all X ∈ P. Note also that the composition of two treemaps is a treemap. A treemap F : T → ℕ^{∗} is said to be A-recursive if it is the restriction to T of a partial A-recursive function.

Remark 9. Let T be a tree and let F : T → ℕ^{∗} be a treemap. Given τ ∈ F (T) let σ ∈ T be minimal such that τ ⊆ F (σ). Then σ is a substring of τ, i.e., σ = ⟨τ(j_{0}), τ(j_{1}), …, τ(j_{l−1})⟩ for some j_{0} < j_{1} < ⋯ < j_{l−1} < |τ|. Thus, in the definition of F (T), the quantifier ∃σ may be replaced by a bounded quantifier,

F (T) = {τ | (∃σ substring of τ) (σ ∈ T and τ ⊆ F (σ))}.

This implies that, for instance, if F and T are A-recursive then so is F (T).

We are now ready to prove Lemma 3.2.

Proof of Lemma 3.2. Given A we construct a particular A′-recursive treemap G : ℕ^{∗} → ℕ^{∗}. We define G(σ) by induction on |σ| beginning with G(⟨⟩) = ⟨⟩. If G(σ) has been defined, let e = |σ| and for each i let G(σ^{⌢}⟨i⟩) = the least τ ⊇ G(σ)^{⌢}⟨i⟩ such that {e}_{|τ|}^{τ⊕A}(e) ↓ if such a τ exists, otherwise G(σ^{⌢}⟨i⟩) = G(σ)^{⌢}⟨i⟩. Clearly G is an A′-recursive treemap, and our construction of G implies that for all e and X, {e}^{G(X)⊕A}(e) ↓ if and only if {e}_{|G(X↾e+1)|}^{G(X↾e+1)⊕A}(e) ↓. Thus X ⊕ A′ ≡_{T} G(X) ⊕ A′ ≡_{T} (G(X) ⊕ A)′ uniformly for all X.

Let G be the A′-recursive treemap which was constructed above. Let P be a Π_{1}^{0,A′} set. By Remarks 8 and 9 we know that the restriction of G to P maps P homeomorphically onto another Π_{1}^{0,A′} set G(P). Applying Lemma 3.1 to G(P) we obtain a Π_{1}^{0,A} set Q and a homeomorphism F : G(P) ≅ Q such that Y ⊕ A ≡_{T} F (Y) ⊕ A uniformly for all Y ∈ G(P). Thus H = F ∘ G is a homeomorphism of P onto Q, and for all X ∈ P we have G(X) ⊕ A ≡_{T} F (G(X)) ⊕ A = H(X) ⊕ A uniformly, hence X ⊕ A′ ≡_{T} H(X) ⊕ A′ ≡_{T} (H(X) ⊕ A)′ uniformly, Q.E.D.

Remark 10. Our proof of Lemma 3.2 via treemaps is similar to the proof of [2, Lemma 5.1]. Within our proof of Lemma 3.2, the construction of the specific treemap G is the same as the standard proof of the Friedberg Jump Theorem as expounded for instance in [11, §13.3].

Lemma 3.3. Given a Π_{1}^{0,0^{(n)}} set P_{n} we can find a Π_{1}^{0} set P_{0} and a homeomorphism H_{0}^{n} : P_{n} ≅ P_{0} such that X_{n}⊕0^{(n)} ≡_{T} X_{0}⊕0^{(n)} ≡_{T} X_{0}^{(n)} uniformly for all X_{n} ∈ P_{n} and X_{0} = H_{0}^{n}(X_{n}) ∈ P_{0}.

Proof. The proof is by induction on n. For n = 0 there is nothing to prove. For the inductive step, given a Π_{1}^{0,0^{(n+1)}} set P_{n+1} apply Lemma 3.2 with A = 0^{(n)} to obtain a Π_{1}^{0,0^{(n)}} set P_{n} and a homeomorphism H_{n} : P_{n+1} ≅ P_{n} such that X_{n+1} ⊕ 0^{(n+1)} ≡_{T} H_{n}(X_{n+1}) ⊕ 0^{(n+1)} ≡_{T} (H_{n}(X_{n+1}) ⊕ 0^{(n)})′ uniformly for all X_{n+1} ∈ P_{n+1}. Then apply the inductive hypothesis to P_{n} to find a Π_{1}^{0} set P_{0} and a homeomorphism H_{0}^{n} : P_{n} ≅ P_{0} such that X_{n} ⊕ 0^{(n)} ≡_{T} X_{0} ⊕ 0^{(n)} ≡_{T} X_{0}^{(n)} uniformly for all X_{n} ∈ P_{n}. Letting H_{0}^{n+1} = H_{n} ∘ H_{0}^{n} it follows that X_{n+1} ⊕ 0^{(n+1)} ≡_{T} X_{0} ⊕ 0^{(n+1)} ≡_{T} X_{0}^{(n+1)} uniformly for all X_{n+1} ∈ P_{n+1} and X_{0} = H_{0}^{n+1}(X_{n+1}) ∈ P_{0}, Q.E.D.

We now use Lemma 3.3 to prove a rudimentary version of Harrington’s theorems.

Theorem 3.4. Given n we can find Π_{1}^{0} singletons X, Y such that X ≰_{T} Y^{(n)} and Y ≰_{T} X^{(n)}.

Proof. It is well known [11, §13.3] that there exist incomparable Turing degrees between 0 and 0′. Relativizing to 0^{(n)}, let X_{n}, Y_{n} be such that 0^{(n)} ≤_{T} X_{n} ≤_{T} 0^{(n+1)} and 0^{(n)} ≤_{T} Y_{n} ≤_{T} 0^{(n+1)} and X_{n} ≰_{T} Y_{n} and Y_{n} ≰_{T} X_{n}. Note that X_{n} and Y_{n} are Δ_{2}^{0,0^{(n)}}, hence X_{n} and Y_{n} are Π_{2}^{0,0^{(n)}} singletons. Therefore, by the proof of Lemma 3.1 we may safely assume that X_{n} and Y_{n} are Π_{1}^{0,0^{(n)}} singletons. Apply Lemma 3.3 to P_{n} = {X_{n}, Y_{n}} to get X_{0} = H_{0}^{n}(X_{n}) and Y_{0} = H_{0}^{n}(Y_{n}). Note that P_{0} = {X_{0}, Y_{0}} is a Π_{1}^{0} set, hence X_{0} and Y_{0} are Π_{1}^{0} singletons. Since X_{n} ≰_{T} Y_{n} ⊕ 0^{(n)} ≡_{T} Y_{0}^{(n)} and X_{n} ⊕ 0^{(n)} ≡_{T} X_{0} ⊕ 0^{(n)} we have X_{0} ≰_{T} Y_{0}^{(n)}, and similarly Y_{0} ≰_{T} X_{0}^{(n)}. Letting X = X_{0} and Y = Y_{0} we obtain our theorem.

Theorem 3.5. Given n we can find a countable Π_{1}^{0} set P such that some Z ∈ P is not a Π_{n}^{0} singleton.

Proof. Let P_{n} be a countable Π_{1}^{0} set such that some Z_{n} ∈ P_{n} is not isolated in P_{n}. (For instance, let P_{n} = {X | ∀i ∀j (X(i) ≠ 0 ≠ X(j) ⇒ i = j)} and let Z_{n} = 0.) Treating P_{n} as a Π_{1}^{0,0^{(n)}} set, apply Lemma 3.3. Then P_{0} is a countable Π_{1}^{0} set and, because H_{0}^{n} : P_{n} ≅ P_{0} is a homeomorphism, Z_{0} = H_{0}^{n}(Z_{n}) is not isolated in P_{0}. We claim that Z_{0} is not a Π_{n}^{0} singleton. Otherwise, let e be such that {Z_{0}} = {X | X^{(n)}(e) = 0}. Since Z_{0}^{(n)}(e) = 0 and Z_{0} ∈ P_{0} and X_{0}^{(n)} ≡_{T} X_{n} ⊕ 0^{(n)} uniformly for all X_{n} ∈ P_{n} and X_{0} = H_{0}^{n}(X_{n}) ∈ P_{0}, there exists j such that X_{0}^{(n)}(e) = 0 for all X_{n} ∈ P_{n} such that X_{n}↾j = Z_{n}↾j. But Z_{n} is not isolated in P_{n}, so there exists X_{n} ∈ P_{n} such that X_{n}↾j = Z_{n}↾j and X_{n} ≠ Z_{n}. Thus X_{0}^{(n)}(e) = 0 and X_{0} ≠ Z_{0}, a contradiction. Letting P = P_{0} and Z = Z_{0} we obtain our theorem.

4 Proof of Harrington’s theorems

In order to prove the full version of Harrington’s theorems, we need to show that Lemma 3.3 holds with n replaced by ω. To this end we first draw out some effective uniformities which are implicit in the proofs of Lemmas 3.1 and 3.2.

Notation. Let W_{e}^{A} for e = 0, 1, 2, … be a standard enumeration of all A-recursively enumerable subsets of ℕ^{∗}. Then

T_{e}^{A} = {σ ∈ ℕ^{∗} | (∀n ≤ |σ|) (σ↾n ∉ W_{e}^{A})}

for e = 0, 1, 2, … is a standard enumeration of all Π_{1}^{0,A} trees. Hence P_{e}^{A} = [T_{e}^{A}] for e = 0, 1, 2, … is a standard enumeration of all Π_{1}^{0,A} sets.

Remark 11. If F is an A-recursive treemap and T is a Π_{1}^{0,A} tree, then F (T) is again a Π_{1}^{0,A} tree. Moreover, this holds uniformly in the sense that there is a primitive recursive function f such that T_{f(e)}^{A} = F (T_{e}^{A}) and P_{f(e)}^{A} = F (P_{e}^{A}) for all e, and we can compute a primitive recursive index of f knowing only an A-recursive index of F.

The next two lemmas are refinements of Lemmas 3.1 and 3.2 respectively.

Lemma 4.1 (refining Lemma 3.1). There is a primitive recursive function f with the following property. Given e we can effectively find an A-recursive treemap F : T_{e}^{A′} → T_{f(e)}^{A} which induces a homeomorphism F : P_{e}^{A′} ≅ P_{f(e)}^{A}. It follows that X ⊕ A ≡_{T} F (X) ⊕ A uniformly for all X ∈ P_{e}^{A′}.

Proof. Let T = T_{e}^{A′} and P = P_{e}^{A′}. Since T_{e}^{A′} is uniformly Π_{1}^{0,A′}, it is uniformly Π_{2}^{0,A}, say T = T_{e}^{A′} = {σ | ∀i ∃j R(σ, e, i, A↾j)} where R ⊆ ℕ^{∗}×ℕ× ℕ×ℕ^{∗} is a fixed primitive recursive predicate. Let (−, −) be a fixed primitive recursive one-to-one mapping of ℕ × ℕ onto ℕ such that m ≤ (m, n) and n ≤ (m, n) for all m and n. Define Q = [T̂] where T̂ = {σ ⊕ τ | |σ| = |τ| and (∀(n, i) < |τ|) (τ((n, i)) = the least j such that R(σ↾n, e, i, A↾j))}. Thus Q = {X ⊕ X̂ | X ∈ P } where X̂((n, i)) = the least j such that R(X↾n, e, i, A↾j). Moreover, we have an A-recursive treemap F : T → T̂ given by F (σ) = σ⊕σ̂ for all σ ∈ T, where |σ| = |σ̂| and (∀(n, i) < |σ|) (σ̂((n, i)) = the least j such that R(σ↾n, e, i, A↾j)). Although we cannot expect to have F (T) = T̂, we nevertheless have F : [T] ≅ [T̂], i.e., F : P ≅ F (P) = Q, and F (X) = X ⊕X̂ and X ⊕A ≡_{T} F (X)⊕A uniformly for all X ∈ P. The definition of T̂ shows that T̂ is uniformly A-recursive, hence uniformly Π_{1}^{0,A}, so we can find a fixed primitive recursive function f such that T_{f(e)}^{A} = T̂_{e}^{A′} for all e and A.

Lemma 4.2 (refining Lemma 3.2). There is a primitive recursive function h with the following property. Given e we can effectively find an A′-recursive treemap H : T_{e}^{A′} → T_{h(e)}^{A} which induces a homeomorphism H : P_{e}^{A′} ≅ P_{h(e)}^{A} such that X ⊕A′ ≡_{T} H(X)⊕A′ ≡_{T} (H(X)⊕A)′ uniformly for all X ∈ P_{e}^{A′}.

Proof. Let G be the specific A′-recursive treemap which was constructed in the proof of Lemma 3.2. By Remark 11 we can find a primitive recursive function g such that for all e we have G(T_{e}^{A′}) = T_{g(e)}^{A′} and the restriction of G to T_{e}^{A′} is a treemap from T_{e}^{A′} to T_{g(e)}^{A′} which induces a homeomorphism G : P_{e}^{A′} ≅ P_{g(e)}^{A′}. By construction of G we have X ⊕ A′ ≡_{T} G(X) ⊕ A′ ≡_{T} (G(X)⊕A)′ uniformly for all X ∈ P_{e}^{A′}. Now applying Lemma 4.1 we obtain an A-recursive treemap F : T_{g(e)}^{A′} → T_{f(g(e))}^{A} which induces a homeomorphism F : P_{g(e)}^{A′} ≅ P_{f(g(e))}^{A} such that Y ⊕A ≡_{T} F (Y)⊕A uniformly for all Y ∈ P_{g(e)}^{A}. Thus the treemap H = F ∘ G : T_{e}^{A′} → T_{f(g(e))}^{A} induces a homeomorphism F ∘ G = H : P_{e}^{A′} ≅ P_{f(g(e))}^{A} such that X ⊕ A′ ≡_{T} H(X) ⊕ A′ ≡_{T} (H(X) ⊕ A)′ uniformly for all X ∈ P_{e}^{A′}. Our lemma follows upon defining h(e) = f(g(e)).

We now show that Lemma 3.3 holds with n replaced by ω.

Lemma 4.3. Given a Π_{1}^{0,0^{(ω)}} set P_{ω} we can effectively find a Π_{1}^{0} set P_{0} and a homeomorphism H_{0}^{ω} : P_{ω} ≅ P_{0} such that X_{ω} ⊕ 0^{(ω)} ≡_{T} X_{0} ⊕ 0^{(ω)} ≡_{T} X_{0}^{(ω)} uniformly for all X_{ω} ∈ P_{ω} and X_{0} = H_{0}^{ω}(X_{ω}) ∈ P_{0}.

Proof. Since P_{ω} is a Π_{1}^{0,0^{(ω)}} set, Remark 8 gives a recursive tree T such that P_{ω} = {X | X ⊕ 0^{(ω)} ∈ [T]}. Moreover, from the definition of 0^{(ω)} we know that 0^{(ω)}↾n is computable from 0^{(n)} uniformly for all n. Thus, letting T_{ω} = {σ | σ ⊕ 0^{(ω)}↾|σ| ∈ T }, we see that P_{ω} = [T_{ω}] and {σ | |σ| ≤ n, σ ∈ T_{ω}} ≤_{T} 0^{(n)} uniformly for all n. Define

T_{e,n} = {σ | |σ| ≤ n} ∪ {σ | |σ| > n, σ↾n ∈ T_{ω}, σ ∈ T_{e}^{⟨n⟩^{⌢}0^{(n)}}}.

Thus T_{e,n} is a Π_{1}^{0,0^{(n)}} tree, hence P_{e,n} = [T_{e,n}] is Π_{1}^{0,0^{(n)}} uniformly for all n.

In the vein of Lemma 4.2, we claim there is a primitive recursive function h^{∗} with the following property. Given e and n we can effectively find a 0^{(n+1)}-recursive treemap

H_{e,n} : T_{e,n+1} → T_{h^{∗}(e),n}

which induces a homeomorphism H_{e,n} : P_{e,n+1} ≅ P_{h^{∗}(e),n} such that X ⊕ 0^{(n+1)} ≡_{T} H_{e,n}(X) ⊕ 0^{(n+1)} ≡_{T} (H_{e,n}(X) ⊕ 0^{(n)})′ uniformly for all X ∈ P_{e,n+1}, and in addition H_{e,n}(σ) = σ for all σ such that |σ| ≤ n.

To prove our claim, let r be a 3-place primitive recursive function such that T_{r(e,n,σ)}^{0^{(n)}} = {τ | σ^{⌢}τ ∈ T_{e,n}} for all e, n, σ. We can then write

T_{e,n+1} = {σ | |σ| ≤ n} ∪ {σ^{⌢}τ | |σ| = n, τ ∈ T_{r(e,n+1,σ)}^{0^{(n+1)}}}.

Since n is uniformly computable from ⟨n⟩^{⌢}0^{(n)}, let h^{∗} be a primitive recursive function such that

T_{h^{∗}(e),n} = {σ | |σ| ≤ n} ∪ {σ^{⌢}τ | |σ| = n, τ ∈ T_{h(r(e,n+1,σ))}^{0^{(n)}}}

where h is as in Lemma 4.2. For all σ and τ such that |σ| = n and τ ∈ T_{r(e,n+1,σ)}^{0^{(n+1)}} let H_{e,n}(σ^{⌢}τ) = σ^{⌢}H(τ) where H : T_{r(e,n+1,σ)}^{0^{(n+1)}} → T_{h(r(e,n+1,σ))}^{0^{(n)}} is as in Lemma 4.2. Clearly h^{∗}(e) and H_{e,n} have the required properties, so our claim is proved.

Let h^{∗} and H_{e,n} be as in the above claim. By the Recursion Theorem (see [11, Chapter 11]) let e^{∗} be a fixed point of h^{∗}, so that T_{h^{∗}(e^{∗})}^{A} = T_{e^{∗}}^{A} for all A, hence T_{h^{∗}(e^{∗}),n} = T_{e^{∗},n} for all n. Let H_{n} = H_{e^{∗},n} and T_{n} = T_{e^{∗},n} and P_{n} = P_{e^{∗},n} = [T_{n}] for all n. As in the proof of Lemma 3.3 we have uniformly for each s > n a 0^{(s)}-recursive treemap H_{n}^{s} = H_{n}∘⋯∘H_{s−1} : T_{s} → T_{n} which induces a homeomorphism H_{n}^{s} : P_{s} ≅ P_{n} such that X ⊕ 0^{(s)} ≡_{T} H_{n}^{s}(X) ⊕ 0^{(s)} ≡_{T} (H_{n}^{s}(X))^{(s−n)} uniformly for all X ∈ P_{s}, and in addition H_{n}^{s}(σ) = σ for all σ such that |σ| ≤ n. We also have for each n a 0^{(ω)}-recursive treemap H_{n}^{ω} : T_{ω} → T_{n} which induces a homeomorphism H_{n}^{ω} : P_{ω} ≅ P_{n}, namely H_{n}^{ω}(σ) = H_{n}^{|σ|}(σ) if |σ| > n and H_{n}^{ω}(σ) = σ if |σ| ≤ n. Note also that for all n < s < t < ω we have H_{n}^{t} = H_{n}^{s} ∘ H_{s}^{t} and H_{n}^{ω} = H_{n}^{s} ∘ H_{s}^{ω}. Finally, given X_{ω} ∈ P_{ω} let X_{n} = H_{n}^{ω}(X_{ω}) for all n. Then X_{ω}↾n = X_{n}↾n and X_{n} ⊕ 0^{(n)} ≡_{T} X_{0} ⊕ 0^{(n)} ≡_{T} X_{0}^{(n)} uniformly for all n and all X_{ω} ∈ P_{ω}, hence X_{ω} ⊕ 0^{(ω)} ≡_{T} X_{0} ⊕ 0^{(ω)} ≡_{T} X_{0}^{(ω)} uniformly for all X_{ω} ∈ P_{ω}. This completes the proof.

We now present Harrington’s construction of arithmetically incomparable arithmetical singletons.

Theorem 4.4. There is a pair of arithmetically incomparable Π_{1}^{0} singletons.

Proof. As in the proof of Theorem 3.4, let X_{ω}, Y_{ω} be such that 0^{(ω)} ≤_{T} X_{ω} ≤_{T} 0^{(ω+1)} and 0^{(ω)} ≤_{T} Y_{ω} ≤_{T} 0^{(ω+1)} and X_{ω} ≰_{T} Y_{ω} and Y_{ω} ≰_{T} X_{ω}. Note that X_{ω} and Y_{ω} are Δ_{2}^{0,0^{(ω)}} and hence Π_{2}^{0,0^{(ω)}} singletons. Therefore, by the proof of Lemma 3.1 we may safely assume that X_{ω} and Y_{ω} are Π_{1}^{0,0^{(ω)}} singletons. Apply Lemma 4.3 to P_{ω} = {X_{ω}, Y_{ω}} to get a Π_{1}^{0} set P_{0} and a homeomorphism H_{0}^{ω} : P_{ω} ≅ P_{0}. Let X_{0} = H_{0}^{ω}(X_{ω}) and Y_{0} = H_{0}^{ω}(Y_{ω}). Since P_{0} = {X_{0}, Y_{0}} it follows that X_{0} and Y_{0} are Π_{1}^{0} singletons. Since X_{ω} ≰_{T} Y_{ω} ⊕ 0^{(ω)} ≡_{T} Y_{0}^{(ω)} and X_{ω} ⊕ 0^{(ω)} ≡_{T} X_{0} ⊕ 0^{(ω)} we have X_{0} ≰_{T} Y_{0}^{(ω)}, and similarly Y_{0} ≰_{T} X_{0}^{(ω)}. In particular X_{0} and Y_{0} are arithmetically incomparable, Q.E.D.

Finally we present Harrington’s construction of a ranked point which is not an arithmetical singleton. This refutes a conjecture which had been known as McLaughlin’s Conjecture and which was suggested by the result of H. Tanaka [15] mentioned in Remark 2 above.

Theorem 4.5. There is a countable Π_{1}^{0} set P such that some Z ∈ P is not an arithmetical singleton.

Proof. As in the proof of Theorem 3.5, let P_{ω} be a countable Π_{1}^{0} set such that some Z_{ω} ∈ P_{ω} is not isolated in P_{ω}. Apply Lemma 4.3 and note that P_{0} is a countable Π_{1}^{0} set and Z_{0} = H_{0}^{ω}(Z_{ω}) ∈ P_{0} is not isolated in P_{0}. We claim that Z_{0} is not an arithmetical singleton. Otherwise, let i be such that {Z_{0}} = {X | X^{(ω)}(i) = 0}. Since Z_{0}^{(ω)}(i) = 0 and Z_{0} ∈ P_{0} and X_{0}^{(ω)} ≡_{T} X_{ω} ⊕0^{(ω)} uniformly for all X_{ω} ∈ P_{ω} and X_{0} = H_{0}^{ω}(X_{ω}) ∈ P_{0}, there exists j such that X_{0}^{(ω)}(i) = 0 for all X_{ω} ∈ P_{ω} such that Z_{ω}↾j ⊂ X_{ω}. But Z_{ω} is not isolated in P_{ω}, so there exists X_{ω} ∈ P_{ω} such that Z_{ω}↾j ⊂ X_{ω} and X_{ω} ≠ Z_{ω}. Thus X_{0}^{(ω)}(i) = 0 and X_{0} ≠ Z_{0}, a contradiction. Letting P = P_{0} and Z = Z_{0} we obtain our theorem.

Remark 12. Modifying the proof of Lemma 4.3, it is easy to replace ω by a small recursive ordinal such as ω + ω or ω · ω or ω^{ω}. Harrington [7] and Gerdes [5] have shown that Lemma 4.3 and consequently Theorems 4.4 and 4.5 hold generally with ω replaced by any recursive ordinal.

References

[1] Christopher J. Ash and Julia F. Knight. Computable Structures and the Hyperarithmetical Hierarchy. Number 144 in Studies in Logic and the Foundations of Mathematics. North-Holland, 2000. XV + 346 pages. 3, 4

[2] Joshua A. Cole and Stephen G. Simpson. Mass problems and hyperarithmeticity. Journal of Mathematical Logic, 7(2):125–143, 2008. 8

[3] Solomon Feferman. Some applications of the notions of forcing and generic sets. Fundamenta Mathematicae, 56:325–345, 1965. 3

[4] Ekaterina Fokina, Sy-David Friedman, and Asger Törnquist. The effective theory of Borel equivalence relations. Annals of Pure and Applied Logic, 161(7):837–850, 2010. 3

[5] Peter M. Gerdes. Harrington’s solution to McLaughlin’s conjecture and non-uniform self-moduli. Preprint, 27 pages, 15 December 2010, arXiv:1012.3427v1, submitted for publication. 3, 4, 12

[6] Leo Harrington. Arithmetically incomparable arithmetic singletons. Handwritten, 28 pages, April 1975. 2, 3, 4

[7] Leo Harrington. McLaughlin’s conjecture. Handwritten, 11 pages, September 1976. 2, 3, 4, 12

[8] Peter G. Hinman and Theodore A. Slaman. Jump embeddings in the Turing degrees. Journal of Symbolic Logic, 56(2):563–591, 1991. 3, 4

[9] Antonio Montalbán. There is no ordering on the classes in the generalized high/low hierarchies. Archive for Mathematical Logic, 45(2):215– 231, 2006. 3, 4

[10] Piergiorgio Odifreddi. Classical Recursion Theory, Volume II. Number 143 in Studies in Logic and the Foundations of Mathematics. North-Holland, 1999. XVI + 949 pages. 3, 4

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

[12] Gerald E. Sacks. On a theorem of Lachlan and Martin. Proceedings of the American Mathematical Society, 18:140–141, 1967. 4 [13] Gerald E. Sacks. Higher Recursion Theory. Perspectives in Mathemat-

ical Logic. Springer-Verlag, 1990. XV + 344 pages. 3

[14] Mark Fraser Simpson. Arithmetic Degrees: Initial Segments, ω-REA Operators, and the ω-Jump. PhD thesis, Cornell University, August 1985. VI + 103 pages. 3, 4

[15] Hisao Tanaka. A property of arithmetic sets. Proceedings of the American Mathematical Society, 31:521–524, 1972. 3, 4, 12