Wikipedia 10K Redux by Reagle from Starling archive. Bugs abound!!!

<-- Previous | Newer --> | Current: 981573186 cobrand.bomis.com at Wed, 07 Feb 2001 19:13:06 +0000.

AxiomOfChoice

The AxiomOfChoice was formulated about a century ago by ErnstZermelo, and was quite contraversial 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 existance.

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 existance 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 existance 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 http://www.emunix.emich.edu/~phoward/]

--RaviDesai