# Axiom:Axiom of Choice

## Axiom

### Formulation 1

For every set of non-empty sets, it is possible to provide a mechanism for choosing one element of each element of the set.

- $\ds \forall s: \paren {\O \notin s \implies \exists \paren {f: s \to \bigcup s}: \forall t \in s: \map f t \in t}$

That is, one can always create a choice function for selecting one element from each element of the set.

### Formulation 2

Let $\family {X_i}_{i \mathop \in I}$ be an indexed family of sets all of which are non-empty, indexed by $I$ which is also non-empty.

Then there exists an indexed family $\family {x_i}_{i \mathop \in I}$ such that:

- $\forall i \in I: x_i \in X_i$

That is, the Cartesian product of a non-empty family of sets which are non-empty is itself non-empty.

### Formulation 3

Let $\SS$ be a set of non-empty pairwise disjoint sets.

Then there exists a set $C$ such that for all $S \in \SS$, $C \cap S$ has exactly one element.

Symbolically:

- $\forall s: \paren {\paren {\O \notin s \land \forall t, u \in s: t = u \lor t \cap u = \O} \implies \exists c: \forall t \in s: \exists x: t \cap c = \set x}$

### Formulation 4

Let $A$ be a non-empty set.

Then there exists a mapping $f: \powerset A \to A$ such that:

- for every non-empty proper subset $x$ of $A$: $\map f x \in x$

where $\powerset A$ denotes the power set of $A$.

## Comment

This page has been identified as a candidate for refactoring of medium complexity.In particular: Decide how best to farm out the discussion in this sectionUntil this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

Although it seems intuitively obvious ("surely you can just pick an element?"), when it comes to infinite sets of sets this axiom leads to non-intuitive results, notably the famous Banach-Tarski Paradox.

For this reason, the **Axiom of Choice** (often abbreviated **AoC** or **AC**) is often treated separately from the rest of the Zermelo-Fraenkel Axioms.

Set theory based on the Zermelo-Fraenkel axioms is referred to ZF, while that based on the ZF axioms including the **AoC** is referred to as ZFC.

## Examples

### Russell's Socks and Shoes

Suppose we have an infinite number of pairs of socks.

Using the **Axiom of Choice**, we can simultaneously pick one sock from each pair.

However, if we also have a infinite number of pairs of shoes, we no longer need the **Axiom of Choice** to pick one shoe from each pair.

We simply choose the left one.

## Additional forms

The following are equivalent, in ZF, to the **Axiom of Choice**:

## Also see

- Results about
**the Axiom of Choice**can be found**here**.

## Historical Note

Ernst Zermelo exposited the **Axiom of Choice** in order to prove what is now known as Zermelo's Well-Ordering Theorem.

He himself did not invent the idea of the choice function; he explains that he is merely formalizing a concept ubiquitous in mathematics.

Formulation 1 and formulation 2 are written in a letter from Zermelo to David Hilbert, postmarked $24$ September $1904$:

*Der vorliegende Beweis beruht auf der Voraussetzung [...] daß es auch für eine unendliche Gesamtheit von Mengen immer Zuordnungen gibt, bei denen jeder Menge eines ihrer Elemente entspricht, oder formal ausgedrückt, daß das Produkt einer unendlichen Gesamtheit von Mengen, deren jede mindestens ein Element enthält, selbst von Null verschieden ist.*

*The present proof is based on the presumption [...] that even for an infinite assembly of sets, there are always assignments in which each set corresponds to one of its elements, or formally expressed, that the product of an infinite assembly of sets, each of which holds at least one element, is itself different from zero.*

Zermelo wrote formulation 3 in 1908: *Neuer Beweis für die Möglichkeit einer Wohlordnung* ("A new proof of the possibility of well-ordering") (*Math. Ann.* **Vol. 65**: pp. 107 – 128)

*Eine Menge $S$, welche in eine Menge getrennter Teile $A, B, C, \ldots$ zerfällt, deren jeder mindestens ein Element enthält, besitzt mindestens eine Untermenge $S_1$, welche mit jedem der betrachteten Teile $A, B, C, \ldots$ genau ein Element gemein hat.*

*A set $S$, which separates into a set of divided parts $A, B, C, \ldots$ each of which contains at least one element, has at least one subset $S_1$, which in turn has in common with each part $A, B, C, \ldots$ exactly one element.*

Kurt Gödel showed in $1938$ that the **Axiom of Choice** is not disprovable in Zermelo-Fraenkel set theory (ZF).

Paul Cohen showed in $1963$ that neither is the **Axiom of Choice** provable in ZF.

## Sources

- 1967: George McCarty:
*Topology: An Introduction with Application to Topological Groups*... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Composition of Functions - 1996: H. Jerome Keisler and Joel Robbin:
*Mathematical Logic and Computability*... (previous) ... (next): Appendix $\text{A}.7$: Inverses - 1998: David Nelson:
*The Penguin Dictionary of Mathematics*(2nd ed.) ... (previous) ... (next):**axiom of choice** - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next):**axiom of choice** - 2010: Raymond M. Smullyan and Melvin Fitting:
*Set Theory and the Continuum Problem*(revised ed.) ... (previous) ... (next): Chapter $1$: General Background: $\S 5$ The continuum problem

- Weisstein, Eric W. "Zermelo-Fraenkel Axioms." From
*MathWorld*--A Wolfram Web Resource. https://mathworld.wolfram.com/Zermelo-FraenkelAxioms.html - Bell, John L., "The Axiom of Choice", The Stanford Encyclopedia of Philosophy (Winter 2021 Edition), Edward N. Zalta (ed.), URL = <https://plato.stanford.edu/archives/win2021/entries/axiom-choice/>.