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.

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|improve this question
3  
What is the question? –  Did Feb 22 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 at 6:40
1  
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 at 6:42
2  
One. Two. Three. Four. Five. Six. And there are definitely more. –  Asaf Karagila Feb 22 at 6:57
add comment

4 Answers

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|improve this answer
add comment

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

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

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|improve this answer
add comment

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

share|improve this answer
    
I thought it's the case that a countable product of countable sets is countable. –  user125093 Feb 22 at 6:38
1  
Countable union of countable sets is countable. Perhaps that is what you had in mind. –  André Nicolas Feb 22 at 6:40
    
Andre, yeah that must be the source of the confusion. Thank you! –  user125093 Feb 22 at 6:41
add comment

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.