%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass[9pt]{beamer}
%\setbeamerfont{frametitle}{size=\normalsize}
\usepackage{tikz}
\usepackage{color, xcolor}
\usetikzlibrary{shapes, patterns, arrows}
%colorblind-friendly palette
\definecolor{dblue}{RGB}{51,34,136}
\definecolor{lblue}{RGB}{136,204,238}
\definecolor{green}{RGB}{17,119,51}
\definecolor{tan}{RGB}{221,204,119}
\definecolor{mauve}{RGB}{204,102,119}

\newcommand{\ds}{\displaystyle}
\newcommand{\dbox}[1]{\colorbox{tan}{\textbf{#1}}}
\usepackage{amsthm}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{convention}{Convention}
\newtheorem*{recall}{Recall}
\newtheorem*{thm}{Theorem}
\tikzstyle{vertex}=[shape=circle, minimum size=2mm, inner sep=0, fill]
\tikzstyle{opendot}=[shape=circle, minimum size=2mm, inner sep=0, fill=white, draw]
\newcommand{\axis}[2]{\draw[help lines, <->] (-#1,0)--(#1,0) node[right]{$x$};
\draw[help lines, <->] (0,-#2)--(0,#2) node[above]{$y$};}
\newcommand{\aaxis}[4]{\draw[help lines, <->] (-#1,0)--(#2,0) 
node[right]{$x$};
\draw[help lines, <->] (0,-#3)--(0,#4) node[above]{$y$};}

\newcommand{\ct}{\textcolor{mauve}{T}}
\newcommand{\cf}{\textcolor{green}{F}}
\newcommand{\lcm}{\textup{\normalfont lcm}}

\newcommand{\one}{\textcolor{mauve}{1}}
\newcommand{\mpr}{\textcolor{mauve}{(2^n-1)}}

\usepackage{multicol}
\setlength{\columnsep}{1cm}

%\usepackage{enumitem, tablists, amsmath,vwcol}
\usepackage{amsmath,vwcol}
\usepackage[linewidth=1pt]{mdframed}
\usepackage[parfill]{parskip}
\mode<presentation> {

% The Beamer class comes with a number of default slide themes
% which change the colors and layouts of slides. Below this is a list
% of all the themes, uncomment each in turn to see what they look like.

%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
%\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% As well as themes, the Beamer class has a number of color themes
% for any slide theme. Uncomment each of these in turn to see how it
% changes the colors of your current slide theme.

%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
%\usecolortheme{wolverine}
\setbeamercolor{alerted text}{fg=mauve}

\setbeamertemplate{footline} % To remove the footer line in all slides uncomment this line
%\setbeamertemplate{footline}[page number] % To replace the footer line in all slides with a simple slide count uncomment this line

\setbeamertemplate{navigation symbols}{} % To remove the navigation symbols from the bottom of all slides uncomment this line
}

\usepackage{multirow}% http://ctan.org/pkg/multirow
\usepackage{hhline}% http://ctan.org/pkg/hhline

\usepackage{xintexpr}
\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\begin{document}

%----------------------------------------------------------------------------------------
\section*{12 Functions}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{12.1 Functions}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Functions as Relations}
\[f(x)=x^2\]\pause
$\left\{(x,y) \in \mathbb R^2 ~:~ x^2=y \right\}\subseteq \mathbb R \times \mathbb R$\pause

$xRy$ if and only if $x^2=y$\pause

\begin{block}{Function}
Suppose $A$ and $B$ are sets. A \dbox{function} $f$ from $A$ to $B$ (denoted as \textcolor{mauve}{$f:A\to B$}) is a relation $f \subseteq A \times B$, satisfying the property that for each $a \in A$ the relation $f$ contains exactly one ordered pair of the form $(a,b)$. \textcolor{dblue}{(Functions pass the vertical line test.)}

The statement $(a,b) \in f$ is abbreviated $f(a)=b$.
\end{block}\pause\color{green}

$\left\{(1,2),(2,4),(3,6),(2.7,5.4),(\pi,2\pi),\ldots\right\}$ \\
\onslide<6->{\textcolor{lblue}{$f:\mathbb R \to \mathbb R$, $f(x)=2x$}}

$\left\{ (1,-1),(1,1),(2,2),(3,3),(4,4),(5,5),\ldots \right\}$\\
\onslide<7->{\textcolor{lblue}{Not a function: $f(1)$ has two values.}}

\end{frame}%----------------------------------------------------------------------------------------
\begin{frame}[t]{Function Vocabulary}

\begin{block}{Function}
Let $f~:~A \to B$ be a function. We call $A$ the \dbox{domain} of $f$, and $B$ the \dbox{codomain} of $f$. The \dbox{range} of $f$ is $\{f(a): a \in A\}$.
\end{block}\pause\color{green}
\begin{align*}
&f:\mathbb (0,\infty) \to \mathbb R, &f(x)&=\ln x
\onslide<3->{&\color{lblue} \mbox{Codomain: }\mathbb R, \mbox{Range: }\mathbb R}\\
&f:\mathbb [1,\infty) \to \mathbb R, &f(x)& = \sqrt{1-x}\onslide<4->{&\color{lblue} \mbox{Codomain: }\mathbb R, \mbox{Range: }[0,\infty)}\\
&f: \mathbb Z \to \mathbb Z, &f(x)&=|x|\onslide<5->{&\color{lblue} \mbox{Codomain: }\mathbb Z, \mbox{Range: }\mathbb N \cup \{0\}}
\end{align*}\color{black}
\onslide<6->{The range is a subset of the codomain.}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Functions that aren't from the reals to the reals}
\onslide<2->{\[p:\mbox{(location)}\to\mbox{(color)}\]}
\begin{center}
\begin{tikzpicture}[scale=0.8]
\draw[fill=mauve] (0,3) rectangle (3,6);
\draw[fill=green] (1,0) rectangle (2,3);
\draw[fill=tan] (1,4) rectangle (2,5);
\draw (0,0) grid (3,6);
\onslide<3->{\foreach \x in {1,2,3}{
	\foreach \y in {1,...,6}
		{\draw (\x-.5,\y-.5) node{\small $(\x,\y)$};}}
}
\end{tikzpicture}
\end{center}
\onslide<4-9>{\[p:\left(\{1,2,3\}\times\{1,2,3,4,5,6\}\right)\to\{\onslide<5->{\mbox{white, mauve, tan, green}}\}\]}
\onslide<6->{$p=\left\{\alert<6>{\left((1,1),\mbox{white}\right)},\alert<7>{\left((1,2),\mbox{white}\right)}\alert<8>{, \left((2,1),\mbox{green}\right),\ldots} \right\}$}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Equality in Functions}
\begin{block}{Equality}
Two functions $f:A \to B$ and $g:X \to Y$ are \dbox{equal} if (and only if):
\begin{itemize}
\item $A=X$, and
\item $f(a)=g(a)$ for every $a \in A$.
\end{itemize}
\end{block}\pause
\color{green}
Equal or Not?
\begin{itemize}\color{green}
\item $f: \mathbb N \to \mathbb N$: $f(x)=x^2$\qquad \onslide<3->{\textcolor{lblue}{$f \neq g$: }}
\item $g: \mathbb R \to \mathbb R$: $g(x)=x^2$\qquad \onslide<3->{\textcolor{lblue}{$g(-1)=1$, while $f$ is not defined at $x=-1$.}}
\end{itemize}\vfill
\begin{itemize}\color{green}
\item $f: \mathbb Z \to \mathbb Z$: $f(x)=x^2$
\item $g: \mathbb Z \to \mathbb R$: $g(x)=|x|*|x|$\qquad \onslide<4->{\textcolor{lblue}{$f = g$}}

\end{itemize}
\vfill
\begin{itemize}\color{green}
\item $f: \{1,2\} \to \{1,2\}$: $f=\{(1,1), (2,1)\}$
\item $g: \{1,2\} \to \{1,2\}$: $g=\{(2,1), (1,1)\}$\qquad \onslide<5->{\textcolor{lblue}{$f = g$}}
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{12.2 Injective and Surjective Functions}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Injective, Surjective, Bijective}
\begin{definition}Let $f$ be a function from $A$ to $B$. 
\begin{itemize}
\item $f$ is \dbox{injective} (also called \emph{one-to-one}) if, for every $x,y \in A$, if $x \neq y$, then $f(x)\neq f(y)$.\pause
\item $f$ is \dbox{surjective} (also called \emph{onto}) if, for every $b \in B$, there exists an $a \in A$ such that $f(a)=b$. (That is: the codomain equals the range.)\pause
\item $f$ is \dbox{bijective} if it is both injective and surjective.\pause
\end{itemize}
\end{definition}
\vfill
\begin{tikzpicture}
\foreach \x in {0,1}{
	\draw (-1,\x) node[vertex](a\x){};}
\draw (1,.5) node[vertex](b0){};	
\draw[thick, ->] (a0)--(b0);
\draw[thick, ->] (a1)--(b0);
\onslide<5->{\draw[lblue] (0,-.5) node{not injective};}
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\foreach \x in {0,1}{
	\draw (1,\x) node[vertex](b\x){};}
\draw (-1,.5) node[vertex](a0){};	
\draw[thick, ->] (a0)--(b0);
\onslide<6->{\draw[lblue] (0,-1) node{not surjective};}
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\foreach \x in {0,1}{
	\draw (1,\x) node[vertex](b\x){};}
\draw (-1,.5) node[vertex](a0){};	
\draw[thick, ->] (a0)--(b0);
\draw[thick, ->] (a0)--(b1);
\onslide<7->{\draw[lblue] (0,-1) node{not a function};}
\end{tikzpicture}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Injective, Surjective, Bijective}
Let $f$ be a function from $A$ to $B$. 
\begin{itemize}
\item $f$ is \dbox{injective} (also called \emph{one-to-one}) if, for every $x,y \in A$, if $x \neq y$, then $f(x)\neq f(y)$.
\item $f$ is \dbox{surjective} (also called \emph{onto}) if, for every $b \in B$, there exists an $a \in A$ such that $f(a)=b$. (That is: the codomain equals the range.)
\item $f$ is \dbox{bijective} if it is both injective and surjective.
\end{itemize}

\only<5->{
\begin{tikzpicture}
\axis{2}{1}
\draw plot[thick, domain=-20:20, samples=150](.1*\x,{.05*\x*sin(\x r)});
\draw (0,-1.1) node {$f: \mathbb R \to \mathbb R$};
\draw (0,-1.45) node {$f(x)=x\sin x$};
\onslide<6->{\draw (0,-2) node[lblue]{surjective};
\draw (0,-2.5) node[lblue]{not injective};}
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\axis{2}{1}
\draw plot[thick, domain=-1.4:1.4, samples=100]({.3*tan( \x r)},{\x*.5});
\draw[dashed] (-2,.75)--(2,.75) (-2,-.75)--(2,.-.75);
\draw (0,-1.1) node {$f: \mathbb R \to \only<-7>{\mathbb R}\only<8->{\alert{\left(-\frac{\pi}{2},\frac{\pi}{2}\right)}}$};
\draw (0,-1.45) node {$f(x)=\arctan x$};
\onslide<7->{\draw (0,-2) node[lblue]{injective};}
\onslide<7>{\draw (0,-2.5) node[lblue]{not surjective};}
\onslide<8>{\draw (0,-2.5) node[mauve]{ surjective};}
\end{tikzpicture}}


\only<1-4>{
\begin{tikzpicture}
\axis{2}{1}
\draw plot[thick, domain=-2:2, samples=20](\x,{\x*\x/4});
\draw (0,-1.1) node {$f: \mathbb R \to \only<1-2>{\mathbb R}\only<3->{\alert{[0,\infty)}}$};
\draw (0,-1.45) node {$f(x)=x^2$};
\onslide<2>{\draw (0,-2) node[lblue]{neither};}
\onslide<3->{\draw (0,-2) node[mauve]{surjective};}
\end{tikzpicture}
\hfill
\begin{tikzpicture}
\axis{2}{1}
\draw plot[thick, domain=-2:2, samples=30]({\x},{\x*\x*\x/8});
\draw (0,-1.1) node {$f: \mathbb R \to \mathbb R$};
\draw (0,-1.45) node {$f(x)=x^3$};
\onslide<4->{\draw (0,-2) node[lblue]{bijective};}
\end{tikzpicture}}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Proving Injectivity and Surjectivity}
\textcolor{green}{Prove or disprove: \\The function $f(x)=3x^4+1$, $f:\mathbb R \to \mathbb R$, is injective.}

\onslide<2->{\textcolor{lblue}{We notice $1$ and $-1$ are in $\mathbb R$, $1 \neq -1$, and $f(1)=f(-1)=4$. \\This shows that $f$ is not injective.}}
\vfill

\textcolor{green}{Prove or disprove:\\ The function $f(x)=3x^4+1$, $f:\mathbb R \to \mathbb R$, is surjective.}

\onslide<3->{\textcolor{lblue}{We notice $0$ is in $\mathbb R$, but no real value of $x$ gives $f(x)=0$.\\ This shows that $f$ is not surjective.}}\vfill
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Proving Injectivity and Surjectivity}
\textcolor{green}{Prove that the function \[f(x)=\dfrac{x+1}{x-1},\quad f:\left(\mathbb R - \{1\} \right)\to\left( \mathbb R - \{1\}\right)\] is bijective.}\color{mauve}

\onslide<2->{\fbox{Injectivity}} \only<3-4>{\onslide<3->{\textcolor{dblue}{Suppose $f(x)=f(y)$ for some $x,y \in \mathbb R-\{1\}$.}}

\onslide<4->{That is:
\begin{align*}
&&\dfrac{x+1}{x-1}&=\dfrac{y+1}{y-1}\\
&\mbox{So:}& (x+1)(y-1)&=(x-1)(y+1)\\
&\mbox{So:}& xy-x+y-1&=xy+x-y-1\\
&\mbox{So:}&-x+y&=x-y\\
&\mbox{So:}&2y&=2x
\end{align*}}

\onslide<3->{\textcolor{dblue}{So, $x=y$. We conclude $f(x)$ is injective.}}}

\onslide<2->{\fbox{Surjectivity}}
\only<5->{\textcolor{dblue}{Let $y \in \mathbb R - \{1\}$, and define $a=\boxed{\onslide<6->{\dfrac{y+1}{y-1}}}$}}\\
\onslide<7->{We note that, since $y \neq 1$, $a \in \mathbb R$. Furthermore, since the equation $\dfrac{y+1}{y-1}=1$ is equivalent to the equation $y+1=y-1$, and so $1=-1$, which has no solutions, we see that $a \neq 1$. We note further:
\[f(a)=\frac{a+1}{a-1}=\frac{\frac{y+1}{y-1}+1}{\frac{y+1}{y-1}-1}=
\frac{\frac{y+1+y-1}{y-1}}{\frac{y+1-(y-1)}{y-1}}=\frac{y+1+y-1}{y+1-(y-1)}=\frac{2y}{2}=y\]}

\onslide<5->{\textcolor{dblue}{Then $a \in \mathbb R - \{1\}$, and $f(a)=y$. We conclude $f(x)$ is surjective.}}
\end{frame}
%----------------------------------------------------------------------------------------%----------------------------------------------------------------------------------------
\begin{frame}[t]{Proving Injectivity and Surjectivity}
\color{green} Consider the function $f: \mathbb R^2 \to \mathbb  R^2$ defined by
\[f(x,y)=(x+y,x-y)\]
Is $f$ injective? Is $f$ surjective? Prove your answers.\pause\color{mauve}

$f$ is injective. \textcolor{dblue}{Suppose there exist $(x,y) \in \mathbb R^2$ and $(a,b) \in \mathbb R^2$ such that $f(x,y)=f(a,b)$.} \onslide<3->{Then:
(1) $x+y=a+b$, and (2) $x-y=a-b$. Adding (1) and (2), we see $2x=2a$, so $x=a$. Then from (1) we see $y=b$.} \\
\textcolor{dblue}{So, $(x,y)=(a,b)$.}

\onslide<4->{$f$ is also surjective. \onslide<5->{Given any $(a,b) \in \mathbb R^2$, 
$\left(\frac{a+b}{2},\frac{a-b}{2}\right) \in \mathbb R^2$, and $f\left(\frac{a+b}{2},\frac{a-b}{2}\right)=(a,b)$. }}
\end{frame}
%----------------------------------------------------------------------------------------%----------------------------------------------------------------------------------------
\begin{frame}[t]{Proving Injectivity and Surjectivity}
\color{green} Consider the function $f: \mathbb R^2 \to \mathbb  R^2$ defined by
\[f(x,y)=(x-y,x^2-y^2)\]
Is $f$ injective? Is $f$ surjective? Prove your answers.\pause

\color{mauve}
$f$ is not injective, because \onslide<3->{$f(0,0)=f(1,1)=(0,0)$.}

$f$ is not surjective. \onslide<4->{We note $(0,1) \in \mathbb R^2$. If $f(x,y)=(0,1)$, then $x-y=0$, so $x=y$. But then $x^2-y^2=0$, so $f(x,y)=(0,0) \neq (0,1)$.}
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{12.3 The Pigeonhole Principle}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Proving Injectivity and Surjectivity}
\color{green} Consider a function $f:A \to B$, where $|A|=3$ and $|B|=2$.

Is $f$ injective? Is $f$ surjective?\pause

\color{mauve}
$f$ is not injective, because there are three different inputs and only two different outputs.

$f$ may or may not be surjective.\color{black}\pause

\begin{block}{Pigeonhole Principle}
Suppose $p$ pigeons are sitting in $h$ pigeonholes.
\begin{itemize}
\item If $p>h$, then some hole has more than one pigeon in it.
\item If $p<h$, then some hole does not have a pigeon in it.
\end{itemize}
\end{block}\pause
Let $A$ and $B$ be finite sets, and let $f:A \to B$ be a function.
\begin{itemize}
\item If $|A|>|B|$, then $f$ is not \onslide<5->{\textbf{injective.}}
\item If $|A|<|B|$, then $f$ is not \onslide<6->{\textbf{surjective.}}
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}{Socks and Pigeons}
Suppose you have a drawer full of red, blue, and green socks. You're grabbing clothes in the dark. How many socks do you have to take before you're guaranteed to have a matching pair?

\vfill

You roll a handful of dice all at once. You are guaranteed to have three dice showing the same number. How many dice did you roll?

\vfill



\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Pigeonhole Principle}
The average person has about 100,000 hair follicles on their head\footnote{\url{http://www.newworldencyclopedia.org/entry/Hair}}\pause

Suppose everyone in Canada has  between 0 and 999,999 hairs on their head. The population of Canada is more than 30 million. What does the Pigeonhole Principle tell us about this situation?\pause\color{mauve}

There are at least two people in Canada with exactly the same number of hairs on their head.\pause\color{dblue}

(Actually, there are at least 30 people in Canada with exactly the same number of hairs on their head.)\pause\color{black}

This is a \emph{non-constructive} proof.
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Pigeonhole Principle}
Pick six distinct numbers from the set $\{1,2,3,4,5,6,7,8,9,10\}$.\pause

Among your picks, there are two numbers that sum to 11.\pause\color{mauve}

Make the following holes:
\[\{1,10\},\quad\{2,9\},\quad\{3,8\},\quad\{4,7\},\quad\{5,6\}\]\pause

Notice every number from the original set of ten appears in one of the holes. By picking six numbers, each of which fits into one of the 5 holes, you must have chosen at least two numbers from the same hole. Their sum is 11.\pause

\color{green} Suppose you have a pack of cards with the face cards removed. That is, you have 40 cards: four of each suit ($\diamondsuit, \heartsuit, \clubsuit, \spadesuit$), with face values 1-10. What is the minimum number of cards you can draw, and still be guaranteed that there are two cards \textbf{of the same suit} that add to 11?
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Pigeonhole Principle}
\textbf{Proposition:} For any $a \in \mathbb N$, there exist distinct $k,\ell \in \mathbb N$ such that $a^k-a^\ell$ is divisible by 7.\pause

