Skip to main content
Mathematics LibreTexts

6.3: Injections, Surjections, and Bijections

  • Page ID
    7069
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    Functions are frequently used in mathematics to define and describe certain relationships between sets and other mathematical objects. In addition, functions can be used to impose certain mathematical structures on sets. In this section, we will study special types of functions that are used to describe these relationships that are called injections and surjections. Before defining these types of functions, we will revisit what the definition of a function tells us and explore certain functions with finite domains.

    Preview Activity \(\PageIndex{1}\): Functions with Finite Domains

    Let \(A\) and \(B\) be sets. Given a function \(f : A \to B\), we know the following:

    • For every \(x \in A\), \(f(x) \in B\). That is, every element of \(A\) is an input for the function \(f\). This could also be stated as follows: For each \(x \in A\), there exists a \(y \in B\) such that \(y = f(x)\).
    • For a given \(x \in A\), there is exactly one \(y \in B\) such that \(y = f(x)\).

    The definition of a function does not require that different inputs produce different outputs. That is, it is possible to have \(x_1, x_2 \in A\) with \(x1 \ne x_2\) and \(f(x_1) = f(x_2)\). The arrow diagram for the function \(f\) in Figure 6.5 illustrates such a function.

    Also, the definition of a function does not require that the range of the function must equal the codomain. The range is always a subset of the codomain, but these two sets are not required to be equal. That is, if \(g: A \to B\), then it is possible to have a \(y \in B\) such that \(g(x) \ne y\) for all \(x \in A\). The arrow diagram for the function g in Figure 6.5 illustrates such a function.

    屏幕快照 2019-03-31 下午3.37.03.png

    Now let \(A = \{1, 2, 3\}\), \(B = \{a, b, c, d\}\), and \(C = \{s, t\}\). Define

    屏幕快照 2019-03-31 下午3.38.25.png

    1. Which of these functions satisfy the following property for a function \(F\)?
      For all \(x, y \in \text{dom}(F)\), if \(x \ne y\), then \(F(x) \ne F(y)\).
    2. Which of these functions satisfy the following property for a function \(F\)?
      For all \(x, y \in \text{dom}(F)\), if \(F(x) = F(y)\), then \(x = y\).
    3. Determine the range of each of these functions.
    4. Which of these functions have their range equal to their codomain?
    5. Which of the these functions satisfy the following property for a function \(F\)?
      For all \(y\) in the codomain of \(F\), there exists an \(x \in \text{dom}(F\)\) such that \(F(x) = y\).
    Preview Activity \(\PageIndex{1}\): Statements Involving Functions

    Let \(A\) and \(B\) be nonempty sets and let \(f: A \to B\). In Preview Activity \(\PageIndex{1}\), we determined whether or not certain functions satisfied some specified properties. These properties were written in the form of statements, and we will now examine these statements in more detail.

    1. Consider the following statement:
      For all \(x, y \in A\), if \(x \ne y\), then \(f(x) \ne f(y)\).

      (a) Write the contrapositive of this conditional statement.
      (b) Write the negation of this conditional statement.
    2. Now consider the statement:
      For all \(y \in B\), there exists an \(x \in A\) such that \(f(x) = y\).
      Write the negation of this statement.
    3. Let \(g: \mathbb{R} \to \mathbb{R}\) be defined by \(g(x) = 5x + 3\), for all \(x \in \mathbb{R}\). Complete the following proofs of the following propositions about the function \(g\).

      Proposition 1. For all \(a, b \in \mathbb{R}\), if \(g(a) = g(b)\), then \(a = b\).
      Proof. We let \(a, b \in \mathbb{R}\), and we assume that \(g(a) = g(b)\) and will prove that \(a = b\). Since \(g(a) = g(b)\), we know that
      \[5a + 3 = 5b + 3.\]
      (Now prove that in this situation, \(a = b\).)

      Proposition 2. For all \(b \in \mathbb{R}\), there exists an \(a \in \mathbb{R}\) such that \(g(a) = b\).
      Proof. We let \(b \in \mathbb{R}\). We will prove that there exists an \(a \in \mathbb{R}\) such that \(g(a) = b\) by constructing such an \(a\) in \(\mathbb{R}\). In order for this to happen, we need \(g(a) = 5a + 3 = b\).
      (Now solve the equation for \(a\) and then show that for this real number \(a\), \(g(a) = b\).)

    Injections

    In previous sections and in Preview Activity \(\PageIndex{1}\), we have seen examples of functions for which there exist different inputs that produce the same output. Using more formal notation, this means that there are functions \(f: A \to B\) for which there exist \(x_1, x_2 \in A\) with \(x_1 \ne x_2\) and \(f(x_1) = f(x_2)\). The work in the preview activities was intended to motivate the following definition.

    Definition

    Let \(f: A \to B\) be a function from the set \(A\) to the set \(B\). The function \(f\) is called an injection provided that

    for all \(x_1, x_2 \in A\), if \(x_1 \ne x_2\), then \(f(x_1) \ne f(x_2)\).

    When \(f\) is an injection, we also say that \(f\) is a one-to-one function, or that \(f\) is an injective function.

    Notice that the condition that specifies that a function \(f\) is an injection is given in the form of a conditional statement. As we shall see, in proofs, it is usually easier to use the contrapositive of this conditional statement. Although we did not define the term then, we have already written the contrapositive for the conditional statement in the definition of an injection in Part (1) of Preview Activity \(\PageIndex{2}\). In that preview activity, we also wrote the negation of the definition of an injection. Following is a summary of this work giving the conditions for \(f\) being an injection or not being an injection.

    Let \(f: A \to B\)

    "The function \(f\) is an injection" means that

    • for all \(x_1, x_2 \in A\), if \(x_1 \ne x_2\), then \(f(x_1) \ne f(x_2)\); or
    • for all \(x_1, x_2 \in A\), if \(f(x_1) = f(x_2)\), then \(x_1 = x_2\).

    “The function \(f\) is not an injection” means that

    • There exist \(x_1, x_2 \in A\) such that \(x_1 \ne x_2\) and \(f(x_1) = f(x_2)\).
    Progress Check 6.10 (Working with the Definition of an Injection)

    Now that we have defined what it means for a function to be an injection, we can see that in Part (3) of Preview Activity \(\PageIndex{2}\), we proved that the function \(g: \mathbb{R} \to \mathbb{R}\) is an injection, where \(g(x/) = 5x + 3\) for all \(x \in \mathbb{R}\). Use the definition (or its negation) to determine whether or not the following functions are injections.

    1. \(k: A \to B\), where \(A = \{a, b, c\}\), \(B = \{1, 2, 3, 4\}\), and \(k(a) = 4, k(b) = 1\), and \(k(c) = 3\).
    2. \(f: A \to C\), where \(A = \{a, b, c\}\), \(C = \{1, 2, 3\}\), and \(f(a) = 2, f(b) = 3\), and \(f(c) = 2\).
    3. \(F: \mathbb{Z} \to \mathbb{Z}\) defined by \(F(m) = 3m + 2\) for all \(m \in \mathbb{Z}\)
    4. \(h: \mathbb{R} \to \mathbb{R}\) defined by \(h(x) = x^2 - 3x\) for all \(x \in \mathbb{R}\)
    5. \(s: \mathbb{Z}_5 \to \mathbb{Z}_5\) defined by \(sx) = x^3\) for all \(x \in \mathbb{Z}_5\)
    Answer

    Add texts here. Do not delete this text first.

    Surjections

    In previous sections and in Preview Activity \(\PageIndex{1}\), we have seen that there exist functions \(f: A \to B\) for which range\((f) = B\). This means that every element of \(B\) is an output of the function f for some input from the set \(A\). Using quantifiers, this means that for every \(y \in B\), there exists an \(x \in A\) such that \(f(x) = y\). One of the objectives of the preview activities was to motivate the following definition.

    Definition

    Let \(f: A \to B\) be a function from the set \(A\) to the set \(B\). The function \(f\) is called a surjection provided that the range of \(f\) equals the codomain of \(f\). This means that

    for every \(y \in B\), there exists an \(x \in A\) such that \(f(x) = y\).

    When \(f\) is a surjection, we also say that \(f\) is an onto function or that \(f\) maps \(A\) onto \(B\). We also say that \(f\) is a surjective function.

    One of the conditions that specifies that a function \(f\) is a surjection is given in the form of a universally quantified statement, which is the primary statement used in proving a function is (or is not) a surjection. Although we did not define the term then, we have already written the negation for the statement defining a surjection in Part (2) of Preview Activity \(\PageIndex{2}\). We now summarize the conditions for \(f\) being a surjection or not being a surjection.

    Let \(f: A \to B\)

    "The function \(f\) is a surjection" means that

    • range(\(f\)) = codom\((f) = B\); or
    • For every \(y \in B\), there exsits an \(x \in A\) such that \(f(x) = y\).

    “The function \(f\) is not a surjection” means that

    • rang(\(f\)) \ne codom(\(f\)); or
    • There exists a \(y \in B\) such that for all \(x \in A\), \(f(x) \ne y\).

    One other important type of function is when a function is both an injection and surjection. This type of function is called a bijection.

    Definition

    A bijection is a function that is both an injection and a surjection. If the function \(f\) is a bijection, we also say that \(f\) is one-to-one and onto and that \(f\) is a bijective function.

    Progress Check 6.11 (Working with the Definition of a Surjection)

    Now that we have defined what it means for a function to be a surjection, we can see that in Part (3) of Preview Activity \(\PageIndex{2}\), we proved that the function \(g: \mathbb{R} \to \mathbb{R}\) is a surjection, where \(g(x) = 5x + 3\) for all \(x \in \mathbb{R}\). Determine whether or not the following functions are surjections.

    1. \(k: A \to B\), where \(A = \{a, b, c\}\), \(B = \{1, 2, 3, 4\}\), and \(k(a) = 4, k(b) = 1\), and \(k(c) = 3\).
    2. \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = 3x + 2\) for all \(x \in \mathbb{R}\).
    3. \(F: \mathbb{Z} \to \mathbb{Z}\) defined by \(F(m) = 3m + 2\) for all \(m \in \mathbb{Z}\).
    4. \(s: \mathbb{Z}_5 \to \mathbb{Z}_5\) defined by \(s(x) = x^3\) for all \(x \in \mathbb{Z}_5\).
    Answer

    Add texts here. Do not delete this text first.

    The Importance of the Domain and Codomain

    The functions in the next two examples will illustrate why the domain and the codomain of a function are just as important as the rule defining the outputs of a function when we need to determine if the function is a surjection.

    Example 6.12 (A Function that Is Neither an Injection nor a Surjection)

    Let \(f: \mathbb{R} \to \mathbb{R}\) be defined by \(f(x) = x^2 + 1\). Notice that

    \(f(2) = 5\) and \(f(-2) = 5\).

    This is enough to prove that the function \(f\) is not an injection since this shows that there exist two different inputs that produce the same output.

    Since \(f(x) = x^2 + 1\), we know that \(f(x) \ge 1\) for all \(x \in \mathbb{R}\). This implies that the function \(f\) is not a surjection. For example, -2 is in the codomain of \(f\) and \(f(x) \ne -2\) for all \(x\) in the domain of \(f\).

    Example 6.13 (A Function that Is Not an Injection but Is a Surjection)

    Let \(T = \{y \in \mathbb{R}\ |\ y \ge 1\}\), and define \(F: \mathbb{R} \to T\) by \(F(x) = x^2 + 1\). As in Example 6.12, the function \(F\) is not an injection since \(F(2) = F(-2) = 5\).

    Is the function \(F\) a surjection? That is, does \(F\) map \(\mathbb{R}\) onto \(T\)? As in Example 6.12, we do know that \(F(x) \ge 1\) for all \(x \in \mathbb{R}\).

    To see if it is a surjection, we must determine if it is true that for every \(y \in T\), there exists an \(x \in \mathbb{R}\) such that \(F(x) = y\). So we choose \(y \in T\). The goal is to determine if there exists an \(x \in \mathbb{R}\) such that

    \[\begin{array} {rcl} {F(x)} &= & {y, \text { or}} \\ {x^2 + 1} &= & {y.} \end{array}\]

    One way to proceed is to work backward and solve the last equation (if possible) for \(x\). Doing so, we get

    \(x^2 = y - 1\)

    \(x = \sqrt{y - 1}\) or \(x = -\sqrt{y - 1}.\)

    Now, since \(y \in T\), we know that \(y \ge 1\) and hence that \(y - 1 \ge 0\). This means that \(\sqrt{y - 1} \in \mathbb{R}\). Hence, if we use \(x = \sqrt{y - 1}\), then \(x \in \mathbb{R}\), and

    \[\begin{array} {rcl} {F(x)} &= & {F(\sqrt{y - 1})} \\ {} &= & {(\sqrt{y - 1})^2 + 1} \\ {} &= & {(y - 1) + 1} \\ {} &= & {y.} \end{array}\]

    This proves that \(F\) is a surjection since we have shown that for all \(y \in T\), there exists an

    \(x \in \mathbb{R}\) such that \(F(x) = y\). Notice that for each \(y \in T\), this was a constructive proof of the existence of an \(x \in \mathbb{R}\) such that \(F(x) = y\).

    An Important Lesson.

    In Examples 6.12 and 6.13, the same mathematical formula was used to determine the outputs for the functions. However, one function was not a surjection and the other one was a surjection. This illustrates the important fact that whether a function is surjective not only depends on the formula that defines the output of the function but also on the domain and codomain of the function.

    The next example will show that whether or not a function is an injection also depends on the domain of the function.

    Example 6.14 (A Function that Is a Injection but Is Not a Surjection)

    Let \(\mathbb{Z}^{\ast} = \{x \in \mathbb{Z}\ |\ x \ge 0\} = \mathbb{N} \cup \{0\}\). Define \(g: \mathbb{Z}^{\ast} \to \mathbb{N}\) by \(g(x) = x^2 + 1\). (Notice that this is the same formula used in Examples 6.12 and 6.13.) Following is a table of values for some inputs for the function \(g\).

    屏幕快照 2019-03-31 下午4.48.49.png

    Notice that the codomain is \(\mathbb{N}\), and the table of values suggests that some natural numbers are not outputs of this function. So it appears that the function \(g\) is not a surjection.

    To prove that g is not a surjection, pick an element of \(\mathbb{N}\) that does not appear to be in the range. We will use 3, and we will use a proof by contradiction to prove that there is no x in the domain (\(\mathbb{Z}^{\ast}\)) such that \(g(x) = 3\). So we assume that there exists an \(x \in \mathbb{Z}^{\ast}\) with \(g(x) = 3\). Then

    \[\begin{array} {rcl} {x^2 + 1} &= & {3} \\ {x^2} &= & {2} \\ {x} &= & {\pm \sqrt{2}.} \end{array}\]

    But this is not possible since \(\sqrt{2} \notin \mathbb{Z}^{\ast}\). Therefore, there is no \(x \in \mathbb{Z}^{\ast}\) with \(g(x) = 3\). This means that for every \(x \in \mathbb{Z}^{\ast}\), \(g(x) \ne 3\). Therefore, 3 is not in the range of \(g\), and hence \(g\) is not a surjection.

    The table of values suggests that different inputs produce different outputs, and hence that \(g\) is an injection. To prove that \(g\) is an injection, assume that \(s, t \in \mathbb{Z}^{\ast}\) (the domain) with \(g(s) = g(t)\). Then

    \[\begin{array} {rcl} {s^2 + 1} &= & {t^2 + 1} \\ {s^2} &= & {t^2.} \end{array}\]

    Since \(s, t \in \mathbb{Z}^{\ast}\), we know that \(s \ge 0\) and \(t \ge 0\). So the preceding equation implies that \(s = t\). Hence, \(g\) is an injection.

    An Important Lesson

    The functions in the three preceding examples all used the same formula to determine the outputs. The functions in Exam- ples 6.12 and 6.13 are not injections but the function in Example 6.14 is an injection. This illustrates the important fact that whether a function is injective not only depends on the formula that defines the output of the function but also on the domain of the function.

    Progress Check 6.15 (The Importance of the Domain and Codomain)

    Let \(R^{+} = \{y \in \mathbb{R}\ |\ y > 0\}\). Define

    \[\begin{array} {rcl} {f} &: & {\mathbb{R} \to \mathbb{R} \text{ by } f(x) = e^{-x}, \text{ for each } x \in \mathbb{R}, \text{ and }} \\ {g} &: & {\mathbb{R} \to \mathbb{R}^{+} \text{ by } g(x) = e^{-x}, \text{ for each } x \in \mathbb{R}.}

    Determine if each of these functions is an injection or a surjection. Justify your conclusions. Note: Before writing proofs, it might be helpful to draw the graph of \(y = e^{-x}\). A reasonable graph can be obtained using \(-3 \le x \le 3\) and \(-2 \le y \le 10\). Please keep in mind that the graph is does not prove your conclusions, but may help you arrive at the correct conclusions, which will still need proof.

    Answer

    Add texts here. Do not delete this text first.

    Working with a Function of Two Variables

    It takes time and practice to become efficient at working with the formal definitions of injection and surjection. As we have seen, all parts of a function are important (the domain, the codomain, and the rule for determining outputs). This is especially true for functions of two variables.

    For example, we define \(f: \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) by

    \(f(a, b) = (2a + b, a - b)\) for all \((a, b) \in \mathbb{R} \times \mathbb{R}\).

    Notice that both the domain and the codomain of this function is the set \(\mathbb{R} \times \mathbb{R}\). Thus, the inputs and the outputs of this function are ordered pairs of real numbers. For example,

    \(f(1, 1) = (3, 0)\) and \(f(-1, 2) = (0, -3)\).

    To explore wheter or not \(f\) is an injection, we assume that \((a, b) \in \mathbb{R} \times \mathbb{R}\), \((c, d) \in \mathbb{R} \times \mathbb{R}\), and \(f(a,b) = f(c,d)\). This means that

    \((2a + b, a - b) = (2c + d, c - d)\).

    Since this equation is an equality of ordered pairs, we see that

    \[\begin{array} {rcl} {2a + b} &= & {2c + d, \text{ and }} \\ {a - b} &= & {c - d.} \end{array}\]

    By adding the corresponding sides of the two equations in this system, we obtain \(3a = 3c\) and hence, \(a = c\). Substituting \(a = c\) into either equation in the system give us \(b = d\). Since \(a = c\) and \(b = d\), we conclude that

    \((a, b) = (c, d)\).

    Hence, we have shown that if \(f(a, b) = f(c, d)\), then \((a, b) = (c, d)\). Therefore, \(f\) is an injection.

    Now, to determine if \(f\) is a surjection, we let \((r, s) \in \mathbb{R} \times \mathbb{R}\), where \((r, s)\) is considered to be an arbitrary element of the codomain of the function f . Can we find an ordered pair \((a, b) \in \mathbb{R} \times \mathbb{R}\) such that \(f(a, b) = (r, s)\)? Working backward, we see that in order to do this, we need

    \((2a + b, a - b) = (r, s).\)

    That is, we need

    \(2a + b = r\) and \(a - b = s\).

    Solving this system for \(a\) and \(b\) yields

    \(a = \dfrac{r + s}{3}\) and \(b = \dfrac{r - 2s}{3}\).

    Since \(r, s \in \mathbb{R}\), we can conclude that \(a \in \mathbb{R}\) and \(b \in \mathbb{R}\) and hence that \((a, b) \in \mathbb{R} \times \mathbb{R}\).

    We now need to verify that for. these values of \(a\) and \(b\), we get \(f(a, b) = (r, s)\). So

    \[\begin{array} {rcl} {f(a, b)} &= & {f(\dfrac{r + s}{3}, \dfrac{r - 2s}{3})} \\ {} &= & {(2(\dfrac{r + s}{3}) + \dfrac{r - 2s}{3}, \dfrac{r + s}{3} - \dfrac{r - 2s}{3})} \\ {} &= & {(\dfrac{2r + 2s + r - 2s}{3}, \dfrac{r + s - r + 2s}{3})} \\ {} &= & {(r, s).} \end{array}\]

    This proves that for all \((r, s) \in \mathbb{R} \times \mathbb{R}\), there exists \((a, b) \in \mathbb{R} \times \mathbb{R}\) such that \(f(a, b) = (r, s)\). Hence, the function \(f\) is a surjection. Since \(f\) is both an injection and a surjection, it is a bijection.

    Progress Check 6.16 (A Function of Two Variables)

    Let \(g: \mathbb{R} \times \mathbb{R} \to \mathbb{R}\) be defined by \(g(x, y) = 2x + y\), for all \((x, y) \in \mathbb{R} \times \mathbb{R}\).

    Note: Be careful! One major difference between this function and the previous example is that for the function \(g\), the codomain is \(\mathbb{R}\), not \(\mathbb{R} \times \mathbb{R}\). It is a good idea to begin by computing several outputs for several inputs (and remember that the inputs are ordered pairs).

    1. Notice that the ordered pair \((1, 0) \in \mathbb{R} \times \mathbb{R}\). That is (1, 0) is in the domain of \(g\). Also notice that \(g(1, 0) = 2\). Is it possible to find another ordered pair \((a, b) \in \mathbb{R} \times \mathbb{R}\) such that \(g(a, b) = 2\)?
    2. Let \(z \in \mathbb{R}\). Then \((0, z) \in \mathbb{R} \times \mathbb{R}\) and so \((0, z) \in \text{dom}(g)\). Now determine \(g(0, z)\)?
    3. Is the function \(g\) an injection? Is the function \(g\) a surjection? Justify your conclusions.
    Answer

    Add texts here. Do not delete this text first.

    Exercise 6.3
    1. (a) Draw an arrow diagram that represents a function that is an injection but is not a surjection.
      (b) Draw an arrow diagram that represents a function that is an injection and is a surjection.
      (c) Draw an arrow diagram that represents a function that is not an injection and is not a surjection.
      (d) Draw an arrow diagram that represents a function that is not an injection but is a surjection.
      (e) Draw an arrow diagram that represents a function that is not a bijection.
    2. Let \(\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}\) and let \(\mathbb{Z}_6 = \{0, 1, 2, 3, 4, 5\}\). For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.

      (a) \(f: \mathbb{Z}_5 \to \mathbb{Z}_5\) by \(f(x) = x^2 + 4\) (mod 5), for all \(x \in \mathbb{Z}_5\)
      (b) \(g: \mathbb{Z}_6 \to \mathbb{Z}_6\) by \(g(x) = x^2 + 4\) (mod 6), for all \(x \in \mathbb{Z}_6\)
      (c) \(F: \mathbb{Z}_5 \to \mathbb{Z}_5\) by \(F(x) = x^3 + 4\) (mod 5), for all \(x \in \mathbb{Z}_5\)
    3. For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.

      (a) \(f: \mathbb{Z} \to \mathbb{Z}\) defined by \(f(x) = 3x + 1\), for all \(x \in \mathbb{Z}\).
      (b) \(F: \mathbb{Q} \to \mathbb{Q}\) defined by \(F(x) = 3x + 1\), for all \(x \in \mathbb{Q}\).
      (c) \(g: \mathbb{R} \to \mathbb{R}\) defined by \(g(x) = x^3\), for all \(x \in \mathbb{R}\).
      (d) \(G: \mathbb{Q} \to \mathbb{Q}\) defined by \(G(x) = x^3\), for all \(x \in \mathbb{Q}\).
      (e) \(k: \mathbb{R} \to \mathbb{R}\) defined by \(k(x) = e^{-x^2}\), for all \(x \in \mathbb{R}\).
      (f) \(K: \mathbb{R}^{\ast} \to \mathbb{R}\) defined by \(K(x) = e^{-x^2}\), for all \(x \in \mathbb{R}^{\ast}\).
      Note: \(\mathbb{R}^{\ast} = \{x \in \mathbb{R}\ |\ x \ge 0\}.\)
      (g) \(K_1: \mathbb{R}^{\ast} \to T\) defined by \(K_1(x) = e^{-x^2}\), for all \(x \in \mathbb{R}^{\ast}\), where \(T = \{y \in \mathbb{R}\ |\ 0 < y \le 1\}\).
      (h) \(h: \mathbb{R} \to \mathbb{R}\) defined by \(h(x) = \dfrac{2x}{x^2 + 4}\), for all \(x \in \mathbb{R}\).
      (i) \(H: \{x \in \mathbb{R}\ |\ x \ge 0\} \to \{y \in \mathbb{R}\ |\ 0 \le y \le \dfrac{1}{2}\}\) defined by \(H(x) = \dfrac{2x}{x^2 + 4}\), for all \(x \in \{x \in \mathbb{R}\ |\ x \ge 0\}\).
    4. For each of the following functions, determine if the function is a bijection. Justify all conclusions.

      (a) \(F: \mathbb{R} \to \mathbb{R}\) defined by \(F(x) = 5x + 3\), for all \(x \in \mathbb{R}\).
      (b) \(G: \mathbb{Z} \to \mathbb{Z}\) defined by \(G(x) = 5x + 3\), for all \(x \in \mathbb{Z}\).
      (c) \(f: (\mathbb{R} - \{4\}) \to \mathbb{R}\) defined by \(f(x) = \dfrac{3x}{x - 4}\), for all \(x \in (\mathbb{R} - \{4\})\).
      (d) \(g: (\mathbb{R} - \{4\}) \to (\mathbb{R} - \{3\})\) defined by \(g(x) = \dfrac{3x}{x - 4}\), for all \(x \in (\mathbb{R} - \{4\})\).
    5. Let \(s: \mathbb{N} \to \mathbb{N}\), where for each \(n \in \mathbb{N}\), \(s(n)\) is the sum of the distinct natural number divisors of \(n\). This is the sum of the divisors function that was introduced in Preview Activity \(\PageIndex{2}\) from Section 6.1. Is \(s\) an injection? Is \(s\) a surjection? Justify your conclusions.
    6. Let \(d: \mathbb{N} \to \mathbb{N}\), where \(d(n)\) is the number of natural number divisors of \(n\). This is the number of divisors function introduced in Exercise (6) from Section 6.1. Is the function \(d\) an injection? Is the function \(d\) a surjection? Justify your conclusions.
    7. In Preview Activity \(\PageIndex{2}\) from Section 6.1 , we introduced the birthday function. Is the birthday function an injection? Is it a surjection? Justify your conclusions.
    8. (a) Let \(f: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\) be defined by \(f(m,n) = 2m + n\). Is the function \(f\) an injection? Is the function \(f\) a surjection? Justify your conclusions.
      (b) Let \(g: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\) be defined by \(g(m,n) = 6m + 3n\). Is the function \(g\) an injection? Is the function \(g\) a surjection? Justify your conclusions.
    9. (a) Let \(f: \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) be defined by \(f(x,y) = (2x, x + y)\). Is the function \(f\) an injection? Is the function \(f\) a surjection? Justify your conclusions.
      (b) Let \(g: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) be defined by \(g(x,y) = (2x, x + y)\). Is the function \(g\) an injection? Is the function \(g\) a surjection? Justify your conclusions.
    10. Let \(f: \mathbb{R} \times \mathbb{R} \to \mathbb{R}\) be the function defined by \(f(x, y) = -x^2y + 3y\), for all \((x, y) \in \mathbb{R} \times \mathbb{R}\). Is the function \(f\) and injection? Is the function \(f\) a surjection? Justify your conclusions.
    11. Let \(g: \mathbb{R} \times \mathbb{R} \to \mathbb{R}\) be the function defined by \(g(x, y) = (x^3 + 2)sin y\), for all \((x, y) \in \mathbb{R} \times \mathbb{R}\). Is the function \(g\) and injection? Is the function \(g\) a surjection? Justify your conclusions.
    12. Let \(A\) be a nonempty set. The identity function on the set \(A\), denoted by \(I_A\), is the function \(I_A: A \to A\) defined by \(I_A (x) = x\) for every \(x\) in \(A\). Is \(I_A\) an injection? Is \(I_A\) a surjection? Justify your conclusions.
    13. Let \(A\) and \(B\) be two nonempty sets. Define
      \[p_1: A \times B \to A \text{ by } p_1(a, b) = a\]
      for every \((a, b) \in A \times B\). That is the first projection function introduced in Exercise (5) in Section 6.2.
      (a) Is the function \(p_1\) a surjection? Justify your conclusion.
      (b) If \(B = \{b\}\), is the function \(p_1\) an injection? Justify your conclusion.
      (c) Under what condition(s) is the function \(p_1\) not an injection? Make a conjecture and prove it.
    14. Define \(f: \mathbb{N} \to \mathbb{Z}\) be defined as follows: For each \(n \in \mathbb{N}\),
      \[f(n) = \dfrac{1 + (-1)^n (2n - 1)}{4}.\]
      Is the function \(f\) an injection? Is the function \(f\) a surjection? Justify your conclusions.

      Suggestions. Start by calculating several outputs for the function before you attempt to write a proof. In exploring whether or not the function is an injection, it might be a good idea to uses cases based on whether the inputs are even or odd. In exploring whether f is a surjection, consider using cases based on whether the output is positive or less than or equal to zero.
    15. Let \(C\) be the set of all real functions that are continuous on the closed interval [0, 1]. Define the function \(A: C \to \mathbb{R}\) as follows: For each \(f \in C\).
      \[A(f) = \int_0^1 f(x)dx.\]
      Is the function \(A\) an injection? Is it a surjection? Justify your conclusions.
    16. Let \(A = \{(m, n)\ |\ m \in \mathbb{Z}, n \in \mathbb{Z}, \text{ and } n \ne 0\}\). Define \(f: A \to \mathbb{Q}\) as follows:
      For each \((m, n) \in A\), \(f(m, n) = \dfrac{m + n}{n}\).
      (a) Is the function f an injection? Justify your conclusion.
      (b) Is the function f a surjection? Justify your conclusion.
    17. Evaluation of proofs
      See the instructions for Exercise (19) on page 100 from Section 3.1.
      (a)

      Proposition. The function \(f: \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) defined by \(f(x, y) = (2x + y, x - y)\) is an injection.

      Proof

      For each \((a, b)\) and \((c, d)\) in \(\mathbb{R} \times \mathbb{R}\), if \(f(a, b) = f(c, d)\), then

      \((2a + b, a - b) = (2c + d, c - d).\)

      We will use systems of equations to prove that \(a = c\) and \(b = d\).

      \[\begin{array} {rcl} {2a + b} &= & {2c + d} \\ {a - b} &= & {c - d} \\ {3a} &= & {3c} \\ {a} &= & {c} \end{array}\]

      Since \(a = c\), we see that

      \((2c + b, c - b) = (2c + d, c - d).\)

      So \(b = d\). Therefore, we have proved that the function \(f\) is an injection.

      (b)

      Proposition. The function \(f: \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) defined by \(f(x, y) = (2x + y, x - y)\) is an surjection.

      Proof

      We need to find an ordered pair such that \(f(x, y) = (a, b)\) for each \((a, b)\) in \(\mathbb{R} \times \mathbb{R}\). That is, we need \((2x + y, x - y) = (a, b)\), or

      \(2x + y = a\) and \(x - y = b\).

      Treating these two equations as a system of equations and solving for \(x\) and \(y\), we find that

      \(x = \dfrac{a + b}{3}\) and \(y = \dfrac{a - 2b}{3}\).

      Hence, \(x\) and \(y\) are real numbers, \((x, y) \in \mathbb{R} \times \mathbb{R}\), and

      \[\begin{array} {rcl} {f(x, y)} &= & {f(\dfrac{a + b}{3}, \dfrac{a - 2b}{3})} \\ {} &= & {(2(\dfrac{a + b}{3}) + \dfrac{a - 2b}{3}, \dfrac{a + b}{3} - \dfrac{a - 2b}{3})} \\ {} &= & {(\dfrac{2a + 2b + a - 2b}{3}, \dfrac{a + b - a + 2b}{3})} \\ {} &= & {(\dfrac{3a}{3}, \dfrac{3b}{3})} \\ {} &= & {(a, b).} \end{array}\]

      Therefore, we. have proved that for every \((a, b) \in \mathbb{R} \times \mathbb{R}\), there exists an \((x, y) \in \mathbb{R} \times \mathbb{R}\) such that \(f(x, y) = (a, b)\). This proves that the function \(f\) is a surjection.

      Explorations and Activities

    18. Piecewise Defined Functions. We often say that a function is a piecewise defined function if it has different rules for determining the output for different parts of its domain. For example, we can define a function \(f: \mathbb{R} \to \mathbb{R}\) by giving a rule for calculating \(f(x)\) when \(x \ge 0\) and giving a rule for calculating \(f(x)\) when x < 0 as follows:
      \[f(x) = \begin{cases} x^2 + 1, & \text{ if \(x\) \(\ge\) 0;} \\ x - 1 & \text{ if \(x\) < 0.} \end{cases}\]
      (a) Sketch a graph of the function \(f\). Is the function \(f\) and injection? Is the function \(f\) a surjection? Justify your conclusions.

      For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.

      (b) \(g: [0, 1] \to (0, 1)\) by
      \[g(x) = \begin{cases} 0.8, & \text{ if \(x = 0\);} \\ 0.5x & \text{ if \(0 < x < 1\);} \\ 0.6 & \text{ if \(x = 1\).} \end{cases}\]
      (c) \(h: \mathbb{Z} \to \{0, 1\}\) by
      \[h(x) = \begin{cases} 0, & \text{ if \(x\) is even;} \\ 1, & \text{ if \(x\) is odd.} \end{cases}\]
    19. Functions Whose Domain is \(\mathcal{M}_2(\mathbb{R})\). Let \(\mathcal{M}_2(\mathbb{R})\). represent the set of all 2 by 2 matrices over \(\mathbb{R}\).

      (a) Defien det: \(\mathcal{M}_2(\mathbb{R}) \to \mathbb{R}\) by
      \[det
      \left [{\begin{array} {cc}
      a & b\\
      c & d\\
      \end{array}} \right]
      = ad - bc.\]
      This is the determinant function introduced in Exercise (9) from Section 6.2. Is the determinant function an injection? Is the determinant function a surjection? Justify your conclusions.

      (b) Define tran: \(\mathcal{M}_2(\mathbb{R}) \to \mathcal{M}_2(\mathbb{R})\) by
      \[tran
      \left [{\begin{array} {cc}
      a & b\\
      c & d\\
      \end{array}} \right]
      = A^T =
      \left [{\begin{array} {cc}
      a & c\\
      b & d\\
      \end{array}} \right].\]
      This is the transpose function introduced in Exercise (10) from Section 6.2. Is the transpose function an injection? Is the transpose function a surjection? Justify your conclusions.

      (c) Define \(F: \mathcal{M}_2(\mathbb{R}) \to \mathbb{R}\) by
      \[F
      \left [{\begin{array} {cc}
      a & b\\
      c & d\\
      \end{array}} \right]
      = a^2 + d^2 - b^2 - c^2.\]
      Is the function \(F\) an injection? Is the function \(F\) a surjection? Justify your conclusions.
    Answer

    Add texts here. Do not delete this text first.


    This page titled 6.3: Injections, Surjections, and Bijections is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform.