%!TEX root = proofs+concepts.tex


\chapter{Functions} \label{functionsChap}


\begin{quote}
\it It is the pervading law of all things %organic and inorganic,
%Of all things physical and metaphysical,
%Of all things human and all things super-human,
%Of all true manifestations of the head,
%Of the heart, of the soul,
%That the life is recognizable in its expression,
\,\dots\
that form ever follows function. 
\\This is the law.
\par\raggedleft \small\rm\sf
Louis Sullivan (1856--1924), American architect
\\
\emph{The tall office building artistically considered}
\end{quote}







\section{Cartesian product} \label{CartProdSect}

We discussed unions and intersections in \cref{SetOperationsSect}. 
The Cartesian product is another important set operation. Before introducing it, let us recall the notation for an ordered pair.
	
\begin{notation} \label{OrderedPairDefn}
For any objects $x$ and~$y$, mathematicians use \nindex{$(x,y)$}$(x,y)$ to denote the \define{ordered pair} whose first coordinate is~$x$ and whose second coordinate is~$y$. It is important to know that the order matters: $(x,y)$ is usually not the same as $(y,x)$. (That is why these are called \emph{ordered} pairs. Notice that sets are not like this: sets are unordered, so $\{x,y\}$ \emph{is} always the same as $\{y,x\}$.) It is important to realize that:
	\factoidbox{$(x_1,y_1) = (x_2,y_2) \qquad \eiff \qquad \text{$x_1 = x_2$ and $y_1 = y_2$}$}
\end{notation}

\begin{eg}
A special case of the Cartesian product is familiar to all algebra students: recall that
	\begin{equation} \label{CartProdR2Defn}
	 \real^2 = \{\, (x,y) \mid \text{$x \in \real$, $y \in \real$} \,\}
	 \end{equation}
is the set of all ordered pairs of real numbers. This is the ``{coordinate plane}'' (or ``$xy$-plane'') that is used to draw the graphs of functions. 
\end{eg}

The formula $y = f(x)$ often appears in elementary algebra, and, in that subject, the variables~$x$ and~$y$ represent real numbers. However, advanced math courses allow $x$ and~$y$ to be elements of any sets $A$ and~$B$, not just from~$\real$. Therefore, it is important to generalize the above example by replacing the two appearances of~$\real$ in the right-hand side of \cref{CartProdR2Defn} with arbitrary sets~$A$ and~$B$:


\begin{defn}
For any sets $A$ and~$B$, we let
$$ A \times B = \{\, (a,b) \mid a \in A, \ b \in B \,\} 
\nindex{$\times$}
.$$
This notation means, for all~$x$, that
	$$ \text{$x \in A \times B$ iff $\exists a \in A, \exists b \in B, \ x = (a,b)$.} $$
The set $A \times B$ is called the \define{Cartesian product} of~$A$ and~$B$.
\end{defn}


\begin{eg} \label{EasyCartesianEg} \ 
\begin{enumerate}
\item $\real \times \real = \real^2$.
\item \label{EasyCartesianEg-123xab}
 $\{1,2,3\} \times \{\var{a}, \var{b} \} =
\bigl\{ (1,\var{a}), (1,\var{b}), (2,\var{a}), (2,\var{b}), (3,\var{a}), (3,\var{b}) \bigr\}$.
\item \label{EasyCartesianEg-abx123}
 $\{\var{a}, \var{b} \} \times \{1,2,3\}  =
\bigl\{ (\var{a},1), (\var{a},2), (\var{a},3), (\var{b},1), (\var{b},2), (\var{b},3) \bigr\}$.
\end{enumerate}
By comparing \pref{EasyCartesianEg-123xab} and \pref{EasyCartesianEg-abx123}, we see that $\times$ is \emph{not} commutative: $A \times B$ is usually \emph{not} equal to $B \times A$.
\end{eg}


\begin{exers} \label{ListCartesianEx}
Specify each set by listing its elements.
\begin{enumerate}
\item \label{ListCartesianEx-aint}
$\{\var{a}, \var{i}\}  \times \{\var{n}, \var{t}\} = $
\item \label{ListCartesianEx-cards}
$\{\var{Q},\var{K} \} \times \{\clubsuit, \diamondsuit,\heartsuit, \spadesuit\}  =$
\item \label{ListCartesianEx-123}
 $\{1,2,3\} \times \{3,4,5\} = $
%\item $\{\var{b},\pp\} \times \bigl( \{\var{a}, \var{i}\}  \times \{\var{n}, \var{t}\} \bigr) = $ 
\end{enumerate}
\end{exers}


\begin{rem} \label{Card(AxB)Rem}
We will prove in \cref{Card(AxB)Thm} that 
	$$\#(A \times B) = \#A \cdot \#B .$$
In other words:
\factoidbox{The cardinality of a Cartesian product \\ is the product of the cardinalities.}
For now, let us just give an informal justification:
%Thus,
%\factoidbox{The cardinality of the Cartesian product \\ is the product of the cardinalities.}

 Suppose $\#A = m$ and $\#B = n$. Then, by listing the elements of these sets, we may write
 	$$ \text{$A = \{a_1,a_2,a_3,\ldots,a_m\}$ \quad and \quad $B = \{b_1,b_2,b_3,\ldots,b_n\}$.} $$
The elements of $A \times B$ are:
$$ \begin{matrix}
(a_1,b_1), & (a_1,b_2), & (a_1,b_3), & \cdots & (a_1,b_n), \\
(a_2,b_1), & (a_2,b_2), & (a_2,b_3), & \cdots & (a_2,b_n), \\
(a_3,b_1), & (a_3,b_2), & (a_3,b_3), & \cdots & (a_3,b_n), \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
(a_m,b_1), & (a_m,b_2), & (a_m,b_3), & \cdots & (a_m,b_n)
. \end{matrix}$$
In this array,
\begin{itemize}
\item each row has exactly $n$ elements, and
\item there are $m$ rows,
\end{itemize}
so the number of elements is the product $m n = \#A \cdot \#B$. \qed
\end{rem}

Here are some examples of proofs involving Cartesian products.

\begin{eg}
If $A$ and~$B$ are nonempty sets, and $A \times B = B \times A$, then $A = B$.
\end{eg}

\begin{proof}
Assume $A$ and $B$ are nonempty sets, such that $A \times B = B \times A$. It suffices to show $A \subset B$ and $B \subset A$. By symmetry, we need only show $A \subset B$.

Let $a_0$ be an arbitrary element of~$A$. Since $B$ is nonempty, there exists some $b_0 \in B$. Then
	$$ (a_0,b_0) \in A \times B = B \times A = \{\, (b,a) \mid b \in B, a \in A \,\} ,$$
so there exist $b \in B$ and $a \in A$, such that $(a_0,b_0) = (b,a)$. Therefore, $a_0 = b$ (and $b_0 = a$, but we do not need that fact). Hence $a_0 = b \in B$.
\end{proof}


\begin{eg} \label{CartProdDisjoint}
If $B$ is disjoint from~$C$, then $A \times B$ is disjoint from $A \times C$.
 \end{eg}

\begin{proof}
We prove the contrapositive: Assume $A \times B$ is \emph{not} disjoint from $A \times C$, and we will show $B$ is \emph{not} disjoint from~$C$.

By assumption, the intersection of $A \times B$ and $A \times C$ is not empty, so we may choose some
	$$x \in (A \times B) \cap (A \times C) .$$
Then:
\begin{itemize}
\item Since $x \in A \times B$, there exist $a_1 \in A$ and $b \in B$, such that $x = (a_1,b)$.
\item Since $x \in A \times C$, there exist $a_2 \in A$ and $c \in C$, such that $x = (a_2,c)$.
\end{itemize}
Hence $(a_1,b) = x = (a_2,c)$, so $b = c$.
Now $b \in B$ and $b = c \in C$, so $b \in B \cap C$. Therefore $B \cap C \neq \emptyset$, so, 
as desired, 
$B$ and~$C$ are \emph{not} disjoint. 
\end{proof}

\begin{rem}
When reading the proof above, you may have noticed that the variable~$x$ (a single letter) was used to represent an ordered pair $(a,b)$.  There is nothing wrong with this, because the ordered pair is a single object, and a variable can represent any mathematical object at all, whether it is an element of a set, or an entire set, or a function, or an ordered pair, or something else.
\end{rem}

\begin{eg}  \label{CartDistribUnionEg}
Assume $A$, $B$, and~$C$ are sets. Prove $ A \times (B \cup C) = (A \times B) \cup (A \times C)$.
\end{eg}

\begin{proof}
($\supset$) Given $x \in (A \times B) \cup (A \times C)$, we have $x \in A \times B$ or $x \in A \times C$. By symmetry, we may assume $x \in A \times B$, so $x = (a,b)$ for some $a \in A$ and $b \in B$. Note that $b \in B \cup C$, so we have $a \in A$ and $b \in B \cup C$. Therefore
	$$ x = (a,b) \in A \times (B \cup C) .$$
Since $x$ is an arbitrary element of $(A \times B) \cup (A \times C)$, this implies $ (A \times B) \cup (A \times C) \subset A \times (B \cup C)$.
%$B$ and~$C$ are subsets of $B \cup C$, so $A \times B$ and $A \times C$ are subsets of $A \times (B \cup C)$ (see \fullcref{CartesianEx}{AxBinAxC}). Therefore $(A \times B) \cup (A \times C) \subset A \times (B \cup C)$ (see \fullcref{SetOpPfEx}{AUBinC}).

($\subset$) Given $(a,x) \in A \times (B \cup C)$, we have $a \in A$, and either $x \in B$ or $x \in C$. By symmetry, we may assume $x \in B$. Then $(a,x) \in A \times B \subset (A \times B) \cup (A \times C)$, so $(a,x) \in (A \times B) \cup (A \times C)$.
Since $(a,x)$ is an arbitrary element of $A \times (B \cup C)$, this implies $A \times (B \cup C) \subset (A \times B) \cup (A \times C)$.
\end{proof}

\begin{exers} \label{CartesianEx} \ 
\begin{enumerate}
\item Suppose $A$, $B$, and~$C$ are sets.
\begin{enumerate}
\item \label{CartesianEx-AxBinAxC}
Show that if $B \subset C$, then $A \times B \subset A \times C$.
\item \label{CartesianEx-AxB=AxC}
Show that if $A \times B = A \times C$, and $A \neq \emptyset$, then $B = C$.
\end{enumerate}


\item \label{CartesianEx-empty}  
Suppose $A$ is a set.
\begin{enumerate}
\item \label{CartesianEx-empty-xempty}
 Show $A \times \emptyset = \emptyset$.
\item \label{CartesianEx-empty-AxA}  
Show $A \times A =  \emptyset$ if and only if $A = \emptyset$.
\end{enumerate}

\item  \label{CartesianEx-DistribUnion}
To say that $\times$ is distributive over~$\cup$ means that, for all sets $A$, $B$, and~$C$, we have
	$$ \text{$ A \times (B \cup C) = (A \times B) \cup (A \times C)$
	\quad and \quad
	$ (B \cup C)  \times A = (B \times A) \cup (C \times A)$} .$$
The first equation was established in \cref{CartDistribUnionEg}. Complete the proof that $\times$ is distributive over~$\cup$ by proving the second equation.

\item  \label{CartesianEx-DistribIntersection}
Show that $\times$ is distributive over~$\cap $. 
 That is, for all sets $A$, $B$, and~$C$, we have
\begin{enumerate}
\item \label{CartesianEx-DistribIntersection-Ax}
$ A \times (B \cap C) = (A \times B) \cap (A \times C)$,
and
\item \label{CartesianEx-DistribIntersection-xA}
$ (B \cap C)  \times A = (B \times A) \cap (C \times A)$.
\end{enumerate}

%\item Suppose $A$, $B$, $C$, and~$D$ are sets. Show that 
% $(A \times B) \cup (C \times D) \subset (A \cup C) \times (B \cup D)$.

\end{enumerate}
\end{exers}






\section{Informal introduction to functions} \label{introfunctionsSect}

You have seen many examples of functions in your previous math classes. 
Most of these were probably given by formulas (such as $f(x) = x^3$), 
but functions can also be given in other ways. The key property of a function
is that it accepts inputs, and provides a corresponding output value for each possible input.

\begin{eg}
 For the function $f(x) = x^3$, the input~$x$ can be any real number.
Plugging a value for~$x$ into the formula yields an output value,
which is also a real number. For example, using $x = 2$ as the input
yields the output value $f(2) = 2^3 = 8$.
\end{eg}

\begin{defn}[(unofficial)]
Suppose $f$ is any function.
\begin{enumerate}
\item The set of allowable inputs of $f$ is called the \define{domain} of~$f$.
\item If $A$ is the domain of~$f$, and $B$~is any set that contains all of the possible outputs of~$f$, then we say that $f$ is a \define[function]{function from~$A$ to~$B$}. In the case of the function $f(x) = x^3$, we may take $A$ and~$B$ to both be the set of real numbers; thus, $f$~is a function from~$\real$ to~$\real$.
\end{enumerate}
\end{defn}
%\begin{enumerate}
%\item Any function has a \emph{domain}, which is the set of allowable inputs. 
%In this example, any real number can be used as the input~$x$, so the domain is~$\real$,
%the set of all real numbers.
%\item Any function also has a \emph{codomain}, which is a set that contains all of the
%possible outputs. In this example, we know that the output is always a real number, 
%so we can use $\real$ as the codomain. Thus, in this example, we could take the domain
%and the codomain to be the same set, but this is not always the case.  
%In fact, an alert reader may have noticed that the output of~$f$ is never a negative number,
%so we could have used the interval $[0,\infty) = \{\, x \in \real \mid x \ge 0 \,\}$ as the codomain.
%\end{enumerate}
%This illustrates the fact that the codomain of a function is not unique. 
%However, the domain of a function \emph{is} unique --- if you decide to change the set of allowable inputs of a function, then you are considered to have changed the function.
%\end{eg}

%\begin{defn}
%We say that $f$ is a function \emph{from~$A$ to~$B$} if
%\begin{itemize}
%\item $A$ is the \emph{domain} of~$f$,
%and
%\item $B$ is the \emph{codomain} of~$f$.
%\end{itemize}
%\end{defn}

\begin{eg}
$g(x) = 1/x$ is \emph{not} a function from~$\real$ to~$\real$.
This is because $0$ is an element of~$\real$, but the formula does not define a value for $g(0)$.
Thus, $0$~cannot be in the domain of~$g$. To correct this problem, one could say that $g$ is a function from the set $\{\, x \in \real \mid x \neq 0\,\}$ of \emph{nonzero} real numbers, to~$\real$.
\end{eg}

Intuitively, a function from~$A$ to~$B$ can be thought of being any process that accepts inputs from the set~$A$, and assigns an element of the set~$B$ to each of these inputs.
The process need not be given by a formula.
Indeed, most of the functions that arise in science or in everyday life are not given by any formula.


 

\begin{eg} \ 
\begin{enumerate}
\item Each point on the surface of the earth has a particular temperature right now,
and the temperature (in degrees centigrade) is a real number.
Thus, temperature defines a function $\var{temp}$ from the surface of the earth to~$\real$:
 $\var{temp}(x)$ is the temperature at the point~$x$.
 \item The items in a grocery store each have a particular price, which is a certain number of cents, so $\var{price}$ can be thought of as a function from the set of items for sale to the set~$\natural$ of all natural numbers:
 $\var{price}(x)$ is the price of item~$x$ (in cents).
 \item If we let $\var{People}$ be the set of all people (alive or dead), then $\var{mother}$ is a function from $\var{People}$ to $\var{People}$. For example, 
 $$\var{mother}(\var{Prince\ Charles}) = \var{Queen\ Elizabeth} .$$
 (To avoid ambiguity, perhaps we should clarify that, by ``mother\rlap,'' we mean ``biological mother\rlap.'')
 \item In contrast, $\var{grandmother}$ is \emph{not} a function
  from $\var{People}$ to $\var{People}$. 
 This is because people have not just one grandmother, but two (a maternal grandmother and a paternal grandmother). For example, if we say that Prince Charles wrote a poem for his grandmother, we do not know whether he wrote the poem for the mother of Queen Elizabeth, or for his other grandmother. A function is not ever allowed to have such an ambiguity.
 (In technical terms, $\var{grandmother}$ is a ``relation\rlap,'' not a function. 
 This will be explained in \cref{sec.relation}.)
\end{enumerate}
\end{eg}

Functions are often given by a \emph{table} of values. 

\begin{eg} \label{InformalFuncPriceList}
The list of prices in a store is an example of this:

