Injection:
A function \(f:A\to B\) is an injection when different inputs are always mapped to different outputs, that is, \(x\neq y\Rightarrow f(x)\neq f(y).\)
In practice we normally use the contrapositive \((f(x)=f(y)\Rightarrow x=y)\) as it is generally easier to prove.
To show a function is not injective, we must show a counterexample. We would need two different inputs \(x_1\neq x_2\) so that their outputs are the same \(f(x_1)=f(x_2).\)
Surjection:
A function \(f:A\to B\) is a surjection if every element of the codomain \(B\) is mapped onto. In other words, for any \(b\in B\) we can find at least one \(a\in A\) so that \(f(a)=b\). One way to do this is to:
- Pick an arbitrary element of the codomain (let \(b\in B\) without specifying anything else about it).
- Look for \(a\in A\) so that \(f(a)=b\) (do this by plugging in \(x\) into \(f\), set \(f(x)=b\) and solve for \(x\) in terms of \(b\).
- Confirm that plugging in this \(x\) into \(f\) actually does output \(b\), as well as making sure that \(x\in A\).
Another way is to prove that the image of \(f\) is equal to the codomain, i.e., \(im(f)=B\).
To show a function is not a surjection, we again must find a counterexample. That would be finding \(b\in B\) so that it isn’t possible that \(f(a)=b\) for any \(a\in A\).
Bijection:
A bijection is a function \(f:A\to B\) which is both injective and surjective. Bijections can be reversed, if \(f\) is a bijection then there is a function \(f^{-1}:B\to A\) (called the inverse function of \(f\)) which undoes what \(f\) does.
Formally, \(f(a)=b\) if and only if \(f^{-1}(b)=a\)
This is demonstrated in the fact that \(f(f^{-1}(x))=x\) and \(f(f^{-1}(x))=x\). It is useful to note that \(f^{-1}\) is also a bijection.
Example
Determine whether the following functions are injective, surjective, bijective or neither.
\(\text{(a)}\quad f:\mathbb{R}\to\mathbb{R},\quad f(x)=\begin{cases}-\frac{1}{x};&x<0\\-x^2+1;&x\geq0\end{cases}\)
\(\mathrm{(b)}\quad f:\mathbb{R}^2\to\mathbb{R},\quad f(a,b)=a\cdot b\)
Solution Part (a).
Since we have a piecewise function, we must handle it slightly differently.
For surjectivity, we must show the combined images of each part are equal to the codomain \(\mathbb{R}\). For injectivity, we must show that each function is injective as well as show that \(-\frac1{x_1}\neq-x_2^2+1\), that is, \(f(x_1)\neq f(x_2).\)
We will test surjection first:
First take \(x<0\), so \(f(x)=-\frac1x.\) We want to build up \(-\frac1x.\) within the \(x>0\) inequality:
\(x<0\Longrightarrow\frac1x<0\Longrightarrow-\frac1x>0\Rightarrow f(x)>0\)
Therefore, the image of \(f\) when \(x<0\) is \((0,\infty).\)
Now for the second part, we begin with \(x\geq0\) and build up \(-x^2+1\) within the inequality:
\(x\geq0\Rightarrow x^2\geq0\Rightarrow-x^2\leq0\Rightarrow-x^2+1\leq1\)
Thus, the image of \(f\) when \(x\geq0\) is \((-\infty,1].\)
Putting these two together, we see that the image of \(f\) is:
\((0,\infty)\cup(-\infty,1]=(-\infty,\infty)=\mathbb{R}\)
and \(f\) is surjective.
We now test injection:
From the work on surjectivity above we see that the images of the two functions that make up \(f\) overlap. This means we should be able to find \(x_1<0\) and \(x_2\geq0\) so that \(f(x_1)=f(x_2),\), that is, \(-\frac1{x_1}=-{x_2}^2+1.\) One way to do this is to try guessing using “easy” numbers. For instance, when \(x_2=0\) then \(-\frac1{x_1}=-{x_2}^2+1\) implies \(-\frac1{x_1}=1\mathrm{~and~}x_1=-1.\) Done! As \(f(0)=1\) and \(f(-1)=1\), we see that \(f(0)=f(-1)\), however, \(0\neq-1\) so \(f\) is not injective.
Alternatively, we have to try to find these \(x_1\) and \(x_2\) to prove the function is not injective. It seems easier to solve for \(x_1\):
\(\begin{aligned}
-\frac1{x_1}& =-x_2^2+1 \\
\text{-1}& =(-x_2^2+1)x_1 \\
\frac{-1}{-x_2^2+1}& =x_1
\end{aligned}\)
Since we said \(x_1<0,\) we can apply this to our expression: \(\frac{-1}{-{x_2}^2+1}<0.\) Since the numerator is negative, the denominator must be a positive for this to be true. That is, \(-{x_2}^2+1>0.\) We can then solve for \(x_2\):
\(-x_2^2+1>0\Longrightarrow-x_2^2>-1\Longrightarrow x_2^2<1\Rightarrow\left|x_2\right|<1\Rightarrow-1<x_2<1\)
Since \(x_{2}\geq0\) this is restricted to \(0\leq x_2<1.\) We pick a value from that range, the easiest being \(x_2=0\) and find the respective \(x_1\): \(\frac{-1}{0^2+1}=x_1\Longrightarrow x_1=-1\)
From here we check their values: \(f(0)=1\) and \(f(-1)=1.\) So \(f(0)=f(-1),\) however, \(0\neq-1\) so \(f\) is not injective.
Since \(f\) is not injective, it is not bijective. Thus \(f\) is only surjective.
Solution Part (b).
We test injection:
One way is to ask the following question: can we find two different pairs of numbers, which, when multiplied, give the same number? Start, for instance, with \(f(2,4)=2\cdot4=8\). Now we need a different pair whose product is 8; there are many such pairs, for instance, \(f(1,8)=1\cdot8=8\). Thus, \(f\) is not injective.
Alternatively: we would like to prove that for \((a,b),(c,d)\in\mathbb{R}\) we have:
\(f(a,b)=f(c,d)\Rightarrow(a,b)=(c,d)\)
i.e., that \(a=c\) and \(b=d\). So, we will try to prove it. We assume \(f(a,b)=f(c,d),\), this would mean, \(ab=cd\). This doesn’t give us much, as we cannot conclude that \(a=c\) and \(b=d\). Therefore, we look for a counterexample:
\(f(2,6)=2\cdot6=12\mathrm{~and~}f(3,4)=3\cdot4=12.\)
Meanwhile, \((2,6)\neq(3,4).\) Therefore, \(f\) is not injective.
Testing surjection:
We pick an arbitrary element of the codomain, let \(r\in\mathbb{R}.\) We must find \((a,b)\in\mathbb{R}^2\) such that \(f(a,b)=r,\). It will be hard to find two variables in one equation so we “fix” one of them to make our work easier; let \(b=1\) and we try to find \(a\) to make the equation work:
\(\begin{array}{r}ab=r\\a(1)=r\\a=r\end{array}\)
This tells us \((1,r)\) satisfies our requirement, we confirm it: \(f(1,r)=1\cdot r=r .\) Since we were able to find \((a,b)\in\mathbb{R}^2\) so that \(f(a,b)=r\) for arbitrary \(r\in\mathbb{R}\text{,}\) \(f\) is a surjective function.
Because it is not injective, \(f\) is not bijective.