HAVING EXPLAINED what it means to say that two sets have the same size, Cantor next invented an absolute measure of size, called cardinal numbers. Again, finite sets are easy. A set with one element has cardinality 1, a set with two elements has cardinality 2, and so on. Cantor proposed a new cardinal number to denote countably infinite sets: aleph-nought, or ℵ0.
Left A countably infinite collection of countable sets (here shown as an infinite array) can still be counted. The arrows show how to place the array into a linear sequence.
So far, I have yet to show you any set with cardinality greater than ℵ0. In fact, the three examples above show that ℵ0 + 1 = ℵ0, ℵ0 + ℵ0 = ℵ0, and ℵ0 · ℵ0 = ℵ0. However, Cantor showed that the set of all real numbers does have greater cardinality; that is, the real numbers cannot be accommodated in our countable hotel. The proof of this fact, called Cantor’s diagonal argument, is one of the most original and fundamental breakthroughs of modern mathematics, yet short enough to explain in a page.
Suppose that I try to come up with a room assignment for all the real numbers between 0 and 1. For the sake of argument, let’s say that the list starts as follows:
Room 1: 0.1415926 … (the decimal part of pi)
Room 2: 0.7182818 … (the decimal part of Euler’s number e)
Room 3: 0.4142135 … (the decimal part of √2)
Room 4: 0.5000000 …
Room 5: 0.1011001 … (I’m running out of interesting numbers, so this is just a random string of 1’s and 0’s).
Notice that the first digit of the first number is highlighted, as is the second digit of the second number, and so forth. Now Georg Cantor comes along and asks me, “Which room is this number in?” and he writes down the number 0.22511 …
It’s no secret how Cantor got this number: he simply took each of the bold numerals and added 1 to it. (If he had encountered the numeral 9, he would have changed it to a 0.) Cantor’s number cannot be in room 1 because its first digit disagrees with the number there. It cannot be in room 2 because its second digit disagrees with the number there. In fact, for the same reason it cannot be in any of the rooms in the hotel. The room assignment is incomplete! More importantly, Georg could repeat this procedure for any room assignment I came up with. Thus there is no way to accommodate the real numbers between 0 and 1 in the hotel (and so, of course, there is no way to accommodate all the real numbers).†
To make intuitive sense of Cantor’s diagonal argument, I like to think of the number line as consisting of a countable set of bricks (the rational numbers) with a sort of “glue” of irrational, transcendental, and mostly just plain random numbers filling the gaps between them. Cantor’s argument shows that the vast majority of the number line is made of glue, not bricks.
Having discovered a cardinal number greater than ℵ0, we need a name for it. The customary name, which emphasizes this bricks-and-mortar intuition about the number line, is the cardinality of the continuum, or c for short. The “continuum” is all of that glue that is hard to get off your hands.
Cantor also discovered a second, and more general, way to produce higher cardinalities. If S is a set, the set consisting of all of its subsets is called the power set of S. Let’s look at a few examples.
If S is a set with one element, say {1}, then it has two subsets, namely the empty set Ø and the entire set {1}. Thus the power set has two elements.
If S is a set with two elements, say {1, 2}, then it has four subsets, namely Ø, the set {1}, the set {2}, and the set {1, 2}. Thus its power set has four elements. Note that 4 = 22.
Similarly, if S is a set with three elements, I invite the reader to check that the figure shown here has eight subsets. Note that 8 = 23.
At this point the pattern seems clear: the power set of S always has more elements than S. In fact, if the cardinality of S is n, then the cardinality of the power set is always 2n.
With a slight modification of the diagonal argument, Cantor showed that the same thing is true for infinite sets: the power set of S always has greater cardinality than S itself. So there is no largest infinite cardinal number. The infinite cardinals form a vast tower that we cannot even begin to comprehend.
Right Tree diagram of the power set of S.
If we cannot ever scale the upper reaches of this tower, perhaps we can at least comprehend the beginning. We know that the “smallest” infinite cardinal is ℵ0. We know that the continuum, c, has a bigger cardinality, although we’re not quite sure yet just how much bigger. The power set of ℵ0 also has larger cardinality than ℵ0, which we can denote 2ℵ0 (by analogy with the pattern for finite sets).
Now Cantor asked: What is the next cardinal number after ℵ0? Is it c? Is it 2ℵ0? He partially answered this question, demonstrating that c = 2ℵ0. In other words, the continuum and the power set of the integers have the same size. But could there be a cardinality that is intermediate in size between ℵ0 and 2ℵ0—a set that is “a little more pregnant” than the integers but “a little less pregnant” than the real numbers? Cantor believed the answer was no. In other words, the next cardinal number after ℵ0, which we denote by ℵ1, is 2ℵ0. Because this is a book about equations, here is Cantor’s Continuum Hypothesis in equation form: 2ℵ0 = ℵ1.
CANTOR DID NOT LIVE to see his question answered. He spent the last few years of his life confined to a mental institution, and died in 1918. Though it is tempting and facile to suggest that the lack of acceptance for his ideas “drove him crazy,” it is a temptation that must be resisted. Depression is too complex an illness to reduce to such a simple formula. What is true is that his work was deeply controversial. Some mathematicians of his era, such as Leopold Kronecker, rejected it in scathing terms, while others, such as David Hilbert, strongly endorsed it. “No one shall expel us from the paradise that Cantor has created,” Hilbert wrote.
In 1900, when Hilbert compiled a list of the 23 most important problems for mathematicians to work on in the twentieth century, he placed the Continuum Hypothesis at the top of the list. As it turned out, the solution of the Continuum Hypothesis would be inextricably linked to the solution of the second problem on Hilbert’s list: a proof of the consistency of mathematics.
By the early years of the twentieth century, the foundations of mathematics were in crisis. This seems to happen periodically in math history. The discovery of irrational numbers in ancient Greece provoked a crisis that led the Greeks to turn toward geometry instead of arithmetic as the foundation of mathematics. The discovery of calculus produced another crisis, because of its apparent manipulations of infinite and infinitesimal quantities. In reaction, mathematicians rejected “completed infinities,” as the quote from Gauss earlier in this chapter attests, and reformulated calculus to use only “potential infinities.”
Above Conceptual artwork of a metal structure conveying the idea of an infinite depth.
Cantor’s work on infinite sets set off another crisis. First, Cantor himself realized that there was no such thing as the set of all sets. If such a set existed, it would perforce have the largest cardinality possible, and yet we have just said that there is no largest cardinality. In 1901, the philosopher Bertrand Russell produced an even simpler paradox. Let R be the set of all sets that do not contain themselves. Does R contain itself?
Well, let’s suppose it does. Then it is a set that contains itself, and therefore it is not an element of R, because R only contains sets that do not contain themselves. But that means R is not an element of R—contradicting the assumption that we just made that R contains itself!
These examples showed that mathematicians do not have complete freedom to create any set that we can describe in words. “Naïve set theory” does not work. There must be some rules governing what is and is not permissible in set theory.
In 1908, Ernst Zermelo drew up a list of seven axioms for set theory that ruled out Cantor’s and Russell’s paradoxes. With some modifications in the 1920s by Abraham Fraenkel (which brought the number of axioms to nine), his syst
em has become the standard working foundation for the vast majority of practicing mathematicians.
In light of these developments, Hilbert’s second problem was reinterpreted as follows: prove that Zermelo–Fraenkel (ZF) set theory is consistent. If this could be done, then mathematicians could sleep soundly at night, knowing that there would be no more crises in the foundations of mathematics from paradoxes we have not thought of yet.
By 1928, Hilbert was optimistic that his problem was near to being solved. At that year’s International Congress of Mathematicians, he announced that only a few more details needed to be put into place in the proof. But within less than two years, the whole enterprise unraveled completely.
WITH HINDSIGHT, Hilbert’s mathematical epistemology, called formalism, seems like a strange one. Hilbert believed that mathematics was essentially a formal game played with symbols. The symbols themselves have no intrinsic meaning. Every statement made with these symbols should be either true or false, and if true it should be provable from the axioms. (In other words, mathematics is complete.) Finally, it should never be possible to prove a statement to be both true and false; mathematics must be consistent.
It is a good thing that Hilbert’s vision turned out to be flawed, because he was proposing to rescue mathematics by killing it. If mathematics loses its content, then it also (I believe) loses most of its beauty. If mathematicians truly believed that they were doing nothing but pushing symbols around, I think that many of them would want to find another way of passing the time.
The person who rescued mathematics from Hilbert’s poorly conceived lifebuoy was Kurt Gödel, a young Austrian logician who was born in Brno (now part of the Czech Republic) in 1906. In 1930, Gödel proved that in any axiomatic system that is strong enough to include the normal rules of arithmetic, there must be statements that are both true and unprovable. In other words, mathematics is incomplete. Very shortly after his first theorem, Gödel proved a second, more specific version: the consistency of the axiomatic system itself is unprovable.
HOW CAN YOU POSSIBLY prove such a theorem as the incompleteness of mathematics? Gödel’s proof contains two main ideas. The first one is an adaptation of a very ancient paradox. The Liar’s Paradox concerns the following statement: “This statement is false.” If the statement is true, then it proclaims its own falsity. We are stuck in the same type of self-referential vicious circle that we were with Russell’s Paradox.
Gödel’s version of the Liar’s Paradox reads as follows: “This statement is unprovable.” If Gödel’s sentence is true, then it cannot be proved. If the statement is false, then it is both false and provable, which means that our axiom system is inconsistent. If we assume the consistency of ZF set theory as a premise, then the second possibility is ruled out, and therefore Gödel’s sentence is true and unprovable.
Below Portrait of the Austrian-US logician and mathematician Kurt Gödel (1906–1978).
So far, though, we have not done any mathematics. The second, and even more ingenious, part of Gödel’s proof is a way of converting the non-mathematical statement “This statement is unprovable” into a mathematical statement about numbers. In any axiomatic system, Gödel realized, there are only ℵ0 possible statements. That is true because we have only a finite alphabet of possible symbols, and only a countable list of possible statement lengths. Therefore every statement—true, false, provable, unprovable, or just plain nonsensical—can be assigned a unique identifying number. Let’s imagine now that we have a list L of all the identification numbers of provable statements.
Now the assertion that a particular statement is unprovable reduces to a mathematical assertion: “This number is not in the set L.” Gödel uses a version of Cantor’s diagonal argument to show that at least one sentence of the form “This number is not in the set L” is, in fact, not on the list of provable statements. Thus that particular statement is both true and unprovable.
Gödel’s proof takes some getting used to; it is easy to get lost in the multiple layers of self-reference. It is intricately linked to Cantor’s diagonal argument and to the counterintuitive nature of infinite cardinals. You would expect that there are many more statements about the integers than there are integers themselves. But that is not true. The fact that you can encode every statement about the integers as an integer, and thus transform a meta-mathematical statement into a mathematical statement, is sheer magic.
I like to think of Gödel’s Incompleteness Theorem as a counterpart to the Heisenberg Uncertainty Principle. (This is the statement from quantum physics that you cannot measure both the position and the momentum of a particle at the same time; more generally, that the act of measuring certain quantitites will alter the system in a way that destroys information about other quantities.) Both of them circumscribe the limits of what humans can possibly know—one in the domain of mathematics, the other in the domain of physics. Both results were discovered within ten years of each other. After a nineteenth century that was dominated by the Victorian belief in progress and the perfectibility of human knowledge, the twentieth century was an era when humans began to become aware of their own limitations. These two landmark discoveries are a part of the philosophical Gestalt of an era.
Though the philosophical implications of Gödel’s theorem were huge, its mathematical implications were curiously muted. In some ways, mathematicians shrugged their shoulders and went on with their business. From today’s perspective, the theorem is similar to the asteroid that killed off the dinosaurs. It killed off some mistaken ideas about mathematics, and it left a large crater, but today that crater is virtually impossible to detect.
Why is its influence so undetectable? One reason, I think, is that Gödel’s unprovable statements are very artificial. The statement “mathematics is consistent” can be written down in words, but its mathematical version, after it has been converted to a statement about numbers, is impossible to write down. Gödel had still not found an unprovable statement with actual mathematical content—a statement that a mathematician might actually care about.
And that is where Cantor’s Continuum Hypothesis re-enters the picture. Is there a set larger than the integers but smaller than the real numbers? It’s a natural question. It seems accessible to our intuition. It’s certainly a question a mathematician would care about. And it is an undecidable question. In 1940, Gödel showed that the Continuum Hypothesis cannot be disproved from the ZF axioms of set theory. And in 1963, an American mathematician, Paul Cohen, closed the circle by showing that the Continuum Hypothesis also cannot be proved from the ZF axioms. In other words, it is logically independent of the other axioms of set theory. You are free to assume it, or you are free to deny it. Neither the Continuum Hypothesis nor its negation will introduce any new paradoxes.
BOTH GÖDEL’S AND COHEN’S arguments proceed by constructing a model of set theory, though I will not explain them in detail. Gödel restricted the universe of possible sets to what he called “constructible sets.” Within this model, he showed that the Continuum Hypothesis is true. Therefore, assuming the ZF axioms are consistent, it is impossible to disprove the Continuum Hypothesis. Cohen, on the other hand, worked out a way of extending the universe of possible sets beyond the minimal model allowed by the ZF axioms. Because it involves the creation of new sets, Cohen’s argument is more difficult than Gödel’s. But the bottom line is that he forced the Continuum Hypothesis to be false … within that model. Again, this does not mean that the “real” Continuum Hypothesis is false, but it does mean that it is impossible to prove the Continuum Hypothesis in all models of ZF set theory.
Cohen’s method of “forcing” allowed mathematicians and logicians to discover many other statements that are independent of the ZF axioms. In this sense, it has had a greater impact on mathematics than Gödel’s Incompleteness Theorem. The crater is still fresh.
So is the story of the Continuum Hypothesis finished? It’s difficult to say. For now, most mathematicians are happy with the ZF axioms, if they
even know them. As long as that remains the case, we will have to let the Continuum Hypothesis remain in the ambiguous state where Gödel and Cohen left it. But the ZF axioms may not remain so fashionable forever. Remember that you can never prove an axiom system; it is only a starting point. Someday logicians might devise an axiom system that mathematicians will like better than ZF, and then the Continuum Hypothesis will have to be reconsidered.
After the Second World War, Gödel ended up at the Institute for Advanced Study in Princeton, where he became best friends with Albert Einstein. Einstein once said that on many days the only reason he would come to the Institute was “to have the privilege to walk home with Gödel.” However, in later years Gödel’s behavior became increasingly odd; for example, he believed in ghosts, and he thought that someone was trying to poison him. He would eat only food that he had personally prepared, and in the end, he practically starved himself to death.
Cohen, thankfully, had none of the struggles with mental health that Cantor and Gödel did. Born in 1934, he grew up in Brooklyn and was a self-taught prodigy. He never finished college but went straight on to graduate school in 1953, at the age of 19. Curiously, he was not trained as a logician, but was attracted to the Continuum Hypothesis because he had a strong intuition that it was false. (That’s right, he disagreed with Cantor.)
Sometimes it takes the fresh outlook of a non-expert to break out of an intellectual logjam. Immediately after he discovered the idea of forcing, other logicians seized on it, and Cohen found himself unable to keep up with them. Nevertheless, Cohen had the honor of being first, and his work received high praise from none other than Gödel himself. “You have just achieved the most important progress in set theory since its axiomatization,” Gödel wrote to him.
* * *
† This argument has a slight flaw in it due to the fact that some numbers have two decimal representations, for example 0.499… = 0.500… I have intentionally given this easier but flawed version for the non-experts. For math experts, repairing the inaccuracy takes a little work but in my opinion no fundamentally new ideas.
The Universe in Zero Words Page 16
