Cantor and Cohen: Infinite investigators part II

June 2008

The continuum hypothesis

This is one half of a two-part article telling a story of two mathematical problems and two men: Georg Cantor, who discovered the strange world that these problems inhabit, and Paul Cohen (who died last year), who eventually solved them. This article explores what is known as the continuum hypothesis, while the other article explores the axiom of choice. Each article is self-contained, so you don't have to read both to get the picture.

Cantor: The infinite match-maker

Georg Cantor was a German logician who, in the late 19th century, achieved a feat which scientists, philosophers, and theologians had previously only dreamed about: a detailed analysis of infinity. For Cantor personally, the consequences of this triumph were not happy. Unable to solve one of the questions his work opened up, he became obsessive and miserable with his failure. This fixation combined with personal tragedy, the death of his son, and the public insult of having his work rejected as being "a hundred years too soon", Cantor spent the last years of his life in and out of sanatoria.

Georg Cantor

Cantor's discovery was that there is not just one infinity, but a never-ending hierarchy, each infinitely bigger than the last. It's a mind-bending thought, but the entrance to his exotic world is a surprisingly easy and familiar concept.

Suppose you have two collections of objects. Call them collection A and collection B. How could you tell which is bigger, or if the two are the same size? Of course, you could just count all the objects in collection A, then count all the objects in collection B, and compare the two numbers. But it might be easier (and eliminate the risk of losing count), to try to match the two sets up: pair every object from A with one from B, until one or the other runs out. Sets which can be matched up are the same size, and sets which can't are different. This idea could hardly be simpler, but in Cantor's hands it yielded an extraordinary discovery: he proved that some infinite sets can never be matched with others. So immediately we know that there are different levels of infinity, with some bigger than others.

Cantor applied this method to some common mathematical objects. For instance the natural numbers are just the ordinary counting numbers: 0, 1, 2, 3, 4,... . It might seem obvious that the set of even numbers {0, 2, 4, 6, 8,...} should be smaller than the set of natural numbers, after all, aren't there only half as many of them? Surprisingly though, the two sets can easily be matched up: 0 to 0, 1 to 2, 2 to 4, 3 to 6, and so on, just multiplying by 2 every time. So we have to conclude that the two sets are, in Cantor's sense, actually the same size.

The set of real numbers is another fundamental object, which can be thought of as the collection of all infinite decimal expansions (such as 19.000000000... or 1.234567891011121314151617181920 ...). You can also think of the real numbers as being the points of an infinitely long line with no holes in it. For this reason the set of real numbers is sometimes called the continuum. Cantor proved that any attempt to match the real numbers with the natural numbers will fail: there will always be some real numbers which get missed out. So we are forced to conclude that the infinity of real numbers is bigger than that of the natural numbers.

Here's a question: is there an infinity between that of the natural numbers and the real numbers? That is, if I take any collection of real numbers, is it true that it can be matched either with natural numbers, or with the entire set of real numbers? Or is there an intermediate size that it could be? The continuum hypothesis is the statement that there is no such middle ground, and this was the question which brought Cantor so much frustration and misery. We can go into more detail using Cantor's system of infinite numbers.

The natural numbers and the continuum — is there an infinity between them?

Cardinal importance

Cantor built a system of special numbers called cardinal numbers, which measure the different possible sizes of sets. The crucial characteristic is that every single set can be matched up to exactly one cardinal. The finite cardinals are just the natural numbers: 0, 1, 2, 3, 4, 5,... . These correspond to the finite sets of the relevant size: a set with one object in it has cardinality 1, a set with two objects has cardinality 2, and so on. But there are infinite cardinals too, infinitely many of them. Cantor discovered how to extend basic operations, such as addition and multiplication, to these infinite numbers.

You can count the natural numbers and even the fractions, but the points along a line form an uncountable set.

