On proving the surjectivity of non-injective functions.

Question

As given in my lectures and several other areas, the definition of a surjective function is "a function f from a set X to a set Y is surjective (or onto), or a surjection, if every element y in Y has a corresponding element x in X such that f(x) = y".

The issue I am having is proving that a non-injective function is surjective. Both in my lectures and in numerous online sources, the method used has always been to find an inverse function.

More precisely, $f(x)=y \iff f^{-1} (f(x)) = f^{-1} (y) \iff x=f^{-1} (y) $ so clearly finding an inverse function proves surjectivivity. However, I cannot see how this holds if we have a function which is not invertible (or indeed, not injective), since in this case we cannot use $f^{-1}$.

What have I missed? I feel that if my blindness is anywhere, it is in my use of the definition.

Answer 1

To show that a function is surjective, you show that every element in the co-domain is mapped to by at least one element of the domain. Then $f^{-1}(y)$ is referred to as the pre-image of $y$. This pre-image could potentially be nothing, one element, or any number of elements. For example, if $f(x)=1, 0\leq x \leq 1 $, then $f^{-1}(1)$ is the interval $[0, 1]$.

You have the correct approach for the problem. An "inverse" $f^{-1}$ of $f$ will find you at least one element in the domain for each in the codomain, it just won't be a function.

Answer 2

Functions are surjective if and only if they have a right-inverse, which is not necessarily an inverse.

If $s:X\to Y$ is a function then it is surjective if and only if some function $i:Y\to X$ exists such that $s\circ i=\text{id}_Y$.

Also the function $i$ is then injective and it is on purpose that I used the symbols $s,i$ instead of the usual $f,g$.

Example $s:\mathbb R\to\mathbb Z$ prescribed by $x\mapsto\lfloor x\rfloor$ is evidently surjective. There are lots of (injective) functions $i:\mathbb Z\to\mathbb R$ with $s\circ i=1_{\mathbb Z}$. Like $n\mapsto n$ of $n\mapsto n+\frac12$.

I advice you to put the expression: $$s\circ i=\text{id}$$ in your mathematical luggage as a mnemonic.

---

edit in order to visualize

arbitrary function

$\begin{array}{ccc} X & f & Y\\ \vdots & \searrow & \vdots\\ \vdots & & \cdot\\ \vdots & \nearrow & \vdots\\ \vdots & \searrow & \vdots\\ \vdots & & \cdot\\ \vdots & \nearrow & \vdots\\ \vdots & \searrow & \vdots\\ \vdots & & \cdot\\ \vdots & \nearrow & \vdots\end{array}$

surjective function together with right-inverse $\dashleftarrow$

$\begin{array}{ccc} X & f & Y\\ \vdots & \searrow\\ \vdots & \dashleftarrow & \cdot\\ \vdots & \nearrow\\ \vdots & \searrow\\ \vdots & \dashleftarrow & \cdot\\ \vdots & \nearrow\\ \vdots & \searrow\\ \vdots & \dashleftarrow & \cdot\\ \vdots & \nearrow\end{array}$

Answer 3

The key here is to realise the difference between surjective and injective.

Injective means that each element of $Y$ is hit by at most one $x$ via $f$ (So for injective it doesn't matter if some elements of $Y$ don't get hit).

Surjective means that each element of $Y$ is hit at least once by an $x$ via $f$ (So for surjective it doesn't matter is some elements in $Y$ are hit more than once).

An example of a non-injective but surjective function is $f:\mathbb{Z} \rightarrow \mathbb{N}$ defined by $f(x) = |x|$. This is not injective since all elements in $\mathbb{N}$ apart from $0$ are hit twice, once by $-x$ and once by $x$. But it is surjective since for every element of $\mathbb{N}$ we can find an $x \in \mathbb{Z}$ which hits it, since for any $n \in \mathbb{N}$ $n$ is also in $\mathbb{Z}$ and $f(n) = n$ since $n$ is positive. Hence we have just shown there is at least one way to hit everything in $\mathbb{N}$.

So one way to find these elements that map to everything in the codomain is to find an inverse or inverse image as discussed in other answers. But if you can just show as above that choosing any element of the codomain you can hit it with an element from the domain, then you're done.

Answer 4

There are several ready-made examples.

---

The function \begin{matrix} f &: & [-1,1] & \to & [0,1] \\ &: & x & \mapsto & x^2 \\ \end{matrix} is surjective but not injective.

The function \begin{array}{rlccc} \sqrt{} & : & [0,1] & \to & [0,1] \\ & : & x & \mapsto & \sqrt x \\ \end{array}

is a right inverse of $f$:

$$\quad f(\sqrt x) = x \quad \text{for all}\; x \in [0,1].$$

---

The function \begin{matrix} \sin &: & \mathbb R & \to & [-1,1] \\ &: & x & \mapsto & \sin x \\ \end{matrix} is surjective and massively not injective.

Yet the function \begin{array}{rlccc} \arcsin{} & : & [-1,1] & \to & \left[-\dfrac{\pi}{2}, \dfrac{\pi}{2} \right] \\ & : & x & \mapsto & \arcsin x \\ \end{array}

is a right inverse of $\;\sin{}$:

$$\quad \sin(\arcsin x) = x \quad \text{for all}\; x \in [-1,1].$$