# Uncountability of $\mathbb{R}$. Is this proof correct?

I'd like to know if this proof of $\mathbb{R}$ being uncountable is correct. (It came to my mind while reading this proof.)

$\mathbb{R}$ is countable iff there is a surjective function $f:\mathbb{N} \mapsto \mathbb{R}$. In order for such a function to exist, it must be true that $\mathbb{N} \supseteq \mathbb{R}$. But that is false, which means $\mathbb{R}$ is not countable.

-
That's wrong. $\mathbb{N} \nsupseteq \mathbb{Z}$, but $\mathbb{Z}$ is certainly countable. – Zhen Lin Oct 16 '11 at 20:27
Let $\mathbb{E}$ be the set of even natural numbers. There is an easy surjective function $f:\mathbb{E} \mapsto \mathbb{N}$, but $\mathbb{E} \supseteq \mathbb{N}$ is false. So the argument is not right. – André Nicolas Oct 16 '11 at 20:28
@Zhen Ah, right. – Paul Manta Oct 16 '11 at 20:28
This proof does not work. For infinite sets, it is possible for there to be a surjection from a proper subset of a set to the whole set. For example, the map from the even integers to $\mathbb Z$ given by $a \mapsto a/2$ is a surjection, but the even integers have the same cardinality as $\mathbb Z$. – user15464 Oct 16 '11 at 20:29
If this were true, then certainly the uncountability of $\mathbb{R}$ would have been proven much earlier in history. – Dustin Tran Oct 16 '11 at 22:11

## 2 Answers

No, that does not work. There is no definition that says that the image of a surjective function must be a subset of the domain. For example, $f(x)=\pi$ is a perfectly good surjective function $\mathbb N\to\{\pi\}$, but $\mathbb N\not\supseteq\{\pi\}$.

-

No, that argument doesn't work. For example, take the set $$\mathbf{N}=\{1',2',3',\ldots\}.$$ There is a surjective function $f:\mathbb{N}\to \mathbf{N}$, defined by $f(n)=n'$ for all $n\in\mathbb{N}$, which demonstrates that $\mathbf{N}$ is countable. However, as the symbols $n'$ are not natural numbers, $\mathbf{N}\not\subseteq\mathbb{N}$.

In general, if you are wondering whether such a statement is correct, ask yourself if what you mean would still be correct if you took the elements of your set and put $'$ on all of them, or painted them all red, or replaced each element with its identical twin (each of my professors has had their own funny way of saying this).

-