we will fail. Implicit in the concept ancestor is the requirement that there are

only ¬nitely many intermediate relatives. But since there is no ¬xed, ¬nite

limit to how distant an ancestor can be, the Compactness Theorem guaran-

tees that there will be structures allowing in¬nitely distant ancestors.

These examples are explored in Exercises 19.30 and 19.31.

Chapter 19

The Compactness Theorem / 551

Exercises

19.24 Consider the following claims:

‚| Smaller than is irre¬‚exive.

Smaller than is asymmetric.

Smaller than is transitive.

Larger than is the inverse of smaller than.

1. Express these claims in a Tarski™s World sentence ¬le.

2. Verify that (the formal versions of) these claims are all veri¬ed as analytical truths by

the Ana Con routine of Fitch.

3. Give an informal argument to the e¬ect that these form a complete set of meaning

postulates for the sublanguage of the blocks language that contains only the predicates

Cube, Smaller, and Larger.

Submit your Tarski™s World ¬le and turn in your informal argument to your instructor. There

is no need to submit a Fitch ¬le.

The next three exercises refer to the following list of sentences. In each exercise, give an informal

argument justifying your answer.

1. ∀x ∀y ∀z [(Larger(x, y) § Larger(y, z)) ’ Larger(x, z)]

2. ∀x ∀y [Larger(x, y) ’ ¬Larger(y, x)]

3. ∀x ¬Larger(x, x)

4. ∀x ∀y [Larger(x, y) ∨ Larger(y, x) ∨ x = y]

∀y ∃¤12 x Larger(x, y)

5.

6. ∀y ∃x Larger(x, y)

19.25 How large is the 19.26 Show that any 19.27 Is there an in¬nite

largest ¬rst-order structure making 1“4 structure making 1“3

structure making 1“5 and 6 true is in¬nite. and 5 true?

true?

19.28 Let T be a set of ¬rst-order sentences. Suppose that for any natural number n, there is a

structure whose domain is larger than n that satis¬es T . Use the Compactness Theorem to

show that there is a structure with an in¬nite domain that satis¬es T . [Hint: Consider the

sentences that say there are at least n things, for each n.]

19.29 Let L be the language of Peano arithmetic augmented with the predicate NatNum, with the

intended interpretation is a natural number. Let T be the set of sentences in this language that

are true of the natural numbers. Let S be as in the proof of the non-standard model theorem.

Show that ¬NatNum(n) is not a ¬rst-order consequence of T ∪ S.

Section 19.7

552 / Completeness and Incompleteness

19.30 Suppose we add the monadic predicate Finite to the ¬rst-order language of set theory, where

this is meant to hold of all and only ¬nite sets. Suppose that T consists of the axioms of

zfc plus new axioms involving this predicate, insisting only that the axioms are true in the

intended universe of sets. Use the Compactness Theorem to show that there is a ¬rst-order

structure satisfying T and containing an element c which satis¬es Finite(x) but has in¬nitely

many members. [Hint: Add to the language a constant symbol c and in¬nitely many constants

b1 , b2 , . . .. Form a theory S that says that the b™s are all di¬erent and all members of c. Show

that T ∪ S is satis¬able.]

19.31 Use the Compactness Theorem to show that the ¬rst-order language with the binary predicates

Par(x, y) and Anc(x, y), meaning parent of and ancestor of, respectively, is not axiomatizable.

That is, there is no set of meaning postulates, ¬nite or in¬nite, which characterize those ¬rst-

order structures which represent logically possible circumstances. [Hint: The crucial point is

that a is an ancestor of b if and only if there is some ¬nite chain linking a to b by the parent

of relation, but it is logically possible for that chain to be arbitrarily long.]

Section 19.8

The G¨del Incompleteness Theorem

o

The theorem showing the existence of nonstandard models of arithmetic shows

a kind of incompleteness of fol. There is, however, a far deeper form of in-

completeness that was discovered by Kurt G¨del a few years after he proved

o

the Completeness Theorem. This is the famous result known as G¨del™s In-

o

completeness Theorem.

Students are sometimes puzzled by the fact that G¨del ¬rst proved some-

o

thing called the Completeness Theorem, but then turned around and proved

completeness vs.

incompleteness the Incompleteness Theorem. Couldn™t he make up his mind? Actually, though,

the senses of “completeness” involved in these two theorems are quite di¬erent.

Recall that the Completeness Theorem tells us that our formal rules of proof

adequately capture ¬rst-order consequence. The Incompleteness Theorem, by

contrast, involves the notion of formal completeness introduced earlier. Re-

member that a theory T is said to be formally complete if for any sentence S of

its language, either S or ¬S is provable from T . (We now know, by soundness

and completeness, that this is equivalent to saying that S or ¬S is a ¬rst-order

consequence of T .)

In the early part of the twentieth century, logicians were analyzing mathe-

matics by looking at axiomatic theories like Peano arithmetic and formal proof

systems like F. The aim was to come up with a formally complete axiomati-

zation of arithmetic, one that allowed us to prove all and only the sentences

Chapter 19

The Godel Incompleteness Theorem / 553

¨

that were true of the natural numbers. This was part of an ambitious project

that came to be known as Hilbert™s Program, after its main proponent, David Hilbert™s Program

