Axiom Of Choice

The axiom of choice is an axiom in set theory with wide-reaching and sometimes counterintuitive consequences. It states that for any collection of sets, one can construct a new set containing an element from each set in the original collection. In other words, one can choose an element from each set in the collection.

Intuitively, the axiom of choice guarantees the existence of mathematical objects which are obtained by a series of choices, so that it can be viewed as an extension of a finite process (choosing objects from bins) to infinite settings. Though this extension seems to be obvious and reasonable, it is also quite powerful; granting it leads to somewhat unexpected and perhaps unnatural-seeming consequences.

Developments in logic in the 20\(^\text{th}\) century established that the axiom of choice was independent of the commonly accepted axioms of set theory due to Zermelo and Fraenkel; that is, Zermelo-Fraenkel set theory with the axiom of choice (ZFC) and Zermelo-Fraenkel set theory without the axiom of choice (ZF\(\neg\)C) are both logically consistent theories. Nevertheless, most mathematicians generally accept the axiom of choice as true and use it when necessary.

Let \(\mathcal{I}\) be a set. A collection indexed by \(\mathcal{I}\) is a collection of sets \(\{S_i\}_{i\in \mathcal{I}}\). In other words, the collection contains one set for each element of \(\mathcal{I}\).

A choice function is a function \[f: \mathcal{I} \to \bigcup_{i\in \mathcal{I}} S_i\] such that \(f(i) \in S_i\) for all \(i \in \mathcal{I}\). The axiom of choice states that for any indexed collection of nonempty sets, there exists a choice function.

Another formulation of the axiom of choice is in terms of the Cartesian product of sets: the axiom of choice is the statement that the Cartesian product of an indexed collection of nonempty sets is nonempty: \[ S_i \ne \emptyset \,\, \forall\,\, i \in {\mathcal{I}} \Rightarrow \prod_{i\in\mathcal{I}} S_i \ne \emptyset. \]

Note that the axiom of choice is only an interesting statement when the indexing set \( \mathcal{I}\) is infinite: it is easy to show that a finite product of nonempty sets is nonempty without using the axiom of choice, e.g. by induction on the number of sets. While the axiom of choice does seem like a straightforward generalization of this property, it has many surprising consequences, some of which are listed in the next two sections.

The axiom of choice was initially introduced by Zermelo in order to prove the following theorem:

Well-ordering Theorem

Every set can be well-ordered: that is, there is a total order on the set such that every nonempty subset has a least element.

This ordering may not be the most obvious order. For instance, the set of real numbers with the usual order is not well-ordered, since many subsets of \( \mathbb R\) (including \( \mathbb R\) itself) do not have a least element. On the other hand, \( \mathbb N\) with its usual order is well-ordered; this is the content of the well-ordering principle.

It turns out that the well-ordering theorem is logically equivalent to the axiom of choice--that is, each one implies the other using only ZF set theory. Here is another equivalent statement that is often used in proofs:

Zorn's Lemma

Let \( X\) be a partially ordered set with the property that every chain in \(X\) has an upper bound in \( X.\) Then \( X\) contains a maximal element.

Recall that a chain is a set of elements of \( X\) which are all comparable to each other, an upper bound of a chain is an element that is comparable to and "greater than" all the elements of the chain, and a maximal element is an element \(x\in X\) such that there is no \( y \in X \) with \( x \prec y.\)

To summarize:

