Week the Fifth (in Hindsight)

Aaaaand it's all about proofs! Though it was cut short by that test I mentioned (which went decently, I thought, in case you were hanging off the edge of your seat in anticipation.) Still, 2 lecture's worth of material is enough to lay a decent introduction to the methodology of proofs (...that's not to say, however, that I'll have much to write about this week. I've a feeling that this post, like the week's lectures, will be cut rather short.)

Onwards! As mentioned last time, Danny's rather obsessively preached the importance of structure in the proofs. (I think that part of the lecture has by far overlapped all others at this point.) But in between the indentations, he's also mentioned a few examples of actual proofs, and showed us how to go about tackling them.

Memorably, sometimes proving things in one direction is easier than in the other (for instance, proving that for any real number n, n being odd implies n^2 is odd is much easier than proving that n^2 being odd implies n is odd.) In cases like these, it is therefore useful to think of a way to invert the problem. Lo and behold, the contrapositive exists! (So use it. QED.)

Also memorably, in trying to prove things like "there exist an infinite number of primes," you can use proof by contradiction (assume the opposite is true - there is a finite number of primes - and try to disprove that.) So, it goes something like this:

Counter: there exists a natural number n such that n is larger or equal to the largest positive prime number.
           assuming that the universe's primes are all in the finite set P = {p1, p2.........pk},
           you can deduce that there is a number m that is the product of all these prime numbers
               (m = p1*p2*...*pk), and is a natural number since all primes are natural and this set is  
               closed under multiplication.
           then m is some number that is ultimately greater than 1 (since p's are greater than 1)
           then m + 1 is greater than 1 (because of above)
           then there exists a prime number p that exactly divides (m + 1) (since every natural number
               greater than 1 has a prime factor - if prime, itself, or if not, its composites)
          and p must also exactly divide m, since m is the product of all prime numbers
          then p must exactly divide ((m + 1) - m), or 1
          which implies p = 1
          but under the definition of prime numbers (one which has only 2 natural numbers that divide
               it), 1 is NOT prime, so that's a CONTRADICTION
and therefore the original claim must be true. (Yay!)
...which is probably a better proof of this problem than the following:

In case you're ever stuck on a problem, here's some useful advice from Danny: "I look up and to the left quite often, because that's where answers seem to come from." (it does explain all those thousand-yard stares during exams.)