Introducing Indirect Proof

1 Comment
Last updated: Monday, May 20, 2024

Indirect proof is a method for proving something by showing that the assumption of its negation would lead to a contradiction. Its Latin name is reductio ad absurdum, which means a reduction to the absurd. The general idea is that if you can demonstrate that a claim has absurd consequences, it cannot be true, and that serves as a demonstration of the opposite claim.

At the end of the last lesson, I noted that we had three rules of replacement left to prove. These were Double Negation, Material Implication, and De Morgan's. One of these could be proven with what we have already learned, the rules of replacement, the rules of inference, and conditional proof. Watch the video or scroll past it for the answer.


Click here for answer
Double Negation
Prove: P ≡ ~~P
1. | P // Assumption
2. || ~P // Assumption
3. || ~P & P // 1,2 Conjunction
4. | ~P ⊃ (~P & P) // 2-3 Conditional Proof
5. || ~P // Assumption
6. | ~P ⊃ ~P // 5 Conditional Proof
7. | ~~P ∨ ~P // 6 Material Implication
8. | ~(~P & P) // 7 De Morgan's
9. | ~~P // 4,8 Modus Tollens
10. P ⊃ ~~P // 1-9 Conditional Proof
11. | ~~P // Assumption
12. || P // Assumption
13. | P ⊃ P // 12 Conditional Proof
14. | ~P ∨ P // 13 Material Implication
15. | P // 11,14 Disjunctive Syllogism
16. ~~P ⊃ P // 11-15 Conditional Proof
17. P ≡ ~~P // 10,15 Biconditional Intro.

Here's the important thing to take from this. In the first part of this proof, I used conditional proof to get a conditional whose consequent was a contradiction. I then use conditional proof again to get ~P ⊃ ~P, which I transformed into the negation of the conditional's contradictory consequent. This transformation used Material Implication and De Morgan's. Therefore, I could not use the same method in proofs for these two rules. But apart this that, this shows that you can prove something by showing that the assumption of its negation leads to a contradiction. Just construct a conditional proof with its negation as an antecedent and a contradiction as its consequent. You can then prove the negation of its contradictory consequent and use Modus Tollens to get the negation of your assumption.

Since a contradiction is never true, this method can be shortened into a new method called Indirect Proof. To do an Indirect Proof, start out by assuming the opposite of what you want to prove, derive a contradiction, then conclude that the opposite of your assumption is true. This may be the negation of your assumption, or if your assumption was already a negation, it may be what your assumption was a negation of.

Let's now take a look at a simple indirect proof. I previously assigned this one in Introducing Conditional Proof. It could be solved without Indirect Proof, but it can be solved in fewer lines with it.

1. P ⊃ Q // Premise
2. R ⊃ ~Q // Premise
Prove: ~(P & R)
[spoiler title=”Click for solution”]3. | P & R // Assumption
4. | P // 3 Simplification
5. | Q // 1,4 Modus Ponens
6. | R // 3 Simplification
7. | ~Q // 2,6 Modus Ponens
8. | Q & ~Q // 5,7 Conjunction
9. ~(P & R) // 3-8 Indirect Proof[/spoiler]

Let's now do a proof of the same rule we proved above, but this time with Indirect Proof.

Click here for proof using Indirect Proof
Double Negation
Prove: P ≡ ~~P

1. | P // Assumption
2. || ~P // Assumption
3. || P & ~P // 1,2 Conjunction
4. | ~~P // 2-3 Indirect Proof
5. P ⊃ ~~P // 1-4 Conditional Proof
6. | ~~P // Assumption
7. || ~P // Assumption
8. || ~P & ~~P // 6,7 Conjunction
9. | P // 7-8 Indirect Proof
10. ~~P ⊃ P // 6-9 Conditional Proof
11. P ≡ ~~P // 5,10 Biconditional Intro.

Note here that each Indirect Proof started with the same assumption, ~P, but each one had a different conclusion. One was used to conclude ~~P, which is the negation of ~P, and one was used to conclude P, which is what ~P is a negation of. In each case, the conclusion is the opposite of the original assumption. An Indirect Proof will work either way.

Now let's do a proof of Material Implication. One side of this is a disjunction, but we will not be able to derive it in the same way we have previously learned to prove a disjunction with conditional proof, because that method uses Material Implication, which is what we are trying to prove here. Instead, we will have to use Indirect Proof.

Material Implication
Prove: (~P ∨ Q) ≡ (P ⊃ Q)

Click here for solution to proof

1. | ~P ∨ Q // Assumption
2. || P // Assumption
3. || ~~P // 2. Double Negation
4. || Q // 1,3 Disjunctive Syllogism
5. | P ⊃ Q // 2-4 Conditional Proof
6. (~P ∨ Q) ⊃ (P ⊃ Q) // 1-5 Conditional Proof
7. | P ⊃ Q // Assumption
8. || ~(~P ∨ Q) // Assumption
9. || ~~P & ~Q // 8 De Morgan's
10. || ~~P // 9 Simplification
11. || P // 10 Double Negation
12. || Q // 7,11 Modus Ponens
13. || ~Q // 9 Simplification
14. || Q & ~Q // 12,13 Conjunction
15. | ~P ∨ Q // 8-14 Indirect Proof
16. (P ⊃ Q) ⊃ (~P ∨ Q) // 7-15 Conditional Proof
17. (~P ∨ Q) ≡ (P ⊃ Q) // 6,16 Biconditional Introduction


Click here for alternate solution to proof

1. | ~P ∨ Q // Assumption
2. || P // Assumption
3. || ~~P // 2. Double Negation
4. || Q // 1,3 Disjunctive Syllogism
5. | P ⊃ Q // 2-4 Conditional Proof
6. (~P ∨ Q) ⊃ (P ⊃ Q) // 1-5 Conditional Proof
7. | P ⊃ Q // Assumption
8. || ~(~P ∨ Q) // Assumption
9. || ~~P & ~Q // 8 De Morgan's
10. || ~~P // 9 Simplification
11. || ~Q // 9 Simplification
12. || ~P // 7,11 Modus Tollens
13. || ~P & ~~P // 10,12 Conjunction
14. | ~P ∨ Q // 8-13 Indirect Proof
15. (P ⊃ Q) ⊃ (~P ∨ Q) // 7-14 Conditional Proof
16. (~P ∨ Q) ≡ (P ⊃ Q) // 6,15 Biconditional Introduction
[raw]

For the next lesson, we will go over how to prove De Morgan’s with Indirect Proof. Try it on your own in the meantime.


Prove De Morgan's Theorem:
~(P & Q) ≡ (~P ∨ ~Q)
~(P ∨ Q) ≡ (~P & ~Q)

One Comment

Leave a Reply

Your email address will not be published. Required fields are marked *