Section 10.2 Properties of functions
- surjective function
a function whose image is all of its codomain — that is, every element of the codomain is an output for the function;
- surjection
a surjective function
- onto
synonym for surjective
- \(\sfuncdef{f}{A}{B}\)
function \(f\) is surjective
A function \(\funcdef{f}{A}{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 10.2.1. Surjective function.
Function \(\funcdef{f}{A}{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 \(\funcdef{f}{A}{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{.}\))
Worked Example 10.2.2.
Show that, of the following functions, \(f\) is surjective and \(g\) is not.
\begin{align*}
f \colon \Z \amp \to \N \amp g \colon \Z \amp \to \Q \\
m \amp \mapsto \abs{m} \amp m \amp \mapsto m/2
\end{align*}
Solution.
Show that \(f\) is surjective.
Consider an arbitrary element \(n\) of the codomain \(\N\text{.}\) Since \(\N \subseteq \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(\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{.}\)
- injective function
a function for which two different inputs never produce the same output
- injection
an injective function
- embedding
synonym for injection
- one-to-one
synonym for injective
- \(\ifuncdef{f}{A}{B}\)
function \(f\) is injective
Test 10.2.3. Injective function.
-
Function \(\funcdef{f}{A}{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 \(\funcdef{f}{A}{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 10.2.4. Demonstrating that a function is not injective.
The function \(\funcdef{f}{\R}{\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 \R\text{.}\)
Worked Example 10.2.5. Demonstrating that a function is injective.
Verify that the function \(\funcdef{f}{\N}{\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 \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 \(\ifuncdef{f}{A}{B}\) gives us a way of thinking of \(A\) as a subset of \(B\text{,}\) by considering \(f(A) \subseteq B\text{.}\)
Example 10.2.6. Turning letters into numbers.
Let \(\Sigma = \ShortEngAlphabet\text{,}\) and define \(\funcdef{\varphi}{\Sigma}{\N}\) by the following table.
| \(\sigma\) |
\(a\) |
\(b\) |
\(c\) |
\(\cdots\) |
\(z\) |
| \(\varphi(\sigma)\) |
\(1\) |
\(2\) |
\(3\) |
\(\cdots\) |
\(26\) |
Then \(f\) embeds \(\Sigma\) into \(\N\) in a familiar way, and lets us think of letters as numbers.
- bijective function
a function that is both injective and surjective
- bijection
an bijective function
- one-to-one correspondence
synonym for bijection
Example 10.2.7.
Function \(\funcdef{f}{\R}{\R}\text{,}\) \(f(x) = x^3\) is bijective.
A bijection \(\funcdef{f}{A}{B}\) allows us to think of \(A\) and \(B\) as essentially the same sets.
Example 10.2.8. Identifying letters with numbers.
Consider again
\(\funcdef{f}{\Sigma}{\N}\) from
Example 10.2.6. If we write
\(B = f(\Sigma) = \{1,2,3,\dotsc,26\}\text{,}\) then really we could think of the function as being defined
\(\funcdef{f}{\Sigma}{B}\text{.}\) This version of
\(f\) is bijective, and allows us to identify each letter with a corresponding number:
\begin{align*}
a \amp \leftrightarrow 1,
\amp b \amp \leftrightarrow 2,
\amp c \amp \leftrightarrow 3,
\amp \amp \dotsc,
\amp z \amp \leftrightarrow 26.
\end{align*}
In this way, we can think of \(\Sigma\) and \(B\) as essentially the same set.
Worked Example 10.2.9. Recognizing bijections.
Which of the following functions are bijections?
\begin{align*}
f \colon \Z \amp \to \Z,
\amp g \colon \Z \amp \to \N,
\amp h \colon \Z \amp \to \Z,\\
m \amp\mapsto 2m,
\amp m \amp \mapsto \abs{m},
\amp m \amp \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 \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 \Z\text{,}\) we can realize \(n\) as an output \(n = h(m)\) by setting \(m = -n\text{.}\)
Checkpoint 10.2.10. Bijections of counting sets.
For \(m \in \N\) write
\begin{equation*}
\natnumlt{m} = \setdef{n \in \N}{ n \lt m} = \{ 0,\, 1,\, \dotsc,\, m-1\} \text{.}
\end{equation*}
Prove that there exists a bijection \(\natnumlt{\ell} \to \natnumlt{m}\) if and only if \(\ell = m\text{.}\)