Example: if $a=2$, then $2^4-2^1=16-2=14=2\times 7$.\\\pause
Example: if $a=3$, then $3^7-3^1=2187-3=2184=312\times 7$\pause

Proof: There are seven congruence classes mod 7. For every $x \in \mathbb N$, $a^x$ is in one of them. Since there are more than seven values of $a^x$ when we let $x \in \mathbb N$, two of them must be in the same congruence class mod 7. Then their difference is divisible by 7.

Actually: there must exist $k,\ell$ in $\{1,\ldots,8\}$ such that $a^k-a^\ell$ is divisible by 7.
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Pigeonhole Principle}
\textbf{Proposition:} In any set of four distinct natural numbers, there exist two distinct natural numbers whose sum or difference is divisible by 5.\pause\vfill

Example: In the set $\{1,2,3,5\}$, $2+3$ is divisible by 5.\\  \pause
Example: In the set $\{1,6,8,10\}$, $6-1$ is divisible by 5.\\\pause\vfill

\textit{Proof} We will use the pigeonhole principle. Let the natural numbers be partitioned into three ``holes"  by their equivalence class mod 5, as follows:
\[[0],\quad [1]\cup[4],\quad [2]\cup[3]\]
By the pigeonhole principle, if we pick four natural numbers, two of them must be in the same hole. If they are in the same equivalence class mod 5, then their difference is divisible by 5. If they are in different equivalence classes (but the same hole), then their sum is divisible by 5.
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{12.4 Composition}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Function Composition}
\begin{block}{Function Composition}
Let $f$ and $g$ be functions, $f:B \to C$ and $g:A \to B$. Then we defined the \dbox{composition} of $f$ and $g$ to be
\[(f\circ g) (x)= f(g(x))\]
\end{block}\pause\color{green}\vfill

