# Can you explain the “Axiom of choice” in simple terms?

As I'm sure many of you do, I read the XKCD webcomic regularly. The most recent one involves a joke about the Axiom of Choice, which I didn't get.

I went to Wikipedia to see what the Axiom of Choice is, but as often happens with things like this, the Wikipedia entry is not in plain, simple, understandable language. Can someone give me a nice simple explanation of what this axiom is, and perhaps explain the XKCD joke as well?

-
The punchline is in the alt-text: "The Banach-Tarski theorem was actually first developed by King Solomon, but his gruesome attempts to apply it set back set theory for centuries." –  Jyotirmoy Bhattacharya Oct 11 '10 at 5:25
If I have an infinite number of pairs of identical socks and can always pick out one from each pair, there is a way to make pumpkins spontaneously reproduce. –  Seamus Oct 11 '10 at 10:37
Look at: Wagon, Stan (1994). The Banach–Tarski Paradox. Cambridge: Cambridge University Press. ISBN 0-521-45704-1 –  Joseph Malkevitch Oct 11 '10 at 13:53
The formulation I like is this: the Cartesian product of two infinite sets is always non-empty (including for uncountably infinite sets). –  Matt Calhoun Oct 15 '10 at 16:20
@Matt: Not precisely, this does not require AC. The correct formulation is: Cartesian product of any family of nonempty sets is nonempty. –  sdcvvc Jan 18 '12 at 17:16

The joke is really about the Banach-Tarski theorem, which says that you can cut up a sphere into a finite number of pieces which when reassembled give you two spheres of the same size as the original sphere. This theorem is extremely counterintuitive since we seem to be doubling volume without adding any material or stretching the material that we have.

The proof the the theorem requires the Axiom of Choice (AC), which says that if you have a collection of sets then there is a way to select one element from each set. It has been proved that AC cannot be derived from the rest of set theory but must be introduced as an additional axiom. Since AC can be used to derive counterintuitive results such as the Banach-Tarski theorem, some mathematicians are very careful to specify when their arguments depend on AC.

Here is a formal statement of AC. Suppose we have a set $W$ and a rule associating a set $S_w$ to each $w \in W$. Then AC says that there is a function $$f:W \to \bigcup_{w \in W} S_w$$ such that $$f(w) \in S_w$$

-
one should also try to read about nonmeasurable sets en.wikipedia.org/wiki/Nonmeasurable_set –  BBischof Oct 11 '10 at 5:23
Look at:Wagon, Stan (1994). The Banach–Tarski Paradox. Cambridge: Cambridge University Press. ISBN 0-521-45704-1 –  Joseph Malkevitch Oct 11 '10 at 13:51
Even though I didn't follow the details, I remembered what the Banach-Tarski theorem was, well enough to understand a visual joke in tonight's season premiere of Futurama, eight months later! Thanks! –  MatrixFrog Jun 24 '11 at 5:45

It might be a good idea to say something about the connection between the axiom of choice and the Banach-Tarski paradox. The reason the Banach-Tarski paradox is counterintuitive is that we expect that if you split up a sphere into finitely many pieces, the total "mass" of all the pieces is still the same - so you shouldn't be able to put those pieces together again into something of twice the total "mass." The reason this reasoning doesn't apply is that the pieces in question don't have mass at all! This is not the same as saying that they have zero mass. It's something much more terrifying: the notion of "mass" (which to a mathematician generally means something precise called measure) can't be defined for these pieces (in a way that still preserves all the reasonable properties we want of our notion of mass).

What does this have to do with the axiom of choice? Well, it turns out that the axiom of choice is one way we can construct these bizarre pieces (non-measurable sets). Without the axiom of choice, it's not possible to prove that such pieces exist. With the axiom of choice, we can construct things like the Vitali set and like the pieces that occur in the Banach-Tarski paradox because AC greatly increases our ability to write down weird sets.

-
Another way of loking at it is to realize that given a set A having volume 1 and a set B having volume 2, both sets have the same cardinality, i.e., both are composed of the same number of points. –  David R Tribble Oct 11 '10 at 17:11
@Loadmaster: it's more subtle than that. That explains why if you can break A up into infinitely many points and B up into infinitely many points, you can turn one into the other. But the Banach-Tarski paradox accomplishes this with finitely many pieces. –  Qiaochu Yuan Oct 11 '10 at 17:14
@Yaun: Yes, I realize that. I was merely pointing out that even without Banach-Tarski, our intuition about infinite sets can be deceiving. Consider a sphere with radius 1 and another with radius 2; both have different volumes but the same cardinalities. Banach-Tarski just takes that same non-intuitiveness to a higher level. –  David R Tribble Oct 12 '10 at 22:37
Sure you know this, but Banach-Tarski is even more terrifying: you can split the sphere into finitely many pieces and assembling them together back forming two spheres of the same size as the original one isometrically; that is, whitout any kind of deformation of the pieces. (And, if I remember correctly, you can do that with just four -five?- pieces, one of them being just a point!) –  a.r. Oct 16 '10 at 1:19
@Agustí Roig: My recollection is that it's five pieces: the center and four non-points. –  Charles Oct 21 '10 at 14:46

The annotation to http://www.irregularwebcomic.net/2339.html has an explanation of the Banach-Tarski paradox in easy to read language. It does ignore some of the technical details, but it covers most of the idea of the construction nicely.

-

"[i]f you have a collection of sets then there is a way to select one element from each set." What does "a way" mean? That there is an algorithm that can select such an element? Obviously, there is a non-algorithmic way to do so -- just go to each set and pick out an element from it. That cannot be what AOC means. But if we mean by "function," just a laundry list that associates one thing with another, that is what it comes to.

-
That is, in fact, exactly what AC means; while it's 'obvious' that there's a non-algorithmic means to do it, it's not true! You can 'go to each set and pick out an element from it' a finite number of times, but for infinite collections of sets that isn't necessarily so. (And you can't simply say 'pick the smallest element of each set' either; AC is equivalent to the notion that 'every set can be given an order'.) –  Steven Stadnicki Dec 9 '12 at 18:05