Calculus

Set Theory

Set Theory Logo

Injection, Surjection, Bijection

Injection

Let \(f : A \to B\) be a function from the domain \(A\) to the codomain \(B.\)

The function \(f\) is called injective (or one-to-one) if it maps distinct elements of \(A\) to distinct elements of \(B.\) In other words, for every element \(y\) in the codomain \(B\) there exists at most one preimage in the domain \(A:\)

\[{\forall {x_1},{x_2} \in A:\;{x_1} \ne {x_2}\;} \Rightarrow {f\left( {{x_1}} \right) \ne f\left( {{x_2}} \right).}\]

Injective and not injective functions.
Figure 1.

A horizontal line intersects the graph of an injective function at most once (that is, once or not at all). In this case, we say that the function passes the horizontal line test.

If a horizontal line intersects the graph of a function in more than one point, the function fails the horizontal line test and is not injective.

Surjection

A function \(f\) from \(A\) to \(B\) is called surjective (or onto) if for every \(y\) in the codomain \(B\) there exists at least one \(x\) in the domain \(A:\)

\[{\forall y \in B:\;\exists x \in A\; \text{such that}\;}\kern0pt{y = f\left( x \right).}\]

Surjective and not surjective functions.
Figure 2.

Any horizontal line should intersect the graph of a surjective function at least once (once or more).

If there is an element of the range of a function such that the horizontal line through this element does not intersect the graph of the function, we say the function fails the horizontal line test and is not surjective.

The range and the codomain for a surjective function are identical.

Bijection

A function \(f\) from set \(A\) to set \(B\) is called bijective (one-to-one and onto) if for every \(y\) in the codomain \(B\) there is exactly one element \(x\) in the domain \(A:\)

\[{\forall y \in B:\;\exists! x \in A\; \text{such that}\;}\kern0pt{y = f\left( x \right).}\]

The notation \(\exists! x\) means that there exists exactly one element \(x.\)

Bijective function
Figure 3.

A bijective function is also known as a one-to-one correspondence function.

Any horizontal line passing through any element of the range should intersect the graph of a bijective function exactly once.

An example of a bijective function is the identity function. The identity function \({I_A}\) on the set \(A\) is defined by

\[{I_A} : A \to A,\; {I_A}\left( x \right) = x.\]

If \(f : A \to B\) is a bijective function, then \(\left| A \right| = \left| B \right|,\) that is, the sets \(A\) and \(B\) have the same cardinality.


Solved Problems

Click or tap a problem to see the solution.

Example 1

Let \(A = \left\{ {a,b,c,d} \right\}\) and \(B = \left\{ {0,1,2,3} \right\}.\) Determine which of the following relations are functions with domain \(A\) and codomain \(B.\) If so, are they injective or surjective?
  1. \(\left\{ {\left( {c,0} \right),\left( {d,1} \right),\left( {b,0} \right),\left( {a,2} \right)} \right\}\)
  2. \(\left\{ {\left( {a,1} \right),\left( {b,3} \right),\left( {c,0} \right),\left( {d,2} \right)} \right\}\)
  3. \(\left\{ {\left( {d,3} \right),\left( {d,2} \right),\left( {a,3} \right),\left( {b,1} \right)} \right\}\)
  4. \(\left\{ {\left( {c,2} \right),\left( {d,3} \right),\left( {a,1} \right)} \right\}\)

Example 2

Determine whether the following functions are injective, surjective, or bijective?
  1. \({f_1}:\mathbb{R} \to \left[ {0,\infty } \right),{f_1}\left( x \right) = \left| x \right|\)
  2. \({f_2}:\mathbb{N} \to \mathbb{N},{f_2}\left( x \right) = 2x^2 -1\)
  3. \({f_3}:\mathbb{R} \to \mathbb{R^+},{f_3}\left( x \right) = e^x\)
  4. \({f_4}:\mathbb{R} \to \mathbb{R},{f_4}\left( x \right) = 1 – x^2\)

Example 3

Let \(f:\mathbb{R} \to \left[ { – 1,1} \right],\) \(f\left( x \right) = \sin x.\) Determine whether the function \(f\) is injective or surjective.

Example 4

Let \(g:\mathbb{N} \to \mathbb{Q},\) \(g\left( x \right) = \large{\frac{x}{{x + 1}}}\normalsize.\) Determine whether the function \(g\) is injective or surjective.

Example 5

Consider \(f:\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z},\) \(f\left( {x,y} \right) = x + y.\) Verify whether this function is injective or surjective.

Example 6

