The axiom of choice

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. The first of these problems — the axiom of choice — is the subject of this article, while the other article explores what is known as the continuum hypothesis. 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, known as the continuum hypothesis, 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 "one 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 have to conclude that there are different levels of infinity, with some bigger than others. (You can find more about the consequences of this idea in the second part of this article The continuum hypothesis.)

Sets and politics

Once Cantor had let his infinite cat out of its bag, his new subject, set theory, attracted excitement and scepticism in equal measure. Through his own work and that of Henri Lebesgue, it quickly became incorporated into respectable mainstream subjects such as analysis and geometry. At the same time, belief in different levels of infinity seemed to some people to go against human instinct, and even Cantor himself said of one of his more counter-intuitive results "I see it, but I do not believe it". So perhaps it's understandable that many in the mathematical community were reluctant to accept these bizarre new ideas.

Principal among the sceptics was Leopold Kronecker, a purist who believed that the only real mathematics was that which could be reached from the integers (whole numbers) in a finite number of steps. To Kronecker, the rest was all fantasy and fiction. This attitude was summed up in his saying "God created the integers, all else is the work of man". To him, Cantor's work played far too freely with concepts that came from nowhere: while Cantor generalised about theoretical matchings between theoretical sets, Kronecker would trust only specific matchings between sets which he could write down and understand. Kronecker went so far as to denounce Cantor as a "scientific charlatan" and "corrupter of youth", and was one of several influential mathematicians to oppose his work. Even Cantor's friend Magnus Mittag-Leffler, the editor of the prestigious journal Acta Mathematica, persuaded him to withdraw his work from publication, as being "one hundred years too soon".

Paradoxes and axioms

But others were more receptive to Cantor's ideas. Inspired by him, the logicians Gottlob Frege and Bertrand Russell came to believe that the whole of mathematics could be built up from the ground, starting only with basic logic and set theory.

Bertrand Russell

In 1901, Frege was about to publish the second volume of a work which tried to do exactly that: The Basic Operations Of Arithmetic. But at the last minute, Russell wrote to him with a discovery which not only undermined Frege's own work, but also threatened to bring the whole edifice of set theory crashing down.

Sets are collections of objects, and if the set $X$ includes the object $y$, then we say that $y$ is a member of $X$, written $y \in X$. Of course some sets are members of other sets. For instance, the set of Alsatian dogs is itself a member of the set of all breeds of dog.

Theoretically, might it even be possible that some sets are members of themselves? Set theorists of the time reasoned that the set of all sets must be an example of a set which was a member of itself. Russell's Paradox was a simple contradiction based on this idea: let $X$ be the collection of exactly those sets which are not members of themselves. Then, is $X$ a member of itself? Think about it! Either way, you get a contradiction.

Russell's was not the first paradox to come out of set theory. In fact, Cantor had discovered one himself, thinking about the size of the set of all sets. But Russell's was so simply stated as to be devastating: it led unavoidably to the conclusion that there was something badly wrong with Cantor's set theory.

Set theory's awkward adolescence lasted for the first two decades of the 20th century: the main challenge was to resolve Russell's paradox. Several people tried, unsuccessfully, starting with Frege, in a hastily written amendment to his treatise, and including in 1923 the philosopher Ludwig Wittgenstein.

Russell himself did find a way through, and with Alfred North Whitehead, he set about attempting what Frege had not managed: using logic and set theory to put the whole of mathematics on a firm foundation. Their three volume work Principia Mathematica, published between 1910 and 1913, showed how to build numbers and other mathematical objects from scratch, using only sets and logic. Famously, it takes until page 86 of the second volume to prepare the necessary ingredients to prove that 1 + 1 = 2, which is accompanied by the comment "The above proposition is occasionally useful".

Early set theory could accommodate infinity, but threw up confounding paradoxes.

Russell and Whitehead realised that it was necessary to be more careful about what could count as a "set" than the naive "collection of objects" definition of Cantor's era. The way to resolve Russell's paradox was to formulate a more restricted definition of "set", so that nonsensical objects such as Russell's X and the set of all sets would not be allowed to count as sets after all, and no set would be allowed to be a member of itself.

Their solution was an elaborate stratification of sets, where every set was assigned a level, and only allowed to include as members sets of lower levels. This sort of system is known as type theory, and its descendants remain important today, especially in computer science. But the search went on for a freer, less cumbersome foundation for mathematics.

