# GetWiki

*law of excluded middle*

ARTICLE SUBJECTS

being →

database →

ethics →

fiction →

history →

internet →

language →

linux →

logic →

method →

news →

policy →

purpose →

religion →

science →

software →

truth →

unix →

wiki →

ARTICLE TYPES

essay →

feed →

help →

system →

wiki →

ARTICLE ORIGINS

critical →

forked →

imported →

original →

law of excluded middle

[ temporary import ]

**please note:**

- the content below is remote from Wikipedia

- it has been imported raw for GetWiki

**law of excluded middle**(or the

**principle of excluded middle**) states that for any proposition, either that proposition is true or its negation is true. It is the third of the three classic laws of thought.The law is also known as the

**law**(or

**principle**)

**of the excluded third**, in Latin

**. Another Latin designation for this law is**

*principium tertii exclusi***: "no third [possibility] is given".The earliest known formulation is in Aristotle's discussion of the principle of non-contradiction, first proposed in**

*tertium non datur**On Interpretation,*Geach p. 74 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.

*On Interpretation*, c. 9 He also states it as a principle in the

*Metaphysics*book 3, saying that it is necessary in every case to affirm or deny,

*Metaphysics 2, 996b 26â€“30 and that it is impossible that there should be anything between the two parts of a contradiction.*Metaphysics 7, 1011b 26â€“27 The principle was stated as a theorem of propositional logic by Russell and Whitehead in

