Talk:Law of excluded middle/Archive 1

Archive 1

Archive 2

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)

On being attentive

• JA: Just giving the article and some of its hyper-associates the quick once over, I am brought to observe that considerable reserve must be exercised in comparing past and present idioms (idiomata?) in logic, even within what considers itself to be a cohortative cultural trans-mission, lest we generate travesties of a sort that were pandemic in the 1900's by way of "rendering" what our forebears understood as logic. Just by way of example, it's not automatic that the classical "laws of thought" and the lately so-styled "principle of bivalence" (POB) even live on the same plane of comparison. So that is one issue to which we must direct further attention. Jon Awbrey 13:16, 2 February 2006 (UTC)

I don't understand a word of this. Try to write in the king's english, without sounding like Miss Manners. Any concrete suggestions here or is this just rant?wvbaileyWvbailey 18:47, 3 April 2006 (UTC)

Just reporting a typo: "Nost radical"

Cleanup

I cleaned up and simplified the language of the introduction. --Scaro 17 Sept 2006.

Ugh, what can we do with this? The current article is disorganized, incomplete, confusing, and nigh-unreadable. It touches on much that seems at best tangentially relevant. The connections drawn are so idiosyncratic that it feels like "original research" (see WP:NOR).

I think most of it should be deleted. It would be better for the current article to become an essay on some non-WP web site, and then maybe link to it here. --Jorend 14:29, 3 April 2006 (UTC)

(later) I deleted the reference to Hermaphroditus and the sigmoid function example. I recognize that I'm deleting stuff that's (arguably) interesting, and which people might like to read. The problem is, as an encyclopedia article, it really ought to be usable as a reference. That entails the ability to answer questions without reading the entire thing. --Jorend 17:29, 3 April 2006 (UTC)

Wrong about the NOR. This is all in the literature, the issue is how to shape my entries. What I'm doing is interpretive. Hence if you look carefully you'll see everying noted as to source. If you have some time and nothing better to do, try to figure out a way to explain Reichenbach's assertion about the exclusive-OR. Also pull in the business (which I don't know much about) of more recent proofs -- circa mid 1960's -- re the "existential" and "universal" operators and how to create antinomies from them ... if indeed this applies to the law of excluded middle. I've been surprised at how deep the issue of The law of excluded middle is, and what a serious issue it was in the early 1900's, cf. the papers of Brouwer's, Kolmorgorov, etc. in Heijenoort's From Grege to Godel, Harvard U. Press, 1967, and the huge arguments it created between Hilbert and his crew on one side, and Brouwer and his disciples (including his student Weyl) (the finitistics) on the other. If the law were to be abandoned, e.g. Turing's proof and Godel's proof (1931) would be in serious jeapordy. Read in particular Kolmorgorov in Heijenoort:

"Brouwer's writings have revealed that it is illegitimate to use the principle of excluded middle in the domain of transfinite arguments" (Kolmorgorov, 1925, "on the law of excluded middle", p.416)

Can you imagine what would happen if e.g. Brouwer's finitistic arguments were accepted? In particular to see the depth of the potential disruption, read the Encyclopedia Britannica article, in the latest edition (2006), re "Mathematics, Foundations of". I'm debating about reverting the sigmoid stuff -- it is germane to the discussion. People need a way of understanding where this comes into play, why it is important. Others have read it and liked it, in fact done a little cleanup on it. Actually the other thing about the fourier series is also germane to the study of analysis in the late 1800's in particular Hilbert et. al's work. wvbaileyWvbailey 18:42, 3 April 2006 (UTC)

I agree that the article consists largely of irrelevant or unnecessary digressions. To explain the law, its significance, and the criticism and its significance, does not require at all going into the philosophy underlying PM, which is somewhat ideosyncratic anyway. I don't agree that Turing's or Gödel's proof would be in jeopardy; it is a somewhat tedious but elementary exercise to formulate these in a fully constructive way. Where the article becomes formal, it is needlessly awkward. Just one example: in the proof at the end, to go from (¬P → ¬P) to (P ∨ ¬P) takes exactly zero steps if (A ∨ B) is defined to stand for (¬A → B). For the critici of the law of the excluded middle, this is totally irrelevant since the definition does not correspond to the notion of disjunction. Somehow the article should make clear that mathematicians who do not accept the law of excluded middle also do not accept the involution of negation, that is, they reject the universal validity of (¬¬P → P). Lambiam^Talk 22:11, 15 April 2006 (UTC)

Indeed as I am the "author" of some of the stuff (but -- not the proof at the end. An editor sliced and diced away and created the "proof" which i haven't bothered to look at; the Russell-PM proof inside the PM discursion is just a one-liner.) What you see I confess it is a jumble -- I threw the thoughts down as they came and as I researched the problem (and threw down examples for my own understanding). I was gonna come back to it but haven't had the time.

I do agree with your ~~P --> P point. I haven't thought it through or researched it for what it "really" means to, or how to interpret it for, the reader. Maybe you can explain it here or on the page?

I do not agree with your comments re PM. With respect to the war between Hilbert versus "intuitionism" and/or "finitism", PM is what started the (historical) ball rolling. You can't understand this stuff in a vacuum of historical context. (This is a sore point with me in general with respect to mathematical/logic Wikipedia entries, they're useless for historical context. I do much better with Britannica. It seems when I add historical context some under-30 aged editor just deletes it (that happened here.) Maybe you have to be an old guy to appreciate history, I dunno... )

I don't agree with you about the Turing proofs (plural). The Godel proof(s) worry me too but i know less about it/them (I am not the only worrier, see the footnotes #4 (p. 34), #30 (p. 97), and #31 (p. 98) of Nagel and Newman. By the way, my personal rule is to use only peer-reviewed printed sources. So whether you & I agree with Nagel and Newman is irrelevant to Wikipedia; they're in print, we're not.) If you know of good discussions and/or re-proofs of Turing's 2nd (recast as Rice's Theorem?) and 3rd proofs lemme know because because I'd like to do some more work on the Turing's Proof page.

From what I can gather, any proof that uses reductio ad absurdum is rendered suspect by the Brouwer arguments. (Don't get me wrong here, I'm agnostic with respect to this excluded middle stuff. I've been able to create antinomies with tri-valued logic so I don't think it or fuzzy logic is any help at all). Altho the first of Turing's three proofs does use reduction it is very constructive ... but it is not the one in jeopardy. It's the second of the three that uses the double-inverse. In fact as I studied it (before I got caught up in this excluded middle thing) I was quite uncomfortable with his (one might say) inverting the infinite case to end up with the null case.

I'm also bugged by the Reichenbach quote. I think his point is serious. But I don't know how to explain it well. I just threw some stuff down to get something down.wvbaileyWvbailey 18:13, 18 April 2006 (UTC)

It is clear that the article cannot remain as it is. To massage the current article into a decent version will take a large amount of effort and time. I'm not sure about the best way to proceed, but a safe way is to first pare the article down to something that is simple, basic and incontrovertible, suitable for the non-specialist, and in an encyclopedic style (see Wikipedia:Manual of Style). The article is too long anyway. Only then should more advanced stuff be added, gradually, making sure at each step that the quality of the article is maintained. See also Wikipedia:Manual of Style (mathematics)#Suggested structure of a mathematics article.

An example of a statement that should either be deleted, or explained and backed up by a solid reference, is the following: "This is not quite the same as the principle of bivalence, which states that P must be either true or false." As stated, this principle is equivalent to the LoEM for classical mathematicians and intuitionists alike. It is the intended reading of the propositional formula (P ∨ ¬P): P is true, or P is not true (false). It is only to formal logicists, for whom these symbols have no a priori meaning, that this is not obvious. To them formula (P ∨ ¬P) might as well mean: (P if the GRH is true, and else (P implies the GRH)).

I didn't write the stuff about the principle of bivalence etc and i disagree with some of the stuff in the lead-in paragraph myself but haven't had time to research it. The "law of excluded middle" seems to have a number of definitions. Some editor culled out my definitions and examples that went back to Aristotle. So I kind of fell back to Principia Mathematica.

By the way can you tell me what LEM and LoEM stands for? Thanks. You sound very expert at this topic. Perhaps you can work the article over a bit? wvbaileyWvbailey 16:25, 29 May 2006 (UTC)

LoEM = Law of Excluded Middle. I didn't use the abbreviation LEM but assume it means the same. As I wrote earlier, I don't have access to a library, so I can't cite sources, which I think is indispensible. If I were you, I'd start by removing bits that are not central to the article, or that are not in the shape you'd expect in an encyclopedia article. For start, the (sub)sections "A detour: an example of the intuitionist objection", "Recent debate", and "Proof" (but let the references stay).

One general problem of this and related articles (Principle of bivalence, Law of noncontradiction) is that they don't give any ground rules and don't seem to use a way of distinguishing formulas (representing propositions or logical statements) "as sequences of symbols" from their meanings. In mathematical logic you basically have three things: a language, a semantics, and a proof system. To state that a formula holds ("It is the case that ...", or using the ⊨ sign) is a claim about the semantics of the formula. If all formulas that can be proved also hold, the logic is sound. If all formulas that hold can be proved, the logic is complete. The semantics is assumed not to be arbitrary. For example, ⊨¬P is usually supposed to be true precisely when ⊨P is false. It is important to know whether there is an assumption that the logic is sound. Is the "Law" of noncontradiction to be considered a requirement on logics, or what? Under the normal rules of logic, if that law does not hold, the logic is unsound. But do we assume our logic follows the normal rules? If not some ground rules have been given, we have no idea what we are talking about. Any symbol might mean anything, and as to the rules of the proof system it's like Alice's game of croquet.

How to proceed? Before we can use them, the symbol ∨ has to have an operational definition, as does the symbol ¬. We might adopt this procedure: Post (1921) first used the notion of "Truth Table" with regards to definition of these two terms (p. 267 in From Frege to Godel). He starts out with

"Let us denote the truth value of any propostion by + if it is true and by - if it is false. This meaning of + and - is convenient to bear in mind as a guide to thought, but ... they are to be considered merely as symbols which we manipulate in a certain way. Then if we attach these two primitive truth tables to ~ and V [here Post gives the tables] we have a means of calculating the truth values of ~p and p V q from those of their arguments [etc]"[ibid]

We could place these little tables in the text. Along with the Post quote to drive home the symbolic, symbol-manipulational, mechanical nature of the enterprise. But how do we tie these simple concepts to the LoEM and to double negation? Isn't the argument against double negation concerned with the existential operators (these are not so easy to explain, hence my flying pig example)?

But then as I was mulling this I realize that the LoEM really is [?] about simultaneity in space and time: that a thing cannot both have a quality and not have the quality at the same time and place. Is this the correct statement? At time T, Alice cannot be in the rabbit hole and not in the rabbit hole; inside the rabbit hole Alice cannot be there and not be there time-simultaneously. But what does that have to do with logical OR? If you follow through with P V ~P and use the Post + and - assignations to P, then +∨- and -∨+ are the only two possible outcomes and both are reasonable. But this isn't really what the LoEM is about, right? There is this mysterious "third"-- the logical possibility that p & ~p can occur simultaneously in space-time and thus in P∨~P produce the weird third case +∨~(-) when (P=+ & P=-) This is the "inclusive" part of the OR. And it is this possibility that "conventional" logic disallows. Are these statements correct? (There's also the weird fourth case -∨~(+) when (P=- & P=+)). What a mess. My mind is fried.wvbaileyWvbailey 16:45, 31 May 2006 (UTC)

In the usual sense of the word, multivalued logics are not logic. They are essentially algebras, like the well-known Boolean algebra for the first-order classical propositional calculus. For a formula P in multivalued logic, it is not clear what it means to say that P holds. Also, there are no proof rules.

I hope this is of some use. --Lambiam^Talk 21:09, 29 May 2006 (UTC)

I am not sure I agree with you on the role of PM. Have you read Brouwer's thesis? It is quite clear that he considered the idea that the formulations in PM amounted to definitions ridiculous. He condemned the formalist/logicist approach to mathematics as being a "meaningless game with symbols", and in particular the idea that this had any relevance whatsoever to foundational issues. Of course I do agree that the issue has to be placed in context, including the historical context, which needs to explain the formalist versus intuitionist approach to the Grundlagenkrise. But not everything needs to be crammed into this article. There should be a solid exposition of that in some other article dedicated to that whole issue, and a concise description here. I see absolutely no need for this article to go into any technical detail concerning how the LoEM is handled in PM, or any other formalist treatment for that matter.

I see no problem with Turing's or Gödel's proofs. Unfortunately I don't have access to a library -- which is also a reason why I can comfortably criticize but not easily contribute except for things like copy editing, restructuring, or correcting obvious errors -- so I can't look up your references to Nagel & Newman and see why they worry about exactly what. But we don't have to report everything that has appeared in peer-reviewed printed sources (does N&N count as such?), especially not if it is wrong.

What I am doing is throwing the kitchen sink at the article -- but a fully documented chapter and verse kitchen sink-- and letting others restructure it. Then I'll go back and fiddle myself as it begins to take form. I just want to get something down. That's the hardest part of this. wvbaileyWvbailey 16:25, 29 May 2006 (UTC)

Not immediately relevant here: I just read the articles Gödel's incompleteness theorems and Turing's proof, and am disappointed by how bad the exposition is for something so important, and how much of it is wrong or misleading. In general, mathematical articles about foundational issues or fundamental concepts tend to be not the strongest on Wikipedia.

I do apologize for the mess of Turing's proof -- at least someone read it. I created the page and all the exposition. My exposition of the 1st proof is rock solid, the second proof sort-of-solid and the last a disaster, mainly because I can't figure his goddamn mess out. He had to redo the proof because he fucked it up the first time around, and he was unable to cull out the misleading/wrong stuff that led up to his flawed attempt. Turing was a young man working on his British Master's thesis, his work was extraordinary but flawed and only a few can even decipher it let alone correct it.

