Implicit Definability in Arithmetic (a 2-hour tutorial)

Stephen G. Simpson Pennsylvania State University

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

Sendai Logic School Mathematical Institute

Tohoku University

Sendai, Japan February 22–23, 2013 Definitions.

Let ℕ, +, ×, = be the natural number system.

For X ⊆ ℕ we say that X is arithmetical if X first-order definable over ℕ, +, ×, =, i.e., X = {n ∈ ℕ | (ℕ, +, ×, =) ⊧ Φ(n)} for some first-order formula Φ.

For X, Y ⊆ ℕ we say that X is arithmetical in Y if X is first-order definable over ℕ, +, ×, =, Y. We say that X, Y are arithmetically equivalent (arithmetically incomparable ) if each (neither) is arithmetical in the other.

Let Pow (ℕ) = {X | X ⊆ ℕ} = the powerset of ℕ. Let S be a subset of Pow (ℕ). We say that S is arithmetical if S = {X ⊆ ℕ | (ℕ, +, ×, =, X) ⊧ Φ} for some first-order sentence Φ.

For X ⊆ ℕ we say that X is implicitly arithmetical or an arithmetical singleton if the singleton set {X} is arithmetical.

Five Theorems.

1. There exists an arithmetical singleton which is not arithmetical.

2. There exist X, Y ⊆ ℕ such that neither X nor Y is an arithmetical singleton, but X ⊕ Y = {2n | n ∈ X} ∪ {2n + 1 | n ∈ Y } is an arithmetical singleton.

3. If S ⊆ Pow (ℕ) is nonempty countable arithmetical, then some X ∈ S is an arithmetical singleton.

4. There are arithmetically incomparable X, Y ⊆ ℕ such that X and Y are arithmetical singletons.

5. There is a countable arithmetical S ⊆ Pow (ℕ) such that not all X ∈ S are arithmetical singletons.

Theorem 3 is due to Hisao Tanaka, 1972, Proceedings of the American Mathematical Society.

Theorems 4 and 5 are due to Leo Harrington, 1975–1976, unpublished.

Some literature.

Hisao Tanaka, A property of arithmetic sets, Proceedings of the American Mathematical Society, 1972, 31, pages 521–524.

Leo Harrington, Arithmetically incomparable arithmetic singletons, handwritten, 28 pages, April 1975.

Leo Harrington, McLaughlin’s conjecture, handwritten, 11 pages, September 1976.

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.

Stephen G. Simpson, Harrington’s results on arithmetical singletons, 9 pages, November 2012, preprint, submitted for publication.

Proof of Theorem 1.

