Law of excluded middle - AbsoluteAstronomy.com

This article uses forms of logical
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

notation. For a concise description of the symbols used in this notation, see List of logic symbols.

In logic

Logic

In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, the law of excluded middle (or the principle of excluded middle) is the third of the so-called three classic laws of thought. It states that for any proposition

Proposition

In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...

, either that proposition is true, or its negation

Negation

In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...

is.

Many modern logic systems reject the law of excluded middle, replacing it with the concept of negation as failure. That is, there is a third possibility: the truth of a proposition is unknown. A classic example illustrating the difference is the proposition: "It is not safe to cross the railroad tracks when a train is coming". One should not deduce it is safe to cross the tracks if one doesn't know a train is coming. The principle of negation-as-failure is used as a foundation for autoepistemic logic

Autoepistemic logic

The autoepistemic logic is a formal logic for the representation and reasoning of knowledge about knowledge. While propositional logic can only express facts, autoepistemic logic can express knowledge and lack of knowledge about facts....

, and is widely used in logic programming

Logic programming

Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...

. In these systems, the programmer is free to assert the law of excluded middle as a true fact; it is not built-in a priori into these systems.

The earliest known formulation of the principle is in the book On Interpretation
On Interpretation
Aristotle's De Interpretatione or On Interpretation is one of the earliest surviving philosophical works in the Western tradition to deal with the relationship between language and logic in a comprehensive, explicit, and formal way.The work begins by analyzing simple categoric...

by Aristotle

Aristotle

Aristotle was a Greek philosopher and polymath, a student of Plato and teacher of Alexander the Great. His writings cover many subjects, including physics, metaphysics, poetry, theater, music, logic, rhetoric, linguistics, politics, government, ethics, biology, and zoology...

, where he says that of two contradictory propositions (i.e. where one proposition is the negation of the other) one must be true, and the other false. He also states it as a principle in the Metaphysics
Metaphysics (Aristotle)
Metaphysics is one of the principal works of Aristotle and the first major work of the branch of philosophy with the same name. The principal subject is "being qua being", or being understood as being. It examines what can be asserted about anything that exists just because of its existence and...

book 3, saying that it is necessary in every case to affirm or deny, and that it is impossible that there should be anything between the two parts of a contradiction.

The principle should not be confused with the principle of bivalence

Principle of bivalence

In logic, the semantic principle of bivalence states that every declarative sentence expressing a proposition has exactly one truth value, either true or false...

, which states that every proposition is either true or false, and has only a semantical formulation.

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 (P ∨ ~P ∨ ~~P ∨ ... ∨ ~...~P), 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 (and not a value that is not one of the n). Other systems reject the law entirely.

The law is also known as the law (or principle) of the excluded third (or of the excluded middle), or, in Latin

Latin

Latin is an Italic language originally spoken in Latium and Ancient Rome. It, along with most European languages, is a descendant of the ancient Proto-Indo-European language. Although it is considered a dead language, a number of scholars and members of the Christian clergy speak it fluently, and...

, principium tertii exclusi. Yet another Latin designation for this law is tertium non datur: "no third (possibility) is given".

The principle of excluded middle, along with its complement, the law of contradiction (the second of the three classic laws of thought), are correlates of the law of identity

Law of identity

In logic, the law of identity is the first of the so-called three classic laws of thought. It states that an object is the same as itself: A → A ; While this can also be listed as A ≡ A this is redundant Any reflexive relation upholds the law of identity...

(the first of these laws). Because the principle of identity intellectually partitions the Universe into exactly two parts: "self" and "other", it creates a dichotomy

Dichotomy

A dichotomy is any splitting of a whole into exactly two non-overlapping parts, meaning it is a procedure in which a whole is divided into two parts...

wherein the two parts are "mutually exclusive" and "jointly exhaustive". The principle of contradiction is merely an expression of the mutually exclusive aspect of that dichotomy, and the principle of excluded middle is an expression of its jointly exhaustive aspect.

Examples

For example, if P is the proposition:

Socrates is mortal.

then the law of excluded middle holds that the logical disjunction

Logical disjunction

In logic and mathematics, a two-place logical connective or, is a logical disjunction, also known as inclusive disjunction or alternation, that results in true whenever one or more of its operands are true. E.g. in this context, "A or B" is true if A is true, or if B is true, or if both A and B are...

Either Socrates is mortal, or it is not the case that Socrates is mortal.

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 (Socrates is mortal) or its negation (it is not the case that Socrates is mortal) must be true.

An example of an argument that depends on the law of excluded middle follows. We seek to prove that there exist two irrational number

Irrational number

In mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....

and

such that

is rational.

It is known that

is irrational (see proof). Consider the number

Clearly (excluded middle) this number is either rational or irrational. If it is rational, the proof is complete, and

and

But if

is irrational, then let

and

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 rational, as the case may be); or a finite algorithm that could determine whether the number is rational or not.

The Law in 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 have to provide a method to exhibit explicitly the entities in question." (p. 85). 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:
Indeed, Hilbert

David Hilbert

David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...

and Brouwer

