You are here
Homeaxiom of choice
Primary tabs
axiom of choice
The ZermeloFraenkel axioms for set theory are often accepted as a basis for an axiomatic set theory. On the other hand, the axiom of choice is somewhat controversial, and it is currently segregated from the ZF system of set theory axioms. When the axiom of choice is combined with the ZF axioms, the whole axiom system is called “ZFC” (for “ZermeloFraenkel with Choice”).
Axiom (Axiom of choice).
Let $C$ be a set of nonempty sets. Then there exists a function
$f\colon C\to\bigcup_{{S\in C}}S$ 
such that $f(x)\in x$ for all $x\in C$.
The function $f$ is sometimes called a choice function on $C$.
For finite sets $C$, a choice function can be constructed without appealing to the axiom of choice. In particular, if $C=\varnothing$, then the choice function is clear: it is the empty set! It is only for infinite (and usually uncountable) sets $C$ that the existence of a choice function becomes an issue. Here one can see why it is not considered “obvious” and always taken for an axiom by everyone: one really cannot imagine any process which makes uncountably many selections without also imagining some rule for making the selections. Given such a rule, the axiom of choice is not needed. Thus, objects that are proved to exist using the axiom of choice cannot generally be described by any kind of systematic rule, for if they could it would not be necessary to their construction.
Let us consider a couple of examples. Imagine that there are infinitely many pairs of shoes (each consisting of one left shoe and one right shoe). Let $\mathcal{P}$ denote the set of all pairs of shoes. In this scenario, it can be verified that the function $\displaystyle f\colon\mathcal{P}\to\bigcup\mathcal{P}$ defined by $f(P)=\text{ the left shoe of }P$ is a choice function. Similarly, imagine that there are infinitely many pairs of socks. Let $\mathcal{S}$ denote the set of all pairs of socks. In this scenario, one cannot assume that a function $\displaystyle g\colon\mathcal{S}\to\bigcup\mathcal{S}$ exists without appealing to the axiom of choice (or something equivalent to it). Note that this scenario cannot be resolved in the same manner as the previous scenario because most people do not differentiate between a ”left sock” and a ”right sock”.
Strange objects that can be constructed using the axiom of choice include nonmeasurable sets (leading to the Hausdorff and BanachTarski paradoxa), and Hamel bases for any vector space. A Hamel basis may not seem strange, but try to imagine a set $S$ of continuous functions such that every continuous function can be expressed uniquely as a linear combination of finitely many elements of $S$. Since in fact the existence of a basis for every vector space is equivalent to the axiom of choice, it is almost guaranteed that no such set $S$ can ever be described. It is for this reason that some mathematicians dislike the axiom of choice.
On the other hand, many very useful facts can be proven using the axiom of choice. For example, the fact that every vector space has a basis, every ring with identity element $1\neq 0$ has a maximal ideal and many other algebraic theorems which are difficult or impossible to prove without using the axiom of choice.
In pure set theory, the axiom of choice is only relevant where most people’s intuition more or less breaks down, when dealing with hierarchies of uncountable infinities.
The relevance of the axiom of choice to various branches of mathematics has led to a detailed study of its truth. It turns out that if the ZermeloFraenkel axioms are consistent, then they remain consistent upon adding the axiom of choice. But they also remain consistent upon adding the negation of the axiom of choice (see [G] and [C]).
Some mathematicians have suggested an axiom that would result in all subsets of the real numbers being measurable; this would of course imply the negation of the axiom of choice.
There are many alternative formulations of the axiom of choice, although it is not always trivial to prove equivalence. These include:

The generalized Cartesian product of a nonempty family of sets is nonempty iff every set is nonempty. Due to this equivalence the axiom of choice is sometimes called the multiplicative axiom (Proof).

Every ring with identity element $1\neq 0$ has a maximal ideal (Proof).

Every surjection is a retraction (Proof).

Every tree has a branch.

Tukey’s lemma (Proof).

Zorn’s lemma (Proof).
Figure 1 shows how these equivalences are proven on PlanetMath.
AC  Axiom of Choice 

Hamel  Every vector space has a basis 
Hausdorff  Hausdorff’s maximum principle 
König  König’s theorem 
Krull  Every ring with identity element $1\neq 0$ has a maximal ideal 
Tukey  Tukey’s lemma 
Well  Zermelo’s wellordering theorem 
Zorn  Zorn’s lemma 
References
 C P. J. Cohen, The independence of the continuum hypothesis. I, II, Proc. Natl. Acad. Sci. USA 50, 1143–1148 (1963); 51, 105–110 (1964).
 G K. Gödel, The consistency of the axiom of choice and of the generalized continuumhypothesis, Proc. Natl. Acad. Sci. USA 24, 556–557 (1938).
Mathematics Subject Classification
03E30 no label found03E25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Attached Articles
Corrections
Koenig's Theorem by yark ✓
update diagram by Wkbj79 ✓
Typo by mrd ✓
problem in page image mode by yark ✓
Comments
update diagram
I am uncertain as to what the protocol is for this situation. I wanted to point out that the diagram in the entry, axiom of choice, should be updated because I have supplied a proof for the fact that the wellordering principle implies the axiom of choice. If I were to file a correction, GrafZahl would be the only person guaranteed to see it. On the other hand, this object is still worldeditable, so if someone else knows how to fix the diagram and wants to do so, they can. I myself am still clueless about making/editing diagrams in TeX.
Will this post suffice, or should I file a correction to the entry ``axiom of choice''?
Thanks,
Warren
Re: update diagram
Actually, yark discusses that the wellordering principle implies the axiom of choice in the entry ``choice function'', so I might need to delete my entry. In any case, though, the diagram still needs to be updated.
Re: update diagram
Wkbj79 writes:
> Actually, yark discusses that the wellordering
> principle implies the axiom of choice in the entry
> ``choice function'', so I might need to delete my entry.
The choice function article only mentions it in passing. I don't see that this is any reason for you to delete your entry.