Hilbert. By the early 1930s a great deal of progress had been made in Hilbert™s

Program. All the known theorems about arithmetic had been shown to follow

from relatively simple axiomatizations like Peano arithmetic. Furthermore,

the logician Moj™ esz Pressburger had shown that any true sentence of the

z

language not mentioning multiplication could be proven from the relevant

Peano axioms.

G¨del™s Incompleteness Theorem showed the positive progress was mis-

o

leading, and that in fact the goal of Hilbert™s Program could never be accom-

plished. A special case of G¨del™s theorem can be stated as follows:

o

Theorem (G¨del™s Incompleteness Theorem for pa) Peano Arithmetic is not

o G¨del™s Incompleteness

o

Theorem

formally complete.

The proof of this theorem, which we will describe below, shows that the

result applies far more broadly than just to Peano™s axiomatization, or just to

the particular formal system F . In fact, it shows that no reasonable extension

of either of these will give you a formally complete theory of arithmetic, in a

sense of “reasonable” that can be made precise.

We™ll try to give you a general idea how the proof goes. A key insight idea of proof

is that any system of symbols can be represented in a coding scheme like

Morse code, where a sequence of dots and dashes, or equivalently, 0™s and 1™s,

is used to represent any individual symbol of the system. With a carefully

designed coding system, any string of symbols can be represented by a string coding system

of 0™s and 1™s. But we can think of such a sequence as denoting a number in

binary notation. Hence, we can use natural numbers to code strings of our

basic symbols. The ¬rst thing G¨del established was that all of the important

o

syntactic notions of ¬rst-order logic can be represented in the language of representability

Peano arithmetic. For example, the following predicates are representable:

n is the code of a w¬,

n is the code of a sentence,

n is the code of an axiom of Peano arithmetic,

n and m are codes of sentences, the second of which follows from the

¬rst by an application of § Elim,

n is the code of a proof in F ,

n is the code of a proof of the sentence whose code is m.

When we say these predicates are representable in Peano arithmetic, we

mean something fairly strong: that the axioms and rules of proof allow us to

Section 19.8

554 / Completeness and Incompleteness

prove all and only the true instances of these predicates. So if p is a proof of

S and n and m are their codes, then the formal version of the last sentence

on our list would actually be a ¬rst-order consequence of the Peano axioms.

A lot of careful work has to be done to show that these notions are rep-

resentable in Peano arithmetic, work that is very similar to what you have

to do to implement a system like F on a computer. (Perhaps G¨del was the

o

world™s ¬rst real hacker.) But it is possible, and fairly routine once you get

the hang of it.

G¨del™s second key insight was that it is possible to get sentences that

o

express facts about themselves, relative to the coding scheme. This is known

as the Diagonal Lemma. This lemma states that for any w¬ P(x) with a single

Diagonal Lemma

free variable, it is possible to ¬nd a number n that codes the sentence P(n)

asserting that n satis¬es P(x). In other words, P(n) can be thought of as

asserting

This sentence has the property expressed by P.

Depending on what property P expresses, some of these will be true and some

false. For example, the formal versions of

This sentence is a well-formed formula

and

This sentence has no free variables

are true, while the formal versions of

This sentence is a proof

and

This sentence is an axiom of Peano arithmetic

are false.

Now consider the formal version of the following sentence, whose existence

the Diagonal Lemma guarantees:

This sentence is not provable from the axioms of Peano arithmetic.

This sentence (the one above, not this one) is called G, after G¨del. Let™s show

o

the G¨del sentence G

o

that G is true but not provable in pa.

Proof: To show that G is true, we give an indirect proof. Suppose G

is not true. Then given what it claims, it must be provable in pa. But

since the axioms of pa are true and F is sound, anything provable

Chapter 19

The Godel Incompleteness Theorem / 555

¨

from pa must be true. So G is true. This contradicts our assumption,

namely that G was not true. So G is indeed true.

Let us now show that G is not provable in pa. We have already shown

that G is true. But then, given what it claims, G is not provable.

G¨del™s Incompleteness Theorem follows immediately from this. We have

o

found a true sentence in the language of Peano arithmetic that is not provable

from the Peano axioms. What™s more, the negation of this sentence cannot be

provable, again because the provable consequences of the Peano axioms are

all true. So Peano arithmetic is not formally complete.

Of course there is nothing particularly sacred about the Peano axioms. applying theorem to

other theories

Having found a true but unprovable sentence G, we could always add it, or

something that would allow us to prove it, as a new axiom. The problem is

that these attempts to strengthen our axioms don™t escape G¨del™s argument,

o

since the argument does not depend on the weakness of Peano arithmetic, but

on its strength. As long as the axioms of the extended system T are true, and

the predicate

n encodes an axiom of T

is representable in T , G¨del™s whole argument can be repeated, generating

o

yet another true sentence that is unprovable in the extended system.

G¨del™s incompleteness result is one of the most important theorems in

o

logic, one whose consequences are still being explored today. We urge the in-

terested reader to explore it further. Detailed proofs of G¨del™s theorem can be

o

found in many advanced textbooks in logic, including Smullyan™s G¨del™s In-

o

completeness Theorems, Enderton™s Mathematical Introduction to Logic, and

Boolos and Je¬rey™s Computability and Logic.