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.

  • $\begingroup$ Try $f)x)=x^3-x.$ $\endgroup$ – bof Nov 27 '17 at 22:05
  • $\begingroup$ I see. So then in a formal proof what do you let S be? $\mathbb{R}$? $\endgroup$ – mathmajor Nov 27 '17 at 22:07
  • $\begingroup$ Yeah, I was thinking of $S=\mathbb R.$ If you want $S=\mathbb C$ then you can just use $f(z)=z^2.$ $\endgroup$ – bof Nov 27 '17 at 22:17
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – mathmajor Nov 27 '17 at 21:59
  • $\begingroup$ Would this be a piecewise function? $\endgroup$ – mathmajor Nov 27 '17 at 22:10
  • $\begingroup$ 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. $\endgroup$ – 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$

  • $\begingroup$ 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. $\endgroup$ – mathmajor Nov 28 '17 at 2:56
  • $\begingroup$ @wannabemathmajor - it's the floor function, the integer part of x. $\endgroup$ – 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/


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.