Outer Limits of Reason (20 page)

The axiom of choice says that for any given set and any partition of that set into nonoverlapping subsets, a set can always be formed with one representative from every subset. This seems like a pretty innocuous requirement. The axiom of choice seems obviously true for finite sets but is slightly more problematic for infinite sets. Is it obvious that such a set can always be formed? Why should we not be able to form such a set? In 1963, Paul Cohen showed that not only is the continuum hypothesis independent of Zermelo-Fraenkel set theory, but the axiom of choice is also independent of those axioms. That is, we cannot prove it or disprove it with Zermelo-Fraenkel set theory.

Many mathematicians think that the axiom of choice is “self-evident” enough and should be added to the axioms of Zermelo-Fraenkel set theory to make a foundation for set theory and mathematics. They call this new axiom system
Zermelo-Fraenkel set theory with choice
or
ZFC
. It is the most popular foundational system in all of mathematics. Other mathematicians are more circumspect and worry about including the axiom of choice.

One of the major reasons for the suspicion about the axiom of choice is the
Banach-Tarski paradox
. This paradox says that with Zermelo-Fraenkel set theory and the axiom of choice (but not Zermelo-Fraenkel set theory alone) one can prove the following: given a three-dimensional ball of any size, one can chop the ball into five nonoverlapping pieces and put them together again into two balls
each of the same size as the original
. (See
figure 4.10
.)

The pieces that the original ball is chopped into are not your typical sane pieces. Rather, they will look like something that was done by Zeno while under the influence of psychedelic drugs. Each piece will be connected but very bizarre looking. Nevertheless, this fact is a provable consequence of the seemingly harmless axiom of choice. Another version of the paradox says that a sphere as small as a pea can be cut up into a finite set of different parts and then be put together to form a sphere the size of the sun. Many people say that since this paradox is the consequence of the axiom of choice, this axiom leads to an obvious false statement and should be excluded from what is reasonable. They want to banish the axiom of choice from mathematics. Others say that we should keep the axiom. They might appeal to Zeno's paradoxes that show that our concept of space is full of counterintuitive properties. Similarly, infinity has some strange mind-bending consequences. After all, as we saw in
section 4.2
, one infinite set can be put into correspondence with another set that is twice its size (even numbers with natural numbers, and natural numbers with positive and negative integers), so why can't an infinitely divisible ball have the same volume as two infinitely divisible balls?
¹⁰

What are we to do with all these questions? Is Zermelo-Fraenkel set theory consistent or not? Is the continuum hypothesis true or false? Is the axiom of choice acceptable or unacceptable? These questions are independent of Zermelo-Fraenkel set theory, which is a basis of most of mathematics. So we cannot use mathematics to answer these questions. The answers to all of these simply stated questions are beyond contemporary mathematics, beyond rational thought, and perhaps even beyond us.

There are two broad philosophical schools of thought on how to deal with these questions. On the one hand there are Platonists or realists, who, following Plato, believe that in some sense sets really exist and that all these questions, as well as any other questions about mathematical objects, have definite answers. Mathematical objects and the theorems that describe the relationships of these objects are real and exist independently of human thought. Platonists believe that there are perfect ideal circles and that the ratio of the circumference to the diameters of these circles is π. If no human being ever existed and thought about numbers, π would still exist. To Platonists, whether or not the continuum hypothesis stands—that is, whether there really is a set between
N
and (0,1)—is something that is either true or false and human beings must venture to answer this question. Since the given axioms cannot answer the question, one must search for more or different axioms that would settle it once and for all. These axioms should somehow be self-evident, not cause contradictions, and not bring us to counterintuitive consequences.

In contrast to that school of thought, people at the other extreme are sometimes called nominalists, anti-Platonists, antirealists, formalists, or fictionalists.
¹¹
They, in essence, do not believe that there is anything “out there.” Mathematical objects are things that mathematicians talk about and that do not have any existence outside of language and human minds. The number 3 does not exist any more than other human-made fictional creations like Mickey Mouse or James Bond. To such philosophers, the reason the questions posed in this section do not have answers is that not enough about these mathematical objects has been described. To a nominalist, the mathematical objects do not really exist, only human descriptions exist. There are certain rules about mathematical objects just as there are certain rules about Mickey and Bond. One would never say that Mickey can be mean, because that would not conform to the fictional character we all grew up with. Similarly, we would never say that Bond was dressed like a slob. When it comes to mathematical objects, they seem more real because there are many more rules about them. So while it is conceivable, but improbable, that Bond would have his shirt untucked in a movie sequence, it is totally impossible for 3 + 2 to equal 6. Returning to our question about the continuum hypothesis: a nominalist would say that the language of sets has not been described well enough for one to make a judgment about the existence of such an intermediate set. Why look for new axioms that make the continuum hypothesis either true or false? There is no external reality to which our axioms must conform. Rather, we should study both systems: we should study Zermelo-Fraenkel set theory with the continuum hypothesis being true and Zermelo-Fraenkel set theory with the continuum hypothesis being false. Both systems are worthy of study. We have the independence, let us use it!
¹²

Some of the clashes between these two schools can be summarized by the answer to the following simple question: Are theorems of mathematics “discovered” or “invented”? The Platonists insist that the theorems and the objects that they are dealing with have always been there and always will be there. To them, a mathematician discovers what has always existed. In contrast, a nominalist would say that a mathematician invents a new theorem. The theorem has to conform to the rest of the known knowledge about some mathematical object, but he or she is nevertheless adding to the fictitious literature, as it were. Informal surveys have shown that the majority of mathematicians are, in fact, Platonists and feel like they are discovering while working. However, since this is a philosophical question and not a mathematical one, perhaps their opinion should not be taken as authoritative.