Suppose $f$ and $g$ are functions from the reals to the reals,\\
 $f(x)=x^2+5x$, $g(x)=\sin x$. Then:\\
$f\circ g(x)=$\pause$\textcolor{lblue}{(\sin x)^2+5\sin x}$\pause\vfill

Suppose $f:\mathbb R^2\to \mathbb R^3$, $g:\mathbb R \to \mathbb R^2$, with\\
$f(x,y)=(x^2,x+y,y^2)$, and $g(x)=(3x,4x).$\\
$f\circ g$\pause$(x)$\pause$=$
\textcolor{lblue}{$f(3x,4x)=(9x^2,7x,16x^2)$}
\vfill
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Composition and Injectivity, Surjectivity}
For the following characteristics, give an example of functions $f$ and $g$ that have them, or show that none exists.\\
\textcolor{dblue}{Assume that the range of $g$ is the same as the domain of $f$.}
\begin{itemize}
\item $f$ injective, $f \circ g$ not injective.\\
\only<2->{\textcolor{lblue}{$f(x)=x$, $g(x)=x^2$}}
\vfill
\item $f$ injective, $g$ injective, $f \circ g$ not injective.\\
\only<4->{\textcolor{mauve}{Suppose $f$ and $g$ are both injective. Then if $f(g(x))=f(g(y))$, by injectivity of $f$, $g(x)=g(y)$. Then, by injectivity of $g$, $g(x)=g(y)$ implies $x=y$. So $f \circ g$ is injective.}}
\vfill
\item $g$ surjective, $f \circ g$ not surjective.\\
\only<3->{\textcolor{lblue}{$f(x)=\sin x$, $g(x)=x$}}\vfill
\item $f$ surjective, $g$ surjective, $f \circ g$ not surjective.\\
\only<5->{\color{mauve}Suppose $f$ and $g$ are surjective, with $g:A \to B$, $f:B \to C$. Then $f \circ g : A \to C$. For any $c \in C$, by surjectivity of $f$, there exists $b \in B$ such that $f(b)=c$. By surjectivity of $g$, there exists $a \in A$ such that $g(a)=b$. Then $f\circ g (a)=f(g(a))=f(b)=c$. So, $f \circ g$ is surjective.}
\vfill
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{12.5 Inverse Functions}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Inverse Relations}
An inverse function ``undoes" the original function. Example: $\sqrt[3]{x^3}=x$, so $f(x)=\sqrt[3]{x}$ is the inverse of $g(x)=x^3$.\pause



