Set Theory Jottings 29. Definability

Prev TOC Next

Three Kinds of Definability

A⊆ℕ is arithmetic if there is a formula φ(x) in ℒ(PA) such that

For all n [n∈A if and only if ℕ⊧φ(n)]

Tarski’s undefinability theorem says that truth in ℕ is not arithmetic: the set of Gödel numbers of sentences of ℒ(PA) that hold in ℕ is not an arithmetic set. Using the Quine bracket notation where ⌜ψ⌝ is the Gödel number of ψ, we can say: there is no φ(x)∈ℒ(PA) such that for all closed ψ∈ℒ(PA),

ℕ⊧ψ if and only if ℕ⊧φ(⌜ψ⌝)

On the other hand, Tarski gave a recursive definition of satisfaction for first-order logic: if ℒ is a language and M is a structure for ℒ, then M⊧φ∧ψ if and only if M⊧φ and M⊧ψ, etc. We can formalize this for Peano arithmetic by adding a new predicate letter, say T, to ℒ(PA). I’ll write ℒ(PA+T) for this language. We can now express Tarski’s recursive definition this way:

T(⌜ψ⌝) ↔

⌜ψ⌝ = ⌜s=t⌝ ∧ s and t are closed terms with equal values

∨ ⌜ψ⌝ = ⌜¬α⌝ ∧ ¬T(⌜α⌝)

∨ ⌜ψ⌝ = ⌜α∧β⌝ ∧ T(⌜α⌝) ∧ T(⌜β⌝)

∨ ⌜ψ⌝ = ⌜∃x φ(x)⌝ ∧ ∃n T(⌜φ(n)⌝)

This is the outline of a sentence in ℒ(PA+T). With a large but bounded amount of work, it can be translated completely into the formal language. I will only hint at why this is true—a convincing explanation would take many pages. You can find that in many textbooks, and my  Logic Notes also have a bit to say. Anyway: one can show that Peano arithmetic can represent any recursive function. It follows that PA can handle all purely syntactical matters. For example, “n is a Gödel number”; or “n is the Gödel number of a formula of the form α∧β, and k is the Gödel number of α and l is the Gödel number of β’’; or “s is the Gödel number of a closed term whose value is v.”

Say A⊆ℕ. (ℕ,+,·,<,A) (or (ℕ,A) for short) is a structure for ℒ(PA+T), if we interpret T(n) as meaning n∈A. Then our sentence holds in (ℕ,A) precisely when A is the set of Gödel numbers of true sentences ψ of ℒ(PA).

I generalize. Write ℒ(PA+S) for ℒ(PA) augmented with a new predicate letter S. (ℕ,A) is a structure for ℒ(PA+S), using A to interpret S. Say we have a class 𝒜 of subsets of ℕ, and a closed formula ψ_S in ℒ(PA+S). Suppose that

For all A⊆ℕ [A∈𝒜 if and only if (ℕ,A)⊧ψ_S]

Then we say that 𝒜 is an arithmetic class.

For example, consider the formula

ψ_S ≡ ∀x (S(x)→S(x·x))

In other words, (ℕ,A)⊧ψ_S means that A is closed under squaring. The class 𝒜 determined by ψ_S contains many sets: the set of all squares, the set of all powers of a prime p, the set of numbers whose prime factors all belong to a fixed set of primes, etc.

If {A} is an arithmetic class, then we say that A is implicitly definable by the formula ψ_S defining its singleton class. So truth in ℕ is implicitly definable.

Observe that any arithmetic set is implicitly definable: just let ψ_S be ∀x[S(x)↔φ(x)], where φ(x) is the formula in ℒ(PA) defining the arithmetic set.

The class of arithmetic sets enjoys some nice properties: it is closed under intersection, union, and complement. This falls out just from using the logical connectives. The existential quantifier gives us another operation, projection. Let 〈y,z〉 be a recursive pairing function, that is, a recursive bijection from ℕ×ℕ to ℕ. If A is defined by φ(x), then the formula ∃y φ(〈y,z〉) defines the projection of the relation 〈y,z〉∈A onto its second coordinate. (If this relation is a function, then the projection is its range. Likewise, if the relation is a partial function, we can project on the first coordinate to find its domain.)

The class of arithmetic sets is precisely the smallest class of subsets of ℕ closed under intersection, union, complement, projection, and containing the singletons {0} and {1} and the graphs of the addition and multiplication operations. (Take a moment to see why this is true.)

As we will see later, the class of implicitly definable sets is less tidy. For one thing, it’s not closed under intersection.

We recover some of the nice features by passing to a yet more inclusive class, the hyperarithmetic sets. First we expand our language to so-called second-order arithmetic: instead of adding a new predicate letter, we allow variables ranging over subsets of ℕ. Quantification is allowed. I will use capital letters for subsets and lowercase for numbers¹. I’ll write S(x) and x∈S to mean the same thing; you can decide which is vernacular. I’ll write ℒ²(PA) for second-order arithmetic.

Suppose A is implicitly definable via a formula ψ_S in ℒ(PA+S). Then A is definable in ℒ²(PA) in two ways, existentially:

∃S (ψ_S ∧ x∈S)

and universally:

∀S (ψ_S → x∈S)

since in both forms, the clause “ψ_S’’ guarantees that S is the set A. Note that each formula has a sole free number variable, x.

A formula in ℒ²(PA) is called a Σ¹₁ formula if it has an existential set quantifier out in front, no universal set quantifiers, and as many number quantifiers as your heart desires. Likewise, a Π¹₁ has a universal set quantifier out front, no existential set quantifiers, and as many number quantifiers as needed. Thus:

Σ11:	∃S ψ(S,x)
Π11:	∀S ψ(S,x)

where ψ(S,x) can contain number quantifiers in abundance, but no other set quantifiers.

A set is hyperarithmetic or Δ¹₁ if it possesses both a Σ¹₁ and a Π¹₁ definition. (That is, Σ¹₁ and a Π¹₁ formulas with one free number variable, but no other free variables.)

An example: the set of even numbers, arithmetically defined by a formula φ(x)∈ℒ(PA), implicitly defined by a formula Φ(S)∈ℒ(PA+S), and hyperarithmetically defined by formulas α(u)∈Π¹₁ and ε(u)∈Σ¹₁.

Arithmetic definition: φ(x) ≡ ∃y (y+y=x)

Implicit definition: Φ(S) ≡ ∀x (S(x)↔∃y(y+y=x))

Π¹₁ definition: α(u) ≡ ∀S [∀x(S(x)↔∃y(y+y=x))→S(u)]

Σ¹₁ definition: ε(u) ≡ ∃S [∀x(S(x)↔∃y(y+y=x))∧S(u)]

The pattern is clear:

Arithmetic definition: φ(x) ≡ ∃y (y+y=x)

Implicit definition: Φ(S) ≡ ∀x (S(x)↔φ(x))

Π¹₁ definition: α(u) ≡ ∀S [Φ(S)→S(u)]

Σ¹₁ definition: ε(u) ≡ ∃S [Φ(S)∧S(u)]

We see from this that every arithmetic set is implicitly definable, and every implicitly definable set is hyperarithmetic.

The set of Gödel numbers of true sentences in ℒ(PA) provides an example of an implicitly definable set that is not arithmetic, as we’ve just seen. Feferman’s theorem provides an example of a hyperarithmetic set that is not implicitly definable.

[1] So this is a two-sorted first-order language. Alternately, add predicates set and number, and treat ∃X… as vernacular for ∃x(set(x) ∧ …), etc.

Prev TOC Next