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.