The Law of Excluded Middle

Author:   Shivam Baurai
B.Sc. (H) Mathematics

---

This is an assessment of the much debated law of excluded middle, which has an intimate relationship with mathematical reasoning. This article will attempt to describe this law, establish its role in mathematics and explore the arguments against the law. An argument against the criticism will be provided to maintain neutrality in this discussion; this article is not written to take any particular side, it is written to introduce the field of metamathematics, using fairly familiar concepts

This article refers to works of formal logic and philosophy. Both fields are treated to make them as irrelevant as possible for the purpose of this article, which is achieved by giving simplified, and not technical, explanations of concepts belonging to these fields.

The references given in the article provide a detailed discussion of the concepts this article introduces. The references, the reader will find, pertain mostly to the fields of logic and mathematical philosophy. Before beginning, it is important to introduce the ideas that are prerequisites for this article.

Following is a list of important symbols:

• $p$ : a proposition. In simple terms, this is a statement. For example, “This car is red”.
• $\sim$ : This symbol denotes negation. For example, $\sim p$ reads “This car is not red”.
• $\circ$ : This symbol denotes the logical conjunction “and”. The usage is similar to the use of the symbol $\cap$ in set theory. For example, given p: “x is an even number” and q: “x is a prime number”, then $p\circ q$ : “x is an even number that is prime” or “$x=2$ ”.
• $\vee$ : This symbol denotes the logical disjunction “or”. The usage is similar to the use of the symbol $\cup$ in set theory. For example, given p: “x is a positive real number” and q: “x is a negative real number”, one deduces that $p\vee q$: “$x\ne 0$”.
• $\Rightarrow$: This symbol denotes implication. $p\Rightarrow q$ means that whenever p is true, q is true and whenever p is false, so is q.

Now, we shall state a few important laws/principles/terms:

• Principle of reductio ad absurdum: A form of argument, where a proposition is disproven following its implication of the absurd. Symbolically put, the argument follows: Assume p is true, $p\Rightarrow q$ , and $p\Rightarrow (q\circ \sim q)$. This means that $p\Rightarrow (q\circ \sim q)$, which cannot hold true (the proof of this will follow later in the article). For convenience, we shall call this RAA.
• Tautology: An assertion that is true for every possible interpretation. For example, p: “The ball is green, or it is not green” is true whatever the colour of the ball.
• De Morgan’s Law: $\sim (p\circ q)\iff \sim p\vee \sim q$.
• Principle of vicious-circle: “Whatever involves all of a collection must not be one of the collection”. This principle is posited as an axiom.

Now, we can define the law of excluded middle (LEM), which we introduce as an axiom.

Given a proposition, either it is true or its negation is.

Symbolically,$$p\vee \sim p$$

We now introduce the law of non-contradiction as a theorem:

Theorem (Law of non-contradiction - LNC). A proposition cannot be both true and false at the same time. Symbolically, $\sim (p\circ \sim p)$

Proof. Note that $p\vee \sim p$ (LEM).

Then, by De Morgan’s law $p\vee \sim p\Rightarrow \sim (p\circ \sim q)$.

It has been shown that LNC is deducible from LEM. Further, we can now present a basic definition of LEM: Given a proposition, either it is true or false. Note that RAA is due to LNC. In the definition of RAA, it was remarked that $p\circ \sim p$ is absurd. As per LNC, it has been established that this assertion is false, and therefore absurd. Recall the technique of proof by contradiction. The technique is a direct application of RAA and LEM. Since it has been shown that LEM is responsible for RAA, we conclude that proof by contradiction is also due to LEM. Any question on the validity of LEM, therefore, has huge consequences for mathematics. Not only is the technique of proof by contradiction under the scanner, but a considerable part of mathematical reasoning needs to be revisited.

Validity of the Law of Excluded Middle

Consider the following proposition (Liar’s Paradox):

I am lying

Let us consider the two possibilities permitted by LEM:

1. The proposition is true - This means I am lying, which implies that I am not lying. Therefore, the proposition is false, which cannot happen (LNC).
2. The proposition is false - This means I am not lying, which implies that I am lying. Therefore, the proposition is true. Again, this cannot happen.

