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

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I did some extra work, but it's good to see the direct implication between choice principles sometimes. $\endgroup$ – Asaf Karagila♦ Jan 7 '12 at 20:38
  • $\begingroup$ 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! $\endgroup$ – Alice Jan 7 '12 at 20:52
  • $\begingroup$ Dear Asaf, what do you mean here by "cut set"?? $\endgroup$ – AgentSmith Apr 14 '17 at 17:59
  • $\begingroup$ @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.) $\endgroup$ – Asaf Karagila♦ Apr 14 '17 at 18:20
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Alice Jan 8 '12 at 18:21
  • $\begingroup$ 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. $\endgroup$ – Michael Greinecker♦ Jan 8 '12 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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