Skip to main content

Section 6.3 One-to-one and Onto

In this section, we look at the formal definition of a function and the properties of one-to-one and onto that make a function a pairing.

Subsection 6.3.A Ordered Pairs and the Definition of Function

The formal definition of function uses the concept of an ordered pair. We have used ordered pairs, for example, in discussing points in the \(xy\)-plane. There is a clever way of defining an ordered pair using sets. We begin with that definition.

Definition 6.3.1 Ordered pairs.

 
  1. For sets \(X\) and \(Y\) and elements \(x\) in \(X\) and \(y\) in \(Y\text{,}\) the ordered pair \((x,y)\) is defined by
    \begin{equation*} (x,y) = \{\{x\}, \{x,y\}\}\text{.} \end{equation*}
    For example, if \(X = \mathbb{Z}\) and \(Y = \mathbb{Z}\text{,}\) then
    \begin{equation*} (3,7) = \{\{3\}, \{3,7\}\} \end{equation*}
    whereas
    \begin{equation*} (7,3) = \{\{7\}, \{3,7\}\} \end{equation*}
    which are different. Note that the same element may be used. For example,
    \begin{equation*} (5,5) = \{\{5\}, \{5,5\}\}=\{\{5\},\{5\}\}=\{\{5\}\}\text{.} \end{equation*}
  2. In the ordered pair \((x,y)\text{,}\) we say that \(x\) is the first coordinate and \(y\) is the second coordinate. For example, in \((3,7)\) the first coordinate is 3 and the second coordinate is 7.
In Definition 6.1.11, we define a function, \(f\text{,}\) as consisting of three parts: a domain set, a codomain set, and a rule that for each element \(x\) in the domain of \(f\) uniquely determines a corresponding element \(y\) in the codomain of \(f\text{.}\) In that definition, the term “rule” was undefined. As we have seen, examples of rules include formulas, piecewise-defined formulas, or even rules described in words. We are ready to provide a formal modern definition of a rule for a function.

Definition 6.3.2 Formal definition of rule for a function.

 
  1. Given a domain set \(X\) and a codomain set \(Y\text{,}\) a rule for a function \(f\) is a set of ordered pairs \((x,y)\) where the first coordinate of each ordered pair, \(x\text{,}\) is an element of the set \(X\text{,}\) the second coordinate of each ordered pair, \(y\text{,}\) is an element of the set \(Y\text{,}\) and the set satisfies the property that each element of the domain is the first coordinate of exactly one ordered pair in the set. For example, if \(X = \{1,2,3\}\) and \(Y=\{0,1,2,3,4\}\text{,}\) then the set
    \begin{equation*} \{(1,0),(2,3),(3,3)\} \end{equation*}
    is the rule for a function because \((1,0)\) is the unique ordered pair with first coordinate 1, \((2,3)\) is the unique ordered pair with first coordinate 2, and \((3,3)\) is the unique ordered pair with first coordinate 3. On the other hand, the set \(\{(2,1), (2,3), (3,2)\}\) is not the rule for a function for two reasons. First, there is no ordered pair with 1 as the first coordinate. Second, there are two different ordered pairs with 2 as the first coordinate. Either of these reasons justifies that the set is not the rule for a function.
  2. We use function notation and write \(f(x) =y\) to indicate that the ordered pair \((x,y)\) is in the rule for \(f\text{.}\) For example, if \((2,3)\) is in the rule for a function \(f\text{,}\) then we write \(f(2)= 3\text{.}\)

Example 6.3.3 Writing the rule for a function as a set of ordered pairs.

For each function, describe the set of ordered pairs in the rule for the function.
  1. The function \(f: \{1,2,3,4,5\} \to {a,b,c,d}\) is defined by
    \begin{equation*} f(1)=a, f(2)=d, f(3)=a, f(4)=d, f(5)=c\text{.} \end{equation*}
    We saw this function in Example 6.1.20
    Solution.
    The rule is
    \begin{equation*} \{(1,a),(2,d),(3,a),(4,d),(5,c)\} \end{equation*}
  2. The function \(\fn{alt}: \mathbb{N} \to \mathbb{Z}\) is defined by \(\fn{alt}(n) = (-1)^n\text{.}\) We saw this function first in Activity 6.1.B.
    Solution.
    The rule is
    \begin{equation*} \{(0,1),(1,-1),(2,1),(3,-1),(4,1),(5,-1), \ldots\} \end{equation*}
  3. The function \(g: \mathbb{R} \to \mathbb{R}\) is defined by \(g(x) = x^2+1\text{.}\)
    Solution.
    The rule is the set of ordered pairs \((x,y)\) where \(y = g(x) = x^2+1\text{.}\) That is, the rule is the set of points on the parabola shown in Figure 6.3.4.
    Figure 6.3.4. The graph of \(y=x^2+1\text{.}\)
Let’s look at how to determine whether a set of ordered pairs is the rule for a function from a visual representation of the function.

