Law Of The Excluded Middle

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.

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)".

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.

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 Rhetoric , the law of excluded middle is readily misapplied, leading to the Formal Fallacy of the excluded middle, also known as a False Dilemma .

EXAMPLES

For example, if ''P'' is the proposition:

Socrates is mortal.

then the law of excluded middle holds that the Logical Disjunction :

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. 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, {Link without Title} and Davis (2000) p. 220, footnote 2. We seek to prove that there exist two Irrational Number s

a

and

b

such that

:

a^b

is rational.

It is known that

\sqrt{2}

is irrational. Consider the number

:

\sqrt{2}^{\sqrt{2}}

.

Clearly (excluded middle) this number is either rational or irrational. If it is rational, we are done. If it is irrational, then let

:

a=\sqrt{2}^{\sqrt{2}}

and

b=\sqrt{2}

.

Then

:

a^b = {(\sqrt{2}^{\sqrt{2}})}^{\sqrt{2}} = \sqrt{2}^{(\sqrt{2}\cdot\sqrt{2})} = \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 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:
:"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 {Link without Title} 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.

One more counterexample to LEM may be noted: Gödel's First Incompleteness Theorem {Link without Title} provides a constructive example of a contingent proposition, which is neither deductively (syntactically) true nor false. An Intuitionist would point out that the negation of the "G-sentence" has only infinite (non-standard) models, and is thus another demonstration of the unsoundness of LEM with respect to infinite domains.

HISTORY

Aristotle

Aristotle wrote that ambiguity can arise from the use of ambiguous names, but cannot exist in the "facts" themselves:

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''.

Leibniz

Its usual form, "Every judgment is either true or false" 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)

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:

# Law Of Identity : 'Whatever is, is.'
# Law Of Noncontradiction : 'Nothing can both be and not be.'
# 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

(''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'

(''x'') ⊻ ~''f''(''x'') "⊻" 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 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:

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:

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''

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

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'' of the assertions is allowed by axiom 1.4

2.12 ''p'' → ~(~''p'') of double negation, part 1

2.13 ''p'' ∨ ~{~(~''p'')} together with ---2.12 used to derive ---2.14

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

2.15 (~''p'' → ''q'') → (~''q'' → ''p'') 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'') 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'') of the 'Principles of transposition'

2.18 (~''p'' → ''p'') → ''p'' “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).

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

2.12 and ---2.14, "double negation":

Intuitionist

L. E. J. Brouwer

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

THE LOGICISTS VERSUS THE INTUITIONISTS

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

...Kronecker insisted that there could be no existence without construction. For him, as for Paul Gordan elderly mathematician , Hilbert's proof of the finiteness of the basis of the invariant system was simply not mathematics. Hilbert, on the other hand, throughout his life was to insist that if one can prove that the attributes assigned to a concept will never lead to a contradiction, the mathematical existence of the concept is thereby established (Reid p. 34)

It was his {Link without Title} contention that nothing could be said to have mathematical existence unless it could actually be constructed with a finite number of positive integers (Reid p. 26)

The debate had a profound effect on Hilbert. Reid indicates that Hilbert's Second Problem (one of Hilbert's Problems from the Second International Conference in Paris in 1900) evolved from this debate (italics in the original):

In his second problem {Link without Title} had asked for a ''mathematical proof'' of the consistency of the axioms of the arithmetic of real numbers.

To show the significance of this problem, he added the following observation:

"If contradictory attributes be assigned to a concept, I say that ''mathematically the concept does not exist''"... (Reid p. 71)

Thus Hilbert was saying: "If ''p'' and ~''p'' are both shown to be true, then ''p'' does not exist" and he was thereby invoking the law of excluded middle cast into the form of the law of contradiction.

And finally constructivists ... restricted mathematics to the study of concrete operations on finite or potentially (but not actually) infinite structures; completed infinite totalities ... were rejected, as were indirect proof based on the Law of Excluded Middle. Most radical among the constructivists were the intuitionists, led by the erstwhile topologist L. E. J. Brouwer ... (Dawson p. 49)

The rancorous debate continued through the early 1900s into the 1920s — in 1927 Brouwer complained about "polemicizing against it {Link without Title} in sneering tones" (Brouwer in van Heijenoort, p. 492). But the debate had been fertile: it had resulted in ''PM'' (1910–1913), and ''PM'' 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 twentieth century:

Out of the rancor, and spawned in part by it, there arose several important logical developments...Zermelo’s axiomatization of set theory (1908a) ... that was followed two years later by the first volume of ''Principia Mathematica'' ... in which Russell and Whitehead showed how, via the theory of types, much of arithmetic could be developed by logicist means (Dawson p. 49)