Here, LEM fails to hold. However, this paradox is not without a solution. Before proceeding further, it should clearly be recorded that LEM is a tautology. (Notice that LEM clearly holds sometimes; for example, p: “x is a positive real number”).

First of all, it should be remarked that natural language is far too incoherent and ambiguous to be formalized. Therefore, the solution must begin with the translation of this statement into the symbolic language of logic. Such an interpretation goes like this:

e is a proposition p, that if I affirm it, it is false

Now, we call our interpretation q. Note that q refers to all propositions p, since we claim that LEM is a tautology. The paradox arises because of self-reference; since q is defined for all propositions p, it must also be defined for q. This, as already seen, leads to contradiction of LEM. Here, the principle of vicious-circle must be referred. This principle prohibits q to refer to itself, and therefore, the paradox is blocked.

The principle is due to Bertrand Russell. He argued that all logical paradoxes arise because of the violation of this principle. To return to familiarity, it is useful to consider Russell’s Paradox, which can be approached along similar lines. The paradox is as follows: Define $R:=x|x\in x$ Then,

$$R\in R\iff R\notin R$$.

The principle of vicious circle solves the Russell’s paradox. However, it is important here to give a slightly more academic treatment of this principle - that is, Russell’s Theory of types.

Russell assigned types to sets. For example, sets of type I would be elements in a set of type II, and no element of type II or higher can be contained in a set of type II. Similarly, we can treat sets of type III, IV and so on, creating a hierarchy of sets. The hierarchy develops as follows: individuals are placed at the lowest level (for example, natural numbers), followed by a class of individuals (for example, a set of natural numbers), and then a class further up (For example, the set of sets of natural numbers), and so on.

It is now easy to see that the question whether R is contained in itself is trivially solved. A similar treatment of the Liar’s paradox is possible. If p is a proposition of type n, then q becomes a proposition of type n + 1, and therefore, the paradox is solved.

Set theory in particular deals with paradoxes of this kind by introducing strict axioms (ZFC Set Theory), which blocks the construction of sets that contain themselves. Since the approach of Russell’s solution is similar to this one (both introduce axioms to block self-reference), and since neither suggests against LEM, a detailed discussion on axiomatic set theory is omitted.

Returning to Liar’s paradox, Russell’s solution is not without criticism. The works of Tarski, Kripke, and Barwise and Etchemendy deal with these criticisms and provide arguably stronger solutions. They are, however, a break from the mathematics-centric perspective that this article attempts to take. It is important here to comment that the contradiction of LEM is far from being merely an abstract idea. Indeed, we have applications where there are more than two truth values (true and false). There is one example of the included middle in quantum mechanics - the famous thought experiment by Erwin Schrödinger (Schrödinger’s cat), which argues that if a cat is sealed in a box with a radioactive item, one would not know whether the cat is dead or alive until the box is opened. In simple terms, the cat, in a sense, is both dead and alive until the box is opened. Further, it is possible to develop systems of logic where, given a proposition, it can have more than two truth values: finite-valued logic, which allows n truth values (applications are found in the field of Electronics Design, and study of stable states of circuits and integrated circuits), and infinite-valued logic, which allows infinitely many truth values (for example, fuzzy logic associates truth values with real numbers in the interval [0, 1], and finds applications in facial recognition, as well as economics, particularly in risk assessment systems).

Constructivism in Mathematics

LEM does not find unanimous support amongst mathematicians. While everyone agrees that LEM holds when limited to finite collections, criticism arises when discussing the extension of LEM to the infinite (although there do exist examples where LEM holds for infinite sets - There are either finite primes or infinite; it cannot be generalized). Mathematics based on a logical system that does not assume LEM is called Constructive Mathematics. Constructivism is not merely mathematics without proofs by contradiction; the differences are far more fundamental. For example, in constructive mathematics, the phrase “there exists” is replaced by “we can construct”. It does not suffice to prove the existence of a mathematical entity, we must also construct it. Constructive logic actually ties existence with construction with the help of the existence property: Whenever we prove constructively that there exists a $x\in X:P(x)$ is true, we actually find at least one $a\in X:P(a)$; we call a the witness.