\begin{block}{Inverse Relation}
Given a relation $A$ from $A$ to $B$, the \dbox{inverse relation} from $B$ to $A$ is defined as\[R^{-1}=\{(y,x)~:~(x,y) \in R\}\]
\end{block}
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}{Inverse Relations}
\begin{center}
\begin{tikzpicture}
\foreach \x/\y in {-1/-1.5,1/-.5,-2/.5,2/1.5}
	{\draw (-1,\y) node[vertex, label=left:{\x}](x\x){};}
\foreach \x/\y in {1/-1,2/1}
	{\draw (1,\y) node[vertex, label=right:{\x}](y\x){};}
\onslide<2->{
	\foreach \x in {-2,2}
	\draw[thick, ->] (x\x)--(y2);
	\foreach \x in {-1,1}
	\draw[thick, ->] (x\x)--(y1);}
\onslide<3->{
	\draw (0,-2.5) node[dblue]{ Relation: ``is the absolute value of"};
	\draw (0,-3) node[dblue]{\small $R=\big\{(2,2),(-2,2),(1,1),(-1,1)\big\}$};}
\onslide<4->{
	\draw (0,-3.5) node{Function: $f(x)=|x|$};
	\draw (0,-4) node{$f:\{1,2,-,1,-2\}\to\{1,2\}$};}
\end{tikzpicture}
\hfill
\only<5->{\begin{tikzpicture}
\foreach \x/\y in {-1/-1.5,1/-.5,-2/.5,2/1.5}
	{\draw (-1,\y) node[vertex, label=left:{\x}](x\x){};}
\foreach \x/\y in {1/-1,2/1}
	{\draw (1,\y) node[vertex, label=right:{\x}](y\x){};}
\onslide<6->{
	\foreach \x in {-2,2}
	\draw[thick, <-] (x\x)--(y2);
	\foreach \x in {-1,1}
	\draw[thick, <-] (x\x)--(y1);}
\onslide<7->{
	\draw (0,-2.5) node[dblue]{ Inverse relation};
	\draw (0,-3) node[dblue]{ $R=\big\{(2,2),(2,-2),(1,1),(1,-1)\big\}$};}
\onslide<8->{
	\draw (0,-3.5) node{\textit{\textcolor{mauve}{Not a function}}};}
\draw (0,-4) node{};
\end{tikzpicture}}
\end{center}

\onslide<9->{\textbf{Theorem 12.3} Let $f:A \to B$ be a function. Then $f$ is bijective if and only if the inverse relation $f^{-1}$ is a function from $B$ to $A$.}

\onslide<10->{If $f$ is not injective, then $f^{-1}$ is not a function.}

\onslide<11->{If $f(x)$ is not surjective, then the domain of $f^{-1}$ is not $B$.}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Inverse Functions}