Luitzen Egbertus Jan Brouwer

Luitzen Egbertus Jan Brouwer FRS , usually cited as L. E. J. Brouwer but known to his friends as Bertus, was a Dutch mathematician and philosopher, a graduate of the University of Amsterdam, who worked in topology, set theory, measure theory and complex analysis.-Biography:Early in his career,...

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" (quoted in Davis 2000:97); and Brouwer's: "Every mathematical species is either finite or infinite." (Brouwer 1923 in van Heijenoort 1967:336).

In general, intuitionists allow the use of the law of excluded middle when it is confined to discourse over finite collections (sets), but not when it is used in discourse over infinite sets (e.g. the natural numbers). Thus intuitionists absolutely disallow the blanket assertion: "For all propositions P concerning infinite sets D: P or ~P" (Kleene 1952:48).

For more about the conflict between the intuitionists (e.g. Brouwer) and the formalists (Hilbert) see Foundations of mathematics
Foundations of mathematics
Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...

and Intuitionism
Intuitionism
In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...

.

Putative counterexamples to the law of excluded middle include the liar paradox

Liar paradox

In philosophy and logic, the liar paradox or liar's paradox , is the statement "this sentence is false"...

or Quine's Paradox

Quine's Paradox

Quine's paradox is a paradox concerning truth values, attributed to Willard Van Orman Quine. It is related to the liar paradox as a problem, and it purports to show that a sentence can be paradoxical even if it is not self-referring and does not use demonstratives or indexicals...

. Certain resolutions of these paradoxes, particularly Graham Priest

Graham Priest

Graham Priest is Boyce Gibson Professor of Philosophy at the University of Melbourne and Distinguished Professor of Philosophy at the CUNY Graduate Center, as well as a regular visitor at St. Andrews University. Priest is a fellow in residence at Ormond College. He was educated at the University...

's dialetheism

Dialetheism

Dialetheism is the view that some statements can be both true and false simultaneously. More precisely, it is the belief that there can be a true statement whose negation is also true...

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.

Aristotle

wrote that ambiguity can arise from the use of ambiguous names, but cannot exist in the "facts" themselves:
Aristotle's assertion that "...it will not be possible to be and not to be the same thing", which would be written in propositional logic as ¬ (P ∧ ¬P), is a statement modern logicians could call the law of excluded middle (P ∨ ¬P), as distribution of the negation of Aristotle's assertion makes them equivalent, regardless that the former claims that no statement is both true and false, while the latter requires that any statement is either true or false.

However, Aristotle also writes, "since it is impossible that contradictories should be at the same time true of the same thing, obviously contraries also cannot belong at the same time to the same thing" (Book IV, CH 6, p. 531). He then proposes that "there cannot be an intermediate between contradictories, but of one subject we must either affirm or deny any one predicate" (Book IV, CH 7, p. 531). In the context of Aristotle's traditional logic, this is a remarkably precise statement of the law of excluded middle, P ∨ ¬P.

Leibniz

Bertrand Russell and Principia Mathematica

Bertrand Russell

Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...

asserts a distinction between the "law of excluded middle" and the "law of noncontradiction". In The Problems of Philosophy
The Problems of Philosophy
The Problems of Philosophy is one of Bertrand Russell's attempts to create a brief and accessible guide to the problems of philosophy...

, he cites three "Laws of Thought" as more or less "self evident" or "a priori" in the sense of Aristotle:
It is correct, at least for bivalent logic—i.e. it can be seen with a Karnaugh map

Karnaugh map

The Karnaugh map , Maurice Karnaugh's 1953 refinement of Edward Veitch's 1952 Veitch diagram, is a method to simplify Boolean algebra expressions...

—that Russell's Law (2) removes "the middle" of the inclusive-or

Logical disjunction

used in his law (3). And this is the point of Reichenbach's demonstration that some believe the exclusive-or should take the place of the inclusive-or

Logical disjunction

.

About this issue (in admittedly very technical terms) Reichenbach observes:
In line (30) the "(x)" means "for all" or "for every", a form used by Russell and Reichenbach; today the symbolism is usually

x. Thus an example of the expression would look like this:

(pig): (Flies(pig) ⊕ ~Flies(pig))
(For all instances of "pig" seen and unseen): ("Pig does fly" or "Pig does not fly" but not both simultaneously)

A formal definition from Principia Mathematica

Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...

(PM) defines the law of excluded middle formally:
So just what is "truth" and "falsehood"? At the opening PM quickly announces some definitions:
This is not much help. But later, in a much deeper discussion, ("Definition and systematic ambiguity of Truth and Falsehood" Chapter II part III, p. 41 ff ) PM defines truth and falsehood in terms of a relationship between the "a" and the "b" and the "percipient". For example "This 'a' is 'b'" (e.g. "This 'object a' is 'red'") really means "'object a' is a sense-datum" and "'red' is a sense-datum", and they "stand in relation" to one another and in relation to "I". Thus what we really mean is: "I perceive that 'This object a is red'" and this is an undeniable-by-3rd-party "truth".

