Take the 2-minute tour ×

When we say that a set $S$ is denumerable, that is, there is a bijection $S \to \omega$, do we mean that there exists such a bijection or do we mean that we have one and are talking about a pair $(S,f)$?

I'm asking because it makes a difference to whether I need choice in some proofs or whether I don't. For example, if we prove that a denumerable union of denumerable sets is denumerable we need countable choice to prove it if we assume the former definition and we do not need choice at all if we assume the latter.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

Denumerable means there exists a bijection between the given set and the set $\mathbb {N}$. This indeed, as you point out, creates subtleties for certain proofs. Further to your comment about the countable union of countable sets being countable, it can be shown that without countable choice this result is false. That is, there exists models of ZF where the countable union of countable sets is not countable.

share|improve this answer
Thank you! Very nice how your last 2 sentences rule out the possibility of pairs $(S,f)$ in the definition of denumerable. I like answers that are short and to the point. –  Matt N. Nov 5 '12 at 9:41
add comment

A set is countable if there exists a bijection with $\omega$. Much like a set is finite if and only if is has a bijection with a finite ordinal.

In the proof that a countable union of countable sets is countable we indeed choose a bijection with $\omega$, and if we were given such bijection to begin with then the axiom of choice is indeed redundant.

However the definitions of countability should never require an explicit bijection to be present. It would contradict a very natural and basic understanding of what a finite set is:

Consider a model in which there exists a countable set of pairs without a choice function. The union of these pairs is uncountable, and it is uncountable only because we cannot choose bijections of the pairs with the set $\{0,1\}$. It is unreasonable that a set with two elements is not finite just because it does not have a coupled bijection, right? This intuition is carried over to the genreal case. Cardinality is about the existence of a bijection, not about the explicitness of this function.

share|improve this answer
add comment

Your Answer