Brouwer reduced the debate to the use of proofs designed from "negative" or "non-existence" versus "constructive" proof:

According to Brouwer, a statement that an object exists having a given property means that, and is only proved, when a method is known which in principle at least will enable such an object to be found or constructed...

Hilbert naturally disagreed.

'...pure existence proofs have been the most important landmarks in the historical development of our science," he maintained. (Reid p. 155)

Brouwer ... refused to accept the Logical Principle of the Excluded Middle... His argument was the following:

"Suppose that A is the statement 'There exists a member of the set ''S'' having the property ''P''.' If the set is finite, it is possible — in principle — to examine each member of ''S'' and determine whether there is a member of ''S'' with the property ''P'' or that every member of ''S'' lacks the property ''P''. For finite sets, therefore, Brouwer accepted the Principle of the Excluded Middle as valid. He refused to accept it for infinite sets because if the set ''S'' is infinite, we cannot — even in principle — examine each member of the set. If, during the course of our examination, we find a member of the set with the property ''P'', the first alternative is substantiated; but if we never find such a member, the second alternative is still not substantiated -- perhaps we have just not persisted long enough!

Since mathematical theorems are often proved by establishing that the negation would involve us in a contradiction, this third possibility which Brouwer suggested would throw into question many of the mathematical statements currently accepted.

'Taking the Principle of the Excluded Middle from the mathematician," Hilbert said, 'is the same as ... prohibiting the boxer the use of his fists.'

"The possible loss did not seem to bother Weyl... Brouwer's program was the coming thing, he insisted to his friends in Zürich." (Reid, p. 149)

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" (Dawson, p. 157))

Gödel's approach to the law of excluded middle was to assert that objections against "the use of 'impredicative definitions'" "carried more weight" than "the law of excluded middle and related theorems of the propositional calculus'" (Dawson p. 156). 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 ~ (∀A: (A ∨ ~A)) (despite the inconsistency of the assumption ∃ A: ~ (A ∨ ~A)..." (Dawson, p. 157)

The debate seemed to weaken: mathematicians, logicians and engineers continue to use the law of excluded middle (and double negation) in their daily work.

Intuitionist Definitions of 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 (i.e. what the law really means). Their difficulties with the law emerges: that they do not want to accept as true, implications drawn from that which is unverifiable (untestable, unknowable) or from the impossible or the false. (All quotes are from van Heijenoort, boldface added).

Brouwer offers his definition of "principle of excluded middle"; we see here also the issue of "testability":

On the basis of the testability just mentioned, there hold, for properties conceived within a specific finite main system, the 'principle of excluded middle', that is, the principle that for every system every property is either correct {Link without Title} or impossible, and in particular the principle of the reciprocity of the complementary species, that is, the principle that for every system the correctness of a property follows from the impossibility of the impossibility of this property. (335)

Kolmogorov's definition cites Hilbert's two Axioms of Negation

''A'' → (~''A'' → ''B'')

(''A'' → ''B'') → { (~''A'' → ''B'') → ''B''}

Hilbert's first axiom of negation, "Anything follows from the false", made its appearance only with the rise of symbolic logic, as did, incidentally, the first axiom of implication.... while... the axiom under consideration 5 asserts something about the consequences of something impossible: we have to accept ''B'' if the true judgment ''A'' is regarded as false...

Hilbert's second axiom of negation expresses the principle of excluded middle. The principle is expressed here in the form in which is it used for derivations: if ''B'' follows from ''A'' as well as from ~''A'', then ''B'' is true. Its usual form, "Every judgment is either true or false" 9 is equivalent to that given above 10 "

Clearly from the first interpretation of negation, that is, the interdiction from regarding the judgment as true, it is impossible to obtain the certitude that the principle of excluded middle is true... Brouwer showed that in the case of such transfinite judgments the principle of excluded middle cannot...be considered obvious

footnote 9: "This is Leibniz's very simple formulation (see ''Nouveaux Essais'', IV,2). The formulation "''A'' is either ''B'' or not-''B''" has nothing to do with the logic of judgments.

footnote 10: "Symbolically the second form is expessed thus

A

where ∨ means "or". The equivalence of the two forms is easily proved... (p. 421)

-->

FOOTNOTES

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'' with commentary, p. 334, van Heijenoort

Andrei Nikolaevich Kolmogorov , 1925, ''On the princple of excluded middle'', with commentary, p. 414, van Heijenoort

Luitzen Egbertus Jan Brouwer , 1927, ''On the domains of definitions of functions'', 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'', 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.

, ''The Vision of Hume'', Vega, London, 2001: a reprint of a portion of ''An Inquiry'' starts on p. 94ff

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT LAW OF EXCLUDED MIDDLE

	laws of thought

	logic

Information About

Law Of The Excluded Middle