Law of excluded middle


In logic, the law of excluded middle or the principle of excluded middle states that for every proposition, either this proposition or its negation is true. Symbolically expressed, the law is.
The law of the excluded middle is also known as the law/'principle of the excluded third', in Latin principium tertii exclusi. Another Latin designation for the law is tertium non datur or "no third is given".
In classical logic, the law of the excluded middle is taken as a tautology. Intuitionistic logic, by contrast, does not affirm the law.

History

Aristotle

writes in a history of the so-called laws of thought:

The Sea Battle

Yet in On Interpretation, Book 9, Aristotle seems to deny the law of excluded middle in the case of future contingents, in his discussion on the sea battle. It would seem to entail fatalism or logical determinism; and for this reason, the Stoics like Chrysippus affirmed it and embraced fatalism. Epicureans denied the law of excluded middle for this reason.
Some also take it to be a denial of the semantical principle of bivalence, which states that every proposition is either true or false. The principle of bivalence always implies the law of excluded middle, while the converse is not always true.

Leibniz

Russell and Whitehead

The principle was stated as a theorem of propositional logic by Russell and Whitehead in Principia Mathematica as:
✸2.1 ~p ∨ ''p''

Formalists versus Intuitionists

From the late 1800s through the 1930s, a bitter, persistent debate raged between Hilbert and his followers versus Hermann Weyl and L. E. J. Brouwer. Brouwer's philosophy, called intuitionism, started in earnest with Leopold Kronecker in the late 1800s.
Hilbert intensely disliked Kronecker's ideas:
The debate had a profound effect on Hilbert. Reid indicates that Hilbert's second problem evolved from this debate :
Thus, Hilbert was saying: "If p and ~p are both shown to be true, then p does not exist", and was thereby invoking the law of excluded middle cast into the form of the law of contradiction.
The rancorous debate continued through the early 1900s into the 1920s; in 1927 Brouwer complained about "polemicizing against it in sneering tones". But the debate was fertile: it resulted in Principia Mathematica, and that work gave a precise definition to the law of excluded middle, and all this provided an intellectual setting and the tools necessary for the mathematicians of the early 20th century:
Brouwer reduced the debate to the use of proofs designed from "negative" or "non-existence" versus "constructive" proof:
In his lecture in 1941 at Yale and the subsequent paper, Gödel proposed a solution: "that the negation of a universal proposition was to be understood as asserting the existence … of a counterexample"
Gödel's approach to the law of excluded middle was to assert that objections against "the use of 'impredicative definitions had "carried more weight" than "the law of excluded middle and related theorems of the propositional calculus". He proposed his "system Σ … and he concluded by mentioning several applications of his interpretation. Among them were a proof of the consistency with intuitionistic logic of the principle ~ "
The debate seemed to weaken: mathematicians, logicians and engineers continue to use the law of excluded middle in their daily work.

Intuitionist definitions of the law (principle) of excluded middle

The following highlights the deep mathematical and philosophic problem behind what it means to "know", and also helps elucidate what the "law" implies. Their difficulties with the law emerge: that they do not want to accept as true implications drawn from that which is unverifiable or from the impossible or the false..
Brouwer offers his definition of "principle of excluded middle"; we see here also the issue of "testability":
Kolmogorov's definition cites Hilbert's two axioms of negation
  1. A →
  2. →
where ∨ means "or". The equivalence of the two forms is easily proved

Examples

For example, if P is the proposition:
then the law of excluded middle holds that the logical disjunction:
is true by virtue of its form alone. That is, the "middle" position, that Socrates is neither mortal nor not-mortal, is excluded by logic, and therefore either the first possibility or its negation must be true.
An example of an argument that depends on the law of excluded middle is a proof by cases such as follows. We seek to prove that
It is known that is irrational. Consider the number
Clearly this number is either rational or irrational. If it is rational, the proof is complete, and
But if is irrational, then let
Then
and 2 is certainly rational. This concludes the proof.
In the above argument, the assertion "this number is either rational or irrational" invokes the law of excluded middle. An intuitionist, for example, would not accept this argument without further support for that statement. This might come in the form of a proof that the number in question is in fact irrational ; or a finite algorithm that could determine whether the number is rational.

