Axiom:Axiom of Choice

From ProofWiki
Jump to: navigation, search


Formulation 1

For every set of non-empty sets, we can provide a mechanism for choosing one element of each element of the set.

$\displaystyle \forall s: \left({\varnothing \notin s \implies \exists \left({f: s \to \bigcup s}\right): \forall t \in s: f \left({t}\right) \in t}\right)$

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

Formulation 2

Let $\left \langle {X_i} \right \rangle_{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 $\left \langle {x_i} \right \rangle_{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 $\mathcal S$ be a set of non-empty pairwise disjoint sets.

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


$\forall s: \left({ \left({\varnothing \notin s \land \forall t, u \in s: t = u \lor t \cap u = \varnothing}\right) \implies \exists c: \forall t \in s: \exists x: t \cap c = \left\{{x}\right\} }\right)$


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 Z-F axioms including the AoC is referred to as ZFC.

Additional forms

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

Historical Note

Ernst Zermelo exposited the axiom of choice in order to prove the Well-Ordering Theorem.

He himself did not invent the idea of choice; 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 September 24, 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: 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 nile $A, B, C, \ldots$ genau ein Element gemein hat.
A set $S$, which seperates 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.

Also see

  • Results about the Axiom of Choice can be found here.