
\section{General Remarks about Proofs}

\subsection{What we expect in your proofs}

In practice, people do not write out real proofs about interesting
mathematical objects in a completely formal, step-by-step style
(unless they are using a computer-aided theorem prover)\.
Rather, they give a kind of proof sketch, skipping some steps\.  
That is what we expect you to do in your proofs on problem sets and tests\.

However, in writing out your proof sketches, it is very important to work {\em
correctly}, so that all the missing steps could be filled in\.  
As in a scientific experiment, it should be possible for someone else
to ``replicate'' (i.e., understand, fill in the details of) your proof\.
{\bf In your homework, that ``someone'' should be another 6.042 student.}

In the real world, anything that has already been proved somewhere
can be cited and used without proof\.
But in this course, you can't do this (because just about everything we ask you
to prove has already been proved somewhere)\.
General guidelines: \\
We don't expect you to reprove arithmetic\. 
Anything from high school math can be used without proof (unless
stated otherwise)\.
Once something has been proved in this course, you can use it again
without proof, citing the theorem\.  
Once it has been used so often as to become commonplace, you can even
stop citing the theorem.

{\bf Do not introduce any new axioms or rules of deduction!}

{\bf When in doubt about whether something can be stated without proof,
prove it!}

\subsection{Wrong proofs}

In this course (and later on), you will encounter incorrect proofs\.
It is good to learn how to find the bugs\.
If a proof is written carefully, the problem is usually obvious;
it's trickier when proofs are sketchy or sloppy\.
Some things that can go wrong: 
\begin{itemize}
\item Deriving a new statement by an invalid deduction rule, such
  as $A \implies B$, and $B$, therefore $A$.
\item Unstated axiom.  Gauss once said ``Clearly if a curve enters a
  region, it has to leave.''  This was accepted as a reason in a proof
  for a long time; only a century later was it cleared up.
\item Misusing a definition\.  Using something ``obvious'' in the
  {\em intent} of the definition that doesn't actually arise from the
  formal definition.
\end{itemize}
The most common problem is a gap between intuition and formalism.

\subsection{Example}
\begin{eqnarray*}
1 & = & \sqrt{1} \\
& = & \sqrt{(-1)(-1)} \\
& = & \sqrt{-1} \sqrt{-1} \\
& = & \sqrt{-1}^2 \\
& = & -1.\\
\mbox{So, }1 & = & -1!
\end{eqnarray*}
What is wrong?  
\forlecture{The assumption that $\sqrt{uv}=\sqrt{u}\sqrt{v}$ arises from
  our ``common usage'' of $\sqrt{\cdot}$ to be the {\em positive} square
  root\.  But this isn't defined for the sqrt of a negative number
  (which is complex, so not positive or negative).}

\forstudents{
\subsection{Wrong proofs through the ages...}

If you make mistakes, you are in good company. 
Even great mathematicians can goof proofs.
\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 for now).
\item Kempe's invalid ``proof'' of the Four Color Theorem stood for 10
years (1879--1890)
\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).
\item In the 1940's Paul Erdos conjectured a certain combinatorial fact about 
arithmetic progressions (every set of natural numbers of positive density 
contains arbitrarily long arithmetic progressions), and offered \$1000 for a
proof or disproof.  Endre Szemeredi proved the conjecture in 1972, but
the proof was so long and badly written that Erdos was not sure whether
to believe it.  Finally, Andras Hajnal stepped in and wrote a much clearer
version of the same proof, which was eventually published under Szemeredi's
name.  At some point during the write-up, Hajnal informed Erdos that
he was now confident enough of the proof that he was willing to buy it 
from Szemeredi for \$500.
\item  There's also the story of Newton waiting 20 years to publish
the Principia because he didn't see how to prove that one could assume all
the mass of a sphere to be concentrated at its center when calculating
gravitational attraction.  The proof ultimately required the invention 
of calculus$\ldots$

\end{itemize}
}
