math-460-unique-proof.tex

\documentclass[fleqn]{beamer}
%\usetheme[height=7mm]{Rochester}
\usetheme{Boadilla} %{Rochester}

\setbeamertemplate{footline}[text line]{%
\parbox{\linewidth}{\vspace*{-8pt}\hfill\insertshortauthor\hfill\insertpagenumber}}
\setbeamertemplate{navigation symbols}{}
%\author[BW]{Dr.\ Barton Willis}
\usepackage{amsmath}\usepackage{amsthm}
\usepackage{isomath}
\usepackage{upgreek}
\usepackage{comment,enumerate,xcolor}

\usepackage[english]{babel}
\usepackage[final,babel]{microtype}%\usepackage[dvipsnames]{color}
\usefonttheme{professionalfonts}
%\usefonttheme{serif}

\newcommand{\reals}{\mathbf{R}}
\newcommand{\complex}{\mathbf{C}}
\newcommand{\integers}{\mathbf{Z}}
\newcommand{\rational}{\mathbf{Q}}

\DeclareMathOperator{\range}{range}
\DeclareMathOperator{\domain}{dom}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\codomain}{codomain}
\DeclareMathOperator{\sspan}{span}
\DeclareMathOperator{\F}{F}
\DeclareMathOperator{\G}{G}
\DeclareMathOperator{\B}{B}
\DeclareMathOperator{\D}{D}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\ball}{ball}

\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath}
\DeclareMathOperator{\nullspace}{nullity}
\theoremstyle{definition}
\newtheorem{mydef}{Definition}
\newtheorem{myqdef}{Quasi-definition}
\newtheorem{myex}{Example}
\newtheorem{myth}{Theorem} 
\newtheorem{myfact}{Fact}
\newtheorem{metathm}{Meta Theorem}
\newtheorem{Question}{Question}
\newtheorem{Answer}{Answer}
\newtheorem{myproof}{Proof}

\newtheorem{myfakeproof}{Fake Proof}
\newtheorem{mybadformproof}{Bad Form Proof}

\newtheorem{hurestic}{Hurestic}

%\usepackage{array}   % for \newcolumntype macro
%\newcolumntype{L}{>{$}l<{$}} % math-mode version of "l" column type

\newenvironment{alphalist}{
  \vspace{-0.0in}
  \begin{enumerate}[(a)]
    \addtolength{\itemsep}{1.0\itemsep}}
  {\end{enumerate}}

\newenvironment{snowflakelist}{
  \vspace{-0.4in}
  \begin{enumerate}[\textleaf]
    \addtolength{\itemsep}{-1.2\itemsep}}
  {\end{enumerate}}





\newenvironment{checklist}{
  \begin{enumerate}[\checkmark]
    \addtolength{\itemsep}{-1.0\itemsep}}
  {\end{enumerate}}

\newenvironment{numberlist}
   {\begin{enumerate}[(1)]
       \addtolength{\itemsep}{-0.5\itemsep}}
     {\end{enumerate}}
\usepackage{amsfonts}
\makeatletter
\def\amsbb{\use@mathgroup \M@U \symAMSb}
\makeatother
\usepackage{bbold}

\usepackage{array}
\newcolumntype{C}{>$c<$}

\newcommand{\llnot}{\lnot \,} % is accepted


%------------------

\subtitle{Lesson 9}
\title{\textbf{A template for uniqueness}}
%\author[Barton Willis] % (optional, for multiple authors)
%{Barton~Willis}%
%\institute[UNK] % (optional)

%{
 % \inst{1}%
%  ``The secret of getting ahead is getting started.'' Mark Twain
%   }
  \date{}
 




%--------
%usepackage[usenames,dvipsnames,svgnames,table]{color}



\begin{document}

\frame{\titlepage}

\begin{frame}{Uniqueness  proofs}

Some propositions assert that there is at most one such thing; example:

\begin{myth}  For every \(x \in \reals_{> 0} \) there is at most one \(z \in \reals_{> 0} \) such that 
\(z^2 = x\). \end{myth}

\vspace{0.3in}
\begin{checklist}

\item Generically, this is an \emph{uniqueness result}.

\vspace{0.1in}
\item In mathematics, ``unique'' means \emph{exactly} one.

\vspace{0.1in}
\item A \textbf{good way} to prove such a theorem is to assume that there are two such objects and show that they are equal. 

\vspace{0.1in}
\item A  \textbf{verbose  way} to prove such a theorem is to assume that there are two such objects that are unequal and to show a contradiction.


\end{checklist}

\end{frame}
\begin{frame}{Good example}

\begin{myproof}  Let \(x  \in \reals_{> 0} \) and suppose that \(z_1, z_2 \in \reals_{> 0} \) and \(z_1^2 = x\) and \(z_2^2  = x\). We have
\begin{align*}
   0 &= x - x,  &\mbox{(arithmetic)} \\
      &= z_1^2 - z_2^2,   &\mbox{(substitute for }  z_1, z_2)\\
      &= (z_1 - z_2)(z_1+z_2), &\mbox{(factor)} \\
       &=  [z_1 -  z_2= 0]   \lor [z_1 + z_2 = 0]. &\mbox{(algebra fact)} 
