Simple City

Paul Cohen has sadly died. The only logician ever to win the Fields Medal, he will primarily be remembered for his work in Set Theory, and in particular for proving two major independence results: that of the Axiom of Choice, and the Continuum Hypothesis. He also worked in mathematical analysis, for which he was awarded the Bôcher Memorial Prize by the American Mathematical Society in 1964.

A short discussion of the Axiom of Choice is below the fold, with a sequel on the Continuum Hypothesis in the pipeline.

In the early 20th century, mathematics faced a foundational challenge: to find a list of fundamental assumptions from which the rest of mathematics could be deduced. Essentially this was achieved by Zermelo and Fraenkel, whose work led to 8 simple axioms* (known as ZF) which govern the behaviour of abstract “sets”, from which numbers and all other mathematical objects can be built. ZF still forms the logical basis of mathematics today.

It was Zermelo in 1904 who had identified another principle which mathematicians use frequently (and even unconsciously). In time it became clear that this couldn’t obviously be derived from ZF.

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 the sets A, B, C, etc. If there is a rule you can use to choose an element from each set, then it’s no problem: to use Bertrand Russell’s analogy, if A, B, C, etc. are pairs of shoes, then ZF already allows you to say pick the left shoe from each pair. But if they are pairs of identical socks, and you have infinitely many of them, you can’t do this. At least not without the Axiom of Choice (AC), which asserts that you always can.

Convinced that it should be true, mathematicians spent many years trying to prove the AC from the axioms of ZF, to no avail. In 1940 Kurt Gödel showed that it is at least (relatively) consistent with ZF.

Cohen’s breakthrough in 1962 was to show that the Axiom of Choice is independent of ZF: it is equally consistent that it holds, or that it fails. The technique he invented to show this is called “forcing”, and is a method of creating new models of ZF (i.e systems of sets which obey the rules of ZF), which satisfy particular properties. Cohen used forcing to construct one model of ZF in which AC holds, and another in which it fails. Independence follows. Forcing plays a central role in modern set-theory, and has been used to settle many other major questions in the area.

These days most people tend to use ZFC, that is ZF together with the AC. However, some people object to AC’s non-constructive nature: it asserts the existence of a particular set, without telling you how to obtain it or what it looks like. Other people are intrigued by the peculiar world without Choice, where many ordinary mathematical objects may not exist, and different definitions of what it means to be “finite” may fail to coincide.

That’s not to say that the Axiom of Choice itself doesn’t produce some surprising consequences. The Banach-Tarski Paradox is the unnerving fact that if you take a three dimensional ball in Euclidean space, AC allows you to chop it up into finitely many pieces, and then using only rigid movements (rotations and translations), reassemble the pieces to make two new balls, each the same size as the original.

* Technically 6 axioms and 2 infinite axiom schemes [thanks to AWT in the comments].