3
$\begingroup$

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

  • 1
    In (2), you need that $X$ is a collection of non-empty sets, not a non-empty collection of sets.2012-01-07

2 Answers 2

6

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

  • 0
    @UtkuOkur: Probably a typo for "choice set". Thanks. (No need to bump this old question, methinks, especially now when this is clarified in the comments.)2017-04-14
3

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.

  • 0
    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.2012-01-08