Talk:Law of excluded middle

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

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 diffrent interoretation 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 that 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?