This article may require cleanup to meet Wikipedia's quality standards. Please discuss this issue on the talk page or replace this tag with a more specific message. This article has been tagged since April 2006.

This article uses, in part, forms of logical notation. For a concise description of the notations used, see the Basic and Derived Argument Forms table here, or First-order predicate logic.

In logic, the law of the excluded middle states that the formula "P ∨ ¬P" ("P or not-P") can be deduced from the calculus under investigation. It is one of the defining properties of classical systems of logic. However, some systems of logic have different but analogous laws, while others reject the law of excluded middle entirely. Image File history File links Broom_icon. ... This article does not cite its references or sources. ... Mathematical logic is a subfield of mathematics that is concerned with formal systems in relation to the way that they encode intuitive concepts of mathematical objects such as sets and numbers, proofs, and computation. ... Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ... First-order predicate calculus or first-order logic (FOL) is a theory in symbolic logic that permits the formulation of quantified statements such as there is at least one X such that. ... Logic, from Classical Greek λόγος logos (meaning word, account, reason or principle), is the study of the principles and criteria of valid inference and demonstration. ... Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. ...

The law is also known as the law (or principle) of the excluded third, or, in Latin, principium tertii exclusi. Yet another Latin designation for this law is Tertium non datur: "there is no third (possibility)". Latin is an ancient Indo-European language originally spoken in Latium, the region immediately surrounding Rome. ...

The law of excluded middle is related to the principle of bivalence, which is a semantic principle instead of a law that can be deduced from the calculus. In logic, the principle of bivalence states that for any proposition P, either P is true or P is false. ...

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). In logic, cyclic negation is (assuming that the truth values are linearly ordered) a unary truth function that takes a truth value n and returns n-1 as value if n isnt the lowest value; otherwise it returns the highest value. ...

In rhetoric, the law of excluded middle is readily misapplied, leading to the formal fallacy of the excluded middle, also known as a false dilemma. Rhetoric (from Greek , rhêtôr, orator, teacher) is generally understood to be the art or technique of persuasion through the use of spoken and written language; however, this definition of rhetoric has expanded greatly since rhetoric emerged as a field of study in universities. ... In philosophy, the term logical fallacy properly refers to a formal fallacy : a flaw in the structure of a deductive argument which renders the argument invalid. ... This article does not cite its references or sources. ...

Examples

For example, if P is the proposition:

Socrates is mortal.

then the law of excluded middle holds that the logical disjunction: OR logic gate. ...

Either Socrates is mortal or Socrates is not mortal.

is true by virtue of its form alone.

An example of an argument that depends on the law of excluded middle follows.^[1]. We seek to prove that there exist two irrational numbers a and b such that In mathematics, an irrational number is any real number that is not a rational number, i. ...

a^b is rational.

It is known that is irrational. Consider the number

.

Clearly (excluded middle) this number is either rational or irrational. If it is rational, we are done. If it 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 finitistic 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 the intuitionists: In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ...

"The proof is nonconstructive because it doesn't give specific numbers a and b that satisfy the theorem but only two separate possibilities, one of which must work. (Actually [] is irrational but there is no known easy proof of that fact.)" (Davis p. 220)

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 the intuitionists when extended to the infinite -- for them the infinite can never be completed:

"In classical mathematics there occur non-constructive or indirect existence proofs, which the intuitionists do not accept. For example, to prove there exists an n such that P(n), the classical mathematician may deduce a contradiction from the assumption for all n, not P(n). Under both the classical and the intuitionistic logic, by reductio ad absurdum this gives not for all n, not P(n). The classical logic allows this result to be transformed into there exists an n such that P(n), but not in general the intuitionistic.... the classical meaning, that somewhere in the completed infinite totality of the natural numbers there occurs an n such that P(n), is not available to him, since he does not conceive the natural numbers as a completed totality."

Indeed Hilbert and Brouwer both give examples of the law of excluded middle extended to the infinite. Hilbert's example (quoted in Davis p. 97): "the assertion that either there are only finitely many prime numbers or there are infinitely many" (p. 97); and Brouwer's: "Every mathematical species is either finite or infinite." (Brouwer 1923, in van Heijenoort p. 336).

In general, the 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 the intuitionists absolutely disallow the blanket assertion: "For all propositions P concerning infinite sets D: P or ~P" (Kleene (1952, 1971), p. 48).

