Equivalence of Versions of Axiom of Choice/Formulation 2 implies Formulation 1

From ProofWiki
Jump to navigation Jump to search

Theorem

The following formulation of the Axiom of Choice:

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.

$\displaystyle \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.


implies the following formulation of the Axiom of Choice:

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.


Proof

Suppose that Formulation 2 holds.

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

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

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

Then the Cartesian product of all the sets in $\CC$ 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 $\CC$.

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 $\CC$ such that:

$A \in \CC \implies \map f A \in A$


Now let $\CC$ 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 $\powerset X \setminus \set \O$ such that:

$A \in \powerset X \setminus \set \O \implies \map f A \in A$

That is, Formulation 1 holds.

$\blacksquare$


Sources