Supporters of constructivism argue that these proofs are superior as they give an algorithm to construct such entities. A mathematical entity, constructivists say, is anything that can be constructed.

Classical logic (where LEM holds) also is not without supporters. Amongst them is David Hilbert, who remarked, “Taking the principle of excluded middle from the mathematician would be the same, say, as proscribing the telescope to the astronomer or to the boxer the use of his fists”. Existence is free from contradiction, argues Hilbert. Therefore, if we can prove that an object, having particular properties, does not cause contradictions, then it exists, and constructing that object is not required. It is fascinating to note that while constructive mathematics and ‘classical’ mathematics differ at the foundational level, their works are remarkably similar. Foundations of Constructive Analysis by E. Bishop develops much of 20^th century analysis using the principles of constructive mathematics.

It is important now to see the working of constructive mathematics, and contrast it with nonconstructive mathematics. The obvious place to begin is with the proof of the irrationality of $\sqrt{2}$.

Theorem.$\sqrt{2}$ is irrational.

Proof. Let $r=\frac{a}{b}$ , where a, b are positive integers.
If a is even, b cannot be even.
Then, a² is doubly even (i.e. divisible by 4), while 2b² is singly even (i.e. divisible by 2, but not 4).
Therefore, 2b² and a² are distinct integers.
If a is odd, and b is even, 2b² and a² are clearly distinct. And if a and b are both odd, we again reach the same conclusion.
So, we have $|2b^2-a^2|\ge 1$. Dividing and multiplying by $\sqrt{2}+\frac{a}{b}$ , we get

$$|\sqrt{2}-\frac{a}{b}|=\frac{|2b^2-a^2|}{b^2(\sqrt{2}+\frac{a}{b})}\ge \frac{1}{b^2(\sqrt{2}+\frac{a}{b})}\ge \frac{1}{3b^2}$$

It has now been established that $\sqrt{2}$ is distinct from any rational number r. Therefore, $\sqrt{2}$ is irrational.

Consider the following theorem, which contrasts the mechanism of constructive and non-constructive proofs.

Theorem. There exist two irrational real numbers a and b such that ab is rational.

Proof. (Non-constructive) Let a and b be irrational real numbers. Consider ab. It must be either rational or irrational. If it is rational, we are done. Assume it is irrational. Suppose we have, ${\sqrt{2}}^{\sqrt{2}}$ which we assume is irrational. Then, ${\left({\sqrt{2}}^{\sqrt{2}}\right)}^{\sqrt{2}}={\sqrt{2}}^{\sqrt{2}}=2$, which is rational.
Proof. (Constructive) Consider the irrational numbers $a=\sqrt{2}$, and $b={\log }_{2}9$. Then $a^b=2({\log }_{2}3)=3$, which is rational.

Note that while the non-constructive proof also constructs irrational numbers a and b which satisfy the theorem (${\sqrt{2}}^{\sqrt{2}}$ is indeed irrational), the proof is not constructive in nature because it explores the possibilities permitted by LEM and shows that one of them must satisfy the theorem, but does not commit to one possibility.

Conclusion

It is important to remark that the debate on the validity of LEM is by no means ‘solved’. However, the deductions that follow from it are still widely accepted in mathematics. Also, as mentioned already, logical systems with more than two truth values not only exist, but also find useful applications in many fields of science and technology. Further, it serves well to remind again of the introductory level of the knowledge provided here; there are sections, especially the one about the validity of LEM, that can be pursued productively, for there are avenues that can be explored (for example, Russell’s solution fails to hold when we strengthen the liar; “The following statement is false”, “The previous statement is true”).

It is a fascinating, almost amusing, fact that constructive proofs are not the new wave of mathematics, as it might seem from the presentation of this article. In fact, some of Hilbert’s earlier works, which were non-constructive, were infamously dismissed as theology. And the initial criticism of Cantor is well-documented. A fantastic presentation of the history of metamathematics and logic, and its protagonists can be found in Logicomix: An Epic Search For Truth (2009) by Apostolos Doxiadis and Christos Papadimitriou.