\documentstyle[11pt]{article}
\oddsidemargin=0.0in % 1" margins on all sides.
\evensidemargin=0.0in
\textwidth=6.5in
\topmargin=0.0in
\textheight=9.0in
\def\qed{ \ \vrule width.2cm height.2cm depth0cm\smallskip}
\newcommand{\myref}[1] {(\ref{#1})}
\newcommand{\A} {{\sf A}}
\newcommand{\B} {{\sf B}}
\renewcommand{\iff} {{\sc if and only if}} % used to be ``<=>''
\newcommand{\ifthen} {{\sc if{\ldots}then}}
\newtheorem{theorem}{Theorem}
\newtheorem{dfn}{Definition}
\newtheorem{conjecture}[theorem]{Theorem(?)}
\newenvironment{proof}
{\vspace{6pt} \noindent {\bf Proof: }}
{\(\qed\)}
\newenvironment{disproof}
{\vspace{6pt} \noindent {\bf Disproof: }}
{\(\qed\)}
\title{Morphology of Proof \\
An introduction to rigorous proof techniques}
\author{Craig Silverstein}
\date{\today}
\begin{document}
\maketitle
\section{Methodology of Proof --- an example} \label{intro}
{\sc Deep down}, all theorems are of the form {\sc if \A\ then \B}.
They may be expressed in some other way, such as {\sc all \A\ are \B}
or {\sc let \A\ be true. Then \B\ is true}, but the goal in each case
is to get from the assumptions~--- the \A\ part~--- to the
conclusions~--- the \B\ part. To prove a theorem, you combine the
{\em assumptions\/} with {\em definitions\/} and other {\em
theorems\/} and show that the conclusion is always true. The hard
part is figuring out what definitions and other theorems to use.
Definitions and theorems let you convert statements to other
statements; by stringing these definitions and theorems together you
can convert the statements of \A\ into the statements of \B. This
constitutes a proof. For instance:
\begin{theorem} \label{thm:2xx2}
Let $x$ be a number greater than or equal to $4$. Then $2^x \geq
x^2$.
\end{theorem}
This theorem converts the statement ``a number $x$ is greater than or
equal to $4$'' to ``for this number, $2^x \geq x^2$.
We can use it in the proof of another theorem, like so:
\begin{theorem}
Let $x$ be the sum of four squares, $a^2 + b^2 + c^2 + d^2$ where
$a$, $b$, $c$, and $d$ are positive integers. Then $2^x \geq x^2$.
\end{theorem}
If we can prove that $x$ is of necessity greater than or equal to $4$
(by noting, for instance, that $a$, $b$, $c$, and $d$ are at least
$1$, and thus their sum is thus at least $4$), then we can convert the
assumption of our theorem from ``$x$ is the sum of four positive
squares'' to ``$x$ is at least $4$.'' Then we can use the first proof
to convert the statement ``$x$ is at least $4$'' to ``$2^x \geq
x^2$.'' This completes our proof.
Often, we use definitions to expand out mathematical shorthand before
we can start applying proofs. For instance, if an assumption is ``$x$
is prime,'' we might need to convert it to ``$x$ has exactly two
positive divisors'' before continuing with the proof. {\bf If you are
at a loss for how to start a proof, convert all the terms in the
assumptions to their definitions.}
Here is a theorem that can be proved using these techniques.
\begin{theorem}
Let $S$ be a finite subset of some infinite set $U$. Let $T$ be the
complement of $S$. Prove $T$ is infinite.
\end{theorem}
Intuitively, this is saying that if you have an infinite supply of
something, and you take a finite amount of it away, you are left with
an infinite amount. This last sentence may seem obvious, but it is not
a proof. To obtain a rigorous proof, we must get from the assumptions
to the conclusion through theorems and definitions. We identify the
assumptions: ``$S$ is a finite subset of an infinite set. It has a
complement $T$.'' A good start is to expand the definitions in the
assuption.
\begin{dfn}
A set $S$ is {\em finite\/} if there exists a number $N$ such that
the number of elements in $S$ (denoted $|S|$) is less than $N$. If
no such $N$ exists, then $S$ is {\em infinite}.
\end{dfn}
Note that you give me the set $S$ before I try to figure out the
number $N$. Thus, if {\em any\/} number $N$ exists that is bigger than
$|S|$, I will be sure to find it, since I know what $S$ is. This
ordering concern (``first we have $S$, then we find $N$'') is
important with statements such as ``there exists'' or ``for all.''
\begin{dfn}
If $S$ and $T$ are both subsets of some set $U$, $T$ is the {\em
complement\/} of $S$ (under $U$) if $S \cup T = U$ and $S \cap T$
is $\emptyset$.
\end{dfn}
Now we use our definitions to convert our assumptions:
\begin{center}
\begin{tabular}{|p{2in}p{2in}|}
\hline
{\bf Original statement} & {\bf New statement} \\
$S$ is finite & There is a number $N$ such that $|S| < N$ \\
$U$ is infinite & There is no number $M$ such that $|U| < M$ \\
$T$ is the complement of $S$
& $S \cup T = U$ and $S \cap T$ is $\emptyset$ \\
\hline
\end{tabular}
\end{center}
We're still stuck, so we have to apply one of the proof methods which
will be discussed in the next sections, which let you work backwards
from the conclusion~--- the \B\ part~--- to help prove the
theorem. In particular, we need the common proof technique of {\em
proof by contrapositive}: We assume that the result is false, and show
that as a result, the assumptions must be false as well. But the
assumptions are never false (by assumption!) so the theorem must be
true.
In this case, we assume the result is false, that is that $T$ is in
fact finite. Then, applying a definition, there is a number $P$ such
that $|T| < P$. Since we know that $S \cup T = U$ and $S \cap T$ is
$\emptyset$, we know $|S| + |T| = |U|$ (if you don't know this, then
you can prove it on its own before you try to include it into this
proof). But we know $|S| < N$ and $|T| < P$, so $|S| + |T| < N+P$;
that is, $|U| < N+P$. But we have just violated the second
assumption, that there is no number such that $|U|$ is less than it.
The only weak link in our chain of deduction is that $T$ is finite, so
that claim must be wrong. Since the contradiction is wrong, the
theorem must be true. We write this up in a more terse, mathematical
form.
\begin{proof}
We know that $S \cup T = U$ and $S$ and $T$ are disjoint, so $|S| +
|T| = |U|$. Since $S$ is finite, $|S| < N$ for some $N$, and since
$U$ is infinite, $|U| \geq M$ for all $M$. So assume $T$ is finite,
that is, for some $P$, $|T| < P$. Then $|S| + |T| < N + P$, or,
substituting, $|U| < N + P$. But this contradicts our claim that $|U|
\geq M$ for all $M$.
\end{proof}
That box is how I indicate the end of a proof. I am limited in what
symbol I used by the fonts on my computer, but in general unlimited
creativity is allowed here.
\subsection{Summary --- how to prove a theorem}
\begin{enumerate}
\item Identify the assumptions and goals of the theorem.
\item Understand the implications of each of the assumptions
made. Translate them into mathematical definitions if you can.
\label{two}
\item Either try to massage the definitions and theorems that you
identified in \myref{two} into the statement you are trying to
prove, or, if that fails
\item Make an assumption about what you are trying to prove and show
that it leads to a proof or a contradiction.
\end{enumerate}
The last two items are the only two possible ways to convert your
assumptions into proof. These and other possible techniques for
proving theorems will be discussed in more detail in the next section.
\section{Taxonomy: techniques useful in proving a theorem}
\begin{enumerate}
\item Proving \iff\ proofs in two directions
\item Structural induction
\item Contrapositive
\item Counterexample
\end{enumerate}
\subsection{Taxonomy of Proof: if and only if}
{\sc While all proofs} are of the form \ifthen, many have more
complicated manifestations. The most basic proof has the form
\begin{center}
{\sc if \A\ then \B} or \\
{\sc \A\ implies \B} or \\
{\sc \A\ $\rightarrow$ \B}
\end{center}
which was explored in Section~\ref{intro}. This means that whenever
\A\ is true, \B\ is also true. A stronger connection between \A\ and
\B\ is implied by the form
\begin{center}
{\sc \A\ if and only if \B} or \\
{\sc \A\ $\leftrightarrow$ \B} or \\
{\sc \A\ iff \B}
\end{center}
The term ``if and only if'' is really a code word for equivalence. To
prove a theorem of this form, you must prove that \A\ and \B\ are
equivalent; that is, not only is \B\ true whenever \A\ is true, but \A\ is
true whenever \B\ is true. ``If and only if'' is meant to be interpreted
as follows:
\begin{center}
\begin{tabular}{rcl}
{\sc \A\ if \B} &means& {\sc if \B\ then \A} \\
{\sc \A\ only if \B} &means& {\sc if not \B\ then not \A}
\end{tabular}
\end{center}
It is a logical law that {\sc if \A\ then \B} is always equivalent to
{\sc if not \B\ then not \A} (this is called the contrapositive, and
is the basis to proof by contrapositive), so {\sc \A\ only if \B} is
equivalent to {\sc if \A\ then \B} as well.
When proving an \iff\ proof directly, you must make sure that the
equivalence you are proving holds in all steps of the proof. This
means that each step in the proof must use either a definition that is
\iff or a theorem that is \iff. Using a less rigorous \ifthen\
statement in one of your steps will invalidate your proof.
Making sure all the steps in your theorem obey this restriction is
usually difficult and often impossible. Therefore it is much more
common to use an alternate proof method: we physically {\bf break an
\iff\ proof into two proofs}, the ``forwards'' and ``backwards''
proofs. To prove a theorem of the form {\sc \A\ \iff\ \B}, you first
prove {\sc if \A\ then \B}, then you prove {\sc if \B\ then \A}, and
that's enough to complete the proof. Using this technique, you can
use \ifthen\ proofs as well as \iff\ proofs in your own proof.
\begin{theorem}
Let $x$ be a number. Let $\lfloor x \rfloor$ be the greatest
integer less than $x$, and $\lceil x \rceil$ be the smallest
integer greater than $x$. Prove that $\lfloor x \rfloor = \lceil x
\rceil$ if and only if $x$ is an integer.
\end{theorem}
\begin{proof}
\begin{itemize}
\item[$\rightarrow$]
In this direction we assume $\lfloor x \rfloor = \lceil x \rceil$ and
try to prove $x$ is an integer. Note that $\lfloor x \rfloor \leq
\lceil x \rceil$. Since $\lfloor x \rfloor = \lceil x \rceil$ (by
assumption), then $x = \lfloor x \rfloor$ as well by the sandwich
theorem. Since $\lfloor x \rfloor$ is an integer, $x$ must be as
well.
\item[$\leftarrow$]
Now we assume $x$ is an integer and try to prove that $\lfloor x
\rfloor = \lceil x \rceil$. If $x$ is an integer, then $\lfloor x
\rfloor = x$ and $\lceil x \rceil = x$ (by definition of both
terms), so $\lfloor x \rfloor = \lceil x \rceil$ as well.
\end{itemize}
\end{proof}
\subsection{Taxonomy of Proof: structural induction}
{\sc ``Straight'' induction} is an occasionally useful proof
technique. It is used to prove there exists a relationship between
some function of the integers and a given formula. Since there are an
infinite number of integers, brute force won't work (``Well, the
pattern holds for 1, and for 2, and for 3, and ...''), so we use
induction:
\begin{itemize}
\item Prove the pattern holds for the smallest number we care about.
\item Assume it holds for an arbitrary number $N$
\item Prove that if it holds for $N$, it must hold for $N+1$ as well.
\end{itemize}
Again, we can't escape the \ifthen\ construction. We can use
induction to prove Theorem~\ref{thm:2xx2} from Section~\ref{intro}.
Recall the theorem: if $x \geq 4$, $2^x \geq x^2$.
\begin{proof}
The base case here is $x = 4$, and $2^4 \geq 4^2$ so that's ok.
How about the inductive step? Assuming it's true for $n$
means that
\begin{equation}
2^n \geq n^2 \label{eqn:n}
\end{equation}
which we have to use to show it's true for $n+1$:
\begin{equation}
2^{n+1} \stackrel{?}{\geq} (n+1)^2 \label{eqn:n+1}
\end{equation}
To get the left-hand size of \myref{eqn:n} to look like the left hand
side of \myref{eqn:n+1}, we multiply both sides by 2 to get $2 \times
2^n \geq 2n^2$, or
\begin{equation}
2^{n+1} \geq 2n^2 \label{eqn:n-prime}
\end{equation}
Is $2n^2 \geq (n+1)^2$? Well, $(n+1)^2 = n^2 + 2n + 1$ which is less
than $2n^2$ if $2n + 1 < n^2$. This is not hard to prove, but I'll
prove it in a short but kinda tricky way which takes advantage of the
fact we know $n \geq 4$: $2 \times n < (n-1) \times n$ for $n \geq 4$,
and $1 < n$ for $n \geq 4$, so $2n + 1 < (n-1)n + n = n^2$ for $n \geq
4$. The point of this whole thing is that we can expand
\myref{eqn:n-prime} to say
\[ 2^{n+1} > 2n^2 > (n+1)^2 \]
But this inequality is just \myref{eqn:n+1} which is what we were
trying to show. Thus the induction holds.
\end{proof}
There aren't many places where straight induction is useful, however,
for we rarely try to prove things about integers. However, forms of
induction can be appropriate when trying to prove things about
structures defined recursively.\footnote{When you consider the
integers as such a structure, where all numbers are defined by
recursively adding one to itself, you get straight induction} For
instance, a {\em string\/} in computer science is defined as a
collection of characters, and proofs about strings often start with
proving the case for single-character strings (or the empty string)
and then proving the rest by induction. This generalized induction is
known as {\em structural induction}. It is useful when objects are
built up from more primitive objects: if we can show the primitive
objects have the desired property, and that the act of building
preserves that property, then we have shown that all objects must have
the property. The inductive hypothesis (i.e., the assumption) is to
assume that something is true for ``simpler'' forms of an object and
then prove that it holds for ``more complex'' forms. ``Complexity''
is defined as a relative term: one object is more complex than another
iff it includes that other object as a subpart. A classic use of
structural induction is to prove that any legal expression has the
same number of left parentheses and right parentheses:
\begin{theorem}
{\bf E} is a well-formed formula (wff) if it has one of the following
forms:
\begin{itemize}
\item a number (constant) or letter (variable)
\item {\bf E + F}, where {\bf E} and {\bf F} are both wffs
\item {\bf E * F}, where {\bf E} and {\bf F} are both wffs, or
\item {\bf (E)}, where {\bf E} is a wff.
\end{itemize}
Prove all wffs have the same number of left and right parentheses.
\end{theorem}
In this example, wffs of type 1 are the primitive types, while the
others make new wffs from simpler ones. We must take care not to
forget a case.
\begin{proof}
We let $E_($ be the number of left parentheses in a wff $E$ and $E_)$
be the number of right parentheses in $E$. We now consider each case
and its parentheses count:
\begin{center}
\begin{tabular}{lll}
case & number of (`s & number of )'s \\
1 & $0$ & $0$ \\
2 & $E_( + F_($ & $E_) + F_)$ \\
3 & $E_( + F_($ & $E_) + F_)$ \\
4 & $E_( + 1$ & $E_)$ + 1
\end{tabular}
\end{center}
In the last three cases, $E$ and $F$ are simpler than the complex
forms they are part of [$E+F$, $E*F$, or $(E)$], and hence for these
cases we can assume the inductive hypothesis for $E$ and $F$: namely,
that $E_( = E_)$ and $F_( = F_)$ for these simpler forms. Using this
assumption, we see that $[E+F]_( = [E+F]_)$, $[E*F]_( = [E*F]_)$, and
$[(E)]_( = [(E)]_)$. Finally, we see by inspection that in the base
case (1) the parenthesis count matches, so they match in all cases.
\end{proof}
\subsection{Taxonomy of proof: contrapositive}
{\sc Contrapositive is a quite powerful} method in proof: it allows
you to attack a proof backwards. Instead of going from the
assumptions and trying to derive the result, you start by assuming the
result is false and show that this violates one of the assumptions.
This makes use of the logical law of {\em contrapositive:}
\begin{center}
\begin{tabular}{rcl}
{\sc if \A\ then \B} & is equivalent to & {\sc if not \B\ then not \A}
\end{tabular}
\end{center}
Since we are assuming that the result is not true and end up by
contradicting our assumptions, this is a kind of proof by
contradiction known as {\bf proof by contrapositive}.\footnote{In the
general form of proof by contradiction, you assume both not \B\ and
\A, and work towards a contradiction somewhere in the middle. In
proof by contrapositive, the contradiction is always on the \A\ side.}
We used it back in Section~\ref{intro} for the very first proof; it is
used quite a lot. It gives a lot of flexibility in \iff, because it
allows us to interpret the ``forward'' and ``backward'' part of the
proof in several different ways:
\vspace{6pt}
\fbox{ \begin{minipage}{6in}
\begin{center}
{\bf The two parts of an \iff\ proof} \\
{\bf Prove:} \A\ iff \B.
\end{center}
\begin{itemize}
\item Prove \A\ implies \B. Then prove \B\ implies \A.
\item Prove \A\ implies \B. Then prove not \A\ implies not \B.
\item Prove \B\ implies \A. Then prove not \B\ implies not \A.
\end{itemize}
\end{minipage} }
\vspace{6pt}
By applying the law of contrapositive, it is fairly easy to see that
all three forms are in fact equivalent. This flexibility in proof
methods is yet another reason to prefer the two-step approach to if
and only if proofs to the monolithic approach.
\subsection{Taxonomy of proof: counterexample}
{\sc It may be significantly easier} to disprove something than to
prove it, for to prove a theorem false, often all you need to do is
provide a counterexample. ``Disproofs'' can be as simple as this:
\begin{conjecture}
All prime numbers are odd.
\end{conjecture}
\begin{disproof}
Two is prime, but two is even.
\end{disproof}
Usually, however, counterexamples are not that easy to come
by. Frequently, you are not asked to disprove something, but are given
a statement and told to either prove or disprove it. A good general
strategy in such cases is to {\bf search for a proof, but use any
weaknesses in your proof strategy to search for counterexamples}. Here
is an example of this technique. The definition we need here is this:
$a \bmod b$ is defined to be the unique integer $r$ such that, for
some $q$, $bq + r = a$, $bq \leq a$, and $b(q+1) > a$ . That is, $a
\bmod b$ is the remainder when $a$ is divided by $b$. Note that from
the definition it follows that $0 \leq a \bmod b < b$.
\begin{conjecture}
Prove or disprove: There is no pair of numbers $a$ and $b$ such
that $a \bmod b = b \bmod a$.
\end{conjecture}
When asked to do things with pairs of objects, it is often possible to
simplify the relationship between the two numbers to help with the
proof. In this case, we can assume $a < b$ without loss of
generality, because if $a > b$, we can swap $a$ and $b$ and get the
same equation~--- we are taking advantage of the problem's {\em
symmetry}. We must be careful not to forget the third case, however,
that $a = b$. This turns out to be the chink in our proof that leads
to a counterexample, but for right now let's plow ahead regardless.
First assume $a < b$. Then $a \bmod b = a$ (from the definition
above, with $q = 0$ and $r = a$). But $b \bmod a < a$, from our
observation above that $x \bmod y$ is always less than $y$. Hence $a
\bmod b \not= b \bmod a$ for any values of $a$ or $b$. By switching
around $a$ and $b$, we get a similar proof for the case $b < a$.
But now we try to prove the theorem for the case $a = b$. And here we
run into problems, because $a \bmod b = 0$ if $a = b$, and $b
\bmod a = 0$ if $b = a$, so then $a \bmod b = b \bmod a$,
disproving the theorem. Here's the disproof:
\begin{disproof}
The theorem is false: if $a = b = 2$, for instance, then $2 \bmod 2 =
2 \bmod 2$.
\end{disproof}
In the process of finding this counterexample, though,
we found out something more than was asked for: we know exactly
those conditions that make $a \bmod b = b \bmod a$. Thus we are
able to prove a modified version of the theorem.
\begin{theorem}
$a \bmod b = b \bmod a$ iff $a = b$.
\end{theorem}
Since this is an if and only if proof, we have to do it in two
directions. {\bf As is often the case in if and only if proofs, one
direction is much easier to do than the other}. We will do the easy
direction first.
\begin{proof}
\begin{itemize}
\item[$\rightarrow$]
We assume $a = b$ and prove $a \bmod b = b \bmod a$. But this is
clearly true, since $x \bmod x = 0$ for all $x$, and $a$ and $b$ are
equal.
\item[$\leftarrow$]
Here we have to prove that if $a \bmod b = b \bmod a$, then $a$ =
$b$. Try to find a direct proof, and then give up and do
the contrapositive: assume $a \not= b$, and prove that $a \bmod b
\not= b \bmod a$. There are two possible cases: $a < b$, and $a > b$
(we've already assumed $a \not= b$).
\begin{itemize}
\item[$a < b$] Then $a \bmod b = a$ . But by definition, $b \bmod a$
is strictly less than $a$, so it cannot be equal to
$a$ and hence can't be equal to $a \bmod b$.
\item[$a > b$] Then $b < a$, and the proof is the same as above with
$a$ replaced by $b$ and $b$ replaced by $a$.
\end{itemize}
\end{itemize}
\end{proof}
\end{document}