Week 6 – Methods for Proofs

I gather there are about 6-7 different methods for proofs that we’ve learned so far.  Here is a list of what I’ve got going:

1)    Direct proofs w/ transitivity – This appears to be the most common where one conclusion leads to another until you eventually arrive at the statement you were trying to prove.

2)    Equivalent proof w/ contra-positive – Initially, I felt this method overcomplicated the proof but I am starting to understand where it becomes useful. My only concern is spending the time to work out the contra-positive on an exam only to find that the original statement was just as easy to prove. I guess we need to practice and develop some intuition when it comes to using this method.

3)    Proof of Existence – Most of the time I see this used with sequences or some other set of concrete numbers.

4)    Proof By Contradiction – This method is the most interesting so far. The approach is to prove a statement by disproving its negation, i.e. we must find some elementary result that is falsified when the statement is negated. What's interesting is that we're able to prove one giant universally quantified statement by finding just one miniscule falsity in its negation. That to me is very powerful. The power behind proof by contradiction is perfectly demonstrated in Euclid’s proof of infinite prime numbers which we touched on in class (more discussion below).

5)    Non-Boolean Proofs – Further study is required here. I’m not sure where the “non-boolean” part comes into play. From what I can see the statements still evaluate to True or False.

6)    Proving the Falsity of Statements – Seems just like method 1 (direct proof with transitivity) except we are instead proving the negation. I guess the trick is figuring out whether to prove the negation or show a contradiction in the original statement. More practice and intuition.

7)    Proof by Cases – Walk down all paths and show the statement is true in each.  Sounds exhausting, I mean exhaustive. So far only used on even or odd cases so, not too bad.

I also wanted to talk a little about Euclid’s proof of infinite primes.  We only got halfway through this in class and, like many other students; I left questioning whether the proof made sense.

It kind of went like this:

·      We used proof by contradiction by assuming there are a finite number of primes all contained in some set P.

·      We then showed that the product of all elements of P plus 1 is either a prime (a contradiction to the set P) or it is not a prime and is thus divisible by some element of P (another contradiction, since no element of P can divide the new number without a remainder of 1).

So that is all well and good.  But then the professor says, “By the way, not all sequential products of primes plus one will lead to another prime. And that’s the end of class. Have a great day.” (To his credit, he did, later on, promise us a full proof of infinite primes).

What?!  That makes no sense!?

It turns out this is a common misconception with this proof. We aren’t saying that some product of n primes plus one is also a prime. What we are saying is if the new number is not a prime then there must be some larger prime outside of the n primes that can divide it. Otherwise, that new number is a prime.  In either case, (yup proof by cases and by contradiction) there is always another prime number outside of the group of n primes.  Thus infinite number of primes. Now if only they could put this on an assignment….