\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}
%\renewcommand{\coursecopyrightyear}{2002}

\newtheorem{method}{Method}
\newcommand{\posints}{\integers^+}


\begin{document}
\lecturenotes{1}{Proofs}




\section{What is a Proof?}

A proof is a method of ascertaining truth.  There are many ways to
do this:

\begin{description}

\item[Jury Trial] Truth is ascertained by twelve people selected at
random.

\item[Word of God] Truth is ascertained by communication with God,
perhaps via a third party.

\item[Word of Boss] Truth is ascertained from someone with whom it is
unwise to disagree.

\item[Experimental Science] The truth is guessed and the hypothesis is
confirmed or refuted by experiments.

\item[Sampling] The truth is obtained by statistical analysis of many
bits of evidence.  For example, public opinion is obtained by polling
only a representative sample.

\item[Inner Conviction/Mysticism] ``{\em My} program is perfect.  I know
this to be true.''

\item[``I don't see why not...'']  Claim something is true and then
shift the burden of proof to anyone who disagrees with you.

\item[``Cogito ergo sum''] Proof by reasoning about undefined terms.

This Latin quote translates as ``I think, therefore I am.'' It comes from
the beginning of a famous essay by the 17th century
Mathematician/Philospher, Ren\'e Descartes.  It may be one of the most
famous quotes in the world: do a web search on the phrase and you will be
flooded with hits.

Deducing your existence from the fact that you're thinking about your
existence sounds like a pretty cool starting axiom.  But it ain't Math.
In fact, Descartes
\href{http://www.btinternet.com/~glynhughes/squashed/descartes.htm}{goes
on} shortly to conclude that there is an infinitely beneficent God.
\end{description}

Mathematics also has a specific notion of ``proof'' or way of
ascertaining truth.

\begin{definition*}
A \emph{formal proof} of a \emph{proposition} is a chain of \emph{logical
deductions} leading to the proposition from a base set of \emph{axioms}.
\end{definition*}

The three key ideas in this definition are highlighted: proposition,
logical deduction, and axiom.  Each of these terms is discussed in a
section below.

\iffalse The last section contains some examples of complete proofs.\fi


\section{Propositions}

\begin{definition*}
A {\em proposition} is a statement that is either true or false.
\end{definition*}

This definition sounds very general, but it does exclude sentences
such as, ``Wherefore art thou Romeo?'' and ``Give me an A!''.

\begin{proposition}
2 + 3 = 5.
\end{proposition}

This proposition is true.

\begin{proposition}
Let $p(n) \eqdef  n^2 + n + 41$.
\[
\forall n \in \naturals\; p(n) \text{ is a prime number}.
\]
\end{proposition}

The symbol $\forall$ is read ``for all''.  The symbol $\naturals$ stands for
the set of {\em natural numbers}, which are 0, 1, 2, 3, \dots; (ask your
TA for the complete list).  A {\em prime} is a natural number greater than
one that is not divisible by any other natural number other than 1 and
itself, for example, 2, 3, 5, 7, 11, \dots.

Let's try some numerical experimentation to check this proposition:
$p(0) = 41$ which is prime.  $p(1) = 43$ which is prime.  $p(2) = 47$
which is prime.  $p(3)=53$ which is prime. \dots $p(20) = 461$ which is
prime.  Hmmm, starts to look like a plausible claim.  In fact we can keep
checking through $n=39$ and confirm that $p(39)=1601$ is prime.

But if $n = 40$, then $p(n) = 40^2 + 40 + 41 = 41 \cdot 41$, which is not
prime.  Since the expression is not prime {\em for all}\/ $n$, the
proposition is false!  In fact, it's not hard to show that \emph{no}
nonconstant polynomial can map all natural numbers into prime numbers.
The point is in general you can't check a claim about an infinite set by
checking a finite set of its elements, no matter how large the finite
set. Here are two even more extreme examples:

\begin{proposition}
$a^4 + b^4 + c^4 = d^4$ has no solution when $a, b, c, d$ are positive
integers.  In logical notation, letting $\posints$ denote the positive
integers, we have
\[
\forall a \in \posints\forall b \in \posints\forall c \in \posints\forall
d \in \posints\; a^4 + b^4 + c^4 \neq d^4.
\]
\end{proposition}

Strings of $\forall$'s like this are usually abbreviated for easier reading:
\[
\forall a, b, c, d \in \posints\; a^4 + b^4 + c^4 \neq d^4.
\]

Euler (pronounced ``oiler'') conjectured this 1769.  But the
proposition was proven false 218 years later by Noam Elkies at the
liberal arts school up Mass Ave.  He found the solution $a = 95800, b
= 217519, c = 414560, d = 422481$.

\begin{proposition}
$313 (x^3 + y^3) = z^3$ has no solution when $x, y, z\in\naturals$.
\end{proposition}

This proposition is also false, but the smallest counterexample has
more than 1000 digits!

\begin{proposition}
Every map can be colored with 4 colors so that adjacent\footnote{Two
regions are adjacent only when they share a boundary segment of positive
length.  They are not considered to be adjacent if their boundaries meet
only at a few points.} regions have different colors.
\end{proposition}

This proposition is true and is known as the ``four-color theorem''.
However, there have been many incorrect proofs, including one that stood
for 10 years in the late 19th century before the mistake was found.  An
extremely laborious proof was finally found about 15 years ago by a
Mathematician named Haaken who used a complex computer program to 
categorize maps as four-colorable; the program left a couple of thousand
maps uncategorized, and these were checked by hand by Haaken and his
assistants---including his 15-year-old daughter.  There was a lot of
debate about whether this was a legitimate proof: the argument was too big
to be checked without a computer, and no one could guarantee that the
computer calculated correctly, nor did anyone have the energy to recheck
the four-colorings of thousands of maps that was done by hand.  Finally,
about five years ago, a humanly intelligible proof of the four color
theorem was found (see
\href{http://www.math.gatech.edu/~thomas/FC/fourcolor.html}
{http://www.math.gatech.edu/~thomas/FC/fourcolor.html}).

\begin{proposition}
The original Pentium chip divided properly.
\end{proposition}

Intel's ``proofs'' by authority and by sampling turned out to be
invalid.  The proposition is false.

\begin{proposition}[Goldbach]
Every even integer greater than 2 is the sum of two primes.
\end{proposition}

No one knows whether this proposition is true or false.  This is the
``Goldbach Conjecture,'' which dates back to 1742.

\section{Axioms}

\begin{definition*}
An {\em axiom} is a proposition that is assumed to be true.
\end{definition*}

There is no proof that an axiom is true; you just assume it is true
because you believe it is reasonable.  Here are some examples:

\begin{axiom}
If $a = b$ and $b = c$, then $a = c$.
\end{axiom}

This seems very reasonable!  But sometimes the right choice of axiom
is not clear.

\begin{axiom}[Euclidean geometry]
Given a line $l$ and a point $p$ not on $l$, there is exactly one line
through $p$ parallel to $l$.
\end{axiom}

\begin{axiom}[Spherical geometry]
Given a line $l$ and a point $p$ not on $l$, there is {\em no} line
through $p$ parallel to $l$.
\end{axiom}

\begin{axiom}[Hyperbolic geometry]
Given a line $l$ and a point $p$ not on $l$, there are {\em infinitely
many} lines through $p$ parallel to $l$.
\end{axiom}

No one of the three preceding axioms is better than the others; all
yield equally good proofs.  Of course, a different choice of axioms
makes different propositions true.  Still, a set of axioms should not
be chosen arbitrarily.  In particular, there are two basic properties
that one would want in any set of axioms; it should be consistent and
complete.

\begin{definition*}
A set of axioms is \emph{consistent} if no proposition can be proven to be
both true and false.
\end{definition*}

This is an absolute must.  One would not want to spend years proving a
proposition true only to have it proven false the next day!  Proofs
would become meaningless if axioms were inconsistent.

\begin{definition*}
A set of axioms is {\em complete} if it can be used to prove or
disprove every proposition.
\end{definition*}

Completeness is an attractive property; we would like to believe that
any proposition could be proven or disproven with sufficient work and
insight.

Surprisingly, making a complete, consistent set of axioms is not easy.
Bertrand Russell and Alfred Whitehead tried during their entire
careers to find such axioms for basic arithmetic and failed.  Then
Kurt G\"{o}del proved that no set of axioms can be both consistent and
complete!  This means that any set of consistent axioms (an absolute
must) can not be complete; there will be true statements that can not
be proven.  For example, it might be that Goldbach's conjecture is
true, but there is no proof!

In 6.042 we will not worry about the precise set of axioms underpinning
our proofs.  The requirements are only that you be upfront about what you
are assuming, that the background knowledge of Math that you assume is
self-consistent, and that you do not try to avoid homework and exam
problems by declaring everything an axiom!

\section{Logical Deductions}

Logical deductions or \emph{inference rules} are used to combine axioms
and true propositions to construct more true propositions.

A fundamental inference rule is \emph{modus ponens}.  This rule says that
if $p$ is true and $p \implies q$ is true, then $q$ is true.  The
expression $p \implies q$ is read ``$p$ implies $q$'' or ``if $p$, then
$q$.''  A truth table for $\implies$ is shown below:

\[
\begin{array}{c|c|c}
p & q & p \rightarrow q \\ \hline
T & T & T \\
T & F & F \\
F & T & T \\
F & F & T 
\end{array}
\]

\iffalse
In this table, $T$ stands for ``true'' and $F$ stands for ``false''.
Note that if $p$ is false, then $p \Rightarrow q$ is always true.  For
example, any statement beginning, ``If pigs fly, then ...'' is
true!
\fi

Inference rules are sometimes written in a funny notation.  For example,
\emph{modus ponens} is written:
\begin{rul*}
\Rule{p, \quad p \implies q}{q}
\end{rul*}

When the statements above the line, called the \emph{antecedents}, are
true, then we can infer that the statement below the line, called the
\emph{conclusion} or the \emph{consequent}, is also true.  There are many
other natural inference rules, for example:
\begin{rul*}
\Rule{p \implies q, \quad q \implies r}{p \implies r}
\end{rul*}

\begin{rul*}
\Rule{p \implies q, \quad \neg q}{\neg p}
\end{rul*}

Rosen describes additional standardized inference rules useful in proofs.
As with axioms, we will not be too formal about the set of legal inference
rules.  Each step in a proof should be clear and ``logical''; in
particular, you should state what previously proved facts are used to
derive each new conclusion.

\iffalse

\section{Examples of Proofs}

The first two examples are simple; the last two are more tricky.

\subsection{Direct Proofs}

\begin{theorem}[DeMorgan's Law]
For any sets $A$ and $B$, $\overline{A \cup B} = \overline{A} \cap
\overline{B}$.
\end{theorem}

The usual way to prove that two sets are equal is to show that each is
a subset of the other.  This means that the proof will have two parts.

\begin{method}
To prove $R = S$, show $R \subseteq S$ and $S \subseteq R$.
\end{method}

\begin{proof}
First, we will show $\overline{A \cup B} \subseteq \overline{A} \cap
\overline{B}$.  We do this by showing that any element of the left
side set is also in the right side set.

Let $x$ be any element of $\overline{A \cup B}$.  This implies that
$x$ is not an element of the complementary set, $A \cup B$.
Therefore, $x$ is contained in neither $A$ nor $B$.  Since $x$ is not
contained in $A$, it must be contained in the complementary set,
$\overline{A}$.  Similarly, since $x$ is not contained in $B$, it must
be contained in $\overline{B}$.  We now know $x \in \overline{A}$ and
$x \in \overline{B}$.  These facts imply that $x$ is contained in the
intersection $\overline{A} \cap \overline{B}$.  We have shown that any
element of the left side set is also in the right side set.  This
proves that $\overline{A \cup B} \subseteq \overline{A} \cap
\overline{B}$.

Second, we will show $\overline{A} \cap \overline{B} \subseteq
\overline{A \cup B}$.  We will use the same style of argument for the second
part of the proof; in fact, we will argue in reverse.

Let $x$ be any element of $\overline{A} \cap \overline{B}$.  This
implies that $x$ is an element of $\overline{A}$ and an element of
$\overline{B}$.  Since $x$ is an element of $\overline{A}$, it can not
be an element of the complementary set $A$.  Similarly, since $x$ is
an element of $\overline{B}$, it can not be an element of $B$.  We now
know that $x \notin A$ and $x \notin B$.  These facts imply that $x$
is not contained in the union $A \cup B$.  This implies that $x$ is
contained in the complementary set $\overline{A \cup B}$.  Again, we
have shown that any element of the left side set is contained in the
right side set.  This proves that $\overline{A} \cap \overline{B}
\subseteq \overline{A \cup B}$.

Since each of the two sets is contained in the other, the two sets
must be equal.
\end{proof}
This is tedious!  But this is the way to prove statements like this
directly from the definitions of the ``Boolean'' set-theoretic
operators union ($\cup$), intersection ($\cap$), and complement.

Actually, there is another way to prove such propositions about sets under
the set-theoretic operations.  We can
translate the set-theoretic equality into a Boolean formula involving
truth-valued variables under the corresponding Boolean operations $\land$,
$\lor$, and $\neg$ and then use truth-tables to check that the Boolean
formula is valid.  So the set-theoretic DeMorgan's law can be reduced to a
truth-table verification of the truth-value version of DeMorgan's Law:

\begin{theorem}[De Morgan]
For any Boolean variables $x$ and $y$,
\[
\neg(x \lor y) \equiv (\neg x \land \neg y).
\]
\end
{theorem}



A Boolean variable is one that is true/false or, equivalently, 0/1.  The
symbol $\equiv$ is read ``if and only if'' and is sometimes also written
``iff'' or $\Leftrightarrow$.  A statement of the form $S \Leftrightarrow R$ holds
provided $S$ is true exactly when $R$ is true.  A common mistake when
writing proofs with iff statements is to forget the only if part and to
only go one way, for example, to show only $S \implies R$.

\begin{method}[truth table method]
To prove a statement about a small number of Boolean variables, make a
truth table and check all the possible cases.
\end{method}

\begin{proof}\text{EDIT FOR DEMORGAN}
\[
\begin{array}{c|c|c|c}
x & y & x \rightarrow y & \neg y \Rightarrow \neg x \\ \hline
T & T & T & T \\
T & F & F & F \\
F & T & T & T \\
F & F & T & T
\end{array}
\]

\end{proof}

\subsection{Proofs by Contradiction}

The two preceding examples are {\em direct proofs}.  In a direct
proof, axioms and previously proved theorems are combined until a new
proof is done.  Sometimes an {\em indirect proof} is easier.  This is
also known as a {\em proof by contradiction}.  The idea is to assume
the opposite of what we are trying to prove and try to derive a
falsehood or contradiction.  Then we can conclude that the assumption
was false.  More formally, we have the following method.

\begin{method}[Proof by Contradiction]
To prove that $p$ is true, we prove that $\neg p \Rightarrow False$.
\end{method}

We can verify the validity of this technique by the truth table
method:

\[
\begin{array}{c|c|c}
p & \neg p & \neg p \Rightarrow False \\ \hline
T & F & T \\
F & T & F \\
\end{array}
\]

The table shows that $p$ is true iff $\neg p \Rightarrow False$.

A good example of proof by contradiction is the proof that $\sqrt{2}$ is
irrational (given in Lecture 1 Slides, and also in Rosen).
\fi

\section{Good Proofs and Bad Proofs}

An estimated 1/3 of all mathematical papers contain errors.  Even some
of the world's most famous mathematicians have botched proofs.  Here
are some famous examples.

\begin{itemize}

\item Andrew Wiles recently announced a proof of Fermat's Last
Theorem.  It was several hundred pages long.  It took mathematicians
months of hard work to discover it had a fatal flaw (so Wiles produced
another proof of several hundred pages; this one seems to have
convinced people).

\item Gauss's 1799 Ph.D. thesis is usually referred to as being the
first rigorous proof of the Fundamental Theorem of Algebra (every
polynomial has a zero over the complex numbers).  But it contains
quotes like
\begin{quote}
  "If a branch of an algebraic curve enters a bounded region, it must
   necessarily leave it again. ... Nobody, to my knowledge, has ever
   doubted [this fact].  But if anybody desires it, then on another
   occasion I intend to give a demonstration which will leave no
   doubt."
\end{quote}
Fields Medalist Steve Smale writes about this, calling it an "immense
gap" in the proof that was not filled in until 1920, more than a
hundred years later.

\item In 1900 Poincare carelessly claimed a certain very simple
topological characterization of the 3-dimensional sphere.  Later
realizing it was not so obvious, he demoted the claim to the status of
a "conjecture" in 1904.  The Poincare Conjecture is now one of the
biggest open questions in mathematics (two Fields Medals have been
given out for partial progress on it).

\end{itemize}

Here are some of the characteristics of a good proof:

\begin{itemize}

\item It is clear and \emph{correct}!

\iffalse
\item It is elegant; surprisingly short or clever.  Like a ``nice
hack'' in code.
\fi

\item It has a nice structure, like a good program.  It is broken up
into separate parts
\iffalse
\footnote{The correct plural of ``lemma'' is
undeniably ``lemmata'', but users of the latter term often die young
from mysterious... accidents.}
\fi
that define and prove key intermediate properties.
This makes it easy to understand the reason the whole thing works.  It
also makes it more likely that pieces can be reused.

\item The pieces are general and abstract.  This avoids the clutter of
unnecessary hypotheses, useless restrictions, etc.  Again, the analogy
to programming holds; a subroutine should be as generally applicable
as possible.

\item Important conclusions are not ``justified'' by being ``left to the
reader,'' nor by intimidating phrases like ``it is obvious that\dots'' or
``any moron can see that\dots.''  These phrases save the writer's time,
but consume the reader's time.  Mistakes in proofs are typically found in
these parts ``left to the reader.''

\item Like a scientific experiment, someone else must be able to
``replicate'' (i.e. understand) your proof.

\end{itemize}

Proofs are important.  They permit you to convince yourself and others
that your reasoning is correct.  The insights gained can help you
understand why something is true and whether it will stay true when
other things change.  Proofs are particularly important in computer
science and electrical engineering.  Bugs have proven costly for
Intel, AT\&T, and Airbus.  A good proof is strong evidence that no
bugs exist.

\end{document}
