Talk:Law of excluded middle/Archive 1

From Wikipedia, the free encyclopedia

Archive This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.
Archive 1
| Archive 2 →


Contents

Derivation

How do we feel about derivations in articles? I'd quite like to add the following:

The law can be proved in propositional calculus thus:

1    1     -(P v -P)              A (for RAA)
2    2     P                      A (for RAA)
2    3     P v -P                 v-I 2
1,2  4    (P v -P) & -(P v -P)    &-I 1,3
1    5    -P                      RAA 2,4
1    6    P v -P                  v-I 5
1    7    (P v -P) & -(P v -P)    &-I 1,6
     8    --(P v -P)              RAA 1,7
     9    P v -P                  DNE 8

The proof is quite sneaky - first it is assumed that (P or not-P), the law of excluded middle, is false. It is then shown that P would contradict this, so it must be the case that not-P. But not-P also contradicts the first line. So the law of excluded middle is thus proven by reductio ad absurdum.

But it's quite technical... Evercat 19:49 30 Jun 2003 (UTC)


If you can add comments for each step which explain what is being done, I'd say go for it. -- Tarquin 19:59 30 Jun 2003 (UTC)


Your argument strikes me as circular, in that step 5 "begs the question". You show that P leads to a contradiction (hence is false), and so assume since P is false then -P must be true. This is exactly what we were trying to prove from the start. Apparently your definition of RAA already entails excluding the middle. --Jdz 18:52, 27 December 2005 (UTC)

Our basic assumption is that what we're trying to prove is false, on this basis we pose the assumption that p is true, and derived a contradition to our basic assumption, thus we are forced to conclude ~p is true. Suppose then we are ASSUMING FURTHER that ~p is true, independent of our previous derivation, then it can be shown that p v ~p is true by disjunction intro, which again, is contradictory to our original basic assumption, thus we are forced to conclude ~~p. We've just shown by reductio that ~p and ~~p are both true given our basic assumption, thus we have derived a contradiction from our basic assumption, thus we are forced to conclude that what we're trying to prove is true.--Macbug 07:37, 7 February 2006 (UTC)
Yes, but how do you justify using reductio ad absurdum? That technique is itself a consequence of the law of excluded middle! So using it to prove the law of excluded middle seems circular. (Disclaimer: I am not a logician.) Jorend 14:20, 3 April 2006 (UTC)
(later) I stand corrected: I am used to Metamath, in which reductio is a theorem. Apparently that is not the way logic is usually constructed; the example logic at propositional logic takes reductio as a built-in rule of inference. So the proof above is valid. I wonder if there's a shorter proof that works in the example logic. (I added a proof to the page, but it follows Metamath's logic. Oops.) --Jorend 18:08, 6 April 2006 (UTC)

Precise definition

Another note: are we sure that the law means either P is true or -P is true? See Bivalence and related laws (the bit on the sea battle) for why you might want to deny that, whilst maintaining that (P or -P) is true. Isn't the latter the correct definition of the law of excluded middle? Evercat 00:51 1 Jul 2003 (UTC)

I may be wrong here, but I think the logical "or" does not mean "either." Specifically, in my experience with logic, "X or Y" means "X, or Y, or both", not "either X or Y, but not both." The latter would be the exclusive-or. I don't know which one applies here; probably exclusive-or. Anyway, as I understand the law of excluded middle, it simply means that something has to be either true or false; it can't be both, or partially-true, or whatever. -- Wapcaplet 01:19 1 Jul 2003 (UTC)

Well, yes, I know that or means inclusive. It doesn't affect the idea that excluded middle might hold even when bivalence does not.

Alas, I should note that I'm confused about this too - it's possible I'm wrong... but it's usually said that there is some distinction between bivalence and excluded middle. If so, you can't make both the definitions the same. :-) Evercat 01:22 1 Jul 2003 (UTC)

Ok, after a bit of reading of the Bivalence article, I think I get it. Bivalence says "it can be true or false, but not both at once." Excluded middle just says "it can only be true or false, or maybe both, but it can't be something else." -- Wapcaplet 01:27 1 Jul 2003 (UTC)

