Proofs Don't Bite!

Dear Students,

  Some people blank out completely when they have to prove something.
It is indeed a leap of abstraction, and if you CAN do it, it means
that you should be very proud of yourself.

Do not memorize proofs by rote! It is very easy for the professor to see
if you faked it! What seems to you an almost exact rendition, to the
professor makes clear that you have no clue on what you are talking about it.

You should first understand it! Of course, you should then memorize your understanding,
but memorizing an understood proof is a piece of cake.

Here is a trick that I can show you how to internalize theorems AND proofs,
that is taken from programming. It is called "tracing a program".
In order to understand a computer program,
you should take some simple input, and run it through the program, 
pretending that you are the computer.

Sample tracing of a theorem and of its proof.

Theorem: Prove that the Null Space of an m by n matrix A is a subspace of R^n.

Proof: By definition, the null space of a matrix A is the SET, let's call in V

V={x in R^n : Ax=ZeroVector}

We have to check the three properties

(i) ZeroVector belongs to V

(ii) if v belongs to V and k is a number then kv belongs to V

(iii) if v1 and v2 belong to V then v1+v2 belongs to V

Proof of property (i): A(ZeroVector)=ZeroVector is true!

Proof of property (ii)if v is in V then  by DEFINITION of V

A(v)=ZeroVector

We have to prove: A(kv)=ZeroVector

Now

A(kv)=kAv  (since it is OK to commute a matrix and a number)

but we know that Av=ZeroVector,

so

A(kv)=k ZeroVector=ZeroVector.

Proof of property (iii): if v1 and v2 belong to V then we know

Av1=ZeroVector

Av2=ZeroVector

Adding these two equations we get

Av1+Av2=ZeroVector

By the associative property, the left side is

A(v1+v2)=ZeroVector

But by definition of V this means v1+v2 belongs to V. QED.
--------------------------

Now this is very abstract! In order to digest it, take a SIMPLE example.
a 1 by 2 matrix (1 by 1 matrix is too simple to see what is going on)

   
A=[ 1, 2]

First let's understand the THEOREM! The set V is

     x1
V={ [  ] in R^2: x1+2x2=0}
     x2


Using high-school algebra, we get x1=-2x2, and x2 is free, so a typical member of V is
 
 -2x2      -2
[   ]= x2 [  ]
  x2        1

                                     -2
So V is the set of all multiples of [  ] (a.k.a. the span of that vector) and for this you can see directly that
                                      1

the theorems is true.
      0
(i)  [ ]  belongs to it 
      0

(ii) if you multiply a constant multiple of the vector ([-2, 1]^T) by another constant, it is still a constant multiple of [-2,1]^T .

(iii) if you add two constant multiples of the vector ([-2,1]^T) together you get yet-another-constant multiple.

---End of spelling-out a special case of the THEOREM--------

----Begin Spelling Out a special case of the PROOF------------

Now, in order to understand what in the world the abstract proof is saying, let's spell it out!

    0
(i)[ ] belongs to V since 0+2*0=0
    0 

         x1
(ii) if [  ] belongs to V this means that x1+2x2=0
         x2
                       kx1
We have to check that [   ] belongs to V, but
                       kx2


  (kx1)+2(kx2)=k(x1+2x2)=0

obviously true!

           x1
(iii) If  [  ] is in V , this means by the (concrete) definition of V that x1+2x2=0
           x2

           y1
      If  [  ] is in V this means by the (concrete) definition of V that  y1+2y2=0
           y2

we have to prove

      x1+y1
     [     ] is in V
      x2+y2

this means by the (concrete) definition of V that  we have to prove 
that the above two relations imply:

(x1+y1)+2(x2+y2)=0

Using the rules of high-school algebra, the left side is:

(x1+2x2)+(y1+2y2)=0+0=0 .

QED.


This applies in general. If you want to UNDERSTAND (not just rote memorize) what a theorem and/or a proof
MEAN, spell-it out with a simple example, and work it out in detail.

Once you understand the concrete example, you can make the CONCEPTUAL LEAP of understanding
an ABSTRACT theorem and its proof!


Rememeber, Computers can compute much better than all of us. We humans should try to UNDERSTAND
concepts and proofs so that we can be good guides to computers, and so that we UNDERSTAND
the right input and output.

    Best wishes

              Dr. Z.