Skip to main content

Section 7.2 Some Examples and Proofs

Many of us have probably heard in precalculus and calculus courses that a linear function is a bijection. We prove this in the following proposition, but notice how careful we are with stating the domain and codomain of the function.

Proof.

We let \(f(x) = mx + b\) be a nonzero real number and let \(b\) be a real number and define \(f: \R \to \R\) by \(f(x) = mx + b\) for all \(x\) in \(\R\text{.}\) We will prove that \(f\) is a bijection by proving it is both an injection and a surjection.

To prove that \(f\) is an injection, we let \(x_1\) and \(x_2\) be real numbers (hence, in the domain of \(f\)) and assume that \(f (x_1) = f(x_2)\text{.}\) This means that \(mx_1 + b = mx_2 + b\text{.}\) We can then subtract \(b\) from both sides of this equation and then divide both sides by \(m\) since \(m \ne 0\) as follows:

\begin{align*} mx_1 + b \amp = mx_2 + b\\ mx_1 \amp = mx_2\\ x_1 \amp = x_2 \end{align*}

So we have proved that for all \(x_1, x_2 \in \R\text{,}\) if \(f (x_1) = f(x_2)\text{,}\) then \(x_1 = x_2\text{,}\) and hence, \(f\) is an injection.

To prove that \(f\) is a surjection, we choose a real number \(y\) in the codomain of \(f\) . We need to prove that there exists an \(x \in \R\) such that \(f (x) = y\text{.}\) Working backward, we see that if \(mx + b = y\text{,}\) then \(x = \frac{y - b}{m}\) (since \(m \ne 0\)). We see that \(x \in \R\) (the domain of \(f\) ) since the real numbers are closed under subtraction and division by nonzero real numbers. This is done as follows:

\begin{align*} f(x) \amp = f \left( \frac{y - b}{m} \right)\\ \amp = m \left( \frac{y - b}{m} \right) + b\\ \amp = ( y - b) + b\\ \amp = b \end{align*}

This proves that for each \(y \in \R\text{,}\) there exists an \(x \in \R\) such that \(f(x) = y\text{,}\) and hence, \(f\) is a surjection.

Since we have proved that \(f\) is both an injection and a surjection, we have proved that \(f\) is a bijection.

We will now discuss some examples of functions that 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 an injection or a surjection.

Example 7.2. The Importance of the Domain and Codomain.

Each of the following functions will have the same rule for computing the outputs corresponding to a given input. However, they will have different domains or different codomains.

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

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

\begin{equation*} f(2 = 5) \text{ and } f(-2) = 5 \end{equation*}

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 \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{.}\)

(b) A Function that Is Not an Injection but Is a Surjection.

Let \(T = \{ y \in \R | y \geq 1 \}\text{,}\) and define \(F: \R \to T\) by \(F(x) = x^2 + 1\text{.}\) As in TaskĀ 7.2.a, 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 \(R\) onto \(T\text{?}\) As in TaskĀ 7.2.a, we do know that \(F (x) \geq 1\) for all \(x \in \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 \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 \R\) such that

\begin{align*} F(x) \amp = y \text{, or}\\ x^2 + 1 \amp = y\text{.} \end{align*}

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

\begin{align*} x^2 \amp = y - 1\\ x = \sqrt{y - 1} \amp \text{ or } x = - \sqrt{y - 1} \end{align*}

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 \R\text{.}\) Hence, if we use \(x = \sqrt{y - 1}\text{,}\) then \(x \in \R\text{,}\) and

\begin{align*} F(x) \amp = F \left( \sqrt{y - 1} \right)\\ \amp = \left( \sqrt{y - 1} \right)^2 + 1\\ \amp = (y - 1) + 1\\ \amp = y \end{align*}

This proves that \(F\) is a surjection since we have shown that for all \(y \in T\text{,}\) there exists an \(x \in \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 \R\) such that \(F(x) = y\text{.}\)

An Important Lesson. In TaskĀ 7.2.a and TaskĀ 7.2.b, 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.

(c) A Function that Is an Injection but Is Not a Surjection.

Let \(\Z ^* = \{ x \in \Z | x \geq 0 \} = \N \cup \{ 0 \}\text{.}\) Define \(g: \Z ^* \to \N\) by \(g(x) = x^2 + 1\text{.}\) (Notice that this is the same formula used in TaskĀ 7.2.a and TaskĀ 7.2.b.) 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 \(\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 \((\Z ^* )\) such that \(g(x) = 3\text{.}\) So we assume that there exists an \(x \in \Z\) with \(g(x) = 3\text{.}\) Then

\begin{align*} x^2 + 1 \amp = 3\\ x^2 \amp = 2\\ x \amp = \pm \sqrt{2} \end{align*}

But this is not possible since \(\sqrt{2} \not \in \Z ^*\text{.}\) Therefore, there is no \(x \in \Z ^*\) with \(g(x) = 3\text{.}\) This means that for every \(x \in \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

\begin{align*} s^2 + 1 \amp = t^2 + 1\\ s^2 \amp = t^2\text{.} \end{align*}

Since \(s, t \in \Z ^*\text{,}\) we know that \(s \geq 0\) 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 TaskĀ 7.2.a and TaskĀ 7.2.b are not injections but the function in TaskĀ 7.2.c 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.