In ZF set theory,
\[
\text{Axiom of choice} \Leftrightarrow \text{Well-ordering theorem} \Leftrightarrow \text{Zorn's lemma.}
\]

Here is a partial list of other statements from other areas of mathematics which are logically equivalent to the axiom of choice. Note that many of them assert the existence of an object without giving a prescription for its computation, much like the axiom of choice itself. Intuitively, these nonconstructive existence results are precisely what the axiom of choice is useful for.

• Every vector space has a basis.

• Every nontrivial ring has a maximal ideal.

• A Cartesian product of (arbitrarily many) compact topological spaces is compact (Tychonoff's theorem).

• Any two sets either have the same cardinality, or one of them has a smaller cardinality than the other.

• Every connected graph has a spanning tree.

• Every surjective function \(f\colon X \to Y\) has a right inverse, i.e. a function \(g \colon Y\to X\) such that \( f\big(g(y)\big)=y\) for all \(y\in Y.\)

There are quite a few statements which are weaker than the axiom of choice--the axiom of choice can be used to prove them, but the reverse implication is not true.

• A union of countably many countable sets is countable.

• Every field has an algebraic closure; that is, if \( k\) is a field, there is an extension \( \overline{k}\) of \(k\) obtained by adjoining algebraic elements, such that every polynomial with coefficients in \( \overline{k}\) has a root in \( \overline{k}.\)

• Every Hilbert space has an orthonormal basis.

• The Banach-Tarski paradox: a 3-dimensional ball can be decomposed into finitely many disjoint subsets, which can be reassembled into two copies of the ball. \((\)The idea is that although this violates our notions of volume, these notions do not make sense for all subsets of \( {\mathbb R}^3.\) The axiom of choice is required to construct the "non-measurable" subsets in the decomposition.\()\)

A common joke [1] is as follows: "The axiom of choice is obviously true; the well-ordering [theorem] is obviously false; and who can tell about Zorn's lemma?" Of course, all three of these statements are logically equivalent; the point is that some forms of the axiom of choice are more intuitively believable than others.

Gödel showed that ZFC was logically consistent in 1938, and Paul Cohen showed that ZF\(\neg\)C was logically consistent in 1962. The upshot of this work was that there was no way to resolve the question of the truth or falsity of the axiom of choice using the axioms of ZF. The question of whether to assume the axiom of choice or its negation is more or less a question of "taste," and the consensus of the mathematical community is that the ZFC universe seems more natural than the ZF\(\neg\)C universe.

Nevertheless, there are mathematicians who either do not "believe in" the axiom of choice or who are interested in the logical repercussions of disallowing this axiom in their set theory. For instance, some mathematicians identified as "constructivists" believe that mathematical objects only exist if they can be constructed explicitly, so the axiom of choice and its nonconstructive nature are unacceptable. The majority of (non-logician) mathematicians view acceptance of the axiom of choice at least partly as a matter of convenience; the theoretical tools that the axiom of choice makes available allow for a richer theory in many contexts where it applies. For instance, knowing that every vector space has a basis can be helpful for proofs and other constructions, even when no explicit basis can be constructed.

It is standard for mathematicians to keep track of which results require the axiom of choice and which ones can be proved without it. The rest of the axioms of ZF set theory are essentially universally accepted, so it is helpful to be precise about exactly when the axiom of choice is unavoidable.

Here is a proof that the well-ordering theorem implies the axiom of choice. (The converse is more involved.)

Let \( S_i\) be a collection of nonempty sets indexed by \(\mathcal{I}.\) Then the union of the \( S_i\) can be well-ordered by the well-ordering theorem. So every subset of the union has a least element; so every \( S_i\) has a least element \(m_i.\) Define \(f \colon {\mathcal{I}} \to \cup_{i\in{\mathcal{I}}} S_i\) by \(f(i)=m_i.\) Then \(f\) is a choice function. \(_\square\)

The point is that the necessary choice is given to us for free by the well-ordering theorem.

Here is a typical example of a proof using Zorn's lemma that every vector space has a basis:

Let \(V\) be a vector space and let \( \mathcal{S}\) be the collection of linearly independent subsets of \( V,\) partially ordered by inclusion. Suppose we are given a chain of linearly independent subsets. Then the union of the subsets in the chain is an upper bound, and it is linearly independent: suppose that \( a_1v_1+\cdots+a_nv_n= 0\) for some \( v_i\) in the union and \(a_i\) in the field of constants. Since each \( v_i\) is in a subset of the chain, there must be some subset in the chain that contains them all. That subset is linearly independent, so all the \( a_i\) must be \(0.\)
\(\phantom{as}\)
Therefore, by Zorn's lemma, \(\mathcal{S}\) has a maximal element; call it \(B.\) Because \(B\) is maximal, this means that \( B\cup\{v\}\) is linearly dependent for \(v\notin B.\) The resulting dependence relation can be simplified to give an expression for \(v\) as a linear combination of elements of \(B\):
\[
\begin{align}
av+\sum_{i=1}^n a_i b_i &= 0 \\
\Rightarrow v &= \sum_{i=1}^n -\frac{a_i}{a} b_i.
\end{align}
\]
The key is that \(a\ne 0\) because otherwise there would be a dependence relation among the \(b_i,\) which is impossible because \(B\) is linearly independent. So \(v\) is in the span of \(B,\) and this is true for all \(v\notin B,\) so \(B\) spans \(V.\) So \(B\) is a basis.

Again, this is by no means an obvious result. For instance, \(\mathbb R\) is a vector space over \(\mathbb Q.\) The axiom of choice implies that it has a basis (and it is not hard to show that such a basis must be uncountable); but finding an explicit basis is basically impossible.

The following (difficult) problems explore some other consequences of the axiom of choice:

[1] This is due to Jerry Bona, as quoted in: Schechter, Eric. Handbook of Analysis and its Foundations. Academic Press, 1997, p. 145.