\documentclass[11pt]{article}

\usepackage{precalc}
\usepackage{graphicx}

\begin{document}

\assigntitle{2}{Functions and Relations}

This week we will examine the concept of a \term{function}, a
fundamental concept underlying all of modern mathematics.  You're
undoubtedly already familiar with functions in an intuitive sense: a
function is something which, given an input, produces an output.
But you've probably never seen the formal definition of a function as
it relates to set theory, which is what we'll look at this week.  

A roadmap for this week: functions are defined as special sorts of
\term{relations}; relations, in turn, are defined in terms of the
\term{Cartesian product} of sets.  After we define what a function is,
we'll look at several other related concepts, including
\term{one-to-one} or \term{injective} functions, \term{onto} or
\term{surjective} functions, \term{bijections}, function
\term{composition}, and \term{inverses}.

\section{Preliminaries}

\subsection{Subsets}

You can probably guess what it means for one set to be a \term{subset}
of another: it just means that the first set is contained within the
second.  More formally:

\begin{defn}{subset, $\subseteq$}
A set $S$ is a \term{subset} of a set $T$, written $S
\subseteq T$, if every element of $S$ is also an element of $T$.
\end{defn}

\pref{fig:subset} shows a graphical representation of two sets, one of
which is a subset of the other.

\begin{figure}[htp]
  \begin{center}
    \includegraphics{diagrams/subset.eps}
  \end{center}
  \caption{$S \subseteq T$} \label{fig:subset}
\end{figure}

\begin{problem}
  Given the sets
  \begin{align*}
    A &= \{1,2,5\} \\
    B &= \{2,5\} \\
    C &= \Z \\
    D &= \Z \setminus \{1\} \\
    E &= \{9.5, 2, 5\},
  \end{align*}
  list all the subset relationships among them.
\end{problem}

\begin{problem}
  Suppose $X \subseteq Y$ and $Y \subseteq X$.  In this situation,
  what else can you say about $X$ and $Y$?
\end{problem}

\begin{problem}
  List all the subsets of $\{1,2,3\}$. (Note: $\emptyset$ counts as a
  subset of every set; every element of $\emptyset$ is also an element
  of every other set, for the same reason that every person who is
  more than thirteen feet tall lives on the moon.)  The set of all
  subsets of a set $S$ is called the \term{power set} of $S$, denoted
  $\mathcal{P}(S)$.
\end{problem}

\begin{problem}
  In general, how many different subsets does a set of cardinality $n$
  have?  (\emph{Hint}: try some small examples and look for a
  pattern.)  Can you explain why this is true?
\end{problem}

\subsection{Cartesian product}

Next, we need to define the \term{Cartesian product} of two sets.
Informally, the Cartesian product gives all possible ways to pair up
an element of one set with an element of another.

\begin{defn}{Cartesian product, $\times$}
The \term{Cartesian product} of two sets $S$ and $T$, denoted $S
\times T$, is the set of all ordered pairs $(s,t)$ where $s \in S$
and $t \in T$: \[ S \times T = \{ (s,t) \suchthat s \in S \text{ and }
t \in T \}. \] \vspace{-2em}
\end{defn}

For example, \[ \{1,2,3\} \times \{5,6\} = \{(1,5), (1,6), (2,5),
(2,6), (3,5), (3,6)\}. \]

As an aside, note that something like $(1,5)$ can mean two things: it
can represent the ordered pair containing $1$ and $5$, or it can
represent the interval of real numbers between (but not including) $1$
and $5$.  Annoying, perhaps, but usually it's very clear from context
which notation is meant.

\begin{problem}
  What is $\{c,a,t\} \times \{h,a,t\}$?
\end{problem}

\begin{problem}
  Assuming $S$ and $T$ are finite sets, how is the cardinality of $S
  \times T$ related to the cardinalities of $S$ and $T$?
\end{problem}

\begin{problem}
  True or false: if $A \subseteq X$ and $B \subseteq Y$, then $A
  \times B \subseteq X \times Y$.  If true, explain why; if false,
  give a \term{counterexample} (some particular sets $A$, $B$, $X$,
  and $Y$ for which $A \subseteq X$ and $B \subseteq Y$ but $A \times
  B$ is \emph{not} a subset of $X \times Y$).
\end{problem}

\subsection{Relations}

A \term{relation} specifies a certain relationship between two sets.
Formally, a relation is just a subset of the Cartesian product:

