<< Предыдущая стр. 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

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

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.

 << Предыдущая стр. 100(из 107 стр.)ОГЛАВЛЕНИЕ Следующая >>