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!

  • 1
    $\begingroup$ Is there a reason that taking say the ceiling function wouldn't work (from $\mathbb{R}_+ \mapsto \mathbb{N})$? $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.