Axiom of choice

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

The axiom of choice is an axiom in set theory. It was formulated about a century ago by Ernst Zermelo, and was quite controversial at the time. It states the following:

Let X be a collection of non-empty sets. Then we can choose a member from each set in that collection. Stated more formally, there exists a function f defined on X such that for each set S in X, f(S) is an element of S.

Hmmm - seems obvious doesn't it? I mean if you've got a bunch of boxes lying around each with at least one item in each of them, the axiom simply states that you can choose one item out of each box. Where's the controversy?

Well, the controversy was over what it meant to choose something from these sets. As an example, let us look at some sample sets.

1. Let X be any finite collection of non-empty sets.
Then f can be stated explicitly (out of set A choose a, ...), since the number of sets is finite.
Here the axiom of choice is not needed, you can simply use the rules of formal logic.
2. Let X be the collection of all non-empty subsets of the natural numbers {0, 1, 2, 3, ... }.
Then f can be the function that chooses the smallest element in each set.
Again the axiom of choice is not needed, since we have a rule for doing the choosing.
3. Let X be the collection of all sub-intervals of (0,1) with a length greater than 0.
Then f can be the function that chooses the midpoint of each interval.
Again the axiom of choice is not needed.
4. Let X be the collection of all nonempty subsets of the reals.
Now we have a problem. There is no obvious definition of f that will guarantee you success, because the other axioms of ZF set theory do not well-order the real numbers.

And therein lies the crux of the axiom. All it states is that there is some function f that can choose an element out of each set in the collection. It gives you no indication about how the function would be defined, it simply mandates its existence.

There are no contradictions if you choose not to accept the axiom of choice, however, most mathematicians (who aren't set theorists or logicians) accept either it, or a weakened variant of it, because it makes their jobs easier. There are many variants of the axiom of choice (for example the axiom of countable choice, which permits a sequence of choices).

The axiom of choice has been proven to be independent of the remaining axioms of set theory, that is, it can be neither proven nor disproven from them.

One of the reasons that some mathematicians don't particularly like the axiom of choice is the fact that it implies the existence of some bizarre counter-intuitive objects. An example of this is the Banach-Tarski Paradox which amounts to saying that it is possible to "carve-up" the 3-dimensional solid unit ball into finitely many pieces, and using only rotation and translation, reassemble the pieces into two balls each with the same volume as the original. Note that the proof, like all proofs involving the axiom of choice, is an existence proof only, it does not tell you how to carve up the unit sphere to make this happen, it simply tells you that it can be done.

One of the most interesting aspects of the axiom of choice is the sheer number of places that it pops up. It has quite far reaching impact, and shows up in many different branches of mathematics (often implicitly, as opposed to explicitly). There are also a remarkable number of concepts that are equivalent to the axiom of choice, among them the well-ordering principle and Zorn's lemma.

Jerry Bona once said: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's Lemma?". In truth, all three of these are mathematically equivalent, but the statement was amusing because it underscored the fact that most mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn's lemma to be too complex to form any intuitive feeling about.

There are many people still doing work on the axiom of choice and its consequences. If you are interested in more, look up Paul Howard at EMU.


(The following text, moved from Set_theory, needs to merged with the above.)

The axiom of choice leads to the existence of several sets in ZFC, like a well-ordering for the real numbers, that can't be constructed in ordinary ZF set theory. However, it is impossible to prove they don't exist - the axiom is independent of the axioms of ZF - and so we are free to add it to our axioms if we want. This has become more or less conventional, since most of the sets it adds are handy to have, even if we can never find an explicit representation for any of them.

It is important to note most results which seem to need the axiom of choice really need a weaker version -- the Ultrafilter Lemma. It follows from the axiom of choice, but is properly weaker: there are models of ZFC with the Ultrafilter Lemma but where there are sets which do not have choice functions. Most paradoxical seeming results, however, still follow from the Ultrafilter Lemma.


/Talk