# Prove or disprove that a set E is at most countable.

I was given this question during an in-class quiz today:

Suppose that E is a set. If there exists a function f from E onto $\mathbb{N}$, then E is at most countable.

I understand that this can be disproved, but I couldn't think of a counterexample. To start E should be equal to the set $\mathbb{R}$, but I'm not sure what my function f should be.

Any help would be appreciated. Thanks in advance!

• Is there a reason that taking say the ceiling function wouldn't work (from $\mathbb{R}_+ \mapsto \mathbb{N})$? – David Mar 1 '17 at 5:55

If $f$ is onto, then this means that $f$ is a surjection: all elements in $\mathbb{N}$ are mapped to by some elements in $E$. However, multiple elements in $E$ can map to the same element in $\mathbb{N}$!

You see the problem: this means that we can potentially map some uncountable set, like $\mathbb{R}$, onto $\mathbb{N}$, so long as the function is set up to map every real number to a natural number. So why don't we construct such a function $f$? How about this:

$$f(x) = \begin{cases} x \text{ if x is an integer} \\ 0\text{ otherwise }\end{cases}$$

Then $f$ maps $\mathbb{R}$ onto $\mathbb{N}$, but $\mathbb{R}$ is not countable, as you know. Thus, in this case, we have a set $E$ which is uncountable. Thus, the proposition is false.

For what it's worth, the proposition is true if $f$ is an injection or a bijection. (Prove this yourself.)

What about $f(x)= \begin{cases} [x+1] & x \ge 0 \\ f(x)= -[x] & x \lt 0 \end{cases}$

($[ \cdot ]$ is greatest integer function).