Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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"? –  Hayden Jun 18 at 16:43
    
He is missing a "not" there ;-) –  Einer Jun 18 at 16:45
    
@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. –  Asaf Karagila Jun 18 at 16:46
    
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! –  Hayden Jun 18 at 16:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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