(Hm, yeah, I suppose there's no way for them both to be true, without creating a logical contradiction... but it does not appear that the law of excluded middle itself prohibits (P == not P) ) -- Wapcaplet 01:30 1 Jul 2003 (UTC)

I guess the simplest way I can put it is that, as I understand it, excluded middle says that the formula (or proposition, whatever)

(P or -P)

is true. As I understand it, it makes no claim about what truth values are available to the proposition P itself... Bivalence does that (or, in multi-valued logics, doesn't exist)

Assuming my understanding isn't fatally flawed, which it may be. :-) Evercat 01:31 1 Jul 2003 (UTC)

Well, I've reverted my changes. Obviously I am in no condition to edit this article :) -- Wapcaplet 01:32 1 Jul 2003 (UTC)

Well, I'm not sure I am. :-) Any logic experts? Evercat 01:33 1 Jul 2003 (UTC)

The seeming violations of the law of the excluded middle are more linguistic than logical. Many words (not only in English)have imprecise meaning, and such a word as bald can have different meanings due to subtle gradations or changing circumstances. In the most rigid sense, bald means lacking hair altogether, but it can refer to someone with complete or partial loss of head hair or to someone whose head has been shaved. Is one bald if one has no head hair yet wears a wig at the time? One could be medically bald yet sartorially rich in hair.

We use words as a sort of clothing for logical reality because formal logic, designed for reliability and simplicity, fails badly for expressing the subtle gradations of reality and consciousness, let alone the cleverness of some human efforts to deceive themselves or others. Many words have differing and at times contradictory meanings, Thus the word good can refer simultaneously to moral virtue and to technical competence. If one says "Jack is a good carpenter" then one could conceivably state that he is a good person who happens to be a carpenter by trade without reference to his performance at shaping and assembling wood products, or that one can say that Jack is a competent shaper and assembler of wood products irrespective of irrespective of his behavior on other matters. A logical fallacy arises due to differnt meanings of the same word should one assume that technical competence implies moral goodness. Jack may have fashioned a wooden object well suited as a device for murder or torture with knowledge of its purpose, but doing so contradicts moral goodness because any deliberate contribution to the misery of others contradicts most concepts of goodness of personal conduct.

Such a subject as mathematics is structured to require rigid categories through rigid definitions. There can be no integer between five and six, and the fact that the square root of a positive integer must be an integer should it be rational depends upon equality of any two numbers requires that those two numbers have the same properties. The law of the excluded middle implies that the square root of 2 cannot have the qualities of an integer and thus must be something other than a rational number. Human experience is more subtle than is mathematics because of ambiguities. It allows ambiguities and even oxymora (example: the reference to the 19th-century politician Stephen Douglas as the "Little Giant") to express such realities as a great orator irrespective of his short stature. Such an expression as "the integer between five and six" or "the rational square root of two" is meaningless, and any effort to assign a word to such a concept is absurd, and worthless in mathematics.--66.231.41.57 11:39, 2 February 2006 (UTC)

"Law of radical middle"?

Removing this text:

Outside the realm of formal logic, the law of the excluded middle has inspired other attempts to reconcile competing claims. For example, a movement calling itself the Radical Center has proposed a Law of radical middle, which holds that pairs of apparently inconsistent philosophical claims are usually both true when viewed from an appropriate perspective.

Looking closely at the radical middle page, there doesn't seem to be much connection between it and the excluded middle law except for a self-promoting choice of name.

Populus 21:15, 10 Sep 2003 (UTC)

My apologies to Populus; I'm somewhat new at this. I'm moved the Radical centrism stuff to the political pages, since that part is more formalized, while I continue to refine the Radical Middle part.
Part of the confusion is that I'm still trying to determine whether the Law of excluded middle is in fact a disjunction or an exclusive disjunction, so I know whether Radical Middle thought disagrees with it.
It's the Inclusive OR (i.e. similar to "disjunction"). See the "Exclusive OR" discussion and the footnote.wvbailey01:22, 22 February 2006 (UTC)

Some "editor" ripped out this footnote so I'll add it back here for the time being:

Footnote|Exclusive-or: The definition of "p exclusive-or q" ( p XOR q, p^q), excludes the third term (the "middle") of the inclusive OR i.e. "or both p is true and q is true"; as shown below where p=1 and q=1 yields p^q=0:

p q ^
0 0 0
0 1 1
1 0 1
1 1 0

Engineers know this as the "half-adder" -- it adds in a binary (finite) field, i.e. 1+1=0 without a "carry". We can derive "carry" from "p AND q", i.e. when both are 1, the carry results. "^" is also equivalent to "not-equals", as in "p is not equal to q".

Exclusive-or "^" (XOR) together with AND "&" can be used to form OR "V", so these two (exclusive-or "^" with AND) can form the complete set of all 16 possible logical operations (with two "inputs" and one "output"). How is this possible? Simply seen: if we "freeze" p=1 in the truth table above, the "^" operation turns q into ~q, i.e. the "^" symbol becomes NOT with p=1. AND and NOT are sufficient to form all 16 of the logic operations (we can derive OR from these two). If we were equipped with only NOT and AND and XOR we could build an OR as follows:

INCLUSIVE-OR V = [(~p&q)^(p&~q)]^(p&q) This simplifies to:

INCLUSIVE-OR V = (p^q)^(p&q) Interestingly, this our half-adder XOR'd with its carry term! Unfortunately the "XOR" is difficult to build as its own tiny machine; the NOT-OR and NOT-AND in particular are very easy to build and form the basis of all digital machines (e.g. computers).

wvbaileyWvbailey 15:28, 29 May 2006 (UTC)

The best summary I've seen so far is Peter Suber's Principle of Exclusive Disjunction for Contradictories, which relates to both the Excluded Middle and Non-Contradiction. Perhaps we should incorporate some of his terminology? Also, is there any clear precedent for whether this is a 'Law' or a 'Principle'?

Drernie 15:05, 20 Sep 2003 (UTC)

De Morgan's Rules

In any system of logic that accepts De Morgan's rules, isn't the law of excluded middle equivalent to the law of non-contradiction? —The preceding unsigned comment was added by Bihzad (talk • contribs) 23:22, 30 May 2005 (UTC).

Well yes, since all tautologies (validities for quantified formulas) are equivalent. If you mean to ask whether one is derivable from the other by De Morgan's, then yes again. Nortexoid 01:06, 31 May 2005 (UTC)