Let T ⊆ ℕ be the truth set for arithmetic , i.e., the set of Gödel numbers of first-order sentences which are true in ℕ, +, ×, =. Tarski’s Theorem on undefinability of truth says that T is not arithmetical. However, T is implicitly arithmetical, namely ∀Φ ∀Ψ (#(Φ ∧ Ψ) ∈ T ⟺ (#(Φ) ∈ T ∧ #(Ψ) ∈ T)), ∀Φ (#(∃n Φ(n)) ∈ T ⟺ ∃n (#(Φ(n)) ∈ T)), etc., where #(Φ) = the Gödel number of Φ.

Proof of Theorem 2.

We use Cohen forcing over ℕ, +, ×, =.

Let {0, 1}∗ be the set of bitstrings , i.e., finite sequences of 0’s and 1’s. For σ, τ ∈ {0, 1}∗ we write σ^{⌢}τ = the concatenation , σ followed by τ. We write σ ⊆ τ if σ is an initial segment of τ, i.e., σ^{⌢}ρ = τ for some ρ ∈ {0, 1}∗.

A set D ⊆ {0, 1}∗ is said to be dense if ∀σ ∃τ (σ ⊆ τ and τ ∈ D).

Let D_{n}, n ∈ ℕ, be an enumeration of the dense sets which are arithmetical. We choose our enumeration to be arithmetical in T, the Tarski truth set.

Proof of Theorem 2, continued.

Define sequences of bitstrings σ_{0} ⊆ σ_{1} ⊆ σ_{2} ⊆ ⋯ σ_{i} ⊆ σ_{i+1} ⊆ ⋯ and τ_{0} ⊆ τ_{1} ⊆ τ_{2} ⊆ ⋯ τ_{i} ⊆ τ_{i+1} ⊆ ⋯ as follows.

Stage 0 . Let σ_{0} = τ_{0} = ⟨⟩ = the empty sequence.

Stage 3n + 1 . Let σ_{3n+1} = σ_{3n}^{⌢}ρ and τ_{3n+1} = τ_{3n}^{⌢}ρ where ρ is the least member of {0, 1}∗ such that σ_{3n}^{⌢}ρ ∈ D_{n}.

Stage 3n + 2 . Let σ_{3n+2} = σ_{3n+1} ^{⌢}ρ and τ_{3n+2} = τ_{3n+1} ^{⌢}ρ where ρ is the least member of {0, 1}∗ such that τ_{3n+1} ^{⌢}ρ ∈ D_{n}.

Stage 3n + 3 . If n ∈ T let σ_{3n+3} = σ_{3n+2} ^{⌢}⟨1⟩ and τ_{3n+3} = τ_{3n+2} ^{⌢}⟨0⟩. If n ∉ T let σ_{3n+3} = σ_{3n+2} ^{⌢}⟨0⟩ and τ_{3n+3} = τ_{3n+2} ^{⌢}⟨1⟩.

Let X, Y ⊆ ℕ be such that ⋃_{i} σ_{i} and ⋃_{i} τ_{i} are the characteristic functions of X and Y respectively.

Clearly X and Y are Cohen generic over ℕ, +, ×, =. Hence X and Y are not arithmetical singletons. However, X ⊕ Y is arithmetically equivalent to T, hence X ⊕ Y is an arithmetical singleton.

Recursion-theoretic concepts.

In order to prove Theorems 3, 4, 5 we use recursion-theoretic concepts and notation.

From now on, instead of working with subsets of ℕ , we shall work with functions from ℕ into ℕ .

Let ℕ^{ℕ} = {X | X : ℕ → ℕ} = the Baire space. Within ℕ^{ℕ} we consider points X, Y, … ∈ ℕ^{ℕ} and sets P, Q, … ⊆ ℕ^{ℕ}.

For e, i, j ∈ ℕ and X ∈ ℕ^{ℕ} we write {e}^{X}(i) ≃ j to mean: the program with Gödel number e using oracle X and input i eventually halts with output j.

We write {e}^{X}(i) ↓ to mean that ∃j ({e}^{X}(i) ≃ j).

We write X ≤_{T} Y to mean that X is Turing reducible to Y, i.e., ∃e ∀i (X(i) = {e}^{Y} (i)).

The Turing jump of X ∈ ℕ^{ℕ} is X′ ∈ ℕ^{ℕ} defined by X′(e) = 1 if {e}^{X}(e) ↓, otherwise X′(e) = 0.

The iterated Turing jumps X^{(n)}, n ∈ ℕ, are defined inductively by X^{(0)} = X and X^{(n+1)} = (X^{(n)})′.

Fact : X is arithmetical in Y ⟺ ∃n (X ≤_{T} Y^{(n)}).

Recursion-theoretic concepts, continued.

For X, Y ∈ ℕ^{ℕ} we define X ⊕ Y ∈ ℕ^{ℕ} by (X ⊕ Y)(2i) = X(i) and (X ⊕ Y)(2i + 1) = Y (i).

A predicate R ⊆ (ℕ^{ℕ})^{k} × ℕ^{n} is said to be computable if ∃e ∀X_{1} ⋯ ∀X_{k} ∀i_{1} ⋯ ∀i_{n} ({e}^{X_{1}⊕···⊕X_{k}}(i_{1}, …, i_{n}) = 1 if R(X_{1}, …, X_{k}, i_{1}, …, i_{n}), {e}^{X_{1}⊕···⊕X_{k}}(i_{1}, …, i_{n}) = 0 if ¬ R(X_{1}, …, X_{k}, i_{1}, …, i_{n})).

A set P ⊆ ℕ^{ℕ} is said to be Π_{n}^{0,Y} if and only if

P = {X | ∀i_{1} ∃i_{2} ∀i_{3} ⋯ i_{n} R(X, Y, i_{1}, …, i_{n})} for some computable predicate R ⊆ (ℕ^{ℕ})^{2} × ℕ^{n}. We also write Π_{n}^{0} = Π_{n}^{0,0} where 0 ∈ ℕ^{ℕ} is defined by 0(i) = 0 for all i. Note: There are n alternating quantifiers. The last quantifier is ∀i_{n} if n is odd, ∃i_{n} if n is even.

Fact : P is arithmetical ⟺ ∃n (P is Π_{n}^{0}).

Caution : P is arithmetical if ∃n (P is Π_{1}^{0,0^{(n)}} ). However, for sets P ⊆ ℕ^{ℕ}, the converse may fail.

Fact : P is topologically closed ⟺ ∃Y (P is Π_{1}^{0,Y} ).

Proof of Theorem 3.

Suppose P ⊆ ℕ^{ℕ} is arithmetical. For example, suppose P is Π_{3}^{0}, say

P = {X | ∀i ∃j ∀n R(X, i, j, n)}

where R is computable.

Given X, we replace the quantifiers ∃j and ∀n by canonical Skolem functions f and g.

Let g(i, j) = 1 + the least n such that ¬ R(X, i, j, n) if such an n exists, otherwise g(i, j) = 0.

Note: g(i, j) = 0 ≡ ∀n R(X, i, j, n).

Let f(i) = 1 + the least j such that g(i, j) = 0 if such a j exists, otherwise f(i) = 0.

Note: f(i) > 0 ≡ ∃j (g(i, j) = 0) ≡ ∃j ∀n R(X, i, j, n). Hence X ∈ P ≡ ∀i (f(i) > 0).

Note: X ⊕ f ⊕ g is arithmetically equivalent to X.

Define F : P → ℕ^{ℕ} by F (X) = X ⊕ f ⊕ g. Clearly F is a one-to-one correspondence between P and Q = {F (X) | X ∈ P }. Clearly Q is Π_{1}^{0}, hence topologically closed.

Assume P is countable and nonempty. Then Q is countable and nonempty, hence there exists Y ∈ Q such that Y is isolated in Q. It follows that Y is a Π_{1}^{0} singleton. Let X ∈ P be such that F (X) = Y. Then X is an arithmetical singleton, Q.E.D.

Proof of Theorems 4 and 5.

To prove Theorems 4 and 5 we use treemaps .

Let ℕ∗ = the set of strings , i.e., finite sequences of natural numbers. For σ, τ ∈ ℕ∗ we write σ ⊆ τ if σ is an initial segment of τ, i.e., σ^{⌢}ρ = τ for some ρ ∈ ℕ∗. For X ∈ ℕ^{ℕ} and n ∈ ℕ we write

X↾n = ⟨X(0), X(1), …, X(n − 1)⟩ and note that X↾n ∈ ℕ∗.

A tree is a set T ⊆ ℕ∗ such that

∀σ ∀τ (σ ⊆ τ, τ ∈ T ⇒ σ ∈ T). In this case we write

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

Fact: A set P ⊆ ℕ^{ℕ} is Π_{1}^{0,A} ⟺ P = [T] where T is Π_{1}^{0,A}, ⟺ P = [T] where T is A-recursive.

A treemap is a function F : T → ℕ∗ such that

∀σ ∀i (σ^{⌢}⟨i⟩ ∈ T ⇒ F (σ)^{⌢}⟨i⟩ ⊆ F (σ^{⌢}⟨i⟩). In this case we have another tree

F (T) = {τ | ∃σ (τ ⊆ F (σ), σ ∈ T)} and F induces a homeomorphism F : [T] ≅ [F (T)] given by F (X) = ⋃{F (X↾n) | n ∈ ℕ} for all X ∈ [T].

A treemap F : T → ℕ∗ is said to be A-recursive if ∃e ∀σ (σ ∈ T ⇒ F (σ) = {e}^{A}(σ)). It is easy to see that if F and T are A-recursive then F (T) is A-recursive.

Lemma 1. Given a Π_{1}^{0,A′} set P we can find a Π_{1}^{0,A} set Q and an A-recursive treemap F : P ≅ Q. Thus X ⊕ A ≡_{T} F (X) ⊕ A uniformly for all X ∈ P.

Proof. P is Π_{2}^{0,A}, say P = {X | ∀i ∃j R(X, i, j)} where R is A-recursive. Let F (X) = X ⊕ f where f(i) = the least j such that R(X, i, j) holds. Clearly F is A-recursive, and it can be shown that F is a treemap.

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

Proof. We first construct a particular A′-recursive treemap G : ℕ∗ → ℕ∗. Begin with G(⟨⟩) = ⟨⟩. If G(σ) has been defined, let e = |σ| = the length of σ, 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⟩. Note that for all X we have X ⊕ A′ ≡_{T} G(X) ⊕ A′ ≡_{T} (G(X) ⊕ A)′ uniformly.

Since G(P) is Π_{1}^{0,A′}, apply Lemma 1 to get an A-recursive treemap F : G(P) ≅ Q where Q is Π_{1}^{0,A}. Then H = F ∘ G : P ≅ Q is our desired H.

Lemma 3. Given a Π_{1}^{0,0^{(n)}} set P_{n} we can find a Π_{1}^{0} set P_{0} and a 0^{(n)}-recursive treemap H : P_{n} ≅ P_{0} such that X ⊕ 0^{(n)} ≡_{T} H(X) ⊕ 0^{(n)} ≡_{T} H(X)^{(n)} uniformly for all X ∈ P_{n}.

Proof. Apply Lemma 2 n times. We then have P_{n} ≅ ⋯ ≅ P_{i} ≅ P_{i−1} ≅ ⋯ ≅ P_{0} and P_{i} is Π_{1}^{0,0^{(i)}} and for each i = 1, …, n we have a treemap H_{i} : P_{i} ≅ P_{i−1} such that, uniformly for all X ∈ P_{i}, X ⊕ 0^{(i)} ≡_{T} H_{i}(X) ⊕ 0^{(i)} ≡_{T} (H_{i}(X) ⊕ 0^{(i−1)} )′. Our desired H : P_{n} ≅ P_{0} is H_{1} ∘ ⋯ ∘ H_{n}.

We now prove weak forms of Theorems 4 and 5.

Theorem 4∗ (simplified version of Theorem 4). For each n there are Π_{1}^{0} singletons X, Y such that X ≰_{T} Y^{(n)} and Y ≰_{T} X^{(n)}.

Proof. Let X_{n} and 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}. Then X_{n} and Y_{n} are Π_{2}^{0,0^{(n)}} singletons. We may safely assume that they are Π_{1}^{0,0^{(n)}} singletons. Let P_{n} = {X_{n}, Y_{n}}. Apply Lemma 3 to get H : P_{n} ≅ P_{0}. Let X_{0} = H(X_{n}) and Y_{0} = H(Y_{n}). Then X_{0}, Y_{0} are the desired X, Y.

Theorem 5∗ (simplified version of Theorem 5). For each n there is 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}. Apply Lemma 3 to get H : P_{n} ≅ P_{0}. Let Z_{0} = H(Z_{n}). Then P_{0} and Z_{0} are the desired P and Z.

Details: H is a homeomorphism of P_{n} onto P_{0}, so Z_{0} is not isolated in P_{0}. Suppose Z_{0} were a Π_{n}^{0} singleton, say {Z_{0}} = {X_{0} | X_{0}^{(n)}(e) = 0}. Since X_{n} ⊕ 0^{(n)} ≡_{T} H(X_{n})^{(n)} uniformly for X_{n} ∈ P_{n}, let j be such that H(X_{n})^{(n)}(e) = 0 for all X_{n} ∈ P_{n} such that X_{n}↾j = Z_{n}↾j. Since Z_{n} is not isolated in P_{n}, let X_{n} ∈ P_{n} be such that X_{n}↾j = Z_{n}↾j and X_{n} ≠ Z_{n}. Letting X_{0} = H(X_{n}) we have X_{0}^{(n)}(e) = 0 and X_{0} ≠ Z_{0}. This is a contradiction.

We now turn to the proofs of Theorems 4 and 5.

To prove Theorems 4 and 5, we extend Lemma 3 replacing n by ω, the first infinite ordinal number. For X ∈ ℕ^{ℕ} define the ω-jump X^{(ω)} ∈ ℕ^{ℕ} by

X^{(ω)} = X ⊕ X′ ⊕ X′′ ⊕ ⋯ ⊕ X^{(n)} ⊕ · · ·. More precisely, let X^{(ω)}((n, i)) = X^{(n)}(i) where (·, ·) is a recursive one-to-one correspondence between ℕ × ℕ and ℕ.