\begin{center}
\begin{tabular}{c|rr}
item & \span price (in cents) \\
\noalign{\hrule}
$\var{apple}$ & \hskip 45pt 65 \\
$\var{banana}$ & 83 \\
$\var{cherry}$ & 7 \\
$\var{donut}$ & 99 \\
$\var{egg}$ & 155 \\
\end{tabular}
\end{center}
In this example:
\begin{itemize}
\item The domain of $\var{price}$ is
 $\{ \var{apple} , \var{banana} , \var{cherry} , \var{donut} , \var{egg}\}$.
\item $\var{price}(\var{banana}) = 83$.
\item $\var{price}(\var{guava})$ does not exist, because $\var{guava}$ is not in the domain of the function.
\end{itemize}
\end{eg}


Instead of making a table, mathematicians prefer to represent each row of the table by an ordered pair. For example, the first row of the table is $\var{apple} \mid 65$. 
This has $\var{apple}$ on the left and $65$ on the right, so we represent it by the ordered pair $(\var{apple}, 65)$, which has $\var{apple}$ on the left and $65$ on the right. 
The second row is represented by $(\var{banana}, 83)$. Continuing in this way yields a total of $5$~ordered pairs (one for each row). To keep them gathered together, a mathematician puts them into a set. Thus, instead of writing a table, a mathematician would represent this function as:
 $$ \bigl\{\, (\var{apple}, 65), 
 (\var{banana}, 83), 
 (\var{cherry}, 7),
  (\var{donut}, 99), 
  (\var{egg}, 155) \,\bigr\} .$$
  The set of ordered pairs contains exactly the same information as a table of values, but the set is a more convenient form for mathematical manipulations.

\vbox to 0pt{%
\vskip\baselineskip
\rightline{
\begin{tabular}{c|c}
$x$ & $f(x)$ \\
\noalign{\hrule}
1 & 7 \\
2 & 3 \\
3 & 2 \\
4 & 4 \\
5 & 9 \\
\end{tabular}}
\vss}
\vskip-0.5\baselineskip

\begin{exer} \label{FunctionByTableEx}
At right is a function~$f$ given by a table of values.
\\(\emph{You do not need to show your work on any parts of this problem.})

\begin{enumerate}
\item  \label{FunctionByTableEx-domain}
What is the domain of~$f$?
%\item What is the range of~$f$? 
\item  \label{FunctionByTableEx-f(3)}
What is $f(3)$?
\item  \label{FunctionByTableEx-pairs}
Represent $f$ as a set of ordered pairs.
\item  \label{FunctionByTableEx-formula}
Find a formula to represent~$f$. \\
\hint{There is a formula of the form $f(x) = ax^2 + bx + c$.}
\end{enumerate}
\end{exer}

\begin{eg}
Not every table of values represents a function. For example, suppose we have the following price list, which is a slight change from \cref{InformalFuncPriceList}:

\begin{center}
\begin{tabular}{c|rr}
item & \span price (in cents) \\
\noalign{\hrule}
$\var{apple}$ &  \hskip 45pt 65 \\
$\var{banana}$ & 83 \\
$\var{cherry}$ & 7 \\
$\var{donut}$ & 99 \\
$\var{banana}$ & 155 \\
\end{tabular}
\end{center}
There is a problem here, because there are two possible prices for a banana, depending on which line of the table is looked at. (So you might pick up a banana, expecting to pay 83~cents, and end up having the cashier charge you \$1.55.) This is not allowed in a function: each input must have exactly one output, not a number of different possible outputs. Thus, if a table represents a function, and an item appears in the left side of more than one row, then all of those rows must have the same output listed on the right side.
\end{eg}

\begin{rem}
A 2-column table represents a function from~$A$ to~$B$ if and only if:
\begin{enumerate}
\item every value that appears in the left column of the table is an element of~$A$,
\item every value that appears in the right column of the table is an element of~$B$,
\item every element of~$A$ appears in the left side of the table,
and
\item no two rows of the table have the same left side, but different right sides.
\end{enumerate}
\end{rem}

\begin{eg} \label{FunctionsWhich123}
 Which of the following are functions from
$\{1, 2, 3\}$ to $\{\var{w},\var{h},\var{o}\}$?
(If it is not such a function, then explain why not.)
\begin{tasks}(2)
\task\fixtask \label{FunctionsWhich123-1w1h1o}
$\{(1, \var{w}), (1, \var{h}), (1,\var{o})\}$
\task\fixtask \label{FunctionsWhich123-1h2h3h}
$\{(1, \var{h}), (2,\var{h}), (3,\var{h})\}$
\task\fixtask \label{FunctionsWhich123-1h2o3w}
$\{(1, \var{h}), (2,\var{o}), (3,\var{w})\}$
\task\fixtask \label{FunctionsWhich123-w1h2o3}
$\{(\var{w},1), (\var{h},2), (\var{o},3)\}$
\end{tasks}
\end{eg}

\begin{solution} \ %Which of the following are functions from
%$\{1, 2, 3\}$ to $\{\mathsf{w},\mathsf{h},\mathsf{o}\}$?
%(If it is not such a function, then explain why not.)
\begin{enumerate}
\item[\pref{FunctionsWhich123-1w1h1o}]
%$\{(1, \mathsf{w}), (1, \mathsf{h}), (1,\mathsf{o})\}$
This is not a function. Since $(1, \mathsf{w}$), $(1, \mathsf{h})$, and $(1,\mathsf{o})$ are all in the set, there are three different elements~$b$ (not a \emph{unique}~$b$), such that $(1,b)$ is in the set.
\item [\pref{FunctionsWhich123-1h2h3h}]
%$\{(1, \mathsf{h}), (2,\mathsf{h}), (3,\mathsf{h})\}$
This is such a function.
\item [\pref{FunctionsWhich123-1h2o3w}]
%$\{(1, \mathsf{h}), (2,\mathsf{o}), (3,\mathsf{w})\}$
This is such a function.
\item [\pref{FunctionsWhich123-w1h2o3}]
%$\{(\mathsf{w},1), (\mathsf{h},2), (\mathsf{o},3)\}$
This is not such a function, because, for the element $(\mathsf{w},1)$ of the set, there do not exist elements~$a$ of $\{1, 2, 3\}$ and $b$ of $\{\mathsf{w},\mathsf{h},\mathsf{o}\}$, such that $(\mathsf{w},1) = (a,b)$. (Instead, we would need to take $a$ in $\{\mathsf{w},\mathsf{h},\mathsf{o}\}$ and $b$ in $\{1, 2, 3\}$, which is backwards from what is required. In fact, $f$ is a function from $\{\mathsf{w},\mathsf{h},\mathsf{o}\}$ to $\{1,2,3\}$, not from $\{1, 2, 3\}$ to $\{\mathsf{w},\mathsf{h},\mathsf{o}\}$.)
\end{enumerate}
\end{solution}

\begin{exer} \label{WhichAreFuncsEx}
Let 
\begin{itemize}
\item $A = \{ \var{a}, \var{b}, \var{c}, \var{d}, \var{e} \}$,
and
\item $B = \{1,3,5,7,9,11\}$.
\end{itemize}
Which of the following sets of ordered pairs are functions from~$A$ to~$B$? 
(For those that are not, explain why.)
\begin{enumerate}
\item \label{WhichAreFuncsEx-a1b3c5d7e9}
$\{ (\var{a}, 1), (\var{b}, 3), (\var{c}, 5), (\var{d}, 7), (\var{e},9) \}$
\item \label{WhichAreFuncsEx-a1b2c3d4e5}
$\{ (\var{a}, 1), (\var{b}, 2), (\var{c}, 3), (\var{d}, 4), (\var{e},5) \}$
\item \label{WhichAreFuncsEx-a1b3c5d3e1}
$\{ (\var{a}, 1), (\var{b}, 3), (\var{c}, 5), (\var{d}, 3), (\var{e},1) \}$
\item \label{WhichAreFuncsEx-a1b3c5d7e9a11}
$\{ (\var{a}, 1), (\var{b}, 3), (\var{c}, 5), (\var{d}, 7), (\var{e},9), (\var{a},11) \}$
\item \label{WhichAreFuncsEx-a1b3c5e7}
$\{ (\var{a}, 1), (\var{b}, 3), (\var{c}, 5), (\var{e},7) \}$
\item \label{WhichAreFuncsEx-a1b1c1d1e1}
$\{ (\var{a}, 1), (\var{b}, 1), (\var{c}, 1), (\var{d}, 1), (\var{e},1) \}$
\item \label{WhichAreFuncsEx-aabacadaea}
$\{ (\var{a}, \var{a}), (\var{b}, \var{a}), (\var{c}, \var{a}), (\var{d}, \var{a}), (\var{e}, \var{a}) \}$
\item \label{WhichAreFuncsEx-a1b3c5d5e3a1}
$\{ (\var{a}, 1), (\var{b}, 3), (\var{c}, 5), (\var{d}, 5), (\var{e}, 3), (\var{a}, 1) \}$
\item \label{WhichAreFuncsEx-1a3a5a7a9a11a}
$\{ (1, \var{a}), (3, \var{a}), (5, \var{a}), (7, \var{a}), (9, \var{a}), (11, \var{a}) \}$
\item \label{WhichAreFuncsEx-c1b3e5a7d9}
$\{ (\var{c}, 1), (\var{b}, 3), (\var{e}, 5), (\var{a}, 7), (\var{d},9) \}$
\end{enumerate}
\end{exer}

\begin{rem}
It is sometimes helpful to represent a function $f \colon A \to B$ by drawing an \define{arrow diagram}: 
\begin{itemize}
\item a dot is drawn for each element of~$A$ and each element of~$B$,
and
\item an arrow is drawn from~$a$ to~$f(a)$, for each $a \in A$.
\end{itemize}
For example, suppose 
\begin{itemize}
\item $A = \{\var{a}, \var{b}, \var{c}, \var{d}, \var{e}\}$,
\item $B = \{1, 2, 3, 4\}$,
and
\item $f = \{ (\var{a},1), (\var{b}, 3), (\var{c}, 4), (\var{d},4), (\var{e}, 3) \}$.
\end{itemize}
Then the picture at right is an arrow diagram of~$f$.
\qquad \vbox to 0pt{\vss
\hbox{\includegraphics{PDF/arrowdiageg.pdf}}
\vskip-\baselineskip
}

\smallskip % !!!

Notice that:
\begin{enumerate}
\item There is exactly one arrow coming out of each element of~$A$. This is true for the arrow diagram of any function.
\item There can be any number of arrows coming into each element of~$B$ (perhaps none, perhaps one, or perhaps more than one).
%The elements of~$B$ that do have arrows into them are precisely the elements of the ``range'' of~$f$. In this example, the range of~$f$ is $\{1,3,4\}$.
\end{enumerate}
\end{rem}





\section{Official definition} \label{FuncDefnSect}


The preceding section provided some intuition about how and why functions are represented as sets of ordered pairs, but it is not at all authoritative. Here are the official definitions.

\begin{defn} \label{FunctionDefn}
 Suppose $A$ and~$B$ are sets.
\begin{enumerate}
\item \label{FunctionDefn-func}
A set~$f$ is a 
\define[function]{function from~$A$ to~$B$} iff
\begin{enumerate}
\item \label{FunctionDefn-func-pair}
 each element of~$f$ is an ordered pair $(a,b)$, such that $a \in A$ and $b \in B$,
and
\item \label{FunctionDefn-func-unique}
  for each $a \in A$, there is a \emph{unique} $b \in B$, such that $(a,b) \in f$.
\end{enumerate}
\item If $f$ is a function from~$A$ to~$B$, then 
\begin{itemize}
\item $A$ is called the \define{domain} of~$f$,
and
\item $B$ is a \define{codomain} of~$f$.
\end{itemize}
\item We write ``$f \colon A \to B$''%
\nindex{$f \colon A \to B$}
to denote that $f$ is a function from~$A$ to~$B$.
\end{enumerate}
\end{defn}

\begin{exer} \label{FunctionsFO}
We can express the definition of a function in {\QL}:
\begin{enumerate}
\item \label{FunctionsFO-translatePair}
 Translate the assertion of \fullcref{FunctionDefn}{func-pair} into First-Order Logic.

\item \label{FunctionsFO-translateUnique}
 Translate the assertion of \fullcref{FunctionDefn}{func-unique} into First-Order Logic.
 \end{enumerate}
\end{exer}


\begin{notation} \label{FunctionNotation}
 Suppose $f \colon A \to B$. 
\begin{enumerate}
\item For $a \in A$, it is convenient to have a name for the element~$b$ of~$B$, such that $(a,b) \in f$. The name we use is $f(a)$:%
\nindex{$f(a)$}
\factoidbox{$f(a) = b$ if and only if $(a,b) \in f$.}
\item \label{FunctionNotation-range}
 Each element~$a$ of~$A$ provides us with an element $f(a)$ of~$B$. The \define[range of a function]{range} of~$f$ is the set that collects together all of these elements $f(a)$. That is,
\factoidbox{$b$ is in the range of $f$ iff there is some $a \in A$, such that $b = f(a)$.}
The range can be denoted $\{\, f(a) \mid a \in A \, \}$.
\end{enumerate}
\end{notation}

\begin{eg}
Suppose the function $f$ is defined by $f(x)=x^2$, on the domain $\{0,1,2,4\}$.  Then:
\begin{enumerate}
\item To represent $f$ as a set of ordered pairs, each element of the domain must appear exactly once as a first coordinate, with the corresponding output given in the second coordinate.  Since there are four elements in the domain, there will be four ordered pairs: $f = \{(0,0), (1,1), (2,4), (4,16)\}$.
\item To give a table for $f$, we include one row for every element of the domain.  The table will be:
\begin{center}
\begin{tabular}{|c|c|}
\noalign{\hrule}
$n$ & $f(n)$ \\
\noalign{\hrule}
0 & 0 \\
 1 & 1 \\
 2  & 4 \\
 4 & 16 \\
\noalign{\hrule}
\end{tabular}
\end{center}
\item If we are asked what is $f(3)$, the answer is that $f(3)$ \emph{does not exist}, because 3 is not in the domain of~$f$.  Even though we know that $3^2=9$, the formula we gave for $f$ only applies to elements that are in the domain of $f$! It is not true that $f(3)=9$.
\item The range of $f$ is the set of possible outputs: in this case, the range of~$f$ is $\{0,1,4,16\}$.
\item If we are asked what is $f(2)$, the answer is $f(2)=4$.
\item Is $f$ a function from $\{n \in \natural \mid n \le 4\}$ to $\{0,1,4,16\}$?  The answer is no, because the first set is $\{0,1,2,3,4\}$, which includes the value $3$, but $3$ is not in the domain of $f$.
\item Is $f$ a function from $\{0,1,2,4\}$ to $\{ n \in \natural \mid n \le 16\}$?  The answer is yes; even though the second set has many values that are not in the range, it is a possible codomain for~$f$.  A codomain can be any set that contains all of the elements of the range, so every function has many different codomains (but only one domain and only one range).
\end{enumerate}
\end{eg}


\begin{exers} \label{FunctionsChapExers} \ 

\begin{enumerate}
\item \label{FunctionsChapExers-gTable}
 The table at right describes a certain function~$g$.

\vskip-\baselineskip
\rightline{\vbox to 0pt{\hbox{\begin{tabular}{|c|c|}
\noalign{\hrule}
$n$ & $g(n)$ \\
\noalign{\hrule}
2 & 7 \\
 4 & 9 \\
 6  & 11 \\
 8 & 13 \\
 10 & 15 \\
\noalign{\hrule}
\end{tabular}}
\vss}\qquad}
\begin{enumerate}
\item   \label{FunctionsChapExers-gTable-domain}
What is the domain of~$g$?
\item   \label{FunctionsChapExers-gTable-range}
What is the range of~$g$?
\item  \label{FunctionsChapExers-gTable-g(6)}
What is $g(6)$?
\item  \label{FunctionsChapExers-gTable-g(7)}
What is $g(7)$?
%\item Draw a graph to depict~$f$.
\item  \label{FunctionsChapExers-gTable-pairs}
Represent~$g$ as a set of ordered pairs.
\item  \label{FunctionsChapExers-gTable-arrow}
Draw an arrow diagram to represent~$g$.
\item  \label{FunctionsChapExers-gTable-formula}
Write down a formula that describes~$g$. 
\\ (Express
$g(n)$ in terms of~$n$, by using simple arithmetic operations.)
\end{enumerate}

\item \label{FunctionsChapExers-fFormula}
 Suppose 