\begin{block}{Identity Function}
Given a set $A$, the \dbox{identity function} on $A$ is the function that maps every element to itself. That is, $i_A(x)=x$ for every $x \in A$.
\end{block}

\begin{block}{Inverse Function}
Let $f:A \to B$ be a bijective function. Note then $f$ is also a relation. Then the inverse relation
$f^{-1}:B \to A$ is the \dbox{inverse function} to $f$.
\end{block}\pause

Under this definition, functions $f$ and $f^{-1}$ have the properties that
\[f^{-1}\circ f = i_A \mbox{ and }f\circ f^{-1}=i_B\]

That is, $f(f^{-1}(x))=x$ and $f^{-1}(f(x))=x$.
\end{frame}

%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Inverse Functions}
$f:\left(\mathbb R  - \{2\}\right)\to\left( \mathbb R-\{3\}\right)$, $f(x)=\dfrac{3x+1}{x-2}$.\\
Find $f^{-1}(x)$.\pause

\textcolor{lblue}{We want to swap the role of input and output, so we swap $x$ and $y$, and we solve for $y$.}\pause

\color{mauve}
\begin{align*}
y&=\frac{3x+1}{x-2}\\
x&=\frac{3y+1}{y-2}\\
yx-2x&=3y+1\\
yx-3y&=2x+1\\
y(x-3)&=2x+1\\
y&=\frac{2x+1}{x-3}
\end{align*}

