In this video, we'll see two simple extensions of direct proof: proof by contradiction and proof by cases.
Recall that an if/then statement \(\forall x, p(x) \rightarrow q(x) \) is equivalent to its contrapositive \(\forall x, \neg q(x) \rightarrow \neg p(x)\). If we prove either one, we have proved the other. Sometimes the contrapositive of a claim is easier to prove than the original.
With some practice, you'll develop intuitions about when the contrapositive might be easier to prove. I usually compare p(x) to \(\neg q(x)\) and see which looks like a better starting point. For example, \(\neg q(x)\) might have an AND of two facts rather than an OR, or it might have separate facts about each variable where p(x) has a fact in which two variables are combined.
Consider this claim:
Claim: For any real number x, if \(x^2 - 2x - 15 \ge 0\), then \(x \ge 2\) or \(x \le -1\).
To write a proof by contradition, we tell the reader what we are doing, write out the contrapositive, and outline a direct proof of the contrapositive. So, for our claim, we have:
Proof: Let's prove the contrapositive of the claim. That is, we'll prove that for any real number x, if \(x < 2\) and \(x > -1\), then \(x^2 - 2x - 15 < 0\),So let x be a real number and suppose that \(x < 2\) and \(x > -1\)
....
So then \(x^2 - 2x - 15 < 0\), which is what we needed to show.
Always tell the reader when you're using an outline other than direct proof. In this class, write out the contrapositive explicitly because it forces you to take a moment to make sure you have constructed it correctly.
Since it's not obvious how to move forwards from the given information, let's work backwards on scratch paper:
Scratch paper: Try factoring \(x^2 - 2x - 15\). It's equal to \((x-5)(x+3)\). So we need to show that \((x-5)(x+3) < 0\). That means that one of the two factors must be negative and the other positive. The bigger one (x+3) must be positive. So we need to show that \(x-5 < 0 \) and \(x+3 > 0\).
Let's rewrite this into forwards order and put it into our draft proof:
Proof: Let's prove the contrapositive of the claim. That is, we'll prove that for any real number x, if \(x < 2\) and \(x > -1\), then \(x^2 - 2x - 15 < 0\),So let x be a real number and suppose that \(x < 2\) and \(x > -1\)
....
So \(x-5 < 0 \) and \(x+3 > 0\).
So \((x+3)(x-5) < 0\).
Multiplying out the lefthand side, gives us \(x^2 - 2x - 15 < 0\), which is what we needed to show.
Now we have a small algebra gap to fill in, and our final proof looks like this:
Proof: Let's prove the contrapositive of the claim. That is, we'll prove that for any real number x, if \(x < 2\) and \(x > -1\), then \(x^2 - 2x - 15 < 0\),So let x be a real number and suppose that \(x < 2\) and \(x > -1\)
Since \(x < 2\), \( x-5 < 2-5 = -3 < 0\).
Since \(x > -1\), \(x+3 > -1 + 3 = 2 > 0\).
So \(x-5 < 0 \) and \(x+3 > 0\).
So \((x+3)(x-5) < 0\).
Multiplying out the lefthand side, gives us \(x^2 - 2x - 15 < 0\), which is what we needed to show.
Notice that filling this final gap required losing information. We know that \(x-5\) is less than -3 but our conclusion only requires that it's less than 0. And similarly for the other factor. Weakening information like this is a valid mathematical step, but it's one that we would never consider if we hadn't worked backwards from the desired conclusion.
Proof by cases allows you to make forward progress when your known information is an OR of two (or more) possibiilties. Here's the outline when there two possibilities.
There are 2 cases:
Case 1: [when is case 1 true?] .... Fact X.
Case 2: [when is case 2 true?] .... Fact X.
In both cases, Fact X is true. ...
The two cases must cover all the possibilites, but they can overlap (i.e. cover some possibilities twice). All the cases end at the same conclusion. The proof then picks up again from that common conclusion.
Consider the following claim.
Claim: For any real number x, if \(|x-3| > 10\), then \(x^2 > 40\).
We first set up our standard direct proof outline:
Proof: Let x be a real number and suppose that \(|x-3| > 10\).
...
So \(x^2 > 40\).
The absolute value is hiding two possibilities, depending on the sign of x-3. So let's make this explicit using cases:
Proof: Let x be a real number and suppose that \(|x-3| > 10\).
There are two cases depending on the sign of x-3:
Case 1: \(x-3 \ge 0\). ....
Case 2: \(x-3 \le 0\). ....
...
So \(x^2 > 40\).
Now we fill in the argument for each case:
Proof: Let x be a real number and suppose that \(|x-3| > 10\).
There are two cases depending on the sign of x-3:
Case 1: \(x-3 \ge 0\). Then \(x-3 = |x-3| > 10\). So \(x > 13\). So \(x^2 > 169 > 40\).
Case 2: \(x-3 \le 0\). Then \(-(x-3) = |x-3| > 10\). So \(-x + 3 > 10\). So \(-x > 7\). So \(x^2 = (-x)^2 > 49 > 40\).
In both cases \(x^2 > 40\), which is what we needed to show.
In this case, the cases covered pretty much the whole proof. However, the cases can cover only a small section in the middle of a longer proof.