Math Week 4: Proof Strategies

This week in math we talked about some basic proof strategies, all based around proving implications.

Direct Proof

This one is the most straight forward. If you are trying to prove that P -> Q, you can use a direct proof by assuming P and deriving Q. Here’s an example:


We will use a direct proof to prove that if x is odd, x + 3 is even. Assume x is odd. This means that x = 2*k + 1, for some integer k. Therefore, x + 3 = 2*k + 1 + 3 = 2*k + 4 = 2 * (k + 2). Since k + 2 is an integer, we know that 2 * (k + 2) must be an even integer. Therefore, if x is odd, x + 3 is even. Q.E.D. —-

Hooray! That wasn’t too complicated.

Trivial Proof

Another method is to simply ignore P and prove that Q is always true, so P -> Q is true whether or not P is true. This is a trivial proof. Here’s an example:


We will use a trivial proof to prove that if it is Sunday, x^2 + 4x + 5 != 0. Since x^2 + 4x + 5 = x^2 + 4x + 4 + 1 = (x + 2)^2 + 1, and (x + 2)^2 is greater than or equal to zero, (x + 2)^2 + 1 >= 0 + 1 > 0. So x^2 + 4x + 5 != 0. Q.E.D. —-

Vacuous Proof

Instead of ignoring P, you can also choose to ignore Q. Remember that P -> Q is true when P is false - regardless of Q. So if we can prove that P is false, we have proven P -> Q. Example time:


We will use a vacuous proof to prove that when |sin(x)| < -(x^2), I am wearing blue socks. Since |sin(x)| >= 0, and -(x^2) Q, we can prove thatnot Q -> not Pinstead. Those two statements are logically equivalent, because(not (P -> Q)) = (P and not Q) = (not Q and not (not P)) = (not Q and P) = (not (not Q -> not P)). So this is like a direct proof - assumenot Q, and provenot P`. Here’s an example:


We will use a Contrapositive proof to prove that if x > 3, then x^2 – 4x + 4 != 0. Assume that x^2 – 4x + 4 = 0: x^2 – 4x + 4 = (x – 2)^2 = 0. Take the square root of both sides, showing that x – 2 = 0, so x = 2. 2 is not greater than 3, so if x^2 – 4x + 4 = 0, x is not greater than 3. Q.E.D. —-

That’s all for this week - I expect more proof techniques next week, but we’ll see what happens.