Calculus

Set Theory

Set Theory Logo

Injection, Surjection, Bijection

Solved Problems

Click or tap a problem to see the solution.

Example 1

Let A = {a, b, c, d} and B = {0, 1, 2, 3}. 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) = \frac{x}{{x + 1}}.\) 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} = \frac{\pi }{4}\) and \({x_2} = \frac{3\pi }{4}.\) For these two values, we have

\[f\left( {{x_1}} \right) = f\left( {\frac{\pi }{4}} \right) = \frac{{\sqrt 2 }}{2},\;\;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) = \frac{x}{{x + 1}}.\) 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 = {\frac{2}{7}},\) 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 = \frac{5}{7} \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.

Page 1 Page 2