Subsection 3.6.5 Theorem upon Theorem (Again): Using Lemmas and Corollaries
Recall that back in our discussion of truth tables, we introduced the idea that, when confronted with a nontrivial problem, we could prove some intermediate results and then use those results (theorems) as though they were additional premises.
This same idea is important when we’re building natural deduction proofs of interesting claims. In fact, there are two notions of “related theorems” that we’ll find useful. They are typically given names:
A lemma is a theorem that we prove along the way toward a proof of a bigger claim. Once we’ve proved a lemma, we can, of course use it in other proofs as well.
A corollary is a theorem that’s a not too distant spinoff of a theorem we’ve just proved. Typically the proof of a corollary is fairly straightforward. But the corollary may put the claim of the theorem in a more useful form.
Exercises Exercises
Exercise Group.
1.
1. Suppose that we have the following premises:
[1] a → p
[2] w → r
[3] s → x
[4] s → w
[5] ( x ∧ w ) → a
[6] ( x ∧ w ) → b
[7] ( x ∧ w ) → c
Further suppose that a , b , and c are all important conclusions that we’d very much like to be able to prove. Which one of the following possible lemmas would it make sense to try to prove:
a
r
s
x
w
2.
Suppose that we have the following premises:
[1] ¬e
[2] p → ¬ q
[3] p → v
[4] q → s
[5] q → b
[6] ¬ r ∨ w
[7] r → c
[8] s → ( a ∨ e )
[9] s → d
[10] s → r
Further suppose that a , b , c , and d are all important conclusions that we’d very much like to be able to prove. Which one of the following possible lemmas would it make sense to try to prove:
p
q
r
s
w