Proofs

Proofs have been an integral part of mathematics since the Ancient Greeks. They can be thought of as a logical arguments for proving a mathematical statement based on assumptions and known relationships. A good proof should be elegant, easy to follow and should stand up to testing. This can be very intimidating for beginners (which is what we are in CSC165). But, if you know how to structure a proof, then there's always a place to start and a good structure can facilitate ideas and insight. Since I am a visual thinker, I going to compare the structure of a proof to matryoshka dolls (cheesy, I know).

Another name for matryoshka dolls is Russian nesting dolls because each smaller doll is contained in a bigger doll. The smallest doll is proof essence of the proof, the part that requires insight and can be tricky. The outer dolls contain that insight and apply it to domains where the relationship is true. I've illustrated a proof structure from last week's tutorial to show what I mean.

If you are comfortable creating the structure of a proof, then you can spend more energy on the little doll. More on how to go about proving the mathematical relationship contained by the small doll in my next post.

Paper Folding Problem

Firstly, apologies to my TA if every post he reads this week is about Friday's problem solving class, but it was the most exciting part of the course this week.

I won't go explain the problem, although it was a new one for me and interesting to solve. (Our group managed to come up with two solutions, so we were pretty chuffed with ourselves.) I want to mention what the exercise taught me instead. Danny gave us a series of steps to follow when solving a problem:

1. Understand the problem. Essentially, decide what the input is and what output should be generated.
2. Devise a plan. Or two or three if you can think of several ways of approaching the problem.
3. Carry out the plan. Having more than one plan can be beneficial for when you get stuck with one approach.
4. Look back. Have you followed the plan? Where has it got you? Have you discovered something helpful?
5. Acknowledge when, and how, you are stuck. This is the hardest step for me, because it's not always easy to know why you're stuck. It's important to solve this before moving on.

*Update (19 Oct 2014): I read in a fellow student's blog that these steps were devised by Polya.*

In general, I think I have intuitively followed these steps when problem-solving, but knowing the steps formalises the process. Recording what you're doing and plan to do helps with communication among team members and with your future self if you need a break from the problem. We found that our original plan lead to other ideas, and eventually, each of us was working on a separate approach but still keeping the others informed of any breakthroughs.

There was surprisingly little frustration (maybe because the problem wasn't too difficult) because we kept making steady progress. I'm going to be applying these steps to my other classes and to life when I am stuck.

Implications

This week in CSC165 we talked a lot about implications, which can be tricky to wrap your head around.  I try to review the lecture slides after class and test whether I can explain the concepts and/or answer the questions. If not, I look up the topic in the course notes and check the discussion board. It doesn't help that sometimes common language doesn't reflect logic. Consider the idiom:

When it rains, it pours.

The antecedent (P) is "it rains". The consequence (Q) is "it pours". P -> Q. Rain implies pouring but pouring does not imply rain (even though experience tells us it should). The only way to prove this implication false is to find an example of a time when it rained (P is true), but did not pour (Q is false). Therefore, drizzly, gray days are the counter-example that make "when it rain, it pours" false. Perhaps a more logical idiom would be:

When it pours, it rains.

Do you agree or disagree with my logic? Can you think of other idioms that are implications?

The thing I find most tricky about implications is deciding if one statement implies the other, or vice versa. We've gone through some sentences in class as examples and it was only once I heard the answer that it seemed obvious. Before hearing the answer, I could reason either. So I need to get more practice and get comfortable with implications, because they are going to be showing up A LOT.