where pn is the nth primes number.

Similarly, if σ1σ2 . . . σ is a sequence of sequences of symbols of LN ,

then the G¨del code of this sequence is

o

= ppσ1 q . . . ppσ q .

σ1 . . . σ 1 k

∀v1 = ·v1S0v1 = 25 313 56 7101113 138 177 1913 .

Example 17.1.

A particular integer n may simultaneously be the G¨del code of a

o

symbol, a sequence of symbols, and a sequence of sequences of symbols

of LN . We shall rely on context to avoid confusion, but, with some

45

46 17. CODING FIRST-ORDER LOGIC

more work, one could set things up so that no integer was the code of

more than one kind of thing.

We need to show that various relations and functions for recognizing

and manipulating G¨del codes are recursive.

o

Problem 17.1. Show that each of the following relations is prim-

itive recursive.

1. Term(n) ⇐’ n = t for some term t of LN .

2. Formula(n) ⇐’ n = • for some formula • of LN .

3. Sentence(n) ⇐’ n = σ for some sentence σ of LN .

4. Logical(n) ⇐’ n = γ for some logical axiom γ of LN .

Using these relations as building blocks, we will develop relations

and functions to handle deductions of LN . First, though, we need to

make “a computable set of formulas” precise.

Definition 17.3. A set ∆ of formulas of LN is said to be recursive

if the set of G¨del codes of formulas of ∆,

o

∆ = { δ | δ ∈ ∆},

is recursive. Similarly, ∆ is said to be recursively enumerable if ∆ is

recursively enumerable.

Problem 17.2. Suppose ∆ is a recursive set of sentences of LN .

Show that each of the following relations is recursive.

1. Premiss∆ (n) ⇐’ n = β for some formula β of LN which

is either a logical axiom or in ∆.

2. Formulas(n) ⇐’ n = •1 . . . •k for some sequence •1 . . . •k

of formulas of LN .

3. Inference(n, i, j) ⇐’ n = •1 . . . •k for some sequence

•1 . . . •k of formulas of LN , 1 ¤ i, j ¤ k, and •k follows from •i

and •j by Modus Ponens.

4. Deduction∆ (n) ⇐’ n = •1 . . . •k for a deduction •1 . . . •k

from ∆ in LN .

5. Conclusion∆ (n, m) ⇐’ n = •1 . . . •k for a deduction

•1 . . . •k from ∆ in LN and m = •k .

If ∆ is primitive recursive, which of these are primitive recursive?

It is at this point that the connection between computability and

completeness begins to appear.

Theorem 17.3. Suppose ∆ is a recursive set of sentences of LN .

Then Th(∆) is

1. recursively enumerable, and

2. recursive if and only if ∆ is complete.

17. CODING FIRST-ORDER LOGIC 47

Note. It follows that Th(∆) is an example of a recursively enu-

merable but not recursive set if ∆ is not complete.

48 17. CODING FIRST-ORDER LOGIC

CHAPTER 18

De¬ning Recursive Functions In Arithmetic

We will also need de¬nitions and results complementing those ob-

tained in Chapter 17: a set of non-logical axioms in LN which prove

enough to let us de¬ne all the recursive functions by suitable formulas

of LN . The non-logical axioms in question essentially just ensure that

basic arithmetic works properly.

Definition 18.1. Let A be the following set of sentences of LN ,

written out in o¬cial form.

∀v0 (¬ = Sv00)

1.

∀v0 ((¬ = v0 0) ’ (¬∀v1 (¬ = Sv1v0)))

2.

∀v0∀v1 (= Sv0Sv1 ’= v0v1 )

3.

∀v0 = +v00v0

4.

∀v0∀v1 = +v0Sv1S + v0 v1

5.

∀v0 = ·v000

6.

∀v0∀v1 = ·v0Sv1 + ·v0 v1v0

7.

∀v0 = Ev00S0

8.

∀v0∀v1 = Ev0Sv1 · Ev0v1v0

9.

Translated from the o¬cial forms, A consists of the following ax-

ioms about the natural numbers:

1. ∀x x + 1 = 0

2. ∀x x = 0 ’ ∃y y + 1 = x

