Subsection 8.6.2 Use of Lemmas
A common way to exploit the divide and conquer idea when we’re trying to write proofs is to exploit lemmas. We prove smaller, intermediate results and then use them as though they were additional premises. The benefit of this approach is that it may help to avoid the combinatorial explosion that can occur when we’re working with too many premises at once.
Recall that we did exactly this in one of our extensions to the Who Drives Me example.
We used these propositional variable names for the basic statements:
J: John must drive me to the store.
M: Mary must drive me to the store.
L: John will be late for work.
G: Mary must buy gas.
D: Mary must have money.
We assumed these premises:
[1] J M John or Mary must drive me to the store.
[2] J L If John drives me to the store, he will be late for work.
[3] L John cannot be late for work.
[4] M G If Mary must drive me to the store, she must buy gas.
[5] G D If Mary must buy gas, she must have money.
We wanted to prove:
[6] D Mary must have money.
We could have started from scratch to prove that the premises imply the conclusion. In other words, we could have proven:
[7] ((J M) (J L) (L) (M G) (G D)) D
But then we noticed that we’d already proven:
[8] M Mary must drive me to the store.
We can use [8] as a lemma. If we do that, we can ignore premises [1] – [3]. We can simply prove:
[9] (M (M G) (G D)) D
Simpler.
Throughout this course we’ve been using lemmas in a big way. We’ve been assuming all the standard facts about arithmetic and algebra.
We’ve also used as mathematical lemmas claims that we have proved in other places.
For example, recall that in our proof that √2 is irrational, we exploited the following claim that we proved elsewhere:
For all integers n, if n2 is even, then n is also even.
Exercises Exercises
1.
Prove that if a quadratic equation with real coefficients has exactly one root then that root must be real. (Hint: Use the quadratic formula as lemma.)
x= (-b±√(b^2-4ac))/2a
We assume that the two roots are equal. So what can we then say about them?
When you’ve finished your proof, click here to see ours: When clicked, should see:
Assume a quadratic equation written as: ax2 + bx + c. Then the quadratic formula tells us what the two roots are:
x= (-b±√(b^2-4ac))/2a
In order for the two roots given by this equation to be equal, it must be the case that:
(-b+√(b^2-4ac))/2a = (-b-√(b^2-4ac))/2a
The only way for that to be true is for √(b^2-4ac) to be 0. In that case, there is a single root:
(-b)/2a
If b is real, so is –b. If a is real, so is 2a. Since we began with a quadratic equation, a is not 0. So the quotient is defined and is also real.