How do you find the number of injections from A to B?
\( \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}}\) Show
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 DomainsLet \(A\) and \(B\) be sets. Given a function \(f : A \to B\), we know the following:
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. Now let \(A = \{1, 2, 3\}\), \(B = \{a, b, c, d\}\), and \(C = \{s, t\}\). Define
Preview Activity \(\PageIndex{1}\): Statements Involving FunctionsLet \(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.
InjectionsIn 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. DefinitionLet \(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
“The function \(f\) is not an injection” means that
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.
Add texts here. Do not delete this text first. SurjectionsIn 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. DefinitionLet \(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
“The function \(f\) is not a surjection” means that
One other important type of function is when a function is both an injection and surjection. This type of function is called a bijection. DefinitionA 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.
Add texts here. Do not delete this text first. The Importance of the Domain and CodomainThe 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\). 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 LessonThe 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. AnswerAdd texts here. Do not delete this text first. Working with a Function of Two VariablesIt 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).
Add texts here. Do not delete this text first. Exercise 6.3
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; a detailed edit history is available upon request. How many injections are there from A to B?Hence, total injections from set A into set B are 24.
How many injections are defined from set A to set B if set A has 4 elements and set B has 5 elements?The number of injections from A to B = 6P5 = 6! = 720. Q. Set A consists of 4 distinct elements & the set B consists of 5 distinct elements.
How many functions are there from 1 2 3 4 5 to ABC?There are only three functions so you can list them out.
What is injection in set?injection, in mathematics, a mapping (or function) between two sets such that the domain (input) of the mapping consists of all the elements of the first set, the range (output) consists of some subset of the second set, and each element of the first set is mapped to a different element of the second set (one-to-one).
|