Lemma 3∗ (Lemma 3 with n replaced by ω).

Given a Π_{1}^{0,0^{(ω)}} set P_{ω} we can find a Π_{1}^{0} set P_{0} and a 0^{(ω)}-recursive treemap H : P_{ω} ≅ P_{0} such that X ⊕ 0^{(ω)} ≡_{T} H(X) ⊕ 0^{(ω)} ≡_{T} H(X)^{(ω)} uniformly for all X ∈ P_{ω}.

In our proof of Lemma 3∗, we shall exploit the uniformity of Lemma 2, as we now explain.

Let T_{e}^{A}, e ∈ ℕ, be a standard enumeration of all Π_{1}^{0,A} trees. Then P_{e}^{A} = [T_{e}^{A}], e ∈ ℕ, is a standard enumeration of all Π_{1}^{0,A} sets.

Lemma 2 holds uniformly. Namely, we can find a recursive function h and, for all e and A, an A′-recursive treemap 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 of Lemma 3∗.

Let T_{ω} be a 0^{(ω)}-recursive tree such that P_{ω} = [T_{ω}]. We can choose T_{ω} in such a way that {σ ∈ T_{ω} | |σ| ≤ n} ≤_{T} 0^{(n)} uniformly for all n.

Let T_{e,n} be a Π_{1}^{0,0^{(n)}} tree consisting of {σ | |σ| ≤ n}

