Equivalence of Versions of Axiom of Choice

From ProofWiki
Jump to navigation Jump to search

Theorem

The following formulations of the Axiom of Choice are equivalent:

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.

Symbolically:

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


Proof

Formulation 2 implies Formulation 1

Suppose that Formulation 2 holds.

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

Let $\mathcal C$ be a non-empty set of non-empty sets.

$\mathcal C$ may be converted into an indexed set by using $\mathcal C$ itself as the index and using the identity mapping on $\mathcal C$ to do the indexing.

Then the Cartesian product of all the sets in $\mathcal C$ has at least one element.

An element of such a Cartesian product is a mapping, that is a family whose domain is the indexing set which in this context is $\mathcal C$.

The value of this mapping at each index is an element of the set which bears that index.

So we have a mapping $f$ whose domain is $\mathcal C$ such that:

$A \in \mathcal C \implies f \left({A}\right) \in A$


Now let $\mathcal C$ be the set of all non-empty subsets of some set $X$.

Then the assertion means that there exists a mapping $f$ whose domain is $\mathcal P \left({X}\right) \setminus \left\{{\varnothing}\right\}$ such that:

$A \in \mathcal P \left({X}\right) \setminus \left\{{\varnothing}\right\} \implies f \left({A}\right) \in A$

That is, Formulation 1 holds.

$\Box$


Formulation 1 implies Formulation 2

The argument can be seen to be reversible.


$\Box$


Formulation 1 implies Formulation 3

Let $\mathcal S$ be the set:

$\mathcal S = \left \{ {s: \varnothing \notin s \land \forall t, u \in s: t = u \lor t \cap u = \varnothing}\right\}$

Let $c$ be a choice function on $\mathcal S$ and consider the image set $c[\mathcal S]$:

$c[\mathcal S] = \left\{{ c(s): \varnothing \notin s \land \forall t, u \in s: t = u \lor t \cap u = \varnothing} \right\}$

By the definition of a choice function, $c(s) \in s$.

By construction of $\mathcal S$, for any $s \in \mathcal S$, $s \cap c[\mathcal S] = \left \{ {c(s)}\right\}$.

$\blacksquare$

Formulation 3 implies Formulation 1

Let $\mathcal B$ be a non-empty collection of non-empty sets indexed by $\mathcal I$.

Consider sets of the following form:

$\mathcal C = \left\{ { (B_i,x): i \in \mathcal I, B_i \in \mathcal B, x \in B_i }\right\}$.

that is, it is the set of ordered pairs of which the first coordinate is a set $B_i \in \mathcal B$ and the second coordinate is an element of $B_i$.

This is, by construction, a subset of the cartesian product:

$\mathcal C \subseteq \displaystyle \mathcal B \times \bigcup_{i \in \mathcal I} B_i$

By hypothesis all sets $B$ are nonempty, thus there is at least one $(B_i,x)$ element in $\mathcal C$ for each $B_i \in \mathcal C$.

By Equality of Ordered Pairs, if $B_j \ne B_k$ in $\mathcal B$, then $(B_i,x) \ne (B_j,x)$ for all such pairs in $\mathcal C$.

So any two sets $\left\{ {(B_j,x):x \in B_j}\right\}$ and $\left\{ {(B_k,x):x \in B_k}\right\}$ are disjoint, by the inequality of their first coordinates.

Then $\mathcal C$ is a collection of disjoint nonempty sets in $\mathcal B \times \bigcup_{i \in \mathcal I} B_i$ and so satisfies the hypotheses of the third formulation of the Axiom of Choice. Let $c$ be a set satisfying $\forall r \in \mathcal C: c \cap r = \{t\}$.

All elements of $c$ are ordered pairs, the first coordinate of which is a set in $B_i \in \mathcal B$, and the second coordinate of which is an element $x \in B_i$. Viewed as a relation, each set in $\mathcal B$ bears $c$ to an element in that set. Every set in $\mathcal B$ bears $c$ to exactly one element inside that set. So $c$ is in fact a mapping and satisfies the criteria of a choice function as exposited in formulation $(1)$.

$\blacksquare$


Sources