10.2: Properties of Functions

Definition: Surjective Function

a function whose image is all of its codomain — that is, every element of the codomain is an output for the function;

Definition: Surjective Function

a surjective function

Definition: Onto

synonym for surjective

Definition: $f: A \twoheadrightarrow B$

function $f$ is surjective

A function $f: A \rightarrow B$ is surjective if $f(A) = B\text{.}$ Since we have $f(A) \subseteq B$ by definition of image, to show that a function is surjective we only need to show $f(A) \supseteq B\text{.}$

Test $\PageIndex{1}$: Surjective function.

• Function $f: A \rightarrow B$ is surjective if $B \subseteq f(A)\text{.}$ That is, $f$ is surjective if for every element $b \in B\text{,}$ there exists at least one element $a \in A$ such that $f(a) = b\text{.}$
• Function $f: A \rightarrow B$ is not surjective if there exists at least one element $b \in B$ for which there is no element $a \in A$ satisfying $f(a) = b\text{.}$ (Equivalently, there exists $b \in B$ for which every $a \in A$ satisifes $f(a) \neq b\text{.}$)

​​​​​​

Example $\PageIndex{1}$

Show that, of the following functions, $f$ is surjective and $g$ is not.

$$\begin{align*} f \colon \mathbb{Z} & \to \mathbb{N} & g \colon \mathbb{Z} & \to \mathbb{Q} \\ m & \mapsto \vert m \vert & m & \mapsto m/2 \end{align*}$$

Solution

Show that $f$ is surjective.

Consider an arbitrary element $n$ of the codomain $\mathbb{N}\text{.}$ Since $\mathbb{N} \subseteq \mathbb{Z}\text{,}$ $n$ is also an element of the domain. In particular, $f(n) = n\text{,}$ since $n\ge 0\text{.}$ Therefore, as an element of the codomain, we have $n\in f(\mathbb{Z})\text{.}$

Show that $g$ is not surjective.

We need to find a specific example of a rational number that is not an output for $g\text{.}$ For this, we could use $1/3\text{,}$ since there is no integer such that $m/2 = 1/3\text{.}$

Definition: Injective Function

a function for which two different inputs never produce the same output

Definition: Injection

an injective function

Definition: Embedding

synonym for injection

Definition: One-to-one

synonym for injective

Definition: $f: A \hookrightarrow B$

function $f$ is injective

Test $\PageIndex{2}$: Injective Function

Function $f: A \rightarrow B$ is injective if the following conditional always holds for elements $a_1,a_2 \in A\text{:}$

if $a_1 \ne a_2$ then $f(a_1) \ne f(a_2)\text{.}$

Alternatively, one can establish that the contrapositive of the above conditional always holds for elements $a_1,a_2 \in A\text{:}$

if $f(a_1) = f(a_2)$ then $a_1 = a_2\text{.}$

Function $f: A \rightarrow B$ is not injective if there exists at least one pair of elements $a_1,a_2 \in A$ with $a_1 \ne a_2$ but $f(a_1) = f(a_2)\text{.}$

Example $\PageIndex{2}$: Demonstrating that a function is not injective.

The function $f: \mathbb{R} \rightarrow \mathbb{R} \text{,}$ $f(x) = x^2\text{,}$ is not injective, since $f$ has repeated outputs. For example, $f(-1) = f(1)\text{.}$ And in fact, $f(-x) = f(x)$ for every $x\in \mathbb{R}\text{.}$

Example $\PageIndex{3}$: Demonstrating that a function is injective.

Verify that the function $f: \mathbb{N} \rightarrow \mathbb{N} \text{,}$ $f(n) = 2n+1\text{,}$ is injective.

Solution

Using the contrapositive version of the Injective Function Test, suppose domain elements $n_1,n_2 \in \mathbb{N}$ satisfy $f(n_1) = f(n_2)\text{.}$ Then using the formula defining the input-output rule for $f\text{,}$ we have

$$\begin{equation*} 2 n_1 + 1 = 2 n_2 + 1 \text{,} \end{equation*}$$
which reduces to $n_1 = n_2\text{.}$

An injection $f: A \hookrightarrow B$ gives us a way of thinking of $A$ as a subset of $B\text{,}$ by considering $f(A) \subseteq B\text{.}$

Example $\PageIndex{4}$: Turning letters into numbers.

Let $\Sigma = \{a, b, \ldots, z\} \text{,}$ and define $\varphi: \Sigma \rightarrow \mathbb{N}$ by the following table.

$\sigma$	$a$	$b$	$c$	$\cdots$	$z$
$\varphi(\sigma)$	$1$	$2$	$3$	$\cdots$	$26$

Then $f$ embeds $\Sigma$ into $\mathbb{N}$ in a familiar way, and lets us think of letters as numbers.

Definition: Bijective Function

a function that is both injective and surjective

Definition: Bijection

an bijective function

Definition: One-to-one Correspondence

synonym for bijection

Example $\PageIndex{5}$

Function $f: \mathbb{R} \rightarrow \mathbb{R} \text{,}$ $f(x) = x^3$ is bijective.

A bijection $f: A \rightarrow B$ allows us to think of $A$ and $B$ as essentially the same sets.

Example $\PageIndex{6}$: Identifying letters with numbers.

Consider again $f: \Sigma \rightarrow \mathbb{N}$ from Example $\PageIndex{4}$. If we write $B = f(\Sigma) = \{1,2,3,\ldots ,26\}\text{,}$ then really we could think of the function as being defined $f: \Sigma \rightarrow B\text{.}$ This version of $f$ is bijective, and allows us to identify each letter with a corresponding number:

$$\begin{align*} a & \leftrightarrow 1, & b & \leftrightarrow 2, & c & \leftrightarrow 3, & & \ldots , & z & \leftrightarrow 26. \end{align*}$$
In this way, we can think of $\Sigma$ and $B$ as essentially the same set.

Example $\PageIndex{7}$: Recognizing bijections.

Which of the following functions are bijections?

$$\begin{align*} f \colon \mathbb{Z} & \to \mathbb{Z}, & g \colon \mathbb{Z} & \to \mathbb{N}, & h \colon \mathbb{Z} & \to \mathbb{Z},\\ m &\mapsto 2m, & m & \mapsto \vert m \vert, & m & \mapsto -m. \end{align*}$$

Solution.

Is $f$ bijective?.

No, $f$ is not bijective because it is not surjective. For example, there is no $m\in \mathbb{Z}$ such that $f(m) = 1\text{.}$

Is $g$ bijective?.

No, $g$ is not bijective because it is not injective. For example, $g(-1) = g(1)\text{.}$

Is $h$ bijective?.

Yes, $h$ is bijective. It is injective because if $m_1 \ne m_2$ then $-m_1 \ne -m_2\text{.}$ And it is surjective because for $n\in \mathbb{Z}\text{,}$ we can realize $n$ as an output $n = h(m)$ by setting $m = -n\text{.}$

Checkpoint $\PageIndex{1}$: Bijections of counting sets.

For $m \in \mathbb{N}$ write

$$\begin{equation*} \mathbb{N}_{<m} = \{n \in \mathbb{N}\rightarrow n \lt m = \{ 0,\, 1,\, \ldots ,\, m-1\} \text{.} \end{equation*}$$
Prove that there exists a bijection $\mathbb{N}_{<l} \to \mathbb{N}_{<m}$ if and only if $\ell = m\text{.}$