Consider \(g:\mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R},\) \(g\left( {x,y} \right) = \left( {x^3 + 2y,y – 1} \right).\) Verify whether this function is bijective.

Example 1.

Let \(A = \left\{ {a,b,c,d} \right\}\) and \(B = \left\{ {0,1,2,3} \right\}.\) Determine which of the following relations are functions with domain \(A\) and codomain \(B.\) If so, are they injective or surjective?
  1. \(\left\{ {\left( {c,0} \right),\left( {d,1} \right),\left( {b,0} \right),\left( {a,2} \right)} \right\}\)
  2. \(\left\{ {\left( {a,1} \right),\left( {b,3} \right),\left( {c,0} \right),\left( {d,2} \right)} \right\}\)
  3. \(\left\{ {\left( {d,3} \right),\left( {d,2} \right),\left( {a,3} \right),\left( {b,1} \right)} \right\}\)
  4. \(\left\{ {\left( {c,2} \right),\left( {d,3} \right),\left( {a,1} \right)} \right\}\)

Solution.

  1. This relation is a function. It is not injective, since \(f\left( c \right) = f\left( b \right) = 0,\) but \(b \ne c.\) It is also not surjective, because there is no preimage for the element \(3 \in B.\)
  2. The relation is a function. It is injective (any pair of distinct elements of the domain is mapped to distinct images in the codomain). The function is also surjective, because the codomain coincides with the range. Thus, the function is bijective.
  3. Not a function, since the element \(d \in A\) has two images, \(3\) and \(2,\) and the relation is not defined for the element \(c \in A.\)
  4. Not a function, because the relation is not defined for the element \(b \in A.\)

Example 2.

Determine whether the following functions are injective, surjective, or bijective?
  1. \({f_1}:\mathbb{R} \to \left[ {0,\infty } \right),{f_1}\left( x \right) = \left| x \right|\)
  2. \({f_2}:\mathbb{N} \to \mathbb{N},{f_2}\left( x \right) = 2x^2 -1\)
  3. \({f_3}:\mathbb{R} \to \mathbb{R^+},{f_3}\left( x \right) = e^x\)
  4. \({f_4}:\mathbb{R} \to \mathbb{R},{f_4}\left( x \right) = 1 – x^2\)

Solution.

  1. The function \({f_1}\) is not injective. For any \(x \ne 0,\) we have \({f_1}\left( -x \right) = {f_1}\left( x \right) = \left| x \right|,\) although \(-x \ne x.\) The function \({f_1}\) is surjective, because for any \(y \in \left[ {0,\infty } \right)\) there is a preimage \(x = \pm y\) in the domain \(\mathbb{R}\) such that \[{f_1}\left( x \right) = \left| x \right| = \left| { \pm y} \right| = y.\]
  2. The function \({f_2}\) is injective. Using the contrapositive approach, we suppose that \({x_1} \ne {x_2}\) but \(f\left( {{x_1}} \right) = f\left( {{x_2}} \right).\) This means \[{2x_1^2 – 1 = 2x_2^2 – 1,}\;\; \Rightarrow {2x_1^2 = 2x_2^2,}\;\; \Rightarrow {x_1^2 = x_2^2,}\;\; \Rightarrow {\left| {{x_1}} \right| = \left| {{x_2}} \right|}.\] Given that the domain of the function is \(\mathbb{N},\) we obtain: \[\left| {{x_1}} \right| = \left| {{x_2}} \right|, \Rightarrow {x_1} = {x_2}.\] This is a contradiction, so \({f_2}\) is injective.

    The function \({f_2}\) is not surjective. To show this, we take a number \(y\) from the codomain and solve the equation for \(x:\) This yields: \[{y = f\left( x \right) = 2{x^2} – 1,}\;\; \Rightarrow {2{x^2} = y + 1,}\;\; \Rightarrow {{x^2} = \frac{{y + 1}}{2},}\;\; \Rightarrow {x = \sqrt {\frac{{y + 1}}{2}} .}\] Let, for example, \(y = 5.\) Then \[x = \sqrt {\frac{{5 + 1}}{2}} = \sqrt 3.\] We see that \(\sqrt 3 \not\in \mathbb{N}.\) Hence, the range of \({f_2}\) is not equal to the codomain. This proves that the function \({f_2}\) is not surjective.
  3. The exponential function \({f_3}\left( x \right) = {e^x}\) from \(\mathbb{R}\) to \(\mathbb{R^+}\) is injective. Prove this by contradiction. Let \({x_1} \ne {x_2}\) and suppose that \({f_3}\left( {{x_1}} \right) = {f_3}\left( {{x_2}} \right)\). It follows from here that \[{{e^{{x_1}}} = {e^{{x_2}}},}\;\; \Rightarrow {\ln {e^{{x_1}}} = \ln {e^{{x_2}}},}\;\; \Rightarrow {{x_1}\ln e = {x_2}\ln e,}\;\; \Rightarrow {{x_1} = {x_2}.}\] This contradiction proves that \({f_3}\) is injective.

    The function \({f_3}\left( x \right) = {e^x}\) from set \(\mathbb{R}\) to set \(\mathbb{R^+}\) is surjective. Take any positive real number \(y.\) The preimage of this number is equal to \(x = \ln y,\) since \[{{f_3}\left( x \right) = {f_3}\left( {\ln y} \right) }={ {e^{\ln y}} }={ y.}\] Thus, the function \({f_3}\) is surjective, and hence, it is bijective.
  4. If we take \({x_1} = -1\) and \({x_2} = 1,\) we see that \({f_4}\left( { – 1} \right) = {f_4}\left( 1 \right) = 0.\) So for \({x_1} \ne {x_2}\) we have \({f_4}\left( {{x_1}} \right) = {f_4}\left( {{x_2}} \right).\) Hence, the function \({f_4}\) is not injective.

    The function \({f_4}\) is also not surjective, because its codomain is \(\mathbb{R},\) but the range is \(\left( { – \infty ,1} \right],\) that is, the range of \({f_4}\) does not coincide with the codomain. For example, if we take \(y = 2,\) then there is no \(x \in \mathbb{R}\) such that \({f_4}\left( x \right) = y.\)

