Jump to content

AxiomOfChoice

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by JimboWales (talk | contribs) at 23:14, 7 March 2001. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The AxiomOfChoice 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 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 AxiomOfChoice is not needed, you can simply use the rules of formal logic.)
2. Let X be the collection of all subsets of the natural numbers {1, 2, 3, ... }.
Then f can be the function that chooses the smallest element in each set.
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.
4. Let X be the collection of all subsets of the reals.
Now we have a problem. There is no obvious definition of f that will guarantee you success.


And therein lies the crux of the AxiomOfChoice. 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 AxiomOfChoice, 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 AxiomOfChoice (for example the AxiomOfCountableChoice, which permits a sequence of choices).


One of the reasons that some mathematicians don't particularly like the AxiomOfChoice is the fact that it implies the existence of some bizarre counter-intuitive objects. An example of this is the BanachTarskiParadoxicalDecomposition which amounts to saying that it is possible to "carve-up" the closed unit sphere into finitely many pieces, and using only rotation and translation, reform the pieces into 2 spheres each with the same volume as the original. Note that the "proof" given in the BanachTarskiParadoxicalDecomposition 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 AxiomOfChoice 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 WellOrderingPrinciple and ZornsLemma.


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 AxiomOfChoice to be intuitive, the WellOrderingPrinciple to be counterintuitive, and ZornsLemma to be too complex to form any intuitive feeling about.


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


--RaviDesai