Definability Tools
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:
∀x1∀x2∃y1∃y2…
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 ℒ2(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 ℒ2(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 a0,…,ax:
| 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 (r1,…,rk) as p1r1···pkrk, where pi is the i-th prime. But this works only once we have a definition of exponentiation, and of the function i↦pi. 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 d1,…,dk, all pairwise coprime, and any sequence r1,…,rk with 0≤ri<di for i=1,…,k, there is an a such that a%di=ri for all i. Here % is the remainder function. We call the di’s divisors and the ri’s remainders.
The Chinese remainder theorem is actually stronger: it says that there is a unique such a satisfying 0≤a<d1···dk. Although we won’t need the stronger version, it falls right out of the easiest proof of the theorem. Let d=d1···dk. Write [d] for the set {0,…,d−1}, likewise for [di]. We have a mapping [d]→[d1]×…×[dk] defined by a↦(a%d1,…,a%dk). The mapping is injective because the di’s are pairwise coprime: if a%di=a′ %di for all i, then di|(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 (r1,…,rk), we just have to find divisors di such that they are pairwise coprime and ri<di for all i. The sequence of divisors has to be “orderly”, in the sense that if we had to specify all the di’s individually, we wouldn’t have gained anything. Gödel chose the arithmetic progression di=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 ∃(r1,…,rk)? Answer: first we define
β(a,b,i) = a%(bi+1)
Formally representing the remainder function is a piece of cake. Then
∃(r1,…,rk)…ri…
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 ∃(r1,…,rk)φ(r1,…,rk). That would suggest a concrete list of k variables. But we want the subscript i in ri 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 p0≤p1≤…, defined inductively, starting with an arbitrary condition p0=c. In other words, we have a function f:ℕ×C→C, where C is the set of conditions, and for all n∈ℕ, pn+1=f(n,pn). Let A=⋃pn; if the pn’s stop growing at some point (i.e., for some n0, we have pn=pn0 for all n≥n0), then we make the rest of A all 0’s after that (i.e., n∉A for all n past the end of pn0). 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:
- (∃ p0,…,pl): we make use of Gödel’s β function. Also, all the pn’s are conditions; we have to make this explicit. I omit details.
- p0=c: c will be a constant, incorporated into our formula.
- pn+1=f(n,pn): see below.
- x∈pl: i.e., bit x in pl is 1. This translates into a statement about the size of a remainder: b has a 1 in position x iff b=2x+1·q+r with 2x≤r<2x+1.
Now, how about pn+1=f(n,pn), 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 Σ11 or the Π11 formula for f into the sketch, getting a formula ψ(x) in ℒ2(PA). The function (or set) quantifier can be migrated to the front, using basic facts of logic. So we have a Σ11 and a Π11 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.