together with {τ | |τ| > n, τ↾n ∈ T_{ω}, τ ∈ T_{e}^{⟨n⟩^{⌢}0^{(n)}} }.

Note that P_{e,n} = [T_{e,n}] is a Π_{1}^{0,0^{(n)}} set.

Using the uniformity of Lemma 2, we can find a recursive function h^{∗} and, for n ≥ 1, 0^{(n)}-recursive treemaps H_{e,n} : P_{e,n} ≅ P_{h^{∗}(e),n−1} such that X ⊕ 0^{(n)} ≡_{T} H_{e,n}(X) ⊕ 0^{(n)} ≡_{T} (H_{e,n}(X) ⊕ 0^{(n−1)} )′ uniformly for all X ∈ P_{e,n}, and furthermore H_{e,n}(σ) = σ for all σ such that |σ| ≤ n.

By the Recursion Theorem , let e be a fixed point of h^{∗}. Thus T_{e}^{A} = T_{h^{∗}(e)}^{A} for all A, so in particular T_{e,n} = T_{h^{∗}(e),n} for all n. Using this e, define P_{n} = P_{e,n} and H_{n} = H_{e,n} for all n. Thus P_{n} is a Π_{1}^{0,0^{(n)}} set and H_{n} : P_{n} ≅ P_{n−1} is a treemap. Define H : P_{ω} ≅ P_{0} by H(σ) = (H_{1} ∘ ⋯ ∘ H_{n})(σ) where n = |σ|. Then P_{0} and H are as desired.

Recall: we obtained Theorems 4∗ and 5∗ as easy consequences of Lemma 3. We shall now obtain Theorems 4 and 5 as easy consequences of Lemma 3∗. The proofs are exactly the same.

Proof of Theorem 4. Let X_{ω} and 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_{ω}. Then X_{ω} and Y_{ω} are Π_{2}^{0,0^{(ω)}} singletons. We may safely assume that they are Π_{1}^{0,0^{(ω)}} singletons. Let P_{ω} = {X_{ω}, Y_{ω}}. Apply Lemma 3∗ to get H : P_{ω} ≅ P_{0}. Let X_{0} = H(X_{ω}) and Y_{0} = H(Y_{ω}). Then X_{0}, Y_{0} are the desired X, Y.

Proof of Theorem 5. Let P_{ω} be a countable Π_{1}^{0} set such that some Z_{ω} ∈ P_{ω} is not isolated in P_{ω}. Apply Lemma 3∗ to get H : P_{ω} ≅ P_{0}. Let Z_{0} = H(Z_{ω}). Then P_{0} and Z_{0} are the desired P and Z.

THE END. THANK YOU!