*Principia Mathematica*as:mathbf{*2cdot11}. vdash . p vee thicksim p.{{citation|author=Alfred North Whitehead, Bertrand Russell|title=Principia Mathematica|publisher=Cambridge|year=1910|pages=105 |url=http://name.umdl.umich.edu/aat3201.0001.001}}The principle should not be confused with the semantical principle of bivalence, which states that every proposition is either true or false.

## Classic laws of thought

The principle of excluded middle, along with its complement, the law of non-contradiction (the second of the three classic laws of thought), are correlates of the law of identity (the first of these laws).## 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**. 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*+1th*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.

## Examples

For example, if*P*is the proposition:

*Socrates is mortal.*

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

*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.This well-known example of a non-constructive proof depending on the law of excluded middle can be found in many places, for example: WEB, Norman, Megill, Metamath: A Computer Language for Pure Mathematics'', footnote on p. 17,,weblink and Davis 2000:220, footnote 2. We seek to prove that there exist two irrational numbers a and b such that

a^b is rational.

It is known that sqrt{2} is irrational (see proof). Consider the number
sqrt{2}^{sqrt{2}}.

Clearly (excluded middle) this number is either rational or irrational. If it is rational, the proof is complete, and
a=sqrt{2} and b=sqrt{2}.

But if sqrt{2}^{sqrt{2}} is irrational, then let
a=sqrt{2}^{sqrt{2}} and b=sqrt{2}.

Then
a^b = left(sqrt{2}^{sqrt{2}}right)^{sqrt{2}} = sqrt{2}^{left(sqrt{2}cdotsqrt{2}right)} = sqrt{2}^2 = 2,

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.### The law in non-constructive proofs over the infinite

The above proof is an example of a*non-constructive*proof disallowed by intuitionists:

is irrational but there is no known easy proof of that fact.) (Davis 2000:220)}} (Constructive proofs of the specific example above are not hard to produce; for example a=sqrt{2} and b=log_2 9 are both easily shown to be irrational, and a^b=3; a proof allowed 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." (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, 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" (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 and Intuitionism.*

## History

### Aristotle

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 asserts a distinction between the "law of excluded middle" and the "law of noncontradiction". 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:

1. Law of identity: "Whatever is, is."
2. Law of noncontradiction: "Nothing can both be and not be."
3.

**Law of excluded middle**: "Everything must either be or not be."
These three laws are samples of self-evident logical principles... (p. 72)

*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*)], where the symbol "âŠ•" signifies exclusive-orThe original symbol as used by Reichenbach is an upside down V, nowadays used for AND. The AND for Reichenbach is the same as that used in Principia Mathematica -- a "dot" cf p. 27 where he shows a truth table where he defines "a.b". Reichenbach defines the exclusive-or on p. 35 as "the negation of the equivalence". One sign used nowadays is a circle with a + in it, i.e. âŠ• (because in binary, a âŠ• b yields modulo-2 addition -- addition without carry). Other signs are â‰¢ (not identical to), or â‰ (not equal to). in which form it would be fully exhaustive and therefore nomological in the narrower sense. (Reichenbach, p. 376)*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*(

*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,*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 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

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.BOOK, Clark, Keith, Logic and Data Bases, Springer-Verlag, 1978, 293â€“322 (Negation as a failure),weblink 10.1007/978-1-4684-3384-5_11, 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."Proof and Knowledge in Mathematics" by Michael Detlefsen

### In Mathematical logic

In modern mathematical logic, the excluded middle has been shown 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",Graham Priest, "Paradoxical Truth",*The New York Times,*November 28, 2010. the statement "this statement is false", which can itself be neither true nor false. 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 paradoxKevin C. Klement, IEP, par-russ, Russell's Paradox, Graham Priest, "The Logical Paradoxes and the Law of Excluded Middle",

*The Philosophical Quarterly*, Vol. 33, No. 131, Apr., 1983, pp. 160-165. DOI: 10.2307/2218742. (abstract at JSTOR._: does the set contain, as one of its elements, itself? GÃ¶del's incompleteness theorem shows that contradictions of this nature are inherent in mathematical systems.

## See also

- Brouwerâ€“Hilbert controversy: an account on the formalist-intuitionist divide around the Law of the excluded middle
- Consequentia mirabilis
- Diaconescu's theorem
- Intuitionistic logic
- Law of bivalence
- Law of excluded fourth
- Law of excluded middle is untrue in many-valued logics such as ternary logic and fuzzy logic
- Laws of thought
- Liar paradox
- Limited principle of omniscience
- Logical graphs: a graphical syntax for propositional logic
- Peirce's law: another way of turning intuition classical
- Logical determinism: the application excluded middle to modal propositions
- Non-affirming negation in the Prasangika school of Buddhism, another system in which the law of excluded middle is untrue

## Footnotes

{{reflist}}## 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*, EncyclopÃ¦dia 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*, EncyclopÃ¦dia Britannica, Inc., Chicago, IL, 1952. Cited as GB 8. 1st published, W.D. Ross (trans.),*The Works of Aristotle*, Oxford University Press, Oxford, UK. - Martin Davis 2000, ''Engines of Logic: Mathematicians and the Origin of the Computer", W. W. Norton & Company, NY, {{ISBN|0-393-32229-7}} pbk.
- 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, especially in function theory*[reprinted with commentary, p. 334, van Heijenoort] - Andrei Nikolaevich Kolmogorov, 1925,
*On the principle 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] - Stephen C. Kleene 1952 original printing, 1971 6th printing with corrections, 10th printing 1991,
*Introduction to Metamathematics*, North-Holland Publishing Company, Amsterdam NY, {{ISBN|0-7204-2103-9}}. - 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,
*An Inquiry Into Meaning and Truth*. The William James Lectures for 1940 Delivered at Harvard University. - 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 EncyclopÃ¦dia Britannica, Volume 35, 1952, p. 449 ff. 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. 94 ff

## External links

{{Classical logic}}{{authority control}}**- content above as imported from Wikipedia**

- "

- time: 10:32am EST - Mon, Dec 10 2018

- "

__law of excluded middle__" does not exist on GetWiki (yet)- time: 10:32am EST - Mon, Dec 10 2018

[ this remote article is provided by Wikipedia ]

LATEST EDITS [ see all ]

GETWIKI 09 MAY 2016

GETWIKI 18 OCT 2015

GETWIKI 20 AUG 2014

GETWIKI 19 AUG 2014

GETWIKI 18 AUG 2014

© 2018 M.R.M. PARROTT | ALL RIGHTS RESERVED