# 3 Statements of axiom of choice are equivalent

This winter I started to study much harder the set theory and especially the axiom of choice. Unfortunately, I have problems with solving the next exercise:

Prove that the 3 statements of the axiom of choice are equivalent :

1) For any non-empty collection $X$ of pairwise disjoint non-empty sets, there exists a choice set.

2) For any non-empty collection $X$ there is a choice function.

3) For any non-empty set $X$, there exists a function $f:P(X)\setminus\{\varnothing\}\to X$ so that for any non-empty set $A\subseteq X$, $f(A) \in A$.

-
Which of six possible implications between the statements can you prove by yourself? – Henning Makholm Jan 7 '12 at 19:37
In (2), you need that $X$ is a collection of non-empty sets, not a non-empty collection of sets. – JDH Jan 7 '12 at 19:39

$3\Rightarrow 2$: Suppose $X$ is a collection of nonempty sets, then $f:P(\bigcup X)\setminus\{\varnothing\}\to\bigcup X$ exists which chooses from every nonempty subset of $\bigcup X$. If we restrict $f$ to the set $X$ then we have a choice function.

$2\Rightarrow 3$: Trivial, if every non-empty collection of non-empty sets has a choice functions, given a non-empty $X$ we have that $P(X)\setminus\{\varnothing\}$ is a non-empty collection of non-empty sets, thus has a choice function.

$2\Rightarrow 1$: Trivial, if every collection has a choice function then every pairwise disjoint collection has a choice function $\{f(x)\mid x\in X\}$ is a choice set.

$1\Rightarrow 2$: Given $X$ a non-empty collection of non-empty sets, let $\{\{x\}\times x\mid x\in X\}$ be a collection of now pairwise disjoint sets. The cut set is a choice function. (You may want to show why they are pairwise disjoint, this is because if $x\neq y$ then $(\{x\}\times x)\cap(\{y\}\times y)=\varnothing$; also you might want to show why the choice set is a function, but it only meets $\{x\}\times x$ at one point... so functionality holds and it is indeed a choice function.)

-
I did some extra work, but it's good to see the direct implication between choice principles sometimes. – Asaf Karagila Jan 7 '12 at 20:38
Thank you very much! Truly, I had some problems with proving the implications. Now I think I can write down the proofs for all 6 implications! – Alice Jan 7 '12 at 20:52

I'll show you how to prove 3) implies 1), the rest should be relatively easy. So let $X$ be a nonempty set. For every nonempty subset $Y$ of $X$, let $Y^*=Y\times\{Y\}$. Then the family $\{Y^*:X\supseteq Y\neq\emptyset\}$ consists of disjoint nonempty sets, so there exists a choice set $C$. Let $f^*$ be the function that maps each nonempty set $Y\subseteq X$ to the unique element of $C$ that lies in $Y^*$. This isn't yet the function we want to construct. So let $\pi$ be the function that maps each element in $\{Y\times\{Y\}:X\supseteq Y\neq\emptyset\}$ (a ordered pair) to its first coordinate. Then letting $f=\pi\circ f^*$ gives you the needed function, as you can easily verify.

-
I must say that I still have a problem! I don't know how to prove these implications using a formal language, with logical notations, such as (if X=>it exists Y)and so on, and using the Zermelo-Fraenkel axioms. – Alice Jan 8 '12 at 18:21
I guess the tricky part is the existence of these functions. In principle, a functon is identified with its graph. So $f^*$ is a subset of $F=\{Y\times\{Y\}:X\supseteq Y\neq\emptyset\}\times C$. In detail: $f^*=\{(a,b)\in F:\exists Y: a=Y\times\{Y\}\wedge b\in Y\times\{Y\}\}$. Using the axioms gets a bit tedious, but you really just have to know that cartesian products exist and define the formula by an axiom of specification. A completely formal proof is likely to be very long. – Michael Greinecker Jan 8 '12 at 19:32