Outer Limits of Reason (63 page)

Gödel's second incompleteness theorem actually says something much more. There is nothing special about Peano Arithmetic in our discussion. We said that Gödel's first incompleteness theorem was true for any axiom system that can encode its own statements. By using the same reasoning we used at the beginning of this section, we can also extend Gödel's second incompleteness theorem to any axiom system that can encode its own statements. ZFC is such a system. Hence, by Gödel's second incompleteness theorem, ZFC cannot prove its own consistency.

This is rather troubling! Most of modern mathematics can be formulated in ZFC. It would be nice to know that the axiom system of ZFC is consistent and that no contradictions can be found. Alas, no such proof exists within ZFC. Researchers have constructed other, more powerful axiom systems that can prove the consistency of ZFC. These systems consist of the ZFC axioms and potent “axioms of infinities.” These new axioms are not used in the typical mathematics. They have an unnatural, ad hoc feel to them. Unlike the usual axioms of ZFC, it is hard to tell if these other axioms are true or not. They are not self-evident. But, even with these new powerful axioms, we do not have a system that can prove its own consistency. One always has to go to a stronger system.

In the last section we saw that Goodstein's theorem is a “natural,” “uncontrived” mathematical result that is beyond the ability of Peano Arithmetic to prove but is nevertheless true and provable in ZFC. Analogous to that result, Harvey Friedman has come up with several “natural,” “uncontrived” mathematical statements that are beyond the ability of ZFC to prove but are nevertheless true in stronger systems.

Figure 9.22
summarizes some of our findings.

Peano Arithmetic cannot prove the consistency of Peano Arithmetic (Con
_PA
). ZFC can prove the consistency of Peano Arithmetic but cannot prove the consistency of ZFC (Con
_ZFC
). We can always build stronger systems that can prove the consistency of ZFC, but these stronger systems will also not be able to prove their own consistency. We can go on forever. This conforms to one of the central themes of this book: any self-referential system, no matter how powerful, is somewhat limited.

Do not worry that modern mathematics or even basic arithmetic is inconsistent. I assure you that they are consistent. Arithmetic has been around for millennia and no one has ever found an inconsistency. There are millions of people working in modern mathematics and no inconsistency has ever been found. Nevertheless, it is unnerving that proving the consistency of the logical systems that are at the foundation of mathematics and science is beyond the bounds of reason.

In a sense, one can view Gödel's theorems and their consequences as a criticism of the axiomatic method. Mathematicians have always looked for axioms in order to find the fewest and simplest statements that imply all the other statements. But Gödel has shown us that no matter how many axioms are added, there will always be something missing. That is, there will always be statements that are true but cannot be proved using those axioms. Much of mathematics can be done without axioms. The vast majority of mathematicians do not work with axiom systems. They simply follow the rules they have learned. It is logicians and set theorists who keep their eyes on what assumptions are used. Even Cantor, the founder of modern set theory, did not prove his theorems using axioms. Rather, the axioms of Zermelo Fraenkel set theory were formulated
after
Cantor did his work. Cantor simply used his intuition.

Another criticism of the axiom system is the way that set theorists seemingly add axioms to make stronger and stronger systems beyond ZFC. The usual axioms of Peano Arithmetic and ZFC seem obvious (or as Thomas Jefferson and his colleagues wrote, “We hold these truths to be self- evident”). The Peano Arithmetic axiom that distinct numbers have distinct successors is obvious to any five-year-old. The ZFC axiom that given a set, its powerset also exists, is obvious. In contrast, certain axioms of infinity that set theorists work with are not self-evident or obvious. They are added because they don't seem to contradict the other axioms and are useful in proving certain theorems. This may feel to some like cheating: we are simply adding axioms that we find useful.

On the other hand, without axioms where would we be? We might stumble into contradictions. Although no sufficiently strong axiom system is complete, with axioms we can at least see the hierarchy of different systems. We can say that ZFC is more powerful than Peano Arithmetic because we can compare their axioms. The power of mathematics is that it is firmly based on axioms and not based on mere human intuitions.

 

There is something slightly disingenuous about the mathematical limitations discussed in this chapter: they are not really limitations, but merely stumbling blocks. There are ways of getting around them. For every limitation
of a mathematical system
, some larger, more powerful system exists that overcomes the limitations:

• We saw that it is impossible to trisect an angle
with a straightedge and a compass
; however it is very easy to perform this task with a simple measuring stick. Measure the angle and divide it by three. With the same amount of ease, we can similarly square the circle and double the cube.

• Galois theory determines when certain equations are unsolvable
using the operations of addition, multiplication, division, and roots
. However, there are calculus-based methods that can always solve such equations.

• Gödel's first incompleteness theorem says that certain statements are true but unprovable
in some finite arithmetical system
. But we saw that the same statements are provable in stronger systems.

• Gödel's second incompleteness theorem says that the consistency of a finite arithmetical system is unprovable
within that system
. Gentzen showed that the consistency is provable in the stronger system of ZFC.

• The consistency of ZFC (as the continuum hypothesis and the axiom of choice that we met in 
section 4.4
) is not provable
within ZFC
. However, there are larger systems in which it is provable.

• For any system larger than ZFC, there are statements that are not provable
in that system
, but there will always be larger systems.