\begin{itemize}
\item $f$ is a function whose domain is $\{0,2,4,6\}$, 
and 
\item $f(x) = 4x - 5$, for every~$x$ in the domain. 
\end{itemize}
Describe the function in each of the following ways:
 \begin{tasks}(3) % !!! 1st column shouldn't be so wide.
\task\fixtask \label{FunctionsChapExers-fFormula-table}%
Make a table.
\task\fixtask \label{FunctionsChapExers-fFormula-arrow}%
Draw an arrow \hbox to 0pt{diagram.\hss} % involving two sets. % hbox !!!
\task\fixtask \label{FunctionsChapExers-fFormula-pairs}%
Use ordered pairs.
\end{tasks}

\item \label{FunctionsChapExers-FindAll}
 For the given sets $A$ and~$B$:
\begingroup 	\setdefaultleftmargin{}{60pt}{}{}{}{} %% extra indentation for (i) and (ii)
\begin{enumerate} 
	\renewcommand{\theenumii}{\roman{enumii}} 
	\makeatletter\renewcommand{\p@enumii}{}\makeatother % want reference to be (i), not (3i)
\item \label{FunctionsChapExers-FindAll-find}
Write each function from~$A$ to~$B$ as a set of ordered pairs.
\item \label{FunctionsChapExers-FindAll-range}
Write down the range of each function.
\end{enumerate}
\endgroup
\begin{tasks}[item-indent=0pt](2) % item-indent (would like to make negative) !!!
\task\fixtask \label{FunctionsChapExers-FindAll-abc+d}
$A = \{\var{a},\var{b},\var{c}\}$, $B = \{\var{d}\}$
\task\fixtask \label{FunctionsChapExers-FindAll-ab+cd}
$A = \{\var{a},\var{b}\}$, $B = \{\var{c},\var{d}\}$
\task\fixtask \label{FunctionsChapExers-FindAll-a+bcd}
$A = \{\var{a}\}$, $B = \{\var{b},\var{c},\var{d}\}$
\task\fixtask \label{FunctionsChapExers-FindAll-ab+cde}
$A = \{\var{a},\var{b}\}$, $B = \{\var{c},\var{d},\var{e}\}$
%\item $A = \{\var{a},\var{b},\var{c}\}$, $B = \{\var{d},\var{e}\}$
\end{tasks}
\hint{For \pref{FunctionsChapExers-FindAll-find}, you may assume, without proof, that if $A$ has exactly $m$~elements, 
and $B$ has exactly $n$~elements, then the number of functions from~$A$ to~$B$
is~$n^m$. (Do you see why this is the correct number?)}

% check to make sure there's no bad page break around here !!!

\item \label{FunctionsChapExers-Whichxy}
 Which of the following sets of ordered pairs are functions from
$\{\var{x}, \var{y}, \var{z}\}$ to $\{\var{a},\var{b},\var{c},\var{d},\var{e}\}$? 
\begin{itemize}
\item If it is such a function, then what is its range? 
\item If it is not such a function, then explain why not.
\end{itemize}
\begin{multicols}{3}
\begin{enumerate}
\item \label{FunctionsChapExers-Whichxy-yaxbyc}
$\{(\var{y}, \var{a}), (\var{x}, \var{b}), (\var{y},\var{c})\}$
\item \label{FunctionsChapExers-Whichxy-yaxbzc}
$\{(\var{y}, \var{a}), (\var{x},\var{b}), (\var{z},\var{c})\}$
\item \label{FunctionsChapExers-Whichxy-yaxcza}
$\{(\var{y}, \var{a}), (\var{x},\var{c}), (\var{z},\var{a})\}$
\end{enumerate}
\end{multicols}

\end{enumerate}
\end{exers}

\begin{eg} \label{BinOpDefn}
If $A$ is a set, then any function from $A \times A$ to~$A$ is called a \define{binary operation} on~$A$. However, when $+$ is a binary operation and $a,b \in A$, we write $a + b$ for the value of the function at $(a,b)$, instead of writing $+\bigl( (a,b) \bigr)$. See \cref{GroupSect} for some examples and many exercises about binary operations.
\end{eg}









\section{One-to-one functions} \label{OnetoOneSect}

%\begin{quote}
%\it 
%To think logically the logically thinkable --- that is the mathematician's aim.
%\par\raggedleft \small\rm\sf
%Cassius Jackson Keyser (1862--1947), American mathematician
%\\
%\emph{The Human Worth of Rigorous Thinking}
%\end{quote}

We begin this \lcnamecref{OnetoOneSect} with an example.
\begin{eg} \ 
\begin{enumerate}
\item Suppose Inspector Thinkright knows two facts:
\begin{enumerate}
\item Alice is the thief's wife,
and
\item Alice is Bob's wife.
\end{enumerate}
Then the Inspector can arrest Bob for theft,
because a woman cannot be the wife of more than one man.

\item On the other hand, suppose the Inspector knows:
\begin{enumerate}
\item Alice is the forger's mother,
and
\item Alice is Charlie's mother.
\end{enumerate}
Then the Inspector does not know enough to be sure who the forger is,
because it could be some other child of Alice, instead of being Charlie.
\end{enumerate}
This example illustrates a fundamental difference between the \var{wife} function and the \var{mother} function: two different people can have the same mother, but only one person can have any particular person as their wife. (For example, if Bud and Charlie have the same wife, then ``Bud'' must be a nickname for Charlie.) 
In mathematical terms, this important property of the $\var{wife}$ function is expressed by saying that the \var{wife} function is ``one-to-one\rlap.''
\end{eg}

The notion is formalized in the following definition:

\begin{defn}
Suppose $f \colon A \to B$. We say $f$ is \define[one-to-one function]{one-to-one} iff, for all $a_1,a_2 \in A$, such that
$f(a_1) = f(a_2)$, we have $a_1 = a_2$. 
\end{defn}

\begin{exers} \label{1stOrder11}
Assume $f \colon A \to B$ and $g \colon X \to Y$. 
Translate each assertion into First-Order Logic.
	\begin{tasks}(2)
	\task\fixtask \label{1stOrder11-f}%
	$f$ is one-to-one.
	\task\fixtask \label{1stOrder11-g}%
	$g$ is one-to-one.
	\task\fixtask \label{1stOrder11-fnot}%
	$f$ is \emph{not} one-to-one.
	\task\fixtask \label{1stOrder11-gnot}%
	$g$ is \emph{not} one-to-one.
	\end{tasks}
\noindent(Simplify your answers in \pref{1stOrder11-fnot} and \pref{1stOrder11-gnot} so that $\enot$ is applied only to predicates.)
\end{exers}

\begin{rem}
If you have an arrow diagram of a function, then it is easy to tell whether or not the function is one-to-one. For example:

\begin{enumerate}
\item The function~$f$ of \cref{arrow11}(a) %on page~\pageref{arrow11} 
is \emph{not} one-to-one. This is because the arrow from~$\var{b}$ and the arrow from~$\var{d}$ go to the same place, so $f(\var{b}) = f(\var{d})$. In general, if arrows from two different elements of the domain go to the same element of the range, then the function is not one-to-one. 

