Behind the scenes of proof by contradiction

Ivar Sand · 2013-03-03 21:40:40

In short. We start with an example: A ⇒ B, B ⇒ C, C ⇒ D, where A is an assumed condition and D is a condition contradictory to A. According to proof by contradiction(a), we conclude ¬A. We demonstrate the truth of this conclusion by proving that A ⇒ B ∧ C ∧ D and then showing that this implication reduces to ¬A.

Background. When we construct proofs, we often use the technique of assuming something to be true while suspecting it is false and then proceeding to derive a contradiction(b) which allows us to conclude (and prove) that what we assumed to be true is instead false.

I often wondered what the logic behind this kind of reasoning was like. Maybe I learned it some long time ago, but I am not sure. As a matter of fact, I think I never learned it. Therefore, I thought it might be fun to do a bit of exploring in order to find out what the logic of proof by contradiction might look like, and this thread is the result.

Outline. Section A shows an example of the use of proof by contradiction, and section B reveals the logic behind the results in section A.

Proven statements are identified by numbers within parentheses.
The right part of the line containing a statement may contain a comment indicating how the statement was produced.

A. An example of the use of proof by contradiction.
I guess there are many ways a proof by contradiction(a) can go. I have chosen to demonstrate one of them.

First we assume A to be true. Note that this does not mean that we consider A to be a proven statement. We procede by deducing something from A:
A ⇒ B (1)
Then we deduce something from B:
B ⇒ C (2)
Then another deducing step:
C ⇒ D (3)
where D is the contradictory condition(b) we are seeking. We conclude from this by the principle of proof by contradiction(a) that:
¬A (4)

B. An analysis of the proof by contradiction in section A.
From the combined implications in section A, we here produce what we might call the grand formula of proof by contradiction. Then we proceed by showing that this formula reduces to (4) which means that ¬A is indeed true.

1. First we combine (1) and (2) into one condition:
(A ⇒ B) ∧ (B ⇒ C) (5) (1) and (2)
which is true because (1) and (2) are true.
Next we manipulate (5). Note: I use = instead of ⇔ since either means the same on the set Bool(e).
(A ⇒ B) ∧ (B ⇒ C) = (5)
(¬A ∨ B) ∧ (B ⇒ C) = by A ⇒ B is defined as ¬A ∨ B(d)
¬A ∧ (B ⇒ C) ∨ B ∧ (B ⇒ C) = by law of distributivity(c)
¬A ∧ (true) ∨ B ∧ (¬B ∨ C) = by (2) and B ⇒ C is defined as ¬B ∨ C(d)
¬A ∨ (B ∧ ¬B ∨ B ∧ C) = by law of identity(c) and law of distributivity(c)
¬A ∨ (false ∨ B ∧ C) = by law of complements(c)
¬A ∨ B ∧ C = by law of identity(c)
A ⇒ B ∧ C (6) by A ⇒ B ∧ C is defined as ¬A ∨ B ∧ C(d)

2. Now we combine (6) and (3):
(A ⇒ B ∧ C) ∧ (C ⇒ D) (7) (6) and (3)
which is true because (6) and (3) are true.
By using (3), we treat (7) in the same way as we used (2) to treat (5):
(A ⇒ B ∧ C) ∧ (C ⇒ D) = (7)
(¬A ∨ B ∧ C) ∧ (C ⇒ D) = by A ⇒ B ∧ C is defined as ¬A ∨ B ∧ C(d)
¬A ∧ (C ⇒ D) ∨ B ∧ C ∧ (C ⇒ D) = by law of distributivity(c)
¬A ∧ (true) ∨ B ∧ C ∧ (¬C ∨ D) = by (3) and C ⇒ D is defined as ¬C ∨ D(d)
¬A ∨ (B ∧ C ∧ ¬C ∨ B ∧ C ∧ D) = by law of identity(c) and law of distributivity(c)
¬A ∨ (false ∨ B ∧ C ∧ D) = by law of complements(c)
¬A ∨ B ∧ C ∧ D = by law of identity(c)
A ⇒ B ∧ C ∧ D (8) by A ⇒ B ∧ C ∧ D is defined as ¬A ∨ B ∧ C ∧ D(d)
(8) is an example of what I call the grand formula of proof by contradiction. It expresses that we can combine the statements (1) (2) and (3) into one statement, i.e. (A ⇒ B) ∧ (B ⇒ C) ∧ (C ⇒ D), and replacing "B) ∧ (B ⇒" with "B ∧" and "C) ∧ (C ⇒" with "C ∧".

3. Let us study the contradictory(b) situation between A and D a bit closer. This situation means that A and D cannot be true at the same time. Therefore, if A is true then D is false and vice versa.
Let us have a closer look at (8):
A ⇒ B ∧ C ∧ D = (8)
¬A ∨ B ∧ C ∧ D = by A ⇒ B ∧ C ∧ D is defined as ¬A ∨ B ∧ C ∧ D(d)
true ∧ (¬A ∨ B ∧ C ∧ D) = by law of identity(c)
(A = true ∨ A = false) ∧ (¬A ∨ B ∧ C ∧ D) = as (A = true ∨ A = false) is true as A is either true or false
(A = true) ∧ (¬A ∨ B ∧ C ∧ D) ∨ (A = false) ∧ (¬A ∨ B ∧ C ∧ D) =
by law of distributivity(c)
(A = true) ∧ (false ∨ B ∧ C ∧ false) ∨ (A = false) ∧ (true ∨ B ∧ C ∧ D) =
as D (the first one) is false when A is true
(A = true) ∧ (false ∨ false) ∨ (A = false) ∧ (true) =
as B ∧ C ∧ false = false(f1) and true ∨ B ∧ C ∧ D = true(f2)
false ∨ ¬A = by law of identity(c) and (A = true) ∧ false = false(f1) and (A = false) = ¬A
¬A by law of identity(c)
which is the same as (4), which is what we wanted to prove.

References.
(a) Proof by contradiction, https://en.wikipedia.org/wiki/Proof_by_contradiction.
(b) Contradiction, https://en.wikipedia.org/wiki/Contradiction.
(c) Boolean algebra (structure), https://en.wikipedia.org/wiki/Boolean_algebra_(structure).
(d) Material implication (rule of inference), https://en.wikipedia.org/wiki/Material_implication_(rule_of_inference).
(e) Logical biconditional, https://en.wikipedia.org/wiki/Logical_biconditional (see Truth table, the column A↔B).
(f) Boolean algebra, https://en.wikipedia.org/wiki/Boolean_algebra.
1. See Logical operation Conjunction.
2. See Logical operation Disjunction.

Last edited by Ivar Sand (2024-08-26 20:49:35)

Math Is Fun Forum

#1 2013-03-03 21:40:40

Behind the scenes of proof by contradiction

Board footer