We call these limitations
relative limitations
, as opposed to
absolute limitations
that can never be solved in any mathematical system. Are there any known absolute limitations? That is, are there any mathematical statements that are true but no human being can ever show that they are true no matter how much ingenuity is applied? Note that even if such a statement did exist, we would never be able to prove or know that it was such a statement since to prove a statement is unprovable but true would mean that we proved it is true. So an absolutely unsolvable problem is a problem that we can never prove, and we can never know that we can never prove. This makes the question of their existence somewhat metaphysical since whether or not they exist is something we can never know.

In contrast to mathematical limitations, the computational limitations discussed in
chapter 6
and in
section 9.3
are, in a sense, absolute. We showed that no computer or mechanistic method can solve certain problems. There are no known better machines that can solve these problems. Even quantum computers, when they come into existence, cannot do more than what regular computers can do. (Their power is their speed at doing what regular computers already can do, not that they can solve unsolvable problems.) The absoluteness of computational limitations comes from the fact that we really know what computers are all about.
²²
This is in contrast to our limited knowledge of the nature of human consciousness and reason.

Gödel summarized the past two paragraphs by positing that either (a) absolutely unsolvable problems exist or (b) the human mind with its seemingly unlimited capacity for ingenuity “infinitely surpasses the powers of any finite machine.” In other words, if the human mind is just a machine, then it will have the same limitations as machines and finite systems. In that case, (a) will be true and the human mind will also have problems that are absolutely unsolvable. By contrast, if the human mind can always solve any problem, then (b) will be true and the mind must be stronger than any computer or finite axiom system that has limitations.

Let us (somewhat hesitatingly) accept these two choices as the only possible options. Which of these alternatives should we believe? It occurs to me that as we learn more and more about the human brain and as cognitive science continues to make progress in understanding how the mind works, we will have no choice but to accept that (a) the brain/mind works in a mechanical way. The human brain is probably the most complicated machine in the entire universe and we are hundreds of years away from actually understanding how the human brain works. Nevertheless, from what we have seen of the workings of the brain, there does not seem to be any mysterious process that would give the human mind powers to “infinitely surpass” a finite physical process. It seems plausible to accept that there are absolute limitations on the abilities of the human brain, as there are absolute limitations on any computing device and any physical machine. Even in the world of pure mathematics, there are limitations of reason.

Further Reading

Section 9.1

The beautiful proof of the irrationality of the square root of 2 was first shown to me by Leon Ehrenpreis. He heard it from Stanley Tenenbaum, who seems to have developed it himself. Eves 1976, Kramer 1970, and Kline 1980 have more about classical limitations.

Section 9.2

A fascinating biography of Galois can be found in chapter 20 of Bell 1937. While many parts of Bell's book have been shown to be stretching the truth, it is still fun to read. Stewart 2003 is a good place to start learning about Galois theory. For math students, good places to learn about Galois theory include chapter 15 of Birkhoff and Mac Lane 1957 and chapter 4 of Jacobson 1985.

Section 9.3

Goodman-Strauss 2010, 2011, are two beautiful articles with many pictures on tilings. The basics on undecidable problems are included in any textbook on theoretical computer science, such as chapter 6 of Cutland 1980. A nice presentation of Hilbert's tenth problem can be found in Davis and Hersh 1973. The use of mattress reorientations as a way of introducing group theory was shamelessly taken from Hayes 2008. A further discussion of undecidability in physics can be found in Pour-El and Richards 1989.

Section 9.4

The theorems of Tarski and Gödel are covered in any logic book—for example, in section 3.5 of Mendelson 1997, chapters 2 and 7 of Manin 2010, or chapter 17 of Boolos, Burgess, and Jeffrey 2002. A readable and complete proof is included in Van Heijenoort 1967. For a short, modern approach and the latest developments, see Davis 2006, Bunch 1982, and Hofstadter 1979. The amazing result about lengths of proofs can be found in Parikh 1971, 496. All the results are also included in Yanofsky 2003.

Goodstein's theorem was taken from Kirby and Paris 1982.

Section 9.5

You can read about some of the implications of Gödel's theorem in Kline 1980. However, be mindful of coming to wild conclusions with regard to Gödel's incompleteness theorems. Much nonsense has been published on the topic. Torkel 2005 and Berto 2009 provide antidotes.

10

Beyond Reason

The eternal silence of these infinite spaces fills me with dread.
¹

—Blaise Pascal

At the present time I seem to be thinking rationally again in the style that is characteristic of scientists. However this is not entirely a matter of joy as if someone returned from physical disability to good physical health. One aspect of this is that rationality of thought imposes a limit on a person's concept of his relation to the cosmos.
²

—John Nash

The meaning of the world is the separation of wish and fact. Wish is a force as applied to thinking beings, to realize something. A fulfilled wish is a union of wish and fact. The meaning of the whole world is the separation and the union of fact and wish.
³

—Kurt Gödel

We have come to the end of our journey. It is time to sum up some of our findings and try to make sense of our explorations. In
section 10.1
I categorize the different types of limitations that we have considered.
Section 10.2
discusses the definition of reason. I
conclude
by looking at what, if anything, is beyond the limitations of reason.

10.1  Summing Up

Every chapter of this book has discussed a different subject and its limitations. There are, however, other ways to categorize the myriad limitations we have found. Here I give another classification of four types of limitations on reason.