<<

. 7
( 10 .)



>>


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.

<<

. 7
( 10 .)



>>