\begin{defn}{relation}
  Let $S$ and $T$ be sets. A \term{relation} on $S$ and $T$ is a
  subset of $S \times T$.  $S$ is called the \term{domain} of any such
  relation, and $T$ is the \term{codomain}.
\end{defn}

\topic{interpreting relations}
``How exactly does a subset of the Cartesian product specify a
relationship between two sets?'' you may ask.  The idea is that
the subset tells you which pairs of elements have a specific
relationship to one another.  For example, suppose we have the sets
\begin{align*}
  P &= \{ \text{Arnold}, \text{Bertha}, \text{Celeste} \} \\
  F &= \{ \text{spinach}, \text{turnips}, \text{ugli fruit},
  \text{vermicelli} \}
\end{align*}

Then one possible relation on these sets, with $P$ as the domain and
$F$ as the codomain, would be (abbreviating
elements of $P$ and $F$ by their first letters): \[ \{(A, s), (A, u),
(C, v), (C, s) \}.  \]  We could think of this relation as specifying
who likes what kinds of food.  In this case, Arnold likes ugli fruit,
Celeste likes vermicelli, Arnold and Celeste both like spinach, no one
likes turnips, and Bertha doesn't like anything. An illustration of
this relation is shown in \pref{fig:relation}.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/relation.eps}
  \caption{A relation on $P$ and $F$}
  \label{fig:relation}
\end{figure}

As another example, ``less than or equal to'' is a familiar relation
on $\Z$. (Note: by saying it is a ``relation on $\Z$'' we mean that
$\Z$ is both the domain and the codomain.) Here are a few elements of
this relation: \[ \{ (0,0), (0,1), (0,2), (1,2), (3,19), (-49,4),
\dots \} \] This relation is infinite, of course; it simply consists
of all pairs of integers where the first is less than or equal to the
second. \[ \{ \leq \} = \{ (a,b) \suchthat a,b \in \Z, a \leq b \}
\subseteq \Z \times \Z. \]

\begin{problem}
  Give an example of a relation on $\Z$ and $\{x,y\}$.
\end{problem}

\begin{problem}
  Given $S = \{\text{states in the US}\}$ and $A = \{\text{letters of
    the alphabet}\}$, give two different examples of a relation on $S$
  and $A$.  For each relation, show at least three pairs which are in
  the relation.
\end{problem}

\section{Functions}

A \term{function} also specifies a relationship between two sets, so
functions are also relations.  However, the kind of relationship that
a function represents is a very specific kind of relation.

\topic{functions as input-output machines}
A function represents an input-output machine: you put in an input
(then optionally push a red button and watch the blinky lights),
and get a corresponding output (\pref{fig:io-machine}).  A general
  relation isn't a suitable model for an input-output machine for two
  reasons: there might be some inputs for which there is no output
  (Bertha, for example), or there might be some inputs for which there
  is more than one output (Arnold, for example).  So we will define a
  function as a relation which doesn't have these problems.

  \begin{figure}[htp]
    \centering
    \includegraphics{diagrams/io-machine.eps}
    \caption{An input-output machine}
    \label{fig:io-machine}
  \end{figure}

\begin{defn}{function}
  A \term{function} is a relation with the property that for every
  element $x$ of the domain, there is \emph{exactly one} pair $(x,y)$
  in the relation.
\end{defn}

In other words, given a function $f$ and any element $x$ of the domain
as input, we are guaranteed to find exactly one element $y$ from the
codomain paired with $x$.  In this case, we write $f(x) = y$.  We also
say that $f$ \term{maps} or \term{sends} $x$ to $y$.

\pref{fig:function} shows an example of a function with the same
domain $P$ and codomain $F$ as the previous example.
This function specifies each person's favorite food among the
available options.  Everyone can only have one favorite food, and even
someone who doesn't like any of the foods still has one they hate the
least.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/function.eps}
  \caption{The ``favorite food of'' function}
  \label{fig:function}
\end{figure}

\subsection{Domain, Codomain, and Range}

You already know what the \term{domain} of a function is: it is the set of
possible inputs to the function.

\topic{codomain and range} You also know what the \term{codomain} of a
function is, and you've probably also heard the term \term{range}
used. It's very important not to get \term{codomain} and \term{range}
mixed up!  The \term{range} is the set of \emph{all actual output
  values} from the function, and the \term{codomain} is the set
\emph{from which the output values are chosen}.  There can be elements
in the codomain which are not elements of the range, if there are no
input values which give them as outputs.  Of course, the range must
always be a \emph{subset} of the codomain.

\begin{problem}
  What is the codomain of the ``favorite food of'' function shown
  above?  What is the range?
