# Definition of denumerable (countable) set

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.

-

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.

-
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. – Rudy the Reindeer Nov 5 '12 at 9:41

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.

-