\item The function~$g$ of \cref{arrow11}(b) is one-to-one. This is because the arrows from two different elements of the domain never go to the same element of the range.  In short, there is only \emph{one} element of the domain that goes \emph{to} any \emph{one} element of the range.  (This is the reason for the terminology ``one-to-one\rlap.'' A function is ``two-to-one'' if there are two elements of the domain mapping to each element of the range, as is true of the function~$h$ in \cref{arrow11}(c), but we do not need this terminology.)
\item \emph{Warning.} Although the arrow diagram of a one-to-one function never has more than one arrow pointing to the same element of the codomain, this does not mean that every element of the codomain has \emph{exactly} one arrow into it. For example, the function~$g$ of \cref{arrow11}(b) is one-to-one (because there is never more than one arrow into any point), but there is a point in the codomain that does not have any arrows to it.
\end{enumerate}
\end{rem}
%\begin{center}
\begin{figure}[h]
\includegraphics{PDF/arrow11.pdf}
\caption{Arrow diagrams of three functions $f$, $g$, and~$h$.}
\label{arrow11}
\end{figure}
%\end{center}
%texpreamble
%("  \usepackage{amsmath}
% ");
%defaultpen(  fontcommand("\normalfont") + fontsize(11) ); 
%
%from graph access *;
%unitsize(2cm);
%
%real vskip = 0.25, voff = 0, h = 0, marg = 0.25, hoff = 0;
%dotfactor = 10;
%real v;
%bool dolabel;
%real sep = 1;
%
%void dotit(string lab, pair side) {
%	dot( (h, v) );
%	if (dolabel) {label( "$\mathsf{" + lab + "}$", (h,v), side );}
%	}
%void makeoval( int n ) {
%	draw( (h, (4 - ((5-n)/2))*vskip + marg)..(h + marg, 2*vskip)..(h,((5-n)/2)*vskip-marg)..(h-marg,2*vskip)..cycle, linewidth(2));
%	}
%void arrowit( int v1, int v2, int n1, int n2 ){
%	draw( (h, ((v1-1)+ ((5-n1)/2))*vskip)--(h+0.95*sep, 
%		((0.95*((v2-1)+ ((5-n2)/2))) + 0.05*(((v1-1)+ ((5-n1)/2))))*vskip), EndArrow);
%	}
%string[] labs = {"a","b","c","d","e"};
%
%h = 0; v = 4*vskip; dolabel = true;
%label( "(a)", (h + (sep/2), 5.5*vskip) );
%label( "$f$", (h + (sep/2), 0) , S);
%for (int i = 0; i < 5; ++i) {
%	dotit( labs[i], W );
%	v = v - vskip;
%	}
%makeoval(5);
%arrowit( 5, 4, 5, 4);
%arrowit( 4, 3, 5, 4);
%arrowit( 3, 2, 5, 4);
%arrowit( 2, 3, 5, 4);
%arrowit( 1, 1, 5, 4);
%h = h + sep; v = 3.5*vskip;
%dolabel = false;
%for (int i = 0; i < 4; ++i) {
%	dotit( labs[i], W );
%	v = v - vskip;
%	}
%makeoval(4);
%
%h = 2; v = 3.5*vskip; dolabel = true;
%label( "(b)", (h + (sep/2), 5.5*vskip) );
%label( "$g$", (h + (sep/2), 0) , S);
%for (int i = 0; i < 4; ++i) {
%	dotit( labs[i], W );
%	v = v - vskip;
%	}
%makeoval(4);
%arrowit( 4, 5, 4, 5);
%arrowit( 3, 4, 4, 5);
%arrowit( 2, 2, 4, 5);
%arrowit( 1, 1, 4, 5);
%h = h + sep; v = 4*vskip;
%dolabel = false;
%for (int i = 0; i < 5; ++i) {
%	dotit( labs[i], W );
%	v = v - vskip;
%	}
%makeoval(5);
%
%h = 4; v = 3.5*vskip; dolabel = true;
%label( "(c)", (h + (sep/2), 5.5*vskip) );
%label( "$h$", (h + (sep/2), 0) , S);
%for (int i = 0; i < 4; ++i) {
%	dotit( labs[i], W );
%	v = v - vskip;
%	}
%makeoval(4);
%arrowit( 4, 2, 4, 2);
%arrowit( 3, 2, 4, 2);
%arrowit( 2, 1, 4, 2);
%arrowit( 1, 1, 4, 2);
%h = h + sep; v = 2.5*vskip;
%dolabel = false;
%for (int i = 0; i < 2; ++i) {
%	dotit( labs[i], W );
%	v = v - vskip;
%	}
%makeoval(2);


\begin{eg}
Without giving official proofs, let us determine which of the following functions are one-to-one.
\begin{enumerate}
\item $f\colon \real\to\real$, defined by $f(x)=x +1$.

This is one-to-one.  For any real numbers $x$ and $y$, $f(x)=f(y)$ means that $x+1=y+1$.  Subtracting 1 from both sides of the equation, we conclude that $x=y$ whenever $f(x)=f(y)$.

\item $g\colon \real\to\real$, defined by $g(x)= |x|$.

This is not one-to-one.  We demonstrate this by finding two distinct real numbers whose image is the same: 
$$g(1)=|1|=1=|-1|=g(-1) ,$$
 but $1\neq -1$.  This shows that $g$ is \emph{not} one-to-one.

\item $f\colon \{1,2,3\} \to \{\var{a}, \var{b},\var{c}\}$ defined by $f=\{(1,b),(2,a),(3,a)\}$.

This is not one-to-one.  We demonstrate this by finding two distinct values in $\{1,2,3\}$ whose image is the same: 
$$f(2)=a=f(3),$$
but $2 \neq 3$.  This shows that $f$ is \emph{not} one-to-one. 

\item $h\colon \natural\to\natural$, defined by $h(x)=|x|$.

This is one-to-one.  Since all natural numbers are nonnegative, we have $|x|=x$ for every natural number~$x$.  So if $h(x)=h(y)$, then 
$$x = |x| = h(x)=h(y) = |y|=y .$$
%making $x=y$.

%\item $f$ is a vertex-colouring of a graph on 3 vertices, using only the colours white and black.

%This is not one-to-one.  Knowing nothing about the graph, we can still see that $f$ must assign the colour white to $0, 1, 2,$ or all 3 of the vertices.  In the last two cases, $f$ maps 2 or 3 (respectively) vertices to the colour white, so $f$ is not one-to-one.  In the first two cases, $f$ must map the remaining 3 or 2 vertices to the colour black, so $f$ is not one-to-one.
\end{enumerate}
\end{eg}

\begin{rem}
These examples demonstrate the general pattern of how to prove a function is (or is not) one-to-one:
	\begin{itemize}
	\item To prove that a function $f\colon A \to B$ \emph{is} one-to-one, we need to demonstrate that for \emph{every} $a_1, a_2 \in A$, if $f(a_1)=f(a_2)$, then $a_1=a_2$.  
	\item To prove that a function $f\colon A \to B$ is \emph{not} one-to-one, we need only find a single pair of values $a_1, a_2 \in A$, for which $f(a_1)=f(a_2)$, but $a_1 \neq a_2$.  
	\end{itemize}
\end{rem}

\begin{exers} \label{11Exers}
 {\it Explain why your answers are correct\/ {\rm(}but you do not need to give formal proofs\/{\rm)}.}
\begin{enumerate}
\item \label{11Exers-formula}
 Each formula defines a function from~$\real$ to~$\real$. Which of the functions are one-to-one?
 \begin{tasks}(3) % !!!
\task\fixtask \label{11Exers-formula-f}%
$f(x) = 1$.
\task\fixtask \label{11Exers-formula-g}%
$g(x) = x$.
\task\fixtask \label{11Exers-formula-h}%
$h(x) = x^2$.
\task\fixtask \label{11Exers-formula-i}%
$i(x) = 3x + 2$.
\task\fixtask \label{11Exers-formula-j}%
$j(x) = 1/ \bigl( |x| + 1 \bigr)$.
\end{tasks}

\item \label{11Exers-pairs}
 Each of the following sets of ordered pairs is a function from $\{1,2,3,4\}$ to $\{\var{a},\var{b},\var{c},\var{d},\var{e}\}$. Which are one-to-one?
 \begin{tasks}(2) % !!!
\task\fixtask \label{11Exers-pairs-f}%
$f = \{ (1,\var{a}), (2,\var{b}), (3,\var{d}), (4,\var{e})\}$
\task\fixtask \label{11Exers-pairs-g}%
$g = \{ (1,\var{c}), (2,\var{d}), (3,\var{d}), (4,\var{e})\}$
\task\fixtask \label{11Exers-pairs-h}%
$h = \{ (1,\var{e}), (2,\var{d}), (3,\var{c}), (4,\var{b})\}$
\task\fixtask \label{11Exers-pairs-i}%
$i = \{ (1,\var{e}), (2,\var{e}), (3,\var{e}), (4,\var{e})\}$
\task\fixtask \label{11Exers-pairs-j}%
$j = \{ (1,\var{a}), (2,\var{c}), (3,\var{e}), (4,\var{c})\}$
\task\fixtask \label{11Exers-pairs-k}%
$k = \{ (1,\var{a}), (2,\var{c}), (3,\var{e}), (4,\var{d})\}$
\end{tasks}

%\item \label{11Exers-colouring}
% If $f$ is a vertex-colouring of the complete graph on $n$ vertices, is $f$ one-to-one?
\end{enumerate}
\end{exers}

Here is an example of a formal proof that a function is one-to-one. 

\begin{eg}
Let $f \colon \real\to \real$ be defined by $f(x)= 2x + 1$.  Then $f$ is one-to-one.
\end{eg}

\begin{scratchwork}
By definition, we wish to show $\forall x_1,x_2 \in \real, \bigl( f(x_1) = f(x_2) \eif x_1 = x_2 \bigr)$. Thus, the proof will use $\forall$-introduction: the first words in the proof will be ``Given $x_1,x_2 \in \real$'' (or other words to that effect). Then, because we wish to show $f(x_1) = f(x_2) \eif x_1 = x_2$, we will assume $f(x_1) = f(x_2)$, and the proof will be complete as soon as we can prove $x_1 = x_2$.

By the definition of~$f$, the assumption $f(x_1) = f(x_2)$ means that 
	$$ 2x_1 +1= 2x_2 + 1 .$$
Subtracting~$1$ from both sides, we see that 
	$$ 2x_1 = 2x_2 .$$
Dividing both sides by~$2$, we conclude that $x_1=x_2$, as desired.

Since readers of this textbook are expected to have a good command of logic and high-school algebra, our official proof can omit the comments that are unnecessary for such a well-educated reader. For example, the reader can be expected to be able to easily verify that the equation $2x + 1 = 2x_2 + 1$ can be simplified to the equation $2 x_1 = 2x_2$, without being told that they should subtract~$1$ from both sides.
\end{scratchwork}

%\begin{proof}
%Let $x_1,x_2 \in \real$ be arbitrary.  Suppose that $f(x_1)=f(x_2)$.  By the definition of~$f$, this means that 
%	$$ \frac{x_1}{2} +1=\frac{x_2}{2}+1 .$$
%Subtracting $1$ from both sides, we see that 
%	$$ \frac{x_1}{2}=\frac{x_2}{2} .$$
%Multiplying both sides by $2$, we conclude that $x_1=x_2$. 
%%
%%We know $f\colon \real \to \real$ (by hypothesis), and we have shown that for every $a, b \in \real$ such that $f(a)=f(b)$, we have $a=b$.  By definition, this means that $f$ is one-to-one.
%\end{proof}



\begin{proof}%[Alternate proof]
Given $x_1,x_2 \in \real$, such that $f(x_1)=f(x_2)$, we have 
	$$ 2x_1 +1= 2 x_2+1 ,$$
so
	$$ 2x_1 = 2x_2 ,$$
so $x_1=x_2$. 
\end{proof}

A very similar argument applies to other linear functions.

\begin{eg}
Define $p \colon \real\to \real$ by $p(z)= 6z - 100$.  Show that $p$ is one-to-one.
\end{eg}

\begin{proof}
Given $z_1,z_2 \in \real$, such that $p(z_1)=p(z_2)$, we have 
	$$ 6z_1 - 100 = 6z_2 - 100 ,$$
so
	$$ 6z_1 = 6z_2 ,$$
so $z_1=z_2$. 
\end{proof}


\begin{exers} \label{11LinEx}
Prove that each function is one-to-one.

\begin{tasks}(2)
\task\fixtask \label{11LinEx-3x+5}%
$f \colon \real \to \real$ defined by $f(x) = 3x + 5$.
\task\fixtask \label{11LinEx-7x-2}%
$f \colon \real \to \real$ defined by $f(x) = 7x - 2$.
\task\fixtask \label{11LinEx-4t+9}%
$g \colon \real \to \real$ defined by $g(t) = 4t + 9$.
\task\fixtask \label{11LinEx-7-8s}%
$h \colon \real \to \real$ defined by $h(s) = 7 - 8s$.
\task\fixtask \label{11LinEx-(5r-2)/7}%
$i \colon \real \to \real$ defined by $i(r) = (5r-2)/7$.
\task\fixtask \label{11LinEx-2n+11}%
$j \colon \integer \to \integer$ defined by $j(n) = 2n + 11$.
\end{tasks}
\end{exers}



The fact that the \var{wife} function is one-to-one can be restated as the fact that two different people cannot have the same wife. In general, a function is one-to-one iff two different elements of the domain always map to two different elements of the range:
\factoidbox{A function $f \colon A \to B$ is one-to-one if and only if 
 \refstepcounter{equation} \label{alternate11}
  \\ \hbox to 0pt{\hss(\theequation)\hskip0.75in}$\displaystyle \forall a_1,a_2 \in A, \bigl( a_1 \neq a_2 \implies f(a_1) \neq f(a_2) \bigr)$.}
(The notation ``$\forall a_1, a_2 \in A$''%
\nindex{$\forall a_1, a_2 \in A$}
is short for ``$\forall a_1\in A, \forall a_2 \in A$\rlap.'')
 
%We can justify this theorem with a two-column proof. However, we need a new rule of proof: ``\define{definition}\rlap.'' 
We should justify the assertion in this box with a proof. The implication $\eif$ is proved in the following theorem; the other direction is an exercise.

\begin{thm} \label{alternate11thm}
If a function $f\colon A \to B$ is one-to-one, then $$\forall a_1, a_2 \in A, \bigl( a_1 \neq a_2 \eif f(a_1) \neq f(a_2)\bigr).$$
\end{thm}

\begin{proof}
Let $f \colon A \to B$ be one-to-one. Given $a_1,a_2 \in A$, we know, from the definition of one-to-one,  that
	$$  f(a_1) = f(a_2) \eif a_1 = a_2 .$$
So the contrapositive of this implication is also true. That is,
	\begin{align*}
	 a_1 \neq a_2 \eif f(a_1) \neq f(a_2) . && \qedhere\end{align*}
\end{proof}

 

\begin{exers} \label{11twocolpfs}\ 
\begin{enumerate}
\item \label{11twocolpfs-alternate}
 Prove the converse of \cref{alternate11thm}. % if \pref{alternate11} holds, then $f$~is one-to-one.
More precisely, assume $f \colon A \to B$, and show that if 
	$$\forall a_1, a_2 \in A, \bigl( a_1 \neq a_2 \eif f(a_1) \neq f(a_2)\bigr),$$
then $f$ is one-to-one.
\item \label{11twocolpfs-composition}
Assume: 
\begin{tasks}(3)
\task\fixtask $f \colon A \to B$,
\task\fixtask $f$ is one-to-one,
\task\fixtask $a_1,a_2 \in A$,
\task\fixtask $g \colon B \to C$,
\task\fixtask $g$ is one-to-one,
\task\fixtask $b_1,b_2 \in B$,
\task\fixtask $f(a_1) = b_1$,
\task\fixtask $f(a_2) = b_2$,
\ and
\task\fixtask $g(b_1) = g(b_2)$.
\end{tasks}
\noindent Show $a_1 = a_2$.
\hint{First use the fact that $g$ is one-to-one, then the fact that $f$ is one-to-one.}
\end{enumerate}
\end{exers}

%In some cases, when a function is not one-to-one, it is easy to find examples of distinct elements whose images are equal.  In other cases, such examples may be hard to find.
%When you do not know whether or not a particular function is one-to-one, it may help to try proving that it \emph{is} one-to-one.  If the proof works, great! --- you are done.  If the proof fails, the manner in which it fails may help you find an example to show that the function is not one-to-one.  Here is an example of this technique.
%
%\begin{eg}
%Let $f\colon \natural \to \natural$ be defined by $f(n)=(n-1)^2$.  Is $f$ one-to-one?
%\end{eg}
%
%\begin{scratchwork}
%Let us try to prove that $f$ is one-to-one, and see what happens.  To do this, we start with arbitrary elements $m, n \in \natural$, and suppose that $f(m)=f(n)$.  By the definition of $f$, this means that $(m-1)^2=(n-1)^2$.  Two numbers have the same square, if and only if they are equal in absolute value, so we can conclude that $m-1 = \pm (n-1)$.  If $m-1=+(n-1)$ then adding 1 to each side, we get $m=n$, completing the proof.  But if $m-1 = -(n-1) = -n+1$, then adding 1 to each side, we get $m=-n+2$.  Since $m,n \in \natural,$ it is not hard to see that if $n \ge 3$, then $-n+2 \le -3+2=-1$, so $-n+2$ is not a natural number, and these cases cannot arise.  But if $n$ is 0, 1, or 2, then $-n+2$ is 2, 1, or 0 (respectively), all of which are natural numbers.  If $n=1$ then $m=-n+2=1=n$, so this case is not a problem.  But if $m=2$ and $n=0$, then $(m-1)^2=1^2=(-1)^2=(n-1)^2$, so $f(m)=f(n)$ even though $m \neq n$.  (We could also choose $m=0$ and $n=2$.)  This is the example that shows that $f$ is \emph{not} one-to-one.
%\end{scratchwork}
%
%\begin{solution}
%$f$ is \emph{not} one-to-one. 
%
%To prove this, let $m = 0$ and $n = 2$. Then 
%	$$ f(m) = f(0) = (0-1)^2 = 1$$
%and
%	$$ f(n) = f(2) = (2-1)^2 = 1 ,$$
%so $f(m) = f(n)$. On the other hand, we also have $m = 0 \neq 2 = n$, so $m \neq n$. Since $f(m) = f(n)$ and $m \neq n$, we know that $f$ is not one-to-one.
%\end{solution}  
%
%\begin{notation}
%Recall (from high-school algebra) that the absolute value~$|x|$ of a real number~$x$ is defined by 
% 	$|x| = \begin{cases} \hfil x & \text{if $x \ge 0$} ,\\ -x & \text{if $x < 0$} . \end{cases}$
%\end{notation}
%
%\begin{exers} \label{IsIt11?}
%For each function, either prove that it is one-to-one, or prove that it is not.
%\begin{problist}
%\item \label{IsIt11?-linear}
% $f \colon \rational \to \rational$ defined by $f(x)=3x/5 - 2$.
%\item \label{IsIt11?-square}
% $f \colon \natural \to \natural$ defined by $f(n)=n^2$.
%\item \label{IsIt11?-abs}
% $g \colon \real \to \real$ defined by $g(t)= |(t+1)/2|$.
%\end{problist}
%\end{exers}


 

\begin{rem}[(alternative terminology)]
Many mathematicians use the word ``\emph{injective}\rlap,'' rather than ``one-to-one\rlap.'' (This comes from French.) Also, a function that is one-to-one can be called an \emph{injection}.
\end{rem}











\section{Onto functions} \label{OntoSect}

%\begin{quote}
%\it There are two ways to do great mathematics. The first way is to be smarter than everybody else. The second way is to be stupider than everybody else -- but persistent.
%\par\raggedleft \small\rm\sf
%Raoul Bott (1923--2005), Harvard mathematician
%\end{quote}

In an arrow diagram of a function $f \colon A \to B$, the definition of a function requires that there is exactly one arrow out of each element of~$A$, but it says nothing about the number of arrows into each element of~$B$. There may be elements of~$B$ with lots of arrows into them (unless the function is one-to-one), and there may be other elements of~$B$ that have no arrows into them. 
The function is called ``onto'' if all of the elements of~$B$ are hit by arrows; none are missed.

\begin{eg}
\Cref{arrowontofig} shows arrow diagrams of various functions, some onto and some not.
\end{eg}

\begin{center}
\begin{figure}[h]
\includegraphics[scale=0.6]{PDF/arrowonto.pdf}
\caption{\hfil\break %Function~$f$ is onto, but not one-to-one. 
%\hfil\break Function~$g$ is both one-to-one and onto. 
%\hfil\break Function~$h$ is neither one-to-one nor onto. 
%\hfil\break Function~$i$ is one-to-one, but not onto.
%\begin{tabular}{cc}
 $f$ is onto, but not one-to-one. 
\hfil $h$ is neither one-to-one nor onto.%
\break $g$ is both one-to-one and onto.
\hfil $i$ is one-to-one, but not onto.%
\break}
\label{arrowontofig}
\end{figure}
\end{center}

\begin{eg}
 Not every woman is a mother. 
%This means there is some woman~$w$, such that there does \emph{not} exist any person~$p$, such that $\var{mother}(p) = w$. 
This means that if you draw an arrow from each person to his or her mother, there will be some women who have no arrows into them. So the function 
$$\var{mother} \colon \var{People} \to \var{Women}$$
 is \emph{not} onto.
\end{eg}

The following official definition of ``onto'' formalizes the ideas described above.

\begin{defn}
Suppose $f \colon A \to B$. We say $f$ is \define[onto function]{onto} iff, for all $b \in B$, 
there is some $a \in A$, such that $f(a) = b$. 
\end{defn}

\vbox{ % keep this on one page !!!
\begin{exers} \label{1stOrderOntoExers}
Suppose $f \colon A \to B$ and $g \colon X \to Y$. Translate each of the following assertions into First-Order Logic:
\begin{multicols}{4}
\begin{enumerate}
\item \label{1stOrderOntoExers-fonto}
 $f$ is onto.
% $\forall b \in B, \ \exists a \in A, \bigl( f(a) = b \bigr)$
\item \label{1stOrderOntoExers-fnot}
 $f$ is \emph{not} onto.
\item \label{1stOrderOntoExers-gonto}
 $g$ is onto.
\item \label{1stOrderOntoExers-gnot}
 $g$ is \emph{not} onto.
\end{enumerate}
\end{multicols}
\noindent (Simplify your answers in \pref{1stOrder11-fnot} and \pref{1stOrder11-gnot} so that $\enot$ is applied only to predicates.)
 \end{exers}
}

\begin{eg}
Without giving formal proofs, let us demonstrate that each of the following functions is not onto.
\begin{enumerate}

%\item $f\colon \real\to\real$, defined by $f(x)=x +1$.
%
%\begin{quote}
%This is onto.  For any real number $y$, $f(x)=y$ means that $x+1=y$.  Subtracting 1 from both sides of the equation, we conclude that for any real number $y$, if $x=y-1$, then $f(x)=y$.
%\end{quote}

\item $f\colon \real\to\real$, defined by $f(x)= |x|$.

\begin{quote}
Recall that the absolute value of a real number can never be negative. In particular, we can never have $|x|=-1$ for any real number~$x$. Thus, there does not exist $x \in \real$, such that $f(x) = -1$. This shows that $f$ is \emph{not} onto.
\end{quote}

\item $g\colon \{1,2,3\} \to \{\var{a}, \var{b},\var{c}\}$ defined by $g=\{(1,b),(2,a),(3,a)\}$.

\begin{quote}
Notice that $c$ never appears as the second coordinate of an ordered pair in this function. This means there does not exist any~$x$, such that $g(x) = \var{c}$. This means that $g$ is \emph{not} onto. 
\end{quote}

%\item $h\colon \natural\to\natural$, defined by $h(x)=|x|$.
%
%\begin{quote}
%This is onto.  Since all natural numbers are nonnegative, we have $|x|=x$ for every natural number $x$.  Thus, given $y \in \real$, we may let $x=y$, and then $h(x) = |x|=x=y$.
%\end{quote}

%\item $f$ is a vertex-colouring of a (simple) graph on 3 vertices that has at least one edge, using only the colours white and black.

%This is onto.  Since the graph has at least one edge, the vertices incident to that edge must have different colours: that is, one must be white and the other black.  So both colours are mapped onto by $f$.
\end{enumerate}
\end{eg}

\vbox{% !!!
\begin{exer} \label{OntoOrNotPairsEx}
 Each of the following sets of ordered pairs is a function from $\{1,2,3,4,5\}$ to $\{\clubsuit,\diamondsuit,\heartsuit,\spadesuit\}$. Which of the functions are onto? {\it Briefly justify your answers.}
 \setlength{\columnsep}{-4pt} % eliminate overfull hboxes !!!
 \begin{tasks}(2)
\task\fixtask \label{OntoOrNotPairsEx-a}%
$a = \{ (1,\clubsuit), (2,\diamondsuit), (3,\heartsuit), (4,\spadesuit), (5,\clubsuit) \}$
\task\fixtask \label{OntoOrNotPairsEx-b}%
$b = \{ (1,\clubsuit), (2,\heartsuit), (3,\clubsuit), (4,\heartsuit), (5,\clubsuit) \}$
\task\fixtask \label{OntoOrNotPairsEx-c}%
$c = \{ (1,\heartsuit), (2,\heartsuit), (3, \heartsuit), (4,\heartsuit), (5, \heartsuit) \}$
\task\fixtask \label{OntoOrNotPairsEx-d}%
$d = \{ (1,\diamondsuit), (2,\spadesuit), (3, \heartsuit), (4,\spadesuit), (5, \clubsuit) \}$
\task\fixtask \label{OntoOrNotPairsEx-e}%
$e = \{ (1,\clubsuit), (2,\spadesuit), (3, \heartsuit), (4,\spadesuit), (5, \clubsuit) \}$
\end{tasks}
\end{exer}
}
 Let us see how to prove that a function $f \colon A \to B$ is onto. By definition, we wish to show:
 $$ \mbox{for all $b \in B$, there is some $a \in A$, such that $f(a) = b$.}$$
 In other words: ``$\forall b \in B, \exists a \in A, \bigl( f(a) = b \bigr)$\rlap.'' 

The first quantifier is~$\forall$; we are required to prove something about every element of~$B$. Hence, we use $\forall$-introduction, so our proof should start with the sentence ``Let $b$ be an arbitrary element of~$B$\rlap.'' (However, this can be abbreviated to: ``Given $b \in B$, \ldots'') After this, our task will be to prove ``$\exists a \in A, \bigl( f(a) = b \bigr)$\rlap.''  

At this point, the quantifier that concerns us is~$\exists$; we are required to prove that some element of~$A$ has a certain property. The tool to use for this is $\exists$-introduction: we find (or ``construct'') an appropriate element of~$A$, and then verify that it does what it is supposed to. Thus, the next step in the proof is ``Let $a = {{?}{?}{?}}$'' (where ${{?}{?}{?}}$ needs to be replaced with an appropriate expression). Then all that remains is to verify that the value we assigned to~$a$ does the job it is required to do: calculate that $f(a)$ is indeed equal to~$b$.

So here what a typical ``onto'' proof looks like:
$$ \mbox{Given $b \in B$, let $a = \raise 4pt \hbox{\hskip-3pt\boxit{\phantom{M}}}$. Then
$f(a) = \cdots = b$.} $$
An appropriate value for~$a$ needs to be put in the box (perhaps a formula that depends on~$b$), and the dots need to be filled in with a calculation that shows the value of~$f(a)$ is~$b$.  (Also, of course, some of the letters will need to be changed if the name of the function is not~$f$, or if the sets are not called $A$ and~$B$.)

\begin{eg}
Define $g \colon \real \to \real$ by $g(x) = 5x - 2$. Show $g$ is onto.
\end{eg}

\begin{scratchwork}
We wish to show $\forall y \in \real, \exists x \in \real, \bigl( g(x) = y \bigr)$. By $\forall$-introduction, the first words of the proof are easy: ``Given $y \in \real$\rlap.'' Then we need to find a value of~$x$ that makes $g(x) = y$. The appropriate value of~$x$ is probably not obvious, so we will do some scratchwork. We postulate the desired equation $g(x) = y$ and use algebra to solve it:
\begin{align*}
g(x) &= y \\
5x-2 &= y \\
5x &= y + 2 \\
x &= \frac{y+2}{5}
.\end{align*}
Now that we know the correct value of~$x$, it is easy to write the rest of the proof.
\end{scratchwork}

\begin{proof} Given $y \in \real$, let $x = (y+2)/5 \in \real$. Then
\begin{align*}
g(x) = 5x - 2 = 5 \left( \frac{y+2}{5} \right) - 2 = (y+2) - 2 = y 
. \end{align*}
\end{proof}


%\begin{rem}
%The simple ``onto'' proof described above is based on two important general principles that are analogues of the $\forall$-introduction rule and the $\exists$-introduction rule.
%\medskip
% \factoidbox{The proof of an assertion that begins
% ``for all $x \in X$\rlap,''
% \\ will usually begin with ``Let $x$ be an arbitrary element of~$X$''
% \\ or, for short, ``Given $x \in X$\rlap,''}
% \factoidbox{The proof of an assertion that begins
% \\ ``there exists $y \in Y$, such that\dots\rlap,''
% \\ will usually be based on the statement ``Let $y = \raise 3pt \hbox{\boxit{\phantom{M}}}$\rlap,'' 
% \\ where the box is filled with an appropriate element of~$Y$.}
%\end{rem}


\vbox{% !!!
\begin{exers} \label{LinearOntoEx}
Each formula defines a function from~$\real$ to~$\real$. Show the function is onto.
\begin{tasks}(3)
\task\fixtask \label{LinearOntoEx-2x+1}%
$f(x) = 2x + 1$.
\task\fixtask \label{LinearOntoEx-7x-3}%
$g(x) = 7x - 3$.
\task\fixtask \label{LinearOntoEx-4t+9}%
$h(t) = 4t + 9$.
\task\fixtask \label{LinearOntoEx-6-11z}%
$i(z) = 6 - 11z$.
\task\fixtask \label{LinearOntoEx-over5}%
$j(r) = (3r - 4)/5$.
\end{tasks}
\end{exers}
}

\begin{rem}
Some ``onto'' proofs are more complicated than what is described above, because it may not be possible to go directly from ``given $b \in B$'' to ``let $a = \raise 3pt \hbox{\boxit{\phantom{x}}}$\,\rlap.'' The problem is that it is sometimes necessary to insert calculations (or other explanations) between ``given~$b$'' and ``let~$a$\rlap.'' Some examples of this will be seen in \cref{CompositionTheoryExers}.
\end{rem}

To complete the discussion, let us also see how to prove that a function $f \colon A \to B$ is \emph{not} onto. By negating the definition of ``onto\rlap,'' we see that we wish to prove ``$\exists b \in B, \forall a \in A, \bigl( f(a) \neq b \bigr)$\rlap.''

The first quantifier is~$\exists$; we are required to prove that some element of~$B$ has a certain property. The tool to use for this is $\exists$-introduction: we find an appropriate element of~$B$, and then we will need to verify that it does what it is supposed to. Thus, the first step in the proof is ``Let $b = {{?}{?}{?}}$'' (where ${{?}{?}{?}}$ needs to be replaced with an appropriate expression). After this, our task will be to prove ``$\forall a \in A, \bigl( f(a) \neq b \bigr)$\rlap.''  

At this point, the quantifier that concerns us is~$\forall$; we are required to prove something about every element of~$A$. Hence, we use $\forall$-introduction, so the next step in our proof is the sentence ``Let $a$ be an arbitrary element of~$A$'' (or, for short,``Given $a \in A$, \ldots''). Then all that remains is to verify that $f(a) \neq b$.

So here what a typical ``not onto'' proof looks like:
$$ \mbox{Let $b = \raise 4pt \hbox{\hskip-3pt\boxit{\phantom{x}}} \in B$. Given $a \in A$, we have \dots, so $f(a) \neq b$.} $$
An appropriate value for~$b$ needs to be put in the box, and the dots need to be filled in with an explanation that leads to the conclusion $f(a) \neq b$.  (Also, as usual, some of the letters will need to be changed if the name of the function is not~$f$, or if the sets are not called $A$ and~$B$.)

\begin{eg} \label{NotOntoFormulaEg-e(r)}
Define $e \colon \real \to \real$ by $e(r) = 1/ \bigl( |r| + 1 \bigr)$.
Show $e$ is not onto.
\end{eg}

\begin{scratchwork}
We wish to prove $\exists y \in \real, \forall r \in \real, \bigl( e(r) \neq y \bigr)$, so we need to come up with an appropriate value of~$y$. To do this, let's attempt to prove $e$ is onto. Hopefully, we will run into trouble, and this difficulty will point us to a good choice for~$y$. Namely, if $e$ were onto, we would be able to solve the equation
	\begin{align*}
	e(r) &= y \\
\intertext{Let's put in the definition of $e(r)$, and use algebra to try to solve this equation:}
	 \frac{1}{ |r| + 1 } &= y \\
	 |r| + 1 &= \frac{1}{y} \\
	 |r| &= \frac{1}{y} - 1
	 . \end{align*}
Now the absolute value $|r|$ is never negative, but the right-hand side of the equation could be negative. For example, if $y = -1$, then 
	$$\frac{1}{-1} - 1 = -1 - 1 = -2 < 0 .$$
This suggests that we should let $y = -1$. With this in mind, we can write the proof.
\end{scratchwork}

\begin{proof}
Let $y = -1$. Given $r \in \real$, we have $|r| \ge 0$, so $|r| + 1 \ge 0 + 1 = 1 > 0$. Therefore
 	$$e(r) = \frac{1}{ |r| + 1 } \ge 0 > -1 = y ,$$
so $e(r) \neq y$. Since $r$ is an arbitrary element of the domain~$\real$, this implies that $e$ is not onto. 
\end{proof}

And sometimes you will need to decide whether a function is onto or not.

\begin{eg}
Define $m \colon \real \times \real \to \real$ by $m (x,y) = x + y$. Is $m$ onto?
\end{eg}

\begin{scratchwork}
Let's try to prove $m$ is onto. (If we fail, this is evidence that $m$ is not onto, and we will try to prove that.) Given $z \in \real$, we try to solve the equation
	\begin{align*}
	 m(x,y) &= z. \\
\intertext{In other words:}
	 x + y &= z
	 . \end{align*}
It is easy to find values of $x$ and~$y$ that satisfy the equation: perhaps the easiest solution is to let $y = 0$ and $x = z$. We can use these values to prove that $m$ is onto.
\end{scratchwork}

\begin{solution}
$m$ is onto.
\begin{proof}
Given $z \in \real$, let $(x,y) = (z,0) \in \real \times \real$. Then 
	\ $m(x,y) = x + y = z + 0 = z$.
\end{proof}
\end{solution}

\vbox{ % keep this on one page !!!
\begin{exers} \label{OntoFormulaEx} \ 
 Each formula defines a function from~$\real$ to~$\real$. Which of the functions are onto?
  {\it Prove that your answers are correct.}
  \begin{tasks}(3)
\task\fixtask \label{OntoFormulaEx-f(x)}%
 $f(x) = 1$.
\task\fixtask \label{OntoFormulaEx-a(x)}%
 $a(x) = x$.
\task\fixtask \label{OntoFormulaEx-b(t)}%
 $b(t) = t^2$.
\task\fixtask \label{OntoFormulaEx-c(s)}%
 $c(s) = 3s + 2$.
%\task\fixtask \label{OntoFormulaEx-f(s)}%
% $f(s) = 4s - 6$.
\task\fixtask \label{OntoFormulaEx-d(r)}%
 $d(r) = \root 3 \of {r+5} - 5$.
\end{tasks}
\end{exers}
} % vbox

%\begin{exers} \label{OntoTheoreticalExers} \ 
%\begin{enumerate}
%% \item Give an example of a function $f \colon \real \to \real$ that is both one-to-one and onto.
%% ({\em Justify your answer!\/})
%% \item Give an example of a function $f \colon \real \to \real$ that is one-to-one, but not onto.
%% ({\em Justify your answer!\/})
%% \item Give an example of a function $f \colon \real \to \real$ that is onto, but not one-to-one.
%% ({\em Justify your answer!\/})
%% \item \label{m>nIFFonto}
%% Suppose $m,n \in \natural$. Show $m \ge n$ if and only if there exists an onto function $f \colon \{1,2,3,\ldots,m\} \to \{1,2,3,\ldots,n\}$.
%% \hint{SHOULD GIVE A HINT!!!}
%\end{enumerate}
%\end{exers}

%\begin{exer} \label{OntoCasesExer}
% Define functions $f$ and~$g$ from~$\real$ to~$\real$ by:
%$$ f(x) = 
%\begin{cases}
%1/x & \mbox{if $x > 0$} \\
%x + 1 & \mbox{if $x \le 0$}
%\end{cases} $$
%and
%$$ g(x) = 
%\begin{cases}
%1/x & \mbox{if $x > 0$} \\
%x - 1 & \mbox{if $x \le 0$}
% . \end{cases} $$
% Show:
% \begin{enumerate}
% \item \label{OntoCasesExer-fOnto}
% $f$ is onto;
% \item \label{OntoCasesExer-gNotOnto}
% $g$ is not onto;
% \item \label{OntoCasesExer-fNot11}
% $f$ is not one-to-one;
% and
% \item \label{OntoCasesExer-g11}
% $g$ is one-to-one.
%\end{enumerate}
%\end{exer}

\begin{exer} \label{OntoExers-range}
%\item \label{OntoExers-colour}
% If $f$ is a vertex-colouring of the complete graph on $n$ vertices that uses $n$ colours, is $f$ onto?
%\emph{Justify your answer.}
 Suppose $f \colon A \to B$. Show that $f$ is onto if and only if the range of~$f$ is~$B$.
\end{exer}

\begin{rem}[(alternative terminology)]
Some mathematicians say ``\emph{surjective}\rlap,'' rather than ``onto\rlap.'' (Like ``injective'' in place of ``one-to-one\rlap,'' this comes from French.) Also, a function that is onto can be called a \emph{surjection}.
\end{rem}









\section{Bijections} \label{BijectionsSect}

%\begin{quote}
%\it ``How dreadful!'' cried Lord Henry. ``I can stand brute force, but brute reason is quite unbearable. There is something unfair about its use. It is hitting below the intellect\rlap.''
%\par\raggedleft \small\rm\sf
%Oscar Wilde (1854--1900), Irish author
%\\
%\emph{The Picture of Dorian Gray}
%\end{quote}

The best functions are {both} one-to-one \emph{and} onto.
These are called ``bijections\rlap.'' 

\begin{defn}
 A function is a \define{bijection} iff it is both one-to-one and onto.
\end{defn}

 \begin{eg} \label{MarriedEg}
 Consider a hypothetical country $\var{Married}$, in which 
 \begin{itemize}
 \item everyone is married (to only one person --- there is no polygamy!),
 and
 \item every marriage is between a man and a woman (there are no same-sex marriages). 
 \end{itemize}
Let 
\begin{itemize}
\item $\var{Men}$ be the set of men in the country,
and 
\item $\var{Women}$ be the set of women in the country.
\end{itemize}
Then $\var{wife} \colon \var{Men} \to \var{Women}$ is a bijection:
\begin{itemize}
 \item Two different men cannot have the same wife, so we know that $\var{wife}$ is one-to-one. 
 \item Every woman is the wife of some man (because everyone is married), so $\var{wife}$ is also onto.
 \end{itemize}
Similarly, the function $\var{husband} \colon \var{Women} \to \var{Men}$ is also a bijection.
 \end{eg}

\begin{rem}
In the country $\var{Married}$ described above, it is clear that the number of men is exactly equal to the number of women. (If there were more men than women, then not every man could have a wife; if there were more women than men, then not every women could have a husband.) This is an example of the following important principle that will be discussed in the later chapter on ``cardinality'':
	\factoidbox{If there is a \textbf{bijection} from~$A$ to~$B$, 
	then \\ the two sets $A$ and~$B$ must have
	exactly the same number of elements.}
Finding a bijection is the most common way to show two sets have the same number of elements.
\end{rem}

\begin{rems} \ 
	\noprelistbreak
	\begin{enumerate}
	\item You may recall that a one-to-one function can be called an ``injection\rlap,'' and an onto function can be called a ``surjection\rlap.''  The term ``bijection'' comes from having both of these two properties.
	\item Some textbooks use the term ``one-to-one correspondence'' for a bijection, but we will avoid that terminology, because it is too easy to confuse with ``one-to-one function\rlap,'' which does not mean the same thing.
	\end{enumerate}
\end{rems}


\begin{rem}
Showing that a function is a bijection requires two things: showing that the function is one-to-one, and showing that the function is onto. So a proof that a function is a bijection will (usually) have two parts:
	\begin{enumerate}
	\item Show that the function is one-to-one.
	\item Show that the function is onto.
	\end{enumerate}
The two parts can come in either order: it is perfectly acceptable to first prove that the function is onto, and then prove that it is one-to-one.
\end{rem}


\begin{eg} \label{5x-7BijectionEg}
\emph{Define $f \colon \real \to \real$ by $f(x) = 5x-7$. Then $f$ is a bijection.}
\end{eg} 

\begin{proof}
It suffices to show that $f$ is both one-to-one and onto.

(one-to-one) Given $x_1,x_2 \in \real$, such that $f(x_1) = f(x_2)$, we have
	$$ 5x_1 - 7 = 5x_2 - 7 ,$$
so 
	$$ 5x_1 = 5x_2 ,$$
so 
	$$ x_1 = x_2 .$$
Therefore $f$ is one-to-one.

(onto) Given $y \in \real$, let $x = (y+7)/5$. Then
$$ f(x) = 5x-7 = 5 \left( \frac{y+7}{5} \right) - 7 = (y+7) - 7 = y .$$
Therefore $f$ is onto.

Since $f$ is both one-to-one and onto, it is a bijection.
\end{proof}


\begin{exer} \label{BijectRtoRExer}
Each formula defines a function from~$\real$ to~$\real$. Show that the function is a bijection.
\begin{tasks}(3)
\task\fixtask \label{BijectRtoRExer-(5x+2)}%
$a(x) = 5x+2$
\task\fixtask \label{BijectRtoRExer-(2x-5)}%
$b(x) = 2x - 5$
\task\fixtask \label{BijectRtoRExer-(12x-15)}%
 $c(x) = 12x-15$
\task\fixtask \label{BijectRtoRExer-(-15x-12)}%
$d(x) = -15x - 12$
\task\fixtask \label{BijectRtoRExer-(x^3)}%
$e(x) = x^3$
\task\fixtask \label{BijectRtoRExer-(root3of(x-4))}%
$f(x) = \root 3 \of {x-4} $
%\task\fixtask $g(x) = \root 3 \of {x+5} - 4$
\end{tasks}
\end{exer}

\begin{notation} \label{IdentityMapDefn}
For any set~$A$, define the \define[identity!map]{identity map} $\Id_A \colon A \to A$%
\nindex{$\Id_A$, $\Id_X$, etc.} by $\Id_A(a) = a$ for every $a \in A$.
\end{notation}

\begin{exer} \label{IdIsBij}
Let $A$ be a set.
Show that the identity map $\Id_A$ is a bijection from~$A$ to~$A$.
\end{exer}

%
%\begin{exers} \label{BijectLinFracExer} \ 
%\begin{enumerate}
%\item Let 
%$$ \mbox{$A = \{\, a \in \real \mid a \neq 2 \,\}$ and $B = \{\, b \in \real \mid b \neq 3 \,\}$,} $$
%and define $f \colon A \to B$ by 
%$$f(a) = \frac{3a+1}{a-2} .$$
%Show that $f$ is a bijection.
%
%\item Let 
%$$ \mbox{$X = \{\, x \in \real \mid x \neq -1 \,\}$ and $Y = \{\, y \in \real \mid y \neq 5/2 \,\}$,} $$
%and define $g \colon X \to Y$ by 
%$$g(x) = \frac{5x-3}{x+1} .$$
%Show that $g$ is a bijection.
%\end{enumerate}
%\end{exers}


\begin{exer} \label{WhichBijRExer}
 Each formula defines a function from~$\real$ to~$\real$. Which of the functions are bijections?
  {\it Show that your answers are correct.}
\begin{tasks}(3)
\task\fixtask \label{WhichBijRExer-(7)}%
$a(x) = 7$.
\task\fixtask \label{WhichBijRExer-(4x-7)}%
$b(x) = 4x-7$.
\task\fixtask \label{WhichBijRExer-(x^2)}%
$c(x) = x^2$.
\task\fixtask \label{WhichBijRExer-(3r+2)}%
$d(r) = 3r + 2$.
%\task\fixtask \label{WhichBijRExer-(1/(|s|+1))}%
%$e(s) = 1/ \bigl( |s| + 1 \bigr)$.
\task\fixtask \label{WhichBijRExer-(3|s|+2)}%
$e(s) = 3 |s| + 2$.
%\task\fixtask \label{WhichBijRExer-(4x-6)}%
%$f(x) = 4x - 6$.
\task\fixtask \label{WhichBijRExer-(sqrt(t^2+1))}%
$f(t) = \sqrt{t^2 + 1}$
\task\fixtask \label{WhichBijRExer-(root3ofu-5)}%
$g(u) = \root 3 \of {u} - 5$.
\end{tasks}
\end{exer}

%\begin{exer} \label{LinearWhenBijectionExer}
%Let $a ,b \in \real$, and define $f \colon \real \to \real$ by $f(x) = a x + b$. 
%\begin{enumerate}
%\item \label{LinearWhenBijectionExer-not0}
%Show that if $a \neq 0$, then $f$ is a bijection.
%\item \label{LinearWhenBijectionExer-0}
%Show that if $a = 0$, then $f$ is \emph{not} a bijection.
%\end{enumerate}
%\end{exer}

\begin{eg} \label{m2+nNotBij}  
 Define $f \colon \natural \times \natural \to \natural$ by $f(m,n) = m^2 + n$. 
\begin{multicols}{2}
 \begin{enumerate}
 \item \label{m2+nNotBij-onto}  
 Show that $f$ is onto.
 \item \label{m2+nNotBij-not11}  
 Show that $f$ is \emph{not} one-to-one.
 \end{enumerate}
 \end{multicols}
 \end{eg}
 
 \begin{solution}
\pref{m2+nNotBij-onto} Given $k \in \natural$, let $x = (0,k) \in \natural \times \natural$. Then 
 	\begin{align*}
	 f(x) = f(0,k) = 0^2 + k = k . 
	 \end{align*}
Since $k$ is an arbitrary element of~$\natural$, we conclude that $f$ is onto.

\pref{m2+nNotBij-not11} 
 Let $x_1 = (1,0)$ and $x_2 = (0,1)$. Then $x_1 \neq x_2$, but
 	\begin{align*}
	 f(x_1) = f(1,0) = 1^2 + 0 = 1 = 0^2 + 1 = f(0,1) = f(x_2) ,
	 \end{align*}
so $f$ is not one-to-one.
 \end{solution}

 \begin{exers}  \label{mpmnNotBij}  
Define $g \colon \integer \times \integer \to \integer \times \integer$ by $g(m,n) = (m + n, m - n)$. 
 \begin{problist}
 \item  \label{mpmnNotBij-notonto}  
Show that $g$ is \emph{not} onto.
\hint{$(m + n) + (m - n) = 2m$. Can this be odd?}
 \item  \label{mpmnNotBij-11}  
Show that $g$ is one-to-one.
\end{problist}
\end{exers}


\begin{prop} \label{BijectionIffExistsUnique}
Suppose $f \colon A \to B$. Show $f$ is a bijection iff, for each $b \in B$, there is a \emph{unique} $a \in A$, such that $f(a) = b$. In other words, $f$ is a bijection if and only if
 $$ \forall b \in B, \exists!\, a \in A, \bigl( f(a) = b \bigr) .$$
 \end{prop}

\begin{proof} ($\Rightarrow$) Let $b$ be an arbitrary element of~$B$. Since $f$ is a bijection, it is onto, so there exists $a \in A$, such that $f(a) = b$. All that remains is to show that $a$ is unique. To this end, let $a' \in A$, such that $f(a') = b$. Then
$$ f(a') = b = f(a) .$$
Since $f$ is a bijection, it is one-to-one, so we conclude that $a' = a$. Thus, $a$ is unique.

($\Leftarrow$) It suffices to show that $f$ is both onto and one-to-one.

(onto) Given $b \in B$, we are assuming that there is a (unique) element~$a$ of~$A$, such that $f(a) = b$. Therefore $f$ is onto.

(one-to-one) Given $a_1,a_2 \in A$, such that $f(a_1) = f(a_2)$, let $b = f(a_1)$. Then $f(a_1) = b$ and $f(a_2) = b$. From the uniqueness of the element~$a$ of~$A$, such that $f(a) = b$, we conclude that $a_1 = a_2$. Since $a_1$ and~$a_2$ are arbitrary elements of~$A$, such that $f(a_1) = f(a_2)$, this implies that $f$ is one-to-one.
\end{proof}




\begin{rem}
Officially, $\times$ is \emph{not} associative, because
	$$ (A \times B) \times C = \{\, \bigl( (a,b),c \bigr) \mid a \in A, b \in B, c \in C\,\} $$
and
	$$ A \times (B \times C) = \{\, \bigl(a,(b,c)\bigr) \mid a \in A, b \in B, c \in C\,\} .$$
are (usually) not the same sets: an element of $(A \times B) \times C$ must have an ordered pair $(a,b)$ as its first coordinate, whereas an element of $A \times (B \times C)$ can have any element of~$A$ as its first coordinate.
\end{rem}


\begin{exer} \label{AxBxCBijectionEx}
Suppose $A$, $B$, and~$C$ are sets. Define
	$$ \text{$f \colon (A \times B) \times C \to A \times (B \times C)$ \quad by \quad $f\bigl( (a,b),c \bigr) = \bigl( a,(b, c) \bigr)$.} $$
Show that $f$ is a bijection.
\end{exer}


\begin{rem}
One can define the Cartesian product of more than two sets. For example, 
	$$ A \times B \times C = \{\, (a,b,c) \mid a \in A, b \in B, c \in C\,\} .$$
%Here, $(a,b,c)$ represents an ordered triple: we have $(a,b,c) = (a',b',c')$ iff $a = a'$, $b = b'$, and $c = c'$. 
Although $A \times B \times C$ is not the same as $(A \times B) \times C$ or $A \times (B \times C)$, the difference between them can often be ignored in practice.
\end{rem}


%\begin{rem} 
%Bijections arise often in mathematics; here are a few examples from graph theory.
%\begin{enumerate}
%\item Suppose $G$ is a bipartite graph with bipartition sets~$L$ and~$R$. One can show that $G$ has a perfect matching if and only if there is a \textbf{bijection} $m \colon L \to R$, such that $m(v)$ is adjacent to~$v$, for every $v \in L$.

%\item Suppose $G$ is a graph with $n$~vertices, and let $V$ be the vertex set of~$G$. One can show that $G$ has a Hamilton path if and only if there is a \textbf{bijection} $f \colon \{1,2,3,\ldots,n\} \to V$, such that 
%	$$ \text{$f(i)$ is adjacent to $f(i+1)$ for $i = 1,2,3,\ldots,n-1$.} $$

%\item Suppose $G$ and~$H$ are two graphs, with vertex sets $V$ and~$W$, respectively. Recall that $G$ is isomorphic to~$H$ if and only if $G$ and~$H$ can be represented by the same drawing.
%That is an unofficial definition; the official definition is that there is a \textbf{bijection} $f \colon V \to W$, such that, for all $v_1,v_2 \in V$, 
%\\[3pt]
%$ \mbox{\quad $v_1$ is adjacent to~$v_2$ }
% \quad \eiff \quad  \mbox{$f(v_1)$ is adjacent to~$f(v_2)$.}
% $
%\end{enumerate}
%\end{rem}









 

 
 \section{Inverse functions} \label{InverseFunctionsSect}

\begin{quote}
\it Backwards poets write inverse.
\par\raggedleft \small\rm\sf
Author unknown
\end{quote}

\medskip\noindent
All students of mathematics have experience with solving an equation for~$x$. Inverse functions are a special case of this.

\begin{eg}
In \cref{5x-7BijectionEg}, it was shown that $f(x) = 5x - 7$ is a bijection. A look at the proof reveals that the formula
$(y+7)/5$
plays a key role.  The reason this formula is so important is that (solving for~$x$) we have
$$ y = 5x - 7 \qquad \eiff \qquad x = \frac{y+7}{5} .$$
In order to see this as an ``inverse function\rlap,'' we translate into the language of functions, by letting $g \colon \real \to \real$ be defined by $g(y) = (y+7)/5$. Then the above assertion can be restated as:
\begin{align} \label{y=f(x)<>x=g(y)}
 y = f(x) \qquad \eiff \qquad x = g(y) .
 \end{align}
This tells us that $g$ does exactly the opposite of what~$f$ does: if $f$ takes $x$ to~$y$, then $g$ takes $y$ to~$x$. We will say that $g$ is the ``inverse'' of~$f$.
\end{eg}

The following exercise provides a restatement of \pref{y=f(x)<>x=g(y)} that will be used in the official definition of inverse functions.
However, we usually use $A$ for the domain of a generic function (and $B$ for the codomain), so it replaces the variables $x$ and~$y$ with $a$ and~$b$.

 \begin{exer} \label{a=g(b)->InverseExer} 
 Suppose  $f \colon A \to B$
 and $g \colon B \to A$.
  Show that if
 $$ \forall a \in A, \forall b \in B, \bigl(b = f(a) \eiff a = g(b) \bigr), $$
then
  \begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}
  \item  \label{a=g(b)->InverseExer-g(f(a))}
 $g \bigl( f(a) \bigr) = a$ for all $a \in A$,
 and
\item  \label{a=g(b)->InverseExer-f(g(b))}
 $f \bigl( g(b) \bigr) = b$ for all $b \in B$.
 \end{enumerate}
 \end{exer}

 \begin{defn} \label{InverseDefn}
 Suppose 
 \begin{itemize}
 \item $f \colon A \to B$,
 and
 \item $g \colon B \to A$.
\end{itemize}
We say that $g$ is the \define[inverse!of a function]{inverse} of~$f$ iff:
 \begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}
 \item $g \bigl( f(a) \bigr) = a$ for all $a \in A$,
 and
 \item $f \bigl( g(b) \bigr) = b$ for all $b \in B$.
 \end{enumerate}
 \end{defn}
 
\begin{eg}
Suppose $z \colon S \to T$ and $k \colon T \to S$. What does it mean to say that $k$ is the inverse of~$z$?
\end{eg}

\begin{solution}
It means that two things are true:
 \begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}
 \item $k \bigl( z(s) \bigr) = s$ for all $s \in S$,
 and
 \item $z \bigl( k(t) \bigr) = t$ for all $t \in T$.
 \qedhere
 \end{enumerate}
