Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I thought the set of natural number functions would be of the same cardinality as the countably infinite product of $\mathbb{N}$, which is countable.

Each natural number function can be identified with an infinite-tuple of $\mathbb{N}$ by letting the $i$th entry be the image of the number $i$ under the function.

share|cite|improve this question
What is the question? – Did Feb 22 '14 at 6:36
I'm wondering where I went wrong in my thoughts on this problem, since I would say the set of functions is countable, but I know that it's actually uncountable. – user125093 Feb 22 '14 at 6:40
Ergo the "argument" that the product of countably many countable sets is countable is at best fishy, no? Actually this argument is wrong and you are probably mixing it up with the fact that the union of countably many countable sets is countable – Did Feb 22 '14 at 6:42
One. Two. Three. Four. Five. Six. And there are definitely more. – Asaf Karagila Feb 22 '14 at 6:57

Every real number in $(0,1)$ has either one or two decimal representations. (Some have two, like $0.1000\ldots$ which is equal to $0.0999\ldots$.) But any way, each real number in $(0,1)$ gives at least one decimal representation. And that decimal representation can be viewed as a function from $\mathbb{N}$ to $\mathbb{N}$ by taking the $n$th digit after the decimal. (Actually, it's more restrictive: from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$.)

For example, $0.72465\ldots$ can be used to define a function $$\begin{align}1&\mapsto7\\ 2&\mapsto2\\ 3&\mapsto4\\ 4&\mapsto6\\ 5&\mapsto5\\ \vdots&\phantom{\mapsto{}}\vdots\end{align}$$

So the set of functions from $\mathbb{N}$ to $\mathbb{N}$ contains a subset that is as large as the real interval $(0,1)$. (And seemingly even stronger, so does the set of functions from $\mathbb{N}$ to $\{0,1,2,3,4,5,6,7,8,9\}$. And seemingly even stronger still, if we used binary instead of decimal, so does the set of functions from $\mathbb{N}$ to $\{0,1\}$.)

share|cite|improve this answer

Cantors diagonalisation method: If it is countable then it is $F=\{f_1,f_2,\ldots\}$. But the function $g(i):=f_i(i)+1$ is not in $F$. A contradiction to the initial assumption.

share|cite|improve this answer

The cardinality of the natural number functions is $\mathbb{N}^{\mathbb{N}} \geq 2^{\mathbb{N}}$ and $2^{\mathbb{N}}$ is uncountable

share|cite|improve this answer
$\geq$ actually (and indeed $=$, I believe). – Eric Stucky Feb 22 '14 at 6:42
@Eric Stucky: thanks – WLOG Feb 22 '14 at 6:47

The countably infinite product of $\mathbb{N}$ is not countable, I believe, by Cantor's diagonal argument.

share|cite|improve this answer
I thought it's the case that a countable product of countable sets is countable. – user125093 Feb 22 '14 at 6:38
Countable union of countable sets is countable. Perhaps that is what you had in mind. – André Nicolas Feb 22 '14 at 6:40
Andre, yeah that must be the source of the confusion. Thank you! – user125093 Feb 22 '14 at 6:41
I have a question. Is the union of the set of natural number functions countable? – Valentino Feb 19 '15 at 18:15
@valentino That is actually the same thing as the countably infinite product of $\mathbb{N}$. Both can be abbreviated $\mathbb{N}^\mathbb{N}$. This is the same as how $\mathbb{R}^3$ can be seen as the space of functions from $\{1,2,3\} \to \mathbb{R}$ – Eric Auld Feb 19 '15 at 18:25

Your Answer


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.