%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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}}

\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{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\begin{document}

%----------------------------------------------------------------------------------------
\section*{7. Proving Nonconditional Statements}
\subsection*{7.1   If-And-Only-If Proof}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Proving If-And-Only-If Statements}
Outline:
\begin{mdframed}
{\bf Proposition:} $P \Leftrightarrow Q$.

\textit{Proof}: \pause

Part 1: $P \Rightarrow Q$.\\\pause
Part 2: $Q \Rightarrow P$.\pause

Therefore, $P \Leftrightarrow Q$.\qed
\end{mdframed} \pause\vfill
\textbf{Proposition:} $\forall a, b \in \mathbb Z$, $a \equiv b \mod 6$ if and only if\\
$a \equiv b \mod 2$ \quad and \quad $a \equiv b \mod 3$.\\
\pause\vfill

\textit{Proof}:\color{green}\\
\textit{Suppose $a \equiv b \mod 6$.} \pause Then $6|(a-b)$, so $6x=(a-b)$ for some $x \in \mathbb Z$. Then $(a-b)=2(3x)=3(2x)$, so $(a-b)$ is divisible by both 2 and 3. Then $a \equiv b \mod 2$\quad and \quad $a \equiv b \mod 3$.
\pause\color{dblue}

\textit{Suppose $a \equiv b \mod 3$ and $a \equiv b \mod 2$.} \pause Then $(a-b)=2x=3y$ for some $x, y \in \mathbb Z$. From the first expression, we see that $(a-b)$ is even, so $y$ is even as well. Then $y=2z$ for some $z \in \mathbb Z$, so $(a-b)=3y=6z$. Therefore $a \equiv b \mod 6$.
\qed
\end{frame}\color{black}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Prove It}
\textbf{Proposition: }$\forall a,b \in \mathbb N$,
$\gcd(a,b)=b \quad \Leftrightarrow \quad b|a$\pause
\vfill\color{mauve}
\textcolor{green}{($\Rightarrow$)}\\
Suppose $\gcd(a,b)=b$. Then $b$ is a divisor of both $a$ and $b$. In particular, $b|a$.

\vfill
\textcolor{green}{($\Leftarrow$)}\\
Suppose $b|a$. Then  $b$ is a divisor of both $a$ and $b$, so $gcd(a,b) \geq b$. Since $b>0$, any $c \in \mathbb N$ with $c>b$ is not a divisor of $b$. So, $\gcd(a,b) \leq b$. Therefore $\gcd(a,b)=b$.
\vfill
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{7.2  Equivalent Statements}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}{Lists of Equivalent Statements}
\textbf{Theorem:}
Suppose $A$ is an $n\times n$  matrix. The following statements are
equivalent:
\begin{enumerate}[(a)]
\item  The matrix $A$ is invertible.
\item The equation $Ax = b$ has a unique solution for every $b \in \mathbb R^
n$.
\item The equation $Ax = 0$ has only the trivial solution.
\item The reduced row echelon form of $A$ is $I_n$.
\item $\det(A)\neq 0$.
\item The matrix $A$ does not have 0 as an eigenvalue.
\end{enumerate}\pause

\begin{center}
\begin{tikzpicture}
\foreach \x/\a in {0/(a),1/(b),2/(c),3/(d),4/(e),5/(f)}{
\draw (0,0)+(120-60*\x:1.75cm) node(P\x){\a};}
\onslide<2>{\foreach \x in {1,...,5}{
	\foreach \y in {0,...,{\x}}{
		 \ifnum \x=\y {}[\else
		\draw[double,  <->]  (P\x)--(P\y);]
	        \fi
	}}}
\onslide<3,5->{
	\foreach \x/\y in {0/1,1/2,2/3,3/4,4/5,5/0}
	{\draw[double, ->] (P\x)--(P\y);}}
\onslide<4>{
	\foreach \x/\y in {0/1,1/2,2/3,3/0}
	{\draw[double, ->] (P\x)--(P\y);}
	\foreach \x/\y in {5/0,4/3}
	{\draw[double, <->] (P\x)--(P\y);}}
