Axiom:Axiom of Choice

From ProofWiki
Jump to navigation Jump to search

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 section
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

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

Retrieved from "https://proofwiki.org/w/index.php?title=Axiom:Axiom_of_Choice&oldid=729464"