Subsection 8.3.3 Proof by Contradiction
Suppose that we want to prove some claim P. To use a proof by contradiction, we assume the negation of P and show that, by doing so, we derive a contradiction.
In more detail: As usual, we assume that we are given some set of premises p1 through pn. Then (to simplify the rest of this discussion) let:
C = p1 ∧ p2 ∧… ∧ pn
We want to prove that, from C, we can derive P.
Here is the structure of a proof by contradiction of P:
[1] C Premises
[2] ¬P (Conditional) Premise (Assuming the negation of our claim)
… (Reasoning, using C and ¬P, as appropriate)
[k] ¬C (Using some rule that derives this final step)
[k+1] ¬P → ¬C Conditional Discharge [2], [k]
[k+2] C → P Contrapositive [k+1]
[k+3] P Modus Ponens [1], [k+2]
Note that the key to this proof is step [k]. We’ve shown that, given ¬P, at least one of our premises would have to be false. But we have asserted that they are all true.
So, in the last three steps of the proof, we show that, since the negation of P leads to a contradiction, P itself must be true.