\end{tikzpicture}
\end{center}
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Equivalent Statements}
\textbf{Proposition:} For any $x,y \in \mathbb R-\{0\}$, the following statements are equivalent:
\begin{enumerate}[(A)]
\item $|x+y|=|x|+|y|$
\item $xy=|xy|$
\item $(x+y)^2=x^2+y^2+2|xy|$
\item  $x$ and $y$ have the same sign
\end{enumerate}\pause
\vfill
\begin{center}
\begin{tikzpicture}
\draw (0,0) node{(C)};
\draw (0,2) node{(B)};
\draw (2,0) node{(D)};
\draw (2,2) node{(A)};
\end{tikzpicture}
\end{center}
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{7.3  Existence and Uniqueness Proofs}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Existence versus Existence and Uniqueness}
\textbf{Proposition:} There exists a natural number $n$ such that $n^2=n$.

\onslide<2->{\textcolor{mauve}{There is at least one.}}

\onslide<4->{\textcolor{green}{$\exists n \in \mathbb N, n^2=n$}}

\onslide<6->{\textcolor{dblue}{
Proof: Note that $1 \in \mathbb N$, and $1^2=1$.
}}
\vfill
\textbf{Proposition:} There exists a \emph{unique} natural number $n$ such that $n^2=n$.

\onslide<3->{\textcolor{mauve}{There is exactly one.}}

\onslide<5->{\textcolor{green}{$\exists ! n \in \mathbb N, n^2=n$}}

\onslide<7->{\color{dblue}
Proof: Note that $1 \in \mathbb N$, and $1^2=1$. So, there exists at least one $n\in \mathbb N$ such that $n^2=1$.

Now, suppose $n \in \mathbb N$ and $n^2=n$. Then $n^2-n=0$, so $n(n-1)=0$. Then $n=1$ or $n=0$. Since $n \in \mathbb N$, we conclude $n=1$. That is, $n=1$ is the \emph{only} natural number such that $n^2=n$.
}

\vfill
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Good or Bad?}
\textbf{Proposition:} Let $f(x)=\dfrac{xe^x-5x^2e^x}{x^4}$. \\There exists a unique integer $x$ such that $f(x)=0$.\\[10pt]\color{mauve}
\textit{Proof:} Suppose $x \in \mathbb Z$ and $f(x)=0$. Then:
\begin{align*}
\dfrac{xe^x-5x^2e^x}{x^4}&=0\\
xe^x-5x^2e^x&=0\\
xe^x(1-5x)&=0\\
x=0\quad\mbox{or}\quad e^x=0\quad\mbox{or}\quad(1-5x)&=0\\
x=0\quad\mbox{or}\quad x&=\frac{1}{5}.
\end{align*}
Since $x\in\mathbb Z$, we conclude $x=0$. That is, the only integer solution to $f(x)=0$ is $x=0$.
\pause \\[10pt]\color{dblue}
But $x=0$ is not in the domain of $f(x)$. IF any integer solution exists, THEN there's only one... but actually, none exists!
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}{Good or Bad?}
\textbf{Proposition:} There exists precisely one even prime number.\\[10pt]\pause

\color{mauve}\textit{Proof:} First, we note that $2$ is an even prime number, so there exists at least one even prime number.