\end{solution}

\begin{exer} \label{InvcExer}
Suppose $c \colon U \to V$ and $d \colon V \to U$. What does it mean to say that $d$ is the inverse of~$c$?
\end{exer}

 \begin{notation}
 The inverse of~$f$ is denoted $f^{-1}$.%
 \nindex{$f^{-1}$}
 \end{notation}

\begin{eg}
Note that:
\begin{itemize}
\item the husband of the wife of any married man is the man himself, i.e.,
$$ \var{husband}\bigl( \var{wife} (m) \bigr) = m, $$
and
\item the wife of the husband of any married woman is the woman herself, i.e.,
$$ \var{wife}\bigl( \var{husband} (w) \bigr) = w . $$
\end{itemize}
This means the $\var{husband}$ function is the inverse of the~$\var{wife}$ function. That is, $\var{wife}^{-1} = \var{husband}$.
\end{eg}

\begin{rem}
The inverse is easy to describe in terms of arrow diagrams. Namely, from the fact that
	$$ b = f(a) \quad \eiff \quad a = f^{-1}(b) ,$$ 
we see that 
	$$ \text{$f$ has an arrow from $a$ to~$b$
		\quad $\eiff$ \quad
		$f^{-1}$ has an arrow from $b$ to~$a$} .$$
