Functions

Doug Baldwin

Spring 2021

This example illustrates what formal proofs that a function is an injection, surjection, or bijection might look like. All the proofs concern the function

\begin{equation} \label {demoEqn} f(x,y) = (x+y,x-y) \end{equation}

We begin by showing that \(f\) is an injection and a surjection.

Theorem 1. The function \(f\) defined by (1) is an injection.

Proof. We will prove that \(f\) is an injection by showing that \(f(a,b) = f(c,d)\) implies that \(a=b\) and \(c=d\). From the definition of \(f\), \(f(a,b) = f(c,d)\) implies the following system of equations.

\begin{align*} a+b &= c+d \\ a-b &= c-d \end{align*}

Adding these equations yields

\begin{equation*} 2a = 2c \end{equation*}
from which we conclude that \(a= c\). Substituting this back into the first equation then produces
\begin{equation*} a + b = a + d \end{equation*}
indicating that \(b = d\). We have now shown that if \(f(a,b) = f(c,d)\) it must be true that \(a=b\) and \(c=d\), which in turn establishes that \(f\) is an injection. □

Theorem 2. Function \(f\) defined by (1) is a surjection.

Proof. We show that \(f\) is a surjection by showing that for any pair of real numbers, \((x,y)\), there is another pair \((a,b)\) such that \(f(a,b) = (x,y)\). From the definition of \(f\), this would require

\begin{align*} a + b &= x \\ a - b &= y \end{align*}

We can rewrite these equations as

\begin{align*} a &= x - b \\ a &= y + b \end{align*}

so that \(x - b = y + b\). We can then isolate \(b\) on one side of this equation:

\begin{align*} x - b &= y + b \\ x - y &= 2b \\ b &= \frac {x-y}{2} \end{align*}

Now we plug this definition of \(b\) back into one of the equations for \(a\) to get

\begin{align*} a &= x - b \\ &= x - \frac {x-y}{2} \\ &= \frac {2x - x + y}{2} \\ &= \frac {x+y}{2} \end{align*}

We finish the proof by verifying that for any pair of real numbers \((x,y)\), \(f(\tfrac {x+y}{2},\tfrac {x-y}{2}) = (x,y)\):

\begin{align*} f\left ( \frac {x+y}{2}, \frac {x-y}{2} \right ) &= \left ( \frac {x+y}{2} + \frac {x-y}{2}, \frac {x+y}{2} - \frac {x-y}{2} \right ) \\ &= \left ( \frac {x+y + x - y}{2}, \frac {x+y - x + y}{2} \right ) \\ &= \left ( \frac {2x}{2}, \frac {2y}{2} \right ) \\ &= (x,y) \end{align*}

We have now shown that every pair \((x,y)\) in the codomain of function \(f\) has a preimage under \(f\), and so \(f\) is a surjection. □

Finally, being an injection and a surjection implies that \(f\) is a bijection:

Corollary 1. Function \(f\) defined by (1) is a bijection.

Proof. That \(f\) is a bijection follows immediately from it being an injection and a surjection. □