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

                                %\makeslides

\renewcommand{\bar}[1]{\overline{#1}}

\begin{document}

\onlystudents

\lecture{notes1}{Proofs}{February 6, 2001}

\renewcommand{\thepage}{\arabic{page}}

\noindent
Topics for today:
\begin{itemize}
\item
  Course overview
\item
  What is a proof?
\item
  Propositions
\item
  Logical systems
\item
  Proof examples 
\end{itemize}


\reading{Velleman Chapter 1, 2; Sections 3.1, 3.2. \\
  Rosen 1.1, 1.2, 1.4, 1.6, 3.1}

\section{Course Overview}


\subsection{Course Goals and Content}

This course is actually a combination of three ``miniature'' courses:
thinking (9 lectures), counting (8), and gambling (9).  We aim to
cover:

\begin{description}
\item[Basic discrete math concepts.]
  Basic data types and structures used in programming and in reasoning
  about computer systems\.
  Numbers, Booleans, strings; sets, functions, relations; digraphs, graphs,
  trees; state machines\.
  Their properties.

\item[Proofs.]
  How to do them, how to read them, how to recognize correct/incorrect ones\.
  Reasoning about propositions, about predicates (with quantifiers)\.
  Common proof strategies:  Direct proof, proof by contradiction, by cases\.
  Induction (very important in this course and elsewhere in CS)\.  We'll
  be working on this topic throughout the term.

\item[Mathematical foundations for programming.]
  Basic concepts and methods underlying formal specification and verification
  of software systems\.
  Developing models for programs and their required behavior\.
  Proving that a program model satisfies its correctness requirements (6.170).

\item[Analytic Tools.]  The quantitative part of discrete math\.
  Methods for handling series, sums, recurrences, asymptotic analysis,
  counting\.  More than calculus, The kind of math that tends to arise
  in computer science problems\.
  Much used in analysis of algorithms (6.046).

\item[Discrete probability.]  
  How to analyze random events\.
  Probability provides good ways of modeling the unpredictability of the
  real world\.
  Critical in the study of real computer systems (6.033).
\end{description}

Overall, we want you to learn how to use mathematics to help you think
about concepts in computer science:
\begin{itemize}
\item Define abstract models for computer science objects like programs,
  computers, networks...
\item Think about these models carefully, correctly.
\item Use the conclusions to help understand the real-world objects.
\end{itemize}

\forlecture{

\subsection{Administrivia}

  {\large \bf SIGN UP} {\tt http://theory.lcs.mit.edu/classes/6.042/}

  \noindent
  See Handout 1\.
  Faculty, TAs, secy
  Prerequisites: First year calculus\.
  Books\.
  Handouts\.
  Lectures, tutorials\.
  Exams\.
  Problem sets\.
  Collaboration policy\.
  Grading
  }

\section{What is a proof (and why should we care)?}

Rough definition:  A way of convincing people that a statement is true\.
But there are many ways to convince someone that a statement is true,
for example:
\begin{description}
\item[Experimental evidence], e.g., physics experiments to validate 
  theories of General Relativity; medical experiments to
  validate that rats that eat sugar get cancer.
\item[Statistical sampling] e.g., Gallup polls to convince people that
  Bush will be elected President.
\item[Citing a reputable authority.]  ``The professor/boss said
  the answer to the problem was...''.
\item[Religion,] the most reputable authority of all.
\item[Acting confident, talking loudly.] ``I'm sure my program
  works now.'' 
\item[I don't see why not.] Shifting the burden of proof to someone
  who disagrees with you. 
\item[Legal system.] Uses ``proof beyond a reasonable
  doubt''---convince a judge and jury
\end{description}

These are not proofs, at least, not in the mathematical sense\.
All of these methods can go wrong, for example:
\begin{itemize}
\item Experiments can be contaminated or otherwise messed up.  
\item Statistics can be misleading. Consider Florida election!
\item Authorities can make mistakes, e.g., Intel said the original
  Pentium chip worked fine.
\item Juries can be fooled.
\end{itemize}
General problem: methods don't convince everyone.

Mathematics uses a particularly convincing way to argue that something is
true:
\begin{definition}
  A {\em proof\/} is a formal verification of a {\em proposition\/} by a chain of
  {\em logical deductions\/} starting from a base set of {\em axioms\/}.
\end{definition}
The important pieces of this definition are:
\begin{description}
\item[Formal language:] 
  Need a precisely defined language for expressing everything.
\item[Proposition:] 
  Statement in the language, e.g., what you want to prove. 
\item[Axioms:] 
  Statements that you are assuming in your proof. 
\item[Logical deductions:] 
  Getting a new truth from old ones, according to agreed-upon,
  formal rules of deduction. 
\end{description}
In the rest of this lecture, I'll explain what these things are,
present basic proof methods, and give examples.

The main idea is to specify everything so precisely that everyone is
convinced\.  If people accept the assumptions and deduction rules,
they must also accept the conclusions\.  Also, even if we can't
understand the entire argument at once, if we believe each deductive
step, we can be comfortable accepting the conclusions\.  This is a
philosophical position, and thus debatable, but most of modern
civilization accepts it.

We will try to teach you how to read and write proofs\.  By learning
to read and do proofs, you will be able to
\begin{itemize}
\item Convince others
\item Find flaws in others' attempts to convince you
\item Find flaws in your own proofs, so can figure out what else you
  need to find out or assume
\end{itemize}

Proofs are like programs, so you also develop the ability to reason
carefully about, attack, and defend ideas that arise in your (and
other people's) computer system designs and implementations.

\section{Basic data types}

\forstudents{\reading{Velleman chapter 1, Rosen 1.1-1.6}}

First, we need to agree on some basic language of discourse
so we can say things to each other.  
We'll be using the standard basic data types used in programming:
numbers, Booleans (true/false)\.
(Also later strings, but skip for now.)
We'll also use other basic data types from mathematics, such as sets and 
functions\. 
These are used in reasoning about programs\.  
This is review for most of you, so I won't lecture about it\.  
I'll just list the basic notions:  definitions, operations, some properties\.
You will be expected to read this material carefully on your own, making sure 
you can do all the study exercises.

\subsection{Booleans}

\forstudents{\reading{Velleman 1.1--1.2, Rosen 1.1}}

Values: 1 (true), 0 (false)\.
Operations: and ($\wedge$), or ($\vee$), not ($\neg$), exclusive-or
($\oplus$)\. 
\\
These operations can be explained with tables:
\\
\begin{tabular}{cc}
  $x$ & $\neg x$ \\
  \hline 
  1   & 0 \\
  0   & 1 \\
\end{tabular}
\\
\\
\begin{tabular}{ccccc}
  $x$ & $y$ & $x \wedge y$ & $x \vee y$ & $x \oplus y$ \\
  \hline 
  1   & 1   & 1            & 1          & 0\\ 
  1   & 0   & 0            & 1          & 1\\
  0   & 1   & 0            & 1          & 1\\
  0   & 0   & 0            & 0          & 0\\
\end{tabular}

\subsection{Numbers}

\forstudents{\reading{Rosen, Section 1.4}}
These are just the standard number classes.
\begin{description}
\item[Natural numbers] $\naturals = \{ 0, 1, 2, \ldots \}$ 

  Most math books actually let $\naturals$ start at 1 rather than 0,
  but computer scientists like to start counting with 0\.  We'll stay
  consistent with the course texts and start with 0\.  We'll write
  $\naturals^+$ for the positive naturals.

  Operations: $+$, $-$ (a partial function), times, integer division (round
  down), remainder (mod), exponentiation

  \forstudents{Prime number: Natural number $\geq 2$ that has no
    divisors except for itself and $1$\.  Example: 7 is prime, 14 is
    not.  }

\item[Integers,] denoted by $\ints$: $\naturals$ and its negatives 
\item[Rationals,] denoted by $\rationals$ 

  These are all numbers that are expressible as a ratio of two integers ${a
    \over b}$, where $b \neq 0$\.  A basic theorem (we might prove it
  later) says that we can write any rational number in lowest terms.
\item[Reals,] denoted by $\reals$
\end{description}

 \subsection{Strings}
 
 Strings are sequences of symbols drawn from some fixed alphabet\.  
 For example, if the alphabet consists of $a, b, c$, some examples of 
 strings are $abc$, $aaa$, $b$, and the empty string ($\lambda$, a shorthand 
 for no symbols)\.
 The main interesting operation is concatenation\. 
 Concatenating the two strings $abc$ and $bba$ gives the string $abcbba$.

\subsection{Sets}

\forstudents{\reading{Velleman 1.3--1.4, Rosen  1.4--1.5}}

Values: $\emptyset$, universal set $U$, singleton sets $\{ a \}$\.
Relationships:  Subset ($\subseteq$), proper subset ($\subset$)\.
Operations are:  Union ($\cup$), intersection ($\cap$), complement
(overbar)\.  

Venn diagrams are useful for reasoning about sets\.
There are many laws about how the operations behave---see Rosen p. 49\.
E.g.: $A \cup A = A$\.
                                %We'll come back to this later.

\subsection{Functions}

\forstudents{\reading{Rosen, Section 1.6}}

A function is a rule that assigns an element of one set (known as the range) 
to each element of another set (the domain)\.
Operations include function inverse and composition ($f \circ g(x) =
f(g(x))$)\.
We'll come back to this later.

\section{Propositions}

Now we consider the kinds of statements that we might want to convince people 
about\.

\subsection{What are propositions?}

\begin{definition}
  A {\em proposition\/} is a statement that has a truth value,
  $\ms{true}$ or $\ms{false}$. 
\end{definition}

Examples:
\begin{enumerate}
\item
  $5$ is a prime number. 

  This is a proposition, and it's true. 

\item
  $8$ is a prime number. 

  This is a false proposition.

\item
  $x$ is a prime number. 

  This is not a proposition\.
  It has no truth value, because we don't know what $x$ is\.
  It's said to be an {\em unbound variable}. 

\item 
  There is an least one prime number.

  This is a true proposition\.  In math notation, it can be written as
  $\exists x (x \mbox{ is a prime})$\. The quantifier $\exists$
  ``binds'' $x$.

\item
  All natural numbers $\geq 2$ are primes. 

  This is a false proposition\.  It can be written as $\forall x \in N,
  x \geq 2 (x \mbox{ is a prime})$\. The quantifier $\forall$ also binds $x$. 

  We will revisit the quantifiers soon (they have their own reasoning
  methods)\.  For now, we are just using them as shorthand notation for
  the English phrases. 

\item
  All $x$ of the form $n^2 + n + 41$, where $n \in N$, are prime. 

  This is a proposition\.
  Is it true or false?
  That's not immediately obvious\. 
  Certainly this proposition is true for many natural numbers $n$:

  \[
  \begin{array}{cc}
    n = 0 \rightarrow 41 & (prime) \\
    n = 1 \rightarrow 43 & (prime) \\
    n = 2 \rightarrow 47 & (prime) \\
    n = 3 \rightarrow 53 & (prime) \\
    \ldots & (more\ primes) \\
    n = 20 \rightarrow 461 & (prime) \\
    \ldots & (still\ more\ primes) \\
    n = 39 \rightarrow 1601 & (prime)
  \end{array}
  \]

  However, if $n = 40$, then $n^2 + n + 41 = 40^2 + 40 + 41 = 41 \cdot 41$,
  which is not prime\.  
  Since it is not the case that the expression is prime {\em for all} $n$, 
  the proposition is false!

\item 
  ``true'' and ``false'' are regarded as propositions, 
  with the obvious truth values.

\item
  $\forall A, B (\bar{A} \cup \bar{B} = \overline{A \cup B})$. 

  Propositions can be about other things besides numbers, for instance, sets\.
  This proposition happens to be false. 

\forstudents{
\item
  $\forall A, B (\bar{A} \cup \bar{B} = \bar{A \cap B})$. \\
  $\forall A, B (\bar{A} \cap \bar{B} = \bar{A \cup B})$. 

  These are called De Morgan's laws and are true.
}

\item
  The original Pentium chip always divided correctly\.

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

\item White can always win at chess.

  A proposition whose truth value nobody knows.

\item Every even integer greater than 2 is the sum of two prime
  numbers.

  No one knows whether this proposition is true or false\.  This is
  the Goldbach Conjecture, which dates back to 1742\.  It was described
  in {\em The Boston Globe} as ``one of the great unsolved
  mysteries.'' 
  Unfortunately, the ``example'' they gave was $20=9+11$!

\item There is no $x, y, z \in N^+, n \geq 3$ such that $x^n + y^n =
  z^n$.

  This is Fermat's last theorem, which he stated in the 1640s\.  
  Although he claimed it, he never proved it\. 
  Only recently have we learned for sure that it's true\.  
  Andrew Wiles, in 1994, gave a 130-page proof\.  
  After months of work, other mathematicians found bugs\. 
  Wiles needed hundreds of more pages to fix them\.  
  But even while we didn't know if it was true or false, it
  was still a proposition.

\item There is no $x, y, z, w \in \naturals^+$ such that
  $x^4+y^4+z^4=w^4$.  

  Note the similarity to Fermat's Theorem\.  This statement was
  conjectured by Euler (1769)\.  The first counterexample was found by
  Elkies, 218 years later\.  The smallest one:
  $95800^4+217519^4+414560^4=422481^4$.

\item Every map can be colored with four colors, in such a way that no two
  adjacent regions have the same color (Four-Color Theorem).

  This proposition was first ``proved'' in 1879\.  
  The ``proof'' stood for 10 years before a flaw was found\.  
  Recently, the theorem was proved with computer aid\.
  People still debate whether this is a valid proof\.  
  After all, nobody has proved that the computer is working correctly!
\end{enumerate}

Not all sentences are propositions:
\begin{itemize}
\item $x = y$.  (Truth depends on knowing what $x$ and $y$ are.)
\item What time is it?
\item This sentence is false.
\end{itemize}

Propositions involve previously {\em defined} terms:
     \begin{itemize}
     \item prime, map, triangle, chess, fair coin, probability.
     \item $+$, $=$, $1$, $\ge$.
     \end{itemize}

\subsection{Compound propositions and truth tables}

Logical connectives are used to combine simple propositions into compound
propositions\.
And ($\wedge$), or ($\vee$), exclusive-or ($\oplus$), and not ($\neg$),
which we already mentioned for Booleans, are also used for propositions\.  
Other connectives used for propositions include implication 
(if-then, $\implies$) and double implication 
(equivalence, $\Leftrightarrow$)\.  
These are very important in logical reasoning\.
The truth values of compound propositions are obtained from the truth
values of the simpler propositions according to the {\em truth tables\/}:

\begin{tabular}{cc}
  $P$  & $\neg P$ \\
  \hline T  &   F \\
  F  &   T \\
\end{tabular}

\noindent If a proposition $P$ is true, then its negation is false, and
vice versa.

\begin{tabular}{ccccc}
  $P$  & $Q$ &    $P \wedge Q$ &  $P \vee Q$ & $P \oplus Q$ \\
  \hline
  T  &  T     &  T &             T   &        F\\
  T  &  F    &   F  &            T  &         T\\
  F  &  T   &    F   &           T &          T\\
  F  &  F  &     F    &          F&           F\\
\end{tabular}

Important: $\vee$ means {\bf inclusive} or\.  
It is true if either \emph{or both} of the two statements are true\.  
Sometimes in English or is used to mean exclusive or: 
``David or Lars will teach today'' is saying one but not both.
%%
%% As I am not a native English speaker, I cannot really make any
%% definite statements on the meaning of either...of in English, but my
%% dictionaries suggest that, depending on the context, it can actually
%% mean either OR, or XOR, or AND! The sample sentences I found include:
%%  
%% 1. He must be either mad or drunk.
%%  
%% 2. He is taller than either you or me.
%%  
%% 3. There were houses on either side of the road.
%%  
%% 4. Either of them will do.
%%
%% Perhaps we should also add a comment roughly as follows:
%%
%%   In general, we will be *very* explicit if we want you to use XOR,
%%   i.e., we would write something like "prove that either X or Y, but
%%   not both, holds".
%%
%% This would reduce some problem set confusions.   /Lars
%%

\vspace{2ex}

\begin{tabular}{cccc}
  $P$ & $Q$ &   $P \Rightarrow Q$ &  $P \Leftrightarrow Q$ \\
  \hline
  T&    T   &       T  &               T \\
  T &   F  &        F   &              F \\
  F  &  T &         T    &             F \\
  F   & F&          T     &            T \\
\end{tabular}

The nice thing about these truth tables is that it doesn't matter what
the specific propositions are; we know how to get compound truth value
from basic truth values.

The only slightly mysterious column here is the implication column\.
We say that $P \Rightarrow Q$ is false only if the hypothesis $P$ is
true and the conclusion $Q$ is false\.  Some thought shows this aligns
with our intuition\.  Consider the statement ``if you do your
homework, then I will give you an A''\.  Under what circumstances
would you accuse me of lying\?  Well, I am clearly lying if you do
your homework but then you don't get an A\.  But if you skip your
homework and I give you an A \emph{anyway,} you won't say I'm lying\.
In this case the statement promises nothing, so it is true regardless
of what I do.

One way to determine truth values for compound propositions is by
adding new columns to the basic truth table(s).  Consider for example 
\[
(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) 
\]
To decide the truth value of this messy proposition, we can evaluate
its sub-propositions in a truth table and then combine their evaluations to
evaluate the whole\.  This yields a column containing all T values\.  
That is, the expression is always true, regardless
of the truth values of $P$ and $Q$.

\begin{tabular}{ccccccc}
  $P$  &$Q$  &  $P \Rightarrow Q$  & $\neg Q$&  $\neg P$ &  $\neg Q\Rightarrow\neg P$ & $(P \Rightarrow Q) \Leftrightarrow (\neg Q \Rightarrow \neg P) $ \\
  \hline
  T&    T   &       T &              F   &      F&        T &T\\
  T &   F  &        F  &             T  &       F &       F &T\\
  F  &  T &         T   &            F &        T  &      T &T\\
  F   & F&          T    &           T&         T   &     T &T\\
\end{tabular}

An expression (like this one) whose column contains all T is called a
{\em tautology}.


\section{Logical Systems}

Now we can say what proofs are\.  
A proof takes {\bf axioms} and {\bf definitions} and
uses {\bf deduction rules}, step by step, to get a desired conclusion.

\subsection{Axioms}

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

Axioms aren't proved---just accepted as reasonable assumptions\.
``Axiom'' is Greek for ``to think worthy,'' not ``to be true''\.
Here are some examples:

\begin{axiom}[Arithmetic]
  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}
None 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\.  In fact, the axioms above are
mutually contradictory---they can't all be true\.  

Mathematicians still argue about which axioms are ``right,'' e.g.,
there is a lot of debate about the Axiom of Choice (whose assertion
and denial are equally consistent with other commonly agreed upon
axioms).

Axioms provide us with a place to start in building proofs\.
Every argument has assumptions\.  
To be rigorous, it is important to state those assumptions explicitly as 
axioms. 

In the real world axioms capture our beliefs about what we are
studying (e.g. Newton's mechanics)\. Definitions capture what we think
is important (e.g. force, velocity)\.  If we prove something with
those axioms, we tend to believe it about the real world\.  If the
real world turns out different, we need to change our axioms (Einstein
made us discard Newton's axioms).

\subsection{Definitions}

Definitions are used to agree on what something means.
\begin{itemize}
\item A natural number $\geq 2$ is prime if it has no divisors other than 
  itself and 1.
\item A divisor of an integer $z$ is a nonzero integer $d$
  for which there exists some integer $k$ such that $z = k d$.  We say
  $d \mid z$
\item A triangle is a polygon with 3 sides.
\end{itemize}
Definitions are axiomatic: we can define terms to mean whatever we want, 
so long as we do so unambiguously\. 
Definitions can be built from prior definitions: polygon, integer.

\subsection{Deduction Rules}

These are also called inference rules\.  They are rules for combining
axioms and true propositions to construct more true propositions\.
The most fundamental inference rule is called \emph{modus ponens}
(Latin: method of affirming)\. Another important rule is called
\emph{modus tollens} (Latin: method of denying)\.
\begin{enumerate}
\item Modus ponens: \\
  Given that $P$ and $P \Rightarrow Q$ are both true \\
  Conclude:  $Q$ 

\item Modus tollens (proof by contradiction): \\
  Given:  $P \Rightarrow Q$, $\neg Q$ \\
  Conclude: $\neg P$ 

\item (Special case of Modus Tollens) \\
  Given:  $\neg P \Rightarrow \ms{false}$ \\
  Conclude:  $P$ 

\item (Another special case) \\
  Given: $P$, $\neg P$: \\
  Conclude: $\ms{false}$ 

\item Syllogism: \\
  Given:  $P \Rightarrow Q$, $Q \Rightarrow R$ \\
  Conclude:  $P \Rightarrow R$ 

\item (Cases): \\
  Given: $Q \Rightarrow P$, $\neg Q \Rightarrow P$ \\
  Conclude: $P$
\end{enumerate}

These deduction rules rely only on the truth values of the statements 
$P,Q,R$, and \emph{not} on what the particular statements are\.  So we can 
apply them in many situations.

Truth tables provide a source of deduction rules, all of which are
accepted in mathematics\.
Namely, if $R \Rightarrow S$ is a tautology, then \\
Given: $R$ \\
Conclude: $S$ \\
is an allowable inference rule\.

\noindent
Examples: 
\begin{enumerate}
\item
  $[P \wedge (P \Rightarrow Q)] \Rightarrow Q$ 
  is a tautology (check the truth table), which leads to (Modus Ponens): \\
  Given: $P \wedge (P \Rightarrow Q)$ \\
  Conclude: $Q$ 

\item
  $(P \wedge \neg P) \Rightarrow \ms{false}$ is a tautology, which leads to: \\
  Given: $P$, $\neg P$: \\
  Conclude: $\ms{false}$ 

\item
  $[(P \vee Q) \wedge \neg P] \implies Q$
  is a tautology, which leads to (Disjunctive Syllogism): \\
  Given: $P \vee Q$, $\neg P$ \\ 
  Conclude: $Q$ 
\end{enumerate}

Another way of getting acceptable deduction rules from a truth table,
exemplified using Modus Ponens again: \\
In the truth table, look at the rows where $P$ and $P \Rightarrow Q$ 
are both true\.
$P$ is true in rows 1, 2 \.
$Q$ is true in rows 1, 3, 4 \.
So, both are true exactly in row 1\.
But in that row, $Q$ is also true. 

\subsection{Formal proofs}

In a complete, formal proof of a theorem, each step follows from
previous steps using formal deduction rules\.  There is no room for
debate or misinterpetation\.  Such a process is ideally so systematic
that it could be checked mechanically by a program\.  Modern theorem
proving programs can do this.

Mathematicians generally don't write proofs that formally\.
Rather, they write them in concise prose, but in such a way that others who
are knowledgeable about proof methods can understand how to fill in the
gaps\.  You must develop a sense of the ``right level of detail'' for
proofs in this course.

What about using a computer to {\em produce\/} proofs of true theorems
automatically?  

Russel and Whitehead, in {\em Principia Mathematica}, tried to write
down a sufficient set of axioms that would let us prove everything
interesting\.  Then Hilbert posed (as one is his 23 famous problems)
the problem of finding such a method\.  One of the great
accomplishments of 20th century math is the proof that no such method
exists (G\"odel)\.  In fact, we don't even have a proof that the
axioms of math are consistent!  Maybe they are all
self-contradictory\!  But they have stood up well over time.

Even if we limit ourselves to things that can be proven, computers
won't be much help\.  Finding a proof---even, say, just a proof that a
given propositional logic statement is a tautology---is {\bf
  NP-complete}\.  This means that it is intractable in a certain
formal sense you will learn about in 6.045 or 6.046.

So we will always rely on human intuition to find the proofs, although
we will be using computers more and more to check if they are right.



\section{Proof examples}

\forstudents{\reading{Velleman Chapter 3, Rosen, Section 3.1}}

This section contains some examples of proofs using the deduction rules
described above\.
They are presented at about the level of detail commonly used by 
mathematicians\.
The examples illustrate basic methods: 
direct proof, proof by contradiction, and proof by cases\.  

These proofs are written in a stylized way, using statements and
reasons (as in high school geometry proofs)\.  
In math books, proofs are usually presented in prose, with the 
logical structure left implicit\.
Caution: 
The proof writer is expecting the reader to figure out the logical
structure\.
To understand the proofs, you really have to do this. 
                                %It should always be possible to rewrite any of these proofs in
                                %structured form (given enough time)\.

\subsection{Direct proof}

To prove that a proposition of the form $P \Rightarrow Q$ is true, it
is enough to assume $P$ and show $Q$\.  Written in a structured style,
the pattern of such a proof is:
\begin{structproof}
  Prove:  $P \Rightarrow Q$ \\
  1. Assume $P$. \\
  2. $Q$ \\
  3. QED 
  \> \> \> \> \> Implication \\
\end{structproof}
QED stands for Quod Erat Demonstrandum, Latin for ``which was to be
proved''\.  Here, it's a shorthand for writing the goal out again as
the final step\.  In paragraph proofs, you often just write a box:
$\qed$

\begin{example} 
  Let's prove that the sum of the first 100 numbers, $1 + ... + 100$,
  is 5050\.
  We'll rewrite this as an implication and use the direct proof rule
  above.

  \begin{proofoverhead}
    Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
    1. Assume  $S = 1 + ... + 100$. \\
    2. $S = 5050$ 
    \> \> \> \> \> ??? \\
    3. QED  (That is, $S = 1 + ... + 100 \Rightarrow S = 5050$.) 
    \> \> \> \> \> Implication 
  \end{proofoverhead}

  Of course, the interesting part is to fill in the ???\.  This needs
  some calculations:

  \begin{proofoverhead}
    Prove:  $S = 1 + ... + 100 \Rightarrow S = 5050$. \\
    1. Assume  $S = 1 + ... + 100$. \\
    2. $S = 5050$ \\
    \> 1. $S = 100 + 99 +...+ 1$  
    \> \> \> \> Commutativity of addition \\
    \> 2. $2S = 101 + 101 + ... + 101$  (100 terms) 
    \> \> \> \> Add term-by-term \\
    \> 3. $2S = 10,100$           
    \> \> \> \> Add the terms up \\
    \> 4. QED  (That is, $S = 5050$.) 
    \> \> \> \> Divide by 2 \\
    3. QED ($S = 1 + ... + 100 \Rightarrow S = 5050$.) 
    \> \> \> \> \> Implication 
  \end{proofoverhead}
\end{example}

\begin{example}
  The following argument shows a property of basic set theory\.
  It says that, if an element $x$ is in the complements of sets $A$ and
  $B$, then it is in the complement of their union\.
  Like the previous proof, this one involves a direct, step-by-step
  calculation.
  \begin{tabbing}
    XXX\=XXX\=XXX\=XXX\=XXXXXXXXXXXXXXXXXXXXX\=    \kill
    Prove: $x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A \cup  B}$ \\
    1. Assume $x \in \bar{A} \cap \bar{B}$ \\
    2. $x \in \bar{A}$, $x \in \bar{B}$ 
    \> \> \> \> \> Definition of intersection \\
    3. $x \notin A$, $x \notin B$ 
    \> \> \> \> \> Definition of complement \\
    4. $x \notin A \cup B$ 
    \> \> \> \>  \> Definition of union \\
    5. $x \in \overline{A \cup  B}$  
    \> \> \> \> \> Definition of complement \\
    6. QED ($x \in \bar{A} \cap \bar{B}  \Rightarrow x \in \bar{A \cup  B}$) 
    \> \> \> \> \> Implication 
  \end{tabbing}
\end{example}

\subsection{Proof by contradiction}

To prove that a proposition $P$ is true, it is enough to prove that 
$\neg P \Rightarrow \ms{false}$\. The pattern is: 
\begin{structproof}
  Prove:  $P$ \\
  1. $\neg P \Rightarrow \ms{false}$ \\
  2. QED   
  \> \> \> \> \> Contradiction
\end{structproof}

\noindent
Some variants of this:

\begin{structproof}
  Prove: $P$ \\
  1. $\neg P \Rightarrow (Q \wedge \neg Q)$ \\
  2. QED 
  \> \> \> \> \> Contradiction \\
  \\
  \\
  Prove: $P$ \\
  1. $\neg P \Rightarrow Q$ \\
  2. $\neg Q$ \\
  3. QED       
  \> \> \> \> \> Contradiction \\
\end{structproof}

\begin{example} Let's prove that the average of two numbers is always
  less than their maximum.
\begin{structproof}
Prove: $\frac{a+b}{2} \le \max(a,b)$\\
1. $\frac{a+b}{2} > \max(a,b) \implies \ms{false}$\\
\> 1. Assume $\frac{a+b}{2} > \max(a,b)$
     \> \> \> \> For $P \implies Q$, Assume $P$, prove $Q$ \\
\> 2. \ms{false}\\
\> \> 1. $\frac{a+b}{2} > a$
      \> \> \> Definition of max \\
\> \> 2. $\frac{a+b}{2} > b$
      \> \> \> Definition of max \\
\> \> 3. $\frac{a+b}{2}+\frac{a+b}{2} > a+b$
      \> \> \> Add previous inequalities \\
\> \> 4. $a+b > a+b$
      \> \> \> Simplify \\
\> \> 6. QED
      \> \> \> Actually $a+b=a+b$ \\
\> 3. QED
      \> \> \> \> Showed $P \implies \ms{false}$ \\
2. QED  \> \> \> \> \> Contradiction \\
\end{structproof}
\end{example}

\comment{
\begin{example}
  \mbox{}
  \begin{structproof}
    Assume: If Richard gets at least four hours of sleep then he passes his 
    6042 final. \\
    Richard fails his 6042 final. \\
    Prove: Richard gets less than four hours of sleep.
  \end{structproof}

  \noindent
  Here, let $P= \mbox{``Richard gets less than four hours sleep.''}$\.
  $Q= \mbox{``Richard passes.''}$. So the proof steps for proving $P$ are:

  \begin{structproof}
    Prove: Richard gets less than four hours of sleep. \\
    1. If Richard gets at least four hours of sleep then he passes. 
    ($\neg P \Rightarrow Q$). \\
    \> \> \> \> \> Assumed \\
    2. Richard fails ($\neg Q$). 
    \> \> \> \> \> Assumed \\
    3. QED (Richard gets less than four hours of sleep.) 
    \> \> \> \> \> Contradiction 
  \end{structproof}
\end{example}
}

\begin{example}
  A more interesting proof by contradiction\.
  \begin{structproof}
    Prove: $\sqrt{2}$ is irrational.\\
    1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
    2. QED 
    \> \> \> \> \> Contradiction. 
  \end{structproof}
  Assume it's rational, play with the definitions, and try to get a
  contradiction. 

  \begin{proofoverhead}
    Prove: $\sqrt{2}$ is irrational. \\
    1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
    \> 1. Assume $\sqrt{2}$ rational. \\
    \> 2. $\ms{false}$ \\
    \> \> 1. Choose $a, b \in N^{+}$, $\sqrt{2} = \frac{a}{b}$, lowest terms.
    \> \> \> Basic property of rationals. \\
    \> \> 2. $2 b^2 = a^2$       
    \> \> \> Algebra \\
    \> \> 3. $a^2$ is even.
    \> \> \> Definition of ``even'' \\
    \> \> 4. $a$ is even. \\   
    \> \> 5. Choose $c \in N$, $a = 2c$. \\
    \> \> 6. $4 c^2 = a^2 = 2b^2$ 
    \> \> \> Algebra \\
    \> \> 7. $2 c^2 = b^2$       
    \> \> \> Algebra \\
    \> \> 8. $b^2$ is even.
    \> \> \> Definition of ``even'' \\
    \> \> 9. $b$ is even. \\
    \> \> 10. $a$ and $b$ aren't in lowest terms. 
    \> \> \> 1.2.4, 1.2.9 \\
    \> \> 11. QED ($\ms{false}$) 
    \> \> \> 1.2.1, 1.2.10, propositional logic \\
    \> 3.  QED ($\sqrt{2}$ rational $\Rightarrow \ms{false}$) 
    \> \> \> \> Implication \\
    2. QED  ($\sqrt{2}$ is irrational) 
    \> \> \> \> \> Contradiction
  \end{proofoverhead}

  Some steps aren't justified here: 
  \begin{itemize}
  \item
    Showing that $a$ and $b$ are even, because we know their squares
    are even.
  \item
    Some other points involving quantifier logic.
  \end{itemize}
  We may revisit this later to fill in the gaps.
\end{example}

\subsection{Proof by cases}

To prove that a proposition $P$ is true, it is enough to prove that
$Q$ and $\neg Q$ both imply $P$, where $Q$ is any other proposition\.
This shows $P$ is true in either case, so it's always true.

\begin{structproof}
  Prove: $P$ \\
  1. $Q \Rightarrow P$ \\
  2. $\neg Q \Rightarrow P$ \\
  3. QED                     
  \> \> \> \> \> Cases 
\end{structproof}

\noindent This generalizes to any number of
predicates, provided that together they cover all possibilities\.  If
$Q_1 \vee Q_2 \vee \ldots \vee Q_k$ is always true, and you can show
each $Q_i$ implies $P$, then you can infer $P$.
\begin{example}
  \mbox{}
  \begin{structproof}
    Assume: $d =$ your birth date (day of month, 1-31). \\
    Prove: $d^2 + d$ is even. \\
    1. $d = 1 \Rightarrow d^2 + d = 2 \mbox{ is even}$. \\
    2. $d = 2 \Rightarrow d^2 + d = 6 \mbox{ is even}$. \\
    3. $\ldots$ \\
    31. $d = 31 \Rightarrow d^2 + d=992 \mbox{ is even}$. \\
    32. QED ($d^2 + d$ is even.)
    \> \> \> \> \> Cases 
  \end{structproof}
  More clever proofs than this one might consider fewer cases\.
  For example, can we just consider whether $d$ is even or odd?
\end{example}

\begin{example}
  This example combines an argument by contradiction and an
  argument by cases\.
  \begin{structproof}
    Prove:  There are infinitely many prime numbers. \\
    1. Assume there are only finitely many prime numbers. \\
    2. $\ms{false}$ \\
    \> 1. Choose $P$ to be the finite set of all prime numbers, and define 
    $m$ to be $1 + \Pi_{p \in P} p$. \\
    \> 2. $m$ isn't in $P$. 
    \> \> \> \> It's larger than all the elements of $P$. \\
    \> 3. $m$ isn't divisible by anything in $P$. 
    \> \> \> \> Remainder is $1$ for any such division. \\
    \> 4. There is some prime that isn't in $P$. \\
    \> \> 1. If $m$ is prime then there is some prime that isn't in $P$. \\
    \> \> \> \> \> $m$ is an example. \\
    \> \> 2. If $m$ is not prime then there is some prime that isn't in $P$. \\
    \> \> \> 1. Assume $m$ is not prime. \\
    \> \> \> 2. $m$ has a prime divisor. 
    \> \> Number theory fact \\
    \> \> \> 3. Choose $q$ to be a prime divisor of $m$. \\
    \> \> \> 4. $q$ isn't in $P$ 
    \> \> $m$ is divisible by $q$, but not by any $p \in P$. \\
    \> \> \> 5. There is some prime that isn't in $P$. \\
    \> \> \> 6. QED 
    \> \> Implication \\
    \> \> 3. QED (There is some prime that isn't in $P$.) \\
    \> \> \> \> \> Cases \\
    \> 3. QED ($\ms{false}$) \\
    3. QED (Infinitely many primes)
    \> \> \> \> \> Contradiction
  \end{structproof}
  We may prove the missing number theory fact later in the course\.
  Again, some arguments about quantifiers are made informally, so we may
  want to return to these after we study quantifier logic.
\end{example}

\section{Good proofs}

Some features of good proofs:
\begin{itemize}
\item
  They must be {\em correct\/}.
\item
  They should be clear and understandable.
\item
  They should have nice structure: 
  They should be broken up into pieces that
  prove key intermediate properties (lemmas)\.
  (This makes them easier to understand, and possibly reusable.) 
\item
  They should be written fairly generally and abstractly, so they apply to
  many cases. 
\item
  Don't leave gaps, saying something is obvious when it isn't.
\item
  Elegant, economical,...
\end{itemize}
Notice that many of these are also features that we look for in 
good programs.
\end{document}

Names to use:
Sonia, BB, Stacy, Ramona,
Joel, Gretchen, Dirk, Greg,
Jenna, Gervase, Colleen, Sean,
Susan, Rudy, Kelly, Richard


Proof handouts?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Coverage:

Tell them what proofs are (propositions, axioms, deduction rules...).
Point them to the basic data types (Booleans, numbers, sets, functions)
Propositional logic, truth tables.
Examples:  Direct, contradiction, cases.

Classification:

Basic discrete math concepts:
Booleans, numbers, strings, sets, functions, 
Proofs:
Know what they are
Propositions, truth tables.
Propositional logic proofs:  direct, contradiction, cases.
Math foundations for programming
Analytic tools
Discrete probability

