Behind the scenes of proof by contradiction II

Ivar Sand · 2025-08-25 01:56:57

(See also Behind the scenes of proof by contradiction at https://www.mathisfunforum.com/viewtopic.php?id=19059)

This post treats the same subject as Behind the scenes of proof by contradiction except in a bit more general way as it treats any number of implications while Behind the scenes of proof by contradiction treats only three. Also, the formulation here uses a sequence of theorems, one theorem referencing the next theorem and I hope that this formulation is more understandable than the formulation found in Behind the scenes of proof by contradiction.

Since these two posts treat the same subject, the introduction found in Behind the scenes of proof by contradiction works for this post as well, so it is not repeated here. Therefore, please look in Behind the scenes of proof by contradiction for the introduction to the subject.

A lemma that treats the special case that the two contradictory propositions are each other's negation is included at the end.

First a note on inconsistency or contradiction:
Two propositions (a) X and Y are inconsistent or contradictory if and only if:
X ∧ Y => false    see reference (b)
Further investigation gives:
(X ∧ Y => false) =
(¬(X ∧ Y) ∨ false) = by the rule of inference (d)
¬(X ∧ Y)    by the law of identity (c1)
which expresses that X and Y cannot be true at the same time, and furthermore:
¬(X ∧ Y) =
¬X ∨ ¬Y    by the first of De Morgan's laws (f)
which expresses that either X or Y is false. (The difference between inconsistency and contradiction is that the Boolean values of two contradictory propositions are different whereas inconsistent propositions may both be false (e).)

Theorem 1:
Let n be a natural number, n>=1.
Let A B1 B2 ... Bn be propositions.
Let
A => B1,
B1 => B2,
...
Bn-1 => Bn
all be true, i.e. proven propositions or theorems.
Let A and Bn be inconsistent or contradictory propositions.

Then:
¬A
is true.

Proof:
We have that:
A => B1,
B1 => B2,
...
Bn-1 => Bn
are true.
Then:
A ⇒ B1 ∧ B2 ... ∧ Bn
is true by Theorem 2.

We also have that A and Bn are inconsistent or contradictory (b) which means that (see the note on inconsistency or contradiction above):
¬A ∨ ¬Bn
is true.

We combine these two propositions using a logical and to get:
(A ⇒ B1 ∧ B2 ... ∧ Bn) ∧ (¬A ∨ ¬Bn)
which is true by the definition of conjunction (g) since both (A ⇒ B1 ∧ B2 ... ∧ Bn) and (¬A ∨ ¬Bn) are true.
We manipulate this proposition:
(A ⇒ B1 ∧ B2 ... ∧ Bn) ∧ (¬A ∨ ¬Bn) =
(¬A ∨ B1 ∧ B2 ... ∧ Bn) ∧ (¬A ∨ ¬Bn) = by the rule of inference (d)
¬A ∨ (B1 ∧ B2 ... ∧ Bn ∧ ¬Bn) =    by the distributivity law (c1) (switch the sides of the equation of the distributivity law)
¬A ∨ (B1 ∧ B2 ... ∧ Bn-1 ∧ false) =    by the complements law (c2)
¬A ∨ (false) =    by the repeated use of the definition of conjunction (g)
¬A    by the identity law (c1)
Accordingly, we have proved that:
¬A
is true since the left-hand side of the first equality in the sequence of equalities is true.
This completes the proof.
QED

Theorem 2:
Let n be a natural number, n>=1.
Let A B1 B2 ... Bn be propositions.
Let
A => B1,
B1 => B2,
...
Bn-1 => Bn
all be true.

Then:
A ⇒ B1 ∧ B2 ... ∧ Bn
is true.

Proof:
We use proof by induction (h).
The proof is trivial for n = 1, the base case of proof by induction.

Now for the induction step of proof by induction.
Suppose that the theorem holds for n = i where i is a natural number, i >= 1.
We need to prove that the theorem holds for n=i+1.

We have that:
A ⇒ B1 ∧ B2 ... ∧ Bi and
Bi ⇒ Bi+1
are true propositions.
We need to prove that:
A ⇒ B1 ∧ B2 ... ∧ Bi ∧ Bi+1
is true.

We combine the propositions A ⇒ B1 ∧ B2 ... ∧ Bi and Bi ⇒ Bi+1:
(A ⇒ B1 ∧ B2 ... ∧ Bi) ∧ (Bi ⇒ Bi+1)
which is true by the definition of conjunction (g) since both (A ⇒ B1 ∧ B2 ... ∧ Bi) and (Bi ⇒ Bi+1) are true
We manipulate this proposition:
(A ⇒ B1 ∧ B2 ... ∧ Bi) ∧ (Bi ⇒ Bi+1) =
(¬A ∨ B1 ∧ B2 ... ∧ Bi) ∧ (Bi ⇒ Bi+1) =    by the rule of inference (d)
¬A ∧ (Bi ⇒ Bi+1) ∨ B1 ∧ B2 ... ∧ Bi ∧ (Bi ⇒ Bi+1) = by the distributivity law (c2) (the commutativity law (c2) is also needed)
¬A ∧ (true) ∨ B1 ∧ B2 ... ∧ Bi ∧ (Bi ⇒ Bi+1) =    as Bi ⇒ Bi+1 is true
¬A ∨ B1 ∧ B2 ... ∧ Bi ∧ (Bi ⇒ Bi+1) =    by the identity law (c2)
¬A ∨ B1 ∧ B2 ... ∧ Bi ∧ (¬Bi ∨ Bi+1) =    by the rule of inference (d)
¬A ∨ B1 ∧ B2 ... ∧ Bi ∧ ¬Bi ∨ B1 ∧ B2 ... ∧ Bi ∧ Bi+1 = by the distributivity law (c2)
¬A ∨ B1 ∧ B2 ... ∧ false ∨ B1 ∧ B2 ... ∧ Bi ∧ Bi+1 = by the complements law (c2)
¬A ∨ false ∨ B1 ∧ B2 ... ∧ Bi ∧ Bi+1 =    by the repeated use of the definition of conjunction (g)
¬A ∨ B1 ∧ B2 ... ∧ Bi ∧ Bi+1 =    by the identity law (c1)
A ⇒ B1 ∧ B2 ... ∧ Bi ∧ Bi+1    by the rule of inference (d)
This means that:
A ⇒ B1 ∧ B2 ... ∧ Bi ∧ Bi+1
is true since the left-hand side of the first equality in the sequence of equalities is true.
This completes the induction procedure and the proof of the theorem.
QED

Lemma:
Let n be a natural number, n>=1.
Let A B1 B2 ... Bn be propositions.
Let
A => B1,
B1 => B2,
...
Bn-1 => Bn
all be true.
Let
Bn = ¬A
be true.

Then:
¬A
is true.

Proof:
We have that the propositions:
A => B1,
B1 => B2,
...
Bn-1 => Bn
are all true.

We intend to prove that A and Bn are inconsistent or contradictory (b).
We do this by evaluating an expression for inconsistency or contradiction.
We choose the expression ¬(A ∧ Bn), see the note on inconsistency or contradiction above.
We have:
   ¬(A ∧ Bn) =
   ¬(A ∧ ¬A) = as Bn = ¬A
   ¬false =    by the law of complements (c2)
   true by reference (i)
from which we conclude that A and Bn are inconsistent or contradictory.

Then it follows by Theorem 1 that:
¬A
is true.
QED

References.
(a) Proposition https://en.wikipedia.org/wiki/Proposition.
(b) Contradiction, https://en.wikipedia.org/wiki/Contradiction.
Note: the formulation "a proposition is a contradiction if false can be derived from it, using the rules of the logic" is a bit more general than the one we use here.
(c) Boolean algebra (structure), https://en.wikipedia.org/wiki/Boolean_a … structure), the table under the header Definition.
(c1) the left column of the table.
(c2) the right column of the table.
(d) Material implication (rule of inference), https://en.wikipedia.org/wiki/Material_ … inference).
(e) 9.1: Recognizing Inconsistency and Contradiction https://human.libretexts.org/Bookshelve … tradiction.
(f) De Morgan's laws https://en.wikipedia.org/wiki/De_Morgan%27s_laws, see for instance the first equation under the header Boolean algebra.
(g) Boolean algebra https://en.wikipedia.org/wiki/Boolean_algebra, the table under the header Basic operations.
(h) Mathematical induction https://en.wikipedia.org/wiki/Mathematical_induction.
(i) Boolean domain https://en.wikipedia.org/wiki/Boolean_domain, the information under the header Generalizations.

Last edited by Ivar Sand (2025-08-27 01:19:45)

Jai Ganesh · 2025-08-25 02:33:18

Please hide tags for hiding the information, and use URL.

Hide here

URL here.

[hide]Hidden text[/ hide]

[url = Here][/url]

Ivar Sand · 2025-08-26 22:46:30

Thanks for the information, Jai Ganesh.

The hide tag does not seem to work because it produces an extra line feed so that the hide tag appears on the next line. Therefore, it is not possible to use the hide tag inside a line, which is what I need it for. The url tag is ok, though.

Jai Ganesh · 2025-08-26 23:02:38

Hi Ivar Sand,

I was experimenting.

Math Is Fun Forum

#1 2025-08-25 01:56:57

Behind the scenes of proof by contradiction II

#2 2025-08-25 02:33:18

Re: Behind the scenes of proof by contradiction II

#3 2025-08-26 22:46:30

Re: Behind the scenes of proof by contradiction II

#4 2025-08-26 23:02:38

Re: Behind the scenes of proof by contradiction II

Board footer