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

Prev Top Next