My current understanding of the Axiom of Countable Choice is that the following example needs it in order to work:

Let $X$ be a countable family of finite sets. Then there exists a choice function $f$ choosing for each $x$ a bijection between $x$ and a natural number $n$.

It seems to me that we need to use the Axiom of Countable Choice, and that the finiteness of the elements of $X$ does not change this.

Is this indeed the case: is the Axiom of Countable Choice needed to define such a set? Why or why not?


Yes, we need the axiom of countable choice for choosing such bijections.

If we can choose a bijection for each finite set, then their union is countable, since we can map it into $\omega\times\omega$ in the obvious way.

An example of a countable set of finite sets, even pairs, whose union is not countable, if so, is an example of a countable family of finite sets that we cannot choose uniformly bijections for all pairs.

For example, consider the mathematical realization of Russell's socks example. It is consistent that there is a countable family of pairs, that does not admit a choice function. If the union of these pairs would have been countable, or even linearly orderable, then we could have chosen the least one from each set. Since we cannot do that (within that particular model of set theory), that union is not countable, and we cannot choose an enumeration for each pair uniformly.

It should, perhaps, be pointed out that in the case of finite sets this is weaker than the axiom of countable choice. This is not a trivial theorem, but an important nonetheless.

Countable choice implies the countable union of countable sets are countable implies every countable family of finite sets admits a choice function (is equivalent to your question about choosing enumerations).

None of the implications are reversible.

  • $\begingroup$ Yes, I meant for the family to be countable, I've added that. When you say that the two limitations do imply one another, are you specifically referring to an equivalence of the Axiom of Countable choice and the "Axiom of Choice for Families of finite sets"? $\endgroup$ – Hayden Jun 18 '14 at 16:43
  • $\begingroup$ He is missing a "not" there ;-) $\endgroup$ – Stefan Mesken Jun 18 '14 at 16:45
  • $\begingroup$ @Hayden: I indeed miss a "not" there. But now I read the question in a whole other light. So I'll delete its current content and rewrite it. $\endgroup$ – Asaf Karagila Jun 18 '14 at 16:46
  • $\begingroup$ Ah, that makes more sense to me. I was confused how they could imply one-another. Sorry for missing the integral data in the question! $\endgroup$ – Hayden Jun 18 '14 at 16:47

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.