Category Archives: Math

Prev TOC Next

We will need some familiarity with the the “definability powers” of Peano arithmetic. Without giving an exhaustive treatment, here are some of the highlights.

Recursive Tupling Functions

We have a 1–1 correspondence ℕ×ℕ→ℕ. Lots of them! We’ll pick one in a moment; we’ll denote it by

(x,y)↦〈x,y〉

Here (x,y)∈ℕ×ℕ is an ordered pair, and 〈x,y〉∈ℕ is the number coding it.

We want 〈·,·〉 to be arithmetically definable. The following formula does the trick:

〈x,y〉= ½(x+y)(x+y+1)+y

It’s easy to see where it comes from. If you list the lattice points in ℕ×ℕ by “cross diagonals” (i.e., (0,0), (1,0), (0,1), (1,1), …), then the predecessors of (x,y) consist of a triangle, plus a “tail” lying along the diagonal. Count them up! You get the above formula. So 〈·,·〉 is not just arithmetic, but recursive.

You can iterate this to get recursive k-tupling correspondences ℕ^k→ℕ for every k. For example,

〈x,y,z〉= 〈〈x,y〉, z〉

The tupling functions allow us to translate formulas like this:

∀x₁∀x₂∃y₁∃y₂…

into this:

∀x∃y…

Using the tupling functions, we can extend the notions of arithmetic and hyperarithmetic to n-ary relations and functions. For relations this is obvious. For a function, we look at its graph: f(x̄) is arithmetic (respectively hyperarithmetic) if the relation f(x̄)=y is.

Our definition of ℒ²(PA) allowed quantification over set variables. Sometimes there are technical advantages to using function variables instead. These can be “translated away” in a mechanical fashion. Admittedly the details can get a little hairy; for example, try expressing ∀x f(g(x))=g(f(x)) using the relations φ_f(x,y) ≡ f(x)=y and φ_g(x,y) ≡ g(x)=y. I will use both freely in ℒ²(PA).

Recursion

Recursion is a basic tool. Here’s the simplest form. Suppose we have a function f:ℕ→ℕ, and let a be any number. Define F by

F(0)	= a
F(n+1)	= f(F(n))

If f is arithmetic (or hyperarithmetic), does that make F arithmetic (hyperarithmetic)? Here are two ways we can write a formula for F(x)=y, provided we can quantify over arbitrary finite sequences a₀,…,a_x:

F(x)=y ≡	(∃a0,…,ax)[
	a0=a
	∧ (∀z<x)(az+1=f(az))
	∧ y=ax]

and

F(x)=y ≡	(∀a0,…,ax)[
	a0=a
	∧ (∀z<x)(az+1=f(az))
	→y=ax]

So we have a choice of ∃ or ∀, good news for the hyperarithmetic case. We’ll see soon how to handle arbitrary finite sequences in PA.

More complicated forms of recursion? No problem. For example, say f(x,ȳ,z) is a function of n+2 variables and g(ȳ) of n variables. Define

F(0,ȳ)	= g(ȳ)
F(n+1,ȳ)	= f(F(n,ȳ),ȳ,n)

So we’re allowing the new value to depend on a bunch of parameters ȳ, on the argument n, and of course on the previous value F(n,ȳ). This scheme is called primitive recursion. It’s handled the same way as the simpler case.

With this in our toolbox, we can define any so-called primitive recursive function. That’s any function you get by starting with a few very basic ones (projection, constant functions, successor) and applying composition and primitive recursion as many times as you like. So-called “course of values” recursions, where the new value depends on all values previously computed, also are available, since we can code the list of previous values using the finite sequence technique (see below). Sets and relations can be coded via functions taking the values 0 and 1; then we can use such relations in boolean conditionals (or more generally “definition by cases”) when defining new functions.

Loosely speaking, primitive recursive functions coincide with the computable functions where you can “clearly see” that the computations always terminate. To get the full panoply of recursive functions, we add the so-called μ-operator. This defines a partial function x̄↦y, like so:

μy(φ(y,x̄))	= the least y such that φ(y,x̄)
	undefined if there is no such y

It’s easy to express this in the language of PA:

μy(φ(y,x̄))=u ≡ φ(u,x̄)∧(∀z<u)¬φ(z,x̄)

Any function defined by applying the μ-operator to a primitive recursive relation is a partial recursive function. If a partial recursive function just happens to be total, it’s a recursive function. But we can’t (computably) tell in general if a partial recursive function is total—that’s the Halting Problem on steroids.

The “sequence trick” (see below) and the μ-operator together tell us that any partial recursive function is arithmetic. (That is, its graph is an arithmetic relation.) But these techniques go beyond this: if f and g are arithmetic or hyperarithmetic, then so is the F defined by the primitive recursion scheme or the μ-operator, even if f and g are horribly, hideously uncomputable.

Finite Sequences

As we’ve just seen, we need a way to code finite sequences of arbitrary length as single numbers. Gödel gave one technique: code (r₁,…,r_k) as p₁^r₁···p_k^r_k, where p_i is the i-th prime. But this works only once we have a definition of exponentiation, and of the function i↦p_i. Both these yield easily to recursion, but that requires a coding of finite sequences!