Example 6.3.5 Determining whether a dot diagram or graph in the \(xy\)-plane is the rule for a function.

 
  1. How can we determine whether a dot diagram is the rule for a function? Give an example.
    Solution.
    Since each element of the domain is the first coordinate of one ordered pair, there must be exactly one arrow out of each element in the domain. For example, let \(X = \{1,2,3\}\) and \(Y = \{0,1,2,3,4\}\text{.}\) Consider the set of ordered pairs
    \begin{equation*} \{(1,0), (2,3), (3,3)\} \end{equation*}
    which we saw in Definition 6.3.2. This set of ordered pairs is the rule for a function. The dot diagram is drawn in Figure 6.3.6. Notice that there is exactly one arrow out the element 1 in the domain, exactly one arrow out the element 2 in the domain, and exactly one arrow out the element 3 in the domain.
    Figure 6.3.6. The dot diagram for a set of ordered pairs that is the rule for a function.
  2. Give an example of a dot diagram that is not the rule for a function.
    Solution.
    Let \(X = \{1,2,3\}\) and \(Y = \{0,1,2,3,4\}\text{.}\) Consider the set of ordered pairs
    \begin{equation*} \{(2,1), (2,3), (3,2)\} \end{equation*}
    which we saw in Definition 6.3.2. This set of ordered pairs is not the rule for a function. The dot diagram is drawn in Figure 6.3.7. Notice that there are no arrows out of the element 1 in the domain. Also, there are two arrows out of the element 2.
    Figure 6.3.7. The dot diagram for a set of ordered pairs that is not the rule for a function.
  3. How can we determine whether a graph in the \(xy\)-plane is the rule for a function from \(\mathbb{R}\) to \(\mathbb{R}\text{?}\)
    Solution.
    Each element of the domain must be the \(x\)-coordinate of a point on the graph. That is, if we draw the vertical line \(x=a\) for any real number \(a\text{,}\) it must intersect the graph exactly once (not never and not twice or more). This result is known as the vertical line test. For example, Figure 6.3.8 shows the vertical lines \(x=-3\) and \(x=1\) each cross the parabola in exactly one point.
    Figure 6.3.8. The graph of \(y=x^2+1\) with sample vertical lines drawn at \(x=-3\) and \(x=1\text{.}\)
  4. Give an example of a graph in the \(xy\)-plane that is not the rule for a function from \(\mathbb{R}\) to \(\mathbb{R}\text{.}\)
    Solution.
    Consider the graph of the equation \(x^2+y^2=1\) which is the unit circle drawn in Figure 6.3.9. There are two reasons why the unit circle is not the graph of a rule of function. First, there are two points on the circle with \(x\)-coordinate equal 0.5, namely \(\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)\) and \(\left(\frac{1}{2},^-\frac{\sqrt{3}}{2}\right)\text{.}\) (We used a little trigonometry to get those points.) Second, there are no points on the unit circle with \(x\)-coordinate equal -1.5.
    Figure 6.3.9. The graph of \(x^2+y^2=1\) with sample vertical lines drawn at \(x=0.5\) and \(x = -1.5\text{.}\)
It is your turn to work with the ordered pairs and the formal definition of a rule for a function.

Activity 6.3.A Ordered pairs and the formal definition of a rule for a function.

 
  1. Explain why \((1,2) \neq (2,1)\) using the formal definition of ordered pair, namely
    \begin{equation*} (x,y) = \{\{x\}, \{x,y\}\}\text{.} \end{equation*}
  2. Explain why the following set of ordered pairs is not the rule for a function from \(\mathbb{N}\) to \(\mathbb{N}\text{:}\)
    \begin{equation*} \{(0,1),(1,1), (1,2), (2,3), (3,3), (3,4), (4,5), (5,5), (5,6), \ldots\}\text{.} \end{equation*}
  3. Explain why the graph of \(x=y^2\text{,}\) drawn in Figure 6.3.11 is not the rule for a function from \(\mathbb{R}\) to \(\mathbb{R}\text{.}\)
    Figure 6.3.11. The graph of the equation \(x = y^2\) with sample vertical lines at \(x=-3\text{,}\) \(x=1\text{,}\) and \(x=9\text{.}\)

Subsection 6.3.B Pairings

How can we determine whether two sets are the same size? For finite sets, we can pair the elements, just as a child might count objects by pairing each object with one of their fingers. Consider the following example.

Example 6.3.12 Pairing finite sets.

Give an example of a pairing of the sets \(X=\{1,2,3,4\}\) and \(Y=\{a,b,c,d\}\text{.}\)
Solution.
A possible pairing is
\begin{equation*} 1 \leftrightarrow a, 2 \leftrightarrow b, 3 \leftrightarrow c, 4 \leftrightarrow d\text{.} \end{equation*}
Another pairing is
\begin{equation*} 1 \leftrightarrow b, 2 \leftrightarrow c, 3 \leftrightarrow d, 4 \leftrightarrow a\text{.} \end{equation*}
We verify this example satisfies the definition of a pairing in Definition 6.3.13.
In defining a pairing, we want to capture the idea that each element of the first set and each element of the second set are paired exactly once.

Definition 6.3.13 Pairing.

A pairing, \(P\text{,}\) between sets \(X\) and \(Y\) is a set of ordered pairs \((x,y)\) where the first coordinate, \(x\text{,}\) is an element of the set \(X\text{,}\) the second coordinate, \(y\text{,}\) is an element of the set \(Y\) and the set \(P\) satisfies the following properties.
  1. Each element of \(X\) is the first coordinate of exactly one ordered pair in \(P\text{.}\)
  2. Each element of \(Y\) is the second coordinate of exactly one ordered pair in \(P\text{.}\)
When we have a pairing, we write \(x \leftrightarrow y\) to denote that \((x,y)\) is in the set.
For example, in Example 6.3.12 we saw that if \(X=\{1,2,3,4\}\) and \(Y=\{a,b,c,d\}\text{,}\) then the set
\begin{equation*} \{(1,b),(2,c),(3,d),(4,a)\} \end{equation*}
is a pairing because 1 is the first coordinate of exactly one ordered pair, namely \((1,b)\text{,}\) 2 is the first coordinate of exactly one ordered pair, namely \((2,c)\text{,}\) 3 is the first coordinate of exactly one ordered pair, namely \((3,d)\text{,}\) and 4 is the first coordinate of exactly one ordered pair, namely \((4,a)\text{.}\) Similarly, \(a\) is the second coordinate of exactly one ordered pair, namely \((4,a)\text{,}\) \(b\) is the second coordinate of exactly one ordered pair, namely \((1,b)\text{,}\) \(c\) is the second coordinate of exactly one ordered pair, namely \((2,c)\text{,}\) and \(d\) is the second coordinate of exactly one ordered pair, namely \((3,d)\text{.}\)
Try pairing sets.

Activity 6.3.B Pairing sets.

 
  1. Find a pairing between the sets \(\{1,2,3,4\}\) and \(\{5,6,7,8\}\text{.}\) Can you describe the pairing using a rule in the form \(n \leftrightarrow \underline{\hspace{.5in}}\text{?}\)
  2. Find a pairing between the set \(\{1,2,3,4\}\) and itself.
  3. How many different pairings between the set \(\{1,2,3,4\}\) and itself are there? Hint: This question asks you to count.
Let’s look at an example like Activity 6.3.B.

Example 6.3.15 Counting the number of pairings between a set and itself.

