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'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.

share|cite|improve this question
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
up vote 6 down vote accepted

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\}$.

share|cite|improve this answer

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).

share|cite|improve this answer

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.