The first infinite cardinal is called $\aleph _0$ (that's "aleph nought", where $\aleph$ is the first letter of the Hebrew alphabet). $\aleph _0$ is the size of the set of natural numbers. So a set has size $\aleph _0$ if its elements can be matched up with the natural numbers: that is to say, if you can count it. For this reason, sets of cardinality $\aleph _0$ are called countable. The next cardinal is $\aleph _1$ : the first uncountable cardinal. Then there's $\aleph _2$ , $\aleph _3$ and so on (and that's just for starters). There is no biggest cardinal: however huge a cardinal is, you can always talk about the next cardinal number, which is the smallest one bigger than the one you already have.

But that's not the only way of obtaining a larger cardinal number from one you already have. If you have a set $X$ , you can form a bigger set $P(X)$ called the power set of $X$ . The set $P(X)$ is the collection of all subsets of $X$ . So for instance if $X$ is the three element set $\{ 1, 2, 3\}$ then $P(X)$ is

$\bigg{\{ } \emptyset , \{ 1\} , \{ 2\} , \{ 3\} , \{ 1,2\} , \{ 1,3\} , \{ 2,3\} , \{ 1,2,3\} \bigg{\} },$

where $\emptyset$ is the empty set: the set with no members. If $X$ is the set of natural numbers, then $P(X)$ includes the set of numbers between 1 and 100: $\{ 1, 2, 3, ... , 100\}$ , the set of primes $\{ 2, 3, 5, 7, 11, ... \}$ , the set of odd numbers $\{ 1, 3, 5, 7, 9, 11, ...\}$ , the empty set $\emptyset$ , and every other conceivable collection of natural numbers. If you do this with a finite set (the above set $\{ 1, 2, 3\}$ has 3 elements), then the number of elements in $P(X)$ is 2 to the power of the size of $X$ (in this case $2^3 = 2 \times 2 \times 2 = 8$ ). Cantor proved that for infinite sets too, the power set $P(X)$ is always bigger than the original set $X$ : the two can never be matched up. If $X$ has cardinal number $A$ , then we say that $P(X)$ has cardinality $2^ A$ . So the cardinal number $2^{\aleph _0}$ is the size of the power set of the natural numbers, and it has a special significance. Many important sets, including the set of real numbers, have cardinality $2^{\aleph _0}$ and this is the reason why $2^{\aleph _0}$ is called the continuum. Now we can rephrase the continuum hypothesis: it is the assertion that

$2^{\aleph _0} = \aleph _1.$

If the continuum hypothesis is true, then there is no cardinal number between $\aleph _0$ and $2^{\aleph _0}$ . So any infinite collection of real numbers must either have cardinality $\aleph _0$ , or $2^{\aleph _0}$ : there is no middle ground. But if the continuum hypothesis is false, then $\aleph _1$ lies between $\aleph _0$ and $2^{\aleph _0}$ . So there must be a collection of real numbers of cardinality $\aleph _1$ : too big to be matched with the natural numbers, but too small to be matched with the whole set of real numbers.

Cantor believed that the continuum hypothesis was true, and spent many years trying to prove it, up until his death in 1918. In 1900, the influential mathematician David Hilbert set out 24 mathematical questions for the new century, which set the course of mathematics for the next 100 years. Hilbert was enthusiastic about set theory, which he called "Cantor's paradise". He put the continuum hypothesis as the first problem on his list.

Paul Cohen: Conquering the continuum

Paul Cohen

The tale of the continuum hypothesis is very similar to that of the axiom of choice, which is treated in another article in this issue of Plus. Mathematicians at the beginning of the twentieth century had been trying to devise a system of axioms that would serve as the foundation of all mathematics. The purpose of working from axioms was to make mathematics rigorous so that the leaps of faith and strokes of inspiration which naturally form part of every mathematician's work can be verified properly from these basic rules. The presumption was that it should be possible to derive every mathematical truth from these axioms, using only the rules of logic.

The work of the mathematician Ernst Zermelo in the early twentieth century provided the basis for such an axiomatic system, built on the theory of sets. This system is now known as ZFC (after Zermelo, Abraham Fraenkel, and choice — see the other article in this issue of Plus), and this version of set theory still underpins almost the whole subject today: all numbers and virtually every mathematical object can easily be constructed within a set-theoretic universe founded on ZFC.

Mathematicians at the time thought that the continuum hypothesis too would find its place in this universe: they set about trying to prove it from the ZFC axioms. But they failed. The first real progress was made in 1940 by the mathematician Kurt Gödel, who showed that at least the continuum hypothesis does not introduce any contradictions into ZFC. Of course this is a long way short of proving that it is actually true.

Paul Cohen's triumph was the invention of forcing, a powerful technique for building new universes of sets which obey ZFC, but which can be tailored to satisfy extra conditions too. In 1963 Cohen turned his pioneering technique upon the continuum hypothesis. He constructed a set-theoretic universe satisfying ZFC, but in which the continuum hypothesis was false. Together with Gödel's work, this proved that the continuum hypothesis is independent of ZFC. It is impossible to conclude from the ordinary rules of mathematics as we understand them, whether the continuum hypothesis is true or not. This was the remarkable result for which in 1966 Cohen won the Fields Medal (the equivalent of the Nobel Prize for mathematics), and in 1967 we was awarded a National Medal Of Science by US President Johnson.

The continuum: The debate continues

Thanks to Cohen's work, we know that we cannot hope to resolve the continuum hypothesis one way or the other from ZFC. But set-theoretic axioms do not exist in a vacuum: they are picked to reflect our intuition about how sets should work. So although we can never prove it, we can still ask whether the continuum hypothesis is a natural assumption, which chimes with our innate ideas about sets.

The celebrated set-theorist Hugh Woodin has argued a case for considering the continuum hypothesis wrong, and that $2^{\aleph _0} = \aleph _2$ is a more natural assumption. Other people have argued for much larger values of the continuum: Cohen himself wrote that he believed $2^{\aleph _0}$ should be bigger than $\aleph _{\aleph _0},$ and even $\aleph _{\aleph _{\aleph _0}}$ .

To infinity and way, way beyond

It was David Hilbert who said "No one shall expel us from the paradise that Cantor has created for us", and over a hundred years after its birth, research in set theory is still going strong. The continuum hypothesis is just the first of a series of "large cardinal axioms" dealing with cardinal numbers unimaginably bigger than $\aleph _0$ . Typically there is no way to write down these cardinals, and their existence is usually independent of ZFC. It is remarkable that such objects from the set-theoretic stratosphere can have consequences back down on Earth, among the natural numbers.

Paul Cohen will not only be remembered for his decisive contributions to the continuum hypothesis and the axiom of choice: the technique he invented, forcing, remains today the standard way to build new universes of set theory, and to illuminate the upper reaches of Cantor's paradise.

About the author

Richard Elwes is a writer and mathematician based in Leeds. He was the winner of the Plus New Writers Award 2006 and has since published articles in New Scientist and talked about maths on Channel 4 radio's The Tube. As well as teaching and researching maths, he enjoys writing about everything from politics to horror films.

Plus.Maths.org

Add new comment