FA19:Lecture 4 Proof techniques
We finished our proof that proof techniques.and used this as a way to demonstrate several
Note: We did not finish the proof in lecture; I have finished it below, but it's also a good exercise to work through on your own.
A direct proof
On the other hand, if then must be in ; otherwise could not be in . Similarly, ; thus so as required.We have now shown that and , which completes the proof that .
This is a good (although perhaps slightly wordy) proof of the claim: each statement is clear, and follows from the previous statements using standard proof techniques.
Proving for all statements
The fact that arbitrary does not mean you get to pick ; on the contrary, your proof should work no matter what you choose. This means you can't use any property of other than that .is
Proving and statements
To prove "and ", you can separately prove and then prove .
Using and statements
If you have already proved (or assumed) and , you can conclude . You can also conclude .
Proving or statements
To prove "or ", you can either prove , or you can prove (your choice!)
Using or statements
If you know that "P or Q" is true for some statements P and Q, and you wish to show a third statement R, you can do so by separately considering the cases where P is true and where Q is true. If you are able to prove R in either case, then you know that R is necessarily true.
This technique is often referred to as case analysis.