$f^{-1}(x)=\dfrac{2x+1}{x-3}$
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Inverse Functions}
$f:\mathbb R^2\to\mathbb R^2$, $f(x,y)=(y(x^2+1),x^3)$ is bijective.\\
Find $f^{-1}(x)$.\pause

\color{lblue}{We want to swap the role of input and output:
\begin{align*}
f^{-1}(x,y)&=(A,B)\qquad\mbox{What are $A$, $B$ in terms of $x$, $y$?}\\
f(A,B)&=(x,y)\\
(B(A^2+1),A^3)&=(x,y)
\end{align*}
}\pause

\color{mauve}
\begin{align*}
&\left\{\begin{array}{ccl}
x&=&B(A^2+1)\\
y&=&A^3
\end{array}\right.\\
A&=y^{1/3}\\
B &= \frac{x}{A^2+1}=\frac{x}{y^{2/3}+1}
\end{align*}

$f^{-1}(x,y)=\left(y^{1/3},\dfrac{x}{y^{2/3}+1}\right)$
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{12.6 Image and Preimage}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}{Notation}
\begin{block}{Image, Preimage}
Suppose $f:A \to B$ is a function, $X \subseteq A$, $Y \subseteq B$.
\begin{itemize}
\item We write $f(X)=\{f(x):x \in X\}$ for the \dbox{image} of $X$ under $f$.
\item We write $f^{-1}(Y)=\{x \in  A : f(x) \in Y\}$ for the \dbox{preimage} of $Y$ under $f$.
\end{itemize}
\end{block}\pause