For more about the conflict between the intuitionists (e.g. Brouwer) and the formalists (Hilbert) see Foundations of mathematics and Intuitionism.

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. Foundations of mathematics is a term sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ... In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach to mathematics as the constructive mental activity of humans. ... In philosophy and logic, the liar paradox encompasses paradoxical statements such as: These statements are paradoxical because there is no way to assign them a consistent truth value. ... Quines paradox is a paradox concerning truth values, attributed to W. V. O. Quine. ... Graham (Grammy) Priest (born 1948) is Boyce Gibson Professor of Philosophy at the University of Melbourne and a regular visitor at St. ... Dialetheism is a paraconsistent logic typified by its tolerance of at least some contradictions. ...

History

Aristotle

Aristotle wrote that ambiguity can arise from the use of ambiguous names, but cannot exist in the "facts" themselves: Aristotle (Greek: Aristotélēs) (384 BC – 322 BC) was a Greek philosopher, a student of Plato and teacher of Alexander the Great. ...

It is impossible, then, that 'being a man' should mean precisely 'not being a man', if 'man' not only signifies something about one subject but also has one significance. …

And it will not be possible to be and not to be the same thing, except in virtue of an ambiguity, just as if one whom we call 'man', and others were to call 'not-man'; but the point in question is not this, whether the same thing can at the same time be and not be a man in name, but whether it can be in fact. (Metaphysics 4.4, W.D. Ross (trans.), GBWW 8, 525–526).

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 not the statement a modern logician would call the law of excluded middle (P ∨ ¬P). The former claims that no statement is both true and false; the latter requires that no statement is neither true nor 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, italics added). In the context of Aristotle's traditional logic, this is a remarkably precise statement of the law of excluded middle, P ∨ ¬P. Traditional logic, also known as term logic, is a loose term for the logical tradition that originated with Aristotle and survived broadly unchanged until the advent of modern predicate logic in the late nineteenth century. ...

Leibniz

Its usual form, "Every judgment is either true or false" [footnote 9]..."(from Kolmogorov in van Heijenoort, p. 421)

footnote 9: "This is Leibniz's very simple formulation (see Nouveaux Essais, IV,2)...." (ibid p 421) Gottfried Leibniz Gottfried Wilhelm von Leibniz (July 1, 1646 in Leipzig - November 14, 1716 in Hannover) was a German philosopher, scientist, mathematician, diplomat, librarian, and lawyer of Sorb descent. ... Nouveaux Essais sur Lentendement humaine (New Essays on Human Understanding) was a chapter-by-chapter rebuttal by Gottfried Leibniz of the John Locke book Essays on Human Understanding. ...

Bertrand Russell and Principia Mathematica

Bertrand Russell asserts a distinction between the "law of excluded middle" and the "law of contradiction". In The Problems of Philosophy, he cites three "Laws of Thought" as more or less "self evident" or "a priori" in the sense of Aristotle: Bertrand Arthur William Russell, 3rd Earl Russell OM FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician and advocate for social reform. ... Introduction The Problems of Philosophy, one of Russells defining writings, is Bertrand Russels attempt to create a brief and accessible guide to the problems of philosophy. ...

1. The law of identity: 'Whatever is, is.'
2. The law of contradiction: 'Nothing can both be and not be.'
3. The law of excluded middle: 'Everything must either be or not be.'

These three laws are samples of self-evident logical principles... (p. 72)

It is correct, at least for bivalent logic — i.e. it can be seen with a Karnaugh map — that Russell's Law (2) removes "the middle" of the inclusive or 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.

About this issue (in admittedly very technical terms) Reichenbach observes:

The tertium non datur

29. (x)[f(x) ∨ ~f(x)]

is not exhaustive in its major terms and is therefore an inflated formula. This fact may perhaps explain why some people consider it unreasonable to write (29) with the inclusive 'or', and want to have it written with the sign of the exclusive 'or'

30. (x)[f(x) ⊻ ~f(x)] [the "⊻" signifies exclusive-or]

in which form it would be fully exhaustive and therefore nomological in the narrower sense. (Reichenbach, p. 376)

In line (30) the "(x)" means "for all" or "for every", thus an example of the expression would look like this: For the corresponding concept in combinational logic, see XOR gate. ...

• (For all Q): (P ⊻ ~P)
• (For all instances of "pig" seen and unseen): ("Pig does fly" or "Pig does not fly" but not both simultaneously)

What Aristotle and Russell believed is characteristic of traditional logic, but this view implicitly depends on a particular notion of truth in which every statement is either true or false.