3. ∀x∀y x + 1 = y + 1 ’ x = y

4. ∀x x + 0 = x

5. ∀x∀y x + y + 1 = (x + y) + 1

6. ∀x x · 0 = 0

7. ∀x∀y x · (y + 1) = (x · y) + x

8. ∀x x0 = 1

9. ∀x∀y xy+1 = (xy ) · x

Each of the axioms in A is true in N = (N, 0, S, +, ·, E). However,

they are a long way from being able to prove all the sentences of ¬rst-

order arithmetic true in N. For example, though we won™t prove it,

it turns out that A is not enough to ensure that induction works:

that for every formula • with at most the variable x free, if •x and

0

49

50 18. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC

∀y (•x ’ •x ) hold, then so does ∀x •. On the other hand, neither LN

y Sy

nor A are quite as minimal as they might be. For example, one could

do without E and de¬ne it from · and +.

It will be convenient to use a couple of conventions in what follows.

First, we will often abbreviate the term of LN consisting of m Ss fol-

lowed by 0 by S m 0. For example, S 3 0 abbreviates SSS0. We will use

S m 0 to represent the natural number m in LN . (The interpretation of

S m 0 in N will, in fact, be the mth successor of 0, namely m.) Second, if

• is a formula of LN with all of its free variables among v1 , . . . , vn , and

m0, m1, . . . , mn are natural numbers, we will write •(S m1 0, . . . , S mk 0)

for the sentence •v1m1 0,...,S mk 0 , i.e. • with every free occurrence of vi

...vn

S

replaced by S mi 0. Note that since the term S mi 0 involves no variables,

it must be substitutable for vi in •.

Definition 18.2. Suppose Σ is a set of sentences of LN . A k-place

function f is said to be representable in Th(Σ) = { „ | Σ „ } if there

is a formula • of LN with at most v1, . . . , vk , and vk+1 as free variables

such that

f(n1 , . . . , nk ) = m ⇐’ •(S n1 0, . . . , S nk 0, S m 0) ∈ Th(Σ)

⇐’ Σ •(S n1 0, . . . , S nk 0, S m 0)

for all n1 , . . . , nk in N. Such a formula • is said to represent f in

Th(Σ).

Similarly, a k-place relation P ⊆ Nk is said to be representable in

Th(Σ) if there is a formula ψ of LN with at most v1, . . . , vk as free

variables such that

P (n1 , . . . , nk ) ⇐’ ψ(S n1 0, . . . , S nk 0) ∈ Th(Σ)

⇐’ Σ ψ(S n1 0, . . . , S nk 0)

for all n1 , . . . , nk in N. Such a formula ψ is said to represent P in

Th(Σ).

We will use this de¬nition mainly with Σ = A.

Example 18.1. The constant function c3 given by c3(n) = 3 is

representable in Th(A); v2 = SSS0 is a formula representing it. Note

that that this formula has no free variable for the input of the 1-place

function in question, but then the input is irrelevant . . .

Almost the same formula, v1 = SSS0, serves to represent the set

” i.e. 1-place relation ” {3} in Th(A).

Example 18.2. The set of all even numbers is a 1-place relation is

representable in Th(A); ∃v0 v1 = S0 · v1 is a formula representing it.

18. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC 51

3

Example 18.3. The projection function π2 can be represented in

Th(A). v2 = v4 is one formula which represents π2 ; another is ∃v7 (v2 =

3

v7 § v7 = v4 ).

Problem 18.1. Suppose Σ and “ are sets of sentences of LN and

Σ “, i.e. Σ γ for every γ ∈ “. Then every function and relation

which is representable in Th(“) is representable in Th(Σ).

Problem 18.2. Suppose Σ is a set of sentences of LN and f is

a k-place function which is representable in Th(Σ). Then Σ must be

consistent.

It turns out that all recursive functions and relations are repre-

sentable in Th(A).

Problem 18.3. Show that the following functions are representable

in Th(A):

1. The zero function O(n) = 0.

2. The successor function S(n) = n + 1.

3. For every positive k and i ¤ k, the projection function πi .

k

Proposition 18.4. A k-place function f is representable in Th(A)