Example: $f:\mathbb R \to \mathbb R$, $f(x)=x^2$.
\begin{itemize}
\item $f\left(3\right)=\onslide<3->{9}$
\item $f\left(\{3,-3\}\right)=\onslide<4->{\{9\}}$
\item $f\left([-4,4]\right)=\onslide<5->{[0,16]}$
\item $f^{-1}\left([0,4]\right)=\onslide<6->{[-2,2]}$
\item $f^{-1}\left([-4,4]\right)=\onslide<7->{[-2,2]}$
\item $f^{-1}\left(\{-2\}\right)=\onslide<8->{\emptyset}$
\end{itemize}
\end{frame}%----------------------------------------------------------------------------------------
\begin{frame}{Properties}
\begin{block}{Theorem 12.4}
Suppose $f:A \to B$ is a function. Let $W,X \subseteq A$ and $Y,Z \subseteq B$. Then:\\
\vspace{2mm}
\begin{itemize}
\item $f(W \cap X) \subseteq f(W) \cap f(X)$
\item $f(W \cup X) =f(W) \cup f(X)$
\item $f^{-1}(Y \cap Z)=f^{-1}(Y) \cap f^{-1}(Z)$
\item $f^{-1}(Y \cup Z)=f^{-1}(Y) \cup f^{-1}(Z)$
\item $X \subseteq f^{-1}\left(f(X)\right)$
\item $f\left(f^{-1}(Y)\right)\subseteq Y$
\end{itemize}
\end{block}\pause