Gödel broke the vicious circle with the Chinese remainder theorem. This says that given any sequence of positive integers d₁,…,d_k, all pairwise coprime, and any sequence r₁,…,r_k with 0≤r_i<d_i for i=1,…,k, there is an a such that a%d_i=r_i for all i. Here % is the remainder function. We call the d_i’s divisors and the r_i’s remainders.

The Chinese remainder theorem is actually stronger: it says that there is a unique such a satisfying 0≤a<d₁···d_k. Although we won’t need the stronger version, it falls right out of the easiest proof of the theorem. Let d=d₁···d_k. Write [d] for the set {0,…,d−1}, likewise for [d_i]. We have a mapping [d]→[d₁]×…×[d_k] defined by a↦(a%d₁,…,a%d_k). The mapping is injective because the d_i’s are pairwise coprime: if a%d_i=a′ %d_i for all i, then d_i|(a−a′) for all i and so d|(a−a′). Since the domain and codomain both have d elements, the mapping is surjective. qed.

So if we are given a finite sequence (r₁,…,r_k), we just have to find divisors d_i such that they are pairwise coprime and r_i<d_i for all i. The sequence of divisors has to be “orderly”, in the sense that if we had to specify all the d_i’s individually, we wouldn’t have gained anything. Gödel chose the arithmetic progression d_i=bi+1, for a suitable b. It turns out that b works if it is a sufficiently large multiple of k!.

How do we use this to handle a quantifier like ∃(r₁,…,r_k)? Answer: first we define

β(a,b,i) = a%(bi+1)

Formally representing the remainder function is a piece of cake. Then

∃(r₁,…,r_k)…r_i…

is equivalent to

∃b∃a…β(a,b,i)…

I’ve been a bit sloppy with notation. The ∃b∃a causes no hiccups. I did not write ∃(r₁,…,r_k)φ(r₁,…,r_k). That would suggest a concrete list of k variables. But we want the subscript i in r_i to be variable as well. Gödel’s β function makes that possible. We’ll see an example next.

Bitstrings

Forcing in arithmetic uses bitstrings. First, we will regard a subset A⊆ℕ as an infinite bitstring, or equivalently, a function A:ℕ→{0,1}. Second, finite bitstrings will play the role of conditions: if p is a condition (i.e., finite bitstring) and an initial segment of A matches p, then we say A satisfies p. If the condition q extends p (or equals it), we write p≤q.

Suppose we have a sequence p₀≤p₁≤…, defined inductively, starting with an arbitrary condition p₀=c. In other words, we have a function f:ℕ×C→C, where C is the set of conditions, and for all n∈ℕ, p_n+1=f(n,p_n). Let A=⋃p_n; if the p_n’s stop growing at some point (i.e., for some n₀, we have p_n=p_n0 for all n≥n₀), then we make the rest of A all 0’s after that (i.e., n∉A for all n past the end of p_n0). Question: if f is arithmetic, or implicitly defined, or hyperarithmetic, can we say the same for A?

First, how do we code conditions? Using binary notation doesn’t quite do the trick: consider 0001 vs. 01, for example. Pairing a binary number with its length works: 〈k,b〉 where k is the length of the bitstring, and b is the bitstring in binary, padded out with leading 0’s if necessary.

A sketch of the formula ψ_S that represents x∈S:

ψS(x)≡	(∃ p0,…,pl)[
	p0=c
	∧ (∀n<l)[pn+1=f(n,pn)]
	∧ x∈pl]

Let’s look at the individual pieces:

• (∃ p₀,…,p_l): we make use of Gödel’s β function. Also, all the p_n’s are conditions; we have to make this explicit. I omit details.
• p₀=c: c will be a constant, incorporated into our formula.
• p_n+1=f(n,p_n): see below.
• x∈p_l: i.e., bit x in p_l is 1. This translates into a statement about the size of a remainder: b has a 1 in position x iff b=2^x+1·q+r with 2^x≤r<2^x+1.

Now, how about p_n+1=f(n,p_n), or in general, w=f(u,v)? If f is an arithmetic function, defined by a formula φ(w,u,v), then we just transcribe φ into our definition ψ_S(x) for A. So if f is arithmetic, then so is A. (Because of c, we have a definition of A for each initial condition c, with A satisfying c.)

Next, say f is implicitly defined, say by φ_F; F is a new function symbol added to ℒ(PA). (So φ_F is a closed formula of ℒ(PA+F).) Transcribing φ_F into the sketch above gives us a “paired” implicit definition. That is, {(f,A)} is definable by a closed formula in ℒ(PA+F+S), where we’ve added two new symbols. As you can imagine, it’s easy to combine f and A into a single function (or set), but that’s not the same as having an implicit definition for A by itself.

Finally, if f is hyperarithmetic, then so is A. We transcribe the Σ¹₁ or the Π¹₁ formula for f into the sketch, getting a formula ψ(x) in ℒ²(PA). The function (or set) quantifier can be migrated to the front, using basic facts of logic. So we have a Σ¹₁ and a Π¹₁ formula defining A.

Summary: if f is arithmetic, so is A; if f is hyperarithmetic, so is A; but if f is implicitly defined, then the best we can do is a paired implicit definition of A with f.

Prev TOC Next

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