A Formal definition from Principia Mathematica

Principia Mathematica (PM) defines the law of excluded middle formally: 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-1913. ...

• 2.1 : ~p ∨ p (PM p. 101)

Example: Either “this is red” is true or “this is not red” is true or both “this is red” and “this is not red” is true. (See below for more about how this is derived from the primitive axioms).

So just what is "truth" and "falsehood"? At the opening PM quickly announces some definitions:

Truth-values. The “truth-values” of a proposition is truth if it is true and falsehood if it is false* [*This phrase is due to Frege]...the truth-value of “p ∨ q” is truth if the truth-value of either p or q is truth, and is falsehood otherwise ... that of “~ p” is the opposite of that of p...” (p. 7-8)

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":

That is, when we judge (say) “this is red”, what occurs is a relation of three terms, the mind, and “this”, and red”. On the other hand, when we perceive “the redness of this”, there is a relation of two terms, namely the mind and the complex object “the redness of this” (p. 43-44).

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):

Let us give the name of ‘sense-data’ to the things that are immediately known in sensation: such things as colours, sounds, smells, hardnesses, roughnesses, and so on. We shall give the name ‘sensation’ to the experience of being immediately aware of these things… The colour itself is a sense-datum, not a sensation. (p. 12)

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 the excluded middle, formula *2.1 in Principia Mathematica, Whitehead and Russell derive some of the most powerful tools in the logician's argumentation toolkit.

*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 ) → (p → q) [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” (p. 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 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). In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach to mathematics as the constructive mental activity of humans. ... Luitzen Egbertus Jan Brouwer (February 27, 1881 - December 2, 1966), usually cited as L. E. J. Brouwer, was a Dutch mathematician, a graduate of the University of Amsterdam, who worked in topology, set theory, and measure theory and complex analysis. ...

This principle is commonly called "the principle of double negation" (cf PM p. 101-102). From the law of excluded middle *2.1 and *2.11 PM derives princple *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.)

Footnotes

1. ^ This well-known example of a non-constructive proof depending on the law of excluded middle can be found in many places, for example: Megill, Norm. Metamath: A Computer Language for Pure Mathematics, footnote on p. 17,[1] and Davis (2000) p. 220, footnote 2.

References

• Aquinas, Thomas, "Summa Theologica", Fathers of the English Dominican Province (trans.), Daniel J. Sullivan (ed.), vols. 19–20 in Robert Maynard Hutchins (ed.), Great Books of the Western World, Encyclopedia Britannica, Inc., Chicago, IL, 1952. Cited as GB 19–20.

• Aristotle, "Metaphysics", W.D. Ross (trans.), vol. 8 in Robert Maynard Hutchins (ed.), Great Books of the Western World, Encyclopedia Britannica, Inc., Chicago, IL, 1952. Cited as GB 8. 1st published, W.D. Ross (trans.), The Works of Aristotle, Oxford University Press, Oxford, UK.

• Dawson, J., Logical Dilemmas, The Life and Work of Kurt Gödel, A.K. Peters, Wellesley, MA, 1997.

• van Heijenoort, J., From Frege to Gödel, A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977.

* Luitzen Egbertus Jan Brouwer, 1923, On the significance of the principle of excluded middle in mathematics, espcecially in function theory [reprinted with commentary, p. 334, van Heijenoort]

* Andrei Nikolaevich Kolmogorov, 1925, On the princple of excluded middle, [reprinted with commentary, p. 414, van Heijenoort]

* Luitzen Egbertus Jan Brouwer, 1927, On the domains of definitions of functions,[reprinted with commentary, p. 446, van Heijenoort] Although not directly germane, in his (1923) Brouwer uses certain words defined in this paper.

* Luitzen Egbertus Jan Brouwer, 1927(2), Intuitionistic reflections on formalism,[reprinted with commentary, p. 490, van Heijenoort]

• Kneale, W. and Kneale, M., The Development of Logic, Oxford University Press, Oxford, UK, 1962. Reprinted with corrections, 1975.

• Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press 1962 (Second Edition of 1927, reprinted). Extremely difficult because of arcane symbolism, but a must-have for serious logicians.

• Bertrand Russell, The Problems of Philosophy, With a New Introduction by John Perry, Oxford University Press, New York, 1997 edition (first published 1912). Very easy to read: Russell was a wonderful writer.

