Outer Limits of Reason (61 page)

Now let's use our fixed-point machine to make some interesting logical statements.

Tarski's Theorem

If our goal is to get a formula analogous to the liar paradox using math and logic, then let us assume that a predicate
Truth
(
x
) exists that expresses

Truth
(
x
)
≡ x
is the Gödel number of a true statement in Peano Arithmetic.

Use this supposed predicate and form:

F
(
x
) ≡ ~
Truth
(
x
).

In other words,
F
(
x
) will be true when
x
is the number of a statement that is not true. Place this
F
(
x
) into our fixed-point machine and get a logical sentence
T
such that

T
≡
F
(“
T
”) = ~
Truth
(“
T
”).

T
says that
T
is not true. Or in other words, we formed the logical sentence that says

“This logical sentence is not true.”

or

“I am false.”

Such a sentence is called a
Tarski sentence
. Let's analyze this logical sentence. If this sentence is true, then since it states that it is false, it is false. On the other hand, if the sentence is false, then since it states that it is false, it is, in fact, true. We have a genuine contradiction. Such contradictions are not permitted in the exact world of mathematics and logic! What went wrong? The only part that was at all troublesome was the assumption that a logical predicate
Truth
(
x
) exists.

The existence of
Truth
(
x
) ⇒ contradiction.

Since we do not permit contradictions, we must have that
Truth
(
x
) cannot exist. That is, we just proved a limitation of basic arithmetic: it cannot determine when its own statements are true or not. For purely logical sentences without arithmetic, we determine the truth or falsity of a statement with a truth table. But here we are not dealing with pure logic. Here we are dealing with mathematics and logic. And for that, it is not possible to use a truth table. Self-reference has handed us a limitation.

The Tarski statement is analogous to the famous liar paradox. Whereas the liar paradox uses English sentences, this uses exact logical sentences. We might be flippant about the meaning of English sentences and say that the liar paradox is like many other English sentences that are meaningless and/or contradictory. But we are going to have to be more careful about logic.

Gödel's First Incompleteness Theorem

We come now to one of the most celebrated theorems in twentieth-century mathematics. It expresses a shocking limitation of mathematics and logic.

Rather than examining truth, as in Tarski's theorem, let's examine provability. Let
Prove
(
y, x
) be a predicate that is true whenever

“
y
is the Gödel number of a proof of a statement whose Gödel number is
x
.”

Since our language is so exact and our encoding is so mechanical, this predicate actually exists. Unlike the
Truth
predicate, which does not exist, one can actually sit down and describe the
Prove
predicate. In broad strokes, the predicate must look at the number
y
and determine that it is the number of a proof. It then must verify that this proof actually proves the statement whose number is
x
. It would be extremely painful to go through all the steps, but it is done in many logic textbooks. Suffice it to say that, unlike the
Truth
predicate, the
Prove
predicate actually exists.

With the
Prove
predicate in hand, we can form the predicate

F
(
x
) ≡ (∀
y
) ~
Prove
(
y
,
x
).

That is,
F
(
x
) means that every single number
y
is
not
a proof of the statement
x
. In other words,
F
(
x
) is true if and only if no proof exists for the logical statement whose Gödel number is
x
. A fixed point for this
F
(
x
) is a sentence
G
such that

G
≡
F
(“
G
”) = (∀
y
)~
Prove
(
y
, “
G
”).

G
says that every single number
y
is not a proof of
G
. In English
G
says

“This logical statement is not provable”

or

“I am unprovable.”

Such a sentence is called a
Gödel sentence
. Let's analyze this statement. If
G
were provable, then since the statement says it is not provable, we proved a false statement. A good logical system like Peano Arithmetic cannot prove false statements. Let's assume then that the Gödel statement is
not
provable. That is exactly what the sentence says and hence makes it true. So the statement is true but not provable.
¹⁸

We just showed that

The Gödel sentence is provable ⇒ contradiction.

We can conclude that the Gödel sentence is unprovable and hence true. But we have to be a little careful here. It could be (although I assure you it is not) that Peano Arithmetic is inconsistent and can prove anything, including the Gödel sentence. While I am firmly convinced that Peano Arithmetic is consistent, we still have to state this assumption very carefully:

“If Peano Arithmetic is consistent, then the Gödel sentence is (unprovable and) true.”

We will revisit this statement in the next section.

Gödel's amazing result deserves much reflection. The “obvious” belief before Gödel came along was that for simple systems like arithmetic, whatever was true was also provable. That is, if a statement is true there must be some proof of it. This is shown in the left-hand diagram in
figure 9.20
.

Gödel showed that this view was wrong. There are sentences like
G
that are true but not provable. (We will see at the end of this section that
G
is not the only statement of this type.)

Parikh's Theorem