\end{problem}

If a function $f$ has domain $A$ and codomain $B$, we write it as $f
: A \to B$.

\subsection{Injections, surjections, and bijections, oh my!}

There are three important categories of special functions you should
know about: \term{injections}, \term{surjections}, and \term{bijections}.

\subsubsection{Injections}

An \term{injection} is a function which sends every input to a
separate output; that is, no two elements of the domain map to the
same element of the codomain.  An \term{injection} is also called an
\term{injective} or \term{one-to-one (1-1)} function.
\pref{fig:injection} shows an illustration of an injection.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/injection.eps}
  \caption{An injection: no two elements of $A$ are sent to the same
    element of $B$.}
  \label{fig:injection}
\end{figure}

\begin{defn}{injection}
  A function $f : A \to B$ is an \term{injection} if, for any $x,y \in
  A$, $f(x) = f(y)$ implies that $x = y$.
\end{defn}

You should take a minute to think about how this formal definition
corresponds to the intuitive description above it.  Essentially, the
formal definition says that the only way for an injection to send $x$
and $y$ to the same output is if $x$ and $y$ were equal in the first
place---which is the same as saying that if $x$ and $y$ \emph{aren't}
equal, then $f$ \emph{won't} send them to the same output.  This
formal definition illustrates a good way to prove that a function is
injective: assume that $f(x) = f(y)$, and show that this must mean $x
= y$.

\begin{problem}
  Suppose $f : A \to B$ is an injection.  What can you say about the
  cardinalities of $A$ and $B$?
\end{problem}

\subsubsection{Surjections}

A \term{surjection} is a function whose range is equal to its
codomain; in other words, every element of the codomain is the output
of the function for at least one input. A \term{surjection} is also
called a \term{surjective} or \term{onto}
function. \pref{fig:surjection} shows an illustration of a surjection.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/surjection.eps}
  \caption{A surjection: the range is the entire codomain.}
  \label{fig:surjection}
\end{figure}

\begin{defn}{surjection}
  A function $f : A \to B$ is a \term{surjection} if for every $y \in
  B$, there is at least one $x \in A$ for which $f(x) = y$.
\end{defn}

You can use the formal definition to prove that a function is a
surjection: let $y$ stand for any element of the codomain, and show
how to find some element $x$ of the domain for which $f(x) = y$.

\begin{problem}
  Suppose $f : A \to B$ is a surjection.  What can you say about the
  cardinalities of $A$ and $B$?
\end{problem}

\subsubsection{Bijections}

Once you know what injections and surjections are, bijections are very
simple:

\begin{defn}{bijection}
  A \term{bijection} is a function which is both injective and
  surjective (one-to-one and onto).
\end{defn}

A bijection is also sometimes called a \term{one-to-one
  correspondence}.  A bijection matches up each element of the domain
with one element of the codomain, and vice versa.  No element of the
codomain is matched with more than one element of the domain (since it
is injective), and no element of the codomain is left out (since it
is a surjective).  \pref{fig:bijection} illustrates this idea.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/bijection.eps}
  \caption{A bijection: the elements of the domain and codomain are perfectly matched up in pairs.}
  \label{fig:bijection}
\end{figure}

\begin{problem}
  Suppose $f : A \to B$ is a bijection.  What can you say about the
  cardinalities of $A$ and $B$?
\end{problem}

\begin{problem}
  For each function, say whether it is an injection, a surjection, a
  bijection, or none of the above, and give the domain, codomain, and
  range.  Justify your answers.
  \begin{subproblems}
    \item $f : \Z \to \Z$, $f(x) = x + 1$
    \item $g : \Z \to \R$, $g(x) = x + 1$
    \item $h : \Z \to \Z$, $h(x) = x^2$
    \item the function with the set of all triangles having area
      $1$ as its domain and $\Z$ as its codomain, which sends each
      triangle to the sum of its angles in degrees
    \item Let $S = \{1,2,3,4,5\}$; then $k : \mathcal{P}(S) \setminus
      \{\emptyset\} \to S$ is the function which sends each nonempty
      subset of $S$ to its largest element
    \item $m : \Q \to \Q$, $m(x) = 1 + 1/x$
  \end{subproblems}
\end{problem}

\begin{problem}
  For each item, write down a function with the given characteristics,
  or state that no such function exists.  Justify your answers.
  \begin{subproblems}
    \item an injection $\Z \to \Z$ which is not a surjection
    \item a surjection $\Z \to \Z$ which is not an injection
    \item a bijection $\Z \to \Z$
    \item a function $\R \to \Z$ which is neither an injection nor a surjection
    \item a surjection with domain the set of states in the USA and
      codomain countries of the world
  \end{subproblems}