Clearly the Turing's proof article is much too long and too complex. I have never seen an article or book that clearly "exposes" the proofs, unlike Godel's proof, with a number of books about the proof. I've wondered if the article shouldn't be split into four separate articles, one a lead-in to the other three, and these treating Turing's proofs separately.

About the Godel's-theorems page I've never read it, can't comment. wvbaileyWvbailey 16:25, 29 May 2006 (UTC)

A proof that uses reductio ad absurdum whose conclusion is a negative statement is generally fully acceptable to intuitionists. So if the conclusion is that something is impossible (as in Turing's and Gödel's proofs), that is fine. But if the conclusion is a positive existential, then this proof method is usually unacceptable. The basic idea behind reductio ad absurdum is this: from a proof of (P → false), conclude ¬P. For an intuitionist, ¬P is an abbreviation of P → false. So in this basic form reductio ad absurdum is a perfect tautology. The way it is usually applied is when you want to prove Q, to prove (¬Q → false), and then the conclusion is ¬¬Q. The problematic thing is the classical step of concluding from there to Q. But if we want to prove, say, ¬R with this method (so Q is ¬R), we end up with ¬¬¬R. And that, to intuitionists as well, is the same as ¬R, so it has then been proved.

Yikes I'll have to peruse your explanation when i can get some time. But: There is something very unsettling about Turing's second proof. Perhaps it is related to the "postive existential" thing you wrote. His proof must go "all the way to infinity" to conclude that "nothing's there", and then the proof continues. I am very uncomfortable with this with respect to a machine-as-algorithm that must do its operations "unto infinity", so I can see why a finitist might disagree. This is damn serious stuff, if you ask me.wvbaileyWvbailey 16:25, 29 May 2006 (UTC)

I agree that tri-valued logic and even more so fuzzy logic are not relevant; I'm not even sure they should be mentioned, but in any case not in an original version. These logics, just like classical logic, are premised on the idea that every proposition has a "truth value", even if we don't know yet what it is. Rather Platonic, and running completely counter to the intuitionistic position that mathematics is a matter of mental construction, a work in progress.

