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,


  • 1
    $\begingroup$ 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}$. $\endgroup$ – Daniel Fischer Sep 30 '16 at 12:59
  • 1
    $\begingroup$ Have you browsed through the site? This was asked several times before. $\endgroup$ – 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.

  • $\begingroup$ I've edited the proof of the leftward implication following your advice; do you think it's correct now? Thank you for your time. $\endgroup$ – lorenzo Oct 2 '16 at 11:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 2 '16 at 19:17
  • $\begingroup$ I've corrected the proof again, it should be correct now; thank you very much for your help. $\endgroup$ – lorenzo Oct 2 '16 at 19:38
  • $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Oct 2 '16 at 19:44

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.