The answer eventually arrived, based on the work of Ernst Zermelo. Zermelo had been working in set theory since the beginning of the century, and in 1922, Abraham Fraenkel and Thoraf Skolem discovered how to put the crucial final touch to his work. What they found was a straightforward list of axioms which govern the behaviour of abstract sets. This system is known as ZF after Zermelo and Fraenkel. ZF is such a logically streamlined system that real-life collections of objects (such as breeds of dog) do not fit in very easily (at least without adjustments): ZF describes a universe built entirely from abstract sets. These can be members of each other, but they are not built from more basic objects. For mathematical purposes, ZF was exactly what was required: strong enough to support the whole of Cantor's infinite world, but weak enough to avoid the paradoxical monsters he and Russell had found.

The axiom of choice

The purpose of axiomatic systems such as ZF (or Russell and Whitehead's) is to describe the whole of mathematics, or at least a great chunk of it, from a small number of fundamental assumptions. Principia Mathematica provided the template for building up mathematics from ZF, 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 ZF.

So did ZF prove once and for all that Kronecker and the other doubters were wrong? It certainly did look as if Cantor's infinities had finally been placed on a solid footing. But all the same, there was one issue which remained mysterious.

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. However, back in 1904 Zermelo had identified a principle which mathematicians use frequently (and even unconsciously), but which didn't seem quite to fit this bill. In particular it played an important (though uncredited) role in Cantor's original match-making.

The principle is this: suppose you have a collection of sets: A, B, C, etc., and you want to create another set by taking one element from A, one from B, one from C, and so on. It seems obvious that you should be allowed to do this. But sometimes there is no clear way to isolate particular elements from A, B, C, etc. You may not have explicit lists of their elements, and of course there could be infinitely many of these sets. If there is a rule you can use to choose an element from each set, then it's no problem: to use Russell's analogy, if A, B, C, etc. are pairs of shoes, then ZF allows you to say "form a new set by picking the left shoe from each pair". But if they are pairs of indistinguishable socks, and if you have infinitely many of them, there is no explicit way to do this. At least, not without the axiom of choice, which always allows you to say "choose one sock from each pair".

If you're dealing with pairs of shoes, you can always pick one. If it's socks, though, you're in trouble.

Paul Cohen: Building different universes

If ZF was the bedrock of mathematics, and the axiom of choice was true (as most people believed), then the presumption was that it should somehow be possible to deduce it from ZF. Mathematicians spent many years trying to do exactly this, but without success. This was frustrating: the axiom of choice was a simple enough property, and if ZF was to serve as the foundation of mathematics, then far more complex mathematical questions should be resolvable solely by reference to it. Or so people thought.

Paul Cohen

However, this hope had to be drastically revised in 1931, when the great logician Kurt Gödel proved his celebrated incompleteness theorems. A consequence of these was that ZF does not form a complete system. That is to say ZF is not after all enough to settle every conceivable question about sets and numbers. This may seem disappointing, but it is not a particular failing of ZF: Gödel had shown that it would be impossible to write down any system which was complete and simultaneously strong enough to describe ordinary arithmetic.

In 1940 Gödel showed that at least the axiom of choice was compatible with ZF: it does not introduce any contradictions into the system. Paul Cohen's triumph was the invention of forcing, a powerful technique for building new universes of sets which obey ZF, but which can be tailored to satisfy extra conditions too. In 1962, Cohen used forcing to build a universe which obeyed ZF, but which did not satisfy the axiom of choice. This was the opposite of what Gödel had shown: it meant that the falsity of the axiom of choice is also compatible with ZF. So Cohen had proved that the axiom of choice is independent of ZF: it is equally consistent either that it holds, or that it fails.

The world without choice

These days, most people opt to use ZFC — that is, ZF with the axiom of choice added in. However, it remains an object of study today. Many interesting criteria have been found which are logically equivalent to it, including some coming from other parts of mathematics altogether. From the perspective of Cantor's infinities, an important one is the principle of trichotomy: for any two sets A and B, either A is bigger than B, or B is bigger than A, or they are the same size. This may seem obvious, but if the axiom of choice is false, then you can find infinite sets which simply cannot be compared to each other.

Some mathematicians do object to the axiom because of its non-constructive nature: it asserts the existence of a particular set, without telling you how to get it or what it looks like. Certainly, Leopold Kronecker would not have liked it. As well as having ideological reasons to oppose it, some people are simply intrigued by the peculiar world without choice, where certain ordinary mathematical objects may not exist, and different definitions of what it means to be "finite" may fail to coincide.

That is not to say that the axiom of choice itself does not produce some surprising consequences. The Banach-Tarski Paradox is the unnerving fact that you can take a three-dimensional ball, use the axiom of choice to chop it into five pieces, and then by only rotating and sliding the pieces around, you can assemble them into two new balls, each exactly the same size as the original. Strange things happen even in a world with choice.

Further reading

• Find out more about Cantor's infinities in the second part of this article The continuum hypothesis by Richard Elwes;
• You can find out more about Gödel's incompleteness theorems in the Plus article Gödel and the limits of logic by John W Dawson.

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.