How to do proofs

Arun Ram
Department of Mathematics
University of Wisconsin, Madison
Madison, WI 53706 USA

Last updates: 4 September 2007.

There is a certain ``formula" or method to doing proofs. Some of the guidelines are given below. The most important factor in learning to do proofs is practice, just as when one is learning a new language.

  1. There are very few words needed in the structure of a proof. Organized in rows by synonyms they are:
    2.  
    To show
    Assume, Let, Suppose, Define, If
    Since, Because, By
    Then, Thus, So
    There exists, There is
    Recall, We know, But
     
  2. The overall structure of a proof is a block structure like an outline. For example:
    3.  
    To show: If   A   then   B   and   C  .
    Assume:   A  .
    To show:
    (a)   B  .
    (b)   C  .
    (a) To show:   B  .
                   .
                   .
                   .
         Thus   B  .
    (b) To show:   C  .
                   .
                   .
                   .
         Thus   C  .
    So   B   and   C  .
    So, if   A   then   B   and   C  .
     
  3. Any proof or section of proof begins with one of the following:
     
    (a) To show: If   A   then   B  .
    (b) To show: There exists   C   such that   D  .
    (c) To show:   E  .
     
  4. Immediately following this, the next step is
     
    Case (a) Assume the ifs and `to show' the thens. The next lines usually are
    • Assume   A  .
    • To show:   B  .
     
    Case (b) To show an object exists you must find it. The next lines usually are
    • Define   xxx  .
    • To show:   xxx   satisfies   D  .
     
    Case (c) Rewrite the statement in   E   by using a definition. The next line is usually
    • To show   E'  .

A useful guideline is, ``Don't think too much." Following the ``method" usually produces a proof without thinking. Most of doing proofs is simply rewriting what has come just before in a different form by plugging in a definition.

 

There are some kinds of proofs which have a special structure.

 

Proofs by contradiction.

(*) Assume the opposite of what you want to show.
               .
               .
               .
End up showing the opposite of some assumption (not necessarily the (*) assumption).
Contradiction.
Thus Assumption (*) is wrong and what you want to show is true.

Counterexamples.

To show that a statement, ``If        then       '', is false you must give an example.

To show: There exists a        such that
(a) it satisfies the ifs of the statement that you are showing is false.
(b) it satisfies the opposite of some assertion in the thens of the statement that you are showing is false.

Proofs of uniqueness.

To show that an object is unique you must show that if there are two of them then they are really the same.

To show: A THING is unique.
Assume X1 and X2 are both THINGs.
To show: X1 = X2.

Proofs by induction.

A statement to be proved by induction must have the form

If   A   then   B   for all positive integers n.

The proof by induction should have the form

Proof by induction.
Base case:
To show: If   A   then   B  , for n = 1.
               .
               .
               .
Thus if   A   then   B  , for n = 1.
Induction step:
Assume If   A   then   B  , for n < N.
To show: If   A   then   B  .

This last to show line contains exactly the same statement except with n replaced by N and ``for all positive integers n" removed.