Example 3.

Let \(f:\mathbb{R} \to \left[ { – 1,1} \right],\) \(f\left( x \right) = \sin x.\) Determine whether the function \(f\) is injective or surjective.

Solution.

Consider \({x_1} = \large{\frac{\pi }{4}}\normalsize\) and \({x_2} = \large{\frac{3\pi }{4}}\normalsize.\) For these two values, we have

\[{f\left( {{x_1}} \right) = f\left( {\frac{\pi }{4}} \right) = \frac{{\sqrt 2 }}{2},\;\;}\kern0pt{f\left( {{x_2}} \right) = f\left( {\frac{{3\pi }}{4}} \right) = \frac{{\sqrt 2 }}{2},}\;\; \Rightarrow {f\left( {{x_1}} \right) = f\left( {{x_2}} \right).}\]

Hence, the sine function is not injective.

Notice that the codomain \(\left[ { – 1,1} \right]\) coincides with the range of the function. One can show that any point in the codomain has a preimage. Suppose \(y \in \left[ { – 1,1} \right].\) This image point matches to the preimage \(x = \arcsin y,\) because

\[f\left( x \right) = \sin x = \sin \left( {\arcsin y} \right) = y.\]

So, the given function is surjective.

Note that if the sine function \(f\left( x \right) = \sin x\) were defined from set \(\mathbb{R}\) to set \(\mathbb{R},\) then it would not be surjective.

Example 4.

Let \(g:\mathbb{N} \to \mathbb{Q},\) \(g\left( x \right) = \large{\frac{x}{{x + 1}}}\normalsize.\) Determine whether the function \(g\) is injective or surjective.

Solution.

Using the contrapositive method, suppose that \({x_1} \ne {x_2}\) but \(g\left( {x_1} \right) = g\left( {x_2} \right).\) Then we have

\[{g\left( {{x_1}} \right) = g\left( {{x_2}} \right),}\;\; \Rightarrow {\frac{{{x_1}}}{{{x_1} + 1}} = \frac{{{x_2}}}{{{x_2} + 1}},}\;\; \Rightarrow {\frac{{{x_1} + 1 – 1}}{{{x_1} + 1}} = \frac{{{x_2} + 1 – 1}}{{{x_2} + 1}},}\;\; \Rightarrow {1 – \frac{1}{{{x_1} + 1}} = 1 – \frac{1}{{{x_2} + 1}},}\;\; \Rightarrow {\frac{1}{{{x_1} + 1}} = \frac{1}{{{x_2} + 1}},}\;\; \Rightarrow {{x_1} + 1 = {x_2} + 1,}\;\; \Rightarrow {{x_1} = {x_2}.}\]

This is a contradiction. So, the function \(g\) is injective.

Show that the function \(g\) is not surjective. Take an arbitrary number \(y \in \mathbb{Q}.\) Solve the equation \(y = g\left( x \right)\) for \(x:\)