Therefore, the arrow diagram of~$f^{-1}$ is obtained by just reversing all the arrows in the arrow diagram of~$f$:
 \par \smallskip
	\centerline{
	\includegraphics{PDF/ArrowFinv-F.pdf}
	\hskip 1in
	\includegraphics{PDF/ArrowFinv-Finv.pdf}
	}
\end{rem}
%texpreamble
%("  \usepackage{amsmath}
% ");
%defaultpen(  fontcommand("\normalfont") + fontsize(11) ); 
%
%from graph access *;
%unitsize(2cm);
%
%real h = 0.5, v = 1.25, x = 0.5, y = 2;
%dotfactor = 10;
%
%draw( (0,0)..(h,v)..(0,2*v)..(-h,v)..cycle, linewidth(2) );
%label( "$A$", (0,0), N );
%dot( (0,x) ); label( "$a_1$", (0,x), W );
%dot( (0,2*x) ); label( "$a_2$", (0,2*x), W );
%dot( (0,3*x) ); label( "$a_3$", (0,3*x), W );
%dot( (0,4*x) ); label( "$a_4$", (0,4*x), W );
%
%draw( (y,0)..(y+h,v)..(y,2*v)..(y-h,v)..cycle, linewidth(2) );
%label( "$B$", (y,0), N );
%dot( (y,x) ); label( "$b_1$", (y,x), E );
%dot( (y,2*x) ); label( "$b_2$", (y,2*x), E );
%dot( (y,3*x) ); label( "$b_3$", (y,3*x), E );
%dot( (y,4*x) ); label( "$b_4$", (y,4*x), E );
%
%//draw( (0,x){ENE} .. {ESE}(y,x), linewidth(2), EndArrow(15) );
%//draw( (0,2*x){ENE} .. {ESE}(y,2*x), linewidth(2), EndArrow(15) );
%//draw( (0,3*x){ENE} .. {ESE}(y,3*x), linewidth(2), EndArrow(15) );
%//draw( (0,4*x){ENE} .. {ESE}(y,4*x), linewidth(2), EndArrow(15) );
%//label( "$f$", (0.5*y, 4.5*x ) , N );
%
%draw( (0,x){ENE} .. {ESE}(y,x), linewidth(2), BeginArrow(15) );
%draw( (0,2*x){ENE} .. {ESE}(y,2*x), linewidth(2), BeginArrow(15) );
%draw( (0,3*x){ENE} .. {ESE}(y,3*x), linewidth(2), BeginArrow(15) );
%draw( (0,4*x){ENE} .. {ESE}(y,4*x), linewidth(2), BeginArrow(15) );
%label( "$f^{-1}$", (0.5*y, 4.5*x ) , N );

\begin{eg}
Define $f \colon \real \to \real$ and $g \colon \real \to \real$ by $f(x) = 7x - 4$ and $g(x) = (x + 4)/7$. Verify that $g$ is the inverse of~$f$.
\end{eg}

\begin{proof}
It suffices to show:
 \begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}
  \item \label{VerifyInvEg-gof}
 $g \bigl( f(x) \bigr) = x$ for all $x \in \real$,
 and
