I would like to know whether or not there exists a function
$$f: \mathbb{Q} \rightarrow \mathbb{N}$$
that is surjective but not injective?
I am rather new to the principle of cardinality. I know that $\mathbb{Q}$ has the same cardinality as $\mathbb{N}$ (with cardinality $\aleph _0$), so there has to be a surjective function between these two sets.
Now I was wondering, if there is one that is surjective but not injective (ie. not bijective). I would guess that one exists but I cannot think of an example.
Best Answer
Notice that $\mathbb{N} \subset \mathbb Q$. Therefore we can just define a function that maps every natural number to itself and maps the remaining elements to an arbitrary number. That way, we have guaranteed surjectivity (since very natural number will be mapped to), but we won't have injectivity since every rational number that is not a natural number will be mapped to the same number.
Here are 3 possible functions $f: \mathbb Q \rightarrow \mathbb N$; $g: \mathbb Q \rightarrow \mathbb N$; $h: \mathbb Q \rightarrow \mathbb N$ such that they are defined in the following way:
$$f(x) = \begin{cases} \space n & \text{if $x \in \mathbb N$} \\[.5em] \space 1 & \text{if $x \not \in \mathbb N$} \end{cases} $$
$$ $$ $$g(x) = \begin{cases} \space n & \text{if $x \in \mathbb N$} \\[.5em] \space 2 & \text{if $x \not \in \mathbb N$} \end{cases} $$
$$ $$ $$h(x) = \begin{cases} \space n & \text{if $x \in \mathbb N$} \\[.5em] \space 3 & \text{if $x \not \in \mathbb N$} \end{cases} $$
$$ ...... \space etc$$
A pattern of how we can define such functions in this particular case should (hopefully) be clear now. But there is more we can say …
You should notice that this is very generalizable. In fact the exact same argument could be made for any $A \subset B$ where $|A| = |B|$ by mapping all the elements of $A$ to itself and the remaining elements to an arbitrary point in the codomain (to ensure that injectivity will not hold).