# Exercise on the Axiom of Choice

I'm working on a proof of the following theorem:

"Let $I$ be a set, and for each $\alpha\in I\$ let $X_{\alpha}$ be a non-empty set. Suppose that all the sets $X_{\alpha}$ are disjoint from each other, i.e. $X_{\alpha}\cap X_{\beta} =\emptyset$ for all distinct $\alpha , \beta \in I$. Using the axiom of choice, show that there exists a set $Y$ such that $\#(Y \cap X_{\alpha})=1\ \forall\alpha\in I$ (i.e. $Y$ intersect each $X_{\alpha}$ in exactly one element). Conversely, show that if the above statement was true for an arbitrary choice of sets $I$ and non-empty disjoint sets $X_{\alpha}$, then the axiom of choice is true".

Axiom of Choice (as written in the text I'm reading):

"Let $I$ be a set, and for each $\alpha\in I$ let $X_{\alpha}$ be a non-empty set. Then there exists a function which assigns to each $\alpha\in I$ an element $x_{\alpha} \in X_{\alpha}$."

Proof. For the rightward implication, since we assume the Axiom of Choice, we have that there exists a function $f\colon I\to \bigcup X_{\alpha}$ which assigns to each $\alpha\in I$ an element $x_{\alpha} \in X_{\alpha}$ thus the set $Y:=\{f(\alpha):\alpha\in I\}$ is the set asked for.

EDIT (LEFTWARD IMPLICATION). Let $I$ be a set, and for each $\alpha\in I$ let $X_{\alpha}$ be a non-empty set. For each $\alpha\in I$ let $Z_{\alpha}:=\{\alpha\}\times X_{\alpha}=\{(\alpha , x):x\in X_{\alpha}\}$. Suppose there exists $\alpha , \beta\in I, \alpha\neq\beta$ such that $Z_{\alpha}\cap Z_{\beta}\neq\emptyset$; this would mean that there exists $\gamma$ such that $\gamma =(\alpha , \overline{x})$ for some $\overline{x}\in X_{\alpha}$ and $\gamma =(\alpha , \tilde{x})$ for some $\tilde{x} \in X_{\beta}$ which means that $(\alpha , \overline{x})=(\beta , \tilde{x})$ which implies that $\alpha =\beta$, a contradiction. Thus the $Z_{\alpha}$ are all disjoint and so by the hypothesis we have that there exists a set $Y$ such that $\#(Y\cap Z_{\alpha})=1\ \forall\alpha\in \ I$. Now, let $f\colon I\to \cup_{\alpha\in I} Z_{\alpha}$ be the function such that $f(\alpha )=(\alpha , x)\in Y\cap Z_{\alpha} \forall\alpha\in\ I$ and $g\colon \cup_{\alpha\in I} Z_{\alpha} \to \cup_{\alpha\in I} X_{\alpha}$ be the function such that $g((\alpha , x))=x\in X_{\alpha} \forall\alpha\in\ I$. Then if we take $g\circ f\colon I\to\cup_{\alpha\in I} X_{\alpha}$ we have a function which assigns to each $\alpha\in I$ an element $x\in X_{\alpha}$, as required by the Axiom of Choice.

Best regards,

lorenzo

• Do something to the $X_{\alpha}$ to get a family of disjoint sets, each of which has an obvious (choice-free) bijection to the corresponding $X_{\alpha}$. – Daniel Fischer Sep 30 '16 at 12:59
• Have you browsed through the site? This was asked several times before. – Asaf Karagila Sep 30 '16 at 13:05

Your second proof really doesn’t make sense. You want to show that if a certain hypothesis holds, then every indexed family of non-empty sets has a choice function, so you should start by letting $\mathscr{X}=\{X_\alpha:\alpha\in I\}$ be an arbitrary indexed family of non-empty sets. If $\mathscr{X}$ is a pairwise disjoint family, then your hypothesis tells you that there is a set $Y$ such that $|Y\cap X_\alpha|=1$ for each $\alpha\in I$, and you can then define $f(\alpha)$ to be the unique element of $Y\cap X_\alpha$ for each $\alpha\in I$, but the family $\mathscr{X}$ may not be pairwise disjoint. And if $\mathscr{X}$ isn’t pairwise disjoint, you have no way to get the set $Y$ that you want to use to define $f$.

HINT: For each $\alpha\in I$ let $D_\alpha=\{\alpha\}\times X_\alpha$, and let $\mathscr{D}=\{D_\alpha:\alpha\in I\}$. Use your idea to find a choice function for $\mathscr{D}$, and then use that to get one for $\mathscr{X}$.

Added: Your edit is fine up through the point at which you state the existence of $Y$. Your definition of $f$ is also correct, but it could be stated a bit more clearly. I would say something like this:

Let $f:I\to\bigcup_{\alpha\in I}Z_\alpha$ be defined by letting $f(\alpha)$ be the unique element of $Y\cap Z_\alpha$ for each $\alpha\in I$.

There’s no need to clutter up the codomain with $Y$. (If you wanted to be really formal, you could let

$$f=\left\{\langle\beta,z\rangle\in\bigcup_{\alpha\in I}Z_\alpha:Y\cap Z_\beta=\{z\}\right\}\;,$$

but that’s overkill in most contexts.) Your definition of $g$, however, doesn’t actually define anything, because you’ve not specified how $x$ is related to $z$. What you want, I expect, is that

$$g:\bigcup_{\alpha\in I}Z_\alpha\to\bigcup_{\alpha\in I}X_\alpha:\langle\alpha,x\rangle\mapsto x\;.$$

Then it is indeed the case that $g\circ f:I\to\bigcup_{\alpha\in I}X_\alpha$ is the desired choice function.

• I've edited the proof of the leftward implication following your advice; do you think it's correct now? Thank you for your time. – lorenzo Oct 2 '16 at 11:12
• @lorenzo: I’ve added to my answer a response to your edit. What you’ve done is basically correct, but it has one genuine oversight and could be made a bit more readable. – Brian M. Scott Oct 2 '16 at 19:17
• I've corrected the proof again, it should be correct now; thank you very much for your help. – lorenzo Oct 2 '16 at 19:38
• @lorenzo: You still need to make explicit the relationship between $z$, on the one hand, and $x$ and $\alpha$, on the other, in your definition of $g$. You can do it very simply by writing $g(\langle\alpha,x\rangle)=x$ where you now have $g(z)=x\in X_\alpha$. (You’re very welcome.) – Brian M. Scott Oct 2 '16 at 19:44