Axiom of Choice

Let C be a collection of nonempty sets. Then we can choose a member from each set in that collection. In other words, there exists a function f defined on C with the property that, for each set S in the collection, f(S) is a member of S.

In set theory class, we had to prove the equivalence of the Axiom of Choice (AC) to some other theorems, such as the well ordered principle, and Zorn's Lemma.

It is an axiom because it has been proven that the axiom of choice cannot be proven or disproven. One of the interesting consquences of AC is the Banach-Tarski Paradoxical Decomposition, which, using AC, is a proof that it is possible to take a 3 dimensional closed unit ball and partition it into finitely many pieces, and reassemble the pieces into two copies of the original ball. Messes with your head, don't it?

Succinctly put, this says that the cartesian product of a set of nonempty sets is itself nonempty. Of course this sounds trivial.

The problem is when you're taking the product of a large number of sets, and you have no clear understanding of their structure. For instance, if you must choose an element of the cartesian product of an infinite number of copies of {0,1}, you can just choose (0,0,...,0,...), and you don't need to invoke the axiom of choice. But say you're trying to get a well ordering of the set of real numbers in the interval [0,1]. Initially, you have no problems: you could pick 0 as the first element, then 1 as the second (i.e. the first element of the rest), then maybe 0.5, followed by 0.3, 0.8, etc.

It's easy even to well-order some countable subset, placing them all at the beginning. But you then need to well-order a new subset, and you'll need to repeat this using some kind of transfinite induction (although you won't be calling it that, because you need the well ordering to do that). But we don't really know any ways of describing what happens at a non-countable "stage" of this process. The problem, in this case, is the repeated application of choice, not just any single application.

You could even make a case that the problem is with the Axiom of Infinity. Sure, it gives you the existence of an infinite set, but now you're looking at the structure of (all of) its subsets. And that's something we've no idea about!

Bertrand Russell had a cute way of describing the Axiom of Choice. You need the axiom to pick your socks, but not your shoes.

Allow me to elaborate. First of all, we must assume that we are talking about infinitely many pairs of socks and infinitely many pairs of shoes. The axiom is not necessary for finite collections of sets. Suppose then that we wish to form an infinite set of shoes containing a shoe from each pair of shoes. In this case we don't need the axiom because we can distinguish the individual shoes in each pair. This gives us an explicit method for picking our shoes. Our method, for example, could be "pick the left shoe from the first googolplex of pairs, and pick the right shoe from the the rest of the pairs." This doesn't require us to make any choice except the one we made at the beginning, before we began our shoe-picking procedure.

No such luck in picking our socks, however. Assuming our pairs of socks are pretty bland (and if we are mathematicians, they probably are), we have no way of distinguishing a left sock from a right sock. As we are going through our pairs of socks and picking a sock, we have to make infinitely many choices. Each time we get to a new pair of socks, we have to (somehow!) decide which one of the socks to put in our ongoing set. And this requires the Axiom of Choice.