I don't understand Reichenbach's problem; it sounds like another logicist thing. It all depends on how you define xor. If (P xor Q) is defined as ((P '∨ Q) ∧ ¬(P ∧ Q)), then also to intuitionists (P ∨ ¬P) is equivalent to (P xor ¬P). I don't think it needs to be mentioned at all.

Lambiam^Talk 21:15, 20 April 2006 (UTC)

Paradox

I've started some cleanup by deleting the following:

The law of excluded middle is at the heart of many logical paradoxes. For example, Russell's paradox starts by constructing the set M = {A | A ∉ A}. Then the statement M∈M cannot be true; and its negation, M∉M, cannot be true either. Without the law of excluded middle, there would be no contradiction here. With it, at least one of those two statements must be true.

This paradox is no mere mathematical curiosity: its discovery by Bertrand Russell destroyed Gottlob Frege's attempt to ground all mathematics in formal logic. Russell himself subsequently attempted the same task with Principia Mathematica, but his efforts met the same fate. Gödel's first incompleteness theorem proved the incompleteness of Principia Mathematica—and indeed any consistent formalization of standard mathematics. At the heart of Gödel's proof was a self-negating statement similar to Russell's paradox, also dependent upon the law of excluded middle.

This is simply incorrect. Russell's paradox does not require LEM. -Dan 20:09, 24 May 2006 (UTC)

Are you absolutely sure? Here's why. (This isn't published anywhere that i know of, at least I've never seen something as simple as this to explain an antinomy). Start with an NAND function, ~(a & b)=c = ~a V ~b. Think of it as a tiny machine. Set up its truth table. Now to create an antinomy wrap the output "c" back to input "b", for example. Then look to see where "c" and "b" are identical and our thingy is in a 'stable condition':

~(a&b)=c

..0..0..1

..0..1..1

..1..0..1 X

..1..1..0 X

Observe that only the top two conditions, rows 1 and 2, are "acceptable", whereas the last two are doing something horrid. Here's why: Suppose we draw a box around our little thingy, our NAND-thingy. Going into the box is one input "a" and coming out is one output "c". When "a" is zero, lo and behold, all is good ("c" = 0). But what happens when "a" = 1? Yikes! Output "c" is in either of two states simultaneously!! Can this be? Not in bivalent mathematics as we know it. And that we know that the inclusive OR form (~a V ~b)is equivalent to this, it suffers the same fate.

Ok. So what happens with the exclusive OR form? (I think it oscillates too, but let's see):

.~a^~b=c

.10010..1

.10101..1

.01110..1X

.01001..0X

It behaves badly too. In fact we have to conclude that ANY logic with inversion (logical NOT) behaves badly when "the output" is fed back to the "input." Engineers of course know this as "destructive feedback"-- it causes either oscillation or latchup (inclusive-OR will "latch" as a memory but the exclusive-OR will not).

And the fact is, you see the same horrid things in feedback theory: OUT = IN*G/(1 +/- G*H) does horrid things if 1-GH goes to zero. But interestingly, a stable condition (OUT= 0.5) can be found when OUT = 1*G/(1+GH) and G=1 and H=1. This is our friend the "middle term" (again, this stuff was cut).

Yikes! Antinomies are popping up everywhere! Are they a feature of our universe?

and in fact self-negation (double-negation in an AND made from an inclusive OR) can result in LATCHUP:

~(~aV~b)=c

..10110..0

..10001..1

..01010..1 X

..01001..1

Again draw a box around our AND-thingy and put in "a" as its single input and "c" as its output. Suppose "c" starts out at 1 and "a" starts as "1". If "a" goes to "0" then "c" goes to "0" and when we return "a" to 1, "c" stays at 0. So this thingy's behavior is time-sequence dependent. Which of course cannot exist in traditional mathematical logic.(Ditto for the OR, just the values of "c" and "a" reverse.)

Because our logic has only two values {0, 1} or {True, False}, the third (0.5) is not allowed (hence my example of Hermaphroditus which an editor cut), so if that stable state can be found, it is not allowed in the logic. Hence, if you ask me, ALL the antinomies, traditional bivalent logic, of all sorts (oscillatory and latching), are due to the absense of the middle third. (That doesn't mean that three-valued logic will not create antinomies, I was successful at applying the same methods and got some antinomies, so i dunno).wvbaileyWvbailey 21:09, 30 May 2006 (UTC)

I don't understand what all this has to do with Russell's paradox and with the question whether it requires the Law of excluded middle. Here is how to derive an inconsistency, once we admit {A | A ∉ A} into the system. Let us call this animal M. I consider A ∉ A an abbreviation for (A ∈ A) → false. Abbreviate M ∈ M to X. Then X ↔ (M ∈ M) ↔ (M ∈ {A | (A ∈ A) → false}) ↔ ((M ∈ M) → false) ↔ (X → false). Each of these steps is just applying a definition. Now we have X ↔ (X → false), and hence X → (X → false), or (X ∧ X) → false, or simply X → false. Since X ↔ (X → false), we now also have X. Combining X → false with X, we now conclude: false. Consistency Control Centre, here is the Inference Engine Room. We have a situation. Look, this requires no appeal to the Law of excluded middle, just steps that are true in pure intuitionistic logic. --Lambiam^Talk

I believe your example is the same as mine: you are just using substitution in place of "wrapping around output to input".

As I wrote earlier, I am agnostic about this stuff. We are just talking philosophy here and neither of us will agree with the other, probably because your world-view and mine are so different. But here's a bit more of my thinking as i wrote the original stuff that some editor carved away.

Your argument has a bunch of hidden premises: e.g. you have divided the Venn-diagram-world of your argument into "false" and "not-false" {false, not-false}: "false" is equivalent to "not-not-false" but there is no (false+not-not-false)/2 (i.e. the boundary between the two zones of the Venn diagram). And your implication and biconditional arrows and AND are "Boolean operators" that do something bivalent (my little truth-table antinomies above also work with implication). And because your bivalent reasoning does not have a "third value" (third mark, symbol, boundary, whatever) to "settle into" or "arrive at", your bivalent reasoning has no possibility of "settling into/arriving at" a "consistent" condition. So your "consistency control center" goes wonky, as did my antinomies. Our minds, on the other hand, are material, and they CAN detect the wonkiness, and to them it feels like "oscillation" (with time as an added variable).

From what I can see, all of logic is infected with this. All of the world is infected with this. There is nothing (made of mass and space and time) in this or any other real universe that hops from Y=false to Y=not-false at exactly X=0.5. The reason has to do with infinite energy, etc. etc. (Example cut from the LOE article: the logistic or sigmoid function Y =1/(1+exp(G*(X-0.5)) is Y=0.5 at X=0.5 no matter how large a number the "gain" G is. ). In the real universe where we (engineers) happen to live, in a world of time as well as space, we (engineers) have to confront oscillation (stability) of mechanical stuff with "feedback control theory" where another variable (time) comes into play and interacts with mass and space to produce velocity, acceleration, momentum, energy, etc. etc. (the editor also cut my example from Fourier analysis that proves that there is indeed a mid value when approximating a "logistic-like" function with a Fourier series. I believe that this gave Hilbert and his analysis-crew a rough time for a while. Correct me if I'm wrong here...) But logicians don't have to confront these earthy things. Me, I just find the Platonist/idealist world of the mathematician (Yikes! Shades of Roger Penrose!) and the earthy world of the engineer curious and incompatible, hence the never-closing distance of our thinking. You are correct: this needen't be brought up here re Russell's Paradox, that's for sure. But it does illustrate the fact that "the LOE problem/question" isn't easy to blow off, and it isn't going away any time soon. wvbaileyWvbailey

It's nothing to do with "my" world-view. I'm just applying standard inference rules from logic. There is no Venn-world dichotomy hiding in here. You can mimic all of this faithfully in topos theory with arbitrary subobject classifiers. As I wrote, all of this is also valid in intuitionistic logic. I have shown conclusively that Russell's paradox does not depend on the Law of excluded middle, something that you contested. But I'm losing track of the point of the discussion. What you write is very original research. But as Wikipedia editors we leave our original research at the door as we enter, and report instead on the notable achievements of others, using reliable published sources that we can cite. So I don't see how any of this can matter to the article, whether I agree with the tenor of your philosophical investigations or not. --Lambiam^Talk 03:59, 31 May 2006 (UTC)

You're way beyond me here with the topos theory. I'll have to defer to your point. You are clearly the expert in this area, not me. And I agree that this is far off-topic. It has been a fun and useful discussion though. Thanks. I agree that if you find "incorrect, incoherent, incomprehensibe statements" then you et. al. should cut/correct them. Re the Russell Paradox thing: "When in doubt leave (cut) it out." Again, I just threw the sink at the page to get something down. But now what the page needs is good knowledgable editing and shaping. Unfortunately, I think what we're discussing is something an editor took from the original stuff that I'd written and whether I wrote something misleading or wrong and he misinterpreted, I dunno. Is there any of that stuff in italics that can be saved? I do remember somewhere, in some source or other, someone writing that about the Godel proof. Kolgomorov maybe? I've got a cc of From Frege to Gödel. Here's a quote from Gödel (p.598):

"The analogy of this argument with the Richard antinomy leaps to the eye. It is closely related to the "Liar" too [footnote 14]....We therefore have before us a propostion that says about itself that it is not provable [in PM] [footnote 15].

Footnote 14: "Any epistomological antinomy could be used for a similar proof of the existence of undecidable propostions.

Footnote 15: "Contrary to appearances, such a proposition involves no faulty circularity...Only subsequently (and so to speak by chance) does it turn out that this formula is precisely the one by which the propostion itself was expressed" (p. 598)

What we need to answer is: what impact, if any, does the LOE have on this? You are saying none(?) My proposed response is: if that which cannot settle down into "the middle third" is "inside the antinomy" then it is (in part) the cause of the antinomy. But if you don't agree then again, "when in doubt leave it out". (As I write this the analogies from feedback theory are running wild in my mind. Whether an antinomy occurs has to do with gain and delay in the "machines-as-logical-operators" located inside the antinomy.)wvbaileyWvbailey 14:23, 31 May 2006 (UTC)

Bravo. If you delete all other incorrect, incoherent or incomprehensible statements, the article will no longer be too long either. --Lambiam^Talk 22:02, 24 May 2006 (UTC)

Well, I myself have wanted to write cogently about Brouwer, Markov, Bishop, and Weyl, at least under intuitionism, predicativism and constructivism (mathematics), and I don't seem to get around to a whole lot myself, and neither does anyone else. Spotting what is irredeemably wrong and toasting it is a lot easier than creating something even partially right, so I'm actually grateful that someone wrote something, even if it obviously needs to be cleaned and perhaps moved to different pages. -Dan 05:22, 25 May 2006 (UTC)

Interesting Reichenbach quotes re law of excluded middle, tie-in to "laws of nature"?

Reichenbach asserts that all tautologies can be reduced to the Law of excluded middle or tertium non datur i.e. P V ~P:

"This is its shortest form. It is clear that we can do the same for every tautology. All tautologies have [this] same shortest form ..." (§11 Derivations, p. 52).

Reichenbach has given the following meaning with regard to so-called nomological formulas:

"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 [e.g. 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. 360?)

In our example [flying pigs], "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 [P V ~P]" (cf Reichenbach p 52).

wvbaileyWvbailey 15:15, 31 May 2006 (UTC)

Cleanup continued

To wvbailey: This style of editing by inserting further comments and reactions between one comment and the next reaction to it creates a beautiful fractal structure but makes it hard to follow any threads, so I'm starting a new section.

While it may be interesting to you to hold a philosophical debate here, that is not the purpose of Wikipedia. We are here to produce an encyclopedia. In the time I've taken to react to you, I could have written an interesting and informative essay on the topic of the Law of excluded middle. But it would be just that: an essay, "original research", a Wikipedia no-no.

The same holds for your ideas, like using truth tables in the text to illustrate the issue: OR. If we had a "reliable source" who did this in reference to an illustration of the Law, then it would be OK for us to report: "So and so gave the following illustration using a truth table: ...". Apart from the fact that OR is against policy, it is furthermore not a good idea to engage in such things unless you are an expert with a firm grasp of the field, or else you are almost certain to blunder. In this case, for example, truth tables are actually totally unsuitable for illustrating the issue, for one simple reason: they already presume that truth is like a 0 or 1 bit. As in "Let me show that something must be either true or false. Well, since there are only two possibilities, true and false, and it must be one of the two, then it follows that it is true or false. QED." It begs the question.

We must not attempt to give a resolution to any perceived or real antinomies. That is not our task as editors. It is OK to report on the efforts of others. For this article, it is actually off topic in any case.

Forget Reichenbach. That stuff is way too technical and complicated. Sources that are an inspiration to ponder the topic are useless. You need to find sources that write about the Law in a form and at a level that is suitable for an encyclopedia article. And if you can't find such sources for this topic, put your energy in other topics for which you can. --Lambiam^Talk 00:14, 1 June 2006 (UTC)

Would be nice to read your essay. It would be useful to me.

Not to worry about the next entries, only a tiny fraction will be used. In this there are some nice (alternate) definitions of the LoEM that would be good to incorporate.

I'm trying to get the thread of Brouwer's (and Kolgomorov's) objections, the nut of their argument. I think I see it. But I have not yet found a good thread from LoEM to the "double negation" objection of Brouwer.

When I fell upon the LoEM I started with fundamental question: what is the LoEM really really? Now Kolgomorov asserts that there are two "...principle[s] that bear the same name"(p. 431) But he doesn't just come out and say what the 2nd one is. Rather he quickly leads into (a few lines later) "double negation" with respect to the "for all" operator: Is this the thread from the LoEM to "double negation"? Do you know anything about this? This is going to take a while: a little here, a little there. Like you I have lots of other fish to fry. wvbaileyWvbailey 14:28, 1 June 2006 (UTC)

Here is a humorous but illuminating and accurate rendering of Brouwers' objections: The Battle of the Frog and the Mouse. Kolmogorov is more technical, although he had many important insights, in particular that the intuitonist position – at least as far as propositional calculus is involved – becomes more or less obvious if you interpret "P is true" as: "We have a method to establish that P is true". But his impact on the debate was not that important. The two versions are almost certainly P ∨ ¬P and ¬(P ∧ ¬P). These two are equivalent in classical mathematics, which accepts the priciple of double negative elimination (as it turns out to be called on Wikipedia). Intuitionists reject the first but accept the second. They might be viewed as attempts to express Aristotle's dicta using present-day symbolic-logic formulas. The question to what extent these attempts are faithful to Aristotle's philosophy raises some precarious issue. Read Aristotle himself: Metaphysics, Book 4.

"But we have now posited that it is impossible for anything at the same time to be and not to be, and by this means have shown that this is the most indisputable of all principles"

[i.e. I assert: That it is not true that: "Flying pigs exist" and "flying pigs do not exist".] [quote and example added by wvbailey]

Fulminations against philosophers accepting the possibility of P ∧ ¬P are all over the place and quite repetitious. This might be called "Tertium non datur": There is no third (middle) ground, although it may be questioned if this dictum faithfully expressus the issue. A dictum by Aristotle suggesting P ∨ ¬P is found in one spot: the first sentence of the section numbered 7.

"But on the other hand there cannot be an intermediate between contradictories, but of one subject we must either affirm or deny any one predicate" (Aristotle 7 first sentence)

[i.e. I assert: "flying pigs exist" or "flying pigs do not exist"] [quote and example added by wvbailey]

That is where the name "excluded middle" comes from. Since the gist and tenor of the whole monologue are the rejection of accepting P ∧ ¬P, something that is reiterated and hashed to death ad nauseam, while this version P ∨ ¬P occurs just once, almost at the end and without much argument, one may wonder if Aristotle really meant embracing P ∨ ¬P as emphatically as it has been taken later, when Aristotle was considered the ultimate authority on all issues philosophical and logical, or that it is perhaps a less felicitous way of asserting once more that ¬(P ∧ ¬P). --Lambiam^Talk 23:47, 1 June 2006 (UTC)

Thanks, this is really interesting. It really helps me understand this whole topic better, esp. the P V ~P and ~(P & ~P). This has to go into the page somewhere. Lots of good quotes and the references to Aristotle esp. the idea that (1) he does not deny that the middle exists, but rather (2) that after repeated applications of ~(P & ~P) the argument converges to a third ("different") thing. Neat! [I saw the same thing with the logistic function inside a feedback loop-- it either "flies" to one state or the other, unless you hit exactly the middle-- a stable state].

I agree that Kolmogorov is useful but less interesting than Brouwer. Can you shed any insights on the Brouwer business below? I have quotable quotes re Brouwer's influence on Godel. And a quote re the vicious circle business; but can this be tied directly into Godel's proofs? He certainly raised the issue of antinomies himself in his footnotes 14 and 15 of his On Formally Decidable Propositions. I don't see this as off-topic if it shows that the uproar over the LoEM is the thread through the uproar in mathematics that still continues today.

Boy that double-negation page needs some serious references and some work. wvbaileyWvbailey 14:43, 2 June 2006 (UTC)

Go easy with the "convergence". I think A's main idea there is that if someone asserts it is somewhere in the middle between white and something else, by that very assertion they have asserted already that it is not white. Remember, no original research. On other issues, see at the various subsections below. --Lambiam^Talk 16:22, 2 June 2006 (UTC)

More of the Aristotle:7 quote

"This is clear, in the first place, if we define what the true and the false are. To say of what is that it is not, or of what is not that it is, is false, while to say of what is that it is, and of what is not that it is not, is true; so that he who says of anything that it is, or that it is not, will say either what is true or what is false; but neither what is nor what is not is said to be or not to be.-Again, the intermediate between the contradictories will be so either in the way in which grey is between black and white,

"...when there is an intermediate it is always observed to change into the extremes. For there is no change except to opposites and to their intermediates.

[Interesting quote, see below where he states "...its [the intermediate's] essence is something different". What he is saying that after a regressions to "the middle", the middle is something different, as in: grey is different from black and white.]

"-Again, there must be an intermediate between all contradictories, if one is not arguing merely for the sake of argument;

"so that it will be possible for a man to say what is neither true nor untrue, and there will be a middle between that which is and that which is not, so that there will also be a kind of change intermediate between generation and destruction.

-Again, in all classes in which the negation of an attribute involves the assertion of its contrary, even in these there will be an intermediate;

[i.e. "I assert ~p" = ~p ??]

For again it will be possible to deny this intermediate with reference both to its assertion and to its negation, and this new term will be some definite thing; for its essence is something different.

[i.e. we start with "I assert: "It is not true: 'flying pigs exist' & not-'flying pigs exist'" but this leads by regress to:

[i.e. "I assert: "It is not true: 'flying & not-flying pigs exist' & not-'flying & not-flying pigs exist'"

[Thus by regression the assertion settles into the middle, and Aristotle asserts "its essence is something different"]

wvbaileyWvbailey 13:39, 2 June 2006 (UTC)

(1) Did Brouwer's "insights" trigger Godel?

Dawson asserts that "it seems to have..."(Dawson, p. 52):

"In his Bologna address Hilbert also raised the question of syntactic completeness for formalized arithmetic [123]. Brouwer, however, took a very different view... in his Vienna lectures [footnote 8 references 10 and 14 March 1928] he went even further: In the first of them he drew a sharp distinction between "consistent" theories and "correct" ones -- an idea that seams to have suggested to Godel that even within classical mathemtics formally undecidable statements might exist [124]" (Dawson p. 52)

"[124] According to Feigel (1969, p. 639), Brower's lecturers also galvanized Wittgenstein to resume his work in philosophy. For the texts of both lectures see Brouwer 1975, pp. 417-428 and 429-440, respectively)(Dawson p. 279)

"Feigel, Herbert (1969, p. 639): The Wiener Kreis in America. In Donald Fleming and Bernard Bailyn, eds., The Intellectual Migration: Europe and America, 1930-1960, 630-673. Cambridge, Mass: Harvard University Press" (Dawson p. 332)

"Brouwer, Luitzen E.J. 1975: Collected Works, ed. Arend heyting. Amsterdam: North-Holland Publishing Co.

This quote ends Dawson's chapter "Excursus". The next chapter is "Moment of Impact (1929-1931) which begins with the quotation of the famous antinomy:

"One of themselves, even a prophet of their own, said, The Cretans are always liars .... This witness is true." -- Titus 1:12-13"(Dawson p. 53)

"Though there is no way to pinpoint when Godel first begain work on his dissertation, internal evidence ... shows that it was sometime in 1928 or early 1929."(Dawson p. 53)

Although the influence is quite possible and even plausible, and in spite of others also having ventured the conjecture, to the best of my knowledge there is no directly supporting evidence, only of an entirely circumstantial nature, doing nothing else than reaffirm it is possible. We can quote but not doubleguess. --Lambiam^Talk 16:22, 2 June 2006 (UTC)

(2) Brouwer did fret about a "vicious circle" in the logicist formulations of Hilbert

The fourth of Brouwer's "insights" comes from a paper of Brouwer's (1927o) where, in a footnote he asserts, the following and then he partially retracts it in 1953 (my boldface):

"...A second argument is the way in which Hilbert seeks to settle the question ...of the reliability of the principle of excluded middle is a vicious circle; for, if we wish to provide a foundation for the correctness of this principle by means of the proof of its consistency, this implicitly presupposes the principle of the reciprocity of the complementary species and hence the principle of exluded middle itself (see Brouwer 1923c. p. 252)..." (p. 460 [see more below at (3)]

His reference to "vicious circle" is per the usage of Whitehead and Russell in PM.

The concept of a circulum vitiosum as a logical fallacy is an old concept. Does the context suggest he refers to the usage in PM? --Lambiam^Talk 16:22, 2 June 2006 (UTC)

No you are correct, the "vicious circle" is referenced to Hilbert not to PM; but I will need to get the book of Brouwer's writings to see more on this. Interesting that he picks on Hilbert incessantly, not so on Russell. Maybe he assumed that Russell was just Hilbert's shill.wvbaileyWvbailey 17:17, 2 June 2006 (UTC)

(3) But later Brouwer asserts that LoEM and double-negation are not equivalent

But Immediately after the vicious circle quote (2) Brouwer asserts the following:

"[Brouwer (1953, p. 14, footnote 1) writes "the equivalence of the principles of the excluded third and of reciprocity of complementarity ... subsequently has been recognized as nonexistent. In fact, as was also shown in the present paper, the fields of validity of these two principles have turned out to be essentially different]"(p 460)

They are not equivalent at a propositional level, but they are equivalent as principles of proof: It is easy to show that if you accept one the other follows, using entirely constructive reasoning as would have been acceptable to Brouwer. So I don't understand what this refers to; it must be a different interpretation of the principles than I have in mind. I'd need to see the paper to understand what is going on here.

(4) So what creates the vicious circle? LoEM or "double negation?" Can we tie what Gödel proved to either of these?

TBD

wvbaileyWvbailey 14:23, 2 June 2006 (UTC)

Although you can mimic this in formal logic systems, the vicious circle is in the (necessarily) somewhat informal justification as proof priciples. Just ask any mathematician, let's say Achilles, around you to justify them and you will hear Achilles say something like the following. "Assume that P or not P does not hold. Then it follows that P does not hold. In other words, we have now that not-P holds. But then the disjunction P or not-P holds, contradicting the earlier assumption. So the assumption is false, and therefore P or not-P does hold." Being a Tortoise, you now protest: "Dear friend Achilles, you have shown that the mere assumption of not-(P or not-P) is absurd and untenable. So I agree that therefore we have no choice but to conclude that not-not-(P or not-P) holds. There are a lot of 'not's in the statement. How did you manage to cut the 'not's in your conclusion down to just one occurrence?" Whereupon Achilles will deliver the following rejoinder: "Elementary, my dear Tortoise, entirely elementary. You see, what we have here is an instance of not-not-Q. Now we can greatly economize on the 'not's by a simple observation. Either Q holds, or it doesn't, as the great Aristotle already tortoise taught us. Clearly, not-not-Q tells us that the position that Q does not hold is not available to us. We have only one choice left: Q holds."  --Lambiam^Talk 16:22, 2 June 2006 (UTC)

Quotes from Dawson re influence on Godel of Brouwer's war on LoEM

[bold face added]

"Toward the end of his introductory remarks [to his dissertation, subsequently omitted from the published version] he [Godel] defended the "essential use" he had made of the Law of Excluded Middle, arguing that "From the intuitionistic point of view, the entire problem [of a completeness proof] would be a different one," one that would entail "the solution of the decision problem for mathematical logic, while in what follows only a transformation of that problem, namely its reduction to the question [of] which formulas are provable, is intended" (p.54)

"...he noted further that 'Brouwer...[in opposition to Hilbert] [brackets in original], has emphatically stressed that from the consistency of a system we cannot conclude without further ado that a model can be constructed."(p.54-55)

"...it should be noted that though Brouwer's role in stimulating Godel's thought seems beyond doubt, how Godel became aware of Brouwer's work remains uncertain.(p. 55)

"Suffice it to summarize their conclusions [Heijenoort and Dreben commenting in Godel's Collected works]: By the Law of Excluded Middle -- applied outside the formal system ---each of the quantifier-free formulas A-sub-n either is, or is not, truth-functionally satisfiable. In the former case, Skolem and Godel both concluded that the original formula F is satisfiable in the domain of natural numbers, whereas Herbrand, though noting "that such a conclusion could be drawn, [nevertheless] abstain[ed] from doing so" because the argument invoved "non-finitistic notion[s]"...

What to do next

I called the bookstore and the books listed above -- Brouwer's Collected Works and Migration -- are out of print (Migration is print-on-demand) and both were/are damned expensive ($100-200 US) unless found used. So further work here will have to be done in the library. bummer. I think it's okay to simply quote Dawson's assertions that Brouwer influenced Godel (we do see in Godel's dissertion his defense of his use of the LoEM) and then eventually research this more. wvbaileyWvbailey 18:23, 2 June 2006 (UTC)

Do the quotes perhaps refer to Gödel's proof of the completeness of the first-order predicate calculus (rather than his incompleteness theorems)? Some of the quotes make more sense under that assumption. Basically all mathematicians, from the time of Aristotle to the day of now, make unrestained use of the LoEM. The exceptions are a handful of (pre-)intuitionists and constructivists. But in the days of Gödel such unrestrained use was under heavy fire from the Brouwerian camp, and G. was of course well aware of this, and also of the risk that he – writing on issues in the heart of the debate – would incur the scorn of Brouwer and be subject to the next volly from his artillery. From the quote it is clear that G. is hedging his position, defending his use of it – which in peace time would not have been given a second's thought – in advance from possible intuitionistic criticism by explicitly recognizing their different position. Interesting, salient, but really a side issue, perhaps worth mentioning in a longer essay for a specialist audience, but not in this encyclopedia article. There is no suggestion that Brouwer's criticism had an impact on G's proof methods, which would have been more interesting. If anywhere on Wikipedia, the most plausible spot is perhaps the section "Foundational crisis of mathematics" in the artice Foundations of mathematics. But I'm not at all convinced it is worth mentioning there either. --Lambiam^Talk 23:03, 2 June 2006 (UTC)

You are correct, the quotes are in reference to and context of his dissertation (1929), not his later work. Dawson repeatedly reiterates the idea that Godel was cautious to the point of pathological so you are probably right about him hedging his bets. Dawson definitely gives (me) the impression that the LoEM, or the arguments around it, caused Godel enough concern to mention it in his (purged) intro to his thesis, so clearly the arguments were messing with his mind. Until I can gleen more, we can let this slide. It is easy to purge, altho I hate to because the tie-in is so interesting, and it adds "heft" to the otherwise rather light-weight LoEM.

Are you aware of any "modern" issues re the LoEM?wvbaileyWvbailey 02:18, 3 June 2006 (UTC)

I'm not aware of any "modern" issues. Even if I was, I'd advocate to first bring the article in good shape before starting to extend it to other issues. Once it is in good shape, then if there are notable modern issues, other editors will bring them in. The present shape keeps people from working on it.

The arguments no longer mess with the mathematicians' minds. Many are at best only vaguely aware that there was some argument without understanding what it was. As is said in Foundations of mathematics: "the crisis has not been resolved, but faded away". Mathematicians practice classical mathematics, which includes classical logic and embraces LoEM without any qualms concerning its unreliability as a proof principle. --Lambiam^Talk 10:16, 3 June 2006 (UTC)

Holding place for quotes from Brouwer and Kolmogorov, Intuitionist Logic, etc.

All quotes are from: Jean van Heijenoort, From Frege to Godel, Harvard University Press, 1967)

Intuitionist Definitions of Law (Principle) of Excluded Middle

Brouwer offers a definition of "principle of excluded middle" (my boldface throughout):

On the basis of the testability just mentioned, there hold, for properties conceived within a speific finite main system, the 'principle of excluded middle', that is, the principle that for every system every property is either correct [richtig] 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).

The second definition is double negation [italics in original].

Kolmogorov's definition of the LoEM: Kolmogorov cites Hilbert's two Axioms of Negation

5. A -> (~A -> B)

6. (A -> B) -> {(~A -> B) -> B}

(my boldface in these quotes):

"Hilbert's first axiom of negation, "Anything follows from the false", made its appearance only with the rise of symbolic logic, as did also, incidentaly, the first axiom of implication.... while... the axiom under consideration [2nd axiom 6.] asserts something about the consequences of something impossible: we have to accept B if the true judgement A is regarded as false"(p. 421)

" 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" [footnote 9] is equivalent to that given above [footnote 10]" (p. 421)

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 V ~A

"where V means "or". The equivalence of the two forms is easily proved..." [etc]" (p. 421)

Intuitionism versus Logicism

By 1927 Brouwer has firmed up his convictions expressed here in 1923. He is clearly concerned that "the laws...were applied without reservation even in the mathemaatics of infinite systems and ... the results are...not open, either practically or theoretically, to any empirical corroboration"(p. 336). In particular he expresses pique at:

"The contradictions that, as a result one repeatedly encountered gave rise to the formalist critique...:the language accompanying the mathematical mental activity is subject to a mathematical examination...the laws of theoretical logic present themselves as operators acting on primitive formulas or axioms, and one sets himself the goal of transforming these axioms in such a way that the linguistic effect of the operators mentioned... can no longer be disturbed by the appearance of the linguistic figure of a contradiction....{but] nothing of mathematical value will thus be gained: an incorrect theroy, even if it cannot be inhibited by any contradiction that would refute it, is none the less incorrect...."(p. 336)

By 1927 he had proposed "Four insights", the second and third and fourth all mentioning the LoEM (my boldface, his italics):

"Second insight: The rejection of the thoughtless use of the logical principle of excluded middle...the investigation of the question why the principle mentioned is justified and to what extent it is valid... in intuitive (contentual) mathematics this principle is valid only for finite systems.

"Third insight: The identification of the principle of excluded middle with the principle of the solvability of every mathematical problem.

"Fourth insight: The recognition...that the (contentual) justification of formalistic mathematics by means of the proof of its consistency contains a vicious circle, since this justification rests ... upon the (contentual) correctness of the principle of excluded middle" (p. 491)

Brouwer's discussion of the third insight he discusses Hilbert's "decidability by means of a finite number of operations" (p. 492)

The fourth insight comes from an earlier paper of Brouwer's (1927o) where, in a footnote he asserts, and then he partially retracts in 1953 (my boldface):

"...A second argument is the way in which Hilbert seeks to settle the question ...of the reliability of the principle of excluded middle is a vicious circle; for, if we wish to provide a foundation for the correctness of this principle by means of the proof of its consistency, this implicitly presupposes the principle of the reciprocity of the complementary species and hence the principle of exluded middle itself (see Brouwer 1923c. p. 252) [Brower (1953, p. 14, footnote 1) writes "the equivalence of the principles of the excluded third and of reciprocity of complementarity ... subsequently has been recognized as nonexistent. In fact, as was also shown in the present paper, the fields of validity of these two principles have turned out to be essentially different]"(p 460)

THIS NEEDS TO BE RESEARCHED!

Kolmogorov's (1925) objections to "the formalistic point of view":

"To deny any real meaning to mathematical propositions is ... what constitutes the basis of the formalistic pint of view in mathematical logic....So long as mathematical logic is regarded only as a formal system whose formulas have no real meaning, it diverges from general logic; the formalistic point of view can exist only in mathematics and mathematical logic but not in the ordinary logic that lays claim to significance in applications to reality.

" As for us, we do not isolate a special "mathematical logic' from general logic....Only in this logic ["a specialized 'Mathematical logic'] does a doubt arise concerning the unconditional applicability of the principle of excluded middle" (p. 418)

He then goes on to present the formalist axioms of Hilbert.

Kolmogorov on "Hilbert's two axioms of negation":

" one of Hilbert's two axioms of negation, Axiom 6, expresses the principle of excluded middle in a somewhat unusual form. Brouwer proved that the application of the principle to arbitrary judgments is without any foundation [his footnote 4]. Axiom 5 is used only in a symbolic presentation of the logic of judgments; therefore it is not affected...."(p. 419)

[Footnote 4]: "So far as the principle of excluded middle in the general logic of judgments (Axiom 6) is concerned, Hilbert does not say anything about the question of its intuitive obviousness; apparently he considers this obviousness to be indubitable....

" First, axiom 6 is not intuitively obvious... the truth of Axiom 6 ... demands for its justification that the content of the judgments be considered, and this content may be transfinite."

Hilbert's two Axioms of negation cited by Kolmogorov:

5. A --> (~A --> B)

6. (A --> B) --> {(~A --> B) --> B}

Kolmogorov proposes a single axiom that he calls "the principle of contradiction" to take the place of the two above:

5'. (A -> B) --> {(A --> ~B) -> ~B}

"Its meaning is: if both the truth and the falsity of a certain judgment B follow from A, the judgment A itself is false."

He also adds a 6th axiom:

6'. ~(~A) -> A

loose quotes

comments in his intro to Brouwer's paper (1923) that the principles of finite mathematics, the origin of logic, were

"...applied to discourse about the physical world and then to non-finite mathematics, but in that last field there is not necessarilty a justification for each of these principles. In particular, such a justification seems to be lacking for the principle of excluded middle and that of double negation" (p. 334,

Here is Brouwer on "testing" that immediately precedes his definition of LoEM:

Within a specific finite "main system" we can always test (that is, either prove or reduce to absurdity) properties of systems, that is, test whether systems can be mapped, with prescribed correspondences between elements, into other systems; for the mapping determined by the property in question can in any case be performed in only a finite number of ways, and each of these can be undertaken by itself and pusued either to its conclusion or to a point of inhibition" (p. 335)

[see Corrigenda (1954) where Brouwer fiddles with his definition of 'to test' (p. 341)

Kolmogorov (1925) seems to be both supportive and critical of the results of Brouwer. He agrees with Brouwer that "it is illegitimate to use the principle of excluded middle in the domain of transfinite arguments" but he believes he can demonstrate why "this illegitimate use has not yet led to contradictions and also why the very illegitimacy has often gone unnoticed." (p. 416). He offers a solution he calls "pseudomathematics".

Kolmogorov openly contradicts Brouwer with his assertion (V, §1.1):

"If a finitary conclusion is obtained with the help of arguments based on the use, even in the domain of the transfinite, of the principle of excluded middle, the conclusion is true in the usual sense."(p. 431)

He goes on to assert that:

"The use of the principle of excluded middle never leads to a contradiction." (p. 431)

Here is Kolmogorov on "judgement":

"In the logic of judgments the judgment is considered the ultimate element in the investigation ... it can be appraised from the point of view of truth or falsity." (p. 418)

>pseudomathematics? n{n(~(~A))-->nA} his formula 56 ??

Kolmogorov asserts that:

"... without the help of the principle of excluded middle it is impossible to prove any proposition whose proof usually comes down to an application of the principle of transfinite induction....

" The proof of such propostions is often carried out without the help of the principle of transfinite induction. But all these proofs rest upon the principle of excluded middle, applied to infinite collections, or upon the principle of double negation." (p. 436) wvbaileyWvbailey 03:07, 1 June 2006 (UTC)

Brouwer examples

He offers examples of failures that result from "...incorrect 'logical" mathematics of infinity ('logical' because it makes use of the princple of excluded middle)" (p. 337) One example that might be familar to students of analysis (the convergence of infinite series) (p. 339) he claims "rests on the Bolzano-Weierstrass theorem and must be rejected along with it" (p. 340).

. The thread is this: he claims "the Paris school" asserts that "every mathematical species is either finite or infinite" and in his footnote 4 to this asserts "For according to the principle of excluded middle a species s either is finite or cannot possibly be finite [etc]". From this derives what he calls the "extended disjunction principle" [union of two sets contains a "fundamental sequence of elements"], and when this fails, the Bolzano-Weierstrass theorem fails "which rests upon it and according to which every bounded infinite point species has a limit point" (p.337)

Reduction of Hilbert's 2nd negation

[What a mess -- just to see what is going on:

(A->B) -> {(~A -> B)-> B}

1 (A->B) -> {~(~A -> B) V B}

2 (A->B) -> {~(~(~A) V B) V B}

3 (A->B) -> {(~(~(~A)) & ~B) V B}

4 (A->B) -> {(~(~(~A)) V B) & (~B V B)}

If we believe that (~B V B) = ALWAYS TRUE, then we have:

5 (A->B) -> {(~(~(~A))V B) & (TRUE)}

We are asserting here that X & (TRUE) is X

6 (A->B) -> {(~(~(~A))V B)}

If we believe that ~(~A) <-> A then we have:

7 (A->B) -> {(~(A) V B)}

And the implication holds as a tautology. Observe that two assumptions are made. One regarding ~B V B)=ALWAYS TRUE and the other regarding ~(~A)<->A. Is his a source of Brouwer's retraction? Which one dominates? Are they really two issues?

If you assume intuitionistic logic, then excluded middle (for any proposition, either A or not-A) follows from double negation elimiation (for any proposition A, if not-not-A, then A), and vice versa. In particular, for any proposition A, ~(~(A v ~A)) is a theorem, in your notation. I'm not sure if that's what you were asking. -Dan 17:23, 5 June 2006 (UTC)

Not exaclty...On the article page I (well, actually, Bertrand Russell...) derived the double-negative from the LoEM. I wrote the above derivation before I (-as-Bertrand) wrote the stuff in the article. But actually the little derivation above is out of place. It used to be under a quote re Brouwer in the 1950's retracting [?, modifying?] his position relative to the "equivalence" of the LoEM and the double negative. But to read his paper and find out what he was up to--the collection of Brouwer's works is out of print and probably cost $100 or more if you can find one -- we will have to crawl deep dark recesses of moldy dusty stacks of a good math library. It probably isn't worth the resultant breaking out in hives or a sneazing fit. My guess is it has to do with definitions of truth and falsity and "testing" and "reducing to absurdity' [to quote Brouwer] and "correct or impossible [to quote Brouwer], and verifying and stuff that I, personally, am finding just too silly. Ferchrissake: "Marks is marks, 'n a mind -- or one o' them newfangled machines-- hasta be there to put meanin' to 'em. There ain't no such a thang as marks with intrinsic meanin'. They's just marks. There ain't no such thang as anythin' a-tall', not even that-there blue sky out yer window, not them number-thangs you fret about, no fancy law of exculpated middle, no nothin' a-tall, without a mind or a machine to be lookin' at it an' puttin' a meanin' to it."wvbaileyWvbailey 18:37, 5 June 2006 (UTC)

I am not aware of Brouwer's retraction... -Dan 20:44, 5 June 2006 (UTC)

Here 'tis:

The fourth insight comes from an earlier paper of Brouwer's (1927o) where, in a footnote he asserts, and then he partially retracts in 1953 (my boldface):

"...A second argument is the way in which Hilbert seeks to settle the question ...of the reliability of the principle of excluded middle is a vicious circle; for, if we wish to provide a foundation for the correctness of this principle by means of the proof of its consistency, this implicitly presupposes the principle of the reciprocity of the complementary species and hence the principle of excluded middle itself (see Brouwer 1923c. p. 252) [Brower (1953, p. 14, footnote 1) writes "the equivalence of the principles of the excluded third and of reciprocity of complementarity ... subsequently has been recognized as nonexistent. In fact, as was also shown in the present paper, the fields of validity of these two principles have turned out to be essentially different]"(p 460)

This is the paper I'm not willing to go sniffing after in the tombs: Brouwer, "Points and Spaces", Canadian Journal of Mathematics, 6 (1954), 1-17. Footnote #1.

I'm with Dan here. As I wrote earlier on the "retraction": "They [LoEM and double-negative elimination] are not equivalent at a propositional level, but they are equivalent as principles of proof: It is easy to show that if you accept one the other follows, using entirely constructive reasoning as would have been acceptable to Brouwer. So I don't understand what this refers to; it must be a different interpretation of the principles than I have in mind. I'd need to see the paper to understand what is going on here." --Lambiam^Talk 23:58, 5 June 2006 (UTC)

I agree with you that one can be derived from the other, at least in bivalent logic; see the tiny proofs on the article page under the PM heading.

FYI: here's the entire quote: Note that it is a flea on a flea: it is in a note to a footnote to a paper mentioned in a footnote (something like that):

"Now, if the relations employed in any given proof can be decomposed into basic relations its 'canonical' form (that is the one decomposed into elemetntary inferences [^8]) employs only basic relations..."[I can't copy the rest of this its just a mass of subscripted F's](p. 460)

"^8 Just as, in general, well ordered species are produced by means of the two generating operations from primitive species (Brouwer 1926, p 451), so, in particular, mathematical proofs are produced by means of the two generating operations from null elements and elementary inferences that are immediatly given in intuition (albeit subject to the restriction that there always occurs a last elementary inference.) These mental [his italics] mathematical proofs that in general contain infinitely many terms must not be confused with their linguistic accompaniments, which are finite and necessarily inadequte, hence do not belong to mathematics.

" The preceding remark contains my main argument against the claims of Hilbert's metamathematics. A second argument is that the way in which Hilbert seeks to settle the question (which, incidentally, was taken over from intuitionism) of the reliability of the principle of excluded middle is a vicious circle; for if we wish to provide a foundation for the correctness of this principle by means of the proof of its consistency, this implicitly presupposes the pinciple of the reciprocity of the complementary species and hence the principle fo excluded middle itself (see Brouwer 1923c p. 252)[| Concerning this passage, Brouwer (1953, p.14. footnote 1) writes: "The equivalence of the principles of the excluded third and of reciprocity of complementarity mentioned there in a footnote by way of remark, subsequently has been recognized as nonexistent. In fact, as was also shown in the present paper the fields of validity of these two principles have turned out to be essentially different".|]." (van Heijenoort p. 460)

The way you read these quotes is the following:

(i) the first part is the "context" from van Heijenoort's reprint of Brouwer's paper: On the Domains of Defintion of Functions (1927)

(ii) the second part is the footnote ^8 at the bottom of van Heijenoort's page 460.

(iii) the third part [| Concerning this passage...|] is a parenthetic comment tacked onto Brouwer's footnote ^8 by someone, probably van Heijenoort or perhaps his translator Stefan Bauer-Mengleberg. Note that it references the 1953 paper and in this paper page 14 there's a "footnote 1" where Brouwer makes his comment (observation, retraction, whatever it is).

Interesting to note that this paper is so difficult that van Heijenoort takes 11 1/2 pges to preface it and the paper itself is only 6 pages long! I have no idea what the paper is saying. Brouwer is reinventing set theory, apparently. Here is the lead paragraph of van Heijenoort's introduction/explication:

"In a series of papers published from 1918 onward, Brouwer set forth an intuitionistic "set theory" and on this basis an intuitionistic reconstruction of point-set topology and analysis. The text below [is part of a paper published in 1927...and contains the proof that every function that is (in the intuitionistic sense) everywhere defined on the closed interval [0,1] of the continuum is uniformly continuous (Theorem 3). In the course of the argument Brouwer proves the fundamental theorem on "sets" that he later (1953) called the bar theorm, as well as its corollary , the fan theorem (Theorem 2)"(p. 446)

I checked the errata page (errata between 1st and 2nd editions) but none were pertaining to the footnote quotes. I hope this helps you folks make some sense out of this. wvbaileyWvbailey 01:17, 6 June 2006 (UTC)

I still can't make anything out of this. The equivalence of the two principles does not depend in any way on the assumption of bivalence. Under that assumption you get classical logic and then both hold, making equivalence completely trivial. If I saw the 1953 paper I don't remember it. Perhaps it might clarify the cryptic remark in the footnote, because Brouwer writes: "as was also shown in the present paper". But Brouwer's expository style is not always the most lucid. Some things he wrote are particularly unclear, and it is entirely possible that perusal of the paper will leave the question unanswered. In the absence of a clear understanding, it would appear best just not to refer to this "retraction" in the article. --Lambiam^Talk 08:12, 6 June 2006 (UTC)

I agree with you all the way. Until we see the paper we are at a loss, and I'm afraid that, as it is a mere parenthetic remark inside a footnote, the question will go unanswered. So to quote you: "In the absence of a clear understanding, it would appear best just not to refer to this "retraction" in the article".wvbaileyWvbailey 13:47, 6 June 2006 (UTC)

Equivalence of the generalization, versus generalization of the equivalence

May I go back to something that was said earlier: there is a difference between equivalence of the excluded middle and double negations as general rules on the one hand, and equivalence of individual assertions of each rule -- or, if you like, between equivalence of the generalization of each instance and generalization of the equivalence of each instance. So for instance "the law of the excluded middle can not lead to contradicton" might be written ~~(p v ~p), but (to abuse some second-order notation) are we really talking about $\neg \neg \forall P:(P\vee \neg P)$? Or are we actually talking about $\forall P:\neg \neg (P\vee \neg P)$?? Unfortunately it is not always made clear. I am not entirely sure I have made anything clearer either, or if this is worth mentioning at all...

For what it's worth, the latter is, to me, correct. In fact some "anti-classical" assumptions are defensible from intuitionist and indeed other constructivist points of view, and we would have families of propositions such that $\neg \forall x:(\phi (x)\vee \neg \phi (x))$, even though we also have $\neg \exists x:\neg (\phi (x)\vee \neg \phi (x))$! Or, if you like, the general law of excluded middle would actually be contradictory, even if there is no "specific-use" of it which is contradictory, because we can't go from not-all-are to some-are-not. Although from other (constructive) points of view, no anti-classical assumptions are necessary, even if not all classical assumptions are necessary. -Dan 15:28, 6 June 2006 (UTC)

If you have a cc of van Heijenoort's From Frege to Godel maybe there may be something of use in Kolmogorov page 431ff (esp p. 432). Whether this is the latest thinking I dunno. But there are lots of little quantifier formulas with "for alls" and 'does not exist" and etc etc. At the bottom of page 431 he writes something very cryptic (my bold-face):

§2. Generally, the propostions that we do not know how to prove without an illegitimate use of the principle of excluded middle ordinarily rest directly, not upon the principle of excluded middle of the logic of judgments, but upon another principle that bears the same name. In fact, from the principle of excluded middle in the form peculiar to the logic of judgments namely, "Every judgment is either true or false", we can obtain further conclusions by following the schema that corresponds to Hilbert's formula: if B follows from A as well as from ~A, then B is true. But in the case that interests us, that of transfinite judgments, it is difficult to obtain any positive conclusion B from the pure negation ~A; for that we must first transform the judgment ~A into some other (p. 432)

He then launches into "The following type of transfinite judgment is the most customary ...etc. etc." Here's where the fromulas similar to what you are writing appear here (the double negative gets mentioned re his formula (59)). If you want I can cc the rest tonight (it'll be a bit of a slog), right now I am supposed to be outside mowing the lawn. wvbaileyWvbailey

I wouldn't make you do that! Mowing the lawn is probably less unpleasant than all that copying. I dug up a copy, and yes, this is what I was talking about with not-all-are to some-are-not. Although "Not upon X but another principle that bears the same name" sounds almost like how Murphy's Law was not propounded by Murphy, but by another man of the same name.

He states that Hilbert believes that certain other principles "justify the application of the principle of excluded middle to infinite collections". In modern notation, these might be: $(\neg \forall x:\phi (x))\iff (\exists x:\neg \phi (x))$ (forward direction is his formula 59, reverse is 60), and: $(\neg \exists x:\phi (x))\iff (\forall x:\neg \phi (x))$ (forward 61, reverse 62).

He then goes on to prove, formally from even more basic principles, the second equivalence, as well as the reverse direction of the first equivalence. He only invokes double negation to prove the forward direction of the first equivalence (59). He asserts that any proof of that direction requires some such invocation. We might say: all X are not Y if and only if there is no X which is Y. We might also say: if some X is not Y, then not all X are Y. All these are proven by contradiction. (For instance for 60, a rough proof might be: assume that some X is not Y, and that all X are Y. Then some X is both Y and not Y! Impossible! Therefore, it follows that if some X is not Y, then not all X are Y -- and conversely he could also have deduced that if all X are Y, then there is no X which is not Y). But it is "illegitimate" for "transfinite judgement" to say if not all X are Y, then some X is not Y.

I had wanted to write about this too somewhere, probably under intuitionistic logic. -Dan 13:42, 8 June 2006 (UTC

I can't do this without examples, that's why I'm an engineer and not a mathematician. Last night I was mulling this over when I should have been sleeping:

We have the universes known and unknown with pigs p in them. One by one we examine these pigs p: We ask propose the proposition P(p) of each instance of our subjects p: "this pig p flies". To test our hypothesis we pick each pig up, one by one, and throw it. (Not very far: no animals are harmed in this experiment). After a while we begin to form a set/collection called "the universe of examined pigs". This collection is a subset of "all pigs seen and unseen throughout this and all other universes known and unknown". We find our subset/collection partitioned into two categories: "proposition p is true for subject p" i.e. P(p) and "proposition is not-true for subject p", i.e. ~P(p)". After a while (a really really long while) we believe that there is not a single instance of a pig anywhere in the universe that we have not examined, and not a single flying pig has been found (how do we arrive at this? I guess we ask an oracle I dunno). The "universe of examined pigs (all p):P(p)" has now the über-set (all p) i.e. it is identical to the transfinite set of "all pigs seen and unseen throughout this and all other universes known and unknown".

~[(all p):P(p)] =?: NO (all p):~P(p)

Had we found one, just one, we could assert that

(Exists a p):P(p)

But we didn't find a single flying pig p. So the proposition P that there exists a pig p and p flies (E p):P(p) is false=not-true. So does it make sense that:

~[(all p):P(p)] =? ~[(E p):P(p)] ?

I think it does <= Bill is wrong, see below

The right-most assertion ~[(E p):P(p)] asserts that "It's NOT TRUE that 'There exists a pig p that satisfies the proposition P(p) 'this pig p flies.' Does this imply that "there exists a pig that does does not fly?"

~[(E p):P(p)] -> (E p):~P(p)

I would think so. Altho the above form on the left seems to assert much more than the one on the right (it goes from the general (infinity) to the specific(an instance).

~[(all p):P(p]) -> (E p):~P(p)

ditto for the above form. [I need to mull this over more with my partitioned set].

What about the double negative?

"This assertion is not true: That after examinations of all pigs its not true that 'This pig flies'."

~[~[(all p):P(p)]] =? ~[(all p):~P(p)]

Something's wrong here: maybe between assertions "This [instance of] pig flies" and the generalizaton we are inclined to move to: "Pigs fly".

My mind is fried, I'll have to come back to this. wvbaileyWvbailey 19:35, 8 June 2006 (UTC)

Eh. In your notation ~[(all p):P(p)] means "It's not true that all pigs fly". This is VERY different from (all p):~P(p) which means "All pigs don't fly" -- they are different even in classical logic, or if you prefer, even in the finite world. This has nothing to do with the law of the excluded middle. I think you need to draw this out. Actually, I was very much thinking of drawing this out for intuitionistic logic... For the finite world (or, according to classical mathematics, in all cases), we can say:

1. There is no pig which doesn't fly = All pigs fly;
2. Not all pigs fly = There is (at least) one pig which doesn't fly;
3. Not all pigs don't fly = There is (at least) one pig which flies;
4. There is no pig which flies = All pigs don't fly.

In the transfinite world, the first three equivalences don't hold (the one on the right is a stronger statement), and the fourth equivalence still holds. We can make inferences from one line to another (e.g. [4] All pigs don't fly -> [2] not all pigs fly), but again, these inferences are also valid in the finite world/classical logic, and having nothing to do with LEM (and also, incidentally, [4] -> [2] depends on the assumption that there is at least one pig --- which is true for this example -- but that also has nothing to do with LEM). -Dan 20:21, 8 June 2006 (UTC)

I need to peruse your explanation when I'm fresher than I am now. But with regards to my bacon-on-the-wing example: Yes you are right: ~[(all p):P(p)] means that not all are flying but some or even none may be flying. Suppose we have a tiny finite set of three oinkers. Not all three are fliers:

~(P(p1) & P(p2) & P(p3)) = ~P(p1) V ~P(p2) V ~P(p3)

(I assume this equivalence is okay with the intuitionists because it is finite?)

~(a & b)= ~a V ~b

For the right side to be True only one of the terms ~P(pn) must be true.

~(P(p1) & P(p2) & P(p3)) = ~P(p1)=true V ~P(p2)=true V ~P(p3)=true

And for any one of these ~P(pj) to be true their respective P(pj) must be false.

~(P(p1) & P(p2) & P(p3)) = P(p1)=false V P(p2)=false V P(p3)=false

Thus any or all of the "P(pj)=false" must be true (!) and this means that there may be 0, 1, or 2 instances of flying pigs but not three instances of them.

The other case (all p):~P(p) means:

~P(p1) & ~P(p2) & ~P(p3) = ~(P(p1) V P(p2) V P(p3))

which means there is no instance whatever of a flyig pig, ie no instance of P(pj)=true.

Did I do this right? My question is: how do you draw this so it makes sense to anyone other than an expert? I agree this doesn't seem to have anything to do with LoEM but am not sure when relative to the double negative. My mind is still fried, will come back to it.wvbaileyWvbailey 23:53, 8 June 2006 (UTC)

Looks like you got it right, and just to be clear: yes, the equivalence is okay, because it is finite, i.e. the set of pigs is finite, and there is a finite decision procedure to definitely tell if any one of them flies (throw it). Both conditions are important.

How to draw it, even for the finite case? Good question. Maybe

| draw 3 pigs | 2 with wings, | 1 with,   | 3 without |
|  with wings |  1 without    | 2 without |           |
|                                                     |
|<---(1)----->|                                       |
|             |<---------------(2)------------------->|
|<----------------(3)-------------------->|           |
|                                         |<--(4)---->|

Corresponding to the 4 numbered equivalences above. Transfinite case? Haven't figured it out. My infinite drafting set got busted when I tried to draw ω^ω (no, seriously, that's really something I want to draw. The page has one for ω²). -Dan 02:34, 9 June 2006 (UTC)

The equivalence ~(a & b)= ~a V ~b is not an intuitionistic tautology. Here is a counterexample using Heyting algebra semantics. Take for the value of a the open half-plane {y : y > 0} and for b the open half-plane {y : y < 0}. Then a&b corresponds to the interior of the intersection of these two, which is empty and therefore already open. Its negation is the interior of the complement, which is the full plane and therefore already open. This is the value of "true". For ~a we need the interior of the complement of {y : y > 0}, that is, the interior of {y : y <= 0}, which is {y : y < 0} -- which happens to be the value of b. Symmetrically, ~b = a. Then ~a V ~b corresponds to the union of these two open half-planes, which is {y : y /= 0}. This is not the same as the full plane. At an intuitive level, knowing that a and b contradict each other, we have no way to point at one of the two and say: this one is false. --Lambiam^Talk 10:51, 9 June 2006 (UTC)

That is absolutely right. It is not valid in general. But these are necessarily infinite examples. For a finite example, in Heyting arithmetic, $(\neg \forall a\in \{1,2,...,99,100\}:a{\mbox{ divides }}b)\leftrightarrow (\exists a\in \{1,2,...,99,100\}:\neg (a{\mbox{ divides }}b))$ is a theorem. The reasoning is alright in this case because a) we are quanitifying over a finite set, and b) there is a finite decision procedure for each instance. Another way to think about the same thing is: assuming LEM, we have ~(a&b) <-> (~a v ~b); but with a finite decision procedure for a and b we don't need to assume LEM, we can prove the specific instances of it that we need (so I guess from that perspective, it is still related to LEM after all). -Dan 13:50, 9 June 2006 (UTC)

I see what Dan is up to and I think it's good. One thought I had relative to the one piggy that flies, is to draw a Karnaugh map (or Venn diagram) of { P, ~P }. Put one dot on the "P" side of the map for the piggy that flies, then color the "~P" side completely black except for the dot that is missing. Now, if we "go to infinity"-- that is, test all piggies in universes known and unknown, the dot gets smaller and smaller and eventually disappears into the page when the ink smears. Per Russell the role of induction in transfinite cases is -- to draw inferences based on probability:

(all days on earth):"on this day on earth sun rises in the east"

is only "true" in the probabilistic sense.

Which brings me to the role of induction in all this [?], and the fact that the LoEM seems to devolve into "philosophy" and into "semantics" or "meaning/definition".

Does anyone know what impredicate means? My dictionary doesn't have it and Google only pulled up 39 instances of drivel.

Lambiam's example above reminds me of my example of the logistic function:

Y = 1/(1+exp^(k*X))

This always has a center point Y=0.5 for X=0 no matter how large the value of k. So we see as k goes to infinity, the weird case of (infinity x 0) = 0.5. The derivative has a maximum or minimum at this point too.

An engineer-as-philosoper would argue that such a function as Lambiam has defined is perverse and unusable bcause it is undefined throughout the plane:

{y:y<0} U {y:y>0} <> whole plane

{y:y=0} is undefined

therefore {y:y<0} & {y:y>0} is undefined

The complement of the union is the value exactly at 0 which is undefined. So it cannot be used in a construction in which the undefined point becomes defined by accident. End of philospher's discussion. Me, being the devil's advocate here (the pay is lousy by the way), I am agnostic: Hence my question about what impredicate means. This was Godel's complaint (cf a quotation above).

To Lambiam's point about the equivalence, now that I am not so tired I see that: By PM's definition, a->~b =def ~aV~b . Ditto by PM's definition, a->a =def ~aVa, the LoEM. So if we don't accept ~aVa then we cannot accept a->a [is this true?] nor a->~b nor ~aV~b nor ~(a&b), all of which follow. Correct?

Does this all devolve into a problem with the definition of implication? Bear with me for a second: I remember when I first encountered "implication" I was stunned to see people defining "an operation of thought-as-logic" based on this definition. We are expected to accept both implications as true based on the assertion of a falsehood:

"The sun rises in the west" implies "my pig flies" OR

"The sun rises in the west" implies "my pig does not fly"

therefore: "The sun rises in the west" implies P(p) OR ~P(p) [LoEM ?]

which I don't have any trouble with, myself (the pig either flies or it doesn't). But:

"The sun rises in the west" implies "my pig flies" AND

"The sun rises in the west" implies "my pig does not fly"

therefore: "The sun rises in the west" implies P(p) AND ~P(p)

seems different. Once asserted the falsehood can "lead to" both a truth and a falsehood on/of the same propostion, simultaneously. [yikes where does this go?]

Interesting that one name for "implication" is "the conditional". My old college test (John Kemeny et. al. Finite Mathematical Structures, Prentice-Hall, Englewood Cliffs NJ 1958-59) defines it this way (his italics):

"Suppose we did not wish to make an outright assertion but rather an assertion containing a condition....[he gives examples here e.g. "If the weather is nice I will take a walk"]... Each of these statements is of the form "if p then q." The conditional is then a new connective which is symbolized by the arrow -->.

In figure 11a he shows a truth table, and the 2 cases (F, T) and (F, F) are filled in with question marks.

"Therefore we make the completely arbitrary decision that the conditional, p-->q, is true whenever p is false, regardless of the truth value of q... we give the conditional p-->q the "benefit of the doubt" and consider it true (see Exercise 1)" (p. 9: I underlined this with wiggly lines, way back in 1966)

Exercise 1 asks the student to fill in the question-marks and observe that no matter how they are filled in we end up with another connective's truth table, or our original propositions p, q etc. In other words, we have no choice but to fill in both of the condtional's question-marks with "true". There are only 16 possible truth tables, and this and its converse q-->p constitute "the last two remaining" truth tables.

But... Kolmogorov does not agree [?] with the "formalistic definition" (p. 420) of implication:

"Or, in the formalistic interpretation: if formula A is written down, we can also write down formula B [footnote 6 has a thing that looks like "G, G->F|F" written in German script that he attributes to Hilbert and to Sigwart]. Thus, the relation of implication between two judgments does not establish any connection between their contents.

" Hilbert's first axiom of implication, which means that "the truth follows from anything" results from such a formalistic interpretation of implication: once B is true by itself, then after having accepted A we also have to regard B as true. [etc] Kolmogorov in von Heijenoort p. 420)

Once again I am left more confused than when I started, e.g. was Kemeny expressing an intuitionist definition of implication? What is Kolmogorov trying to say? Is he for or against the formalist definition of implication? But if he accepts it doesn't he have to accept the LoEM? Under what conditions won't he accept the LoEM? Does "impredicate" have anything to do with this? (Maybe this confusion is okay: it shows what befalls semi-literate Wiki readers like myself when they confront :intuitionism", the LoEM, implication, etc).wvbaileyWvbailey 13:21, 9 June 2006 (UTC)

"Impredicate" might be impredicative. That's a whole other issue related to constructivism. And yes, I highly suspect a lot of people look at constructivism and go, what the **** is this ****? What's more I think I might have confused you with my comments. I am sorry. What I really meant to say before was: that sort of "truth table" thing worked only because we were in the finite pig pen. NO, a->b is NOT equivalent to ~a v b to an intuitionist. The latter is a stronger statement. Maybe it might help to have a look at BHK interpretation. Or maybe that just confuses things further.

a->a is ok (it is easy to go from a to a: you're already there), but a v ~a is not (which one is it?). I am starting to think we need a completely separate presentation of intuitionistic logic. It is clearly not good enough for that page to sort of refer back to classical logic and say "well, you know, kind of the same, but remove the law of the excluded middle..." -Dan 14:19, 9 June 2006 (UTC)

I found this on the web, this definition of "impredicative"

Torkel Franzen wrote:

"The Model-Based Mind" by Kercel, VanHoozer, and VanHoozer, citing Kleene, presents it as:

""An impredicative property, P(x), of an object x in X, is the property such that X is the set of objects possessing property P(x). In other words, an impredicative property participates in its own definition. Mathematicians do not deny the existence of impredicativities, [sic] but regard them as a necessary evil. Impredicativite [sic] processes, closed loops of causality and bizarre systems are equivalent concepts."

"" I guess it's inevitable that the logical term "impredicative" should inspire all sorts of extended or analogous uses. The above, however, is not at all correct applied to the use of "impredicative" in logic. An impredicative definition, in logic, is one that defines an object -typically a set - by means of quantification over a totality to which that object itself belongs."

What the hell is the difference between the two "definitions"? What kind of word is this "impredicativities"? Are angels dancing on pin-heds here? Is this just Russell's paradox in the buff? wvbaileyWvbailey 14:28, 9 June 2006 (UTC)

It's defining something in terms of a collection that it's supposed to belong to. Rather than defining objects before trying to define the collections which contain them. I'm not sure it's really relevant here... Maybe we can split that discussion to Talk:Impredicative to preserve at least a little bit of sanity. -Dan 14:45, 9 June 2006 (UTC)

After seeing the definitions I agree it isn't relevant to the LoEM, at least per my superficial level of understanding. wvbaileyWvbailey 16:56, 9 June 2006 (UTC)

The definitions of PM are irrelevant to the question whether something is an acceptable proof principle in intuitionistic mathematics, or a tautology in intuitionistic logic. The usual intuitionistic interpretation of implication, due to Kolmogorov, is: When we assert a → b, it means that we have a method to produce a proof of b, given a proof of a. Under this interpretation, whatever the statement a, it is trivially the case that a → a. Likewise, a V b means: we have a proof of (at least one of) a and b. It is clearly not the case that for every mathematical statement a we have a proof of a or a proof of not a, so an intuitionist is not in a position to assert a V ~a. In conclusion, a → a and a V ~a are in general very different statements.

PM is an attempt to reduce the notion of mathematical truth to a formal system of symbols. An important part of Brouwer's criticism was that even attempting such a reduction is completely unwarranted: (formal) logic is a branch of mathematics, just like arithmetic, algebra and geometry, and as such is not suitable to serve as a foundation of mathematics; any attempt to do so is circular wishful thinking. A principle of proof can not be justified by inventing a game with symbols in which it is one of the rules. This is putting the cart before the horse. Only after we have justified a proof principle should we include it in the rules of the formal game, if that game is supposed to model valid proof methods. --Lambiam^Talk 15:26, 9 June 2006 (UTC)

I think we're all on the same page now. Dan's explanations forced me to think with examples. And Lambiam's two paragraphs above explains what is going on very well. This is the best exposition I've seen of this: succinct and clear. Perhaps the should be embedded into the article? The only thing that is missing is the why with respect to transfinite proofs and the double negative (which sort of falls out once you understand that a-->a is not a V ~a for an intuitionist).

The following is a summary of my understanding so far:

IF we are intuitionists THEN:

We do accept a-->a AND/BUT we do NOT accept PM's LoEM "~a V a" and "a V ~a" for the reasons given below;

THEREFORE we do not accept either the PM derivation ~(~a)-->a from ~a V a (and vice versa) nor the derivation ~a --> ~a and a --> a from a V ~a (and vice versa) BECAUSE the derivations require use of (and thus imply) the rejected LoEM.[correct?]

Reasons for not accepting the LoEM:

The first reason: "It is clearly not the case that for every mathematical statement a we have a proof of a or a proof of not a, so an intuitionist is not in a position to assert a V ~a." This problem occurs [only? usually? primarily? always?] in transfinite proofs because of the following ...[need succinct explanation here re reasoning that draws a truth from a negative/false outcome[?] ].

The second reason: "PM is an attempt to reduce the notion of mathematical truth to a formal system of symbols. An important part of Brouwer's criticism was that even attempting such a reduction is completely unwarranted...etc"

AND finally: an intuitionist's cure for this state of affairs is the following:

[I draw a blank here: is it Kolmogorov's restated axioms? New definitions of what constitutes "a proof?" Unresolved?]

wvbaileyWvbailey 15:12, 10 June 2006 (UTC)

For Lambiam: I owe you some input on what you've written; I like it and think it is excellent. It probably does belong in intuitionism, but on the other hand the LoEM and intuitionism are so intertwined that a person reading about intuitionism would need some grounding in what the LoEM fuss is all about. Probably the LoEM article could then be trimmed.

With reference to citation/attribution and support: I need to learn more about Brouwer et. al. I will have to go hunting for his biography or whatever is written about him (Do you know of one? Any good historical reading re the development of intuitionist logic? By the way, how did you come to learn so much about Brouwer and intuitionism?). I want to probe backward and learn what caused Brouwer's philosophy to diverge so much from that of Hilbert + Russell-Whitehead. Something like this with more links drawn:

? --> Kummer --> Kronecker --> Brouwer --> Weyl, Kolmogorov -->?

? --> ? Leibniz --> Boole --> Peirce --> Frege + Peano + Whitehead --> Hilbert, Poincare --> Russell --> PM

? --> "analysis" --> ?

? --> Cantor --> ?

In fact as I am sitting here typing this I have been thumbing through Dawson's chapter III Excursus (p. 37ff) that gives a brief history of the development of logic; he starts it with: (lo and behold!) Aristotle and the LoEM! His exposition parallels the little chart above that I gleaned from the references in the back of van Heijenoort.

I did find some support of what you've written in Encyclopedia Britannica in the article titled "Analysis". I'll paste this into a section following your exposition. And other support as I find it. wvbaileyWvbailey 12:53, 15 June 2006 (UTC)

Lambiam's exposition

What counts as an acceptable proof method to intuitionists will necessarily always remain a bit vague, as these issues precede any attempts at formalization. In fact, not all intuitionists agreed or agree on all aspects; see for example the article on Ultrafinitism. Most would agree, though, that intuitionistic logic faithfully internalizes the propositional aspect of intuitionistically acceptable mathematical reasoning, and so will accept a valid theorem in that logic as being also a valid theorem schema in mathematics itself. In many ways intuitionistic type theory has gone further, extending the scope of the formal-logical approach. In general, the methods of constructive mathematics are also acceptable to intuitionists, and some people even identify intuitionism with constructivism in mathematics.

Intuitionists accept P V ~P for any specific proposition P whose truth or falsehood has been demonstrated. Furthermore, they accept this for classes of propositions for which an effective method is known for testing whether they hold. For example, consider the class in which P takes the form X = Y in which X and Y are arithmetic formulas involving only numerals and the familiar arithmetic operations. To test the validity of such a P, just evaluate the two sides of the equation and check whether they are the same. If such a test is not (known to be) available, usually the problem involves, so to speak, to test an infinity of cases, and no known reasoning allowing us to reduce this infinity to a finite number of effectively testable cases. A well-known example is Goldbach's conjecture. For many classes of formally infinite problems an effective (and therefore finite) test procedure is known, however, and then intuitionists will gladly assert P V ~P for these classes. What counts as effective to intuitionists, and which effective procedures count as true tests, will necessarily always remain a bit vague; see above.

Intuitionists can look at PM derivations in two ways. One is that the logician is playing a game with self-invented rules, like peg solitaire but more complicated, and then they can look at the process and verify that the logician is not cheating. Just as for peg solitaire, this has nothing to do with notions of truth. They can also look at this game, bearing in mind that the logician claims the symbols mean something and allow the game player to express truths. Then there are many potential problems, some having to do with what counts as an acceptable definition (for example of notions like function and real number), some with the range of quantifications, some with the validity of inference rules, and some with the axioms. What these objections have in common is that intuitionists believe that the use of unreliable definitional approaches, unreliable inference rules and unreliable axioms does not offer a reliable way for examining the truth of mathematical claims. Clearly, derivations assuming LoEM or using double negative elimination are not considered kosher. Intuitionists will consider a PM derivation of a → a from a V ~a as a good example of how you can occasionally and accidentally reach correct conclusions using unreliable methods.

The "cure" intuitionists would prescribe to the mathematical ailment of unreliability is: Use only methods whose reliability has been established. What is reliable and what not, is open to discussion, as is the question what constitutes sufficient evidence or justification. But if, in order to justify a principle, you need to resort to a circular argument, you have failed to establish reliability. Also, the argument that something has a respectable pedigree harking back to Aristotle, is believed to be sound by more than five million mathematicians, and has not failed thus far in any case where it was applied, is unacceptable.

I'm not sure how much detail of this (assuming proper citations) should be presented in the article Law of excluded middle. If it should be presented at all, then the article Intuitionism may be a better place. --Lambiam^Talk 18:16, 12 June 2006 (UTC)

Citations, comments etc on the above

References:

"analysis." Encyclopædia Britannica. 2006. Encyclopædia Britannica 2006 Ultimate Reference Suite DVD 15 June 2006, "Constructive analysis" (Ian Stewart, author)

Goldstein, Rebecca, Incompleteness: The Proof and Paradox of Kurt Godel, Atlas Books, W.W. Norton, New York, 2005.

Rosenbloom. Paul C., The Elements of Mathematical Logic, Dover Publications Inc, Mineola, New York, 1950.

Anglin, W. S., Mathematics: A Concise history and Philosophy, Springer-Verlag, New York, 1994.

Encyclopedia Britannica:

Stewart's reference in E.B.:

"Errett Bishop and Douglas Bridges, Constructive Analysis (1985), offers a fairly accessible introduction to the ideas and methods of constructive analysis."

"Constructive analysis

"One philosophical feature of traditional analysis, which worries mathematicians whose outlook is especially concrete, is that many basic theorems assert the existence of various numbers or functions but do not specify what those numbers or functions are. For instance, the completeness property of the real numbers tells us that every Cauchy sequence converges, but not what it converges to. A school of analysis initiated by the American mathematician Errett Bishop .... This philosophy has its origins in the earlier work of the Dutch mathematician-logician L.E.J. Brouwer, who criticized “mainstream” mathematical logicians for accepting proofs that mathematical objects exist without there being any specific construction of them (for example, a proof that some series converges without any specification of the limit which it converges to). Brouwer founded an entire school of mathematical logic, known as intuitionism, to advance his views [italics and boldface added]

"However, constructive analysis remains on the fringes of the mathematical mainstream... Nevertheless, constructive analysis is very much in the same algorithmic spirit as computer science, and in the future there may be some fruitful interaction with this area" (Britannica Analysis/Constructive Analysis)

wvbaileyWvbailey 13:10, 15 June 2006 (UTC)

W.S. Anglin’s exposition

In his Chapter 39. Foundations, Anglin has three sections titled “Platonism”, “Formalism” and “Intuitionism”. I will quote most of “Intuitionism”. Anglin begins each as follows:

”Platonism

”Platonists, such as Kurt Gödel, hold that numbers are abstract, necessarily existing objects, independent of the human mind” (p. 218)

”Formaism

“Formalists, such as David Hilbert (1862-1943), hold that mathematics is no more or less than mathematical language. It is simply a series of games...” (p. 218)

”Intuitionism

”Intuitionists, such as L. E. J. Brouwer (1882-1966), hold that mathematics is a creation of the human mind. Numbers, like fairy tale characters, are merely mental entities, which would not exist if there were never any human minds to think about them.

”Intuitionism is a philosophy in the tradition of Kantian subjectivism where, at least for all practical purposes, there are not externally existing objects at all: everything, including mathematics, is just in our minds. Since, in this tradition, a statement p does not acquire its truth or falsity from a correspondence or noncorrespondence with an objective reality, it may fail to be ‘true or false’. Thus intuitionists can, and do, deny that, for any mathematical statement p, it is a logical truth that ‘either p or not p’.

”Since intuitionists reject objective existence in mathematics, they are not necessarily convinced by the reasoning of the form:

”If there is not mathematical object A, then there is a contradiction; hence there is an A.

[I found this confusing. Does he mean: There exists B: (~A -> ~B) & B -> A [?]]

"If the details of the reasoning provide a way of imagining or conceiving an A, in a way open to ordinary human beings by, say, calculating it in a finite number of steps), then the intuitionist will agree that there is, indeed, an A. However, if the details of the reasoning do not provide this, the intuitionist will remain skeptical. For a Platonist, it is of interest that there is an A even if it is only God who can conceive it. For an intuitionist, however, a mathematical object is meaningless unless it can be somehow ‘constructed’ and ‘intuited’ by a human being.

"For the intuitionist, the human mind is basically finite, and Cantor’s hierarchy of infinites is just so much fantasy. Intuitionists thus reject any mathematics which is based on it, including most of calculus and most of topology.

"... To ... objections, the intuitionist can replay: (1) it does not make sense for human minds to try to conceive a world without human minds, and (2) it is better to have a small amount of mathematics all of which is solid and reliable than to have a large amount of mathematics, most of which is nonsense”(p. 219)

Find irrational a and b such that a^b is rational

From the article: “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 [a=$\sqrt{2}^\sqrt{2}$] is irrational but there is no known easy proof of that fact.)" (Davis p. 220)

I’m not question the fact that Davis has reported this statement and as such I’m not criticizing the accuracy of this encyclopedic article. However, I like to call attention to the apparent fallacy that this statement seems to imply. The statement seems to imply that since [$\sqrt{2}^\sqrt{2}$] is in fact irrational (with no easy way to show it), the proof is also incorrect (presumably with no easy way to show it). This implication is simply not true and the wording of the statement is misleading. To see this, go back to the original problem and read it as “prove there are irrational numbers a and b such that $a^b$ is a positive integer”. The proof is still applicable despite the fact that it is quite easy to show that [a=$\sqrt{2}^\sqrt{2}$] is not an integer. Whether [a=$\sqrt{2}^\sqrt{2}$] is an integer, a rational, or an irrational number (and how easy or difficult it is to show that fact) has nothing to do with the logic of the argument.

My only criticism of the article is that if this example is meant to show that that are problems with the non-constructive proof over the infinite, then neither the example nor Davis’s criticism of the example is applicable. In fact, there are logical problems with such “proofs”, but this example is not one of them. —The preceding comment is by Zaquaraya (talk • contribs) 10:50, May 9, 2007 (UTC): Please sign your posts!

Why should the fact that ${\sqrt {2}}^{\sqrt {2}}$ is irrational imply that the proof (which proof exactly) is incorrect? A constructive proof of the existence of irrational a and b such that a^b is rational that uses the fact that the square root of 2, raised to itself, is irrational, must contain a proof of this irrationality. The given proof does not, and can therefore not be called constructive. The known (not-easy) proof of irrationality is in fact based on the Gelfond–Schneider theorem; it is doubtful that the proof of that theorem is constructive, and it may not be easy to make it sufficiently constructive that it can be contained in another proof without losing constructivity for the larger proof.  --Lambiam^Talk 11:56, 9 May 2007 (UTC)

I withdraw my criticism. I misunderstood Davis’s statement on the first reading. In fact, he is saying that not only the conjecture is true by the proof of existence that was given, but also by construction—i.e. the two irrational numbers that satisfy the conjecture are $a={\sqrt {2}}^{\sqrt {2}}$ and $b={\sqrt {2}}$, alas with no easy way to show that $a$ is in fact irrational. Zaquaraya 03:41, 10 May 2007 (UTC)

Argument map representation

I am thinking of adding a visual representation of the simple deductive schema of excluded middle to this page. Image:Anonymous Lefty excluded middle.png. It is a real example of an informal argument, see here. Any thoughts? - Grumpyyoungman01 00:29, 20 May 2007 (UTC)

It is a good example of a fallacious argument, but what would it be doing here? Do you really want to point out the hidden assumptions in the example making it an informal fallacy (such as that the reduction in danger, if real, is due to the leadership of these man; or more egregious, that only these men can protect us against evil if it hasn't been subdued)? This is not the place to bring in political convictions. But if the fallacy is not exposed, it may be even more confusing; readers would think it is a formal fallacy due to the application of the Law. Since, in the example, the application of LEM is just the capstone on a crumbling construction, and the fallacy is in that construction, it is not clear what this would illustrate. It is not truly a "real example", since it is clearly presented in irony by Mr. Sear. In choosing examples, it is best if they do need no explanation and don't draw on the political nonce; sooner than you think, younger readers will say: "Who the **** is Tony Blair?"  --Lambiam^Talk 06:36, 20 May 2007 (UTC)

Thanks Lambiam, one thing I am not sure of is on which article to put this image if it were appropriate. This does seem like the wrong place and maybe nobody has as yet created the fallacy(argument) page. You should also be aware of the NPOV dispute about the image on its talk page. - Grumpyyoungman01 11:59, 20 May 2007 (UTC)

Since you ask, I don't think it would be appropriate anywhere (except perhaps, if Mr. Sear's blog was notable enough to merit an article, to explain the point made to the ironically challenged – but even then I would have my doubts). I don't really see what fallacy or whatever the diagram is supposed to illustrate, but nevertheless, whatever the fallacy may be, I'm fairly convinced this diagram is not a good illustration of it.  --Lambiam^Talk 12:50, 20 May 2007 (UTC)

I better correct something here, I obviously wasn't paying attention. It is not a fallacy, but may appear that way because the premises are not backed up by other premises (the whole argument is not fully fleshed out). I have the argument form written down as a simple deductive schema of excluded middle. Does this argument pattern have its own article? If not I will start it and use the image keeping the Ps and Qs and ditch the other stuff. In summary this is not supposed to represent a false dilemma but a true one. - Grumpyyoungman01 23:21, 20 May 2007 (UTC)

Yes, mind your Ps and Qs. Is this particular form of dilemma notable? You can't just start a new article on an argument pattern and invent your own name for it. The topic of an article has to enjoy a certain notability as such, the first sign of which for this would be a name commonly understood to mean this specific argument pattern. This form of the dilemma is found in that leading to the implicit conclusion of the common saying "Damned if you do, damned if you don't". (Take P = "do" and Q = "damned".) (In Wikipedia, Damned if you do, damned if you don't redirects to Catch-22 (logic), an article – whose own logic is severely impaired – that displays a quite different argument as being "Catch-22".) This form of the dilemma is also the pattern of the nonconstructive proof of the theorem "There exist irrational numbers a and b such that a^b is rational" also found in this article. And it is given in symbolic form in the article on Philosophical skepticism as the form of Thomas Reid's argument against skepticism. There Reid's argument is called "a dilemma, like this: if P, then Q; if not-P, then Q; either P or not-P; therefore, in either case, Q." I don't know a name for this particular form, and I'd think that if there was a common name for it, one of the editors at the Philosophical skepticism article, and before at Skepticism, would have known and supplied that name in the now almost six years this text has been with us.[1]

What I think you could do, if you feel up to it, is replace the current redirect page at Damned if you do, damned if you don't by a somewhat decent, if still stubby, proper article, and add a Rationale diagram as illustration. If you choose to do that, then you should (in my opinion) substitute P = "Damned" and Q = "Do" in the diagram at Image:Anonymous Lefty excluded middle.png, and, moreover, leave out the first of the three bottom boxes, since "P or not P" is not an assumption of the argument.  --Lambiam^Talk 05:07, 21 May 2007 (UTC)

Done!, although it needs copyediting and references, not quite quality yet. Thanks for your input. - Grumpyyoungman01 10:10, 21 May 2007 (UTC)

Schrodinger's catscrawl

> "Every judgment is either true or false"

...or some dirty quantum-mechanicist just wrecked your nice philosophy book, because the subject of the judgement may be factually green or red or both at the same time or not even God knows what.

Therefore I think quantum mechanics should deserve a mention in this article as a sign of contradiction. Physics is applied maths, so it is a valid connection. 81.0.68.145 21:07, 15 September 2007 (UTC)

What middle is excluded?

I added a sentence under "Examples" to clarify what the "middle" is that is being "excluded":

That is, the "middle" possibility, that Socrates is neither mortal nor immortal, is excluded by logic, and therefore either the first possibility (Socrates is mortal) or its opposite (Socrates is not mortal) must be true.

I added it because I can't find any explanation of what the words "excluded middle" actually refer to. Improvements, and perhaps additional wording in the intro, are of course welcome. — Loadmaster (talk) 21:49, 6 February 2008 (UTC)

I think this was a good addition (with the subsequent minor emendations). The statement of Aristotle's is good too -- I'm quoting this from the article:

[Aristotle] 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.

Bill Wvbailey (talk) 15:46, 7 February 2008 (UTC)

LoEM eqivalence?

Is there a logical difference between the statement "A proposition MAY NOT be BOTH true and false" and "a proposition MUST be EITHER true XOR false" ? IOW, is there a logical difference between prohibiting "Socrates is BOTH mortal AND immortal" and prohibiting "Socrates is NEITHER mortal NOR immortal" ?? I'm not a logician. I'd just like a clarification here, because I'd always heard LoEM was the former and this entire article clearly states it is the latter. Thanks. roricka 2/15/09

There certainly is a difference. You may be interested to read the articles on dialethism and related matters —Dominus (talk) 09:13, 15 February 2009 (UTC)

Humour

The law has well been stated as "that that is is that that is not that that is not that that is". I would kinda like that included, but this is a very serious article and not sure it belongs here.

SimonTrew (talk) 17:35, 24 February 2009 (UTC)

Principia-style notation

A well-meaning editor recently changed several formulas like this:

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

to formulas like this:

($\forall$ x)[f(x) ∨ ~f(x)]

But this is not correct. The passage is a quotation from Reichenbach, and should be quoted verbatim. Reichenbach is quoting Principia Mathematica, and the Principia Mathematica notation for universal quantification of a variable x is indeed (x), the $\forall$ symbol not having been invented yet.

The following paragraph explains the old notation anyway, so I have changed it back. —Dominus (talk) 13:44, 2 April 2009 (UTC)

Not sure I totally agree with you. Surely some of the other logic symbols had not been "invented yet" either. I don't see that simply changing a symbol changes the meaning or substantially makes it a misquote. I would see a parallel in changing caps in a quote— generally advised against, but if it made sense I don't think many would object.

I would suggest perhaps move the definition of (x) i.e. "for all" or "for every" above the formula itself, that way it does not stay a puzzle until one reads the following sentence. SimonTrew (talk) 13:52, 2 April 2009 (UTC)

I'm not sure I agree with me either. I found it jarring to see a mixture of old- and new-style notation. On the other hand, a fully PM-style expression would look rather different, and might be unintelligible to modern readers. —Dominus (talk) 14:51, 2 April 2009 (UTC)

Intro - question

A question about the definition chosen in the intro, "is the principle that for any proposition, either that proposition is true, or its negation is." Why not state "either that proposition is true, or false." ? I ask because this would seem to drag things into requiring a definition of "negation"? CecilWard (talk) 17:40, 9 December 2009 (UTC)

The statement "a proposition is either true or false" is not the Law of Excluded Middle, it is the Law of Bivalence. The point of the Law of Excluded Middle is that a statement and its negation must always have opposite truth values. There can never be a situation where 'P' and 'not P' are both true. 128.135.4.56 (talk) 21:54, 22 February 2010 (UTC)

Non-intuitionist philosophies that do not allow for an excluded middle?

Are there Wikipedia articles about philosophies that do not allow for an excluded middle? (or N+1th?) Thanks. 76.202.63.148 (talk) 12:11, 29 June 2010 (UTC)

exclusive or or inclusive or?

When the law of the excluded middle is stated as "p or not p" are we using inclusive or exclusive or? (At some point we intend to add that it can't be both true and not true but is that included in this axiom or do we use inclusive or and have the separate non-contradiction law as well?) RJFJR (talk) 16:40, 30 June 2009 (UTC)

(i) The LoEM is invoking the inclusive OR, not exclusive OR. Hence the special paragraph that discusses this issue re Reichenbach's take on it.

(ii) Bertrand Russell considered these "axioms" to actually be 'Laws of Thought' or 'general principles' where these laws/principles are "self-evident"; I take this to mean they are derived from observation, as does Russell. Russell named them as follows

"For no very good reason, three of these prinicples have been singled out by tradition under the name of 'Laws of Thought'.¶ They are as follows

"(1) The law of identity

'Whatever is, is.'

"(2) The law of [non]contradiction

'Nothing can both be and not be.'

"(3) The law of excluded middle

'Everything must either be or not be.'

" . . . the name 'laws of thought' is also misleading, for what is important is not the fact that we think in accordance with these laws, but the fact that things behave in accordance with them; in other words, the fact that when we think in accordance with them we think truly. But this is a large question . . ." (p.72-73 in Russell, 1912/1999, "The Problems of Philosophy", Oxford University Press, NY, ISBN 0-19-511552-x).

My take on the exclusive-OR issue is this: that to invoke it is to invoke both laws (2) and (3) at the same time. wvbaileyWvbailey (talk) 19:00, 30 June 2009 (UTC)

With all respect, Bertrand Russell managed to give an ill formulation of the law of the excluded middle. It should be formulated as: 'Nothing can neither be nor not be.' which corresponds with the formulation of the law of noncontradiction. From this formulation together with his formulation of the law of noncontradiction it can be deduced that 'everything must either be or not be' (exclusive OR). (sorry, I made a bit of a mess) [Sarahcroft] 81.47.114.254 (talk) 19:05, 18 August 2010 (UTC)

Read the section 4 "A Historical perspective" a few sections above this one and look closely at the drawings. Morton Shumway and I delved as deeply into the history about as far as mankind should go (it's kind of like Dante's journey into Hell). What we discovered is that the LoEM has had a checkered past -- not all philosophers §have agreed with its inclusion in "the Laws of Thought". The intuitionists will accept the form FOR ALL p: ~(p & ~p), but not the form FOR ALL p: (p V ~p).

What really is the problem, the source of the trouble, is the "Law of double negation" (e.g. Kleene 1952:119 formula *49). The problem arises when we assert FOR ALL p: ~~p is p, and the FOR ALL extends over all p in the entire universe (not a bounded universe of discourse but rather the entire universe of existence). If you attempt to draw this out as a Venn diagram, you will see that ~p (all that which is not a p or doesn't have the property p) is not the customary bounded box that you blithely label "universe of discourse"; rather, it is an unbounded cloud of uncertainty extending off your paper all the way to infinity. A cautious (non-idealist, non-Platonist) thinker has a pretty hard time convincing themselves they've captured all that this universe-minus-p contains, especially if the universe is expanding and/or is creative. So when you (re)assert p from ~(~p), and if your universe has expanded or been creative, you may end up including a few unexpected things (probably from the outer edges of your expanding universe, but maybe from something creative well inside the expanding outer edges) that you didn't have in your original set p. Whether or not you accept this argument against the LoEM depends entirely on your philosophic outlook, and few folks today give this much thought (they accept that FOR ALL p: p V ~p). Bill Wvbailey (talk) 22:54, 18 August 2010 (UTC)

The question concerning the validity of the law of excluded middle should not be confused with the question of the validity of the "completed (actual) infinity", as you seem to suggest. Thus, Errett Bishop accepted the completed infinity of the integers, as well as the validity of the law of excluded middle for effectively computable predicates over such a completed infinity. Numerous philosophers have made the error of thinking that LEM is problematic because it is being applied over an infinite domain. This is too simplistic. Please let's not add to the confusion by perpetuating this misconception. Tkuvho (talk) 15:19, 19 August 2010 (UTC)

What you wrote could not be more incorrect. This is from Kleene 1952:48 (1991 impression) re his section §13 INTUITIONISM pages 46-53: "Brouwer's non-acceptance of the law of the excluded middle for infinite sets D does not rest on the failure of mathematicians thus far to have solved this particular problem, or an other particular problem. To meet his objection, one would have to provide a method adequate in principle for solving not only all the outstanding unsolved mathematical problems, but any others that might ever be proposed in the future. How likely it is that such a method will be found, we leave for the time being to the reader to speculate." Besides Brouwer and Weyl, other important mathematicians who took this matter seriously were Hilbert and his associates, Goedel, and Kleene. (Kleene's book has been reprinted in paperback recently; I assume you have a copy but just haven't read the relevant Chapter III A CRITIQUE OF MATHEMATICAL REASONING pages 36-65.) Bill Wvbailey (talk) 17:15, 19 August 2010 (UTC)

You should not conflate intuitionism and constructivism. The figures you mentioned are certainly all great mathematicians. None of them would dispute the fact that modern constructivism accepts completed infinity, as well as LEM over it under certain circumstances. The view that everything boils down to potential versus completed may make for breathtaking philosophy, but it is an oversimplification (based on a single source) nonetheless, one that still needs to be sorted out at Brouwer-Hilbert controversy. Tkuvho (talk) 17:28, 19 August 2010 (UTC)

I've lost your thread. How/why did constructivism enter the discussion? It's all about the LoEM -- whatever it is that you believe is "the truth about the LoEM" is irrelevant to what is in the published literature. Please read the Kleene 1952 chapter III cited above; then we'll continue this discussion. BillWvbailey (talk) 22:15, 19 August 2010 (UTC)

Law or Principle?

"In logic, The law of excluded middle, also known as the Principle of excluded middle or excluded middle [...]"; apparently philosophers do not really appreciate the difference between a law and a principle. A 'principle' in its original meaning can be stated as a 'origin' (c.1380, "fundamental truth or proposition," from Anglo-Norm. principle, from O.Fr. principe, from L. principium (pl. principia ) "a beginning, first part," from princeps (see prince). Meaning "origin, source" is attested from 1413. Sense of "general rule of conduct" is from c.1532. Used absolutely for (good or moral) principle from 1653). Without talking about the truth or falsehood of the law of excluded middle, its formulation should be constructed by defining this middle ("neither P nor not P") and then exclude this middle. Hence, the formulation 'nothing can neither be nor not be'. This formulation is based upon the concept 'nothing' and therefore does not presuppose 'anything', that is, it is the most elementary way of formulating and can be considered the Principle of excluded middle. However, Bertrand Russell’s formulation ('everything must either be or not be') is based upon the concept 'everything' and should therefore be seen as a law instead of a principle. Also, the formulation "FOR ALL p: (p V ~p)" appears to encode a law derived from the principle of excluded middle but does not formulate the principle of excluded middle itself. A lot of philosophical confusion would most probably be avoided if this difference was pointed out more clearly. Sarahcroft (talk) 15:43, 25 August 2010 (UTC)

Pls read the history above (where the drawings are). From Aristotle on down all are confused about what we should call the LoEM because there are many ways it has & can be stated, and there are at least two different contexts in which it can be stated: the finite-set-theoretic where we can examine each element to see if it is a p or a ~p, and the completed-infinite set-theoretic where we cannot. Starting with Aristotle, it's been called "a Law of thought", "the maxim of Excluded Middle, "an axiom of Logic", "a Rule of thought", "a principle of reasoning" etc etc. Nowadays, for the mathematician/logician, it's an "axiom of Logic" (given they choose to include it in their axiom-set, as the intuitionists are NOT inclined to do) . But for the empirically-minded philosopher it is a "Law of Nature" (i.e. a "natural law") based as it is on repeated, accumulated experience, so-called "inductive reasoning". BillWvbailey (talk) 22:29, 25 August 2010 (UTC)

In medieval Scholasticism, the University masters were under oath to maintain that God can do absolutely anything except that... A testament to the value they placed on logic (and possibly still church doctrine?) I'd think a deity who can't manage a simple contradiction might consider a more suitable career. Work in mysterious ways smarter, not harder: p and ~p therefore whatever QED—Machine Elf 1735 (talk) 09:18, 14 November 2010 (UTC)

Notice

There is a substantive discussion about this article (and what might be wrong or confusing with it) at Talk:Principle_of_bivalence#Musing_about_LoEM. Tijfo098 (talk) 01:07, 16 April 2011 (UTC)

Just reading the lead here, the wiki article contradicts itself. Tijfo098 (talk) 01:09, 16 April 2011 (UTC)