How many different pairings between the set \(\{0,1,2,3,4\}\) and itself are there?
Solution.
The question “how many” suggests that we should count.
There are five elements in the set, so there are five choices for which element is paired with 0. Next, there are four elements we have not used yet, so there are four choices for which element is paired with 1. Similarly, there are three choices for which element is paired with 2 and then two choices for which element is paired with 3 and then one choice for which element is paired with 4.
Since steps multiply Theorem 2.2.3, there are \((5)(4)(3)(2)(1) = 5!\) pairings between the set \(\{0,1,2,3,4\}\) and itself.
We can pair infinite sets.

Example 6.3.16 Pairing infinite sets.

 
  1. Check that \(n \leftrightarrow 2n\) gives a pairing between \(\mathbb{Z}\) and the set of even integers \(\mathbb{E}\text{.}\)
    Solution.
    In the dot diagram drawn in Figure 6.3.17, each integer has exactly one arrow pointing out of it and each even integer has exactly one arrow pointing into it. Thus, we have a pairing.
    Figure 6.3.17. A pairing between the set of integers and the set of even integers.
  2. Explain why \(n \leftrightarrow n+1\) is not a pairing between \(\mathbb{N}\) and itself.
    Solution.
    In the dot diagram drawn in Figure 6.3.18, there is no arrow pointing into 0. That means there is no ordered pair with second coordinate 0 and so we do not have a pairing.
    Figure 6.3.18. Dot diagram of \(n \leftrightarrow n+1\) showing it is not a pairing between \(\mathbb{N}\) and itself.
  3. Explain why \(n \leftrightarrow \lfloor\frac{n}{2}\rfloor\) is not a pairing between \(\mathbb{N}\) and itself.
    Solution.
    In the dot diagram drawn in Figure 6.3.19, there are two different arrows pointing into 0. That means there are two ordered pairs with second coordinate 0, namely \((0,0)\) and \((1,0)\text{.}\)
    Figure 6.3.19. Dot diagram of \(n \leftrightarrow \left\lfloor \frac{n}{2} \right\rfloor\) showing it is not a pairing between \(\mathbb{N}\) and itself.
  4. Find a pairing of \(\mathbb{N}\) with itself that is not the identity pairing \(n \leftrightarrow n\text{.}\)
    Solution.
    In the dot diagram drawn in Figure 6.3.20, there is exactly one arrow pointing out of each natural number and exactly one arrow pointing into each natural number. Thus, we have a pairing. By the way, we can give a formula for this function
    \begin{equation*} f(n) = \left\{ \begin{array}{cc} n+1 \amp \text{ if } n \text{ is even } \\ n-1 \amp \text{ if } n \text{ is odd } \end{array} \right.\text{.} \end{equation*}
    Figure 6.3.20. A nonidentity pairing of \(\mathbb{N}\) with itself.

Subsection 6.3.C One-to-one and Onto

Every pairing defines a rule of a function because the definition of function Definition 6.3.2 includes the first property of the definition of a pairing ( Definition 6.3.13 (a)). Therefore, we can describe pairings using function notation.

Remark 6.3.21 Function notation for pairings.

For sets \(X\) and \(Y\text{,}\) a pairing, \(P\text{,}\) between \(X\) and \(Y\) defines a function \(f:X \to Y\) by \(f(x)=y\) when \((x,y)\) is in \(P\text{.}\) In this context, we write \(x \leftrightarrow f(x)\text{.}\)
In this section, we explore the second property Definition 6.3.13 (b), which the rule of a function needs to satisfy to be a pairing. For that purpose, it is helpful to separate Definition 6.3.13 (b) into two parts.

Remark 6.3.22 When the rule of a function is a pairing.

For sets \(X\) and \(Y\text{,}\) a rule, \(P\text{,}\) for a function \(f:X \to Y\) is a pairing if it satisfies the following properties.
  1. Existence: Each element of \(Y\) is the second coordinate of at least one ordered pair in \(P\text{.}\) That is, for each element \(y\) in \(Y\text{,}\) there is at least one element \(x\) in \(X\) such that \(f(x) = y\text{.}\) (Onto property)
  2. Uniqueness: Each element of \(Y\) is the second coordinate of at most one ordered pair in \(P\text{.}\) That is, or each element \(y \in Y\text{,}\) there is at most one element \(x \in X\) such that \(f(x)=y\text{.}\) (One-to-one property)
Let’s take a closer look at the existence and uniqueness properties of a pairing. We start with existence.

Definition 6.3.23 Onto.

A function \(f: X \to Y\) is onto (or surjective) if for each element \(y\) of \(Y\text{,}\) there is at least one element \(x \in X\) such that \(f(x) =y\text{.}\) That is, for each element \(y\) in \(Y\text{,}\) there is at least one ordered pair in the rule for \(f\) with second coordinate \(y\text{.}\) For example, the functions \(f\) and \(k\) defined by the dot diagrams in Figure 6.3.24 are onto, but the function \(g\) is not onto because nothing maps to \(b\) and the function \(h\) is not onto because nothing maps to \(a\text{.}\)
Figure 6.3.24. Finite functions
We can determine whether a function is onto by identifying its image.

Example 6.3.25 Onto in terms of image.

 
  1. Restate the definition of onto in terms of the image of a function.
    Solution.
    A function \(f:X \to Y\) is onto if the image of \(f\) is the entire codomain \(Y\text{.}\)
  2. Use the image to determine which of the functions in Figure 6.3.24. are onto.
    Solution.
    The image and codomain of \(f\) are \(\{a,b,c,d\}\) and so \(f\) is onto.
    The image of \(g\) is \(\{a,c,d\}\) which is not all of its codomain \(\{a,b,c,d\}\) and so \(g\) is not onto.
    The image of \(h\) is \(\{b,c,d\}\) which is not all of its codomain \(\{a,b,c,d\}\) and so \(h\) is not onto.
    Notice that the function \(k\) has the same rule and the same domain as \(g\text{,}\) but the codomain of \(k\) is \(\{a,c,d\}\) which equals the image of \(k\) and so \(k\) is onto.
Let’s look at some additional examples.

Example 6.3.26 Show functions are not onto.

Show that each function is not onto.
  1. The function \(f:\mathbb{R} \to \mathbb{R}\) is defined by \(f(x) = x^2+1\text{.}\)
    Solution.
    The function \(f\) is not onto because for any real number \(x\) we know that \(x^2 \ge 0\) and so \(f(x) \ge 1\text{.}\) For example, there is no value of \(x\) for which \(f(x) = 0\text{.}\) In the graph of \(f\text{,}\) shown in Figure 6.3.4, we can see that the lowest point on the graph is \((0,1)\) and the image of \(f\) is \([1,\infty)\) which is not all of the codomain \(\mathbb{R}\text{.}\)
  2. The function \(g: \mathbb{Z} \to \mathbb{Z}\) is defined by \(g(n) = 3n\text{.}\)
    Solution.
    The function \(g\) is not onto because the image is only multiples of 3. For example, there is no value of \(n\) for which \(g(n) = 5\text{.}\)
  3. The function \(l:\mathbb{B} \to \mathbb{Z}\) is defined by \(l(b) =\) the length of the bit string \(b\) where \(\mathbb{B}\) is the set of all bit strings.
    Solution.
    Since the length of a bit string is nonnegative, there is no bit string \(b\) with \(l(b) = -2\text{,}\) for example. Note that if we had set the codomain as \(\mathbb{N}\text{,}\) then the function would be onto.
  4. The function \(\fn{twopart}: \mathbb{N} \to \mathbb{N}\) defined by \(\fn{twopart}(n)\) is the highest power of two that divides \(n\text{.}\) We saw this function in Activity 6.2.B.
    Solution.
    The image of \(\str{twopart}\) is the set of powers of two:
    \begin{equation*} \{1,2,4,8,16,\ldots\}\text{.} \end{equation*}
    Since the image is not all of the codomain \(\mathbb{N}\text{,}\) the function \(\str{twopart}\) is not onto. As a specific counterexample we could say \(\fn{twopart}(n) = 3\) has no solution.
Since the onto property says \(\forall\)y \(\exists\)x\(~ f(x)=y\text{,}\) we can prove that a function is onto using proof formats for universally and existentially quantified statements.

Example 6.3.27 Proof that a function is onto.

Use the proof formats for universally and existentially quantified statements ( Theorem 5.2.18 and Theorem 5.2.14) to prove that the function \(h: \mathbb{R} \to \mathbb{R}\) defined by \(h(x) = 3x\) is onto.
Solution.
Proof. Let \(y\) be a real number. Consider \(x = \frac{y}{3}\) which is also a real number. Then
\begin{equation*} h(x) = 3x = 3\left(\frac{y}{3}\right) = y\text{.} \end{equation*}
Thus, there exists a real number \(x\) such that \(h(x) = y\text{,}\) namely \(x = \frac{y}{3}\text{.}\) \(\Box\)
Note that we nested Theorem 5.2.14 inside Theorem 5.2.18. For another example of a similar proof, see Activity 5.2.D in Section 5.2.
Now, let’s look at the uniqueness property of a pairing.

Definition 6.3.28 One-to-one.

A function \(f: X \to Y\) is one-to-one (or injective) if for each element \(y\) of \(Y\text{,}\) there is at most one element \(x \in X\) such that \(f(x) =y\text{.}\) That is, for each element \(y\) in \(y\text{,}\) there is at most one ordered pair in the rule for \(f\) with second coordinate \(y\text{.}\) For example, the functions \(f\) and \(h\) defined by the dot diagrams in Figure 6.3.24 are one-to-one, but the functions \(g\) and \(k\) are not one-to-one because, for example \(g(2)=c=g(4)\) and \(k(2)=c=k(4)\text{.}\)
Let’s look at some additional examples.

Example 6.3.29 Show functions are not one-to-one.

Show that each function is not one-to-one.
  1. The function \(f:\mathbb{R} \to \mathbb{R}\) is defined by \(f(x) = x^2+1\text{.}\)
    Solution.
    The function \(f\) is not one-to-one because \(f(2) = (2)^2+1 = 5\) and \(f(-2) = (-2)^2+1 =5\text{.}\)
  2. The function \(\fn{countdiv}: \mathbb{Z}^+ \to \mathbb{Z}^+\) is defined by \(\fn{countdiv}(n)=\) the number of positive divisors of \(n\text{.}\)
    Solution.
    The positive divisors of six are 1, 2, 3, and 6 and the positive divisors of 10 are 1, 2, 5, and 10. Therefore, the function \(\fn{countdiv}\) is not one-to-one because \(\fn{countdiv}(6) = 4\) and \(\fn{countdiv}(10) = 4\) (because ).
  3. The function \(l:\mathbb{B} \to \mathbb{Z}\) is defined by \(l(b) =\) the length of the bit string \(b\) where \(\mathbb{B}\) is the set of all bit strings.
    Solution.
    The function is not one-to-one because, for example, \(l(\bs{1101})=4\) and also \(l(\bs{0011})=4\text{.}\)
Try working with the definitions of one-to-one and onto.

Activity 6.3.C Four functions.

In each part of this problem you are given four functions. For each function, decide if it is onto (yes/no) and decide if it is one-to-one (yes/no).
  1. Consider the following finite functions. Hint: The graphs are drawn in Figure 6.3.31.
    • The function \(f:\{1,2,3,4\} \to \{0,1,2\}\) is defined by \(f(1) = 0, f(2) =0, f(3) = 2, f(4) = 1\text{.}\)
    • The function \(g:\{1,2,3,4\} \to \{0,1,2\}\) is defined by \(g(1) = 0, g(2) =0, g(3) = 2, g(4) = 2\text{.}\)
    • The function \(h:\{1,2,3\} \to \{0,1,2\}\) is defined by \(h(1) = 0, h(2) =2, h(3) = 1\text{.}\)
    • The function \(k:\{1,2,3\} \to \{0,1,2,3\}\) is defined by \(k(1) = 0, k(2) =3, k(3) = 2\text{.}\)
    Figure 6.3.31. Four finite functions for Activity 6.3.C.
  2. Consider the following real-valued functions. Hint: The graphs are drawn in Figure 6.3.32.
    • The function \(f: \mathbb{R} \to \mathbb{R}\) is defined by \(f(x) = x^2\text{.}\)
    • The function \(g: \mathbb{R} \to \mathbb{R}\) is defined by \(g(x) = x^3-2x+1\text{.}\)
    • The function \(h: \mathbb{R} \to \mathbb{R}\) is defined by \(h(x) = 2^x\text{.}\)
    • The function \(k: \mathbb{R} \to \mathbb{R}\) is defined by \(k(x) = x^3\text{.}\)
    Figure 6.3.32. Graphs of the real-valued functions \(f, g, h\) and \(k\) from Activity 6.3.C (b).
  3. Consider the following functions on the integers. Challenge yourself to decide without drawing the dot diagram.
    • The function \(f: \mathbb{Z} \to \mathbb{Z}\) is defined by \(f(n) = 2n\text{.}\)
    • The function \(g: \mathbb{Z} \to \mathbb{Z}\) is defined by \(g(n) = n+1\text{.}\)
    • The function \(h: \mathbb{Z} \to \mathbb{Z}\) is defined by \(h(n) = \fn{abs}(n)\text{,}\) the absolute value function.
    • The function \(k: \mathbb{Z} \to \mathbb{Z}\) is defined by
      \begin{equation*} k(n) = \left\{ \begin{array}{cl} n \amp \text{ if } n\text{ is odd } \\ \frac{n}{2} \amp \text{ if } n\text{ is even } \end{array} \right.\text{.} \end{equation*}
  4. As usual, \(\mathbb{B}\) is the set of all bit strings, \(\mathbb{B}^*\) is the set of all nonempty bit strings, and \(\lambda\) is the empty bit string. Consider the following functions on bit strings.
    • The function \(\fn{lastbit}:\mathbb{B}^* \to \mathbb{B}\) is defined by \(\fn{lastbit}(b) =\) the last bit in the bit string \(b\text{.}\)
    • The function \(\fn{append}:\mathbb{B}\to \mathbb{B}^*\) is defined by \(\fn{append}(b)=b\bs{1}\text{,}\) literally the bit string \(b\) with a \(\bs{1}\) added to the right.
    • The function \(\fn{reverse}:\mathbb{B}\to \mathbb{B}\) is defined by \(\fn{reverse}(b)=\overleftarrow{b}\text{,}\) where \(\overleftarrow{b}\) means the bit string \(b\) written in reverse order.
    • The function \(f:\mathbb{B}^*\to \mathbb{B}\) defined by
      \begin{equation*} f(b)= \left\{ \begin{array}{ll} b \amp \text{ if the last bit of the bit string } b \text{ is } \bs{0} \\ b \text{ without its last bit } \amp \text{ if the last bit of the bit string } b \text{ is } \bs{1} \end{array} \right.\text{.} \end{equation*}
A function that is onto and one-to-one has a special name.

Definition 6.3.33 Bijection.

A function \(f: X \to Y\) is a bijection if it is one-to-one and onto. Note that \(f\) is a bijection exactly when \(x \leftrightarrow f(x)\) is a pairing. For example, the function \(f\) defined by the dot diagrams in Figure 6.3.24 is a bijection. It corresponds to the pairing
\begin{equation*} 1 \leftrightarrow b, 2 \leftrightarrow c, 3 \leftrightarrow d, 4 \leftrightarrow a \end{equation*}
which we saw in Definition 6.3.13.
Let’s look at some additional examples.

Example 6.3.34 Examples of bijections.

Explain how we know each of the following functions is a bijection.
  1. The function \(f: \mathbb{N} \to \mathbb{N}\) defined by
    \begin{equation*} f(n) = \left\{ \begin{array}{cl} n+1 \amp \text{ if } n\text{ is even } \\ n-1 \amp \text{ if } n\text{ is odd } \end{array} \right.\text{.} \end{equation*}
    Solution.
    We drew the graph of this function in Figure 6.3.20. Note that each point in the bottom row has exactly one arrow pointing into it, and so the function is a bijection.
  2. The function \(h: \mathbb{R} \to \mathbb{R}\) is defined by \(h(x) = 3x\text{.}\)
    Solution.
    Given a real number \(y\text{,}\) there is exactly one real number \(x\) such that \(h(x)=y\text{.}\) As we saw in Example 6.3.27, it must be \(x = \frac{y}{3}\text{.}\)
  3. Let \(\mathbb{G}\) be the set of all graphs. The function \(\fn{comp}: \mathbb{G} \to \mathbb{G}\) defined by \(\fn{comp}(G)= \overline{G}\text{,}\) the graph-theoretic complement of \(G\text{.}\)
    Solution.
    Given a graph \(H\text{,}\) there is exactly one graph \(G\) such that \(\fn{comp}(G) = H\text{,}\) namely \(G =\overline{H}\) because \(\fn{comp}(\overline{H}) = \overline{\overline{H}}=H\text{.}\)

Subsection 6.3.D Exercises

Subsubsection Exercises for 6.3.A Ordered Pairs and the Definition of Function

1. Practice.

 
  1. Explain why \((2,5) \neq (5,2)\) using the formal definition of ordered pair Definition 6.3.1.
  2. Use the definition of ordered pairs to write \((3,3)\) as a set. Simplify your answer as much as possible.

2. Practice.

 
  1. Explain why the following set of ordered pairs is not the rule for a function from \(\{1,2,3\}\) to \(\{1,2,3\}\text{:}\)
    \begin{equation*} \{(1,1),(2,3),(2,1),(3,2)\}\text{.} \end{equation*}
  2. Explain why the following set of ordered pairs is not the rule for a function \(\mathbb{Z}\) to \(\mathbb{Z}\) (assuming the pattern continues):
    \begin{equation*} \{ \ldots, (-3,-2),(-1,0),(1,2),(3,4),(5,6),\ldots\} \end{equation*}
  3. Explain why the graph of the hyperbola \(x^2-y^2=1\text{,}\) drawn in Figure 6.3.37, is not the rule for a function from \(\mathbb{R}\) to \(\mathbb{R}\text{.}\)
Figure 6.3.37. The graph of the hyperbola \(x^2-y^2=1\) does not define a function.
Check.
  1. Hint: The rule contains both \((2,3)\) and \((2,1)\text{.}\)
  2. Hint: All the points have an odd first coordinate.
  3. Hint: One explanation is that there is no point with first coordinate 0. Another explanation would be to find \(x\)-values where there are two points on the hyperbola.

3. Understand.

 
  1. Draw all possible dot diagrams from \(\{0,1\}\) to \(\{0,1\}\) that define a function.
  2. Draw four dot diagrams from \(\{0,1\}\) to \(\{0,1\}\) that do not define a function. Note that your diagram may include at most one of each arrow \(0 \to 0\text{,}\) \(0 \to 1\text{,}\) \(1 \to 0\text{,}\) \(1 \to 1\text{.}\)
  3. Explain why there are 16 dot diagrams from \(\{0,1\}\) to \(\{0,1\}\text{,}\) again under the assumption that your diagram may include at most one of each arrow \(0 \to 0\text{,}\) \(0 \to 1\text{,}\) \(1 \to 0\text{,}\) \(1 \to 1\text{.}\)
  4. How many of those 16 dot diagrams do not define a function? Hint: Subtract.

4. Recap.

Do you know …
  1. What the formal definition of an ordered pair is?
  2. What the formal definition of a rule for a function is?
  3. How to show that a list of ordered pairs is not the rule of a function?
  4. How to show that a dot diagram or graph does not define the rule for a function.

Subsubsection Exercises for 6.3.B Pairings

5. Practice.

Find a pairing between the given sets. You may describe your using a formula or by drawing a dot diagram.
  1. \(\{0,1,2,3,4\}\) and \(\{1,2,3,4,5\}\)
  2. \(\{1,2,\ldots, 10\}\) and \(\{10,20,\ldots,100\}\)
  3. \(N\) and \(T\) where \(T\) is the nonnegative multiples of 10.
  4. \(\mathbb{N}\) and \(\mathbb{Z}^+\)
Check.
Hint: There are many correct answers to each part, but the most obvious ones have a nice formula.

6. Practice.

 
  1. Explain why \(\{(0,1),(1,2),(2,1)\}\) is not a pairing between \(\{0,1,2\}\) and \(\{1,2\}\text{.}\)
  2. Explain why \(\{(0,1),(1,2),(2,3)\}\) is not a pairing between \(\{0,1,2\}\) and \(\{0,1,2,3\}\text{.}\)
  3. Explain why there does not exist a pairing between \(\{0,1,2\}\) and \(\{1,2\}\text{.}\)
  4. Explain why there does not exist a pairing between \(\{0,1,2\}\) and \(\{0,1,2,3\}\text{.}\)
Check.
  1. One is the second coordinate of \((0,1)\) and \((2,1)\text{.}\)
  2. Zero is not the first coordinate of any ordered pair.
  3. Hint: Once you have paired zero and one, what is left to pair with two?
  4. Hint: Once you have paired zero, one, and two, what is the problem?

7. Practice.

 
  1. Explain why \(n \leftrightarrow n\) is not a pairing from \(\mathbb{N}\) to \(\mathbb{Z}\text{.}\)
  2. Explain why \(x \leftrightarrow \lfloor x \rfloor\) is not a pairing from \(\mathbb{R}\) to \(\mathbb{Z}\text{.}\)

8. Understand.

Describe a pairing between the two sets.
  1. The set of bit strings of length 10 that begin with \(\bs{0}\) and the set of bit strings of length 10 that end with \(\bs{0}\text{.}\)
  2. The set of bit strings of length 10 that begin with \(\bs{0}\) and the set of bit strings of length 10 that begin with \(\bs{1}\text{.}\)
  3. The set of bit strings of length 10 with weight three and the set of bit strings of length 10 and weight seven.
Check.
  1. Hint: One answer is \(\fn{reverse}\) from Activity 6.2.D.
  2. Hint: What is the simplest was to change a bit string that begins with \(\bs{0}\) into a bit string that begins with \(\bs{1}\text{?}\)
  3. Hint: Weight three means there are three \(\bs{1}\) s and weight seven means there are three \(\bs{0}\) s.

9. Understand.

 
  1. In the Squares and Dominoes puzzle Activity 2.1.A, we created strings of \(1 \times 1\) squares (\(\bullet\)) and \(1 \times 2\) dominoes (\(\boldsymbol{-}\)) that tiled a \(1 \times n\) grid. Describe a pairing between the set of square-domino tilings of a \(1 \times 10\) grid and the set of strings of \(\bs{1}\) s and \(\str{2}\) where the digits in the string add to 10. For example, \(\str{122212}\) is such a string because \(1+2+2+2+1+2=10\text{.}\)
  2. For the set \(\{0,1,2,3,4,5,6,7,8,9\}\text{,}\) describe a pairing between the set of 4-element subsets and the set of 6-element subsets.
  3. Describe a pairing between the set of subsets of \(\{0,1,2,3,4,5,6,7,8,9\}\) and the set of subsets of \(\{1,2,3,4,5,6,7,8,9,10\}\text{.}\)

10. Recap.

Do you know …
  1. What a pairing between sets is?
  2. How to construct pairings between sets, both finite and infinite?

11. Explore.

In each part of this problem, find a pairing between the two sets and describe your pairing using a rule of the form \(x \leftrightarrow\) (formula involving \(x\)). The letters \(a, b,c\text{,}\) and \(d\) represent positive real numbers with \(d > c\text{.}\)
  1. The intervals \((0,1)\) and \((0,b)\text{.}\)
  2. The intervals \((0,1)\) and \((a,a+1)\text{.}\)
  3. The intervals \((0,1)\) and \((a,a+b)\text{.}\)
  4. The intervals \((0,1)\) and \((c,d)\)

12. Explore.

Find a pairing between \(\mathbb{N}\) and \(\mathbb{Z}\text{.}\) You may describe your pairing using a dot diagram. Make sure the pattern is clear. Hint: Alternate between positive and negatives.

Subsubsection Exercises for 6.3.C One-to-one and Onto

13. Practice.

Each of the following functions is not onto. Give a specific counterexample to prove that the function is not onto.
  1. The function \(g: \{1,2,3,4\} \to \{1,2,3,4\}\) defined by \(g(1)=3\text{,}\) \(g(2)=2\text{,}\) \(g(3)=4\text{,}\) \(g(4)=3\text{.}\)
  2. The function \(h: \mathbb{Z} \to \mathbb{Z}\) defined by \(h(n) = 3n-1\text{.}\)
  3. The function \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = x^2\text{.}\)
Check.
  1. Hint: Identify an element of the codomain that is not the output of any value in the domain.
  2. There is no integer \(k\) with \(h(k)=1\) (because if \(3k-1=1\text{,}\) then \(k= \frac{2}{3}\) which is not an integer.)
  3. Hint: Identify a real number \(y\) such that \(x^2=y\) has no real solution.

14. Practice.

Each of the following functions is not onto. Give a specific counterexample to prove that the function is not onto.
  1. As usual, let \(\mathbb{B}\) denote the set of all bit strings. The function \(f: \mathbb{N} \to \mathbb{B}\) is defined by \(f(n)=\) the bit string consisting of \(n\) \(\bs{0}\) s followed by \(n\) \(\bs{1}\) s.
  2. Let \(\mathbb{G}_{10}\) denote the set of all graphs with ten vertices. The function \(\Delta: \mathbb{G}_{10} \to \mathbb{N}\) is defined by \(\Delta(G)\) is the maximum degree of any vertex in \(G\text{.}\)
  3. The function \(\fn{gplt}: \mathbb{Z}^+ \to \mathbb{N}\) defined by
    \begin{equation*} \fn{gplt}(n) = \left\{ \begin{array}{cl} 0 \amp \text{ if } n=1 \\ \text{ the largest prime less than or equal to } n \amp \text{ if } n\ge 2 \end{array} \right.\text{.} \end{equation*}
Check.
  1. Hint: All values of \(f(n)\) are bit strings that begin with \(\bs{0}\text{.}\)
  2. Hint: What is the biggest degree a vertex in a graph \(G\) could have when \(G\) has ten vertices?
  3. Hint: All positive values of \(\fn{gplt}\) are primes.

15. Practice.

Each of the following functions is not one-to-one. Give a specific counterexample to prove that the function is not one-to-one.
  1. The function \(g: \{1,2,3,4\} \to \{1,2,3,4\}\) defined by \(g(1)=3\text{,}\) \(g(2)=2\text{,}\) \(g(3)=4\text{,}\) \(g(4)=3\text{.}\)
  2. The function \(h: \mathbb{N} \to \mathbb{N}\) defined by \(h(n) =\lceil \frac{n}{2} \rceil\text{.}\)
  3. The function \(f: \mathbb{R} \to \mathbb{R}\) defined by \(f(x) = x^2\text{.}\)
Check.
  1. \(f(1) = 3 = f(4)\text{.}\)
  2. Hint: Evaluate \(g(0), g(1), g(2)\text{,}\) and so on until you hit a repeat.
  3. Hint: Your answer should include a negative integer.

16. Practice.

Each of the following functions is not one-to-one. Give a specific counterexample to prove that the function is not one-to-one.
  1. As usual, let \(\mathbb{B}\) denote the set of all bit strings. The function \(\fn{runzero}: \mathbb{B} \to \mathbb{N}\) is defined by \(\fn{runzero}(b) =\) the longest number of consecutive \(\bs{0}\) s in the bit string \(b\text{.}\)
  2. Let \(\mathbb{G}_{10}\) denote the set of all graphs with ten vertices. The function \(\chi: \mathbb{G}_{10} \to \mathbb{N}\) is defined by \(\chi(G)\) is the chromatic number of the graph \(G\text{.}\)
  3. Euler’s phi function \(\varphi: \mathbb{Z}^+ \to \mathbb{Z}^+\) is defined by \(\varphi(n)=\) the number of integers between 1 and \(n\) that are coprime to \(n\text{.}\)
Check.
  1. Hint: Find two bit strings that have the same longest number of consecutive \(\bs{0}\) s.
  2. Hint: Find two graphs with 10 vertices that each have chromatic number two. Some graphs with chromatic number two are cycles, paths, and stars.
  3. Hint: Look at the table in Activity 4.5.C.

17. Understand.

For each of the finite functions given, decide whether the function is onto (yes/no) and whether the function is one-to-one (yes/no). No justification required for “yes” but give a counterexample or brief explanation when “no”.
  1. \(f: \{1, 2, 3, 4\} \to \{a, b, c\}\) defined by \(f(1) = a, f(2) = b, f(3) = a, f(4) = c\)
  2. \(g: \{1, 2, 3, 4\} \to \{a, b, c, d,e\}\) defined by \(g(1) = a, g(2) = b, g(3) = e, g(4) = c\)
  3. \(h: \{1, 2, 3, 4\} \to \{1,2,3,4\}\) defined by \(h(1) = 2, h(2) = 3, h(3) = 4, h(4) = 1\)
  4. \(k: \{1, 2, 3, 4\} \to \{1,2,3,4\}\) defined by \(k(1) = 3, k(2) = 3, k(3) = 3, k(4) =3\)
Check.
  1. Hint: The answer is yes/no. Explain why the function is not one-to-one.
  2. Hint: The answer is no/yes. Explain why the functions is not onto.
  3. Hint: The answer has not been used yet.
  4. Hint: The answer has not been used yet.

18. Understand.

For each function decide if it is one-to-one, onto, both, or neither. Briefly explain your reasoning.
  1. Let \(X\) be a set with 10 elements. The identity function \(i: X \to X\) is defined by \(i(x) = x\text{.}\)
  2. Let \(X\) be a set with 10 elements, one of which is \(c\text{.}\) The constant function \(f:X \to X\) is defined by \(f(x) = c\text{.}\)

19. Understand.

Consider the closely related functions \(g: \mathbb{Z} \to \mathbb{Z}\) defined by \(g(n) = n+2\) and \(h: \mathbb{N} \to \mathbb{N}\) defined by \(h(n) = n+2\)
  1. Describe the image of \(g\text{.}\) Is \(g\) onto?
  2. Describe the image of \(h\) Is \(h\) onto?

20. Understand.

Recall from Definition 4.3.7 that the integers mod \(n\text{,}\) \(\mathbb{Z}_n\text{,}\) is the set \(\{0,1,2,\ldots, n-1\}\) with addition and multiplication defined by
\begin{equation*} a \oplus b = a + b \text{ (mod } n) \text{ and } a \otimes b = ab \text{ (mod } n) \end{equation*}
  1. Consider the function \(f: \mathbb{Z} \to \mathbb{Z}_{10}\) defined by \(f(a) = a \text{ mod } 10\text{.}\) Is \(f\) one-to-one? Is \(f\) onto? Explain briefly.
  2. Consider the function \(g: \mathbb{Z}_{10} \to \mathbb{Z}_{10}\) defined by \(g(a) = 3 \otimes a\text{.}\) Is \(g\) one-to-one? Is \(g\) onto? Explain briefly.
  3. Consider the function \(h: \mathbb{Z}_{10} \to \mathbb{Z}_{10}\) defined by \(h(a) = 2 \otimes a\text{.}\) Is \(h\) one-to-one? Is \(h\) onto? Explain briefly.
Check.
  1. Hint: The answer is no/yes. Explain why the function is not one-to-one.
  2. Hint: Make a table showing \(g(a)\) for \(a = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\text{.}\)
  3. Hint: Make a table showing \(h(a)\) for \(a = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9\text{.}\)

21. Understand.

Prove each function is onto by listing the elements of the codomain and for each element of the codomain, identify an example of an element of the domain that maps to it.
  1. The function \(f: \{0,1,2,3,4,5\} \to \{\text{ even } , \text{ odd } \}\) defined by
    \begin{equation*} f(n) = \left\{ \begin{array}{cl} \text{ even } \amp \text{ if } n\text{ is even } \\ \text{ odd } \amp \text{ if } n\text{ is odd } \end{array} \right.\text{.} \end{equation*}
  2. Let \(\mathbb{G}_4\) denote the set of all graphs with four vertices. The function \(\fn{cleaf}: \mathbb{G}_4 \to \{0,1,2,3,4\}\) is defined by \(\fn{cleaf}(G)\) is the number of leaves (degree 1 vertices) in the graph \(G\text{.}\) Yes, draw five graphs.
Check.
  1. \(f(0)=\) even and \(f(1)=\) odd.
  2. Hint: Look at the path \(P_4\text{,}\) the star \(K_{1,4}\text{,}\) the cycle \(C_4\text{,}\) the cycle \(C_3\) with an additional vertex and edge, and a tree with longest path of length three edges.

22. Understand.

Prove that each function is onto by copying and editing the proof in Example 6.3.27.
  1. The function \(g: \mathbb{R} \to \mathbb{R}\) defined by \(g(x) = 2x + 3\text{.}\)
  2. The function \(g: \mathbb{Z} \to \mathbb{Z}\) defined by \(g(n) = n-1\text{.}\)
Check.
  1. Hint: If \(2x+3 = y\text{,}\) then solve for \(x\text{.}\)
  2. Hint: Your proof should mention integers (not real numbers).

23. Understand.

As usual, \(\mathbb{B}\) is the set of all bit strings. The function \(g: \mathbb{B}^* \to \mathbb{B}^*\) is defined by \(g(b)\) is the bit string \(b\) with its first bit changed from \(\bs{0}\) to \(\bs{1}\) or vice versa. For example, \(g(\bs{10111}) = \bs{00111}\) and \(g(\bs{010}) = \bs{110}\text{.}\) Explain how we know that \(g\) is a bijection.

24. Recap.

Do you know …
  1. What it means for a function to be onto?
  2. How to show that a function is not onto?
  3. How to prove that a function is onto?
  4. What it means for a function to be one-to-one?
  5. How to show that a function is not one-to-one?
  6. Which two properties a function needs to have to be a bijection?

25. Explore.

In this exercise, we introduce the horizontal line test. Consider a function \(f: \mathbb{R} \to \mathbb{R}\text{.}\)
  1. Suppose there is a horizontal line (\(y=t\)) that intersect the graph of \(f\) in two (or more) points. What does that tell you about the function \(f\text{?}\)
  2. Suppose there is a horizontal line (\(y=t\)) that does not intersect the graph of \(f\text{.}\) What does that tell you about the function \(f\text{?}\)
  3. Suppose every horizontal line (\(y=t\)) intersects the graph of \(f\) in exactly one point. What does that tell you about the function \(f\text{?}\)
Check.
Hint: The answers in some order are \(f\) is a bijection, \(f\) is not onto, and \(f\) is not one-to-one.

26. Explore.

 
  1. List all of the bijections \(f: \{1,2,3\} \to \{1,2,3\}\) by drawing dot diagram for each.
  2. How many bijections \(f: \{1,2,3 \ldots,n\} \to \{1,2,3 \ldots,n\}\) are there? Explain how you counted.

27. Explore.

 
  1. How many one-to-one functions \(f:\{1,2\} \to \{1,2,3,4\}\) are there? Explain how to count. Hint: In Step 1 decide on the value of \(f(1)\) and in Step 2 decide on the value of \(f(2)\text{.}\)
  2. How many one-to-one functions \(f:\{1,2\} \to \{1,2,3 \ldots,n\}\) are there?
  3. How many one-to-one functions \(f:\{1,2,3\} \to \{1,2,3 \ldots,n\}\) are there?
Check.
  1. Hint: The answer is 12.
  2. Hint: Use the same two steps as in 27.(a). Your answer should involve \(n\text{.}\)
  3. Hint: Use three steps.

28. Explore.

 
  1. How many one-to-one functions
    \begin{equation*} f:\{1,2, \ldots, k\} \to \{1,2,3 \ldots,n\} \end{equation*}
    are there, assuming \(k \le n\text{?}\) Explain briefly.
  2. What happens if \(k > n\text{?}\) Explain briefly.

29. Explore.

The function \(\fn{countdiv}: \mathbb{Z}^+ \to \mathbb{Z}^+\) is defined by \(\fn{countdiv}(n)=\) the number of positive divisors of \(n\text{.}\) Prove \(\fn{countdiv}\) is onto. Hint: given \(m \in \mathbb{Z}^+\text{,}\) use prime factorization as in Subsection 4.4.C to construct an integer with exactly \(m\) divisors.

30. Explore.

Give an example of a function \(f: \mathbb{N} \to \mathbb{N}\) as described. Be sure the domain and codomain is \(\mathbb{N}\text{.}\) You may give a rule for the function, including possibly a piecewise-defined function, or you may draw an infinite dot diagram (as long at the pattern is clear.)
  1. One-to-one, but not onto.
  2. Onto, but not one-to-one.
  3. Neither one-to-one nor onto.
  4. A bijection, but not the identity function and not the example we used in Example 6.3.34.
Check.
  1. Hint: Look at Example 6.3.16.
  2. Hint: Look at Example 6.3.16.
  3. Hint: Look at Example 6.3.26.
  4. Hint: In that example, we used the cases of even (\(n\) mod 2 = 0) and odd (\(n\) mod 2 = 1). Try cases based on mod 3 instead.
PrevTopNext