PM further defines a distinction between a "sense-datum" and a "sensation":
Russell reiterated his distinction between "sense-datum" and "sensation" in his book The Problems of Philosophy (1912) published at the same time as PM (1910–1913):
Russell further described his reasoning behind his definitions of "truth" and "falsehood" in the same book (Chapter XII Truth and Falsehood).

Consequences of the law of excluded middle in Principia Mathematica

From the law of excluded middle, formula ✸2.1 in Principia Mathematica
Principia Mathematica
The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...

, Whitehead and Russell derive some of the most powerful tools in the logician's argumentation toolkit. (In Principia Mathematica, formulas and propositions are identified by a leading asterisk and two numbers, such as "✸2.1".)

✸2.1 ~p ∨ p "This is the Law of excluded middle" (PM, p. 101).

The proof of ✸2.1 is roughly as follows: "primitive idea" 1.08 defines p → q = ~p ∨ q. Substituting p for q in this rule yields p → p = ~p ∨ p. Since p → p is true (this is Theorem 2.08, which is proved separately), then ~p ∨ p must be true.

✸2.11 p ∨ ~p (Permutation of the assertions is allowed by axiom 1.4)

✸2.12 p → ~(~p) (Principle of double negation, part 1: if "this rose is red" is true then it's not true that "'this rose is not-red' is true".)

✸2.13 p ∨ ~{~(~p)} (Lemma together with 2.12 used to derive 2.14)

✸2.14 ~(~p) → p (Principle of double negation, part 2)

✸2.15 (~p → q) → (~q → p) (One of the four "Principles of transposition". Similar to 1.03, 1.16 and 1.17. A very long demonstration was required here.)

✸2.16 (p → q) → (~q → ~p) (If it's true that "If this rose is red then this pig flies" then it's true that "If this pig doesn't fly then this rose isn't red.")

✸2.17 ( ~p → ~q ) → (q → p) (Another of the "Principles of transposition".)

✸2.18 (~p → p) → p (Called "The complement of reductio ad absurdum. It states that a proposition which follows from the hypothesis of its own falsehood is true" (PM, pp. 103–104).)

Most of these theorems—in particular ✸2.1, ✸2.11, and ✸2.14—are rejected by intuitionism. These tools are recast into another form that Kolmogorov cites as "Hilbert's four axioms of implication" and "Hilbert's two axioms of negation" (Kolmogorov in van Heijenoort, p. 335).

Propositions ✸2.12 and ✸2.14, "double negation":
The intuitionist

Intuitionism

In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied...

writings of L. E. J. Brouwer refer to what he calls "the principle of the reciprocity of the multiple species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property" (Brouwer, ibid, p. 335).

This principle is commonly called "the principle of double negation" (PM, pp. 101–102). From the law of excluded middle (✸2.1 and ✸2.11), PM derives principle ✸2.12 immediately. We substitute ~p for p in 2.11 to yield ~p ∨ ~(~p), and by the definition of implication (i.e. 1.01 p → q = ~p ∨ q) then ~p ∨ ~(~p)= p → ~(~p). QED (The derivation of 2.14 is a bit more involved.)

Criticisms

Mathematicians such as L. E. J. Brouwer

Luitzen Egbertus Jan Brouwer

and Arend Heyting

Arend Heyting

Arend Heyting was a Dutch mathematician and logician. He was a student of Luitzen Egbertus Jan Brouwer at the University of Amsterdam, and did much to put intuitionistic logic on a footing where it could become part of mathematical logic...

contested the usefulness of the law of excluded middle in the context of the modern mathematics

Stéphane Lupasco

Stéphane Lupasco

Stéphane Lupasco Stéphane Lupasco Stéphane Lupasco (born Ştefan Lupaşcu; (1900–1988) was a Romanian philosopher who developed Non-Aristotelian logic.-Early years:Stéphane Lupasco was born in Bucharest on 11 August 1900. His family belonged to the old Moldavian aristocracy...

(1900-1988) has also substantiated the logic of the included middle, showing that it constitutes "a true logic, mathematically formalized, multivalent (with three values: A, non-A, and T) and non-contradictory" .
Quantum mechanics is said to be an exemplar of this logic, through the superposition

Superposition

Superposition can refer to:* The superposition principle in physics, mathematics, and engineering, describes the overlapping of waves. Particular applications include :** Quantum superposition, in quantum physics** Superposition theorem, in electronics....

of "yes" and "no" quantum states; the included middle is also mentioned as one of the three axioms of transdisciplinarity

Transdisciplinarity

Transdisciplinarity connotes a research strategy that crosses many disciplinary boundaries to create a holistic approach. It applies to research efforts focused on problems that cross the boundaries of two or more disciplines, such as research on effective information systems for biomedical...

, without which reality cannot be understood .

External links

"Contradiction" entry in the Stanford Encyclopedia of Philosophy
Stanford Encyclopedia of Philosophy
The Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Examples

The Law in non-constructive proofs over the infinite

Aristotle

Leibniz

Bertrand Russell and Principia Mathematica

A formal definition from Principia Mathematica

Consequences of the law of excluded middle in Principia Mathematica

Criticisms

See also

External links