| Law Of Excluded Middle |
Article Index for Law Of |
Website Links For Law |
Information AboutLaw Of Excluded Middle |
| CATEGORIES ABOUT LAW OF EXCLUDED MIDDLE | |
| laws of thought | |
| logic | |
|
In as "''A'' is ''B'' or ''A'' is not ''B''". It is a basic theorem of Propositional Logic , where it is written P ∨ ¬ P; that is, "P or not P". For example, if P is : Joe is bald then the inclusive Disjunction : Joe is bald, or Joe is not bald is true. This is not quite the same as the Principle Of Bivalence , which states that P must be either true or false. It also differs from the Law Of Noncontradiction , which states that ¬(P ∧ ¬P) is true. The law of excluded middle only says that the total (P ∨ ¬P) is true, but does not comment on what truth values P itself may take. In a bivalent logic, P and ¬P will have opposite truth-values (that is, one is true and one is false), and the law of excluded middle necessarily follows. However, the same cannot be said about non-bivalent logics, or Many-valued Logic s. Certain systems of logic may reject bivalence by allowing more than two truth values (e.g.; true, false, and indeterminate; true, false, neither, both), but accept the law of excluded middle. In such logics, (P ∨ ¬P) may be true while P and ¬P are not assigned opposite truth-values like true and false, respectively. Some logics do not accept the law of excluded middle, most notably Intuitionistic Logic . The article " Bivalence And Related Laws " discusses this issue in greater detail. The law of excluded middle can be misapplied, leading to the Logical Fallacy of the excluded middle, also known as a False Dilemma . WIDE-RANGING ESSAY ON THE LAW OF EXCLUDED MIDDLE Historical background 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, Book IV, Chapter 4, translated by W.D Ross, GBWW volume 8 p. 525-6) Bertrand Russell echoed this sentiment. He cites three "Laws of Thought" as more or less "self evident" or "a priori" in the sense of Aristotle: : (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. Law (2) removes "the middle" of the inclusive-OR used in law (3). For more about this, see below.) 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. Examples of logical systems that contradict this idea include Ternary Logic , in which statements may be true, false, or unknown; Fuzzy Logic , in which statements may be true, false, or somewhere in between; and Intuitionistic Logic , in which the notion of truth is despensed with entirely, and ''provability'' considered in its place. A precise definition, and historical importance ''Principia Mathematica'' (PM) defines the “law of excluded middle” formally:
: 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:
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). These definitions derived directly from Bertrand Russell's philosophy. At the beginning of the 1900's a debate raged between the so-called “Logicists” (e.g. Russell, Frege) and the “constructivists” especially over topics including strict finitism, intuitionism, and predicativism (Dawson p. 49 in footnote 5). Russell presented 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''). This is of interest here because the debate between the “logicists” and the so-called “constructivists” resulted in PM, and PM gave the precise definition the "Law of Excluded Middle", and all this provided some of the tools required for Gödel's undecidability proof: : 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 ... : 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) Dawson observes that Brouwer "...campaigned against the use of the Law of Excluded Middle in proofs" (p. 321). (See next section for more about Brouwer.) About this issue (in admittedly very technical terms) Reichenbach observes: : The tertium non datur :: (x) ~f(x) (29) : 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)^~f(x)] (30) [the "^" signifies Exclusive-or ] : in which form it would be fully exhaustive and therefore nomological in the narrower sense. (Reichenbach, p. 376)
:: Either “pigs fly” is true or “pigs don’t fly” or both “pigs fly” and “pigs don’t fly” are true assertions. PM derives “the law” from Theorem 2.08 ( p -> p) and “primitive idea” 1.08 ( p -> q ) =def ( ~p V q). First we substitute p for q in 1.08 to get p -> p. Then we use definition so that ~p V p. QED]
:: Actually the stronger case of 2.18 (~p -> p) = p (equals, not implies) is true. Let ~p = q. Then q -> p =def ~q V p. Substitute ~p for q: ~(~p) V p. This is equivalent to p V p which is p. QED Kronecker 's, and Brouwer 's objection -- This is a work in progress -- > Useful discussion because it high-lights a deep mathematical and philosophic problem behind what it means to "know", also helps elucidate what the "law" implies (i.e. what the law really means) In late 1800's through the 1930's a bitter, persistent debate raged between Hilbert + his followers versus Weyl + Brouwer. Brouwer's philosophy-- called Intuitionism -- started in earnest with Kronecker. Kronecker's ideas were intensely disliked by Hilbert: : "...Kronecker insisted that there could be no existence without construction. For him, as for 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 his "Second Problem" (cf Hilbert's Problems from the Second International Conference in Paris in 1900) evolved from this debate 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" exist together, then "p" does not exist", and he was thereby invoking The Law of Excluded Middle. > Godel was to later point out reference here that problem came in two parts, the first less serious than the second. The second resides/evolves from, when designing proofs, the use of the universal quantifier "for all" versus the existential "there exists at least one". Issue is described well in Reid's book here . : "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) A detour: an example of the intuitionist objection The section above stated that the intuitionists believe that only if we can investigate ''all'' instances of a finite set { a, b, c, d, e, f, g, ... z } can we assert a truth or its negation. But when we evoke NOT-(FOR ALL x) where "ALL x" covers all cases known and unknown, we can "never be sure", : e.g. Not true that "Pigs fly" can be written: :: ~((Ax)Ey Ez:(IF x is a z THEN x & y)) ["A" here the universal quantifier "For all...", "E" is the existential quantifier "There exists at least one instance of..." : Thus e.g. IT IS NOT TRUE IN ANY INSTANCE WHATEVER THAT: :: "For all objects x of the entire universe known and all universes unknown, given that at least one prototype (concept, description, attribute, sensation) 'pig' exists and at least one prototype (concept, description, attribute, sensation) 'fly' exists: IF object x is a member of the set (class) of objects 'pig' THEN object 'pig' possesses attribute 'fly'." Here's an example using finite logic: Let's examine n objects (say n=142), O1, O2, O3, up to On=O142 and decide if they are flying pigs. Let p1, p2, p3,...pi up to p142 stand for "object Oi is a pig that flies" (e.g. we examine O42 and decide whether or not O42 is a flying pig, and then we assign p42 a "truth value" of 1 if O42 is a flying pig and 0 if it is not). Let "P" stand for the proposition that "Some of these objects are flying pigs". And let "Q" be the question P V ~P: "Some are flying pigs", or not-"some are flying pigs" The first proposition P we write as "the disjunction" (fancy word for logical OR) of all 142 of our investigations: P = (p1 V p2 V p3 ... V p142), e.g. "Either p1 or p2 or p3 or ... pn indicates a flying pig". And we know that this statement is either "true" or "false". The second proposition ~P starts out simply as the negation of P, but then we do some fancy footwork to convert it into a conjunction (fancy word for logical AND). Thus : Q = P V ~P = (p1 V p2 V p3 ... V p142) V ~(p1 V p2 V p3 V p4 ... V p142) :: The next step is the fancy footwork: it comes about from the definition in PM of logical AND i.e. (a & b) = ~(~a V ~b), and the theorem a = ~(~a). : Q = P V ~P = (p1 V p2 V p3 V ... V p142) V (~p1 & ~p2 & ~p3 & ~p4 & ... ~p142) Now suppose that we want to determine the truth-value of our question Q. We examine our objects-as-possible-flying-pigs O1 to O142 one after another. We are done as soon as we find a flying pig: e.g. if p1 is not a flying pig = 0 (false), but if p2 is a flying pig = 1 (true), then we're done: : Q = P V ~P = (0 V 1 V doesn't matter) V (doesn't matter) Thus even a single instance of a flying pig answers the question: : (0 V 1 V any truth-values whatever) = 1 But suppose we aren't having much luck, and we have to go "all the way to the end", i.e. examine all 142 objects. When we hit #141 we have: : Q = P V ~P = (0 V 0 V 0 V ... V 0 V p142) V (~0 & ~0 & ~0 V ... & ~0 & ~p142) AS we approach object O142 there's only two possible otucomes: either (1) O142 is a flying pig and p142=1 or (2) O142 is not a flying pig and p142=0: : Case 1-- p142 is a flying pig: :: Q = (0 V 0 V 0 ... 0 V 1) V (~0 & ~0 & ~0 ... & ~0 & ~1) :: Q = (0 V 0 V 0 ... 0 V 1) V (1 & 1 & 1 ... & 1 & 0) :: Q = (P=1 V ~P=0) = (1) V (0) = 1 :: It's true: Pigs fly! : Case 2-- p142 is not a flying pig: :: Q = (0 V 0 V 0 ... 0 V 0) V (~0 & ~0 & ~0 ... & ~0 & ~0) :: Q = (0 V 0 V 0 ... 0 V 1) V (1 & 1 & 1 ... & 1 & 1) :: Q = (P=0 V ~P=1) = (0) V (1) = 1 :: It's true: Pigs don't fly! accurately we now know that: ''Some'' pigs don't fly. Observe, however, that to reach our understanding that ~P is the true case (not a single instance of flying pigs in our 142 objects), we had to ''go all the way to the end''. Every pig-object had to be examined-- and this is because of the logical AND in the construction. This is okay when we're dealing with finite numbers of objects, but what happens when we have infinite numbers of objects? How can we be sure there isn't a lone instance of a flying pig somewhere e.g. a freak hiding under a rock on planet Org in sun-system R2D2, galaxy C3PO, universe Chewbacca? We can't be sure. One thus would argue that we have to rely on Induction -- the probability that after examining 1.32 x 10^132 pig-like objects and not finding a single flying pig, that there really and truly aren't any. (cf Russell 2) -- work in progress here -- :: This sub-section will attempt to give meaning to Reichenbach's difficult statement above re the possible use of "exclusive-OR" for tertium non datur. Reichenbach has given the following meaning with regard to so-called ''nomological'' formulas. This is important: it touches on the problem of Natural Law if we are using tertium non datur in the formation of natural laws, and something might be wrong with tertium non datur. Reichenbach attempts to treat this in the last chapter of his book: ::: "The term 'nomological', derived from the Greek word 'nomos' meaning 'law', is chosen to express the idea that the formulas are either laws of nature or logical laws. Analytic nomological formulas are tautological formulas always true: P V ~P, the tertium non datur, more below , or logical laws; synthetic nomological formulas are laws of nature. The term 'nomological' is therefore a generalization of term 'tautological' (Reichenbach, p.)(see Natural Law for more) In our example above, "Q = P V ~P" is called a "tautology" because it is always true-- either (1) some of the objects are flying pigs or (2) not true that some of the objects are flying pigs or (3) both statements are true. In fact Reichenbach ''defines'' "tautology" as the tertium non datur P V ~P: : "All tautologies have the same shortest disjunctive normal form namely V ~P (cf Reichenbach p 52). An explanation of "disjunctive normal form" will follow shortly ("disjunction" is the fancy name for logical inclusive OR) Here's Reichenbach again: : "A true statement is ''exhaustive in its major terms'' if none of its residual statements in major terms is true." (p. 362) A "residual statement" is what is left if we cancel/remove one or more terms of our expression, e.g. if we start with the tertium non datur Q = "P V ~P" we can cancel "P" or "~P". The residual statement would then be "~P" if we cancel "P", and vice versa. : "An inflated form we shall understand a one-scope statement that is not exhaustive in its major terms ..." (p. 365) What is a "term"? Suppose we have two "variables" (sentences identifying sensations, for example sentence "a" is "This is a pig" and sentence "b" is "this is flying". We can form the possible combinations of the "truths" of our sentences (here abbreviated) from the two collections: {"not-pig", "pig"}, and {"not-flying, "flying"}. (Notice that we have "bifurcated" the world with the variable and its negation.) Now what happens when we look for these two "qualities" simultaneously in an object? To find out, first we create what known as "the power set" of the two collections by "multiplying" them together. This yields all possible combinations: 2 x 2 = 4 ANDs to describe all the (minimal) logical possibilities of two "variables" (these minimal &-constructions are sometimes called "minterms"): : { (not-pig & not-flying), (not-pig & flying), (pig & not-flying), (pig & flying) } Secondly, we pick out the minterms we want use to construct our logical formula. Lastly, we logically OR our selected terms together. For example, the basic formulas of 2-variable logic are 16 in number; we give 10 useful ones here (The rest are, in a sense, the "converses" of these): : pig V flying = (not-pig & flying) V (pig & not-flying) V (pig & flying) : pig ^ flying = (not-pig & flying) V (pig & not-flying) ;the exclusive-or : pig & flying = (pig & flying) : not-pig = (not-pig & not-flying) V (not-pig & flying) : not-flying = (not-pig & not-flying) V (pig & not-flying) : pig = (pig & not-flying) V (pig & flying) : flying = (not-pig & flying) V (pig & flying) : pig -> flying =def (not-pig) V flying) = (not-pig & not-flying) V (not-pig & flying) V (pig & flying) : flying -> pig =def (not-flying V pig) = (not-pig & not-flying) V (pig & not-flying) V (pig & flying) : always true = (not-pig & not-flying) V (not-pig & flying)V (pig & not-flying) V (pig & flying) ;the tautology When we compare the first two formulas for pig V flying versus pig ^ flying, we see "the third term", the term (pig & flying). Residual elements: In the expression pig V flying, we can pluck out any one of the three terms and see if the expression is still true: : Remove first term (not-pig & flying): :: pig = (pig & not-flying) V (pig & flying) : Remove second term (pig & not-flying): :: flying = (not-pig & flying) V (pig & flying) : Remove the third term (pig and flying): :: pig^flying = (not-pig & flying) V (pig & not-flying) In this last, third case we see that we are left with an expression that still "works", that is, it classifies an object into "a pig" or "flying" is one that correctly "partitions" our objects in the sense that we mean it do. So we could substitute it for logical OR and still retain the correctness of our expression. Reichenbach invokes Russell (p. 357) and David Hume in particular : "We agree with Hume that physical necessity is translatable into statements about repeated occurrences, including the prediction that the same combination will occur in the future, without exception. 'Physcially necessary' is expressible in terms of 'always'." (p. 356) Back to the debate Hilbert believed that, if accepted, the Intuitionist would eliminate the mathematics of Cantor et. al. with regard to "the infinite" and "trans-finite", have profound effects on set theory, etc. > Godel's PhD thesis invoked the Law. An important connection because after he finished his thesis he proceeded on to his "First Incompleteness Theorem" that (arguably) answered Hilbert's Second Question (some argue: in the negative): : "In any case, Godel was certainly well acquainted with the tenets of intuitionism. Toward the end of his introductory remarks from the published paper"-- note added he defended the "essential use" he had made of the Law of Excluded Middle, arguing that "from the intuitionistic point of view, the entire problem a completeness proof would be a different one"(Dawson p. 54-56] > The question reduced to the use of proofs designed from 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) > Late in his professional life 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)) > Turing's second proof (that no method (algorithm, machine) exists that can determine in general whether or not a given Turing machine M will print a particular symbol e.g. 0) in particular uses the universal quantifier and an "existence" (reductio ad absurdum) proof. The philosophic issues that still surround "the infinite" (a Turing machine has an infinite tape, but a finite "program") are not trivial. Paradoxes |
|
|