• Bertrand Russell, The Art of Philosophizing and Other Essays, Littlefield, Adams & Co., Totowa, NJ, 1974 edition (first published 1968). Includes a wonderful essay on "The Art of drawing Inferences".

• Hans Reichenbach, Elements of Symbolic Logic, Dover, New York, 1947, 1975.

• Tom Mitchell, Machine Learning, WCB McGraw-Hill, 1997.

• Constance Reid, Hilbert, Copernicus: Springer-Verlag New York, Inc. 1996, first published 1969. Contains a wealth of biographical information, much derived from interviews.

• Bart Kosko, Fuzzy Thinking: The New Science of Fuzzy Logic, Hyperion, New York, 1993. Fuzzy thinking at its finest. But a good introduction to the concepts.

• David Hume, An Inquiry Concerning Human Understanding, reprinted in Great Books of the Western World Encyclopedia Britannica, Volume 35, 1952, p.449ff. This work was published by Hume in 1758 as his rewrite of his "juvenile" Treatise of Human Nature: Being An attempt to introduce the experimental method of Reasoning into Moral Subjects Vol. I, Of The Understanding first published 1739, reprinted as: David Hume, A Treatise of Human Nature, Penguin Classics, 1985. Also see: David Applebaum, The Vision of Hume, Vega, London, 2001: a reprint of a portion of An Inquiry starts on p. 94ff

Saint Thomas Aquinas (also Thomas of Aquin, or Aquino; c. ... The Summa Theologica (also widely known as the Summa Theologiae) is the most famous work of St. ... Robert Maynard Hutchins (January 17, 1899, Brooklyn, New York - May 17, 1977, Santa Barbara, California) was a philosopher. ... The Great Books Great Books of the Western World is a series of books originally published in the United States in 1952 by Encyclopædia Britannica Inc. ... Aristotle (Greek: AristotélÄ“s) (384 BC – 322 BC) was a Greek philosopher, a student of Plato and teacher of Alexander the Great. ... Metaphysics is one of the principal works of Aristotle and the first major work of the branch of philosophy with the same name. ... W. D. Ross is an Oxford philosopher whose ethics is a well-known form of deontology which sprung from a response to G.E. Moore. ... Robert Maynard Hutchins (January 17, 1899, Brooklyn, New York - May 17, 1977, Santa Barbara, California) was a philosopher. ... The Great Books Great Books of the Western World is a series of books originally published in the United States in 1952 by Encyclopædia Britannica Inc. ... Jean van Heijenoort (prounounced highenort) (July 23, 1912, Creil France - March 29, 1986, Mexico City) was a pioneer historian of mathematical logic. ... Brouwer is the last name of different people. ... Andrey Kolmogorov Andrey Nikolaevich Kolmogorov (Андре́й Никола́евич Колмого́ров) (kahl-mah-GAW-raff) (April 25, 1903 in Tambov - October 20, 1987 in Moscow) was a... Brouwer is the last name of different people. ... Brouwer is the last name of different people. ... Alfred North Whitehead, OM (February 15, 1861 Ramsgate, Kent, England – December 30, 1947 Cambridge, Massachusetts, USA) was an English-born mathematician who became a philosopher. ... Bertrand Arthur William Russell, 3rd Earl Russell OM FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician and advocate for social reform. ... Bertrand Arthur William Russell, 3rd Earl Russell OM FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician and advocate for social reform. ... Bertrand Arthur William Russell, 3rd Earl Russell OM FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician and advocate for social reform. ... Hans Reichenbach (September 26, 1891, Hamburg, – April 9, 1953, Los Angeles) was a leading philosopher of science, educator and proponent of logical positivism. ... Tom Mitchell is a balding pillock born in Gloucester in 1982. ... Constance Bowman Reid is the author of several biographies of mathematicians and popular books about mathematics. ... Bart Kosko is professor of electrical engineering at the University of Southern California (USC). ... see also: David Hume of Godscroft David Hume (April 26, 1711 – August 25, 1776)[1] was a Scottish philosopher, economist, and historian. ...

See also

• Laws of thought
• Logical graphs — Graphical syntax for propositional logic
• Peirce's law — Another way of turning intuition classical

There were four classic laws of thought recognised in European thought of the seventeenth and eighteenth century, which held sway also during nineteenth century (while subject to greater debate). ... A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. ... Peirces law in logic is named after the philosopher and logician Charles Sanders Peirce. ...

External links

• Stanford Encyclopedia of Philosophy, Contradiction.