Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

2 Answers

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.