Claim: $f(W \cap X) \subseteq f(W) \cap f(X)$.\\
Proof: \pause Let $y \in f(W \cap X)$. Then there exists  $x \in W \cap X$ such that $f(x)=y$. Since $x$ is in both $W$ and $X$, we know $f(x)$ is in both $f(W)$ and $f(X)$.Then $x \in f(W) \cap f(X)$. We conclude $f(W \cap X) \subseteq f(W) \cap f(X)$.\pause\color{green}

Give an example where $f(W \cap X) \neq f(W) \cap f(X)$.\pause\color{lblue}

$f(x)=x^2$, $W=[-1,0]$, $Z=[0,1]$.
\end{frame}%----------------------------------------------------------------------------------------
\begin{frame}{Properties}
\begin{block}{Theorem 12.4}
Suppose $f:A \to B$ is a function. Let $W,X \subseteq A$ and $Y,Z \subseteq B$. Then:\\
\vspace{2mm}
\begin{itemize}
\item $f(W \cap X) \subseteq f(W) \cap f(X)$
\item $f(W \cup X) =f(W) \cup f(X)$
\item $f^{-1}(Y \cap Z)=f^{-1}(Y) \cap f^{-1}(Z)$
\item $f^{-1}(Y \cup Z)=f^{-1}(Y) \cup f^{-1}(Z)$
\item $X \subseteq f^{-1}\left(f(X)\right)$
\item $f\left(f^{-1}(Y)\right)\subseteq Y$
\end{itemize}
\end{block}\pause\color{green}
Suppose $f$ is injective. Then show that $f(W \cap X)=f(W) \cap f(X)$.\\\pause\color{mauve}

Proof: We already showed  $f(W \cap X) \subseteq f(W) \cap f(X)$. Let $y \in f(W) \cap f(X)$. Then there exist $x_1$ and $x_2$, $x_1 \in W$ and $x_2 \in X$, such that $f(x_1)=y$ and $f(x_2)=y$. Since $f$ is injective, $x_1=x_2$, so $x_1 \in W \cap X$, so $y \in f(W \cap X).$ Hence $f(W) \cap f(X) \subseteq f(W \cap X)$, and so the claim holds. \end{frame}
\end{document}