Worksheet 5.3.1 Worksheet
Guiding Questions.
In this section, we’ll seek to answer the questions:
What does it mean for a function to be injective, surjetive, or bijective?
What does it mean for two graphs to be isomorphic?
What does it mean for a function to have an inverse?
We begin with some definitions.
Definition 5.3.1.
Let \(f: X\to Y\) be a function.
We say that \(f\) is injective, or one-to-one (or that \(f\) is an injection), if whenever \(f(a) = f(b)\) we have \(a = b\text{.}\)
We say that \(f\) is surjective, or onto (or that \(f\) is n surjection), if for all \(y\in Y\) there exists \(x\in X\) such that \(f(x) = y\text{.}\)
If \(f\) is injective and surjective we say it is bijective, or a bijection, or a one-to-one correspondence.
Activity 5.3.2.
Consider the function
\(f\) from
Problem 5.2.6. Is
\(f\) injective? Surjective? Bijective? Justify.
Activity 5.3.3.
Using your answers to
Activity 5.3.2 as a model, explain in words what it means for a function to
not be injective, or
not be surjective.
Problem 5.3.4.
Give examples of each of the following as well as an informal proof of your claim.
A function \(f: \Z\to \Z\) that is injective but not surjective.
A function \(f: \Z\to \Z\) that is surjective but not injective.
A function \(f: \Z\to \Z\) that is neither injective nor surjective.
A function \(f: \Z\to\Z\) that is bijective.
Problem 5.3.5.
Let \(X = \set{1,2,3,4}\text{,}\) \(Y = \set{a,b,c,d,e}\text{,}\) \(f: X\to Y\text{,}\) and \(g: Y \to X\text{.}\) Determine whether or not it is possible for each of the following to be true. Be prepared to share your thinking via an informal proof or a counterexample.
\(f\) is injective
\(f\) is surjective
\(f\) is bijective
\(g\) is injective
\(g\) is surjective
\(g\) is bijective
Write a few sentences summarizing your observations.
Functions are helpful tools for characterizing and comparing mathematical objects. An important class of functions relating to graphs are isomorphisms.
Definition 5.3.6.
Let \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) be graphs. An isomorphism from \(G_1\) to \(G_2\) is a bijection \(f : V_1 \to V_2\) such that \(\set{u,v}\in E_1\) if and only if \(\set{f(u), f(v)}\in E_2\text{.}\) In this case, we say that \(G_1\) and \(G_2\) are isomorphic, and write \(G_1 \cong G_2\text{.}\)
Problem 5.3.8.
Write a few sentences explaining (in plain English) what
Definition 5.3.6 means.
Activity 5.3.9.
Are any pairs of graphs in
Problem 2.1.1 isomorphic? If so, justify by stating an isomorphism. If not, explain why not.
To explore graph isomorphisms in more detail, an additional definition will be helpful.
Definition 5.3.10.
A cycle on \(n\) vertices, denoted \(C_n\text{,}\) is a graph with vertex set \(V(C_n) = \set{v_1, v_2, \ldots, v_n}\) and edge set
\begin{equation*}
E(C_n) = \set{v_1 v_2, v_2 v_3, v_3 v_4, \ldots, v_{n-1} v_n, v_n v_1},
\end{equation*}
where, for \(u,v\in V\text{,}\) we represent the edge \(\set{u,v}\) by \(vu\) or \(uv\text{.}\)
Activity 5.3.11.
For various small values of \(n\text{,}\) draw examples of \(C_n\text{.}\)
Activity 5.3.12.
For the same small values of
\(n\) as in
Activity 5.3.11, draw
\(C_n^c\text{.}\) For any values of
\(n\text{,}\) do we have
\(C_n \cong C_n^c\text{?}\) If so, justify by explicitly stating the isomorphism. If not, explain why not.
Another important function concept is that of a composition of functions.
Definition 5.3.13.
Let \(f: X\to Y\) and \(g : Y\to Z\text{.}\) We define the composite function (or composition of \(f\) with \(g\)) to be the function \(g\circ f : X \to Z\) by, for each \(x\in X\text{,}\) \((g\circ f)(x) = g(f(x))\text{.}\)
Problem 5.3.15.
Let \(X = \set{a,b,c,d,e}\text{,}\) \(Y = \set{1,2,3,4,5}\text{,}\) and \(Z = \set{\alpha,\beta,\gamma,\delta}\text{.}\) Define a function \(f: X\to Y\) by
\begin{equation*}
f = \set{(a,3), (b,3), (c,1), (d,2), (e,5)}
\end{equation*}
and \(g : Y\to Z\) by
\begin{equation*}
g = \set{(1,\gamma), (2,\alpha), (3,\beta), (4,\delta), (5,\gamma)}.
\end{equation*}
Fully describe the composite \(h = g\circ f\text{.}\)
Function composition preserves the properties in which we are interested.
Theorem 5.3.16.
Let \(f : X\to Y\) and \(g : Y\to Z\) be injections. Then so is \(g\circ f: X\to Z\text{.}\)
Theorem 5.3.17.
Let \(f : X\to Y\) and \(g : Y\to Z\) be surjections. Then so is \(g\circ f: X\to Z\text{.}\)
Theorem 5.3.18.
Let \(f : X\to Y\) and \(g : Y\to Z\) be bijections. Then so is \(g\circ f: X\to Z\text{.}\)
This yields a couple of nice results about graphs.
Theorem 5.3.19.
Let \(G_i = (V_i, E_i)\) be graphs, for \(i = 1, 2, 3 \text{.}\) If \(G_1\cong G_2\) and \(G_2 \cong G_3\text{,}\) then \(G_1 \cong G_3\text{.}\)
Theorem 5.3.20.
Let \(\mathcal{G}\) be the universe of all graphs. Then the relation “is isomorphic to” is an equivalence relation on \(\mathcal{G}\text{.}\)
