Taming of the Proof - Week 8

While the topic of the course has switched to theory of computation, and more specifically algorithm analysis, I have been more focused on the regular math proofs we have been doing. This is largely due to the assignment that is due on Monday and the midterm that is on Tuesday. While it is surprising that my ability to solve proofs is getting better very quickly, I am noticing some common trends in where I am stuck with solving proofs. I seem to be able to find a conclusion and then show how I came to that conclusion but I struggle with identifying the entry point of where to start in that proof. This is especially true when trying to prove a statement with a format such as p Ù q. You cannot assume p and so where do you begin in your proof to prove p? There must be some base assumption of p that is legitimate to start with. My problem seems to be identifying what is the correct base assumption. I have had to rewrite numerous proofs as I realized I was starting with the consequent and deriving the antecedent.

One of the most useful (but perhaps obvious) lessons I have learned this week related to base assumptions is that proofs cannot start with a tautology. When trying to show that two different things are equal, I tried to show how you can start with p = p, which could be derived to show that p = q.  However, as the proof started with a tautology it is invalid. I had to go back and find an attribute of p that would later link it to q. In the end it was successful but it was not the most intuitive step to take.

Overall, while I am getting better at writing proofs, the ordering of steps and the entry point of a proof is still something I need to work on. Hopefully with some more practice, it will become more natural. 

Logic Looks Not with the Eyes, But with the Mind - Week 7

The last few weeks I have been writing about developing both intuition and structure for proofs.  As time is passing, I feel like I am making some progress but it continues to be a very trying experience at times. It can feel like there are moments when I am going through the motions of how to understand something rather than recognizing things that my brain already knows to be true. In this week’s tutorial, I encountered a problem of this sort. We were given the following:

Definition:  ëxû = max {z e Z, z  £  x}

And here is the question that we had to disprove:

"x, y e Â, (x ³ 1 Ù y ³ 1) Þ  ëx/yû =  ëëxû/ ëyû û

The first step I simply negated the statement.

$x, y e Â, (x ³ 1 Ù y ³ 1) Ù  ëx/yû ¹  ëëxû/ ëyû û

The universal became an existential and the implication transformed into a conjunction with the form P Ù ØQ.

Next, I established the basic layout of the proof I wanted to do:

Pick x = ___. Then x e Â

Pick y = ___. Then x e Â

Then x ³ 1 Ù y ³ 1

Then ëx/yû =   _____ #algebra

Then ëëxû/ ëyû û =  _____#algebra

Then ëx/yû ¹  ëëxû/ ëyû û

Conclude $x, y e Â, (x ³ 1 Ù y ³ 1) Ù  ëx/yû ¹  ëëxû/ ëyû û

Once I had established that layout, I became stuck choosing values. While I had set up the majority of the proof, I could not think through the problem logically as I was becoming caught up in the definition of what the floor of a number is rather than just trying to think of two concrete numbers. It took some thinking before I realized that if I chose two numbers that when divided created a whole number, it would provide the example I was looking for. I ended up choosing 8.4 and 2.8. Thus, the final proof was:

Pick x = _8.4_. Then x e Â

Pick y = _2.8_. Then x e Â

Then x ³ 1 Ù y ³ 1

Then ëx/yû =   _3_ #algebra

Then ëëxû/ ëyû û =  _4_#algebra

Then ëx/yû ¹  ëëxû/ ëyû û  #as 3 ¹ 4

Conclude $x, y e Â, (x ³ 1 Ù y ³ 1) Ù  ëx/yû ¹  ëëxû/ ëyû û

In the end, I am trying to get over the fact that I am actually writing proofs and instead treat each component like a small puzzle to solve. If I spend too much time getting caught up in the symbols, I forget that I may already know the answer. Going forward, I will try to think more with my mind rather than simply reading it only with my eyes.

Be Not Afraid Of Proofs: For Those Who Have Proofs Thrust Upon Them. - Week 6

This week we went over the epsilon-delta proof once again. While we have covered the material before, this time, it was more formal and the example was more complex. I also had an interesting conversation with the Professor after class talking about the difference approaching something from a rigorous perspective and approaching it from an intuitive perspective. Both elements are required to write the proof but both require practice. In my own experience, I know that I have trouble translating my conceptual understanding of what are epsilon and delta into mathematical notation.

Currently, this is my understanding of the overall approach to these kinds of proofs:

 You are up against a challenge of an opponent who is trying to “screw you over”. However, you have the advantage of being able to make your move after he/she has made theirs. In other words, if someone gives you an epsilon range you can always pick a delta that fits that range. You can do it for any range that you are given and the epsilon and delta have always been restricted to positive real numbers. This has been the foundation for any epsilon/delta proof that we have encountered.

The difficulties come with solving the specific problem that comes with solving epsilon/delta proofs.

For example, having the requirements that |x – 3| < d Þ |x² – 3²| < e, requires techniques such as factoring, telescoping and the use of the triangle inequality. Furthermore, it requires choosing a delta that makes your overall problem simpler when you have to do addition at the end. While in hindsight this problem seems straight-forward, I had difficulties at the beginning of how to move forward.

I am going to spend the next week, trying to develop further intuition of how to approach the problems, as well as review some basic mathematical rules and techniques that my brain has forgotten. Hopefully with these tools, the next time I encounter an epsilon/delta proof, I will be able to approach it without feeling overwhelmed. 

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.

To Thine Own Proof Be True - Week 4

This is the first week of proofs and thus it is the commencement of what I believe to be the scariest material I am going to learn at university. However, although I am extremely hesitant to start working on proofs, the one thing that has resonated the most with me this week is how we were taught to approach a proof. In order to do a proof, you must have an understanding about what is actually going on. It takes creativity and examples to sometimes gain this understanding. I am also realizing more and more that is also about allowing trial and error. While this is applicable to more complex proofs, the same method can be applied to simple proofs. Take this example:

P Þ (Q Þ (R Þ S))       Û        P Ù Q Ù  R Þ S

P Þ (Q Þ (ØR Ú S))   #implication

P Þ (ØQ Ú (ØR Ú S))  #implication 

ØP Ú(ØQ Ú (ØR Ú S))  #implication

(ØP Ú ØQ Ú ØR )Ú S   #associative

Ø(P Ù Q Ù R )Ú S   #DeMorgan’s Laws

P Ù Q Ù  R Þ S    #implication

Again, while the proof is simple, I still had to look at where I was starting from, figure out where I was going and understand the small steps that got me from one end to the other. I plan to use the same thought process in more complex proofs. While it may take more time, more creativity and a greater acceptance of the mistakes that I will surely make, I just have to remember: to be true to my proof, I have to start to trust in my logic.