Rohit Parikh took Gödel's ideas further by pointing out some of the stranger aspects of the nature of proof. Consider the following predicate:

Prooflen
(
m, x
)
≡ m
is the length (in symbols) of a proof of the statement whose Gödel number is
x
.

For a given
m
and
x
, there is no problem determining if this predicate is true or false: simply go through all proofs of length
m
(there are a large but finite number of them) and see if any of the proofs end with a statement whose Gödel number is
x
. If such a proof exists, then the predicate is true. Otherwise, it is false.

Now, let
n
be a large number, and consider the predicate:

F
(
x
) ≡ ~(∃
m
<
n
Prooflen
(
m
,
x
)).

This predicate is true if there is no proof of
x
whose length is shorter than
n
. Applying the fixed-point machine to
F
(
x
) gives us a fixed point
P
such that

P ≡ F
(
“P”
)
≡ ~(∃m < n Prooflen
(
m, “P”
)).

That is,
P
is equivalent to the sentence that says it is false that there exists an
msuch that
m
is the length of a proof of
P
. In other words,
P
says

“This logical sentence does not have a proof shorter than
n.”

or

“I do not have a short proof.”

We call such a logical sentence a
Parikh sentence
.

Let us determine if this sentence is true or false. If
P
were false then a (short) proof of
P does
exist. But how can there be a proof of a false statement within a consistent system? So the sentence is not false and must be true. As we saw above with Gödel's incompleteness theorem, just because a statement is true, does not mean it is provable. Now let's consider the following relatively short proof that a (long) proof of the Parikh sentence exists:

If the Parikh sentence does not have a proof, then in particular it does not have a short proof. Then we can easily check all proofs less than
n
and see that none of them prove
P.
Summing up: if the sentence cannot be proved, then we can prove it.

This proof can be formulated in Peano Arithmetic and is fairly short. A Parikh sentence is an example of a sentence that has a very long proof, but a short proof of the fact that it has such a long proof. Strange but true!

Löb's Paradox

For our final use of the fixed-point machine we are going to go off the deep end and prove that every logical sentence—no matter how crazy—is provable. In particular, we will show that, as we long suspected, the moon
is
made of green cheese!

We saw that if
A
is a logical statement then
“A”
is the Gödel number that corresponds to
A
. One of the requirements of the arithmetization process is that we can also go the other way: given a number
x
that corresponds to a logical statement, we will refer to its corresponding logical statement as
|x|
. If we start with a logical sentence
A,
look at its number
“A”
, and then look at the number's logical sentence
|“A”|,
we return to the same logical sentence
A.
In symbols
|“A”|=A.

Let
M
(for moon) be any logical sentence. We will prove that
M
is always true.

Consider the predicate

F
(
x
) ≡ |
x
| →
M
.

F
(
x
) is true only if the logical sentence that corresponds to the number
x
implies
M
. Use the fixed-point machine on this predicate. A fixed point looks like

L
≡
F
(“
L
”) = (|“
L
”| →
M
) = (
L
→
M
) .

In other words,
L
says

“This logical sentence implies
M
”

and is called a
Löb sentence
. Assume, for a moment, that
L
is true. Then since
L
is the same as
L → M
, our assumption implies that
L → M
is also true. Since both
L
and
L → M
are true, then, by modus ponens,
M
is true. So, by assuming that
L
is true, we have proved that
M
is true. In other words, we have proved that
L
implies
M
and hence
L → M
is true. But
L → M
is equivalent to
L.
So
L
is true. We conclude that
M—
which stands for the fact that the moon is made of green cheese—is true.

We just proved that the moon is made of green cheese. This is ludicrous! What went wrong? The problem arises because we did not put a restriction on the formulas
F
(
x
) for which we are permitted to use the fixed-point machine. We saw in
section 4.4
that in order to avoid Russell's paradox of set theory, we had to restrict the axiom of comprehension. We also saw in
section 2.1
that some researchers insist that to avoid linguistic paradoxes we must adhere to a hierarchy of permitted English sentences. We must stay away from certain English sentences to steer clear of contradictions. In a similar way, here we must restrict the fixed-point machine in order to avoid proving false statements. Such a restriction might seem strange because the proof that the fixed-point machine works seems applicable to all
F
(
x
). But restrict we must lest we go beyond the bounds of reason.

 

Although we have stated all these limitations in the language of Peano Arithmetic, such phenomena can be described in much more general terms. Peano Arithmetic has all the usual arithmetic operations to code and decode logical statements as numbers. However, there are many other systems that allow one to talk about statements as numbers and numbers as statements. Once any such encoding is possible, we are going to have self-reference and hence similar limitations. It is worthwhile to state Gödel's incompleteness theorem in this general form:

In any “nice” logical system that has enough structure so that it can encode and decode its own statements, there will be self-reference and hence limitations. In particular, statements exist that are true but unprovable.