Proof By Contradiction/Indirect Proof

This lecture introduces a new type of proof strategy that is useful to logicians, mathematicians, and game theorists.

Takeaway Points

  1. Suppose you would like to prove P but cannot do it through the direct methods we have explored previously.
  2. 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.
  3. 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.
  4. 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.
  5. All indented proofs must be closed before completing the full proof.

Back to Logic 101