This lecture introduces a new type of proof strategy that is useful to logicians, mathematicians, and game theorists.
Takeaway Points
- Suppose you would like to prove P but cannot do it through the direct methods we have explored previously.
- To attempt a proof by contradiction, begin by assuming that ~P is true. Then continue the proof using the standard rules of inference and replacement. Your goal is to derive an explicit contradiction (like Q ^ ~Q). If you succeed, then you have successfully proven that P is true.
- This works because our rules are truth preserving. If something impossible is “true,” it cannot be because of our rules. The problem must be the assumption we made.
- When starting a proof by contradiction, indent all lines in it. Close the indentation when are finished. You may use any above lines that are not part of a closed proof. However, once a proof is closed, you may no longer use the lines within the closed proof. This is because you derived them with an assumption that is not a part of the normal proof.
- All indented proofs must be closed before completing the full proof.