\[{y = g\left( x \right) = \frac{x}{{x + 1}},}\;\; \Rightarrow {y = \frac{{x + 1 – 1}}{{x + 1}},}\;\; \Rightarrow {y = 1 – \frac{1}{{x + 1}},}\;\; \Rightarrow {\frac{1}{{x + 1}} = 1 – y,}\;\; \Rightarrow {x + 1 = \frac{1}{{1 – y}},}\;\; \Rightarrow {x = \frac{1}{{1 – y}} – 1 = \frac{y}{{1 – y}}.}\]

We can check that the values of \(x\) are not always natural numbers. Indeed, if we substitute \(y = \large{{\frac{2}{7}}}\normalsize,\) we get

\[{x = \frac{{\frac{2}{7}}}{{1 – \frac{2}{7}}} }={ \frac{{\frac{2}{7}}}{{\frac{5}{7}}} }={ \frac{5}{7}.}\]

It is obvious that \(x = \large{\frac{5}{7}}\normalsize \not\in \mathbb{N}.\) Thus, the range of the function \(g\) is not equal to the codomain \(\mathbb{Q},\) that is, the function \(g\) is not surjective.

Example 5.

Consider \(f:\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z},\) \(f\left( {x,y} \right) = x + y.\) Verify whether this function is injective or surjective.

Solution.

This function is not injective, because for two distinct elements \(\left( {1,2} \right)\) and \(\left( {2,1} \right)\) in the domain, we have \(f\left( {1,2} \right) = f\left( {2,1} \right) = 3.\)

Prove that the function \(f\) is surjective. Let \(z\) be an arbitrary integer in the codomain of \(f.\) We need to show that there exists at least one pair of numbers \(\left( {x,y} \right)\) in the domain \(\mathbb{Z} \times \mathbb{Z}\) such that \(f\left( {x,y} \right) = x+ y = z.\) We can simply let \(y = 0.\) Then \(x = z.\) Hence, the pair of numbers \(\left( {z,0} \right)\) always satisfies the equation:

\[f\left( {z,0} \right) = z + 0 = z.\]

Therefore, \(f\) is surjective. (The proof is very simple, isn’t it?)

Example 6.

Consider \(g:\mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R},\) \(g\left( {x,y} \right) = \left( {x^3 + 2y,y – 1} \right).\) Verify whether this function is bijective.

Solution.

Check for injectivity by contradiction. Let \(\left( {{x_1},{y_1}} \right) \ne \left( {{x_2},{y_2}} \right)\) but \(g\left( {{x_1},{y_1}} \right) = g\left( {{x_2},{y_2}} \right).\) So we have

\[{\left( {x_1^3 + 2{y_1},{y_1} – 1} \right) = \left( {x_2^3 + 2{y_2},{y_2} – 1} \right),}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {x_1^3 + 2{y_1} = x_2^3 + 2{y_2}}\\ {{y_1} – 1 = {y_2} – 1} \end{array}} \right..}\]

It follows from the second equation that \({y_1} = {y_2}.\) Then

\[{x_1^3 = x_2^3,}\;\; \Rightarrow {{x_1} = {x_2},}\]

that is, \(\left( {{x_1},{y_1}} \right) = \left( {{x_2},{y_2}} \right).\) This is a contradiction. Therefore, the function \(g\) is injective.

Now consider an arbitrary element \(\left( {a,b} \right) \in \mathbb{R}^2.\) Show that there exists at least one element \(\left( {x,y} \right)\) in the domain of \(g\) such that \(g\left( {x,y} \right) = \left( {a,b} \right).\) The last equation means

\[{g\left( {x,y} \right) = \left( {a,b} \right),}\;\; \Rightarrow {\left( {{x^3} + 2y,y – 1} \right) = \left( {a,b} \right),}\;\; \Rightarrow {\left\{ {\begin{array}{*{20}{l}} {{x^3} + 2y = a}\\ {y – 1 = b} \end{array}} \right..}\]

Substituting \(y = b+1\) from the second equation into the first one gives

\[{{x^3} + 2\left( {b + 1} \right) = a,}\;\; \Rightarrow {{x^3} = a – 2b – 2,}\;\; \Rightarrow {x = \sqrt[3]{{a – 2b – 2}}.}\]

Thus, if we take the preimage \(\left( {x,y} \right) = \left( {\sqrt[3]{{a – 2b – 2}},b + 1} \right),\) we obtain \(g\left( {x,y} \right) = \left( {a,b} \right)\) for any element \(\left( {a,b} \right)\) in the codomain of \(g.\)

So, the function \(g\) is surjective, and hence, it is bijective.