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