Non-constructive proofs over the infinite

The above proof is an example of a non-constructive proof disallowed by intuitionists:
.
By non-constructive Davis means that "a proof that there actually are mathematic entities satisfying certain conditions would not have to provide a method to exhibit explicitly the entities in question.". Such proofs presume the existence of a totality that is complete, a notion disallowed by intuitionists when extended to the infinite—for them the infinite can never be completed:
David Hilbert and Luitzen E. J. Brouwer both give examples of the law of excluded middle extended to the infinite. Hilbert's example: "the assertion that either there are only finitely many prime numbers or there are infinitely many" ; and Brouwer's: "Every mathematical species is either finite or infinite.". In general, intuitionists allow the use of the law of excluded middle when it is confined to discourse over finite collections, but not when it is used in discourse over infinite sets. Thus intuitionists absolutely disallow the blanket assertion: "For all propositions P concerning infinite sets D: P or ~P".
Putative counterexamples to the law of excluded middle include the liar paradox or Quine's paradox. Certain resolutions of these paradoxes, particularly Graham Priest's dialetheism as formalised in LP, have the law of excluded middle as a theorem, but resolve out the Liar as both true and false. In this way, the law of excluded middle is true, but because truth itself, and therefore disjunction, is not exclusive, it says next to nothing if one of the disjuncts is paradoxical, or both true and false.

Criticisms

The Catuṣkoṭi is an ancient alternative to the law of excluded middle, which examines all four possible assignments of truth values to a proposition and its negation. It has been important in Indian logic and Buddhist logic as well as the ancient Greek philosophical school known as Pyrrhonism.
Many modern logic systems replace the law of excluded middle with the concept of negation as failure. Instead of a proposition's being either true or false, a proposition is either true or not able to be proved true. These two dichotomies only differ in logical systems that are not complete. The principle of negation as failure is used as a foundation for autoepistemic logic, and is widely used in logic programming. In these systems, the programmer is free to assert the law of excluded middle as a true fact, but it is not built-in a priori into these systems.
Mathematicians such as L. E. J. Brouwer and Arend Heyting have also contested the usefulness of the law of excluded middle in the context of modern mathematics.

In mathematical logic

In modern mathematical logic, the excluded middle has been argued to result in possible self-contradiction. It is possible in logic to make well-constructed propositions that can be neither true nor false; a common example of this is the "Liar's paradox", the statement "this statement is false", which is argued to itself be neither true nor false. Arthur Prior has argued that the Paradox is not an example of a statement that cannot be true or false. The law of excluded middle still holds here as the negation of this statement "This statement is not false", can be assigned true. In set theory, such a self-referential paradox can be constructed by examining the set "the set of all sets that do not contain themselves". This set is unambiguously defined, but leads to a Russell's paradox: does the set contain, as one of its elements, itself? However, in the modern Zermelo–Fraenkel set theory, this type of contradiction is no longer admitted. Furthermore, paradoxes of self reference can be constructed without even invoking negation at all, as in Curry's paradox.

Analogous laws

Some systems of logic have different but analogous laws. For some finite n-valued logics, there is an analogous law called the law of excluded n''+1th. If negation is cyclic and "∨" is a "max operator", then the law can be expressed in the object language by, where "~...~" represents n''−1 negation signs and "∨... ∨" n−1 disjunction signs. It is easy to check that the sentence must receive at least one of the n truth values.
Other systems reject the law entirely.

Law of the weak excluded middle

A particularly well-studied intermediate logic is given by De Morgan logic, which adds the axiom to intuitionistic logic, which is sometimes called the law of the weak excluded middle.
This is equivalent to a few other statements:
*