if and only if the k + 1-place relation Pf de¬ned by

Pf (n1 , . . . , nk , nk+1 ) ⇐’ f(n1 , . . . , nk ) = nk+1

is representable in Th(A).

Also, a relation P ⊆ Nk is representable in Th(A) if and only if its

characteristic function χP is representable in Th(A).

Proposition 18.5. Suppose g1 , . . . , gm are k-place functions and

h is an m-place function, all of them representable in Th(A). Then

f = h —¦ (g1 , . . . , gm ) is a k-place function representable in Th(A).

Proposition 18.6. Suppose g is a k + 1-place regular function

which is representable in Th(A). Then the unbounded minimalization

of g is a k-place function representable in Th(A).

Between them, the above results supply most of the ingredients

needed to conclude that all recursive functions and relations on the

natural numbers are representable. The exception is showing that func-

tions de¬ned by primitive recursion from representable functions are

also representable, which requires some additional e¬ort. The basic

problem is that it is not obvious how a formula de¬ning a function

can get at previous values of the function. To accomplish this, we will

borrow a trick from Chapter 14.

52 18. DEFINING RECURSIVE FUNCTIONS IN ARITHMETIC

Problem 18.7. Show that each of the following relations and func-

tions (¬rst de¬ned in Problem 14.9) is representable in Th(A).

1. Div(n, m) ⇐’ n | m

2. IsPrime(n) ⇐’ n is prime

3. Prime(k) = pk , where p0 = 1 and pk is the kth prime if k ≥ 1.

4. Power(n, m) = k, where k ≥ 0 is maximal such that nk | m.

5. Length(n) = , where is maximal such that p | n.

6. Element(n, i) = ni , where n = pn1 . . . pnk (and ni = 0 if i > k).

1 k

Using the representable functions and relations given above, we can

represent the “history” function of any representable function . . .

Problem 18.8. Suppose f is a k-place function representable in

Th(A). Show that

f (n1 ,...,nk ,0) f (n ,...,nk ,m)

1

F (n1, . . . , nk , m) = p1 . . . pm+1

m

f (n1 ,...,nk ,i)

= pi

i=0

is also representable in Th(A).

. . . and use it!

Proposition 18.9. Suppose g is a k-place function and h is a

k + 2-place function, both representable in Th(A). Then the k + 1-

place function f de¬ned by primitive recursion from g and h is also

representable in Th(A).

Theorem 18.10. Recursive functions are representable in Th(A).

In particular, it follows that there are formulas of LN represent-

ing each of the functions from Chapter 17 for manipulating the codes

of formulas. This will permit us to construct formulas which encode

assertions about terms, formulas, and deductions; we will ultimately

prove the Incompleteness Theorem by showing there is a formula which

codes its own unprovability.

CHAPTER 19

The Incompleteness Theorem

By pulling the material in Chapters 16“18 together, we can ¬nally

state and prove the Incompleteness Theorem.

Problem 19.1. Show that A is a recursive set of sentences of LN .

Problem 19.2. Show that the function

±

•(S k 0) if n = • for a formula • of LN

Sub(n, k) = with at most v1 free

0 otherwise

is recursive.

The key result needed to prove the Incompleteness Theorem is the

following lemma.

Lemma 19.3 (Fixed-Point Lemma). Suppose • is a formula of LN

with only v1 as a free variable. Then there is a sentence σ of LN such

that

A σ ” •(S pσq0) .

Note that σ must be di¬erent from the sentence •(S pσq0): there is

no way to ¬nd a formula • with one free variable and an integer k such

that •(S k 0) = k. (Think about how G¨del codes are de¬ned . . . )

o

With the Fixed-Point Lemma in hand, G¨del™s Incompleteness The-

o

orem can be put away in fairly short order.

Theorem 19.4 (G¨del™s Incompleteness Theorem). Suppose Σ is

o

a consistent recursive set of sentences of LN such that Σ A. Then Σ

is not complete.

That is, any consistent set of sentences which proves at least as

much about the natural numbers as A does can™t be both complete

and recursive. The Incompleteness Theorem has many variations and

corollaries; [11] is a good place to learn about many of them.