Section 6.3 Injections, Surjections, and Bijections
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.
Beginning Activity Beginning Activity 1: Functions with Finite Domains
Let \(A\) and \(B\) be sets. Given a function \(f\x A \to B\text{,}\) we know the following:
For every \(x \in A\text{,}\) \(f( x ) \in B\text{.}\) That is, every element of \(A\) is an input for the function \(f\text{.}\) This could also be stated as follows: For each \(x \in A\text{,}\) there exists a \(y \in B\) such that \(y = f( x )\text{.}\)
For a given \(x \in A\text{,}\) there is exactly one \(y \in B\) such that \(y = f( x )\text{.}\)
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 \(x_1 \ne x_2\) and \(f( {x_1 } ) = f( {x_2 } )\text{.}\) The arrow diagram for the function \(f\) in Figure 6.15 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\x A \to B\text{,}\) then it is possible to have a \(y \in B\) such that \(g( x ) \ne y\) for all \(x \in A\text{.}\) The arrow diagram for the function \(g\) in Figure 6.15 illustrates such a function.
Now let \(A = \left\{ {1,2,3} \right\}\text{,}\) \(B = \left\{ {a,b,c,d} \right\}\text{,}\) and \(C = \left\{ {s,t} \right\}\text{.}\) Define
| \(f\x A \to B\) by | \(g\x A \to B\) by | \(h\x A \to C\) by |
| \(f( 1 ) = a\) | \(g( 1 ) = a\) | \(h( 1 ) = s\) |
| \(f( 2 ) = b\) | \(g( 2 ) = b\) | \(h( 2 ) = t\) |
| \(f( 3 ) = c\) | \(g( 3 ) = a\) | \(h( 3 ) = s\) |
1.
Which of these functions satisfy the following property for a function \(F\text{?}\)
For all \(x, y \in \text{ dom} ( F )\text{,}\) if \(x \ne y\text{,}\) then \(F(x) \ne F(y)\text{.}\)
2.
Which of these functions satisfy the following property for a function \(F\text{?}\)
For all \(x, y \in \text{ dom} ( F )\text{,}\) if \(F( x ) = F( y )\text{,}\) then \(x = y\text{.}\)
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\text{?}\)
For all \(y\) in the codomain of \(F\text{,}\) there exists an \(x \in \text{ dom} ( F )\) such that \(F( x ) = y\text{.}\)
Beginning Activity Beginning Activity 2: Statements Involving Functions
Let \(A\) and \(B\) be nonempty sets and let \(f\x A \to B\text{.}\) In Beginning Activity 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\text{,}\) if \(x \ne y\text{,}\) then \(f ( x ) \ne f ( y )\text{.}\)
(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\text{,}\) there exists an \(x \in A\) such that \(f ( x ) = y\text{.}\)Write the negation of this statement.
3.
Let \(g:\R \to \R\) be defined by \(g ( x ) = 5x + 3\text{,}\) for all \(x \in \R\text{.}\) Complete the following proofs of the following propositions about the function \(g\text{.}\)
- Propostion 1
For all \(a, b \in \R\text{,}\) if \(g ( a ) = g ( b )\text{,}\) then \(a = b\text{.}\)
- Proof
-
We let \(a, b \in \R\text{,}\) and we assume that \(g ( a ) = g ( b )\) and will prove that \(a = b\text{.}\) Since \(g(a) = g(b)\text{,}\) we know that
\begin{equation*} 5a + 3 = 5b + 3\text{.} \end{equation*}(Now prove that in this situation, \(a = b\text{.}\))
- Proposition 2
For all \(b \in \R\text{,}\) there exists an \(a \in \R\) such that \(g ( a ) = b\text{.}\)
- Proof
-
We let \(b \in \R\text{.}\) We will prove that there exists an \(a \in \R\) such that \(g ( a ) = b\) by constructing such an \(a\) in \(\R\text{.}\) In order for this to happen, we need \(g(a) = 5a + 3 = b\text{.}\)
(Now solve the equation for \(a\) and then show that for this real number \(a\text{,}\) \(g ( a ) = b\text{.}\))
Subsection Injections
In previous sections and in Beginning Activity 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 } )\text{.}\) The work in the beginning 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\text{.}\) The function \(f\) is called an injection provided that
for all \(x_1 , x_2 \in A\text{,}\) if \(x_1 \ne x_2\text{,}\) then \(f( {x_1 } ) \ne f( {x_2 } )\text{.}\)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 Exercise 1 of Beginning Activity 2. In that 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 \(\boldsymbol{f\x A \to B}\).
“The function \(\boldsymbol{f}\) is an injection” means that
For all \(x_1 , x_2 \in A\text{,}\) if \(x_1 \ne x_2\text{,}\) then \(f( {x_1 } ) \ne f( {x_2 } )\text{;}\) or
For all \(x_1 , x_2 \in A\text{,}\) if \(f( {x_1 } ) = f( {x_2 } )\text{,}\) then \(x_1 = x_2\text{.}\)
“The function \(\boldsymbol{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 } )\text{.}\)
Progress Check 6.16. 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 Exercise 3 of Beginning Actiivty 2, we proved that the function \(g\x \R \to \R\) is an injection, where \(g ( x ) = 5x + 3\) for all \(x \in \R\text{.}\) Use the definition (or its negation) to determine whether or not the following functions are injections.
(a)
\(k:A \to B\text{,}\) where \(A = \left\{a, b, c \right\}\text{,}\) \(B = \left\{1, 2, 3, 4 \right\}\text{,}\) and \(k (a) = 4\text{,}\) \(k(b) = 1\text{,}\) and \(k(c) = 3\text{.}\)
(b)
\(f:A \to C\text{,}\) where \(A = \left\{a, b, c \right\}\text{,}\) \(C = \left\{1, 2, 3\right\}\text{,}\) and \(f(a) = 2\text{,}\) \(f(b) = 3\text{,}\) and \(f(c) = 2\text{.}\)
(c)
\(F: \Z \to \Z\) defined by \(F ( m ) = 3m + 2\) for all \(m \in \Z\)
(d)
\(h: \R \to \R\) defined by \(h ( x ) = x^2 - 3x\) for all \(x \in \R\)
(e)
\(R_5 = \{0, 1, 2, 3, 4 \}\) and \(s:R_5 \to R_5\) defined by \(s ( x ) = x^3 \pmod 5\) for all \(x \in R_5\text{.}\)
The functions \(k\text{,}\) \(F\text{,}\) and \(s\) are injections. The functions \(f\) and \(h\) are not injections.
Subsection Surjections
In previous sections and in Beginning Activity 1, we have seen that there exist functions \(f\x A \to B\) for which \(\text{ range} (f) = B\text{.}\) This means that every element of \(B\) is an output of the function \(f\) for some input from the set \(A\text{.}\) Using quantifiers, this means that for every \(y \in B\text{,}\) there exists an \(x \in A\) such that \(f( x ) = y\) . One of the objectives of the beginning activities was to motivate the following definition.
Definition.
Let \(f\x A \to B\) be a function from the set \(A\) to the set \(B\text{.}\) The function \(f\) is called a surjection provided that the range of \(f\) equals the codomain of \(f\text{.}\) This means that
for every \(y \in B\text{,}\) there exists an \(x \in A\) such that \(f( x ) = y\text{.}\)When \(f\) is a surjection, we also say that \(f\) is an onto function or that \(f\) maps \(\boldsymbol{A}\) onto \(\boldsymbol{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 Exercise 2 of Beginning Activity 2. We now summarize the conditions for \(f\) being a surjection or not being a surjection.
Let \(\boldsymbol{f\x A \to B}\).
“The function \(\boldsymbol{f}\) is a surjection” means that
\(\text{ range} ( f ) = \text{ codom} ( f ) = B\text{;}\) or
For every \(y \in B\text{,}\) there exists an \(x \in A\) such that \(f( x ) = y\text{.}\)
“The function \(\boldsymbol{f}\) is not a surjection” means that
\(\text{ range} ( f ) \ne \text{ codom} ( f )\text{;}\) or
There exists a \(y \in B\) such that for all \(x \in A\text{,}\) \(f( x ) \ne y\text{.}\)
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.17. 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 Exercise 3 of Beginning Activity 2, we proved that the function \(g: \R \to \R\) is a surjection, where \(g ( x ) = 5x + 3\) for all \(x \in \R\text{.}\) Determine whether or not the following functions are surjections.
(a)
\(k\x A \to B\text{,}\) where \(A = \left\{a, b, c \right\}\text{,}\) \(B = \left\{1, 2, 3, 4 \right\}\text{,}\) and \(k (a) = 4\text{,}\) \(k(b) = 1\text{,}\) and \(k(c) = 3\text{.}\)
(b)
\(f\x \R \to \R\) defined by \(f ( x ) = 3x + 2\) for all \(x \in \R\text{.}\)
(c)
\(F\x \Z \to \Z\) defined by \(F ( m ) = 3m + 2\) for all \(m \in \Z\text{.}\)
(d)
\(s:R_5 \to R_5\) defined by \(s ( x ) = x^3 \pmod 5\) for all \(x \in R_5\text{.}\)
The functions \(f\) and \(s\) are surjections. The functions \(k\) and \(F\) are not surjections.
Subsection 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.18. A Function that Is Neither an Injection nor a Surjection.
Let \(f\x \mathbb{R} \to \mathbb{R}\) be defined by \(f( x ) = x^2 + 1\text{.}\) Notice that
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\text{,}\) we know that \(f( x ) \geq 1\) for all \(x \in \mathbb{R}\text{.}\) 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\text{.}\)
Example 6.19. A Function that Is Not an Injection but Is a Surjection.
Let \(T = \left\{ y \in \mathbb{R} \mid y \geq 1 \right\}\text{,}\) and define \(F\x \mathbb{R} \to T\) by \(F( x ) = x^2 + 1\text{.}\) As in Example 6.18, the function \(F\) is not an injection since \(F( 2 ) = F( { - 2} ) = 5\text{.}\)
Is the function \(F\) a surjection? That is, does \(F\) map \(\mathbb{R}\) onto \(T\text{?}\) As in Example 6.18, we do know that \(F( x ) \geq 1\) for all \(x \in \mathbb{R}\text{.}\)
To see if it is a surjection, we must determine if it is true that for every \(y \in T\text{,}\) there exists an \(x \in \mathbb{R}\) such that \(F ( x ) = y\text{.}\) So we choose \(y \in T\text{.}\) The goal is to determine if there exists an \(x \in \mathbb{R}\) such that
One way to proceed is to work backward and solve the last equation (if possible) for \(x\text{.}\) Doing so, we get
Now, since \(y \in T\text{,}\) we know that \(y \geq 1\) and hence that \(y - 1 \geq 0\text{.}\) This means that \(\sqrt {y - 1} \in \mathbb{R}\text{.}\) Hence, if we use \(x = \sqrt {y - 1}\text{,}\) then \(x \in \mathbb{R}\text{,}\) and
This proves that \(F\) is a surjection since we have shown that for all \(y \in T\text{,}\) there exists an \(x \in \mathbb{R}\) such that \(F( x ) = y\text{.}\) Notice that for each \(y \in T\text{,}\) this was a constructive proof of the existence of an \(x \in \mathbb{R}\) such that \(F ( x ) = y\text{.}\)
An Important Lesson.
In Example 6.18 and Example 6.19, 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 depends not only 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.20. A Function that Is an Injection but Is Not a Surjection.
Let \(\mathbb{Z}^* = \left\{ { {x \in \mathbb{Z}} \mid x \geq 0} \right\} = \mathbb{N} \cup \left\{ 0 \right\}\text{.}\) Define \(g\x \mathbb{Z}^* \to \mathbb{N}\) by \(g( x ) = x^2 + 1\text{.}\) (Notice that this is the same formula used in Example 6.18 and Example 6.19.) Following is a table of values for some inputs for the function \(g\text{.}\)
| \(x\) | \(g ( x )\) |
| 0 | 1 |
| 1 | 2 |
| 2 | 5 |
| 3 | 10 |
| 4 | 17 |
| 5 | 26 |
Notice that the codomain is \(\mathbb{N}\text{,}\) 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 \(\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 \(\left( \Z^*\right)\) such that \(g( x ) = 3\text{.}\) So we assume that there exists an \(x \in \Z^*\) with \(g( x ) = 3\text{.}\) Then
But this is not possible since \(\sqrt 2 \notin \mathbb{Z}^*\text{.}\) Therefore, there is no \(x \in \mathbb{Z}^*\) with \(g( x ) = 3\text{.}\) This means that for every \(x \in \mathbb{Z}^*\text{,}\) \(g( x ) \ne 3\text{.}\) Therefore, 3 is not in the range of \(g\text{,}\) 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 \Z^*\) (the domain) with \(g( s ) = g( t )\text{.}\) Then
Since \(s, t \in \mathbb{Z}^*\text{,}\) we know that \(s \geq 0\text{ and } t \geq 0\text{.}\) So the preceding equation implies that \(s = t\text{.}\) 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 Example 6.18 and Example 6.19 are not injections but the function in Example 6.20 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.21. The Importance of the Domain and Codomain.
Let \(\R^+ = \{ y \in \R \mid y > 0 \}\text{.}\) Define
\(f \x \R \to \R\) by \(f(x) = e^{-x}\text{,}\) for each \(x \in \R\text{,}\) and
\(g \x \R \to \R^+\) by \(g(x) = e^{-x}\text{,}\) for each \(x \in \R\text{.}\)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}\text{.}\) A reasonable graph can be obtained using \(-3 \leq x \leq 3\) and \(-2 \leq y \leq 10\text{.}\) Please keep in mind that the graph does not prove any conclusion, but may help us arrive at the correct conclusions, which will still need proof.
The function \(f\) is an injection but not a surjection. To see that it is an injection, let \(a, b \in \R\) and assume that \(f(a) = f(b)\text{.}\) This implies that \(e^{-a} = e^{-b}\text{.}\) Now use the natural logarithm function to prove that \(a = b\text{.}\) Since \(e^{-x} > 0\) for each real number \(x\text{,}\) there is no \(x \in \R\) such that \(f(x) = -1\text{.}\) So \(f\) is not a surjection.
The function \(g\) is an injection and is a surjection. The proof that \(g\) is an injection is basically the same as the proof that \(f\) is an injection. To prove that \(g\) is a surjection, let \(b \in \R^+\text{.}\) To construct the real number \(a\) such that \(g(a) = b\text{,}\) solve the equation \(e^{-a} = b\) for \(a\text{.}\) The solution is \(a = -\ln b\text{.}\) It can then be verified that \(g(a) = b\text{.}\)
Subsection 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\x \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) by
Notice that both the domain and the codomain of this function are the set \(\mathbb{R} \times \mathbb{R}\text{.}\) Thus, the inputs and the outputs of this function are ordered pairs of real numbers. For example,
To explore whether or not \(f\) is an injection, we assume that \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) \(( {c, d} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) and \(f( {a, b} ) = f( {c, d} )\text{.}\) This means that
Since this equation is an equality of ordered pairs, we see that
By adding the corresponding sides of the two equations in this system, we obtain \(3a = 3c\) and hence, \(a = c\text{.}\) Substituting \(a = c\) into either equation in the system give us \(b = d\text{.}\) Since \(a = c\) and \(b = d\text{,}\) we conclude that
Hence, we have shown that if \(f( {a, b} ) = f( {c, d} )\text{,}\) then \(( {a, b} ) = ( {c, d} )\text{.}\) Therefore, \(f\) is an injection.
Now, to determine if \(f\) is a surjection, we let \(( {r, s} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) where \(( {r, s} )\) is considered to be an arbitrary element of the codomain of the function \(f\text{.}\) Can we find an ordered pair \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\) such that \(f( {a, b} ) = ( {r, s} )\text{?}\) Working backward, we see that in order to do this, we need
That is, we need
Solving this system for \(a\) and \(b\) yields
Since \(r, s \in \mathbb{R}\text{,}\) we can conclude that \(a \in \mathbb{R}\) and \(b \in \mathbb{R}\) and hence that \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\text{.}\) We now need to verify that for these values of \(a\) and \(b\text{,}\) we get \(f( {a, b} ) = ( {r, s} )\text{.}\) So
This proves that for all \(( {r, s} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) there exists \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\) such that \(f( {a, b} ) = ( {r, s} )\text{.}\) Hence, the function \(f\) is a surjection. Since \(f\) is both an injection and a surjection, it is a bijection.
Progress Check 6.22. A Function of Two Variables.
Let \(g \x \R \times \R \to \R\) be defined by \(g(x, y) = 2x + y\text{,}\) for all \((x, y) \in \R \times \R\text{.}\)
Note: Be careful! One major difference between this function and the previous example is that for the function \(g\text{,}\) the codomain is \(\R\text{,}\) not \(\R \times \R\text{.}\) It is a good idea to begin by computing several outputs for several inputs (and remember that the inputs are ordered pairs).
(a)
Notice that the ordered pair \((1, 0) \in \R \times \R\text{.}\) That is, \((1, 0)\) is in the domain of \(g\text{.}\) Also notice that \(g(1, 0) = 2\text{.}\) Is it possible to find another ordered pair \((a, b) \in \R \times \R\) such that \(g(a, b) = 2\text{?}\)
There are several ordered pairs \((a, b) \in \R \times \R\) such that \(g(a, b) = 2\text{.}\) For example, \(g(0, 2) = 2\text{,}\) \(g(-1, 4) = 2\text{,}\) and \(g(2, -2) = 2\text{.}\)
(b)
Let \(z \in \R\text{.}\) Then \((0, z) \in \R \times \R\) and so \((0, z) \in \text{ dom} (g)\text{.}\) Now determine \(g(0, z)\text{.}\)
For each \(z \in \R\text{,}\) \(g(0, z) = z\text{.}\)
(c)
Is the function \(g\) an injection? Is the function \(g\) a surjection? Justify your conclusions.
Part (1) implies that the function \(g\) is not an injection. Part (2) implies that the function \(g\) is a surjection since for each \(z \in \R\text{,}\) \((0, z)\) is in the domain of \(g\) and \(g(0, z) = z\text{.}\)
Exercises Exercises
1.
Draw an arrow diagram that
(a)
represents a function that is an injection but is not a surjection.
(b)
represents a function that is an injection and is a surjection.
(c)
represents a function that is not an injection and is not a surjection.
(d)
represents a function that is not an injection but is a surjection.
(e)
represents a function that is not a bijection.
2.
We know \(R_5 = \left\{ {0, 1, 2, 3, 4} \right\}\) and \(R_6 = \left\{ {0, 1, 2, 3, 4, 5} \right\}\text{.}\) 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\x R_5 \to R_5\) by \(f( x ) = x^2 + 4 \pmod 5\text{,}\) for all \(x \in R_5\)
Notice that \(f(0) = 4\text{,}\) \(f(1) = 0\text{,}\) \(f(2) = 3\text{,}\) \(f(3) = 3\text{,}\) and \(f(4) = 0\text{.}\) So the function \(f\) is not an injection and is not a surjection.
(b)
\(g\x R_6 \to R_6\) by \(g( x ) = x^2 + 4 \pmod 6\text{,}\) for all \(x \in R_6\)
(c)
\(F\x R_5 \to R_5\) by \(F( x ) = x^3 + 4 \pmod 5\text{,}\) for all \(x \in R_5\)
Notice that \(F(0) = 4\text{,}\) \(F(1) = 0\text{,}\) \(F(2) = 2\text{,}\) \(F(3) = 1\text{,}\) and \(F(4) = 3\text{.}\) So the function \(F\) is an injection and is a surjection.
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\x\mathbb{Z} \to \mathbb{Z}\) defined by \(f( x ) = 3x + 1\text{,}\) for all \(x \in \Z\text{.}\)
The function \(f\) is an injection. To prove this, let \(x_1, x_2 \in \mathbb{Z}\) and assume that \(f ( x_1 ) = f ( x_2 )\text{.}\) Then,
Hence, \(f\) is an injection. Now, for each \(x \in \mathbb{Z}\text{,}\) \(3x + 1 \equiv 1 \pmod 3\text{,}\) and hence \(f ( x ) \equiv 1 \pmod 3\text{.}\) This means that there is no integer \(x\) such that \(f ( x ) = 0\text{.}\) Therefore, \(f\) is not a surjection.
(b)
\(F\x\mathbb{Q} \to \mathbb{Q}\) defined by \(F( x ) = 3x + 1\text{,}\) for all \(x \in \Q\text{.}\)
The proof that \(F\) is an injection is similar to the proof in Part (a) that \(f\) is an injection. To prove that \(F\) is a surjection, let \(y \in \mathbb{Q}\text{.}\) Then, \(\dfrac{y-1}{3} \in \mathbb{Q}\) and \(F \left( \dfrac{y-1}{3} \right) = y\) and hence, \(F\) is a surjection.
(c)
\(g\x\mathbb{R} \to \mathbb{R}\) defined by \(g( x ) = x^3\text{,}\) for all \(x \in \R\text{.}\)
(d)
\(G \x\mathbb{Q} \to \mathbb{Q}\) defined by \(G( x ) = x^3\text{,}\) for all \(x \in \Q\text{.}\)
(e)
\(k \x \R \to \R\) defined by \(k(x) = e^{-x^2}\text{,}\) for all \(x \in \R\text{.}\)
(f)
\(K\x \R^* \to \R\) defined by \(K(x) = e^{-x^2}\text{,}\) for all \(x \in \R^*\text{.}\)
Note: \(\R^* = \left\{ x \in \R \mid x \geq 0 \right\}\text{.}\)
(g)
\(K_1 \x \R^* \to T\) defined by \(K_1(x) = e^{-x^2}\text{,}\) for all \(x \in \R^*\text{,}\) where \(T = \left\{ y \in \R \mid 0 \lt y \leq 1 \right\}\text{.}\)
(h)
\(h \x\R \to \R\) defined by \(h ( x ) = \dfrac{2x}{x^2 + 4}\text{,}\) for all \(x \in \R\text{.}\)
Since \(h(1) = h(4)\text{,}\) the function \(h\) is not an injection. Using calculus, we can see that the function \(h\) has a maximum when \(x = 2\) and a minimum when \(x = -2\text{,}\) and so for each \(x \in \R\text{,}\) \(h(-2) \leq h(x) \leq h(2)\) or
This can be used to prove that \(h\) is not a surjection. We can also prove that there is no \(x \in \R\) such that \(h(x) = 1\) using a proof by contradiction. If such an \(x\) were to exist, then \(\dfrac{2x}{x^2 + 4} = 1\) or \(2x = x^2 + 4\text{.}\) Hence, \(x^2 - 2x + 4 = 0\text{.}\) We can then use the quadratic formula to prove that \(x\) is not a real number. Hence, there is no real number \(x\) such that \(h(x) = 1\) and so \(h\) is not a surjection.
(i)
\(H \x \{x \in \R \mid x \geq 0 \} \to \left\{ y \in \R \left| 0 \leq y \leq \dfrac{1}{2} \right. \right\}\) defined by \(H ( x ) = \dfrac{2x}{x^2 + 4}\text{,}\) for all \(x \in \{x \in \R \mid x \geq 0 \}\text{.}\)
4.
For each of the following functions, determine if the function is a bijection. Justify all conclusions.
(a)
\(F\x\mathbb{R} \to \mathbb{R}\) defined by \(F( x ) = 5x + 3\text{,}\) for all \(x \in \mathbb{R}\text{.}\)
Let \(F\x \mathbb{R} \to \mathbb{R}\) be defined by \(F( x ) = 5x + 3\) for all \(x \in \mathbb{R}\text{.}\) Let \(x_1, x_2 \in \mathbb{R}\) and assume that \(F( x_1 ) = F( x_2 )\text{.}\) Then \(5x_1 + 3 = 5x_2 + 3\text{.}\) Show that this implies that \(x_1 = x_2\) and, hence, \(F\) is an injection. Now let \(y \in \mathbb{R}\text{.}\) Then \(\dfrac{y - 3}{5} \in \mathbb{R}\text{.}\) Prove that \(F \!\left( \dfrac{y - 3}{5} \right) = y\text{.}\) Thus, \(F\) is a surjection and hence \(F\) is a bijection.
(b)
\(G\x\Z \to \Z\) defined by \(G( x ) = 5x + 3\text{,}\) for all \(x \in \Z\text{.}\)
The proof that \(G\) is an injection is similar to the proof in Part (a) that \(F\) is an injection. Notice that for each \(x \in \Z\text{,}\) \(G(x) \equiv 3 \pmod 5\text{.}\) Now explain why \(G\) is not a surjection.
(c)
\(f\x ( \R -\left\{ 4 \right\} ) \to \R\) defined by \(f ( x ) = \dfrac{3x}{x - 4}\text{,}\) for all \(x \in \left( \R - \{ 4 \} \right)\text{.}\)
(d)
\(g\x ( \R -\left\{ 4 \right\} ) \to ( \R - \left\{ 3 \right\} )\) defined by \(g ( x ) = \dfrac{3x}{x - 4}\text{,}\) for all \linebreak\(x \in \left( \R - \{ 4 \} \right)\text{.}\)
5.
Let \(s\x\mathbb{N} \to \mathbb{N}\text{,}\) where for each \(n \in \mathbb{N}\text{,}\) \(s( n )\) is the sum of the distinct natural number divisors of \(n\text{.}\) This is the sum of the divisors function that was introduced in Beginning Activity 2 from Section 6.1. Is \(s\) an injection? Is \(s\) a surjection? Justify your conclusions.
6.
Let \(d\x\mathbb{N} \to \mathbb{N}\text{,}\) where \(d( n )\) is the number of natural number divisors of \(n\text{.}\) 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 Beginning Activity 2 from Section 6.1, we introduced the birthday function. Is the birthday function an injection? Is it a surjection? Justify your conclusions.
The birthday function is not an injection since there are two different people with the same birthday. The birthday function is a surjection since for each day of the year, there is a person that was born on that day.
8.
Complete the following. Justify your conclusions.
(a)
Let \(f\x\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\) be defined by \(f( {m, n} ) = 2m + n\text{.}\) Is the function \(f\) an injection? Is the function \(f\) a surjection?
(b)
Let \(g\x\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\) be defined by \(g( {m, n} ) = 6m + 3n\text{.}\) Is the function \(g\) an injection? Is the function \(g\) a surjection?
9.
Complete the following. Justify your conclusions.
(a)
Let \(f\x\mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}\) be defined by \(f( {x, y} ) = ( {2x, x + y} )\text{.}\) Is the function \(f\) an injection? Is the function \(f\) a surjection?
The function \(f\) is an injection and a surjection. To prove that \(f\) is an injection, we assume that \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) \(( {c, d} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) and that \(f( {a, b} ) = f( {c, d} )\text{.}\) This means that
Since this equation is an equality of ordered pairs, we see that
The first equation implies that \(a = c\text{.}\) Substituting this into the second equation shows that \(b = d\text{.}\) Hence,
and we have shown that if \(f( {a, b} ) = f( {c, d} )\text{,}\) then \(( {a, b} ) = ( {c, d} )\text{.}\) Therefore, \(f\) is an injection.
Now, to determine if \(f\) is a surjection, we let \(( {r, s} ) \in \mathbb{R} \times \mathbb{R}\text{.}\) To find an ordered pair \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\) such that \(f( {a, b} ) = ( {r, s} )\text{,}\) we need
That is, we need
Solving this system for \(a\) and \(b\) yields
Since \(r, s \in \mathbb{R}\text{,}\) we can conclude that \(a \in \mathbb{R}\) and \(b \in \mathbb{R}\) and hence that \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\) . So,
This proves that for all \(( {r, s} ) \in \mathbb{R} \times \mathbb{R}\text{,}\) there exists \(( {a, b} ) \in \mathbb{R} \times \mathbb{R}\) such that \(f( {a, b} ) = ( {r, s} )\text{.}\) Hence, the function \(f\) is a surjection. Since \(f\) is both an injection and a surjection, it is a bijection.
(b)
Let \(g\x\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) be defined by \(g( {x, y} ) = ( {2x, x + y} )\text{.}\) Is the function \(g\) an injection? Is the function \(g\) a surjection?
The proof that the function \(g\) is an injection is similar to the proof that \(f\) is an injection in Part (a). Now use the fact that the first coordinate of \(g(x, y)\) is an even integer to explain why the function \(g\) is not a surjection.
10.
Let \(f\x\R \times \R \to \R\) be the function defined by \(f (x, y ) = -x^2y+3y\text{,}\) for all \((x, y ) \in \R \times \R\text{.}\) Is the function \(f\) an injection? Is the function \(f\) a surjection? Justify your conclusions.
11.
Let \(g\x\R \times \R \to \R\) be the function defined by \(g (x, y ) = ( x^3 + 2) \sin y\text{,}\) for all \((x, y ) \in \R \times \R\text{.}\) Is the function \(g\) an injection? Is the function \(g\) a surjection? Justify your conclusions.
12.
Let \(A\) be a nonempty set. The identity function on the set \(\boldsymbol{A}\), denoted by \(I_A\text{,}\) is the function \(I_A \x A \to A\) defined by \(I_A ( x ) = x\) for every \(x\) in \(A\text{.}\) Is \(I_A\) an injection? Is \(I_A\) a surjection? Justify your conclusions.
13.
Let \(A\) and \(B\) be two nonempty sets. Define
for every \(( {a, b} ) \in A \times B\text{.}\) This 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 = \left\{ b \right\}\text{,}\) 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:\N \to \Z\) as follows: For each \(n \in \N\text{,}\)
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 use 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 \(\left[ 0, 1 \right]\text{.}\) Define the function \(A\x C \to \mathbb{R}\) as follows: For each \(f \in C\text{,}\)
Is the function \(A\) an injection? Is it a surjection? Justify your conclusions.
16.
Let \(A = \left\{ ( m, n ) \mid m \in \mathbb{Z}, n \in \mathbb{Z}, \text{ and } n \ne 0 \right\}\text{.}\) Define \(f\x A \to \mathbb{Q}\) as follows:
For each \(( m, n ) \in A\text{,}\) \(f ( m, n ) = \dfrac{m+n}{n}\text{.}\)
(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 from Section 3.1.
(a)
- Proposition
Propostion: The function \(f\x\R \times \R \to \R \times \R\) defined by \(f( {x, y} ) = ( {2x + y, x - y} )\) is an injection.
- Proof
-
For each \((a, b)\) and \((c, d)\) in \(\R \times \R\text{,}\) if \(f(a, b) = f(c, d)\text{,}\) then
\begin{equation*} (2a + b, a - b) = (2c + d, c - d)\text{.} \end{equation*}We will use systems of equations to prove that \(a = c\) and \(b = d\text{.}\)
\begin{align*} 2a + b \amp = 2c + d\\ a - b \amp = c - d\\ 3a \amp = 3c\\ a \amp = c \end{align*}Since \(a = c\text{,}\) we see that
\begin{equation*} (2c + b, c - b) = (2c + d, c - d)\text{.} \end{equation*}So \(b = d\text{.}\) Therefore, we have proved that the function \(f\) is an injection.
(b)
- Proposition
The function \(f\x\R \times \R \to \R \times \R\) defined by \(f( {x, y} ) = ( {2x + y, x - y} )\) is a surjection.
- Proof
-
We need to find an ordered pair such that \(f(x, y) = (a, b)\) for each \((a, b)\) in \(\R \times \R\text{.}\) That is, we need \((2x + y, x - y) = (a, b)\text{,}\) or
\begin{equation*} 2x + y = a \qquad \text{ and } \qquad x - y = b\text{.} \end{equation*}Treating these two equations as a system of equations and solving for \(x\) and \(y\text{,}\) we find that
\begin{equation*} x = \frac{a + b}{3} \qquad \text{ and } \qquad y = \frac{a - 2b}{3}\text{.} \end{equation*}Hence, \(x\) and \(y\) are real numbers, \((x, y) \in \R \times \R\text{,}\) and
\begin{align*} f(x, y) \amp = f \left( \frac{a + b}{3}, \frac{a - 2b}{3} \right)\\ \amp = \left(2 \left( \frac{a + b}{3} \right) + \frac{a - 2b}{3}, \frac{a + b}{3} - \frac{a - 2b}{3} \right)\\ \amp = \left( \frac{2a + 2b + a - 2b}{3}, \frac{a + b - a + 2b}{3} \right)\\ \amp = \left( \frac{3a}{3}, \frac{3b}{3} \right)\\ \amp = (a, b)\text{.} \end{align*}Therefore, we have proved that for every \((a, b) \in \R \times \R\text{,}\) there exists an \((x, y) \in \R \times \R\) such that \(f(x, y) = (a, b)\text{.}\) This proves that the function \(f\) is a surjection.
Activity 36. 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\x\R \to \R\) by giving a rule for calculating \(f(x)\) when \(x \geq 0\) and giving a rule for calculating \(f(x)\) when \(x \lt 0\) as follows:
(a)
Sketch a graph of the function \(f\text{.}\) Is the function \(f\) an injection? Is the function \(f\) a surjection? Justify your conclusions.
(b)
For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.
(i)
\(g\x[0, 1] \to (0, 1)\) by
(ii)
\(h\x\Z \to \left\{ 0, 1 \right\}\) by
Activity 37. Functions Whose Domain is \(\boldsymbol{\mathcal{M}_2(\R)}\).
Let \(\mathcal{M}_2 ( \R )\) represent the set of all 2 by 2 matrices over \(\mathbb{R}\text{.}\)
(a)
Define \(\det \x\mathcal{M}_2( \R ) \to \mathbb{R}\) by
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 \(\text{ tran } \x\mathcal{M}_2( \R ) \to \mathcal{M}_2 ( \R )\) by
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 \x\mathcal{M}_2( \R ) \to \mathbb{R}\) by
Is the function \(F\) an injection? Is the function \(F\) a surjection? Justify your conclusions.