\newlec

\textbf{Uniqueness}
\vskip1em
\defn $\exists!$ means ``There exists a unique''.
\vskip1em
\note To prove uniqueness, we can do one of the following:
\begin{enumerate}
\item Assume $\exists x,y\in S$ such that $P(x) \wedge P(y)$ is true and show $x=y$.
\item Argue by assuming that $\exists x,y \in S$ are distinct such that $P(x) \wedge P(y)$, then derive a contradiction.
\end{enumerate}
To prove uniqueness and existence, we also need to show that $\exists x \in S$ such that $P(x)$ is true. 
\vskip1em
\ex Suppose $x \in \mathbb{R} - \mathbb{Z}$ and $m \in \mathbb{Z}$ such that $x < m < x+1$. Show that $m$ is unique.
\vskip1em
\pf Assume that $\exists m,n \in \mathbb{Z}$ such that 
\begin{align*}
x < m < x+1 \quad\quad \text{ and } \quad\quad x < n < x+1
\end{align*}
Look at the value $m-n$. This value is largest when $m$ is largest and $n$ is smallest. Since $m < x+1$ and $n > x$, we see that $m-n < 1$. Further, for this to be minimal, we could flip the roles of $m$ and $n$ above to see that $-1 < m-n$. Thus $-1 < m-n < 1$ and $m-n \in \mathbb{Z}$. Hence $m-n=0$, that is $m=n$. 
\newpage
\hdc
Let $f(x)$ be the function defined by
\begin{align*}
f: (0,\infty) &\rightarrow (0,\infty) \\
x &\mapsto x^{2}.
\end{align*}
Prove for all $y \in (0,\infty)$ there exists a unique $x\in(0,\infty)$ such that $f(x) = y$
\ic{ Some things to note: This is the first time students will realize that in order to properly define a function, a function has a domain and codomain that are given. Note that the range is the set of all values the domain maps into. The codomain might actually be larger than the range. They have not seen this notation before so you'll be wise to explain to them that this is the same as $f(x) = x^{2}$.}
\vskip3em
\pf Existence. For each $y \in (0,\infty)$, let $x = \sqrt{y}$. Then 
\[f(x) = f(\sqrt{y}) = (\sqrt{y})^{2} = y\]
Uniqueness. Suppose that there exists $a,b \in (0,\infty)$ such that
\begin{align*}
f(a) &= f(b)\\
a^{2} &= b^{2}\\
|a| &= |b|
\end{align*}
and since $a,b > 0$, we have that $a=b$. \qed
\ic{Use this as a lead in to Injections and Surjections. This is the 15 minute mark.}

\newpage

\textbf{Injections and Surjections}

\vskip1em
\defn Let $S$ and $T$ be sets. A function $f: S \rightarrow T$ is said to be 
\begin{enumerate}
\item Injective (or one to one or $1:1$) if and only if $$\forall x,y \in S, f(x) = f(y) \Rightarrow x=y.$$
\item Surjective (or onto) if and only if 
$$\forall y \in T ~\exists x \in S \text{ such that } f(x) = y$$
\end{enumerate}
\ex A function that is one to one but not onto:
\begin{center}
\includegraphics[scale=0.5]{L11P1.png}
\end{center}
\vskip1em
\ex A function that is onto but not one to one:
\begin{center}
\includegraphics[scale=0.5]{L11P2.png}
\end{center}
\vskip1em
\ex Prove 
\begin{align*}
f: \mathbb{R} &\rightarrow \mathbb{R} \\
x &\mapsto x^{2}
\end{align*}
is not injective.
\vskip1em
\pf Notice that
\[
f(-1) = (-1)^{2} = 1 = (1)^{2} = f(1)
\]
but $-1 \neq 1$. \qed
\ic{ Emphasize that this is the negation of the definition above. Disproving a for all means finding a counter example.}
\vskip1em
\ex Prove 
\begin{align*}
f: \mathbb{R} &\rightarrow \mathbb{R} \\
x &\mapsto 2x^{3}+1
\end{align*}
is one to one.
\vskip1em
\pf Let $x, y \in \mathbb{R}$ such that $f(x) = f(y)$. Then
\begin{align*}
2x^{3} + 1 &= 2y^{3} + 1 \\
x^{3} &= y^{3} \\
\sqrt[3]{x^{3}} &= \sqrt[3]{y^{3}}\\
x &= y
\end{align*}
Thus $f$ is injective. \qed
\vskip1em
\ex Prove 
\begin{align*}
f: \mathbb{R} &\rightarrow (-\infty,1) \\
x &\mapsto 1-e^{-x}
\end{align*}
is onto.
\vskip1em
\pf We need to show that every $y \in (-\infty,1)$ has some $x \in \mathbb{R}$ with $f(x) = y$. 
\vskip1em
\textbf{Discovery:} 
\begin{align*}
1-e^{-x} &= y\\
e^{-x} &= 1-y\\
-x &= \ln(1-y)\\
x &= -\ln(1-y)
\end{align*}
\vskip1em
\textbf{Formal proof:} Take $x = -\ln(1-y)$ for any $y \in (-\infty,1)$. Notice that this is well defined since $\ln(1-y)$ is defined on $(-\infty,1)$. Then 
\begin{align*}
f(x) &= 1-e^{-x}\\
&= 1-e^{-(-\ln(1-y))}\\
&= 1-e^{\ln(1-y)}\\
&= 1-(1-y) \\
&= y
\end{align*}
Therefore, $f$ is an onto function. \qed
\ic{This is the 35-40 minute mark.}

\textbf{Division Algorithm}
\vskip1em
This is just like grade school division. For example, $51/7$ can be written as:
$$
51 = 7(7) + 2
$$
where $a=51$, $b=7$, $q=7$ and $r=2$. Similarly, $-35/6$ can be written as
$$
-35 = 6(-6) + 1
$$
where $a = -35$, $b=6$, $q = -6$, and $r=1$.
\newpage
\hdc 
\thm (Division Algorithm) Let $a \in \mathbb{Z}$ and $b \in \mathbb{N}$. Then $\exists! q,r\in\mathbb{Z}$ such that $a = bq + r$ where $0 \leq r < b$.
\vskip1em
\pf Existence: Use the Well Ordering Principle on the set
\[
S = \{ a - bq: a-bq \geq 0 \wedge q \in \mathbb{Z}\}
\]
Uniqueness:
\vskip1em
Suppose that $a = q_1 b+r_1$ with $0 \leq r_1 < b$. Also, suppose that $a = q_2 b+r_2$ with
$0\leq r_2 < b$ and $r_1\neq r_2$. Without loss of generality, we can assume $r_1 < r_2$.
\ic{Introduce the acronym WLOG. Explain that if two integers are not equal, then one must be bigger than the other and the proof is symmetric depending if $r_{1} < r_{2}$ or $r_{2} < r_{1}$}
Then $0 < r_2 - r_1 < b$ and $(q_1 - q_2)b=r_2 -r_1$.
\ic{Take the difference of the two $a$ values. Given that $0 \leq r_{1} , r_{2} < b$, the biggest value of $r_{2} - r_{1}$ is $b$.}
Hence $b \mid (r_2 -  r_1)$. By Bounds By Divisibility, $b \leq r_2 - r_1$ which contradicts the fact that $r_2 -  r_1 < b$.
\ic{This is a contradiction. Notice that we don't need $|b|$ as in (BBD) since $b \in \mathbb{N}$. }
Therefore, the assumption that $r_1\neq r_2$ is false and in fact $r_1 = r_2$. But then $(q_1- q_2)b=r_2- r_1$ implies $q_1 =q_2$.

\vskip3em
\ic{ This is the 50 minute mark. Note you could leave the division algorithm for extra reading if you'd like and replace it by an example with a negative number. If you have time, I'd recommend digesting the Division algorithm proof carefully. If you're really ahead try the following:\\
Define a line to be the set of points $(x,y)$ satisfying $y=mx+b$ for some $m,b \in \mathbb{R}$. Show that if two lines have distinct slopes ($m$ values) and that they intersect, then this solution is unique.}