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

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.

• Try $f)x)=x^3-x.$ – bof Nov 27 '17 at 22:05
• I see. So then in a formal proof what do you let S be? $\mathbb{R}$? – mathmajor Nov 27 '17 at 22:07
• Yeah, I was thinking of $S=\mathbb R.$ If you want $S=\mathbb C$ then you can just use $f(z)=z^2.$ – bof Nov 27 '17 at 22:17
• I'd suggest, just start with natural numbers. Then make a function where, for every natural number $n$, there are 2 different values $x$, $y$, such that $f(x) = n$ and $f(y) = n$. – DanielV Nov 28 '17 at 14:07

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.

• Right. So 0-->0, 1-->0, 2-->1, 3-->1, 4-->2, 5-->2, etc... This would be an infinite set S mapped to itself, being surjective and not injective. Now to figure out what the rule is. – mathmajor Nov 27 '17 at 21:59
• Would this be a piecewise function? – mathmajor Nov 27 '17 at 22:10
• Try dividing by $2$, it might help? Well, technically it can be viewed as a piecewise function, if you separate the rules for odd numbers and even number. but there are function to combine it into a single rule. – Siong Thye Goh Nov 27 '17 at 22:14

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.

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

• So let S = $\mathbb{Z}$, and let f: $\mathbb{Z}$ --> $\mathbb{Z}$ be defined by the rule f(2n) = n, and f(2n+1) = n...? I guess I'm confused with what the n --> (n/2) is referring to. – mathmajor Nov 28 '17 at 2:56
• @wannabemathmajor - it's the floor function, the integer part of x. – steven gregory Nov 28 '17 at 5:12

Choose $$~A = \mathbb{N}~$$ and $$~f(n) = max\{1,n − 1\}~$$ for all $$~n ∈ \mathbb{N}~$$.

Then $$f(n +1) = n$$ for all $$n ∈ \mathbb{N}$$, so $$f$$ is surjective.

But $$f(1) = 1 = f(2)$$ and $$1 ≠ 2$$.

Therefore $$f$$ is not injective.

This website provide really good answer https://mathgraphy.com/functions/