Outer Limits of Reason (62 page)

There are systems of logic that are very “weak” in that they cannot encode their own statements. These systems will not have self-referential limitations and hence Gödel's incompleteness theorem will not apply to them. Such systems are called
complete
because every statement that is true has a proof. An example of such a complete system is
Presburger Arithmetic
, which is a logical system that only deals with addition and does not have enough power to deal with multiplication and other operations. Another example is a certain logical system that deals with basic geometry, which is also not powerful enough to encode its own statements. There is something a bit paradoxical here. Systems that are so weak that they cannot encode their own statements have the strength that everything that is true is provable. In contrast, a system that has the strength to encode its own statements has the weakness that it has true but unprovable statements.

In this section we have described several true but unprovable mathematical statements. One might think that only these few “pathological” mathematical statements are problematic and that most “regular” true mathematical statements can be proved. A little counting argument will show us that this is not so.
¹⁹

Consider all the subsets of the natural numbers. As we saw in 
section 4.3
, there are uncountably infinite such subsets. If
S
is a subset of the natural numbers and
x
a natural number, then exactly one of the following two mathematical facts is true:

x
is an element of
S
      or      
x
is not an element of
S.

Since there are uncountably infinite subsets of the natural numbers, such true facts about numbers are uncountably infinite. This is all about mathematical facts—not about what can be stated. A mathematical statement is a mathematical fact that can be put into symbols. We saw above that arithmetization is a correspondence between mathematical statements and the natural numbers. This implies that there are countably infinite mathematical statements. Hence there are massively more mathematical facts than mathematical statements.

Gödel's theorem takes this further. The entire purpose of his incompleteness theorem is to show that the set of provable mathematical statements is a proper subset of all mathematical statements, as in
figure 9.21
.

Since there is a natural number for every proof, the set of provable mathematical statements is also countably infinite. Cristian S. Calude, together with several others, recently proved that even within the set of all true mathematical statements, the ones that are provable are rarities. We conclude that although mathematical proofs can prove a countably infinite number of true statements, there are immensely more true mathematical statements and facts that are unprovable and, hence, beyond rational thought.
²⁰

Gödel's shocking theorem was that a true but unprovable sentence exists in Peano Arithmetic. Although the Gödel sentence was the first example of such a sentence, there is a feeling that it is a bit “contrived” or “unnatural” and not “real mathematics.” As we showed, there are countably infinite statements that are also true but unprovable in Peano Arithmetic. It would be nice to see more such statements that are “natural” and look like “real mathematics.” One such statement is
Goodstein's theorem
.

First some background. Any number can be written as a sum of powers of 2. For example,

• 19 = 2
⁴
+ 2
¹
+ 1

• 87 = 2
⁶
+ 2
⁴
+ 2
¹
+ 1

• 266 = 2
⁸
+ 2
³
+ 2
¹

Let's look at 266 more carefully. The exponents can also be written as powers of 2:

The number is now totally expressed with numbers of 2 or less. This way of writing numbers is called “hereditary base-2 notation.” We are now going to perform a two-step process as a way of expressing 266:

• Step (a):  Increment the base from 2 to 3 in the expression.

• Step (b):  Subtract 1 from the whole number.

This gives us

This number is about 10
³⁸
. The two-step process can be iterated by changing all 3s to 4s:

And once again:

Each time, we are incrementing the base by 1 and subtracting 1. As you can see, the numbers increase wildly. You could imagine that if you continue this process, the numbers will simply continue to grow and grow. Or would they? In 1944, English mathematician Reuben Goodstein (1912–1985) proved the following remarkable theorem:

Take any number, write it in hereditary base 2 notation and then iterate the following two-step procedure: (a) change all the
n
's in hereditary base
n
notation to
n
+ 1's and (b) subtract 1. Eventually the result will hit . . . zero!

That is, instead of the number getting bigger and bigger, it eventually—after a very long time—will start going down and will eventually go all the way down to zero. This is shocking. Of the two steps in our procedure, one step massively increases the number and the other step simply subtracts 1. Our intuition tells us that this sequence of numbers will simply get bigger and bigger. Our intuition is wrong! The numbers will “eventually” start getting smaller. The number of iterations this will demand is immense, but it will, nevertheless happen. Goodstein proved this amazing theorem using infinitary methods and the full power of set theory. In 1982, Laurie Kirby and Jeff Paris demonstrated that this theorem can only be proved using such infinitary methods and that although the theorem can be stated in the language of Peano Arithmetic, it cannot be proved in that system. The numbers simply get too big for that system. So Goodstein's theorem, like Gödel's sentence, is true but unprovable in Peano Arithmetic.

9.5  Axioms and Independence

Let's move on and use Gödel's first incompleteness theorem to obtain more results. We found that the Gödel sentence,

“This logical statement is not provable.”

is unprovable and hence true. We actually proved that

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

This fact can be formalized and proved within Peano Arithmetic. That means we can write a proof of what we did in the last section within the language of Peano Arithmetic. This proved statement is written as the following implication:

“Peano Arithmetic is consistent” → “The Gödel sentence is true.”

Assume we can prove that “Peano Arithmetic is consistent” within Peano Arithmetic. Then we would have the following deduction in Peano Arithmetic:

“Peano Arithmetic is consistent”

“Peano Arithmetic is consistent” → “The Gödel sentence is true.”

“The Gödel sentence is true.”

That would be a proof in Peano Arithmetic that the Gödel sentence is true. But Gödel's sentence says that no such proof can exist! There must be something wrong with our assumption. The only statement we assumed was that Peano Arithmetic can prove its own consistency. This leads us to Gödel's second incompleteness theorem:
Peano Arithmeti
c cannot prove its own consistency. That is, using basic arithmetic one cannot prove that basic arithmetic is consistent.

It is important to notice that Gödel's second incompleteness theorem was proved piggybacking on Gödel's first incompleteness theorem. The first theorem is the implication:

The Gödel sentence is provable in Peano Arithmetic ⇒ contradiction.

In this section, we showed the implication:

“Peano Arithmetic is consistent” is provable in Peano Arithmetic

⇒ The Gödel sentence is provable in Peano Arithmetic.

Combining these two implications gives us

“Peano Arithmetic is consistent” is provable in Peano Arithmetic ⇒ contradiction.

We conclude that “Peano Arithmetic is consistent” is
not
provable in Peano Arithmetic.

We just showed that the statement “Peano Arithmetic is consistent” cannot be proved in Peano Arithmetic. But is the statement true? Can it possibly be false? Are we really to believe that arithmetic is not consistent? Will someone one day prove that 2 + 2 is not 4? Fear not, dear reader. In 1935, Gerhard Gentzen (1909–1945) proved that the stronger axiom system of Zermelo-Fraenkel set theory with choice (ZFC)
does
prove the consistency of arithmetic. In detail, since we can interpret arithmetic within ZFC, and since that system has the ability to deal with the more powerful ideas of infinity, it can prove the consistency of Peano Arithmetic. In other words, a simple “finitistic” proof of the consistency of arithmetic does not exist but there is an “infinitary” proof of it. Gentzen proved that if ZFC is consistent, then so is Peano Arithmetic.
²¹
There is one small problem: Who says ZFC is consistent?