\end{problem}

\subsection{Function composition}

You've probably learned about function composition before: it's just
putting two functions (input-output machines) together to make one big
function (input-output machine), as shown in \pref{fig:composition}.

\begin{figure}[htp]
  \centering
  \includegraphics{diagrams/composition.eps}
  \caption{Composing two functions.}
  \label{fig:composition}
\end{figure}

\begin{defn}{function composition, $\circ$}
  Given functions $f : A \to B$ and $g : B \to C$, we can
  \term{compose} $g$ with $f$ to form the composite function $g \circ
  f : A \to C$, defined by $(g \circ f)(x) = g(f(x))$.
\end{defn}

Note that for $g \circ f$ to make any sense, the codomain of $f$ must
be the same as the domain of $g$.  Otherwise, we could not use the
output of $f$ as input to $g$.

\topic{composition notation} Be careful: the notation for composition
can be a bit confusing, since from one perspective it seems
``backwards'': $g \circ f$ means to apply first $f$, then $g$.  It
makes sense, though, if you think of the way we normally write
function application, $f(x)$, with the function on the \emph{left} and
the input on the \emph{right}.  Therefore, we write $(g \circ f)(x) =
g(f(x))$.  That's also why \pref{fig:composition} shows the input on
the right and output on the left.

\begin{problem}
  True or false: if $f$ and $g$ are injections, so is $g \circ f$.
\end{problem}

\begin{problem}
  Given $f : \R \to \R$ defined by $f(x) = \sqrt{x^2 + 7}$, and $g :
  \R \to \R$ defined by $g(x) = 3x + 1$, what is $(g \circ f)(3)$?
  What is $(f \circ g)(3)$?
\end{problem}
\subsection{Inverse functions}

\topic{reversed IO-machines}
Often we want to take an input-output machine (function) and put it in
reverse, so that output becomes input.  Such reversed machines answer
the question, ``what would I have to input in order to get \emph{this}
as output?''  If you put a value $x$ into a function $f$ and get out
$y$, and then put $y$ into the inverse of $f$, you get out $x$,
exactly what you started with.

\begin{defn}{inverse function}
Given a function $f : A \to B$, its \term{inverse}, if it exists, is a
function denoted $f^{-1}$ with the property that $f^{-1} \circ f : A
\to A$ is the identity function; that is, $(f^{-1} \circ f)(x) = x$,
for all values of $x$.
\end{defn}

Inverse functions are often useful in solving equations involving a
function application.  For example, given the equation $f(p) = q$, we
can apply $f^{-1}$ to both sides to obtain
\begin{equation*}
  \begin{split}
    f(p) &= q \\
    f^{-1}(f(p)) &= f^{-1}(q) \\
    p &= f^{-1}(q)
  \end{split}
\end{equation*}
The key step to note is that $f^{-1}(f(p)) = p$, by definition of $f^{-1}$.

\begin{problem}
  Not all functions have inverses.  What must be true about a function
  $f$ to guarantee that it has a valid inverse function?  (It should
  be noted that a lot of math textbooks get this wrong, because they
  are confusing codomain and range!)
\end{problem}

\begin{problem}
  Find the inverse of each function, or explain why it doesn't have
  one.
  \begin{subproblems}
    \item $f : \Z \to \Z$, $f(x) = x + 3$
    \item $c : \Q \to \Q$, $c(t) = 9t/5 + 32$
    \item $h : \R \to \R$, $h(x) = x^2$
    \item $j : [0,\infty) \to [0, \infty)$, $j(x) = x^2$
  \end{subproblems}

  \begin{problem}
    Can a function be its own inverse?  If yes, give an example; if
    no, explain why not.
  \end{problem}
\end{problem}

\subsection{Real-valued functions}

\topic{graphing functions $\R \to \R$}
Functions that have the real numbers $\R$ as their domain and codomain
are special, since they can be \emph{graphed} in a way that is
certainly familiar to you.  Let's explore the relationship between
graphs of functions on $\R$ and some of the other concepts in this
assignment.

\begin{problem}
  How can you tell whether a function is one-to-one by looking at its graph?
\end{problem}

\begin{problem}
  How can you tell whether a function is onto by looking at its graph?
\end{problem}

\begin{problem}
  How are the graphs of a bijection and its inverse related?
\end{problem}

\end{document}