Constructing and Writing Mathematical Proofs: A Guide for Mathematics Students

(a) 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\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)\ge 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{.}$

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

Let $T=\{y\in \mathbb{R}|y\ge 1\}\text{,}$ and define $F:\mathbb{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)\ge 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\ge 1$ and hence that$y-1\ge 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 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 ${\mathbb{Z}}^{\ast }=\{x\in \mathbb{Z}|x\ge 0\}=\mathbb{N}\cup \{0\}\text{.}$ Define $g:{\mathbb{Z}}^{\ast }\to \mathbb{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{.}$

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 $\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\text{.}$ So we assume that there exists an $x\in \mathbb{Z}$ with $g(x)=3\text{.}$ Then

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

Since $s,t\in {\mathbb{Z}}^{\ast }\text{,}$ we know that $s\ge 0$ and $t\ge 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.