\end{align*}
But \(z_1+z_2 \neq 0\) because both \(z_1\) and \(z_2\) are positive. So \(z_1 - z_2 = 0\); therefore \(z_1 = z_2\).
\end{myproof}
\end{frame}


\begin{frame}{Verbose (=bad) example}

\begin{myproof}  Let \(x  \in \reals_{> 0} \) and suppose that \(z_1, z_2 \in \reals_{> 0} \) and \(z_1^2 = x\) and \(z_2^2  = x\). For contradiction, suppose \(z_1 \neq z_2\) We have
\begin{align*}
   0 &= x - x,  & \mbox{(arithmetic)} \\
      &= z_1^2 - z_2^2,   &  \mbox{(substitute for }  z_1, z_2)\\
      &= (z_1 - z_2)(z_1+z_2), & \mbox{(factor)} \\
      &=  [z_1 -  z_2= 0]   \lor [z_1 + z_2 = 0].  &  \mbox{(algebra fact)} 
\end{align*}
But \(z_1+z_2 \neq 0\) because both \(z_1\) and \(z_2\) are positive.  And by assumption \(z_1 - z_2 \neq  0\); thus \(  (z_1 - z_2)(z_1+z_2) \neq  0\). This contradicts  \((z_1 - z_2)(z_1+z_2) = 0\); therefore \(z_1 = z_2\).

\end{myproof}

\begin{checklist}
\item The proof by contradiction is longer than the direct proof.

\item Concise and intelligible proofs are always better than a longer proof.

\end{checklist}

\end{frame}

\begin{frame}{Grubby practice}
\begin{myth} There is at most one \(x \in \reals\) such that \(x^5 + x^3 + 1 = 0\). \end{myth}

\begin{myproof}  Suppose   \(a,b \in \reals\) and that  \(a^5 + a^3 + 1= 0\) and \(b^5 + b^3 + 1= 0\). We have
\begin{align*}
   0 &= (a^5 + a^3 + 1) - (b^5 + b^3 + 1), \\
      &= \left( a-b\right) \, \left( {{b}^{4}}+a\, {{b}^{3}}+{{a}^{2}}\, {{b}^{2}}+{{b}^{2}}+{{a}^{3}} b+a b+{{a}^{4}}+{{a}^{2}}\right).
\end{align*}
Either \(a-b = 0\) or \( {{b}^{4}}+a\, {{b}^{3}}+{{a}^{2}}\, {{b}^{2}}+{{b}^{2}}+{{a}^{3}} b+a b+{{a}^{4}}+{{a}^{2}}= 0\). But the second is a sum of nonnegative terms, so the only way for it to vanish is if \(a=0\) and \(b=0\); for either case, we have \(a=0\) and \(b=0\).

\end{myproof} 
\begin{checklist}
\item That's a great deal of grubby algebra.

\item But a reader can check it if s/he wishes.

\end{checklist}

\end{frame}

\begin{frame}{When grubby algebra fails}

\begin{myth} There is at most one \(x \in \reals_{\geq 0} \) such that \(\sqrt{x+1}-\sqrt{x}-\sqrt{6}+\sqrt{5}\). \end{myth}

\begin{enumerate}

\item One such number is \(5\).  

\item Following the pattern of the previous example leads to factoring
\[
\sqrt{a+1}-\sqrt{a} - (\sqrt{b+1}-\sqrt{b})
\]
Maybe I don't know enough algebra, but I'm stuck.

\item But a bit of calculus shows that the function \(F = x \in \reals_{\geq 0} \mapsto \sqrt{x+1}-\sqrt{x}-\sqrt{6}+\sqrt{5}\) decreases.
\end{enumerate}

\end{frame}
\begin{frame}{Similarly}

\begin{myproof} Let \(F = x \in \reals_{\geq 0} \mapsto \sqrt{x+1}-\sqrt{x}-\sqrt{6}+\sqrt{5}\).  This derivative of \(F\) is everywhere negative, so this function is  decreasing. 
Suppose \(F(a) = 0\) and \(F(b) = 0\).  Either \(a < b\), \(a = b\), or \(a > b\).  For the case \(a < b\), we have
\begin{align*}
[a < b ] \implies [F(a) < F(b)] \implies [0 < 0] 
\end{align*}
But \(0 < 0\) is false, so \(a < b\) is false.  For the case \(a > b\), we have
\begin{align*}
[a > b ] \implies [F(a) > F(b)] \implies [0 > 0] 
\end{align*}
Again, \(0 > 0\) is false, so the assumption \(a > b\) is also false; since both \(a < b\) and \(a > b\) are false, we've shown that \(a=b\).


\end{myproof} 


\end{frame}

\end{document}