\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{enumerate}

\usepackage{hyperref}

\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}

\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.35in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.7in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}


\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

\newcommand{\LEMMA}{\vspace{0.05in} \noindent \fbox{\large\bf Lemma:}  }
\newcommand{\COR}{\vspace{0.05in} \noindent \fbox{\large\bf Corollary:}  }
\newcommand{\DEF}{\vspace{0.05in} \noindent \fbox{\large\bf Definition:}  }
\newcommand{\THM}{\vspace{0.05in} \noindent \fbox{\large\bf Theorem:}  }
\newcommand{\PROP}{\vspace{0.05in} \noindent \fbox{\large\bf Proposition:}  }
\newcommand{\EX}{\vspace{0.05in} \noindent \fbox{\large\bf Example:}  }
\newcommand{\bproof}{\vspace{0.1in} \noindent {\bf Proof:} }
\newcommand{\eproof}{$\blacksquare$ \vspace{0.05in}}

\newcommand{\id}[1]{{\mathrm{id}_{#1}}}
\newcommand{\idA}{\id{A}}
\newcommand{\idB}{\id{B}}

\begin{document}

\pagestyle{empty}

\noindent
{\bf Math 2110}
\hfill \parbox{5in}{\large\bf \force \hfill Some Function Facts \hfill \force} \hfill 
{\bf Tech. of Proof}

\vspace{0.1in}

Let $A$ and $B$ be sets and $f: A \to B$ be some function. Note: If $A=\emptyset$, then $f:\emptyset \to B$ must send nothing nowhere. This is the only function with domain $\emptyset$ and codomain $B$. It is called the {\bf empty function}. If $B = \emptyset$ and $A \not= \emptyset$, then there is no function $f:A \to B$ (since the elements of $A$ have nowhere to go). Thus a function whose codomain is empty must also have an empty domain. Confusing but true. For what follows we will {\it assume that $A$ and $B$ are non-empty}.

\vspace{0.05in}

Recall that $\idA:A \to A$ is the {\bf identity function} where $\idA(x)=x$ for all $x \in A$. We say that $f$ has a {\bf left inverse} $g:B \to A$ if  $g \circ f = \idA$ and $f$ has a right inverse $h:B \to A$ if $f \circ h = \idB$. Since function composition is associative, if $f$ has a left inverse $g$ and right inverse $h$, then $g = g \circ \idB = g \circ (f \circ h) = (g \circ f) \circ h = \idA \circ h = h$. Thus if $f$ has both a left and right inverse, they must match. We call such a two-sided inverse (which we just proved is unique) {\it the} {\bf inverse} of $f$ and denote it by $f^{-1}$.

\vspace{0.05in}

\PROP Let $f: A \to B$ (where $A$ and $B$ are non-empty).
\begin{enumerate}[i)]
\item The function $f$ has a left inverse if and only if it is injective (i.e., one-to-one).
\item The function $f$ has a right inverse if and only if it is surjective (i.e., onto).
\item The function $f$ has an inverse if and only if it is bijective (i.e., one-to-one and onto).
\end{enumerate}

\bproof
\begin{enumerate}[i)]
\item Suppose $f$ has a left inverse $g:B \to A$ and suppose that $f(a)=f(b)$ for some $a,b \in A$. Then $a=\idA(a) = (g\circ f)(a) = g(f(a))=g(f(b)) = (g \circ f)(b) = \idB(b)=b$. Thus $f$ is injective. 

Now suppose $f$ is injective. Pick some $a_0 \in A$ ($A$ is non-empty so this is possible). Next, consider any element $y$ in the range of $f$. Then there is some $x \in A$ such that $f(x)=y$ (this is what it means to belong to the range of $f$). Notice that if $f(x)=y=f(x')$ then $x=x'$ since $f$ is one-to-one. Therefore, for any element $y$ in the range of $f$, there is a {\it unique} element $x \in A$ such that $f(x)=y$. Call this element $x=f^{-1}(y)$. Now define $g:B \to A$ as follows:
$$ g(y) = \left\{ \begin{array}{ccc} f^{-1}(y) & & y \text{ is in the range of } f\\ a_0 & & y \text{ is not in the range of }  f\end{array}\right.$$
Finally, notice that $g(f(x))=f^{-1}(f(x))=x$ where we use the first formula in $g$ since $f(x)$ belongs to the range of $f$ and $f^{-1}(f(x))=x$ by the way we defined what ``$f^{-1}(y)$'' means (it is the element that maps to $y$ by $f$ -- certainly $x$ is the element that maps to $f(x)$ by $f$). Therefore, $g \circ f = \idA$ so that $g$  is a left inverse for $f$.

\item Suppose that $f$ has a right inverse $h:B \to A$ and suppose $y \in B$. Then $h(y) \in A$ and $f(h(y))=\idB(y)=y$. Therefore, $y$ is in the range of $f$ and thus $f$ is surjective (i.e., onto). 

Now suppose $f$ is surjective. For each $b \in B$, we know that $b$ is in the range of $f$ (because it's onto). Thus we can choose some $a \in A$ such that $f(a)=b$. We (arbitrarily) choose such an input for each $b$. Let's name our choice $a_b$ (so $a_b \in A$ and $f(a_b)=b$). Now define $h:B \to A$ as follows: $h(b)=a_b$.  Since we chose exactly one $a_b$ for each $b \in B$, we have a well defined function $h$. Then $(f \circ h)(y)=f(h(y))=f(a_y)=y=\idB(y)$ for all $y \in B$. Therefore, $f \circ h= \idB$ and thus $h$ is a right inverse of $f$.

\item We now know that $f$ has an inverse if and only if it has a left and right inverse if and only if it is both injective and surjective if and only if it is bijective.
\end{enumerate}
\eproof

\vspace{0.05in}

\noindent
Without proof I will state the following (easy to prove) proposition:

\vspace{0.05in}

\PROP Let $f:A \to B$ and $g:B \to C$.
\begin{enumerate}[i)]
\item If both $f$ and $g$ are injective, then $g \circ f$ is too.
\item If both $f$ and $g$ are surjective, then $g \circ f$ is too.
\item If both $f$ and $g$ are bijective, then $g \circ f$ is too. Moreover, $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.
\end{enumerate}

\newpage

\DEF Let $f:A \to B$. Then we {\it induce} two functions on the powersets of $A$ and $B$. 
\begin{itemize}
\item $f:\mathcal{P}(A) \to \mathcal{P}(B)$ where given any $C \subseteq A$ we define $f(C) = \{ f(x) \;|\; x \in C \}$. We call $f(A)$ the {\bf image} of $C$ under the function $f$.
\item $f^{-1}:\mathcal{P}(B) \to \mathcal{P}(A)$ where given any $D \subseteq B$ we define $f^{-1}(D) = \{ x \in A \;|\; f(x) \in D \}$. We call $f^{-1}(D)$ the {\bf inverse image} or {\bf preimage} of $D$ under the function $f$.
\end{itemize}

Let me emphasize: The preimage is defined regardless of whether $f$ has an inverse or not! Keep in mind that by definition: $x \in f^{-1}(D)$ if and only if $f(x)\in D$.

\vspace{0.05in}

The first thing to acknowledge is that many people find this notation confusing. This is a classical {\it abuse of notation}. We are using $f$ for both the name of the original function and for a new function between powersets. Also, $f^{-1}$ is being used as a new function between powersets when the original function may not even have an inverse! In fact, if $f$ does have an inverse (i.e., it is bijective), then $f^{-1}(D)$ has two different meanings. It could mean the image of $D$ under $f^{-1}$ or the preimage of $D$ under $f$. In the end, this is ok since in the case that $f$ has an inverse, these sets are the same.

Quick proof: Suppose $f$ is invertible. Let $D \subseteq B$, let $M$ be the image of $D$ under $f^{-1}$ and $N$ be the preimage of $D$ under $f$. Suppose $x \in M$. Then because $M$ is the image of $D$ under $f^{-1}$, there exists some $y \in D$ such that $f^{-1}(y)=x$. Therefore, $y=f(x)$ and so $x \in N$ since $f(x)=y \in D$. Conversely, let $x \in N$. Then by definition, $f(x) \in D$ and so $x = f^{-1}(f(x))$ is the image under $f^{-1}$ of the element $f(x)$ in $D$. Thus $x \in M$. Therefore, $x \in M$ if and only if $x \in N$ (i.e., $M=N$).

The range of a function is the set of all outputs. This is the same as the image of the domain. The range is thus denoted in a bunch of different ways: $\mathrm{range}(f) = \mathrm{image}(f) = f(A)$ (and others). 

\vspace{0.05in}

\EX Consider the function $f:\{a,b,c\} \to \{1,2,3,4\}$ where $f(a)=1$, $f(b)=2$, and $f(c)=2$. Then $f(\{a,c\}) = \{f(a),f(c)\} = \{1,2\}$. Also, $f(\{a,b,c\})=\{f(a),f(b),f(c)\} = \{1,2\}$. This means that the range of $f$ is $\{1,2\}$. We could also consider the other extreme case, $f(\emptyset) = \emptyset$ (nothing maps to nothing). On the other hand, $f^{-1}(\emptyset) = \{ x \in \{a,b,c\} \;|\; f(x) \in \emptyset \} = \emptyset$ (only nothing maps to nothing). Consider $f^{-1}(\{2,3,4\}) = \{ x \in \{a,b,c\} \;|\; f(x) \in \{2,3,4\} \} = \{ b,c\}$ since $f(b)=f(c)=2$ but $a$ doesn't map to 2, 3, or  4. Again notice that $f^{-1}(\{2\}) = \{b,c\}$ and that $f^{-1}(\{3,4\}) = \emptyset$ (nothing maps to 3 or 4).

\vspace{0.05in}

\noindent
Staring at the above example, one might make the following observations:

\vspace{0.05in}

\PROP Let $f:A \to B$.
\begin{enumerate}[i)]
\item The function $f$ is injective (i.e., one-to-one) if and only if for every $x \in B$, $f^{-1}(\{x\})$ has at most one element.
\item The function $f$ is surjective (i.e., onto) if and only if for every $x \in B$, $f^{-1}(\{x\})$ is not empty.
\end{enumerate}

\vspace{0.05in}

In fact, there is a special name for the inverse image of a singleton set such as $f^{-1}(\{x\})$. We call this the {\bf fiber} over $x$. Thus onto functions are exactly those with non-empty fibers and one-to-one functions are exactly those whose non-empty fibers have exactly one element. Having a non-empty fiber over $x$ means that $x$ is in the range of our function.

\vspace{0.05in}

\noindent
One could ask if $f:\mathcal{P}(A) \to \mathcal{P}(B)$ and $f^{-1}:\mathcal{P}(B) \to \mathcal{P}(A)$ are inverses -- the notation would seem to indicate that they are. But, alas, in this case we are victims of bad notation. I will state without proof (although the proofs are not difficult) the following result:

\PROP Let $f:A \to B$.
\begin{enumerate}[i)]
\item For any $C \subseteq A$, it is always the case that $C \subseteq f^{-1}(f(C))$.
\item On the other hand, $f^{-1}(f(C))=C$ for all $C \subseteq A$ if and only if $f$ is injective (i.e., one-to-one).\\ Thus $f^{-1}:\mathcal{P}(B) \to \mathcal{P}(A)$ is a left inverse of $f:\mathcal{P}(A) \to \mathcal{P}(B)$ if and only if $f:A \to B$ has a left inverse (i.e., it is injective = one-to-one).
\item For any $D \subseteq B$, it is always the case that $f(f^{-1}(D)) \subseteq D$.
\item On the other hand, $f(f^{-1}(D))=D$ for all $D \subseteq B$ if and only if $f$ is surjective (i.e., onto).\\ Thus $f^{-1}:\mathcal{P}(B) \to \mathcal{P}(A)$ is a right inverse of $f:\mathcal{P}(A) \to \mathcal{P}(B)$ if and only if $f:A \to B$ has a right inverse (i.e., it is surjective = onto).
\item $f^{-1}:\mathcal{P}(B) \to \mathcal{P}(A)$ is the inverse of $f:\mathcal{P}(A) \to \mathcal{P}(B)$ if and only if $f$ has an inverse (i.e., it is bijective = one-to-one and onto).
\end{enumerate}


\end{document}