\item \label{VerifyInvEg-fog}
 $f \bigl( g(y) \bigr) = y$ for all $y \in \real$.
 \end{enumerate}

\pref{VerifyInvEg-gof} Given $x \in \real$, we have
	\begin{align*}
	g \bigl( f(x) \bigr) 
	= \frac{f(x) + 4}{7}
	= \frac{\bigl( 7x - 4 \bigr) + 4}{7}
	= \frac{7x}{7}
	= x
	. \end{align*}

\pref{VerifyInvEg-fog} Given $y \in \real$, we have
	\begin{align*} f \bigl( g(y) \bigr) 
	= 7 \, g(y) - 4 
	= 7 \left( \frac{y+4}{7} \right) - 4 
	= \bigl( y+4 \bigr) - 4 
	= y 
	. \end{align*}
\end{proof}

 \begin{exers} \label{VerifyInverseExers}
 In each case, verify that $g$ is the inverse of~$f$.
 \begin{enumerate}
 \item \label{VerifyInverseExers-(9x-6)}
$f \colon \real \to \real$ is defined by $f(x) = 9x - 6$ and 
 \\ $g \colon \real \to \real$ is defined by $g(x) = (x + 6)/9$.
 \item \label{VerifyInverseExers-(x^2)}
$f \colon \real^+ \to \real^+$ is defined by $f(x) = x^2$ and 
 \\ $g \colon \real^+ \to \real^+$ is defined by $g(x) = \sqrt{x}$.
 \item \label{VerifyInverseExers-(1/x)}
$f \colon \real^+ \to \real^+$ is defined by $f(x) = 1/x$ and 
 \\ $g \colon \real^+ \to \real^+$ is defined by $g(x) = 1/x$.
 \item \label{VerifyInverseExers-(sqrt(x+1)-1)}
$f \colon \real^+ \to \real^+$ is defined by $f(x) = \sqrt{x+1} - 1$ and 
 \\ $g \colon \real^+ \to \real^+$ is defined by $g(x) = x^2 + 2x$.
 \end{enumerate}
 \end{exers}
   

 Most functions do \emph{not} have an inverse. In fact, only bijections have an inverse:
 

 \begin{thm} \label{Inverse->Bijection}
 Suppose $f\colon A \to B$. If $f$ has an inverse $f^{-1} \colon B \to A$, then $f$ is a bijection.
 \end{thm}
 

 \begin{proof}
 Assume there is a function $f^{-1} \colon B \to A$ that is an inverse of~$f$. Then
\begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}
\item $f^{-1} \bigl( f(a) \bigr) = a$ for all $a \in A$,
and
\item $f \bigl( f^{-1}(b) \bigr) = b$ for all $b \in B$.
\end{enumerate}
 We wish to show that $f$ is a bijection. This is left as an exercise for the reader. \hint{This is very similar to many of the previous proofs that functions are bijections, but with the equation $a = f^{-1}(b)$ in place of an explicit formula for~$a$. For example, if $f(a_1) = f(a_2)$, then $f^{-1} \bigl( f(a_1) \bigr) = f^{-1} \bigl( f(a_2) \bigr)$. What is each side of this equation equal to?}
 \end{proof}


 \begin{exers} \label{InverseUniqueExers} \ 
 \begin{enumerate}
 \item \label{InverseUniqueExers-bij}
 Prove that the inverse of a bijection is a bijection.
 \item \label{InverseUniqueExers-converse}
 Prove the converse of \cref{a=g(b)->InverseExer}.
 \item \label{InverseUniqueExers-unique}
 Show that the inverse of a function is \emph{unique}: if $g_1$ and~$g_2$ are inverses of~$f$, then $g_1 = g_2$. (This is why we speak of \emph{the} inverse of~$f$, rather than \emph{an} inverse of~$f$.)
 \end{enumerate}
 \end{exers}


\begin{rem}
If $f$ is a function that has an inverse, then it is easy to find~$f^{-1}$ as a set of ordered pairs. Namely, 
$$ f^{-1} = \{\, (b,a) \mid (a,b) \in f \,\} .$$
This is simply a restatement of the fact that
 $$b = f(a) \eiff a = f^{-1}(b) $$
 (or the fact that the arrow diagram of~$f^{-1}$ is obtained by reversing the arrows in the arrow diagram of~$f$).
\end{rem}


\begin{exer} \label{Bijection->InverseEx}
Prove the converse of \cref{Inverse->Bijection}.
\hfil \hint{Find $f^{-1}$ as a set of ordered pairs.}
\end{exer}




\begin{exer} \label{InvOfInv}
Suppose $f \colon A \to B$ is a bijection. Show that the inverse of~$f^{-1}$ is~$f$. That is, $(f^{-1})^{-1} = f$.
\end{exer}











\section{Composition of functions} \label{CompositionSect}

\begin{quote}
\it Nothing goes by luck in composition. It allows of no tricks.
\par\raggedleft \small\rm\sf
Henry David Thoreau (1817--1862), American author
%\\
%in his Journal
\end{quote}

\medskip\noindent
The term ``composition'' is a name that mathematicians use for an idea that comes up fairly often in everyday life.

\begin{eg} \ 
\begin{enumerate}
\item The father of the mother of a person is the grandfather of the person.
 (To be precise, it is the \emph{maternal} grandfather of the person --- and his or her other grandfather is \emph{paternal}.) To express the relationship in a mathematical formula, we can write:
 $$ \forall x,  \Bigl( \var{grandfather}(x) = \var{father} \bigl( \var{mother}(x) \bigr) \Bigr) .$$
 A mathematician abbreviates this formula by writing
 $$ \var{grandfather} = \var{father} \compose \var{mother} $$
 and says that the (maternal) \var{grandfather} function is the \emph{composition} of \var{father} and \var{mother}.
 \item The brother of the mother of a person is an uncle of the person, so \var{uncle} is the composition of \var{brother} and \var{mother}:
  $$ \forall x, \Bigl( \var{uncle}(x) = \var{brother} \bigl( \var{mother}(x) \bigr) \Bigr) ,$$ 
  or, more briefly,
  $$ \var{uncle} = \var{brother} \compose \var{mother} .$$
 (For the sake of this example, let us ignore the issue that \var{uncle} and \var{brother} are not functions, because some people have no uncle or no brother, or have more than one.)
\item The daughter of a child is a granddaughter, so \var{granddaughter} is a composition of \var{daughter} and \var{child}:
$$ \var{granddaughter} = \var{daughter} \compose \var{child} .$$
(We ignore the fact that \var{granddaughter}, \var{daughter}, and \var{child} are not functions.)
\end{enumerate}
\end{eg}


 

\begin{exers} \label{RealWorldCompositionExer}
State the usual name for each composition. 
 (Ignore the fact that \var{sister}, \var{daughter}, and many of the other relations are not functions.)
 \begin{tasks}(2)
\task\fixtask \label{RealWorldCompositionExer-HusbandOfSister}%
$\var{husband} \compose \var{sister} =$
\task\fixtask \label{RealWorldCompositionExer-HusbandOfMother}%
$\var{husband} \compose \var{mother} =$
\task\fixtask \label{RealWorldCompositionExer-HusbandOfWife}%
$\var{husband} \compose \var{wife} =$
\task\fixtask \label{RealWorldCompositionExer-HusbandOfDaughter}%
$\var{husband} \compose \var{daughter} =$
\task\fixtask \label{RealWorldCompositionExer-MotherOfSister}%
$\var{mother} \compose \var{sister} =$
\task\fixtask \label{RealWorldCompositionExer-DaughterOfSister}%
$\var{daughter} \compose \var{sister} =$
\task\fixtask \label{RealWorldCompositionExer-ParentOfParent}%
$\var{parent} \compose \var{parent} =$
\task\fixtask \label{RealWorldCompositionExer-ChildOfChild}%
$\var{child} \compose \var{child} =$
\task\fixtask \label{RealWorldCompositionExer-ParentOfParentOfParent}%
$\var{parent} \compose \var{parent} \compose \var{parent} =$
\task\fixtask \label{RealWorldCompositionExer-ChildOfBrotherOfParent}%
$\var{child} \compose \var{brother} \compose \var{parent} =$
\end{tasks}
\end{exers}

\begin{defn}
Suppose $f \colon A \to B$ and $g \colon B \to C$. The \define[composition of functions]{composition} $g \compose f$%
\nindex{$\compose$}
of~$g$ and~$f$ is the function from~$A$ to~$C$ defined by
$$ \mbox{$(g \compose f)(a) = g \bigl( f(a) \bigr)$ for all $a \in A$.} $$
\end{defn}

\begin{eg}
Define $f \colon \real \to \real$ and $g \colon \real \to \real$ by
$f(x) = 3x$ and $g(x) = x^2$. Then $g \compose f$ and $f \compose g$ are functions from~$\real$ to~$\real$. For all $x \in \real$, we have
$$(g \compose f)(x) = g \bigl( f(x) \bigr) = g(3x) =(3x)^2 =  9x^2 $$
and
$$(f \compose g)(x) = f \bigl( g(x) \bigr) = f(x^2) = 3(x^2) = 3x^2 .$$
Notice that (in this example) $f \compose g \neq g \compose f$, so \emph{composition is \textbf{not} commutative}.
\end{eg}

\begin{exer} \label{ComposeFormEx} 
 The formulas define functions $f$ and~$g$ from~$\real$ to~$\real$. Find formulas for \text{$(f \compose g)(x)$} and $(g \compose f)(x)$.
\begin{problist}
\item \label{ComposeFormEx-(3x+1)(x2+2)}
 $f(x) = 3x + 1$ and $g(x) = x^2 + 2$.
\item \label{ComposeFormEx-(3x+1)(x-1/3)}
 $f(x) = 3x + 1$ and $g(x) = (x-1)/3$.
\item \label{ComposeFormEx-(ax+b)(cx+d)}
 $f(x) = ax + b$ and $g(x) = c x + d$ (where $a,b,c,d \in \real$).
\item \label{ComposeFormEx-(|x|)(x2)}
 $f(x) = |x|$ and $g(x) = x^2$.
\item \label{ComposeFormEx-(|x|)(-x)}
 $f(x) = |x|$ and $g(x) = -x$.
\end{problist}
\end{exer}

\begin{warn} \label{ComposeWarn}
To calculate the value of the function $g \compose f$ at the point~$a$, do \emph{not} begin by calculating $g(a)$. Instead, you need to calculate $f(a)$. Then plug that value into the function~$g$.
\end{warn}

\begin{eg}
\Cref{arrowcomposefig} provides an arrow diagram to illustrate the composition $g \compose f$.
\begin{itemize}
\item Starting from any point of~$A$, follow the arrow (for the function~$f$) that starts there to arrive at some point of~$B$.
\item Then follow the arrow (for the function~$g$) that starts there to arrive at a point of~$C$.
\end{itemize}
For example, the $f$-arrow from~$a$ leads to~$m$ and the $g$-arrow from~$m$ leads to~$u$. So $(g \compose f)(a) = u$.

%\begin{center}
\begin{figure}[h]
\includegraphics[scale=0.55]{PDF/arrowcompose.pdf}
\caption{Arrows for the composition $g \circ f$ are dotted.}
\label{arrowcomposefig}
\end{figure}
%\end{center}

Notice that even though~$g$ appears on the left in the expression $g \compose f$, the arrow diagram for~$g$ appears on the right in the figure. This is an unfortunate consequence of the way that we calculate $g \bigl(f(x) \bigr)$ --- see the warning above.
\end{eg}

\begin{exers} \label{ComposePairsEx} 
 Let $A = \{1,2,3,4\}$, $B = \{\var{a},\var{b},\var{c},\var{d}\}$, and $C = \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\}$. The sets of ordered pairs in each part are functions $f \colon A \to B$ and $g \colon B \to C$. Represent $g \compose f$ as a set of ordered pairs.
\begin{tasks}[after-item-skip = \medskipamount](2) % !!!
\task\fixtask \label{ComposePairsEx-(abcd)(cdhs)}% 
 $f = \{(1,\var{a}), (2,\var{b}), (3,\var{c}), (4,\var{d})\}$,
 \\ $g = \{(\var{a},\clubsuit), (\var{b},\diamondsuit), (\var{c},\heartsuit), (\var{d},\spadesuit) \}$
\task\fixtask \label{ComposePairsEx-(abcd)(cccc)}% 
 $f = \{(1,\var{a}), (2,\var{b}), (3,\var{c}), (4,\var{d})\}$,
 \\ $g = \{(\var{a},\clubsuit), (\var{b},\clubsuit), (\var{c},\clubsuit), (\var{d},\clubsuit) \}$
\task\fixtask \label{ComposePairsEx-(bcda)(cshd)}% 
 $f = \{(1,\var{b}), (2,\var{c}), (3,\var{d}), (4,\var{a})\}$,
 \\ $g = \{(\var{a},\clubsuit), (\var{b}, \spadesuit), (\var{c},\heartsuit), (\var{d}, \diamondsuit) \}$
\task\fixtask \label{ComposePairsEx-(abcd)(cchs)}% 
 $f = \{(1,\var{a}), (2,\var{b}), (3,\var{c}), (4,\var{d})\}$,
 \\ $g= \{(\var{a},\clubsuit), (\var{b},\clubsuit), (\var{c}, \heartsuit), (\var{d}, \spadesuit) \}$
\task\fixtask \label{ComposePairsEx-(abab)(cchs)}% 
 $f = \{(1,\var{a}), (2,\var{b}), (3,\var{a}), (4,\var{b})\}$,
 \\ $g = \{(\var{a},\clubsuit), (\var{b},\clubsuit), (\var{c}, \heartsuit), (\var{d}, \spadesuit) \}$
%\task\fixtask $f = \{(1,\var{a}), (2,\var{b}), (3,\var{c}), (4,\var{d})\}$,
% \\ $g = \{(\var{a},\heartsuit), (\var{b},\clubsuit), (\var{c},\heartsuit), (\var{d},\heartsuit) \}$
\end{tasks}
\end{exers}

\begin{exer} \label{ComposeDomainMatch}
The definition of $g \compose f$ requires that the domain of~$g$ is equal to the codomain of~$f$. (They are both called~$B$ in the definition, so they are required to be equal.) \emph{Why?}
\end{exer}

Here are some examples of proofs that combine composition with other important ideas that we have seen.

\begin{eg} \label{gof11Eg}
Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $g \compose f$ is one-to-one, then $f$ is one-to-one.
\end{eg}

\begin{proof}
Given $a_1,a_2 \in A$, such that $f(a_1) = f(a_2)$, we have
	\begin{align*}
	g \bigl( f(a_1) \bigr) &= g \bigl( f(a_2) \bigr) , \\
\intertext{so}
	(g \compose f)(a_1) &= (g \compose f)(a_2)
	. \end{align*}
Since $g \compose f$ is one-to-one, this implies $a_1 = a_2$. So $f$ is one-to-one.
\end{proof}

\begin{eg} \label{gofontoEg} 
 Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $f$ and~$g$ are onto, then $g \compose f$ is onto.
\end{eg}

\begin{proof}
 Let $c$ be an arbitrary element of~$C$. Since $g$ is onto, there is some $b \in B$, such that $g(b) = c$. Then, since $f$ is onto, there is some $a \in A$, such that $f(a) = b$. Therefore
  \begin{align*}
   (g \compose f)(a) = g\bigl( f(a) \bigr) = g(b) = c 
   . \end{align*}
Since $c$ is an arbitrary element of~$C$, this implies that $g \compose f$ is onto.
\end{proof}

\begin{eg}  \label{ComposegBijEg}
 Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $f$ and $g\compose f$ are bijections, then $g$ is a bijection.
\end{eg}

 \begin{proof}
It suffices to show that $g$ is both one-to-one and onto.