Do infinite sets exist? Does the number 3 exist? I have never seen an infinite set nor have I ever stubbed my toe against the number 3. We can talk about infinite sets, but I can talk about unicorns and Pinocchio as well. I can also tell a very long, logical, and plausible tale about Little Red Riding Hood even though she never existed outside a human mind. Can we claim the same nonexistence for the set of natural numbers with all its structure that is seemingly so real? Is the sequence 0, 1, 2, 3, . . . simply an invention of language and culture? Perhaps we are confused by the many possible meanings of the word
exist
? It is hard to imagine that these seemingly obvious ideas about natural numbers are simply a part of language and do not really exist in some true sense. Nevertheless, language, and the culture that governs the way we use language, seems sufficient to explain how we use numbers.

The strongest argument for Platonism is the amazing consistency of mathematics. For thousands of years, mathematicians have been working in isolation from each other and have come to similar, noncontradictory ideas. It seems that the only way this is possible is that they are all trying to describe something that is external to their mind.

The strongest arguments for nominalism are questions like the following: Who set up these Platonic ideals? Why are they there? For the past several hundred years, scientists have made steady progress by eliminating metaphysical presuppositions. Why keep any such metaphysics in mathematics and in set theory? A nominalist would counter a Platonist's proof by saying that the mathematicians are not all isolated from each other. Before they entered their lonely writer's garret, they were all aware of the rules for being a good mathematician. They knew that if they were to write anything that would cause a contradiction, they would lose their status as a mathematician. They were not isolated because they knew the language beforehand.

One issue that bothers both camps is the incredible usefulness of mathematics and set theory in the physical sciences. Why does the physical world somehow conform to the ideas of mathematicians and set theorists? The Platonists say that there is some type of (mysterious) connection between the Platonic realm of ideas and our physical world. They also posit some type of (mysterious) connection between the Platonic realm and our minds that permits us to discover these Platonic ideals. In contrast, nominalists say that the reason mathematics works so well is that mathematics was a language formed by humans with the intuition they received from the physical world. To them, it is not shocking that a system developed while observing the physical world should be suited to the physical world.
¹³

Do not think that one can easily come to the “correct” choice between these two camps. The two giants who worked out the independence of the continuum hypothesis came to different conclusions. Gödel felt that we have to find new axioms that will somehow capture the Platonic world of sets. In contrast, Cohen felt that there is no real answer to the continuum hypothesis.
¹⁴

These battles have raged for millennia with no apparent victor. To me, any argument that Platonists give can be answered better by the nominalists. However, I am aware that we, mere mortals, are not going to come to any firm conclusions.

Further Reading

Sections 4.1–4.3

The material in the first three sections can be found in many places. There are portions of popular history books such as chapter 24 of Kramer 1970 or section 15–4 of Eves 1976. There are also other nontechnical books like Kline 1980 and Rucker 1982. Two technical places to look are section 13.3 of Ross and Wright 2003 and section 3.4 of Truss 1998. Most of the ideas can also be found in any calculus text.

Joseph Dauben has written a fantastic biography of Georg Cantor. Although Cantor's work seems obvious to us now, in his lifetime, it was considered radical and unacceptable by many of his fellow mathematicians. Cantor suffered tremendously for holding fast to his ideas. Dauben 1979 describes Cantor's life and work in great detail.

The story of Hilbert's hotel can be found in Gamow 1988.

Section 4.4

For Russell's letter to Frege, see Van Heijenoort 1967, 124–125.

The Zermelo-Fraenkel set theory axioms were taken from chapter 1 of the authoritative Jech 1978 and chapter 2 of Devlin 1993.

Wapner 2007 is a very clear presentation of the Banach-Tarski paradox for the layperson.

One can read about the different types of Platonism in Wang 1996 and more about fictionalism in Balaguer 2008 and Eklund 2007.

Gödel presents his views on Platonism in his popular article, Gödel 1947. Cohen's anti-Platonism can be seen in the last section of Cohen 2005.

To learn more about the infinite and the paradoxes of set theory, see Rucker 1982 and Lavine 1994. Cohen 2005 also has many deep ideas related to our theme of the limits of formal reasoning.

There is a nice BBC Horizon documentary titled
To Infinity and Beyond
that covers some of these topics. For more information on the documentary, go to
http://www.bbc.co.uk/programmes/b00qszch
.

5

Computing Complexities

The guiding motto in the life of every natural philosopher should be, seek simplicity and distrust it.

—Alfred North Whitehead (1861–1947)

I do not like paradoxes, and I consider those who like them to be lacking in culture and intelligence.

—Rashid al-Daif
¹

A fool can throw a stone into the sea and ten wise men will not be able to retrieve it.

—Yiddish proverb

Computers are paragons of reason. They are heartless machines that relentlessly obey the laws of logic. There is nothing emotional or wishy-washy about computers: they do exactly as they are told by following the dictates of logic. It is from the perspective of computers as engines of reason that we examine these machines and determine what tasks they can and cannot perform. We all have an intuition as to what computers can do and what they can do with ease. They have no problem summing a list of numbers, nor do they have a problem sorting through myriad records or other simple tasks. However, it is surprising to learn that there are some easily stated problems that computers cannot satisfactorily solve. In this chapter I look at several problems that computers can theoretically solve, but that in practice would require an immense amount of time and resources. I also explain why these problems seem so hard and why researchers believe that they will never be solved easily.