What's in a Proof? - Week 5

This week has been mostly about the structure of proofs. It is a bit strange for me to think about proof structure without delving into the details of the proof itself. In order to figure out the structure, I believe there has to be some insight concerning where you should be starting from and where you are trying to go. In that case, there has to be intuition about what is required from you to construct the proof. Thus, although the focus of this week was supposed to be purely on the structural components, in reality, it was truly the real introduction on what it means to prove something. One of the first proofs we worked through was the following:

S: "n e À, ½P½> n

In this example, P is the set of all primes and ½P½ is the size of P.  When creating the structure of the proof, the choice of how you wish to approach the proof makes a difference. For example, the example provided below is one that uses contradiction:

Assume ØS: $n  e À, ½P½> n #negation of S

                Then there is a finite list, p1, pk of elements in P

Let q = p₁ x...x p_k   #q is the product of all primes

Then q > 1   #as q is at least 2 x 3 = 6

Then q + 1 > 2

Then $d  e P such that d divides q + 1  #every integer >2 has a prime divisor

Then d is one of p₁ to p_k  # these are all possible primes

Then d divides q

Then d divides q + 1 – q   #as d divides both q +1 and q (number theory)

Then d divides 1

Then d = 1   #only 1 divides 1

Then 1 e P   #this is the contradiction as 1 is not a prime number

Then S

This is just an example from the notes. But without knowing that the intention was to show a contradiction, it would be difficult to figure out what is required when it comes to setting some basic assumptions and values. In the end, there is more to a proof than what may meet the eye at first glance. So to answer the question: what’s in a proof? It is some great formatting and some even better thinking.