1
$\begingroup$

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.

  • 1
    That's wrong. $\mathbb{N} \nsupseteq \mathbb{Z}$, but $\mathbb{Z}$ is certainly countable.2011-10-16
  • 1
    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.2011-10-16
  • 0
    @Zhen Ah, right.2011-10-16
  • 1
    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$.2011-10-16
  • 0
    If this were true, then certainly the uncountability of $\mathbb{R}$ would have been proven much earlier in history.2011-10-16

2 Answers 2

6

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

4

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