. 100
( 107 .)


ing is an ancestor of, then however we try to capture its meaning with axioms,
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


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)
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?
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
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
the Completeness Theorem. This is the famous result known as G¨del™s In-
completeness Theorem.
Students are sometimes puzzled by the fact that G¨del ¬rst proved some-
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
language not mentioning multiplication could be proven from the relevant
Peano axioms.
G¨del™s Incompleteness Theorem showed the positive progress was mis-
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:
Theorem (G¨del™s Incompleteness Theorem for pa) Peano Arithmetic is not
o G¨del™s Incompleteness
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
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
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
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

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


This sentence has no free variables

are true, while the formal versions of

This sentence is a proof


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
the G¨del sentence G
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
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,
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
yet another true sentence that is unprovable in the extended system.
G¨del™s incompleteness result is one of the most important theorems in
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
found in many advanced textbooks in logic, including Smullyan™s G¨del™s In-
completeness Theorems, Enderton™s Mathematical Introduction to Logic, and
Boolos and Je¬rey™s Computability and Logic.


. 100
( 107 .)