Implicit definability in arithmetic

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

January 31, 2013

This is the abstract of my two-hour tutorial, part of the Sendai Logic Winter School to be held at Tohoku University, February 22–23, 2013.

Let ℕ = {0, 1, 2, …} be the set of natural numbers. We consider explicit and implicit definability over the structure ℕ, +, ×, =. Let ℕ^{ℕ} be the Baire space, i.e., the space of total functions X : ℕ → ℕ. A point X ∈ ℕ^{ℕ} is said to be explicitly definable if X = {(i, j) ∈ ℕ × ℕ | (ℕ, +, ×, =) ⊧ Φ(i, j)} for some first-order formula Φ(i, j). More generally, for X, Y ∈ ℕ^{ℕ} we say that X is explicitly definable from Y if X = {(i, j) ∈ ℕ × ℕ | (ℕ, +, ×, =, Y) ⊧ Φ(i, j, Y)} for some first-order formula Φ(i, j, Y). A set P ⊆ ℕ^{ℕ} is said to be explicitly definable if P = {X ∈ ℕ^{ℕ} | (ℕ, +, ×, =, X) ⊧ Ψ(X)} for some first-order formula Ψ(X). Note that a point X or a set P is explicitly definable if and only if it is arithmetical, i.e., Π_{k}^{0} for some k < ω. A point X ∈ ℕ^{ℕ} is said to be implicitly definable or implicitly arithmetical or an arithmetical singleton if the singleton set {X} is arithmetical.

The Tarski Truth Theorem provides an example of a point which is implicitly definable but not explicitly definable. The Kleene/Souslin Theorem implies that a point is hyperarithmetical if and only if it is explicitly definable from some implicitly definable point. Cohen forcing provides an implicitly definable pair of points such that neither point is implicitly definable. A 1972 theorem of Tanaka says that every countable, nonempty, explicitly definable set of points contains an implicitly definable point. An unpublished 1975 theorem of Harrington provides a pair of implicitly definable points such that neither point is explicitly definable from the other. An unpublished 1976 theorem of Harrington provides a countable, explicitly definable set of points such that not every point in the set is implicitly definable. The proofs of Harrington’s theorems involve a remarkable application of the Recursion Theorem.