Principium tertii exclusi and Reductio ad absurdum: ancient mathematical “spells”
Since ancient Greece, mathematicians have sought from logic to prove that mathematical properties are true.
Thus, there are several techniques of demonstration, the direct form, the contrapositive, the inductive … but one in particular is somewhat polemical as well as effective, the Reductio ad absurdum (which in Latin means Reduction to the Absurd).
This technique has been around since ancient Greece, and it starts from a principle that the simplest logics do not have, known as Principium tertii exclusi (which in Latin means Law of the excluded middle).
These mysterious words, which with some unusual frequency make us resort to their Latin pronunciation and seem more like spells like those seen in fantasy films, have a simple isolated meaning compared to the “devastating” power they exert in some demonstrations.
To begin with, the Law of the excluded middle WHEN IT APPLIES, it says that a statement is true, or its negation is true, and there is no “third option” (do you understand why it is called “the excluded middle”?). A situation where the Law of the Excluded Middle DOES NOT APPLY has already been discussed in this blog post The Double Negative-Inator Failure.
This Law belongs to Classical Logic, so it fits well in Mathematics as we know it, see an example:
- Let x be a Natural number greater than 1. One of the statements will be true.
- the number x is prime;
- the number x is not prime.
Note that in this case there is no third option. That is, if we show that either of the two statements is false, then the other must be true. But be careful, we can easily spell this law wrong thinking we are on the right track, see an example:
- Let x be an integer. One of the statements will be true.
- the number x divides y with remainder 0;
- the number x divides y with a remainder other than 0.
In this example, we might get the impression that the Law of the Excluded Middle has applied… but what if y is equal to 0? Neither of the two options occurs, that is, there is still a “third option”.
Thus, when an assertion allows the use of the Law of the Excluded Middle, it can be attacked with Reduction to Absurdity. The idea in this case involves demonstrating that one of the statements is false assuming that it is true (did it seem a bit confusing? it seems that we are going in the opposite direction of what we intend). However, when we assume that the statement is true and show that this has led us to an Absurdity (a contradictory conclusion), then we have that statement to be false. So, by the Law of the Excluded Middle the other statement must be true.
To better illustrate this mathematical “spell”, we will present two proofs by Reduction to absurdity that have existed since ancient Greece.
Statement: √2 is not rational (be careful, Pythagoras killed the student who created this proof)
- Demonstration:
- suppose √2 is rational
- then √2 can be written as p/q where p and q ∈ ℤ, q ≠ 0 and gcd(p, q) = 1;
- but (p/q)² = p²/q² = 2, so p² = 2.q²;
- this implies that p² is even, so p must be even, so we can write p as 2.n where n ∈ ℤ;
- thus, (2.n)² = 4.n² = 2.q², so 2.n² = q²;
- this implies that q² is even, so q must be even, so we can write q as 2.m where m ∈ ℤ;
- however, we have that gcd(p, q) = gcd(2.n, 2.m) = 2, Absurd (the contradiction is that p and q were defined so that gcd(p, q) = 1);
- therefore, √2 is not rational.
Statement: There are infinitely many prime numbers (this demonstration has already appeared in the post Demonstrate with charm)
- Demonstration:
- suppose there are only k primes, p1, p2, …, pk;
- take n = p1.p2…pk (the product of the k primes);
- being n+1 greater than pk, n+1 is not prime and does not have a common divisor with n;
- being pj (one of k primes) divisor of n and n+1, then pj divides [(n+1) – n] = 1, which is absurd (the contradiction lies that no prime number can divide 1).
Remember as a diligent apprentice of sorcery, whenever we want to use the “spell” Reductio ad absurdum we must first use the “spell” Principium tertii exclusi.