# 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 20th 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.

#### Contents

## Formal Statement

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.

## Well-ordering theorem and Zorn's lemma

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

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.(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.

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 everychainin \(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.}

\]

## Other equivalent statements

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(g(y))=y\) for all \(y\in Y.\)

## Statements implied by the axiom of choice

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.)

## Independence and controversy

A common joke [1] is: "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 identify as "constructivists"--they 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.

## Selected proofs

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 \\

v &= \sum_{i=1}^n (-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. \(\square\)

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.

Countably infinitely many mathematicians have been taken hostage. They are indexed by the positive integers (each mathematician knows their integer) and are standing in a line so that mathematician \(n\) can see each mathematician \(m\) for \(m>n\).

The mathematicians are each given a red or blue hat; they cannot see their own. Starting from the back (mathematician 1), each mathematician will guess their own hat color **(one at a time)**. They can hear all previous answers. All mathematicians who guess correctly may leave after their turn. The mathematicians are not allowed to communicate extra information other than their guess (e.g. by gesturing or changing tone) on pain of death to all the participants - they must simply guess.

Beforehand, the mathematicians have agreed upon a strategy to minimize the number of mathematicians who might guess incorrectly. Ignoring problems like limited vision or finite memory capacity and **assuming the axiom of choice holds**, what is the greatest possible number of mathematicians that might guess incorrectly?

###### This problem is original but based off of the famous red/blue hat puzzle. If you are stuck, try this problem first.

Countably infinitely many mathematicians have been taken hostage. They are indexed by the positive integers (each mathematician knows their integer) and are standing in a line so that mathematician \(n\) can see each mathematician \(m\) for \(m>n\).

The mathematicians are each given a red or blue hat; they cannot see their own. **Simultaneously**, the mathematicians will each guess their own hat colors. All mathematicians who guess correctly may leave. The mathematicians are not allowed to communicate extra information other than their guess (e.g. by gesturing) on pain of death to all the participants - they must simply guess.

Beforehand, the mathematicians have agreed upon a strategy to minimize the number of mathematicians who might guess incorrectly. Ignoring problems like limited vision or finite memory capacity and **assuming the axiom of choice holds**, what is the greatest possible number of mathematicians that might guess incorrectly?

###### This problem is not original. It seems similar to the famous red/blue hat puzzle, but looks can be deceiving.

## References

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