To show that 2 is unique, suppose $n$ is an even prime number. Since $n$ is even, $n=2a$ for some integer $a$. Since $n$ is prime, $n$ is positive, and the only positive divisors of $n$  are 1 and $n$. But, we just showed that 2 is a positive divisor of $n$. So, $2\in\{x\in\mathbb N:x|n\}=\{1,n\}$. Since $2 \neq 1$, we conclude $2=n$. We conclude that 2 is the only even prime number.
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Greatest Common Divisor}
\textbf{Proposition:} Given any two coprime integers $a$ and $b$, there exist $k,\ell \in \mathbb Z$ such that $$ak+b\ell = 1$$.\\
\pause\color{mauve}
\textit{Proof:}\\
Let $A = \{ax+by : x,y \in \mathbb Z\}$.\\
Let $d$ be the smallest positive element of $A$, and say $d=ak+b\ell$.\\
\textbf{Claim:} $d|a$.
\begin{quote}\color{dblue}
\textit{Proof of Claim:} \\
There exists an integer $q$ such that $a=dq+r$ for some $r \in \mathbb Z$, $0 \leq r < d$. (Division.)
\begin{align*}
r&=a-dq\\
&=a-[ak+b\ell]q\\
&=a(1-kq)+b(-\ell q)
\end{align*}
So, $r\in A$. Since $0 \leq r < d$ (since it's a remainder) and $r\le 0$ or $r \ge d$, we conclude $r=0$. That is, $d|a$.
\end{quote}
By the same logic, $d|b$, so $d=1$.
\end{frame}
%----------------------------------------------------------------------------------------%----------------------------------------------------------------------------------------
\begin{frame}[t]{Greatest Common Divisor}
\textbf{Proposition:} Given any two coprime integers $a$ and $b$, there exist $k,\ell \in \mathbb Z$ such that $$ak+b\ell = 1$$.\\
\color{green}
\textbf{Corollary:} Given any two integers $a$ and $b$, there exist $k,\ell \in \mathbb Z$ such that $$ak+b\ell = \gcd(a,b)$$.\\\pause

\color{mauve}
\textit{Proof:}\\
Let $d=\gcd(a,b)$.
\begin{itemize}
\item \textbf{Claim 1:} $\dfrac{a}{d},\dfrac{b}{d} \in \mathbb Z$.
\item \textbf{Claim 2:} $\gcd\left(\frac{a}{d},\frac{b}{d}\right)=1$.
\end{itemize}
By the Proposition above, there exist $k, \ell \in \mathbb Z$ such that
$\left(\frac{a}{d}\right)k+\left(\frac{b}{d}\right)\ell =1$.\\
Then, multiplying both sides of the equation by $d$,
\[ak+b\ell =d.\]
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\subsection*{7.4  (Non-) Constructive Proofs}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Greatest Common Divisor: Use the Proof?}
\textbf{Proposition:} Given any two coprime integers $a$ and $b$, there exist $k,\ell \in \mathbb Z$ such that $$ak+b\ell = 1$$.\\

\begin{itemize}\color{mauve}
\item $a=3$, $b=7$:\qquad \pause {\textcolor{lblue}{$7(2)-3(1)=1$}} \pause
\item $a=5$, $b=8$:\qquad \pause {\textcolor{lblue}{$5(5)-8(3)=1$; also $8(2)-5(3)=1$}}\pause
\item $a=22$, $b=37$:\qquad\pause \textcolor{lblue}{$37(3)-22(5)=111-110=1$}
\end{itemize}\pause

The proof we gave was non-constructive. It didn't tell us \emph{what} $k$ and $\ell$ were--only that they exist.
\end{frame}
%----------------------------------------------------------------------------------------
\begin{frame}[t]{Powers of Irrationals}
\textbf{Proposition:} $\exists x , y \in \mathbb R - \mathbb Q$, $x^y \in \mathbb Q$

\color{green}\only<2-7>{\textit{Proof:} (non-constructive)

Let $r=\sqrt{2}^{\sqrt{2}}$.\\}

\only<3-7>{If $r$ is rational,} \only<4-7>{then take $x=y=\sqrt{2}$.}

\only<3-7>{If $r$ is irrational,} \only<5-7>{then take $x=r$ and $y=\sqrt{2}$.
\only<6-7>{\[x^y=\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}}=\sqrt{2}^{(\sqrt 2)(\sqrt{2})}=\sqrt{2}^2=2\]}
}


\color{black}\onslide<7->{\textbf{Proposition:} $\exists x , y \in \mathbb R - \mathbb Q$, $x^y \in \mathbb Q$}\color{green}

\onslide<8->{\textit{Proof}: (Constructive)

Let $x=\sqrt{2}$ and $y=\log_2 9$.
}

\begin{quote}\color{green}
\onslide<9->{Claim: $y \not\in \mathbb Q$.}

\color{dblue}\onslide<10->{Proof of claim: Suppose $\frac{p}{q}=\log_2 9$ for some $p,q \in \mathbb Z$. Since $\log_2 9>0$, actually we can choose $p,q \in \mathbb N$.

 Then $2^{p/q}=9=3^2$, so $2^p=3^{2q}$. Since $p \in \mathbb N$, the left-hand side of the equation is even. But the right-hand side is the product of odd numbers, so it is odd. Then an even number is equal to an odd number, which is a contradiction.
 
 We conclude $y \not\in \mathbb Q$. }
\end{quote}
\color{green}
 
 \onslide<11->{\[x^y=\sqrt{2}^{\log_2 9}=\sqrt{2}^{2\log_2 3}=2^{\log_2 3}=3\]}
\end{frame}
%----------------------------------------------------------------------------------------
%----------------------------------------------------------------------------------------

\end{document} 