(one-to-one) Let $b_1$ and $b_2$ be arbitrary elements of~$B$, such that $g(b_1) = g(b_2)$. Since $f$ is a bijection, it is onto, so there exist $a_1,a_2 \in A$, such that $f(a_1) = b_1$ and $f(a_2) = b_2$. Then
$$ (g\compose f)(a_1) = g\bigl( f(a_1) \bigr) = g(b_1) = g(b_2) =g \bigl( f(a_2) \bigr) = (g \compose f)(a_2) .$$
Since $g \compose f$ is a bijection, it is one-to-one, so we conclude that $a_1 = a_2$. Therefore
$$ b_1 = f(a_1) = f(a_2) = b_2 .$$
Since $b_1$ and~$b_2$ are arbitrary elements of~$B$, such that $g(b_1) = g(b_2)$, this implies that $g$ is one-to-one.
  
(onto) Let $c$ be an arbitrary element of~$C$. Since $g \compose f$ is a bijection, it is onto, so there exists $a \in A$, such that $(g \compose f)(a) = c$. Let $b = f(a)$. Then
 $$ g(b) = g \bigl( f(a) \bigr) = (g \compose f)(a) = c .$$
 Since $c$ is an arbitrary element of~$C$, we conclude that $g$ is onto.
\end{proof}


 \begin{exers} \label{BijectionComposeExer}
 Suppose $f \colon A \to B$ and $g \colon B \to C$.
 \begin{enumerate}
 \item \label{BijectionComposeExer-gf}
 Show that if $f$ and~$g$ are bijections, then $g \compose f$ is a bijection.
 \item \label{BijectionComposeExer-f}
Show that if $g$ and~$g \compose f$ are bijections, then $f$ is a bijection.
 \item \label{BijectionComposeExer-inverse}
 Show that if $f$ and~$g$ are bijections, then $(g \compose f)^{-1} = f^{-1} \compose g^{-1}$.
 \end{enumerate}
 \end{exers}


\begin{exers} \label{IdCompEx}
Assume $f \colon A \to B$ and $g \colon B \to A$
(and see \cref{IdentityMapDefn} for the definition of the identity maps $\Id_A$ and $\Id_B$).
\begin{problist}
\item \label{IdCompEx-inverse}
Show that $g$ is the inverse of~$f$ if and only if
\ $f \compose g = \Id_B$ \  and \  $g \compose f = \Id_A$.
\item \label{IdCompEx-Iof}
What are $f \compose \Id_A$ and $\Id_B \compose f$?
\end{problist}
\end{exers}

\begin{exers}  \label{CompositionTheoryExers} \ 
\begin{enumerate}
% \item \label{CompositionTheoryExers-gof11} 
% Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $f$ and~$g$ are one-to-one, then $g \compose f$ is one-to-one. 
% \item \label{CompositionTheoryExers-gonto} 
%Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $g \compose f$ is onto, then $g$ is onto.
 \item \label{CompositionTheoryExers-egNotOnto} 
Give an example of functions $f \colon A \to B$ and $g \colon B \to C$, such that $g \compose f$ is onto, but $f$ is \emph{not} onto.
 \hint{Let $A = B = \real$, $C = [0,\infty)$, $f(x) = x^2$, and $g(x) = x^2$.}
% \item \label{CompositionTheoryExers-fonto} 
%Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $g \compose f$ is onto, 
% and $g$~is one-to-one, then $f$ is onto.
% \item  \label{CompositionTheoryExers-g11} 
%Suppose $f \colon A \to B$ and $g \colon B \to C$. Show that if $g \compose f$ is one-to-one, 
% and the range of~$f$ is~$B$, then $g$ is one-to-one.
 \item  \label{CompositionTheoryExers-gNot11} 
Define $f \colon [0,\infty) \to \real$ by $f(x) = x$ and $g \colon \real \to \real$ by $g(x) = |x|$. Show that $g \compose f$ is one-to-one, but $g$ is \emph{not} one-to-one.
 \item \label{CompositionTheoryExers-Defn}
 (\emph{harder}) Suppose $f \colon A \to B$ and $g \colon B \to C$. Write a definition of $g \compose f$ purely in terms of sets of ordered pairs.  That is, find a predicate $P(x,y)$, such that  
 $$g \compose f = \bigset{ (a,c) \in A \times C}{ P(a,c) } .$$
 The predicate cannot use the notation $f(x)$ or $g(x)$.  Instead, it should refer to the ordered pairs that are elements of~$f$ and~$g$.
  \end{enumerate}
\end{exers}



%\begin{exer}  \label{Compose11Ex}
%Suppose $f\colon A \to B$ and $g \colon B \to C$. Show that if 
%$$\mbox{$(g \compose f)(a) = a$, for every $a \in A$,} $$
% then $f$ is one-to-one.
%\end{exer}







\section{Image and pre-image} \label{ImageSect}

It is sometimes necessary to collect together many values of a function. Let us start with a real-world example.

\begin{eg}
Suppose the astronomy club at an elementary school decides to have a Father's Day party. Then they should make a list of all of their fathers, so that invitations can be sent. Mathematically speaking, they want to make a set that contains precisely the people who are the father of someone in the club. That is, if $A_1$ is the set of people in the club, then they are interested in
	$$ \bigset{ x }{ \exists a \in A_1,   \bigl( x = \var{father}(a) \bigr) } .$$
Another way of thinking of this is that they should apply the $\var{father}$ function to every element of the set~$A_1$, and gather all of the resulting values into a set. The mathematical notation for this set that gathers together the values is
	$$  \{\, \var{father}(a) \mid a \in A_1 \,\}  .$$
In English, we could call this set ``the fathers of the elements of~$A_1$\rlap,'' but mathematicians abbreviate this to ``$\var{father}(A_1)$\rlap.''
In summary, the same set has three names:
	$$ \var{father}(A_1) = \{\, \var{father}(a) \mid a \in A_1 \,\} = \bigset{ x }{ \exists a \in A_1,   \bigl( x = \var{father}(a) \bigr) } .$$
\end{eg}

A similar idea can be applied to any function $f \colon A \to B$. Namely, if $A_1 \subset A$, then we can apply~$f$ to every element of the set~$A_1$, and  gather all of the resulting values into a set. We call this set $f(A_1)$.

\begin{defn} \label{ImageDefn}
Suppose $f \colon A \to B$, and $A_1 \subset A$. The \define{image} of $A_1$ under~$f$ is
$$ f(A_1) = \bigset{\vphantom{\big|} f(a) }{ a \in A_1 } 
\nindex{$f(A_1)$}
\nindex{$\bigset{\vphantom{\big|} f(a) }{ a \in A_1 } $}
.$$
It is a subset of~$B$. The notation means that, for all~$x$, we have
	$$ x \in f(A_1) \quad \eiff \quad \exists a \in A_1, \bigl( x = f(a) \bigr) .$$
\end{defn}

\begin{rem}
We can take the image of any subset of the domain of~$f$, and the result will be some subset of the range of~$f$. In the special case where we take the entire domain of~$f$ as our set~$A_1$, we obtain the entire range of~$f$ as the image.
\end{rem}

You are expected to be able to combine the definition of ``image'' with the proof techniques that you already know.

\begin{eg}
Assume $f \colon A \to B$. 
Show that if $A_1$ and~$A_2$ are subsets of~$A$,
and $f$ is one-to-one, then \  $f(A_1) \cap f(A_2) \ \subset \ f(A_1 \cap A_2)$.
\end{eg}

\begin{proof}
Given $b \in f(A_1) \cap f(A_2)$, we know $b \in f(A_1)$ and $b \in f(A_2)$. Therefore, since $b \in f(A_1)$, we know there is some $a_1 \in A_1$, such that $b = f(a_1)$. Also, since $b \in f(A_2)$, we know there is some $a_2 \in A_2$, such that $b = f(a_2)$. Then
	$$ f(a_1) = b = f(a_2) .$$
Since $f$ is one-to-one, this implies $a_1 = a_2 \in A_2$. Since we also know that $a_1 \in A_1$, this implies $a_1 \in A_1 \cap A_2$. So $f(a_1) \in f(A_1 \cap A_2)$. Since $b = f(a_1)$, this means $b \in f(A_1 \cap A_2)$. Since $b$ is an arbitrary element of $f(A_1) \cap f(A_2)$, we conclude that $f(A_1) \cap f(A_2) \subset f(A_1 \cap A_2)$.
\end{proof}

\begin{exers} \label{ImgEx}
Assume $f \colon A \to B$.
\begin{problist}
\item \label{ImgEx-f(A2)inf(A1)}
Show that if $A_1$ and~$A_2$ are subsets of~$A$, such that $A_2 \subset A_1$, then $f(A_2) \subset f(A_1)$.
\item \label{ImgEx-f(a)inf(A_1)}
Assume $f$ is one-to-one, and $a \in A$. Show that if $f(a) \in f(A_1)$, then $a \in A_1$.
\end{problist}
\end{exers}

Taking the image of a subset of the domain yields a subset of the codomain. Sometimes we need to go the other direction.

\begin{eg}
Perhaps we would like to make a list of all the people whose father is a friend of the pop singer Bono. If $B_1$ is the set of Bono's friends, then the mathematical notation for the set of these people is
	$$ \{\, x \in \var{PEOPLE} \mid \var{father}(x) \in B_1 \,\} .$$
Notice that if the \var{father} function had an inverse, then the same set could be obtained by applying $\var{father}^{-1}$ to the elements of~$B_1$. That is, the set would be $\var{father}^{-1}(B_1)$. Mathematicians use this notation for the set even if there is no inverse function.
\end{eg}

\begin{defn} \label{PreimageDefn}
Suppose $f \colon A \to B$, and $B_1 \subset B$. The \define[pre-image|indsee{inverse image}]{pre-image} (or \define[inverse!image]{inverse image}) of $B_1$ under~$f$ is
$$ f^{-1}(B_1) = \bigset{\vphantom{\big|} a \in A }{ f(a) \in B_1 } 
\nindex{$f^{-1}(B_1)$}
.$$
It is a subset of~$A$. When $B_1 = \{b\}$ has only one element, we usually write $f^{-1}(b)$, instead of $f^{-1} \bigl( \{b\} \bigr)$.
\end{defn}

\begin{warn}
The fact that we write $f^{-1}(B_1)$ does not imply that $f$ has an inverse, or that $f^{-1}$ is a function. This is simply a notation that refers to the set we have defined.
\end{warn}

\begin{eg} \ 
\begin{enumerate}
\item For the function $\var{mother} \colon \var{PEOPLE} \to \var{WOMEN}$, $\var{mother}^{-1}(m)$ is the set of all children of~$m$.
\item For the function $f \colon \real \to \real$ defined by $f(x) = x^2$:
\begin{enumerate}
\item We have $f^{-1}(4) = \{2,-2\}$, because $2$ and~$-2$ are all of the square roots of~$4$.
\item We have $f^{-1} \bigl( [0,4] \bigr) = [-2,2]$, because $0 \le x^2 \le 4$ iff $-2 \le x \le 2$.
\end{enumerate}
\end{enumerate}
\end{eg}

Here are examples of proofs involving inverse images:

\begin{eg} \label{InvImgContainEg}
Suppose $f \colon A \to B$ and $B_1 \subset B$.
\begin{multicols}{2}
\begin{enumerate}
\item \label{InvImgContainEg-f(f(B1))inB1}
 We have $f \bigl( f^{-1}(B_1) \bigr) \subset B_1$.
\item \label{InvImgContainEg-f(f(B1))=B1}
 If $f$ is onto, then $f \bigl( f^{-1}(B_1) \bigr) = B_1$.
\end{enumerate}
\end{multicols}
\end{eg}

\begin{proof}
\pref{InvImgContainEg-f(f(B1))inB1} Let $b \in f \bigl( f^{-1}(B_1) \bigr)$. By definition, we have
	$$ f \bigl( f^{-1}(B_1) \bigr) = \bigset{ f(a) }{ a \in f^{-1}(B_1) } ,$$
so we must have $b =  f(a_1)$, for some $a_1 \in f^{-1}(B_1)$. From the definition of $f^{-1}(B_1)$, we know that $f(a_1) \in B_1$. Therefore $b = f(a_1) \in B_1$. Since $b$ is an arbitrary element of $f \bigl( f^{-1}(B_1) \bigr)$, this implies that $f \bigl( f^{-1}(B_1) \bigr) \subset B_1$, as desired.

\smallskip
\pref{InvImgContainEg-f(f(B1))=B1} Assume $f$ is onto. We know, from~\pref{InvImgContainEg-f(f(B1))inB1}, that $f \bigl( f^{-1}(B_1) \bigr) \subset B_1$, so it suffices to show that $B_1 \subset f \bigl( f^{-1}(B_1) \bigr)$. 

Let $b \in B_1$ be arbitrary. Because $f$ is onto, we know there exists $a_1 \in A$, such that $f(a_1) = b$. Then $f(a_1) = b \in B_1$, so $a_1 \in  f^{-1}(B_1)$. Therefore
	$$ f(a_1) \in \bigset{ f(a) }{ a \in f^{-1}(B_1) } = f \bigl( f^{-1}(B_1) \bigr) .$$
Since $f(a_1) = b$, we conclude that $b \in f \bigl( f^{-1}(B_1) \bigr)$.
Since $b$ is an arbitrary element of~$B_1$, this implies that $B_1 \subset f \bigl( f^{-1}(B_1) \bigr)$, as desired.
\end{proof}



 

\begin{exers} \label{InverseImgEx}
Suppose that $f \colon A \to B$, that $A_1 \subset A$, and that $B_1 \subset B$.
%\begin{multicols}{2}
\begin{enumerate}
\item \label{InverseImgEx-finv(B2)infinv(B1)}
 Show that if $B_2 \subset B_1$, then $f^{-1}(B_2) \subset f^{-1}(B_1)$.
\item \label{InverseImgEx-Ainf(f(A))}
 Show $A_1 \subset f^{-1} \bigl( f(A_1) \bigr)$.
%\item \label{InverseImgEx-A1=}
% Show that if $f$ is one-to-one, then $A_1 = f^{-1} \bigl( f(A_1) \bigr)$.
% \item \label{InverseImgEx-onetoone} % from Fall 2010 Midterm Exam
% Let $a \in A$. Show that if $f$ is one-to-one, and $f(a) \in f(A_1)$, then $a \in A_1$.
%\item \label{InverseImgEx-=f(A1)}
% Show $f \Bigl( f^{-1} \bigl( f(A_1) \bigr) \Bigr) = f(A_1)$.
 \end{enumerate}
% \end{multicols}
\end{exers}


\begin{exer} \label{IntersectionOfInverseImg} % modified from Fall 2010 Midterm
Assume \  $f \colon X \to Y$, \  $A \subset Y$, \ and \ $B \subset Y$. 
\quad Show  
	$$f^{-1}(A) \cap f^{-1}(B)  = f^{-1}(A \cap B) .$$
\end{exer}

\begin{exer}  \label{ginv(Z1)Ex}
 Assume
	\  $f \colon X \to Y$, \  $g \colon Y \to Z$,
	\  $X_1 \subset X$, \  $Z_1 \subset Z$,
	\ and \ 
	 $(g \circ f)(X_1) \subset Z_1$.%
\\Show $f(X_1) \subset g^{-1}(Z_1)$.
\end{exer}






\filbreak
\vbox{%
\begin{summary}
%\item A function accepts inputs, and provides a single output for each input.
%%\item The set of allowable inputs is called the domain of the function.
%\item Some ways of representing functions are:
%\begin{itemize}
%\item a formula;
%\item a table;
%\item a set of ordered pairs;
%\item an arrow diagram.
%\end{itemize}
\medskip \itemsep=\bigskipamount

\item Important definitions:
\medskip
\begin{multicols}{3}
\begin{itemize}
\item Cartesian product %$A \times B$
\item function
\item domain
\item codomain, range
\item one-to-one
\item onto
\item bijection
\item identity map % $\Id_A$
\item inverse function
\item composition % of functions % $(g \compose f) (x)= g\bigl(f(x)\bigr)$
\item image
\item pre-image
\end{itemize}
\end{multicols}

\item Notation:
\medskip
\begin{multicols}{4}
\begin{itemize}
\item $A \times B$
\item $f \colon A \to B$
\item $f(a)$
\item $\forall a_1, a_2 \in A$ % means $\forall a_1 \in A, \forall a_2 \in A$.
\item $\Id_A$ % (identity map)
\item $f^{-1}$
\item $g \compose f$
\item $\{\, f(a) \mid a \in A \,\}$
\item $f(A_1)$
\item $f^{-1}(B_1)$
\end{itemize}
\end{multicols}

\item A function $f \colon A \to B$ has an inverse $f^{-1} \colon B \to A$ iff $f$ is a bijection.

\item The inverse of a bijection is a bijection.

%\item well-defined !!!

\end{summary}
}
 