The Axiom of Choice

You can't get too far in analysis without running into the Axiom of Choice (AC), which is an easy idea to explain but deceptively tricky to grasp, I think. (Analysis, for those who aren't aware, is basically the study of functions - it is what calculus is called when it gets theoretical.) I've wanted to write about AC for a while.

What the Axiom of Choice says is that if you have an infinite collection of nonempty sets, it is possible to choose an item from each set. So if you had, for instance, an infinite set of sock drawers, you could choose a sock from each drawer.

There are two "choice" types of situations where you don't need AC. If you have a finite number of sets, no matter how many, then you don't need AC. You can use the principle of mathematical induction instead. That is, you can say, basically, OK, I can choose something from the first bin because, duh, it's not empty. Then, if I've chosen something from some number of bins up to this point, I can always choose something from the next bin, because again, it's not empty. But even though this works for any finite number of bins (even one billion bins), it doesn't cover an infinite number of bins.

You also don't need AC if you have a specific method of choosing from the sets (bins). For instance, if you have an infinite collection of pairs of shoes, you could say, "From each pair, choose the left shoe." That's basically creating a function from the pairs to the chosen objects, which is what we want. (AC says there is such a function whether we can define it explicitly or not.) People often contrast shoes with socks to explain this difference, because shoes have a right and left and so there is an explicit function for choosing, but socks are undifferentiated.

Of course, AC is usually used with sets of numbers, not sets of socks, because there are not actually an infinite number of socks even in the entire universe, as best I'm aware.

Now, if we were talking about sets of natural numbers (subsets, that is, of {1, 2, 3, ...}) we could just say, "Always choose the smallest one." Every set of natural numbers has a smallest element. This property is called being "well-ordered."

The real numbers, though, in their normal order, don't have this property. There isn't a smallest one of all, and there are a lot of sets of them, even bounded sets, that don't have a least element. For instance, "Every real number larger than 2" doesn't have a least element. (2 isn't in the set, so that's not it, and no matter how close you to get to 2, even if you pick, say, 2.000000001, there is always a smaller one still in there, say 2.0000000000000000000001.)

The Axiom of Choice is equivalent to saying that the real numbers are well-ordered. It's not true in their normal order, but AC says that there is some order you could put them in such that every subset of them would have a least element. (It's sort of a crazy idea - don't try it at home. AC doesn't provide such an order, it just claims that it exists. In fact, if we could define the order, we wouldn't need AC at all!)

To see the equivalence, let's say you had an infinite collection of sets of numbers, and you wanted to choose a number from each set. If you have well-ordering then you can use the rule "always choose the smallest number."

Similarly, if we have Choice, and we want to well-order the reals, we can first choose one to be the lowest one, then choose another one to be the next lowest, and so on ad infinitum.

So why this is interesting? First, AC is an Axiom. That means you can't prove (or disprove) it from anything else in the normal theories we use about numbers. It's just an assertion from the heavens. And while most axioms that you commonly encounter (such as that two points determine a unique line, or that a*b = b*a) are what we might call "obvious," AC is...well, is it obvious to you?

In fact, its use is rather contested.

If you don't use AC, then you can't prove a lot of the important theorems of calculus. And that's not just a matter of theoretical concern - we use calculus all the time to solve all sorts of problems, and it demonstrably works. Calculus is important, and it would be nice to think that it has a sound theoretical basis and isn't just a bunch of malarkey that works by chance, or for reasons beyond human comprehension.

On the other hand, if you do use AC, then you get some crazy results like the Banach-Tarski paradox. Those guys proved that, using AC, you can cut a sphere into a finite number of pieces and then reassemble the pieces into two spheres the same size as the original, which is more or less obviously not true. (The way the cuts are done is not something we can actually replicate, even though it is a small number of cuts, so this isn't an empirical question.)


So, there you have it: the Axiom of Choice.