Why we don't need Axiom of Choice to prove the following statement

Let $S_{\alpha}, \alpha \in A$ be a family of disjoint nonempty sets, and consider $P = \bigcup_{\alpha \in A} S_{\alpha}$. If $|A|$ is finite then there exists $Q \subset P$ such that for each $\alpha \in A$, we have $|Q \cap S_{\alpha}| = 1$

with this as the proof (taken from https://math.stackexchange.com/a/29383/)

Since each of the $S_\alpha$'s are nonempty, then by definition for each $\alpha$ there exits $b_{\alpha} \in S_{\alpha}$. So $Q = \{b_{\alpha} | \alpha \in A \}$ works.

But apparently we do need Axiom of Choice to prove the exact same hypothesis with just the hypothesis ``$|A|$ is finite" removed.

Can someone provide some intuition on why the proof won't work for infinite $A$ ?

  • $\begingroup$ In the proof you adjointed there is a step where they use a choice function. So that's why it doesn't work for finite sets $\endgroup$ – miraunpajaro Aug 29 '19 at 13:35
  • $\begingroup$ math.stackexchange.com/questions/85153/… math.stackexchange.com/questions/717961/… and I feel like we've covered this before a lot on the site. Did you go through some of the old questions about this subject? $\endgroup$ – Asaf Karagila Aug 29 '19 at 14:47
  • $\begingroup$ The proof you said was "taken from math.stackexchange.com/a/29383" doesn't seem to actually be there. Furthermore, your formulation of the proof is confusing because it never explicitly uses the finiteness of $A$ (whereas the linked answer to the earlier question does). $\endgroup$ – Andreas Blass Aug 29 '19 at 18:42

You're choosing the $b_\alpha$. If you can specify a way to single out a unique $b_\alpha$ for each $\alpha$ (including if $|A|$ is finite, and you, say, list the $b_\alpha$ explicitly), the axiom schema of replacement can tell you that $\{b_\alpha\mid \alpha\in A\}$ is a set. If not, then none of the ZF axioms let you say that $\{b_\alpha\mid \alpha\in A\}$ (whatever it now is) is a set. That's exactly what the Axiom of Choice does.

So without Chioce, and with infinite $|A|$, in general a collection of the form $\{b_\alpha\mid \alpha\in A\}$ will not be a set. With Choice, you know that there is at least one such set, although it doesn't say in any way how the $b_\alpha$ in such a set were chosen.


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.