Skip to main content

Section 8.3 One-to-one and Onto Functions

There are a few properties that certain functions have which are important enough to be given names.

Subsection 8.3.1 Oneo-to-one and Onto Functions

Let \(f: X \rightarrow Y\) be a function.

Definition 8.3.1.

A function \(f\) is injective (or is one-to-one, or \(f\) is an injection) if for all \(x_1, x_2 \in A\text{,}\) if \(f(x_1) = f(x_2)\text{,}\) then \(x_1 = x_2\text{.}\)

Equivalently, for all \(x_1, x_2 \in X\text{,}\) if \(x_1 \neq x_2\text{,}\) then \(f(x_1) \neq f(x_2)\text{.}\) In other words, if the inputs are different, then the outputs will be different.

Definition 8.3.2.

Let \(f: X \rightarrow Y\) be a function. \(f\) is surjective (or onto, or \(f\) is a surjection) if for all \(y \in Y\text{,}\) there exists \(x \in X\) such that \(f(x) = y\text{.}\)

In other words, \(R(f) = Y\text{.}\) Or, \(f\) is not surjective if there exists \(y \in Y\) such that for all \(x \in X\text{,}\) \(f(x) \neq y\text{.}\)

Subsection 8.3.2 One-to-one Correspondence

Definition 8.3.3.

Let \(f: X \rightarrow Y\) be a function. \(f\) is a one-to-one correspondence if \(f\) is injective and surjective.

Each element in \(y\) is mapped from exactly 1 element in \(X\text{,}\) and each element in \(X\) maps to exactly one element in \(y\text{.}\) In other words,

\begin{gather*} \forall x \in X, \exists y \in Y \text{ such that } f(x) = y\\ \forall y \in Y, \exists x \in X \text{ such that } f(x) = y \end{gather*}

In this way, for a one-to-one correspondence function \(f\text{,}\) given an element of \(X\text{,}\) we can completely determine its corresponding element \(y\text{,}\) and vise versa.

Subsection 8.3.3 Proving a Function is Onto

To prove a function \(f: X \rightarrow Y\) is surjective, consider an arbitrary element of the codomain \(y \in Y\text{.}\) Then, the goal is to find an element \(x \in X\) such that \(f(x) = y\text{.}\) Here, \(y\) is “given” and we need to solve for \(x\text{.}\) Often, this involves solving the equation \(f(x) = y\) for \(x\) in terms of \(y\text{.}\)

Let \(f: \mathbb{R} \rightarrow \mathbb{R}\text{,}\) \(f(x) = 7x - 3\text{.}\) Then, \(f\) is injective and surjective.

  • Let \(x_1, x_2 \in \mathbb{R}\) with \(f(x_1) = f(x_2)\text{.}\) Then, \(7x_1 - 3 = 7x_2 - 3\text{,}\) and so \(x_1 = x_2\text{.}\) Thus, \(f\) is injective.

  • Let \(y \in \mathbb{R}\text{,}\) so that \(x = \frac{y+3}{7} \in \mathbb{R}\text{.}\) Then, \(f(x) = 7(x+3)/7 - 3 = y\text{.}\) Thus, \(f\) is surjective.

Let \(f: \mathbb{R} \rightarrow \mathbb{R}\text{,}\) \(f(x) = x^2\text{.}\) Then, \(f\) is not injective and not surjective.

  • Let \(x_1 = 1, x_2 = -1\text{.}\) Then, \(f(x_1) = f(1) = 1^2 = (-1)^2 = f(-1) = f(x_2)\text{.}\) Thus, \(f\) is injective.

  • Let \(y = -1, x \in \mathbb{R}\text{.}\) Then, \(f(x) = x^2 \geq 0\text{,}\) so \(f(x) \neq -1\text{.}\)

Let \(f: \mathbb{R} \setminus \set{2} \rightarrow \mathbb{R} \setminus \set{5}\text{,}\) \(f(x) = \frac{5x+1}{x-2}\text{.}\) Then, \(f\) is bijective.

We will prove that \(f\) is injective and surjective.

  • Let \(x_1, x_2 \in \mathbb{R} \setminus \set{2}\) with \(f(x_1) = f(x_2)\text{.}\) Then,

    \begin{align*} \frac{5x_1 + 1}{x_1 - 2} \amp = \frac{5x_2 + 1}{x_2 - 2}\\ (5x_1 + 1)(x_2 - 2) \amp = (x_1 - 2)(5x_2 + 1)\\ 5x_1x_2 - 10x_1 + x_2 - 2 \amp = 5x_1x_2 + x_1 - 10x_2 - 2 \\ 11x_1 \amp = 11x_2\\ x_1 \amp = x_2 \end{align*}
    Thus, \(f\) is injective.

  • Let \(y \in \mathbb{R} \setminus \set{5}\text{,}\) \(x = \frac{2y + 1}{y - 5} = 2 + \frac{11}{y-5}\text{.}\) Then, \(x \neq 2\text{.}\) Also, \(y \neq 5\text{.}\) Thus, \(x \in \mathbb{R} \setminus \set{2}\text{.}\) Thus,

    \begin{equation*} f(x) = \frac{5\brac{\frac{2y + 1}{y - 5}} + 1}{\frac{2y + 1}{y - 5} - 2} = \frac{5(2y+1) + y - 5}{2y + 1 - 2(y - 5)} = \frac{11y}{11} = y \end{equation*}
    Thus, \(f\) is surjective.

Subsection 8.3.4 Cardinality and Function Properties

For \(f: X \rightarrow Y\) to be a bijection, we need to map each of the \(n\) elements in \(X\) to each of the \(n\) elements in \(Y\text{,}\) such that no two elements of \(X\) are mapped to the same element in \(y\text{.}\) In other words, we need to create \(n\) pairs of elements \((x,y)\) where \(x \in X\) and \(y \in Y\text{,}\) using no elements more than once. For the first element of \(X\text{,}\) there are \(n\) elements in \(y\) that it can be paired with. For the second elements of \(X\text{,}\) there are now \(n - 1\) elements in \(y\) it can be paired with, because we cannot re-use the element already chosen. Continuing in this way, for the 2nd last element of \(X\text{,}\) there are 2 elements in \(Y\) it can be paired with. For the last element of \(X\text{,}\) there is only 1 element in \(Y\) it can be paired with. In this way, to describe \(f: X \rightarrow Y\text{,}\) the number of ways to do it is,

\begin{equation*} n \cdot (n - 1) \cdots 2 \cdot 1 = n! \end{equation*}

Subsection 8.3.5 Remarks

In more advanced math, one-to-one functions are called injective, onto functions are called surjective, and a one-to-one correspondence is called bijective. Then, the noun equivalent for these terms are injection, surjection, and bijection, respectively.