10.2: Properties of Functions
- Page ID
- 83452
a function whose image is all of its codomain — that is, every element of the codomain is an output for the function;
a surjective function
synonym for surjective
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{.}\)
- 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{.}\))
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{.}\)
a function for which two different inputs never produce the same output
an injective function
synonym for injection
synonym for injective
function \(f\) is injective
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{.}\)
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{.}\)
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{.}\)
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.
a function that is both injective and surjective
an bijective function
synonym for bijection
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.
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.
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{.}\)