Find an infinite set $S$ and a function $g : S \to S$ that is surjective but not injective.

Question

Find an infinite set $S$ and a function $g : S \to S$ that is surjective but not injective.

This is all that is given in the problem. Should I fix $S$ to be a certain set, like the integers, or natural numbers, and work from there? Or should I just create a function, like $f(x) = x^2$? Any guidance would be appreciated.

What about this: Let $S$ be $\mathbb{R}$, and let $g : S \to S$ be defined by $f(x) = x^2$. This is surjective but not injective.

EDIT 11/27, 3:53pm CT: I totally confused myself about what it means to be surjective. I'm not sure what I was thinking. Clearly, $f(x) = x^2$ is not surjective since each y-coordinate is not mapped to.

Answer 1

Your proposed function won't work because it is not surjective. For example, $-1$ has no preimage but $-1 \in \mathbb{R}$.

Possible direction:

To make it work, for example, you can let $S$ be the set of nonnegative integer.

Let $g(0)=0=g(1)$, $g(2)=1=g(3)$, and et cetera.

Try to come out with a rule to describe what I did.

Answer 2

What about this: Let S be $\mathbb{R}$, and let g : S → S be defined by f(x) = $x^2$. This is surjective but not injective.

This is not surjective. $-1$ is not mapped to by any element in the domain.

Should I fix $S$ to be a certain set, like the integers, or natural numbers, and work from there?

Yes, from what I can understand you're free to choose $S$, and then come up with a function that solves the problem. Your goal is to try to map multiple elements to the same element, here is an example for $\mathbb{N}_0$:

0 1 2 3 4 5 6 7 8 9 10 11 ...
0 0 1 1 2 2 3 3 4 4 5  5  ...

It is generally easier for this kind of problem to first come up with a solution in general in your head, and then derive a formula for that solution.

Answer 3

\begin{align} f:\mathbb Z &\to \mathbb Z \\ n &\mapsto \left \lfloor \dfrac n2 \right \rfloor \end{align}

For every integer, $n$, $f(2n) = n$ and $f(2n+1)=n$