Axiom of choice

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.

Another formulation of the axiom of choice (AC) states:

Given any set of mutually exclusive non-empty sets, there exists at least one set that contains exactly one element in common with each of the non-empty sets.

It seems obvious: if you've got a bunch of boxes lying around 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 non-empty 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. Theorems whose proofs involve the axiom of choice are always non-constructive: they postulate the existence of something without telling you how to get it.

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 (unless those remaining axioms contain a contradiction, which we don't know). This is the result of work by Kurt Gödel and Paul Cohen. There are thus no contradictions if you choose not to accept the axiom of choice; however, most mathematicians accept either it, or a weakened variant of it, because it makes their jobs easier. Despite this, there is some study of systems in which the axiom of choice is either not true or at least not assumed (see also axiom of regularity). In these cases it is important to be aware which proofs in mathematics use the axiom of choice and which do not.

One of the reasons that some mathematicians do not particularly like the axiom of choice is 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 in mathematics that it shows up. There are also a remarkable number of statements that are equivalent to the axiom of choice, most important among them Zorn's lemma and the well-ordering principle: every set can be well-ordered. (In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering principle.)

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. Several central theorems in various branches of mathematics require the axiom of choice (or one of its weaker versions, such as the ultrafilter lemma, the axiom of countable choice, or the axiom of dependent choice). These branches are:

• Set theory
  • Any union of countably many countable sets is itself countable.
  • If the set A is infinite, then there exists an injection from the natural numbers N to A.
  • If the set A is infinite, then A and A×A have the same cardinality.
  • If two sets are given, then they either have the same cardinality, or one has a smaller cardinality than the other.
• Algebra
  • Every vector space has a basis.
  • Every ring contains a maximal ideal.
  • Every field has an algebraic closure.
  • The Stone representation theorem, stating that every boolean algebra is isomorphic to some boolean algebra of sets.
• Functional analysis
  • The Hahn-Banach theorem in functional analysis, allowing the extension of linear functionals.
  • The Banach-Alaoglu theorem about compactness of sets of functionals.
  • The Baire category theorem about complete metric spaces, and its consequences, such as the open mapping theorem and the closed graph theorem.
• General topology
  • Tychonoff's theorem stating that every product of compact topological spaces is compact.
  • In the product topology, the closure of a product of subsets is equal to the product of the closures.
  • Any product of complete uniform spaces is complete.
  • A uniform space is compact if and only if it is complete and totally bounded.
  • Every Tychonoff space has a Stone-Cech compactification.

External link

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.