Talk:Gödel's incompleteness theorems/Archive 3

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

Because of their length, the previous discussions on this page have been archived. If further archiving is needed, see Wikipedia:How to archive a talk page.

Previous discussions:

Re: Gödel's Incompleteness Theorems - A Brief Introduction

Hey, User:Paul_August, I am curious what fault you found with the article at http://www.mind-crafts.com/godels_incompleteness_theorems.html that made you remove the link to it I put in External Links. I have to confess that IMHO it's the best non-technical introduction to Gödel's theorems on the Internet. 66.217.176.211 16:55, 16 November 2006 (UTC)

Paul, actually, I took a brief look and (at least at that level of scrutiny) it does look pretty good. We don't want to encourage link farming but this one really might be worthwhile. --Trovatore 03:52, 27 November 2006 (UTC)

OK, I restored the link - since no arguments were given against it. Will be happy to listen and discuss if anybody comes up with cogent args. 66.217.179.50 22:45, 3 December 2006 (UTC)

Removal of Godel's statement of theorem

I removed Godel's original statement of the theorem, but it's been reverted back. Godel's statement:

To every ω-consistent recursive class κ of formulae there correspond recursive class signs r, such that neither v Gen r nor Neg(v Gen r) belongs to Flg(κ) (where v is the free variable of r).

is only meaningful if you explain Godel's notation (e.g., class signs, Gen, Neg, and Flg), which we don't really need to do in this article. Perhaps for historical interest, we can have all this in its own section of the article, but it's not useful where it stands now and will just mystify most people. If there are no objections, I'll remove it again soon. -SpuriousQ 09:55, 27 November 2006 (UTC)

Obviously, I disagree or I would not have reverted you. You took out a section header which is inappropriate. And the formal statement of the theorem may be of interest to some people, such as those who have read the paper. If you think that it is too advanced a topic, the appropriate course is to move it to the end of the article and add more explanatory material. JRSpriggs 10:29, 27 November 2006 (UTC)

Thanks for the explanation, JRSpriggs. The section header was removed because it was introducing the deleted content and didn't make sense without it. As for the content itself, I don't think it's a matter of the topic being "too advanced"; it's that it's unreasonable for us to expect our audience to have read Godel's paper (with the German abbreviations intact, at that). As stated right now, I feel it does more harm than good, especially given the recent remarks about the article's accessibility. Like you suggest, a possible solution would be to move it to the end with more explanation, which I would be happy with and may attempt when I get a chance. -SpuriousQ 16:12, 27 November 2006 (UTC)

With respect to JR, I tend to agree with Spurious here. Gödel's proof was brilliant; his notation, like almost all version-1.0 notation, was less than ideal from the point of view of long-after-the-fact exposition. And even if the notation were nicer, we still should not want to get into the details of a specific coding scheme early in the article, as it's kind of beside the point. --Trovatore 16:27, 27 November 2006 (UTC)

The bizarre proof sketch

How can you say that P(x) can be proved if x is the Gödel number of a provable statement explicitly explaining in the previous paragraph that the Gödel numbers encode single-parameter formulas, which are not statements and, therefore, cannot be proved or disproved? In other words, the concept of "provability" is inappropriate to F when we rewrite P(x) as P(G(F)). --Javalenok 02:17, 6 January 2007 (UTC)

A given Gödel number might encode a single-parameter formula, or any other formula, or a statement. I've made an edit that I think might clarify a bit; does it address the problem you see? If not, can you be more specific about what text you see the problem in? Thanks in advance! —Ruakh_TALK 06:49, 6 January 2007 (UTC)

At first, reading this article and the Gödel number, I have got the affirmation that a given Gödel number encodes a formula. The mapping one-to-one at that. Therefore, it seems that you are wrong when telling that a number (a means one in english) encodes a form or another form. It encodes only one form but not another. Secondly, since x is a natural number, a form generates an infinite number of statements. That is, infinitely many statements F(x) conform to a form F. Taking into account that the notion of proof does not apply to the forms, we are precluded from defining the decider P(G(F)). The decider must be provided with a statement; i.e., both the number of F and x. --Javalenok 13:15, 6 January 2007 (UTC)

Sorry, you misunderstood me. I didn't mean that a Gödel number might simultaneously encode all of those things; I meant that a given Gödel number could be a Gödel number that encodes a single-parameter formula, or a Gödel number that encodes a formula of some other type, or a Gödel number that encodes a statement.

Also, the article does not use the term decider and does not make reference to P(G(F)), so I don't know what you're referring to. Can you quote a specific sentence from the article so I can see what you're objecting to?

—Ruakh_TALK 19:41, 6 January 2007 (UTC)

To Javalenok: Please do not remove the messages of other editors (unless they are vandalism, libel, obscenity, etc.). Also do not remove your own prior messages if they provide context to another user's messages. If you like, you may strike-out the parts of your messages with which you no longer agree using <s> and </s> (having this effect ~~and~~ ). Consequently, I have restored the messages by Ruakh and yours which provide context. JRSpriggs 07:35, 9 January 2007 (UTC)

Sorry my fussiness, I have overlooked in the beginning that statements can also have Gödel numbers. Before this discussion will be deleted, please explain why do you substitute the Godel number x by formula F(G(F)) in P(x)? The formula is not a number. The grammatically correct statement would be P(G(F(G(F)))). Furthermore, the substitution of variable x in P('x') by the number of statement p turns the form into statement and its number changes accordingly. But the resulting statement is p, so its number 1)must be fixed; and 2) known in advance!!! Where do we get the number from? --Javalenok 20:33, 11 January 2007 (UTC)

Also, I suggest to incorporate the the '#' notation for 'G()' as in [1] so that P(#F(#F)) looks better than P(G(F(G(F)))). --Javalenok 16:10, 8 January 2007 (UTC)

In addition, let me note that the formalism p = SU(#SU) corresponds to the sentence 'p is equal to "this statement is not provable"' rather than the 'desired' "p cannot be proved". Peahaps, the difference between two sentences of lair paradox does not really matter. Nevertheless, the neccessety for the redundant 'p' confuses me. --Javalenok 23:02, 8 January 2007 (UTC)

What is the need for self-unprovable formulas?

Let me give a shorter sketch. I see no need to define SU. The statement p equivalent to "p cannot be proven" can be easily formalized as p = ~P(p). Now, if p is provable true then the argument p would be not provable (a contradiction). Alternatively, if p is false (that is, not provable true) then P(p) would be true meaning the argument p is provable true (again contradiction). --Javalenok 13:44, 10 January 2007 (UTC)

You said "...if p is false (that is, not provable true)...". Falsity is the same as not BEING true. That is different from not PROVABLE. This distinction is essential to understanding Gödel's theorem. There is no inconsistency in the existence of a sentence p which is simultaneously true and not provable. Gödel never proved p, i.e. that p cannot be proved. What he proved was ω-con→p, i.e. that IF arithmetic is ω-consistent, THEN p cannot be proved. JRSpriggs 06:39, 11 January 2007 (UTC)

OK, may be I should tell: IF p = false THEN P(p) = true HENCE p is provable true HENCE contradiction (p and ~p) = true. The purpose of the incompleteness theorem is to show that a consistent theory cannot be complete. I'm showing that it is possible to do without introducing the self-unprovable forms. Any objections? --Javalenok 08:47, 11 January 2007 (UTC)

Your first step, going from Neg(p) to P(p), is changing context which is logically invalid. You are going from an arithmetic statement to a meta-arithmetic statement. Although Gödel showed that some meta-arithmetic statements can be pushed down into arithmetic, it does NOT go the other way (as you would have it). Also you say "I'm showing that it is possible to do without introducing the self-unprovable forms.". I do not see what you are getting at here. You are still using p in your argument, and p is the "self-unprovable form" to which you object, is it not? JRSpriggs 08:36, 12 January 2007 (UTC)

Look, SU(#F) is defined as ~P(#F(#F)), so SU(#SU) = ~P(#SU(#SU)). Given SU(#SU) = p, we can rewrite the equality as p = ~P(#p). This equality states self-unprovability explicitly and, furthermore, eliminates the needles self-unprovable form SU(#F). The Neg(p) is ~~P(#p). But you deny the logical conclusion ~~P(#p) => P(#p). Instead, you prefer to go to english language. But stating that some self-unprovable can be proved is an outright nonsense. The [2] dares to state: "Suppose that ~(~P(p)) is a theorem. Hence P(p) is a theorem." --Javalenok 23:32, 13 January 2007 (UTC)

You have completely misunderstood my last message. There is no meaningful difference between "P(p)" and "~~P(p)"; and I did not say otherwise. The vital distinction which you are ignoring is between statements in English about arithmetic and statements in the language of arithmetic which might be regarded as (in some sense) encoding the English statements. Although the encoding is chosen with the intention of making them equivalent, they are not (known to be) PROVABLY equivalent either from the axioms of arithmetic or from meta-arithmetic considerations. JRSpriggs 09:24, 17 January 2007 (UTC)

How About

We split out the philosophical ruminations into a separate article and make *this* article as clear and concise a description of the theorem(s) and their context in mathematics and metamathematics (no easy feat, I'm sure). If nothing else this article is becoming very long and I think it'd benefit.

That said, I confess I'm not sure how this would be done -- do we need to have a discussion/vote? should one be bold and just start the other article? Thoughts? Zero sharp 21:31, 10 January 2007 (UTC)

Let's talk about it first. The ruminations here are quite short, which seems like the ideal situation to me. Are you saying that you would like to expand them?

If you have time and would like to improve this article, you might start by going through and changing the tone so that it is more encyclopedic, without the "we" statements. CMummert · talk 12:22, 11 January 2007 (UTC)

Well, the Minds and machines section may be better fit in its own article, or merged over to Mechanism (philosophy). Actually, there are a bunch of disparate treatments of this scattered over Wikipedia, e.g., here, in Mechanism (philosophy)#Anthropic_mechanism, John Lucas (philosopher), and Minds, Machines and Gödel. We should pick a primary place for the content to go and the rest can link to it. -SpuriousQ 12:27, 12 January 2007 (UTC)

I am all in favor of reducing redundancy. I am fearful about a separate article because I am not a philosopher. I am afraid it might grow into a giant mess of speculation, OR, and non-notable opinions, and it would be hard to fix. But I wouldn't revert the move if it happened. You might leave a one-paragraph summary here, and point to the main article with the {{main}} template. CMummert · talk 14:23, 12 January 2007 (UTC)

I think we need to distinguish between two sorts of philosophical issue. At least something ought to be said in this article about implications for philosopy of mathematics -- particularly, the difficulties that Gödel's results have presented for the formalist and logicist programs. That's part of the historical background in which the results were announced.

The stuff about philosophy of mind, on the other hand, should not be here in my opinion, with the exception of a link somewhere and a very brief summary. This is a mathematics article. --Trovatore 20:59, 12 January 2007 (UTC)

OK, I merged the "Minds and Machines" section over to Mechanism (philosophy). -SpuriousQ 01:14, 17 January 2007 (UTC)

Gödel sentence is an objection to AI. Is it true?

Moved to Talk:Gödel's incompleteness theorems/Arguments.

This question is not an "argument over the validity of the incompeteness theorem". Why was it moved there? --Javalenok 20:36, 11 January 2007 (UTC)

It's not directly related to improving the article. --Trovatore 21:24, 11 January 2007 (UTC)

Is the incompleteness theorem complete???

Moved to Talk:Gödel's incompleteness theorems/Arguments.

"Publication" cat

There's been a bit of reverting going on over the category Category:Important publication in mathematics. My take: first of all, the cat itself should be renamed (categories of this sort take plural names). Second, no, this article doesn't belong in that category, though ~~a category~~ an article named after Gödel's famous paper, "On Formally Undecidable Propositions...", would belong in the category. This article is not (primarily) about that paper, and therefore doesn't. --Trovatore 20:43, 17 January 2007 (UTC)

I strongly agree that the category should be pluralized, and weakly agree that it isn't suitable here. —Ruakh_TALK 22:44, 17 January 2007 (UTC)

The category tag seems to be added and removed over and over again. I think Trovatore's contention is that this article is about the theorems, not the publication. I agree. How about I create a short article on the actual publication, which is certainly notable because it introduced these theorems. Then that page can get added to the category, and everyone wins. CMummert · talk 18:55, 24 January 2007 (UTC)

Yes, please! And if the article is out of copyright, we can put its full text on Wikisource and both articles can link to it. :-D —Ruakh_TALK 19:17, 24 January 2007 (UTC)

The article itself was originally published in German in 1931; I have no idea what its copyright status is. The later English translations are almost certainly still under copyright in the United States. CMummert · talk 19:27, 24 January 2007 (UTC)

Done: On Formally Undecidable Propositions of Principia Mathematica and Related Systems. CMummert · talk 02:02, 25 January 2007 (UTC)

Nice work, Carl. I might quibble on the link to the problematic article Gödel numbering, which I think should probably be deleted or redirected somewhere. But it looks very good, and you finished it quickly! --Trovatore 02:51, 25 January 2007 (UTC)

My general philosophy is that a link should be provided if it theoretically helps the linking article. Otherwise, when the destination article is improved, how will anyone know which articles should link to it? I have the same belief about red links. CMummert · talk 03:29, 25 January 2007 (UTC)

Well, that makes sense, if there ought to be an article called "Gödel numbering". Should there? I'm not convinced. A redirect for sure, but an article? And the argument doesn't strike me as being quite as strong when talking about redirects. --Trovatore 03:52, 25 January 2007 (UTC)

The concept of Godel numbering the sentences of a first-order theory deserves some article. When the current article on Godel numbering is fixed, at least "what links here" will be accurate. The person making the redirect, or a bot in some cases, should resolve the link in the original article to bypass the redirect.

My thought about the Godel numbering article is that it should be an article, but it should just give a catalog of the various senses of the phrase, possibly with links to larger articles on each of these senses. CMummert · talk 04:12, 25 January 2007 (UTC)

Recent anon edits

While I generally feel that anyone wanting to make such extensive revisions to a high-profile article ought to log in, I think the recent spate of edits by 132.181.160.42 have generally been of high quality. However I can't agree with a couple of the changes to the intro. Explaining myself here. The anon wrote:

These theorems show that no consistent formal system can completely describe Peano arithmetic (addition and multiplication over the natural numbers), and that no system capable of representing that arithmetic can prove its own consistency.

This statement is insufficiently precise to be either right or wrong, but it has reasonable readings that are just wrong. Peano arithmetic, for example, is a syntactic rather than semantic construct (as opposed to the structure of the naturals, which is semantic); it's certainly possible for a consistent formal system to completely describe the syntactic manipulations of Peano arithmetic. Moreover there needs to be something said about what sort of formal system (say, that its axioms are computable), otherwise no such conclusion is possible. The anon also says:

The theorems also have extensive implications for philosophy and cognitive science.

A great deal of bad philosophy and cognitive science has been based on the theorems (so say I, a hardcore metaphysical libertarian and substance dualist who likes the conclusion of the Lucas arguments, just not the arguments themselves). In general any claimed philosophical implications outside of mathematics should be viewed with suspicion; it's not ruled out a priori that no such implications can be drawn, but I have never seen one that worked. I think there's a good bit of possibly accurate stuff that's suggested by the theorems, by analogy as it were, and these may even be a reasonable heuristic guide to truth. But the word "implication" is too strong. These are theorems of mathematics, and we should keep the focus firmly there. --Trovatore 07:34, 26 January 2007 (UTC)

I agree that Peano arithmetic is a formal system that adequately formalizes Peano arithmetic. I added a caveat to the lead - the well known decidable formal systems for geometry and the real numbers are simple, but not "trivial". CMummert · talk 13:36, 26 January 2007 (UTC)

Commercial links

The link to "Askanas, Malgosia, 2006, "Gödel Incompleteness Theorems - A Brief Introduction." A lucid and enjoyable exposition of both theorems in the spirit of Gödel's original proof. "is not a bad site for explaining this theorem--well above the high school student's level though--but its "lucid and enjoyable" presents a value judgement which is not at all consistent with the purpose of the article and Wikipedia. It is a commercial site selling services in math education. It should be retained, in my view, it does a fairly good job of explaining the concepts, but the evaluation needs to be reconsidered. Malangthon 03:31, 27 January 2007 (UTC)

I removed the annotation. You could (and, I would suggest, should) have moved it here along with your comment. In cases where a phrase is clearly not neutral POV, seems to advertise for a commercial service, or both, there is no reason to leave the statement while inquiring about it. CMummert · talk 03:54, 27 January 2007 (UTC)

is the incompleteness theorem complete?

This section discussed the underlying mathematics issues rather than the article. It has been moved to the arguments page and can be found here. CMummert · talk 02:16, 29 January 2007 (UTC)

Could we shorten the article.....considerably?

There are previously complaints about this not being accesible to laymen to understand the main points of Godel's Incompletness theorems.

Perhaps majorly shortening the article would help? Just throwing out a suggestion. Fephisto 22:45, 4 March 2007 (UTC)

Shortening it, by itself, will not make it more accessible. Moreover, I would not be in favor of removing material just because it requires a technical background to understand it. Ideally, that material should appear later in the article, with the more understandable material up front, but that's a matter of reorganizing, not shortening.

However it is true that the article is a bit long. It's difficult to maintain focus in articles this long, because people edit in the middle without considering the overall flow. I think the sections on the first and second theorems should be split out to their own separate articles; that would help a bit. That's one of those things I may get around to one day if no one else does it first. --Trovatore 00:59, 5 March 2007 (UTC)

A non-mathematical analogy?

Is the incompleteness theorem *very roughly* analogous to a logical aporia? An aporia is an irresolvable internal contradiction or logical disjunction in a text, argument, or theory. For example, if a Cretan declares all Cretans to be liars, there is an irresolvable contradition between the subject and the predicate. Another example would be: "Language cannot communicate truth", which, if true, is inherently untrue, and therefore true, and so on to infinity.

I am asking purely out of curiosity and am not suggesting this have any bearing on the article.

Thanks. —The preceding unsigned comment was added by Ulrich kinbote (talk • contribs) 07:58, 5 March 2007 (UTC)

Yes, there's a rough analogy there; that's a good way to put it (except the term I knew for it was "antinomy"; is there a distinction between "aporia" and "antinomy"?). Unfortunately a lot of people try to take it as too strict an analogy, and a small but noticeable percentage of these decide that they've "solved the problem" and rant on about some "subtle error" that they think Gödel made. --Trovatore 08:10, 5 March 2007 (UTC)

The problem is that while these theorems are given press coverage, they are intrinsically very difficult to understand. There is no "royal road", no analogy, no easy way to understand them. The layman will NEVER understand them. Only a person who has spent years studying mathematical logic has any hope of understanding them. However, they do not cause the crisis that some popularizers try to say that they cause. They just show that mathematics is infinitely ramified, i.e. there is always more to learn about it. JRSpriggs 10:34, 5 March 2007 (UTC)

Well, that might be a little overstating the case. An undergrad math major in a one-semester course in math logic should be able to get the basic idea pretty well. He might not bother to work through all the gory details of arithmetization of syntax, but those aren't very important anyway.

As to the "crisis" -- I think it was a crisis for the foundational schools that were fashionable at the time, such as Hilbert-style formalism. I think the theorems were the main cause of the latter-20th-century rehabilitation of realism/Platonism to a position of respect, not because they made the problems of realism any lighter, but because they heaped heavy difficulties on realism's leading competitors (while leaving realism itself more or less untouched). --Trovatore 07:07, 6 March 2007 (UTC)

Godel, Escher, Bach gives a completely accessible (i.e. nontechnical) but basically rigorous description and proof of the theorem. It goes off into all kinds of discursions as it threads through the entire book, but it's entertaining reading throughout. I'd consider it readable by any interested and math-inclined high school student. I read it before I knew anything about logic and it made the intro-to-logic class I took later (the usual undergraduate one that ends with the incompleteness theorem) very natural and easy. Raymond Smullyan's What is the Name of this Book? develops the theorem through a series of knights and knaves puzzles but that one's a bit more contorted. Sooner or later I hope we have a wikibook about logic (right now there are a few very tentative beginnings at one). —Preceding unsigned comment added by 207.241.238.233 (talk) 05:33, 25 September 2007 (UTC)

Request for untruth

Can I convince people here to remove the word "true" and "truths" from the statements of the incompleteness theorems? There are two reasons for this. One is that these theorems are formal results about formal systems, and have nothing to do with truth except in certain philosophical interpretations. The interpretations should be in their own section, and not be mixed in with the formal statements of the theorems. The other reason is pedagogical. Despite having a pretty strong mathematical background, I was confused for years about the exact nature of Godel's theorems, precisely because I didn't understand what it meant to be "true but unprovable". It took a very long time for me to realize that the theorems are simply about provability of a sentence and its negation, and once I realized that I immediately understood them. In retrospect I feel that I was misled by nearly every description of the theorems into thinking they were more mysterious than they are, and wasted a lot of time in confusion as a result.

I would state the first incompleteness theorem something like this:

Every [formal system meeting certain criteria] contains a statement which either cannot be proven or disproven from the axioms (making the system incomplete) or which can be proven and disproven from the axioms (making the system inconsistent).

where the bracketed portion is either a placeholder for the actual criteria, or else those exact words with the definition occurring out of line. Probably the latter is better.

I think that the phrasing "every system is inconsistent or incomplete" is much clearer than the phrasing "every consistent system is incomplete". The latter suggests that consistency is just another technical requirement like recursive enumerability, which it certainly is not! -- BenRG 17:25, 23 March 2007 (UTC)

I would support a change like that, provided that the important interpretation of Godel sentences as "true but unprovable" is discussed somewhere else. I have thought for a while that this use of "truth" so early in the article is above the level of the intended reader (they will misunderstand what it means), and the footnote is too terse to help them understand the subtlety of the concept. Several other people watch this page, so I have no plans to rush any changes here. CMummert · talk 17:53, 23 March 2007 (UTC)

I'm not really in favor of such a change. Saying that T does not prove G_T is precisely the same as saying that G_T is true, and that's what we need to get across. It's possible to doubt that G_T has a determinate truth value, but then you are also required to doubt that the proposition "T does not prove G_T" has a determinate truth value. Or at least it's not obvious how you'll avoid it. --Trovatore 18:40, 23 March 2007 (UTC)

They are not the same, because you cannot say that G_T asserts its own unprovability unless you interpret it as a statement about natural numbers. This is not a mere technicality, because it follows from the completeness theorem that if T is provably consistent in some system T', then there exist models of T in T' under which G_T does not hold (i.e. the interpretation of ~G_T is a theorem of T'). I'm not sure I got that exactly right, but I assure you that there is no way to talk about the truth of G_T without making interpretational assumptions that can't be formally justified. -- BenRG 20:19, 23 March 2007 (UTC)

What I said was that if you doubt the existence of a determinate truth value for G_T, you also have to doubt it for the proposition "T does not prove G_T". The latter statement asserts the nonexistence of a finite string of sentences starting with the axioms following the rules of inference yada yada yada. If "natural number" (sempliciter, not relativized to any model) is problematic, then so is "finite string of sentences". If you don't think so, then please explain your semantics for interpreting "T does not prove G_T", and explain why you don't have to relativize *those* semantics to a model. --Trovatore 20:41, 23 March 2007 (UTC)

Natural numbers are not problematic, just not unique. Let's assume Platonism, since presumably non-Platonists will have no objection to my original proposal. Without getting bogged down in issues of philosophy of language and levels of English quotation and whatnot, "T does not prove G_T" is a statement about the Platonic realm, saying yada yada yada. But even to a Platonist, G_T is not such a statement. T is a formal system by assumption, and so G_T is a string of symbols by definition. Unlike real propositions and theorems, the so-called propositions and theorems of a formal system are just strings of symbols, and a Platonist is not obliged to interpret them in any particular way. The only important thing is that the interpretation be consistent, i.e. that all of the axioms and rules of inference be valid under the interpretation. The Platonic version of the result about T' is: "if T is provably consistent then there exists a consistent interpretation of T under which G_T is false". The quoted statement is true if the completeness theorem is true, which I think any Platonist would accept.

Different consistent interpretations of T give you different theorems, all of which are true. In one interpretation G_T, though not a theorem of T, happens to encode a true statement about natural numbers that's equivalent to an assertion of G_T's unprovability in T. In other interpretations G_T might encode other true statements. In at least one interpretation G_T encodes a false statement, but ~G_T, which is also not a theorem of T, encodes a true statement.

The point is that G_T isn't a statement about natural numbers, and never was. The only reason people talk about natural numbers in the context of Gödel's proof is that it's a convenient informal way of describing the Gödelization process. All that's really necessary for the proof is a certain formal structure within the system, which can be provided by natural numbers but also by other things that aren't the same as natural numbers. They all suffice to construct the Gödelization of the system, but they differ in whether it's a true-but-unprovable statement or a false-but-undisprovable statement. -- BenRG 22:10, 23 March 2007 (UTC)

Let's stick to the naturals, please; it'll save us a lot of confusion. Sure, the objects of discourse of T may not literally be natural numbers (e.g., they might be sets, if T is for example ZFC). But the relevant objects of discourse of T are the ones that play the role of the natural numbers in the assumed relative interpretation of PA into T. These are the only ones for which we need provide an interpretation in order to interpret G_T. So they might as well be the natural numbers.

Yes, if T is consistent then there is a model of T in which G_T is false. But that model will (necessarily) have nonstandard natural numbers. Interpreted in the standard natural numbers (which are unique, up to a unique isomorphism) G_T is true. Again, this is no more problematic than the claim that the statment "T does not prove G_T" is true. --Trovatore 22:28, 23 March 2007 (UTC)

I disagree that sticking to the naturals saves confusion; I think it creates confusion. As I said before, it certainly did for me. Despite your use of "again", this is the first time you've said that G_T interpreted in a particular way is true, rather than implying that G_T itself is true. Personally I interpret the (first) incompleteness theorem in a completely different way. In light of the completeness theorem, it seems clear that it's not about the inability of axiomatic systems to capture truth. They can prove exactly what they ought to be able to prove (everything that's true in all models). What it's really about is the inability of axiomatic systems to fix the objects of discourse. To me this is a much more interesting result. It's a reasonable interpretation of what Gödel actually proved, but not a reasonable interpretation of the pre-interpreted version that implies that G_T is really true. Of course I'm not saying that this objects-of-discourse thing should be in the theorem statement; it should be in a later section, after a theorem statement accurate enough to accommodate all interpretations.

If this doesn't change your mind then we may be at an impasse. I hope a few other people will weigh in on this. -- BenRG 14:28, 24 March 2007 (UTC)

You don't actually need the incompleteness theorems to show that (first-order) axiomatic systems can't "fix the objects of discourse". Löwenheim–Skolem is sufficient for that (and more directly on-point).

But it does seem that we're not arguing about what I thought we were; it may be more a difference of terminology. The way I think of it, G_T, taken literally, is directly a statement about the natural numbers. It's written in the language of arithmetic. If T is not in the language of arithmetic, then the sentence that T literally fails to prove or disprove is not G_T itself, but what we might call Translate(G_T), where the Translate() function is the thing assumed to exist by the hypothesis that says PA is relatively interpretable in T. What G_T asserts is not "T cannot prove me" but rather "T cannot prove my translation". Then I ordinarily suppress mention of translations from casual descriptions, because they really are a technical detail, and speak of T proving or not proving sentences of arithmetic, when literally speaking I really mean proving or not proving their translations.

Using this terminology, where G_T is directly and literally a statement about the naturals, do you agree that if T is consistent, then G_T is true? --Trovatore 18:15, 24 March 2007 (UTC)

There is a second translation: from the statement G_T, which is just some Pi^0_1 sentence, to a statement at the meta level about provability. We recognize, at the meta level, that any actual proof could be coded as a standard natural number. It is because of this second translation that I think it would be worthwhile to have a whole paragraph in the article rather than just a footnote. This translation is already lightly covered one or two places, including the proof, but not as explicitly as it could be. CMummert · talk 19:24, 24 March 2007 (UTC)

Carl, of course you're right about this other level of translation, but it doesn't seem to be in dispute at the moment, especially in relation to the use of the word "true". I seem to have understood wrongly, at first, what BenRG's actual complaint was; it doesn't seem to be about theories of truth, but more about whether the Gödel sentence should be thought of as arithmetical. (For some reason BenRG didn't complain about the word "arithmetical" in the statement he was referring to.) Ben, do you see where I'm coming from on that now, and do you agree that the arithmetical version of G_T is properly described as "true" if T is consistent? --Trovatore 01:52, 25 March 2007 (UTC)

So the big problem with using the word "true" in this context is that it is POV. The definition of "true" requires a footnoted definition which is as long (longer perhaps) than the statement of the theorem itself. If "true" is being used in a *particular sense* then its not truly NPOV and certainly will confuse the average reader. Its perfectly valid to have a philosophical position that uses the concept of "truth" but does not accept that the Godel sentence is true. There are, after all, models in which it is both satisfied and unsatisfied (true and false if you like). Really the problem here is the belief -- very widely held I admit -- that there is an "intended model" in which we can say that it is true. That's not nearly as cut and dried a philosophical position as many would like.

I'd suggest dropping the "true" bit of the definition of the theorem itself. I accept that it was a position which Godel found attractive and is implicit in his approach, but the focus of his theorem was the formal undecidability not the semantics of his sentence. For the first theorem, surely a reasonable approach would be to state it like that (as a theorem about undecidable sentences) and then remark that most mathematicians take an approach where they can say "its true but not provable".

The key thing is that wikipedia shouldn't try to adopt a particular position on the point. Francis Davey 00:15, 7 July 2007 (UTC)

The notion of the truth of the Gödel sentence (well, Rosser sentence, maybe) of T is no more problematic than the notion of the consistency of T, which is one of the hypotheses. As you say, there are models that fail to satisfy G_T, but those models also hold that T is inconsistent, meaning that, from the perspective of those models, we're not even in the situation where the theorem applies. So it's seriously misleading to quibble on the concept of truth for G_T, while not mentioning that the hypotheses of the theorem have exactly the same issue. --Trovatore 00:45, 7 July 2007 (UTC)

I'm not sure that's quite right. There are *consistent* models of PA (or whatever system) in which the Godel sentence is false, but the incompleteness theorem is still valid (and its hypotheses hold). Its true that such models may deny Con(T), but they are consistent nonetheless. All that is required to prove the first theorem is consistency (i.e. that falsity is not provable) -- which is a property of the theory not of a particular model. The Godel sentence is true in some of those models but not all, the theorem is true in all models because its a theorem. Maybe I am misunderstanding what you are saying, but there seems not problem to me in questioning whether the Godel sentence is "true" but still being entirely happy with the theorem (which says the sentence is not provable). Francis Davey 10:34, 7 July 2007 (UTC)

You can be entirely happy with the theorem, as a formal theorem, even if you doubt the determinate truth value of G_T, yes. But in that case you can't really interpret the conclusion as "G_T can't be proved", at least not in full generality. That's because, while G_T is a claim about an arbitrary natural number, the statement that G_T can't be proved is a claim about an arbitrary proof. And if arbitrary natural numbers are problematic, then arbitrary proofs are equally so. To put it another way, yes, there are models in which G_T is false, but in those models, G_T can be proved.

If you say, as you do, that consistency of a theory is a property of a theory rather than the model, then you must have some notion of what an arbitrary proof is "really", without reference to any model. But then you can use that notion to understand what an arbitrary natural number is, "really" (for example, "a natural number is the length of some proof or initial segment of a proof"). And that's all you need to give a determinate truth value to G_T. --Trovatore 18:18, 7 July 2007 (UTC)

I don't think you are saying more than that in order to say many meaningful things about PA (or other applicable theory) as a theory we often need stronger (or different) assumptions in a meta theory to do it. Eg, we cannot prove the consistency of PA within PA. G_T cannot be said to be "provable" in non-standard models of T in which G_T is false, since "provable in a model of the theory" isn't a meaningful concept. What I think you are saying is that there are models of the meta theory of proofs in which G_T is provable. That seems to me to say little more than the obvious, namely that there is no firm ground on which we can build a formal explanation of what a natural number is, the best we can do is push the problem elsewhere. One might not wish to do that -- and my point is that is a perfectly valid philosophical standpoint. There is nothing *logical* that forces one to accept that the standard model is somehow the "right" or God-given model, although there might be metaphysical reasons for choosing it.

You can certainly give a determinate truth value to G_T, but really that's not very interesting. The fact that something is valid in some models and not in others is really very common. You can pick a model in which it is true, but that doesn't mean it *is* true does it? Francis Davey 23:27, 7 July 2007 (UTC)

"Provable in a model" is indeed a meaningful concept. It means that the model has an element that, according to the model, is a proof of the statement. The model may, of course, be wrong about that -- that is, the statement may be provable in the model, but not really provable. Just as G_T may be false in the model, but not really false.

What's a perfectly valid philosophical standpoint is that there may not be a "standard model" of PA. But then, the questions about what's provable and not become just as problematic as the question about what's true about the (standard) naturals.

What's not a valid philosophical viewpoint is to say, "yes, there's a standard model of PA, but I'm not going to use it to give a truth value to G_T" -- that's not a viewpoint, it's a linguistic quibble. The objects of discourse of G_T are the natural numbers, so saying that G_T is true is exactly the same as saying it's true in the standard model. That's not philosophy, just understanding ordinary mathematical language. --Trovatore 06:43, 8 July 2007 (UTC)

Quite so. I thought that was clear from what I said. Maybe we are talking at cross-purposes. Francis Davey 10:53, 8 July 2007 (UTC)

Could be. I'm not sure exactly what you are saying, but it appears clear that you want to apply restrictions to the claim that "G_T is true" that you are not willing to apply to the claim "T does not prove G_T", and you haven't explained just what your semantics for the latter claim are.

As regards your remarks about "models of the meta theory of proofs" -- note that we don't have to look very far for them. Every model of T is already a model of the metatheory. That's the whole point of the requirement that PA be relatively interpretable in T. And, any model of T in which G_T fails, is a model of the claim that T proves G_T. --Trovatore 00:36, 9 July 2007 (UTC)

It is possible to understand Godel's theorem without referring to the truth of the statement, but almot every standard presentation does discuss the truth of the Godel statement. What the article needs is slightly more information than a footnote about this, not less. The article ought to explain how the truth of the sentence can either be interpreted disquotationally or interpreted as truth in the standard model (which is very similar). Suppressing the fact that the Godel sentence is widely considered to be true would impose an uncommon POV on the article. — Carl (CBM · talk) 13:25, 7 July 2007 (UTC)

I'm not proposing (and I don't think anyone is - though I may be wrong about that) that the fact that many consider that it is useful to explain the Godel sentence as true but unprovable be suppressed. Clearly that would be wrong. It is a point of view. But the fact that it is a point of view means that it ought not to be stated uncritically. Francis Davey 23:27, 7 July 2007 (UTC)

I see; I misunderstood. I would accept moving the discussion of truth to a separate section and adding a line to the lede to summarize that section. That's contingent on the new section being acceptably written, of course, but I would try to help. Whether others are as willing as I am remains to be seen - the interpretation of the statement as true but unprovable is extremely common, because it does have a strong justification. — Carl (CBM · talk) 00:15, 8 July 2007 (UTC)

I am against that plan. I frankly think that Francis has still not quite understood the issue, probably because the sources he's read didn't understand it either. Failing to state this plainly is likely to result in further confusion.

We should have a section dealing with other interpretations, and mention that the "truth" interpretation becomes problematic if you don't believe in the totality of the natural numbers -- but that the "provability" interpretation also becomes problematic in that case.

I would note another point here: Strictly speaking, the claim that the Gödel sentence of a consistent theory is neither provable nor refutable from that theory, is not even true. The sentence certainly not provable, but it may be refutable, if the theory is ω-inconsistent. So to follow Francis's suggestion, we either have to explain ω-consistency earlier than is really desirable, or we have to use Rosser sentences -- which would make the explanation not strictly about Gödel's theorem, but rather Rosser's strengthening of it. --Trovatore 07:03, 8 July 2007 (UTC)

Actually I think that touches on something of importance, namely that Godel assumed omega-consistency to prove the theorem and (as you say) it is only after Rosser that we have the theorem requiring only consistency. Nevertheless the normal citation of the theorem is in the Rosser version (i.e. after strengthening). That is normal for mathematical usage (the eponymist of a theorem retaining their origination even if the theorem is "improved") though another usage might be the Godel-Rosser theorem.

By the way, I quite accept that, in historical terms, the remark about the sentence being "true" is correct, since that is the interpretation Godel himself gave to it, though it is presented as a corollary rather than as the main theorem which is merely about undecidability. Francis Davey 10:53, 8 July 2007 (UTC)

A question about computable enumerability

The following is stated in the article:

Some technical hypotheses have been omitted here; the most important is the stipulation that the theory be computably enumerable. That is, for Gödel's theorem to be applicable, it must be possible in principle to write a computer program that correctly decides whether statements are axioms of the theory, and a second computer program that, if allowed to run forever, would output (one at a time) a list containing all the theorems of the theory and no other statements.

If there is "computer program that, if allowed to run forever, would output (one at a time) a list containing all the theorems of the theory and no other statements" then doesn't that contradict Godel's theorem about the theory being incomplete? I don't claim to understand this subject very well but this is my intuition as a computer science student. I think the above should be changed to "a list containing all the theorems of the theory and their negations". Please explain if you think I am wrong.

Panayk 18:27, 8 April 2007 (UTC)

It outputs the list of theorems, i.e., the list of sentences provable from the axioms. This cannot include any particular sentence and its negation, for then the axioms would be inconsistent. There will be some sentences, such as the Godel sentence, for which neither the sentence nor its negation is a theorem, and so neither one will be included in the list. CMummert · talk 18:34, 8 April 2007 (UTC)

Ah thanks, I misunderstood what we mean be theorem (i.e. I thought a theorem is a true sentence that is not an axiom). Just to make sure: is the reason that such a program (that lists the provable sentences) can exist, that we don't require it to terminate? Because otherwise we could use it to "look-up" a sentence (and its negation) and find out if it's decidable, something that Turing (I think) precluded as mentioned in the article. I hope I am making sense. Panayk 21:52, 8 April 2007 (UTC)

Yes, it doesn't decide whether a given sentence is a theorem, it just tests all possible proofs and outputs their conclusions. CMummert · talk 23:01, 8 April 2007 (UTC)

So while the theorems can be enumerated recursively, one CANNOT recursively enumerate them in a predefined order, e.g. by the number of characters in the formula (and lexicographically for each length). That would make the theorems a recursive set (rather than just a recursively enumerable set) which is impossible unless number theory is inconsistent. JRSpriggs 09:59, 9 April 2007 (UTC)

Thanks. You know, even though I was first introduced to Godel's work some years ago, I never quite understood it until now. Part of the blame is on one of the articles I first read, one that tried to reconcile the classical notion of truth with Godel's notion of "truth == provability". For example the author was saying that the Godel sentence was true but unprovable. The author then went on to claim that we (humans) are "special" in that we can "see" the truth of the Godel sentence. It now occurs to me that this is absurd. In the context of the incompleteness theorems provability is synonymous with truth: "true == provable" and "false == the negation is provable". Nothing else, period. Panayk 21:10, 22 April 2007 (UTC)

No, if that's the lesson you took away from it, I'm afraid you got it wrong. Prior to Gödel it was perhaps reasonable to believe that truth equaled provability; afterwards it was not, and referring to "truth==provability" as "Gödel's notion" is simply ahistorical.

As to whether humans are special are not, that's beyond the scope of a mathematical theorem. Gödel himself believed that humans are special, but to the best of my knowledge, never claimed to have proved it. --Trovatore 01:28, 23 April 2007 (UTC)

I meant, that as I now understand it, the incompleteness theorem doesn't deal with truth but only with provability. The notion of truth doesn't exist in the context of the theorem, and you don't need it to make sense of it. A sentence is "true" if you can prove it, "false" if you can prove its negation, and undecidable in all other cases (e.g. the Gödel sentence, which we have nothing to say about). That's how "true" and "false" is used in the following sketch of the proof: http://www.ncsu.edu/felder-public/kenny/papers/godel.html. It's only a formal thing, the author may have as well used the words "red" and "black". That's what I meant by "truth==provability", that in the context of the theorem we don't care about (or define) the notion of truth, only of provability. The theorem has nothing to say about the "truth" of the Gödel sentence or whether humans can see it. (Not to say that such questions are not valid given an external definition of "truth"). Am I on the right track? Panayk 14:50, 23 April 2007 (UTC)

Hmm, better, but still some quibbles. You're right, the proof of the theorem deals mainly with whether sentences are provable, not whether they're true. But it's an extremely bad idea to use the words "true" and "false" here in place of "provable" and "refutable" -- you'd do much, much better using "red" and "black" than "true" and "false".

Part of the reason that this is so is that the proof of the theorem does show that the Gödel sentence of a consistent theory is in fact true. To understand that, you need to have separate notions of "true" and "provable". --Trovatore 19:05, 23 April 2007 (UTC)

After looking at the paper you linked to, I think I see why you are confused. The people who follow Hofstadter's proof tend to use proofs like this, with the same poor terminology. Sometimes when he says "statement about natural numbers" he means a statement with no quantifiers whatsoever. For formulas with no quantifiers, provability in PA is equivalent to truth. But for statements with even one quantifier, provability and truth do not coincide. The paper you linked to is particularly vague about this point. You would be better served by finding any undergrad level mathematical logic book rather than anything based on Hofstadter's proof. CMummert · talk 20:08, 23 April 2007 (UTC)

You are probably right. Would you care to recommend one (or more)? Most of the material I have read was either too popularized or only dealt with the subject very briefly as an introduction to something else. I am trying to get the whole picture, but that's hard to do when I have only my intuition to figure out what exactly 'truth', 'theory' etc. mean. I'd also be interested to know how exactly this relates to computer science and computability theory. Panayk 23:34, 23 April 2007 (UTC)

One respected undergrad logic book is: Herbert Enderton (2002) A mathematical introduction to logic, 2nd ed. An equally good book, at a slightly higher level but lower price, is Computability and Logic by Boolos, Burgess, and Jeffrey, 4th edition 2002. CMummert · talk 23:52, 23 April 2007 (UTC)

Thanks. Panayk 09:35, 24 April 2007 (UTC)

An example of a statement which is true but not provable?

It seems the article should give one or two examples of a central aspect of Gödel's theory, that there are statements in math which are true but unprovable. Referring to these two sentences:

In fact, there are infinitely many statements in the theory that share with the Gödel sentence the property of being true but not provable from the theory. "Elementary arithmetic" consists merely of addition and multiplication over the natural numbers.

Is "elementary arithmetic" an example? It's not clear that it is (it should say "for example"). Secondly, how is this an example? Is it actually unprovable that two numbers added together create a sum? This doesn't seem like a good example for a layman, as the reason this is unprovable isn't easy to grasp. Can someone give a better example, something that's not a basic axiom? Scott Teresi 15:16, 8 July 2007 (UTC)

Elementary arithmetic has to be part of the theory, so any theorem of elementary arithmetic is provable in the theory. I rearranged the paragraph some. Given one true but unprovable statement S, statements like "S and 0 = 0" and "S or 1 = 2" are also true and unprovable, so there are trivially infinitely many other true but unprovable sentences. — Carl (CBM · talk) 17:44, 8 July 2007 (UTC)

Can you give some examples of S? I remember things a lot better when I know a few good examples of something. Scott Teresi 20:34, 9 July 2007 (UTC)

The proof of Godel's theorem gives a construction of such an S, although if written out explicitly it would be very long. The sentence essentially says "There is no natural number that encodes a proof of this sentence". The difficult thing is making the self reference work out correctly.

There are other known examples of unprovable sentences. For example the Paris-Harrington theorem is true but not provable from Peano arithmetic, and many people would say that although the continuum hypothesis is not provable or disprovable from ZFC it is either true or false in the "real world". — Carl (CBM · talk) 20:51, 9 July 2007 (UTC)

Second theorem

How does Gödel's second incompleteness theorem follow from his first? I know and understand the proof of his first, except for what exactly is needed for a theory to state the provability of a given theorem. I'm willing to trust that adding axioms and computable axiom schemas won't make the first theorem cease to apply, although I don't understand why. I also figured out a simple way to prove his first theorem from his second, although I doubt that's useful. — Daniel 19:13, 12 July 2007 (UTC)

The second theorem doesn't follow "from the first" directly; the proof of the second relies on the fact that a proof of the first incompleteness theorem can be carried out inside any sufficiently strong theory of arithmetic. The first incompleteness theorem, as an approximation, gives a sentence that says "I am not provable", and shows that this sentence is true but not provable. The second incompleteness theorem, as an even coarser approximation, gives "The sentence 'I am not provable' is not provable" as a sentence that is true but not provable. This latter sentence, essentially, asserts the consistency of the theory, because a theory is consistent if and only if it has at least one unprovable sentence. — Carl (CBM · talk) 22:03, 13 July 2007 (UTC)

The latter sentence (which, if I am not mistaken, is essentially identical to the former) does assert the consistency of the theory, but I don't see why it would be the only one. Wouldn't "The sentence <insert sentence> is not provable" work with any sentence? Does "The sentence '0=1' is not provable" imply "The sentence 'I am not provable' is not provable"? By the way, the best r=translation of the sentence into something like English I can think of is "', when preceded by its own quotation, cannot be proven using <insert system used for proofs in given theory, not just the name>', when preceded by its own quotation, cannot be proven using <same as last insertion>" How come they never use something like that? Is it too complex for the layman? Is it just more than they want to know? — Daniel 01:23, 16 July 2007 (UTC)

That's a very close translation that is very useful in the context of quines. I don't know why it isn't the "textbook standard" version, but it may be because it is so much less succinct than the other translations, to the point that the main idea is easy to miss. The "latter sentence" in my post above is not at all identical to the former, and this difference is the difference between the two incompleteness theorems. The latter one has an extra level of indirection that the first one doesn't.

Your other question gets exactly to the point of the theorems. You're right that "The sentence <insert sentence> is not provable in theory T" asserts the consistency of theory T for any inserted sentence. But it is trivially correct for any disprovable sentence of T if T is consistent; I think that accounts for your example of "0=1".

One key innovation in Godel's work was showing that proofs can be encoded in very weak fragments of arithmetic so that arithmetical sentences can be used to assert the provability of other arithmetical sentences. The most surprising result is that there are unprovable sentences that are true in the standard model, which means they aren't disprovable either. Thus any consistent effectively axiomatizable theory of arithmetic is incomplete, which was not known before Godel's work. You don't get that directly if you use sentences like 0=1. This contrasts with Hilbert's proof that there are complete effectively axiomatizable theories of Euclidean geometry. — Carl (CBM · talk) 02:42, 16 July 2007 (UTC)

It doesn't matter that "The sentence <disprovable sentence> is not provable in theory T" is trivially correct when T is consistent. The point of the second theorem is that that sentence can't be proven no matter what sentence is inserted in T. How did he prove this? — Daniel 16:20, 18 July 2007 (UTC)

Ademh: Your post "Paradox in Godel's incompleteness theorem that invalidates it" is now at Talk:Gödel's incompleteness theorems/Arguments

retitled Wvbailey 00:18, 10 October 2007 (UTC)

Move to the arguments page here. — Carl (CBM · talk) 15:16, 9 October 2007 (UTC)

Sub-section(s)-in-progress re criticisms? misunderstandings? of Godel's incompleteness theorems

Would it make sense, though, to have a little section on the page re this very issue? That these arguments have been discredited since Finser (or some such)? Bill Wvbailey 16:03, 9 October 2007 (UTC)

It would be worth having something in the article about persistent misunderstandings. I thought there was such a section, but apparently there isn't. There are some difficulties writing such a section:

We want to limit it to only very notable objections (not a free-for-all of complaints)
We need to source it well, so it's clear that it is not original research or opinion of Wikipedia editors. Franzen's book will be helpful for that.

But I think it could be done. — Carl (CBM · talk) 16:15, 9 October 2007 (UTC)

Would you recommend that we create a "working article" (suggested title?) or do the work here? (As you know, I create a lot of clutter while I'm researching and "collecting"). Bill Wvbailey 16:38, 9 October 2007 (UTC)

If you want to collect quotes and sources for later use, I'd recommend a subpage of your user page. I think it's parallel to the way some people make large numbers of index cards when doing research at a library, so that they can use those cards later to piece together a paper. If you haven't looked at Franzen's book, that would be a good resource, as would:

"The Reception of Godel's Incompleteness Theorems", John W. Dawson, Jr., PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, Vol. 1984, Volume Two: Symposia and Invited Papers. (1984), pp. 253-271. [3]

That paper has specific comments about Finsler and Godel's communications, and about other criticism of Godel's work shortly after it was published. — Carl (CBM · talk) 17:37, 9 October 2007 (UTC)

Voilá: User:Wvbailey/Criticism of Godel's incompleteness theorems‎. All are invited to participate in adding research -- e.g. references, quotes (with citations, please) etc. Please add the raw stuff to the talk page. If anything good comes of these labors, I'll write something up there, transport it here for comment, and we can emend before putting into article. Bill Wvbailey 19:10, 9 October 2007 (UTC)

Hmm -- the only thing you have there so far is a brief note about Finsler, who (if I've understood correctly) didn't have a criticism of Gödel's arguments; he just thought he (Finsler) should have gotten some of the credit. Do I have that right? That seems to be another matter altogether. Admittedly the source apparently treats this together with criticisms of the arguments themselves, but I think at least the proposed article needs a different title if this is to be included in the subject matter. --Trovatore 04:18, 10 October 2007 (UTC)

You do have it mostly correct about Finsler, he claimed priority, and Godel gently tried to explain to him the error of his ways. But there is an implied criticism -- or perhaps disappointment -- also evident in Finsler and Post re the notion of "absolute". In a draft letter (ca summer 1970, composed but never sent) to Yossef Balas Godel writes the following (this is all in English, by now he was loosing his German a bit -- I believe this because my grandmother lost all of hers) such as "he (Finsler) omits exactly the main point which makes a proof possible, namely restriction to (some well defined formal system... he had the nonsensical aim of proving formal undecidabliity in an absolute sense. This leads to the nonsensical definition... the flagrant inconsistency ... if Finsler had confined himself to some well defined formal sysem S, his proof ... could be made correct and applicable to any formal system. I myself did not know his paper when I wrote mine, and other mathematicians or logicians probably disregarded it because it contains the obvious nonsense just mentioned."

Re the last sentence above Godel also used, then crossed out the words "This proof" [which incidentally was not known to me when I wrote my paper] is therefore worthless and the result claimed, namely the existence of "absolutely" undecidable propostions is very likely worng." (page 10 of volume V? IV? the two volumes are stolen from the library and I had to take photographs of what I could get off the web)

RE this business of "undecidablility in an absolute sense" I found something in Post 1941 (unpublished until Davis 1965) re Post's desire for the same. See in particular p. 340 in The Undecidable, Footnote 1.) This is an interesting "criticism", in my mind, i.e. they're saying it's a puny proof, clever but puny because it fails to address "absolute undecidability". Fair enough criticism, I should say.

You got to my sub-article-in-the-making too quickly. I'm probably going to move (most of) the stuff to an article on Finsler. But Finsler is the poster-child -- the shining explar -- of those who misunderstand "the point" re a tightly-system "system" with an "adequate" amount of arithmetic. So I'm pursuing an angle there, just exploring, with an intention of forking off an article re Finsler. I have to peddle my little bike up to the campus (thereby avoiding a parking fine) to access JSTOR for Carl's article (or pay $14), and I've got Franzen and another book, but will have to read them more carefully than my first quick pass at them and scan through Dawson too. Bill Wvbailey 17:26, 10 October 2007 (UTC)

Well, I don't know if we need two new articles -- from your description it seems as though the Finsler material fits with the rest of it. It's just the title that needs work. Maybe scholarly reaction to Gödel's incompleteness theorems or some such. --Trovatore 17:59, 10 October 2007 (UTC)

My intention would be to add one or two short sub-sections (not separate sub-articles ... sorry .... mea culpa: I've changed the title of this section) to the main article. I suspect that scholarly criticism is very limited, probably to the "disappointment" of Post and Finsler alluded to above. (Altho our friend Ademh seems to have found a published critic, too.) It's misunderstandings, that seem to fall into two camps: (1) nutcase and (ii) honest-intentions but misunderstanding. Excepting Dawson's commentary re Finsler (p. 407) I have no firm evidence yet, but my hunch is the misunderstandings are around Godel's "true ≢ provable". A clear understanding of this takes away about 95% of the scariness of his proofs, at least it did for me. Now the proofs seem almost obvious:

"...However (and this is the decisive point) it follows from the ~~in this model it would have to be shown that truth and demonstrability are equivalent [i.e. Dem(p)≡ p]. But the decisive point is now to apply the~~ correct solution of the semantic paradoxes ~~i.e., the fact~~ that ~~the concept of "truth" of~~ the propositions of a language cannot be expressed in the same language, while provability (being an arithmetical relation can. Hence true ≢ provable.)" (strikeouts in original (1st one is shown in a footnote); unmailed ca 1970 letter from Gödel to Yossef Balas in Dawson's Collected Works vol. 4? )

Bill Wvbailey 14:21, 11 October 2007 (UTC)

New Proof

I added a short modern proof, that is essentially identical to Godel's, except using the modern intuition about computers. It seems a shame to not use modern computer science, which really makes the whole thing trivial. The interesting part of Godel's actual proof consists of the peculiar encoding he does, which uses powers of primes to encode the data. The main lemma in his paper, though, is that any primitive recursive function (aka computer program with for loops) can be represented as an arithmetic function with plus and times. This is the "embedding of a computer" alluded to in the new section.Likebox 23:28, 10 October 2007 (UTC)

I like the general thrust of it, but I fear it may be a little too glib -- someone reading it casually may underestimate the difficulties. I'm also fairly suspicious of the claim that an argument this short (even black-boxing the arithmetization stuff) can dispense with ω-consistency; I really think you need something like the Rosser trick for this. A test case would be to try it out on a consistent theory that proves its own inconsistency. I have a suspicion that you may have hidden an appeal to Σ₁ correctness somewhere in the argument (which is stronger than consistency). --Trovatore 20:21, 11 October 2007 (UTC)

There are no difficulties. It is a complete proof. Likebox 21:31, 11 October 2007 (UTC)

Here's the problem (well, a problem; I haven't had time to think through all the stuff about "printing code into a variable" and it's not obvious that such phrases have a unique reading). You say:

If the axiom system proves that DEDUCE doesn't halt, it is inconsistent. If the axiom system does not prove that DEDUCE doesn't halt, it is incomplete.

But what you haven't explained is how to deal with the following possibility: What if the axiom system proves that DEDUCE does halt, when in actual fact DEDUCE does not halt? Note that this does not imply that the axiom system is inconsistent, just that it proves a false Σ₁ statement. And it is not obvious in this case how to conclude that the axiom system is incomplete. As I said, I don't think you'll be able to avoid doing something along the lines of the Rosser trick. --Trovatore 21:52, 11 October 2007 (UTC)

I see your point. There is an omega-consistency assumption. Your sigma one statement is the same as omega consistency. I though what I was doing is the Rosser trick. I'll try to Rosserize the argument, and I'll delete the false claim until I do.216.7.9.34 00:43, 12 October 2007 (UTC)

I put an argument for incompleteness in. Thanks for catching that Trovatore. 216.7.9.34 04:11, 12 October 2007 (UTC)

The printing code into a variable is a standard thing. To encode it into the axiom system is the non-unique step.

Just to be clear, to embed a computer into an axiom system means the following: find some encoding of the memory of the computer inside the objects described by the axiom system, which requires an arbitrarily large integer, and a single statement of the form "for each memory contents M there exists a unique M'= f(M)" where f is a primitive recursive function which takes one processor step in time. The processor could be as idiotic as a Turing machine or a cellular automaton, so long as there is some published path from that to a random-access machine and a modern architecture. Then the first order statements about M are statements about the memory of the computer, which are capable of expressing any precise english statement about the behavior of the machine. For example, to say the program doesn't stop would be "There does not exist and n such that

G_{n}(M_{0})=G_{n+1}(M_{0})

(assuming that the encoding of a stopped program doesn't do anything). To encode that a program doesn't print something not-exist-n such that

Screen(G_{n}(M))!=empty

where "screen" is a primitive recursive function which projects the memory of the computer to the sub-memory which is identified as the contents of the screen. Blah blah blah obvious, blah blah blah obvious.

The Godel encoding works just fine: Write an integer as a list of prime numbers

2^{a_{1}}3^{a_{2}}5^{a_{3}}....p_{n}^{a_{n}}

and note that finding the n-th prime number is primitive recursive.

Then identify

a_{1}....a_{n}

as the state of your computer. —Preceding unsigned comment added by 216.7.9.34 (talk) 16:44, 12 October 2007 (UTC)

Proposed Revisions

What was reverted by Trovatore.Likebox 21:47, 11 October 2007 (UTC)

What I had in mind was, why don't you create a subpage in your user space, and develop it there, soliciting comment? Then it can be copied over (or merged) once there's some consensus for it. That's what I did when I revised definable real number (still a horribly problematic page that should probably be deleted, but it's less bad than it was). --Trovatore 21:55, 11 October 2007 (UTC)

Ok--- here are the proposed revisions Likebox 01:02, 13 October 2007 (UTC)

Good idea, I never did that "user page" thing before. I will do that if this bid for consensus fails. Let me try to say what the edits I made were, because I think they are pretty pedestrian. I didn't remove any material except for what I thought were two inaccuracies.

The statement that Cohen and Godel didn't use incompleteness to prove independence of AC and CH, which might be true as a textual statement but I can't logically make sense out of it, because its hard to say whether you are "using" a proved result. Cohen uses a countable transitive model axiom and without mention notes that the countable model axiom is unprovable, and that's the incompleteness theorem for ZFC.
I got rid of the "and complete" from the statement that "godel's theorem shows that an axiom system which is consistent and complete cannot prove its own consistency", which is not just overcautious, it is a slip up. If it is complete, it must either prove its own consistency or its own inconsistency. It should read "Godel's theorem shows that a (sufficiently powerful) axiom system which is consistent is incomplete".

The rest of the edits were just organizational:

I reorganized the "undecidable" page so that it was sectioned up. I split it into "undecidable decision problems" and "theorems independent from axiom systems". I then sectioned up the axiom systems section into "independent from ZF(C)" and "independent from PA", and left the Chaitin and Hofstadter comments untouched.

I tried to start each section with "result 0", which is the most primitive undecidability result.

In "decision problems" result 0 is the Halting problem. Results 1 and 2 were obvious equivalents, Kleene's separation lemma, and another one made up at random just to show readers that this stuff is considered well understood today. Result 3 was the word problem for groups, were I added a comment on Turing's paper on monoids, which started the whole thing. Result 4 is the cellular automata prediction problem, which has the Conway Game of Life result.

In "ZF Independent", independent theorem 0 is "large cardinals", independent theorem 1 and 2 are CH and AC. I added independent theorem 3 which is Solovay's measurable R universe, and 4 was one of Shelah's mentioned already.

In "PA Independent", independent theorem 0 is Gentzen's down-counting from epsilon0, which should be mentioned because it's the grandfather of everything. indep. 1 is Goodstein, which is a finitary rewrite of 0, indep. 2. is Paris Harrington, which is also equivalent to consis(PA), and indep 3. is this tree theorem mentioned on the current page which I don't know anything about.

Last thing I did was add a comment on Hawking's claim that Godel prevents you from knowing the laws of physics. This is not accurate, because undecidability does not prevent you from knowing the rules to the game of life. That's like knowing the axioms. It just prevents you from predicting whats going to happen arbitrarily far into the future.Likebox 05:30, 12 October 2007 (UTC)

that needs a source. 1Z 08:03, 12 October 2007 (UTC)

The source in this case is Dr. Willard Obvious and his colleage Dr. Margaret Self-Evident, in their little-known but influential paper "Self Evident and Obvious Comment on Godel's Incompleteness Theorem". Sadly, their pioneering contributions to science and mathematics are seldom acknowledged.Likebox 17:28, 12 October 2007 (UTC)

Since I mostly just reorganized and edited, I figure the next person could prune away what they didn't like. I don't think I made a single claim that is in controversy. Is there consensus???Likebox 05:30, 12 October 2007 (UTC)

Here are the proposed revisions Likebox 01:02, 13 October 2007 (UTC)

The upper link has an extra space in it, whereas this lower link proposed revisions does not. I added some comments/emendations to the article at the upper link proposed revisions, but you won't see them in the lower link. Bill —Preceding unsigned comment added by Wvbailey (talk • contribs) 21:35, 14 October 2007 (UTC)

comment on new text

G.I.T (1931) is not "about computers" (1941...) 1Z 00:07, 15 October 2007 (UTC)

Actually, it is. Because by the middle 1960's Gödel had come to accept Turing's work as the sine qua non, going so far as to renounce his own recursion theory in favor of Turing-Post's version of "formal system":

Godel's 1931 is still not about computersm you are talking about later developments.1Z 11:04, 15 October 2007 (UTC)

I don't disagree. An article could "split" -- the historical Godel 1931 plus a modern explanation using a formal system "M" devised from an axiomatization (or at specificication of) an abstract-machine model, not a number-theoretic model such as P. I.e. rather than hewing too strictly to the arcane symbolism and difficult presentation of Godel, an explanation/example might use a more "modern" approach using "abstract computation machines". I know of no such approach. In fact I'd like to see one. Even Godel knew the paper was "dense"; he had intended to write a part II but became incapacitated and abandoned the attempt. His later 1934 is somewhat simpler, too, but still recursion-based. Bill Wvbailey 16:58, 15 October 2007 (UTC)

The following note in "Postscriptum", dated June 3, 1964, appears in Davis 1965:71-73. Here is where he utterly blows off recursion theory (Church 1936 and his own §9 General recursive functions) in favor of Turing 1936 and Post 1936:

"As for previous equivalent deifintions of computability, which, however, are much less suitable for our purpose, see A. Church, Am. J.. math, vol. 58(19360 pp. 356-358 (this anthology, [Davis 1965] pp. 100-102). One of those definitions is given in §9 of these lectures."

A skeptic might think he was sick of mind, but he repeats his assertion in a differnt way to van Heijenoort two years later (after working for months with van H on a new and better translation of his 1931):

"In consequence of later advances, in particular of the fact that due to A. M. Turing's work⁶⁹ a precise and unquestionably adequate definition of the general notion of formal system⁷⁰ can now be given, a completely general version of Theorems VI and XI is now possible....

"⁶⁹ see Turing 1937, p. 249

"⁷⁰ In my opinion the term "formal system" or "formalism" should never be used for anything but this notion.... I suggested certain transfinite generalizations of fomalisms, but these are something radically different from formal systems in the proper sense of the term, whose characteristic property is that reasoning in them, in principle, can be completely replaced by mechanical devices." (Gödel 1963, note at end of Gödel 1931 as appears in van Heijenoort 1967, 3rd printing 1972:616)

So yes, if you take the man at his word, he says the "proper" way to construct a formal system is with mechanical devices. Period. Bill Wvbailey 01:37, 15 October 2007 (UTC)

Fine, then explain that in the article, don't just baldly state it. 1Z 11:04, 15 October 2007 (UTC)

It is not only Godel's result that is about computers, but the later recursion results of Post, Friedberg, Muchnik, the minimal degree arguments, and most modern recursion arguments about the structure of the Turing degrees are about computer programs. All these arguments are greatly clarified by writing them in a reasonable modern syntax. I did that for a few of the early arguments, but it would be nice to do it for all of them, becuase this stuff is very important and IMO obscure for no reason.

One problem is that the recursion theorists write their computer programs in their own computer language, circa 1954, which is incredibly inexpressive. It does not have a "print your own code" primitive, it does not have a reasonable way to express self-modifying code, and any sophisticated data structure has to be described in set theory, which is equivalent to coding in LISP, which is unpopular for a reason. This is why I think it would be nice to take any opportunity to rewrite the recursion theory algorithms in a modern C-like syntax, which I think makes them so clear that they can be understood by anyone who has ever programmed a computer. Just my 2c.Likebox 06:28, 15 October 2007 (UTC)

If I understand this discussion properly (use of computer-like models to explain the G.I.T.) I see the difficulties as follows:

RE no O.R.: As wikipedians we're supposed to be using established sources. (I personally try to stick to print media that presumably has gone through a vetting process (I'm leery of self-published articles on the web, for instance). I try to restrict myself to what I can locate in an academic library).

But then there's the problem of examples -- when does an example become a form of O.R. That's a tough one.

RE computer programs vs recursion: I don't understand this either. But I have some theories:

(i) Set theory has been axiomized for at least 100 years (Zermelo 1908: Party-time!). The logic etc derived from it is pretty solid (assuming we accept the axioms). Ditto for the Peano axioms. On the other hand, abstract computational machine-models are NOT axiomatized ... as for why, see History of the Church-Turing thesis.
(ii) Because recursion theory is (kind of, more or less) axiomatized and is closer to (an extension of??) set theory and the Peano axioms, it provides a measure for abstract computation-machine models -- thus we have the Church-Turing thesis, not just the Turing thesis or just the Church thesis.

RE self-modifying programs: For your purpose the abstract computational machine model of choice is the Random Access Stored Program machine (RASP model). But the real trick behind all this is the availability of indirect addressing in your instruction-set. There's no O.R. here: as applied to abstract computational models, the notion has been in the literature since 1961. The first abstract-computation theorist to use indirection, as far as I've been able to trace it is Melzak 1961 An Informal Arithmetical Approach To Computability and Computation, Canadian Mathematical Bulletin, vol. 4. no. 3, September 1961. European researchers in the 1950's may have described this first (See Shepherdson and Sturgis 1963, JACM 10:217-255). By the early 1970's you see indirection actively-used by Hartmanis 1971 and Cook and Reckhow 1973. The nut is this:

"The indirect instructions are necessary in order for a fixed program to access an unbounded number of registers as the inputs vary" (Cook and Reckhow 1973)

And, if you don't have indirect addressing available (as is the case with the simple counter machines and random access machines (RAMs)) designing a universal program U is a bitch; you need to (in essence) Godelize the variables to effect indirect addressing. At least so far I haven't figured out a way to do it otherwise.

With indirect addressing in your machine's TABLE of instructions you can write a universal machine U in about an hour.

RE choice of abstract computational machine model: It seems that every abstract-machine "code monkey" has his pet model. Because they have indirect addressing etc., for your purpose I would recommend a look at J. Hartmanis 1971 Computational Complexity of Random Access Stored Program Machines, Mathematical Systems theory 5, 3 (1971) pp. 232-245. Also see Stephen A. Cook and Robert A. Reckhow 1973 Time-Bounded Random Access Machines Journal of Computational System Science 7(1973) 354-375.

RE computer programs: like the abstract-model theorists, every "computer-code monkey" has his pet "code" or form of "pseudocode". To avoid O.R. and every code monkey who comes along hacking your work and putting in their own version, I suggest (if it's possible) to write examples using an established abstract model that you can find in the literature perhaps augmenting it a bit, if necessary. If necessary exhibit "subroutines" (e.g. "multiply", "divide", whatever) and then use these thereafter. (Pick-and-choose the best from Minsky, Lambek, Melzak is pretty hard to use, Shepherdson-Sturgis, Cook and Reckhow, Hartmanis, Schonhage; just make sure you've defined your stuff up front).

For an excellent reference about this abstract-machine approach, with 141 references, see Peter van Emde Boas pp.3-66 "Machine Models and Simulations" in Jan van Leeuwen, ed. 1990, Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, ISBN 0-444-88071-2 (Volume A).

Bill Wvbailey 16:58, 15 October 2007 (UTC)

Thanks for the comments, and the references! I get lost in the CS literature. I agree that the model is a Random Access Machine. That's everybody's modern computer, and if you don't have a stored program and pointers (indirect reference, self-modification) it becomes a nightmare to do anything nontrivial. That's the serious problem with recursion theorists computer language.

No OR means no new ideas. It means -- don't put up your own crackpot theories, ideas, or syntheses of ideas. It does not mean the presentation can't be clear, concise, and original. As a matter of fact, to avoid plagiarism, it better be original! If you copy text, the guy you're ripping off is going to sue wikipedia.

As for "code monkeys" coming in, that's me.

If you feel that the style is confusing, by all means, find a clearer pseudocode. If you like recursion theory pseudocode, please write a complete proof in recursion theory. You could finish the recursion Godel proof that someone else started. But I notice that the page has been up for a long time and nobody else did that. Why not? It's because to write up the recursion theory code, you need to write a quine in first order logic. That's what Godel did. It's tricky to write a quine in any language, but this is especially annoying. You have to duplicate a variable to write a quine.

It's tricky enough that I notice a guy above said something like "No layman will ever understand Godel's theorem", which might be true for any non-LISP programmer. But actually, it's probably more true of students studying recursion theory than of any lay LISP programmer.Likebox 18:12, 15 October 2007 (UTC)

I'm against having anything here that purports to be a full proof of either of the theorems. That belongs maybe at Wikibooks.

I'm not against a very high-level description giving an idea of the proof, and I kind of like the computer-based approach as a way of making the arithmetization of syntax and the Kleene recursion theorem appear plausible without getting into detail. But I think Likebox's effort is far too chatty; it needs to be tightened and, ideally, sourced. Also it should be unified with the existing proof sketch (we certainly don't need two proof sketches). --Trovatore 01:35, 16 October 2007 (UTC)

Trovatore, I think you are usually right on the money, but this time, I have to disagree. I didn't give a proof sketch. I didn't give a plausibility argument. I gave a full 100% rigorous proof. There are no holes. There are no gaps. Because it focuses on computers, not logic, it only black-boxes quining, not arithmetization. There are two tedious part in conventional proofs, one is arithmetization, the second is the quine. The quine is usually produced by using either Godel's "two x's" thing or by Kleene's fixed point stuff. Neither argument is reasonable nowadays, because quining is a simple operation in C or ALGOL or FORTRAN, or any other not-even-modern language. Quining is completely trivial in assembly language, because you can read your own code.

If you use a computer, there is absolutely no explicit need to even talk about any arithmetization of syntax. You can just use any programming language to manipulate explicit strings in TeX. This is arithmetization as we do it every day on wikipedia. I think it's ridiculous in this day and age to talk about arithmetization as if it's a conceptual hurdle. Everybody knows ASCII, everybody knows UNICODE, and everybody knows TeX. The only conceptual hurdle that in Godel's proof is the quining. If you know how to quine, there is no hurdle.Likebox 05:15, 16 October 2007 (UTC)

What I'm saying is, even if you're right, a proof does not belong here. The broad ideas of the proof, yes. But not the proof itself. In general your style is too expository, not sufficiently encyclopedic. The expository stuff belongs somewhere else, like Wikibooks.

In any case, we do need to talk about arithmetization to some extent, because the hypotheses of the theorem say that PA is relatively interpretable in T, not that the basic notions of computation are relatively interpretable in T. --Trovatore 05:46, 16 October 2007 (UTC)

I see your point. I will respond on your talk page. Likebox 05:48, 16 October 2007 (UTC)

I reread Godel's paper last night to see what's going on. It's true--- he does use PA. But he does also assume without any hesitation that primitive recursion includes formal logic, and the "explicit" construction in his paper is far from explicit. He just lists a bunch of subroutines which if he could write as primitive recursive then he can complete the proof. The main routine, in section 2.5 is not done at all, it is only poorly sketched. That's because primitive recursion is a crappy programming language. This is not meant to denigrate the great work. It is obvious he can do it. But it is only obvious that he can do it because mathematical intuition at the time included the idea that primitive recursion is just a computation without unbounded loops. I think that was due to Kronecker. Maybe Godel. I don't know.

If I understand you, it was Herbrand's suggestion to Godel to introduce the unbounded operator. He did so in his 1934 lectures to the IAS. He called it his є-operator. As far as I know, Godel was the first, to really peg "primitive recursion", where he did so in his 1931. Another interesting note: his arithmetization method changed quite a bit between his 1931 and 1934. If you have a cc of Davis's The Undecidable that's where you can get a cc of his 1934. BillWvbailey 14:33, 17 October 2007 (UTC)

So while the letter of Godel's proof is that you can embed PA, the spirit of Godel's proof is that you can express an arbitrary statement about primitive recursive functions, about computer programs with for-loops, the ones in his proof. I think the spirit is easy to preserve. You can say, the axiom systems must describe enormous integers, it must be have enough operations to define at least one Turing complete function F(n) and its iterations F(F....(F(n))))), and it must be able to express any statement of the form (for all n) property(n) where property is some specific primitive recursive function which extracts the halting state and output of the program. That PA has these properties is obvious to anyone who knows PA.Likebox 16:46, 16 October 2007 (UTC)

A very important point of the historical context is the impact on the logicist project, which, having failed to reduce set theory to logic (via the refutation of Frege's system by the Russell paradox) still hoped to reduce arithmetic to logic. The Goedel theorems are widely held to have shown that this is impossible (though I have to confess I never completely followed that argument -- which is not to say I think arithmetic can be reduced to logic; I don't).

So we really can't get away from talking about arithmetic, I think. Note also that it's a lot easier to see that a foundationally relevant theory encodes PA, than that it encodes the C programming language. --Trovatore 17:40, 16 October 2007 (UTC)

Hmm. You're right about the history. The history is important. If I understood correctly, the idea you're referring to was that while set theory would not have a discretist logical foundation, maybe arithmetic can be given a firm discrete foundation. The Godel theorem shows that there is no fixed computer program which can generate all arithmetical truths, so there is no discrete foundation for arithmetic. That's a big blow indeed.

But the reason they called it "arithmetic" was to express the fact that the objects are discrete, and that an arbitrary reasonably finite computation can be performed. To distinguish it from "set theory" where you can talk about analysis and geometry. Saying PA back then is the equivalent of saying "computer" today. So I think that the dichotemy can be clearly expressed this way "While the Russel antimonies showed that set theory is not just logic on the universe of all sets, but requires a strictly ramified Cantorian theory of infinite ordinals, many hoped that arithmetic, which does not refer to unimaginably infinite collections like the set of all everywhere discontinuous functions on R, would have an associated computer program which produced all the true statements."

Regarding your second point, I think that to a C-programmer, the idea that you can encode the C-programming language in a random-access machine is much more obvious than any logic stuff, especially considering that gcc is almost a proof by construction. Also to any machine-level programmer, the idea that you can embed a random-access machine in PA is even more obvious. I mean, PA can speak about any ordered list of integers and any finite operation on them! The only subtlety is to find an addressing scheme which can refer to an unbounded memory, but you can cook up a scheme in 5 minutes. For me personally, I didn't study logic until way after I learned to program a computer, and I think that's true of a lot of newcomers to the field.Likebox 20:36, 16 October 2007 (UTC)

So first of all logicism, as I understand it (which isn't necessarily terribly well) is not particularly about discreteness. The logicist idea is something like this: Mathematics (or at least arithmetic) has no content external to pure logic, understood as "the science of making correct inferences". That is, once you get the definitions right, you should be able to do mathematics with no assumptions, no intuitive revelations, and no empirical discoveries, just following a pure chain of deduction from the definitions. That is, the truths of mathematics are analytic truths, "true by virtue of their meaning", like the statement "all bachelors are unmarried" (Kant's example from the WP article).

Whether this notion is even well-defined from the point of view of contemporary mathematical logic is not so clear; it seems to assume as given a notion of correct deduction that is not as clear as it might be. But what does seem clear is that there is no obvious reference to discreteness or computation. --Trovatore 04:06, 17 October 2007 (UTC)

This was my second question on your talk page: whether "arithmetic" confines you to "discrete symbols" (i.e. natural numbers). Yes, if we are to take Kleene's definition: "Arithmetic or number theory may be defined as the branch of mathematics which deals with the natural numbers and other (categorically defined) enumerable systems of objects such as the integers or the rational numbers. A particular such system (or the theory of it) may be called an arithmetic. The treatment is usually abstract.... the objects are usually treated as individuals [arithmetic in the narrower sense has to do with + and *, in the wider sense it is the full-blown number theory]. He says that the cardinal numbers of arithmetic are aleph0 or finite, whereas analysis deals with the real numbers and other systems of objects having the the cardinal 2^aleph0 (or higher) (p. 29)

"Logicism" per Kleene: Russell and Whitehead: "...mathematics is a branch of logic. The mathematical notions are to be defined in terms of the logical notions. The theorems of mathematics are to be proved as theorems of logic." (Kleene 1952:43)). Logicism died because the antinomies killed it -- and the theory of types could not resuscitate it. Specifically: some of the definitions are impredicative (cf p. 44), the axiom of reducibility was suspect, even by Russell himself. "Thus neither Whitehead and Russell nor Ramsey succeeded in attaining the logicistic goal constructively." (p. 45). Weyl 1946 blows it off, saying if you [are silly enough to] accept logicism then why not just accept set theory, which is simpler.

"Formalism" per Kleene: "formalism or axiomatic school" (Hilbert)). Formalism: "Classical mathematics shall be formulated as a formal axiomatic theory, and this theory shall be proved to be consistent, i.e. free from contradiction" (p. 53). So formalism pulls into itself more than just "logic" ... but what exactly?

What additional formalization did Godel bring to the party; What Godel 1931 brought to the party was the formation rule (concatentation) for the terms and from the terms the formulas, and then the substitution rule that allows you to stuff numbers (as "parameters" or numbers "passed back" from formulas) into variables and his notion of primitive recursion. It's unclear what Godel brought to the party. Apparently before 1931 the notion of "formal system" was highly-developed by Hilbert and Bernays, including "recursion" (witness Ackermann 1928's non-recursive function). Godel 1931 cites "the formal systems constructed recently by D. Hilbert and his co-workers so far has these have been published to the present. Hilbert 1922, 1922a, 1927, Bernays 1923, von Neumann 1927, Ackermann 1924. (NOTE: these are different in my two translations!). By 1934 Hilbert and Bernays had published their Grundlagen der Mathematik. Godel was very clear about the formality of his "system" in his 1934: "For the considerations which follow, the meaning of the symbols is immaterial, and it is desirable that they be forgotten." (p. 53).

Kleene 1952 "cleans" this up in his formal system (in his Chapter IV A Formal System (axiomatic number theory)). As does Godel, Kleene 1952 cites works of Hilbert and Ackermann 1928, Hilbert and Bernays 1934, 1939, Gentszen 1934-5, Bernays 1936 and "less immediate sources." "First, the formal system itself must be described and investigated, by finitary methods [his definition: "No infinite class may be regarded as a completed whole. Proofs of existence shall give, at least implicitly, a method for constructing the object which is being proved to exist." p. 63] and without making use of an interpretation of the system." (italics added, p. 69) I.e. it's all discrete symbols and syntax. No semantics whatever, just discrete-symbol manipulation. "Total abstraction from the meaning" (Kleene citing Hilbert, p. 61). There's an interesting discussion of "systems of objects" in Kleene p. 24ff. In particular, he notes that the axioms are defined from outside the system S, and "it is only from outside the axiomatic theory (i.e. in some other theory) that one can investigate whether one, or more than one, or not abstract system S satisfies the axioms."

This discussion in Kleene is not trivial and takes quite a few pages -- p. 43-65 -- hence cannot be easily summarized (by me). There's a lot about on what basis are axioms to be accepted i.e. about hypotheses concerning the "actual world" (p. 46) versus containing just an "ideal elements" or both (cf p.55), about the logicist notion of "number" versus the intuitionist and formalist notions, etc. Bill Wvbailey 19:19, 17 October 2007 (UTC)

recursive enumerability

Let A be a set of axioms and $U=\{u_{1},u_{2},\dots \}$ be the set of sentences undecidable over A.

Question: is U recursively enumerable? I.e. is there an effective algorithm for writing down all the undecidable statements of number theory, set theory, etc.? Does it depend on the particular axiom set? If the answer is known maybe it can be added to the article. Obviously you can write down infinitely many undecidable statements by iterating Gödel's diagonalization scheme but I don't know if you can get them all by such methods. Thanks.

I assume that by "u is decidable over A" you mean that either u or its negation is provable from A. If I knew that u was either provable or disprovable, then by searching all proofs I could determine which of these two options holds; but if a particular u is neither provable nor disprovable then the search would go on forever. If the set of undecidable sentences was alsou recursively enumerable, then I could enumerate that at the same time, preventing my search from going on forever. So if the set of undecidable sentences was enumerable, I could decide, given a sentence, whether it is provable, disprovable, or undecidable, which means that the set of provable sentences would be recursive. But for almost every first-order theory the set of provable sentences is not recursive, but only recursively enumerable. Tracing back, this means that the set of undecidable sentences must not be r.e. — Carl (CBM · talk) 12:28, 30 October 2007 (UTC)

Ah yes, of course. Thanks. —Preceding unsigned comment added by 75.62.4.229 (talk) 16:11, 30 October 2007 (UTC)

Modern Proof

Recently User:CeilingCrash removed the "Modern Proof" section, without (as far as I can tell) discussion on the talk page. He included a detailed comment for why he removed it, but I think it the edit should first be discussed on the talk page. To make sure everyone agrees that the proof is in fact bad before removing it. --DFRussia 11:54, 1 November 2007 (UTC)

I agree with removing that section, and I removed it again. That section didn't actually provide a proof - it instead gave a vague argument about "computer programs". It was alluding to a correct proof using the diagonal lemma, but such a proof would need to be written using the correct terminology (representability of computable functions, etc.) rather than vague statements such as "and that it has enough operations (addition and multiplication are sufficient) to describe the working of a computer." The supposed proof of the second incompleteness theorem was "To prove the second incompleteness theorem, note that the consistency of the axioms proves that DEDUCE does not halt, so the axiom system cannot prove its own consistency" which completely ignores the actual issue there, which is the arithmetization of proof.

This is not ignored. The arithmetization is sidestepped by using a modern computer, where arithmetization is automatic and a part of day-to-day life. It's ASCII and unicode.Likebox 21:53, 1 November 2007 (UTC)

I don't know whether we need a proof via the diagonal lemma in this article; we can discuss that. But if we are going to claim something is a proof it needs to actually prove something. — Carl (CBM · talk) 13:20, 1 November 2007 (UTC)

The proof is complete and correct, as others have verified. Please check the previous discussions first.Likebox 21:53, 1 November 2007 (UTC)

Ceilingcrash is correct -- both Turing and Church used the notion of arithmetization in their proofs. It is this plus Godel's use of a fully-specified proof system plus the "shift from "true" to "provable"" (to quote van Heijenoort) that, e.g. distinguished Godel's proof from Finsler's uncacceptable proof (1926). Whereas these key notions are probably understandable by most lay readers who've come to this article, where and exactly how the diagonal argument enters is absolutely obscure ... At least for me ... I know it's embedded in the "first" theorem somewhere, but I haven't been able to trace the exact steps because of Godel's difficult presentation: it's discussed in Rosser (1939?) but I haven't gotten that far. There's no doubt that Turing's argument is easier to follow for computer-science folks: his machine busily creates diagonal numbers from its "decider algorithm" working on numbers-as-programs until it fails to do so when its "decider" hits its own number to test. Yes, I would like to see more about the incompleteness theorems' diagonalization in this article. Bill Wvbailey 17:56, 1 November 2007 (UTC)

DFRussia was right, i shd have brought the issue up here first. The crux of my argument is that the C-T came some years after G, and uses G's most critical innovations. By using the C-T as a Lemma, we have smuggled in G, which of course makes G easy to then prove, but seems (to me) to mis-attribute the idea and is tail-chasing.

About diagonalization, I agree w/ WvB that the diagonalization trick is a quite vivid way to get incompleteness. (An ancestor of the technique can be seen in Cantor, to prove certain elements are not contained in a lower order of Infinity.) I don't think Godel expressed his argument this way, he finds the 'smoking gun' by beefing up the formal system with some elements of a programming language : string manipulation operators like substitute, concatenate, mapping of godel-number to symbol, etc. Once he has this, he has theorems which can make build theorems, and make assertions about their provability. Finally, he builds a theorem (G) which denies its own provability. An interesting exercise gives a gist of how this axiomatic "introspection" can be achieved :

In any programming language, write a program that prints out precisely its own source code (without resorting to tricks like reading the source from disk or memory.) Hint, you have to be clever about string substitutions, and it is permissible to ASCII codes to generate characters. Anyone who does this will readily understand how Godel made G.

I too would like to see if someone has recast Godel's argument using the diagonalization trick, which is so vivid and comprehensible. updated CeilingCrash 18:42, 1 November 2007 (UTC) 2007 (UTC)

I have edited the proof sketch to emphasize the diagonalization more, and to explicitly use the diagonal lemma. I think breaking that out of the sketch here is good, since it allows the reader to ignore how that formula is constructed for a while when reading this proof, and later investigate the proof of the diagonal lemma. Please let me know what you think; I'm done for this afternoon. — Carl (CBM · talk) 19:09, 1 November 2007 (UTC)|

Hat's off to CBM ! This is very nice indeed. Godel's creation of G is constructive, which is nice, because we get to see exactly what it is. But it is subtle and very difficult to follow. The diagonal argument proves existence - which is all we really need for incompleteness - and much easier to follow. Well done and thank you! (I added Hilbert's 10th problem to the examples just now.) CeilingCrash 19:53, 1 November 2007 (UTC)

Hopefully I did't offend anyone with my original roll-back. I am glad there is now an active discussion. You guys seem to have made a lot of progress on the article over the last hours. Well done --DFRussia 20:58, 1 November 2007 (UTC)

(deindent) Hello, I reinserted modern proof, and I would like to adress the objections raised. First of all, the argument is self-contained. It only uses the "Church-Turing" thesis to argue that formal logic is a computer program, which is not the general Church-Turing thesis, but a special obvious case. The argument is simplified by black-boxing the process of quining, which is an exercise in modern CS curriculum. The argument is otherwise complete. It is designed to be both correct and comprehensible to anyone who knows how to program a computer. It is in my opinion ridiculous to leave out such a simple proof, which is essentially equivalent to Godel and Rosser but much much easier to understand.Likebox 21:38, 1 November 2007 (UTC)

In response to the previous comments--- the persons who wrote them probably don't like this proof, because they have their own favorite proof. This is fine, there is no reason not to have multiple proofs. But there should be no dispute about the correctness of the argument. I included it precisely because it is the shortest, clearest proof.Likebox 21:53, 1 November 2007 (UTC)

Please don't be offended, Likebox, but we have consensus with myself, Wvbailey, and (implied anyway)CBM, who went to the trouble of retrieving the baby from the bathwater (the diagonal lemma) and reworking the Sketch Argument. Our objections to the Modern Proof are not stylistic, they substantive and listed in this discussion. Also, absent a source for it, it is Original Research. Long story short, Church-Turing based their work on Godel, not the other way around. I will roll back the inclusion re consensus, I hope not to spark an edit war.

Can you point us to a source for this version of the proof?CeilingCrash 22:44, 1 November 2007 (UTC)

(added) On second reading, it is a very elegant way to get at GIT, and it would be nice to retain this exposition in some form. It's not clear to me that we should call it a modern *proof*, since certain notions such as Quining and the fact a program can always print itself, would require expanding - and this expansion would lead us right back to godel (or an imitation thereof.)

I think if we retitle this section as something to the effect of, "GIT as seen from an algorithmic point of view", and note that some of these notions - so pedestrian today - owe their genesis to godel, it would be nice section to keep. Basically, if we don't call it a proof i'm cool. Others?CeilingCrash 23:11, 1 November 2007 (UTC)

The source is cited, although this discussion expands a little. The objections are not so substantive. They are right about the history, of course. But this is 2007 after all, not 1931. I am not at all offended, just puzzled. Why do you folks not like it? I really want people to understand Godel's theorem, and I am worried that current expositions are too bogged down in stupid details like arithmetization. This makes it very difficult for nonspecialists. I think every human being should understand Godel's theorem completely.Likebox 23:27, 1 November 2007 (UTC)

(Likebox and I got into an edit conflict.) I must confess to having judged this section too quickly. It is stunningly clear and beautiful, and on closer inspection I cannot substantively object to any part of it. (Upon first reading I thought CT was assumed in its entirety.) I wd be happy to see this text included, with the proviso that certain of these notions originated with godel (however commonplace and obvious to us today.) My apologies to Likebox. I would like to see certain bits expanded upon via link, for example to quining and to self-generating programs, i'd be happy to add these links to the text.

Oh - a few years ago I wrote a self-printing program in C and showed a printout to my coworker. He asked, "is that the source or the output?" At that moment, I achieved enlightenment :-b CeilingCrash 23:39, 1 November 2007 (UTC)

Thanks CeilingCrash. I incorporated a sentence that hopefully adresses your concerns.Likebox 23:44, 1 November 2007 (UTC)

My objection (not a strong one) is that a demonstration via machine computation smears two historically-separable events -- (i) a consistency proof re "arithmetic" versus (ii) an undecidability proof re an answer to the Entscheidungsproblem. Here's my understanding of what happened back then (ca 1930's):

Godel demonstrated (via his "1st" theorem VI) that undecidable "objects" existed, but he had not produced a specific "effectively-computable object" inside his formal system for our observation and amusement. (He was working with "proof systems", not "calculations/computations"). Thus Godel put to rest the Hilbert question of consistency, but the Hilbert question around the Entscheidungsproblem had to wait until the notion of "effectively calculable" was defined enough to proceed.

Church (1934) and Turing (1936-7), had to do two things: (1) define precisely the intuitive notion of "effectively calculable", and then (2) within a formal system and using their notions of "effectively-calculable", produce an "object" that would be, indeed, "undecidable". Church defined a notion of "algorithm" (lambda-calculus computations) and produced an "algorithmic object" that was "undecidable", but he worried about his proof (and soon emended it)). Turing, on the other hand, produced an indisputably "effectively-computable object" (a machine and an undecidable computation to be done by said machine) that even Godel accepted (in the 1960's) as the sine qua non. The consensus is that Godel could have easily gone the extra last step, defined "effectively computable" (for his purposes), and put an end to the Entscheidungsproblem once and for all, but he was just bored with the whole thing and went on to other stuff...

What we don't want to do is mix up the reader with respect to these various "Hilbert problems". When introduced into Godel's proof, machine computations add this other dimension ("effectively calculable"). At least that's my interpretation of the crux of the problem. It's not that a great machine-based demo can't offered, it's that such a demo may cause confusion. If anything such stuff should go into Turing's proof. Bill Wvbailey 00:55, 2 November 2007 (UTC)

I agree with your sentiment, although not with the conclusion. It is a major historical fib to claim that undecidability preceded incompleteness. But it is a shame to not use undecidability to prove incompleteness, because it makes the proof short and comprehensible. The section made no pretense of being historical, it was just a proof of the theorem using modern notions of computability that everyone recognizes. Perhaps a sentence pointing out that the section is ahistorical would be enough. Likebox 20:09, 5 November 2007 (UTC)

"Everyone" meaning computer programmers, right? I agree that readability by nonmathematicians is a worthy goal. But I have a difficult time calling it a proof, because it is so vague and handwavy about important details (like what language are the programs coded in, how are the desired program transformations coded, and is that language capable of addressing unbounded amounts of memory). —David Eppstein 20:14, 5 November 2007 (UTC)

"Modern proof"

This section is full of things that are either incorrect, completely vague, use the wrong or nonstandard language, or absurd. Examples:

"Assuming that a computer exists, and that formal logic can be represented as a computer program"

Of course a computer exists! But Godel's theorem is not about physical computers. Moreover, it makes no sense to say "represent formal logic as a computer program".

You might not be familiar with the completeness theorem. Godel's completeness theorem is an explicit algorithm to write down all deductions following from a given set of axioms. The algorithm is explicit, and can be written as a computer program. The only "nonphysical" thing about the computer required is the fact that it has infinite memory. That's the only idealization to go from a regular ordinary computer to a Turing machine.Likebox 20:34, 5 November 2007 (UTC)

The Quine lemma

The actual name of the needed result is the recursion theorem. Quines are just one application of the recursion theorem. The result below does not actually follow from quines, but from an application of the recursion theorem. In shor,t this is just wrong.

No it isn't. The recursion theorem is not the quine lemma, it is a confusing piece of obviousness required to prove that quines exist in recursion theory language. In computer science language there is no need for a proof, because you can easily write an explicit quine. The whole point of this proof is to avoid the recursion theorem.Likebox 20:34, 5 November 2007 (UTC)

The Halting lemma: There does not exist a computer program PREDICT(P)

There no such thing as the "Halting lemma". This is completely nonstandard terminology. There is a result relating to the halting problem, which is usually phrased as "the halting problem is unsolvable."

If you notice, the proof does not use the actual halting lemma. This is just presented as motivation.

proof: Write DEDUCE to deduce all consequences of the axiom system.

How is it supposed to do this? Most of an actual proof is spent achieving this!

It does this by the completness theorem. Godel did not prove this in any explicit way, and neither do any modern treatments. This proof is no better and no worse in that regard. Godel just listed a bunch of different algorithms which could be used to make a deduction program, and noted that they are all primitive recursive. Godel stopped writing down algorithms after a certain point, because it was too tedious, and he just noted "the rest of this requires writing a primitive recursive function to do this and this and this", where "this and this and this" is the rest of the algorithm of the completeness theorem. This proof just says flat out "There is an algorithm for deducing consequences of axioms", and does not bother to write any code. The difficulty in Godel's original proof is in the arithmetization, which is required because he did not know what a computer is, and in the quining, which he avoided by a trick.Likebox 20:34, 5 November 2007 (UTC)

Let DEDUCE print its own code into the variable R,

But DEDUCE is already defined - this is a second, different program.

DEDUCE first prints its code into R, then deduces all consequences of the axioms looking for the theorem R does not halt. It halts if it finds this theorem.Likebox 20:34, 5 November 2007 (UTC)

If the axiom system proves that DEDUCE doesn't halt, it is inconsistent. If the system is consistent, DEDUCE doesn't halt and the axioms cannot prove it.

Why? This is another thing that requires explicit justification but is presented with none.

The moment that the axioms prove that R does not halt, DEDUCE halts. Since the axioms can also calculate the finite-time state of DEDUCE, they can follow the operations of the computer program, this means that the axioms also prove that DEDUCE halts. That's a contradiction. So the axioms cannot prove that DEDUCE does not halt.Likebox 20:34, 5 November 2007 (UTC)

The assumption is that the axioms can follow the finite time operation of any computer program. This is an assumption in Godel's paper, where he asks that the value of any primitive recursive function can be calculated correctly by the axiom system. In other words, for any primitive recursive function f, the theorem F(n) = the number F(n) is a finite time deduction of the axiom system. This is true in PA, so he just assumes that PA is embedded in the system. The point of PA is only that the value of any primitive recursive function will eventually be calculated at some point in time as a theorem.Likebox 20:34, 5 November 2007 (UTC)

If the axiom system is consistent, it cannot prove either ROSSER eventually prints something nor the negation ROSSER does not print anything. So whatever its conclusions about DEDUCE, the axiom system is incomplete.

This, again, is just a restatement of what is supposed to be proved.

No it isn't. It's a proof. ROSSER prints its code into R, and looks for theorems about its behavior. If it finds a theorem that says "You do this" it does "not this". If it finds a theorem that says "You do not do this" it does "this". This is exactly ROSSER's argument for avoiding the omega-consistency issues, translated into modern language.Likebox 20:34, 5 November 2007 (UTC)

To prove the second incompleteness theorem, note that the consistency of the axioms proves that DEDUCE does not halt, so the axiom system cannot prove its own consistency

This "noting" does not prove the second incompleteness theorem, which requires a great deal of effort to prove.

It only requires a great deal of effort if you do not understand it. If you understand it, it is obvious. There do not exist theorems which "require a great deal of effort to prove". Either you get it or you don't.Likebox 20:34, 5 November 2007 (UTC)

R. Maimon "The Computational Theory of Biological Function I", arXiv:q-bio/0503028

The reference is an unpublished paper in the arxiv, not any sort of respected logic text.

Respectibility is a political decision. it requires a vote.Likebox 20:34, 5 November 2007 (UTC)

In short, this "modern proof" could only be salvaged by completely rewriting it. But there is already a proof sketch in the article, and if this one were fixed there would be two proof sketches. In any case, the current state of this section is embarrassing;it claims to be a proof but is just handwaving. Removing the section is the right thing to do. — Carl (CBM · talk) 01:44, 2 November 2007 (UTC)

Agree that certain terminology needs tweaking, especially "assume a computer exists." Is there a subtle error in it? I think we shd keep the standard Sketch, but from a pedagogical viewpoint this I think this perspective is valuable provided there are no serious gaps (as CBM claims) and, hopefully, it can be sourced to dead trees. If it is correct, I would be suprised if it's not published. To address one of the alleged gaps, can't DEDUCE proceed by brute force, attempting all rules of inference against all axioms and theorems ? I'd like to see where we could go with some small terminology changes and gap-filling.

It may indeed be very easy to understand GIT from a modern perspective. Much of what Godel had to invent, from Godel-numbering to his string manipulation functions, as well as the conceptual decoupling of symbols from meaning, we get for free if we start with the idea of a computing machine. What is admittedly historical heresy may be pedagogical gold. Seems worth a shot, anyway. CeilingCrash 02:08, 2 November 2007 (UTC)

We don't need two proof sketches, though. We could add in that a consequence of the incompleteness theorem is that, when everything is formalized properly, a consequence of the incompleteness theorem is that there are Turing machine programs that cannot be proven to halt and cannot be proven not to halt (such as the program that searches for a Godel number of a proof of the Godel sentence p from the proof sketch). The proof sketch in the article and the "modern proof" are not actually very different; the recursion theorem used in the "modern proof" is just the computability analogue of the recursion theorem. There are indeed large gaps in the exposition of the "modern proof". This is evidenced by the fact that he other proof sketch is just a sketch, while this is claimed to be a "proof", but this is much shorter. The reason that the proof of Godel's theorem is usually found difficult is because it is difficult. It doesn't serve the reader to claim the "modern proof" is a proof when in fact it doesn't even use existing terminology correctly. — Carl (CBM · talk) 02:12, 2 November 2007 (UTC)

If we repair the terminology, and avoid referring to this section as a 'proof' (which Like has already changed), would that be acceptable? I see it as a perspective, a pedagogical tool. If I had to explain GIT to a modern human, for instance, I think i would do it this way. CeilingCrash 02:43, 2 November 2007 (UTC)

If you would like to rewrite it somewhere in a sandbox, I'd be glad to comment on it. The fact that incompleteness of axiom systems is related to recursive unsolvability of problems is well known, and a section on that would certainly be worthwhile, especially if it didn't try to prove the theorem but just showed how the two are related. In the end, any actual proof has to deal with Godel numbering, arithmetization, etc.

At a bare minimum, the terminology would need to be made standard, and the vagueness would need to be reduced. — Carl (CBM · talk) 02:50, 2 November 2007 (UTC)

Sounds good to me, I'll start a sandbox in my user:Talk soon and post the link here ... CeilingCrash 02:58, 2 November 2007 (UTC)

I have already rewritten it here. — Carl (CBM · talk) 03:00, 2 November 2007 (UTC)

Rewrite

(outdent) I think I have a dead-tree source for this, I can't access the whole article tho (not a member)

A Proof of Godel's Theorem in Terms of Computer Programs, Arthur Charlesworth, Mathematics Magazine, Vol. 54, No. 3 (May, 1981), pp. 109-121. http://links.jstor.org/sici?sici=0025-570X%28198105%2954%3A3%3C109%3AAPOGTI%3E2.0.CO%3B2-1&size=LARGE&origin=JSTOR-enlargePage

CeilingCrash 03:14, 2 November 2007 (UTC)

I'll email you that article; the proof is well known in any case, so there is a source somewhere. I rewrote the section to be more explicit about what's going on. It now gives a sort of proof sketch of how to use the undecidability of the halting problem to prove Godel's theorem. It currently glossed over ωconsistency, which could be fixed. I hope other people will add links and smooth the text some. — Carl (CBM · talk) 03:24, 2 November 2007 (UTC)

Comments by likebox

I am quite familiar with the completeness theorem. It does not show that recursive functions are representable in arithmetic - that proof of representabilily is the first third of the proof of the incompleteness theorem. There is simply no way to prove the incompletness theorem without some sort of arithmetization result. And Godel's original proof did explicitly develop a formula for Bew...

The idea that the recursion theorem can be avoided by a reference to some sort of "quine lemma" is interesting, but there is no result well-known as the quine lemma, and the result needed here is not just the existence of a quine but the existence of a fixed point for a certain recursive operator. Only the recursion theorem is going to give you that.

Statements such as 'It only requires a great deal of effort if you do not understand it. If you understand it, it is obvious. " seem to indicate some unfamiliarity with the idea of a mathematical proof. The idea is to justify statements to a level where they are convincing to the intended reader. "Either you get it or you don't." is not the way things are proved in mathematics.

Can you say what you disliked about the rewritten version? I tried to keep the informal tone while not having all the terminological errors and vague claims of the "modern proof".— Carl (CBM · talk) 21:14, 5 November 2007 (UTC)

The person who wrote this has never written a quine. If you actually spend the time to write a quine, then it will become clear to you that you can turn any program into a quine by adding a quining subroutine. The subroutine will print out all the code before the subroutine, then print itself out, then print out all the code after the subroutine, and it is obvious to anyone who has written a quine that this will produce a printout of the whole code. Manipulating the printout can then simulate the code, and turning the printout into an arithmetic object is automatic, since the printout is already an enormous ASCII integer.

This result does not require a recursion theorem or a fixed point theorem. It only requires about half-an-hours effort to sit down and do it. It is assumed in the proof that the reader has already done this at some point in their life, otherwise the proof will be incomprehensible, since the central event in the proof is the printing out of your own source-code.

Once you understand this, and this is not completely trivial, the rest of the proof is trivial. The whole game of Godel and Turing is really just a game of self-reference, and the self-reference is best stated in a modern programming language where it is self-evident.Likebox 20:57, 7 November 2007 (UTC)

Dude. That result doesn't require a fixed point theorem: it is a fixed point theorem. Face it, when you write about this sort of stuff, you, Likebox, are acting as a recursion theorist. You're just doing so using nonstandard language. But here at Wikipedia, our task isn't to invent or popularize new language to describe existing results: it is to explain as clearly as possible those results using the standard language already in use. Anything else would be original research. —David Eppstein 21:39, 7 November 2007 (UTC)

It is not original research. It is original exposition. Those are two different things. Learn to distinguish between them.Likebox 22:13, 7 November 2007 (UTC)

another question

Does the second incompleteness theorem apply as well to second order logic? In particular, can the classical Peano axioms (i.e. with full second order semantics for the set quantifier in the induction axiom) prove their own consistency? Thanks. —Preceding unsigned comment added by 75.62.4.229 (talk) 10:01, 2 November 2007 (UTC)

There are two possible answer, based on what you want "incompleteness" to mean in the absence of the completeness theorem, which does not hold for second-order logic. The following are true; pick the one you want.

Peano arithmetic in second-order logic has exactly one model. Thus it is semantically complete - every sentence in its language is either a second-order logical consequence of the second-order PA axioms, or the negation of a second-order logical consequence of second-order PA. In this sense, there is no incompleteness theorem for second-order PA.
There is no complete, effective proof system for second-order logic. Given an effective proof system, the proof of Godel's incompleteness theorem gives an example of a true sentence of second-order PA that is not provable in that system. So in this sense the incompleteness theorem continues to apply. Unlike the first-order case though, this isn't a special property of theories of arithmetic; no second-order theory that has an infinite model can have be given an effective proof system that proves all the logical consequences of the theory.

— Carl (CBM · talk) 12:09, 2 November 2007 (UTC)

Let me expand on Carl's statement that "There is no complete, effective proof system for second-order logic.". Contrary to the situation in first-order logic, the set of consequences of a finite set of axioms may not be recursively enumerable in second-order logic. Worse, the set of consequences may not even be definable in the language of second-order logic. In which case, the "formula" stating that the second-order theory is consistent is not only unprovable, it does not even exist in the language. JRSpriggs 18:45, 2 November 2007 (UTC)

Not a proof

IS TOO A PROOF! Likebox 23:40, 5 November 2007 (UTC)

I see that Likebox has reinserted the "modern proof". I insist that this is not a proof, and cannot be a proof until notions such as what programming language is being used and how it is encoded are nailed down, which would make it not dissimilar in length and content to the standard proof. At best this is a proof sketch. It is also phrased in such a way as to make it sound like original research, although I am sure one can find printed sources for similar expositions. I would like to request that the section either be removed again (my preference), or that it be called a proof sketch, the word "modern" removed, sources provided, and it be incorporated more smoothly into the existing "proof sketch" section rather than trying to stand alone as a separate section. —David Eppstein 21:12, 5 November 2007 (UTC)

Of course there is no exact line between a "proof" and a "proof sketch" (or more precisely, if one attempts to draw such a line, one will find that virtually all published proofs are "sketches"), so let's not waste effort arguing on whether it's a proof or a sketch.

I think we can all agree that a valid proof/proof sketch along these lines is possible (whether Likebox's specifically is such a one, I have not checked), and I agree with Likebox that such an approach more easily connects with many people's intuitions, replacing the tedious proofs of the recursion theorem and arithmetization with such things as correctness of compilers -- things that readers haven't personally checked at a level that could be called "proof", but which they're more willing to believe on the basis of experience.

However I agree with David that the proof needs to be made less personal and idiosyncratic, and that it should be integrated with the other proof. --Trovatore 21:25, 5 November 2007 (UTC)

(e/c) Please note that the "Relationship with undecidable problems" section is the same idea, just rewritten to use more standard terminology. It presents the same proof outline (although it is does a better job of alluding to the fact that any undecidable, r.e. set can be used). It is intended to be a sort of compromise, including the ideas from the flawed "modern proof" section without the expositional problems I described at length above. — Carl (CBM · talk) 21:27, 5 November 2007 (UTC)

I see that there is controversy, and I would like to comment. I respect all sides here, and I am not trying to be a bully. I just wanted to explain.

First I did come up with this proof, but I am not the first person to come up with it. It is ideosyncratic because I don't want to use language which a layperson cannot follow. That is the crucial part, and replacing the discussion with a discussion which uses "standard terminology" is just code for making it obscure. Please do not make a clear discussion obscure.

Using standard terminology has another insidious effect in that it protects those who benefit from a monopoly on knowledge. This authority-reinforcing tendency is natural, but in my opinion, unfortunate.

As for technical precision, this proof is exactly as rigorous, no more and no less, as Godel's original exposition. I took it largely from Godel's paper, except replacing arithmetization with a modern obvious arithmetization (ASCII and TeX), and replacing statements about deductions with statements about computer programs that do the deducing. The proof is identical, but is much easier to follow, because modern readers know what a computer is. There really is no difference in the content in any way. Perhaps the reason it strikes people as implausible is because they think "it can't possibly be that simple!" Sorry folks, it is.Likebox 22:52, 5 November 2007 (UTC)

The difficulty is not whether computers can do things - the halting problem is easy to prove because it is just about what computers can do. Godel's theorem requires proving that some universal model of computation can be faithfully represented within arithmetic. In his original paper Godel explicitly demonstrated this. Now people may be more willing to take it on faith, but any actual proof must still address arithmetization. After Smullyan's influence, the most common "modern proof" is the one using the diagonal lemma. — Carl (CBM · talk) 23:13, 5 November 2007 (UTC)

Look, you're absolutely right. I didn't prove that arithmetic embeds a computer, and Godel did show that arithmetic embeds a "computer" (meaning a computer running the algorithm of the completeness theorem and only the algorithm of the completeness theorem) in a somewhat more explicit way. But if arithmetic doesn't embed a computer, it's a pretty sorry system! If that's true, then you can't make statements about the behavior of computer programs in arithmetic. That's why I stated the theorem about axiom systems which can describe computation, not as a theorem about Peano arithmetic.

To prove that Peano arithmetic embeds a computer, you can use Godel's system--- write an integer as a list of prime powers:

n=2^{n_{0}}3^{n_{1}}5^{n_{2}}7^{n_{3}}

and note that some first order sentence extracts each

n_{i}

from n, since the property of being the n-th prime is primitive recursive.

If you want to embed a turing machine, let

n_{0}

be the state of the head, let

n_{1}

be the position of the head, and let

n_{2},n_{3}...

be the content of the tape. Then you need to construct a first order sentence which says that the update of the quadruple

(n_{0},n_{1},n_{n_{1}})

will be

(n_{0}',n_{1}\pm 1,0\;\mathrm {or} \;1)

with a long list of options to describe different outcomes depending on the state of the head. Do I need to go translate that explicitly into first order sentences? It would require a lot of fiddling around with pairing functions and prime-extraction functions. What's the point? If this couldn't be done we would just throw away Peano arithmetic.Likebox 23:38, 5 November 2007 (UTC)

That's completely backwards - Peano arithmetic is justified as a theory of the natural numbers. The relationship between arithmetic and computability is not a motivation in the mere definition of PA, and PA would still be of interest if it didn't represent computable functions. The entire point of a rigorous proof of the incompleteness theorem is that it has to show that a sufficiently strong theory of arithmetic can represent something - either some basic computability or some basic proof theory.

I copyedited, but didn't remove, the stuff you added. Please work towards a compromise version, rather than merely reverting. Remember that (1) we don't need to prove everything here and (2) the general consensus in this article is not to dwell on the Rosser extension of the theorem, since all true theories of arithmetic are ω-consistent anyway. Try to focus on making the section match the rest of the article. There is a lot of work left to do, but I will leave it alone for tonight. — Carl (CBM · talk) —Preceding comment was added at 23:48, 5 November 2007 (UTC)

Likebox, please quit reverting, and get the "political" chip off your shoulder. None of us wants to hide the Goedel theorems from the common man. But an encyclopedia is not a teaching tool, it's a reference work. You need to make your additions consistent with that, or convince us that a departure from that principle is justified in this case. --Trovatore 23:56, 5 November 2007 (UTC)

That's your point of view. The effect of this point of view is exactly to hide the Godel theorems from the common man.Likebox 01:06, 6 November 2007 (UTC)

Spelling nit

Please, everyone, quit writing "Godel", even in the talk pages; it's a flat misspelling. You don't have to go to the effort of putting in the ö character -- just write "Goedel", which is correct. The umlaut is not a diacritic in the ordinary sense, but a marker for the missing e. --Trovatore 00:00, 6 November 2007 (UTC)

" language that should have been retired decades ago"

Moved from User talk:CBM

Look, I sympathize with your position, but do not edit a proof you think is invalid. Think about it for a few days first. Your edits make it imprecise and vague, by reverting to very, very unfortunate recursion theory language, language that should have been retired decades ago. I worked hard to make it correct and precise.Likebox 23:52, 5 November 2007 (UTC)

It isn't our place to decide what terminology should have been retired when, and a consequence of WP:NOR is that our articles use standard terminology. In the case of Recursion theory means terminology such as "represent all computable functions" and "recursively enumerable set". If you want to change the world, or make people use new terminology, Wikipedia is not the place for you.

In the meantime, please try to work towards a consensus version. I have no objection to the idea of a sketch of a computational proof, but several people including me have expressed reservations about the current wording. — Carl (CBM · talk) 23:58, 5 November 2007 (UTC)

I am not asking that the recursion language be scrapped. I am asking that you include a reasonable proof in computational langauge in addition to a proof in recursion language. This might have the effect of causing people to abandon recursion theoretic language in the future, but that's not for me or Wikipedia to decide. But there are both people who believe in recursion language, and people who do not. It is ridiculous to assume that recursion language is "preferred" because many people who do research in the field are forced to use it. You must represent all points of view in proportion to their number.Likebox 00:24, 6 November 2007 (UTC)

Also, I don't really care what the language is, so long as the computer programs are spelled out precisely, and their properties are manifest. The edits that you have done have made the proof vague.Likebox 00:26, 6 November 2007 (UTC)

From my perspective, there is no significant difference between computer science terminology and recursion theoretic terminology. If you believe there is, I encourage you to present some references to computer science texts that use your preferred terminology, so that the other people here can see how the terms are defined in those texts. — Carl (CBM · talk) 00:40, 6 November 2007 (UTC)

That is not true. You can easily write self modifying code in computer science language, you can't do it easily in recursion language. The computer science texts are "The C programming language" by Kernighan and Ritchie, and the countless papers in the 1970's on Random Access Machines. The existence of pointers and indirect adressing are crucial, and are hard to mimic in recursion theory. The insights of the 1970's need to be recognized, although they have yet to change any of the recursion theory texts. That doesn't matter. You can keep all your favorite language. Just don't delete someone elses favorite language.Likebox 01:05, 6 November 2007 (UTC)

Kernighan and Ritchie is not a text on theoretical computability, it's about the C programming language... There are lots of computer science texts on computability theory. In my experience, they use virtually the same terminology as mathematics texts on computability theory. If you can provide some counterexamples, I will be glad to look through them. As I said, Wikipedia is not the place to right the wrongs of the world. If you can't justify your additions in terms of the existing texts and standard expositions of the topic, it will end of removed. It's up to you to give it more justification than just "I like it". — Carl (CBM · talk) 01:09, 6 November 2007 (UTC)

Can someone please clarify what is meant by 'computer science language'? I am aware that there are two names used for the field 'recursion theory' -- that, and 'computability theory', the latter being the more modern and by some preferred. Do you mean a particular programming language (like C, Perl, Python, ADA, whatever...) Thanks. Zero sharp 01:13, 6 November 2007 (UTC)

Only Likebox can say for sure what he or she means by "computer science language", but it refers to terminology, not a programming language. Based on edits here and to Halting problem (also see my talk page), it seems Likebox dislikes the standard terminology of recursion theory, preferring to use terms like "computer program" instead "computable function", etc. — Carl (CBM · talk) 04:47, 6 November 2007 (UTC)

The distinction between "computer science language" and "recursion theory language" is a distinction between the way in which you describe an algorithm. A recursion theoretic description does not have enough operations which allow you to print your own code in any simple way, nor does it have an easy way to state things like "print Hello World". This is an important terminology distinction, which makes the proof I wrote clear and comprehensible, and makes the proof that is presented in the current version an unacceptably vague sketch.

The current text, while it follows the outline of my proof, does not do it very well. The new text does not prove the Rosser version of the incompleteness theorem at all, and requires an omega-consistency assumption which is not acceptable in any way. The current text does not give a rigorous proof of anything at all, because it does not specify the computer programs precisely enough. It is just a bad sketch. The discussion I gave is a complete and correct proof, as rigorous as any other presentation. To replace a correct proof with a vague sketch is insane.

Finally, this proof has the gall to pretend that Kleene et al. and alls y'all actually understood the relation between halting and Godel's theorem before you read the proof that I wrote. While, in hindsight, after a few weeks of bickering, it is clear to all you folks that quining and the fixed-point theorem are identical, that Godel and Halting are identical, none of you knew exactly how before I told you. If your going to use my insights, use my language and cite the paper I cited. The only reason this is not original research is because some dude wrote a paper in 1981, and because of the reference provided. To pretend that this proof is somehow implicit in the standard presentations is a credit-stealing lie. It was precisely because the standard presentations are so god-awful that I had to go to great lengths to come up with this one.

So I revert to the old terminology, and I ask that you hold some sort of vote among neutral parties. If you are going to prove the theorem, the proof I gave is the shortest, the clearest, and comes straight from Erdos's book. It describes the computer programs completely and precisely, so that any programmer can actually write them. It proves the strong version of the theorem, and it is logically equivalent to Godel's original proof. But the language and presentation are not due to Godel or Kleene. They are due to that dude in 1981 and to a lesser extent to the author of the more recent preprint. Certainly not to any recursion theorist.Likebox 06:22, 6 November 2007 (UTC)

Ok I know I'm late to the party here, but Likebox, can you please cite (and my apologies if you have already done so elsewhere but I"m having a REALLY hard time following this discussion) 'Erdos' book' and "that dude in 1981" Zero sharp 06:40, 6 November 2007 (UTC)

and, for the record, can you explain why this is not Original Research? Thanks. Zero sharp 06:42, 6 November 2007 (UTC)

It's not original research because somebody published it already in 1981. That's this guy, from the discussion above:

A Proof of Godel's Theorem in Terms of Computer Programs, Arthur Charlesworth, Mathematics Magazine, Vol. 54, No. 3 (May, 1981), pp. 109-121. http://links.jstor.org/sici?sici=0025-570X%28198105%2954%3A3%3C109%3AAPOGTI%3E2.0.CO%3B2-1&size=LARGE&origin=JSTOR-enlargePage

The logic of the discussion follows that paper, but the language follows the reference cited. Erdos's "book" is God's book of proofs, the shortest proof of every theorem. It's not a real book, but a mathematician's description of the most elegant proof of a theorem. I am pretty sure that the proof presented here is the book proof of the Godel's theorem.Likebox 06:47, 6 November 2007 (UTC)

I put the reference to Charlesworth in. I would have put it in earlier had I known about it.Likebox 06:53, 6 November 2007 (UTC)

One thing I agree with Likebox about is that this proof concept is not original research (although the citation Likebox gives isn't ideal). It is very well known that Godel's theorem can be proven from the existence of an r.e. undecidable problem. Such a proof does have the advantage of highlighting the role of effectiveness in the incompleteness theorem.

But the language Likebox is proposing is very nonstandard - for example, his "quine lemma" is not a lemma about quines but actually Kleene's recursion theorem. I have no objection to the idea of a computational proof in the article, but it needs to use standard terminology. The text also fails to read like an encyclopedia article, fails to integrate into the rest of the article, and obscures what is going on by dwelling on specific programs too much. I keep editing it to resolve those issues. — Carl (CBM · talk) 12:32, 6 November 2007 (UTC)

I once saw Bob Solovay present a similar proof on a blackboard in about 15 seconds, so it's not as if logicians have never heard of Turing machines. Maybe this situation is best resolved (parties willing) if Likebox were to write up a computer-based proof as a wikibook module, which the encyclopedia article could link to. Wikibooks have more room for exposition than encyclopedia articles do, wikipedia should link to wikibooks in preference to traditional books when it can, and wikibooks.org definitely needs more coverage of logic-related subjects.

Another thought: spin off a new article called Godel incompleteness theorems: Modern proofs or some such, and link it back to this article. Then everyone can discuss it on that page. The fact that there is a published article (I've read it now) should alleviate the O.R. concerns. [Note: that is a pretty good article. Its lead-in commentary follows to some degree Rosser 1939 "An Informal Exposition..." (found in The Undecidable) and Gödel 1934 §6 "Conditions that a formal system must satisfy..." (p. 61ff in The Undecidable) ]. Another thought if everyone howls about the first suggestion: create a page in your "user space" as follows User:Likebox/Gödel modern proof and move your proof there until its ready to be moved over to the new sub-article. (If you want, I will create the page for you). Others can contribute on its talk page. I want to look at it as if it were an article, not as part of your talk page or in history. Bill Wvbailey 15:16, 7 November 2007 (UTC)

We don't need another spinoff article/POV fork/whatever it would be. We already have one proof sketch spinoff page; Wikipedia is an encyclopedia, not a compendium of numerous expositions of the same proof. Someone else suggested wikibooks as a place Likebox might be able to publish his proof.

There is no difficulty here with original research; the proof is well known. The issue is that Likebox eschews interest in working towards compromise [4]. The proof Likebox is presenting is exactly the proof from Kleene 1943, just rewritten to avoid terminology that Likebox rails against [5]. Even if Likebox were right that the entire computer science and math logic community uses poor terminology for basic computability theory, we're not here to cleanse the world of bad terminology. It's ironic that Likebox motivates his recursion-theoretic proof by saying 'there is not a single shred of insight to be gained from learning any recursion theory'. — Carl (CBM · talk) 15:55, 7 November 2007 (UTC)

I hear you. I think a "semi-formal" (i.e. a really good-quality) "non-recursion-theory" version (i.e. "computational-machine"-based) is not going to be trivial, especially if it does not invoke undecidability of the "halting problem" as a premise (a cop-out IMO). I've deconstructed (and compressed into bullet-points) part of the Charlesworth paper, part of Rosser 1939 and part of Gödel 1934 §6 at User:wvbailey/Explication of Godel's incompleteness theorems -- it's just my holding/working place, I have no further intentions for it at this time. But the deconstructions are quite interesting and may be useful. Bill Wvbailey 17:23, 7 November 2007 (UTC)

Although likebox will no longer touch this encyclopedia page with a ten foot pole, I would like to comment that I came up with my proof indepedently many years before I actually studied any logic or any recursion theory. I did read "Godel Escher Bach" though when I was in high school, so it wasn't a research project, just an exposition project.

Knowing this nifty proof made me curious to see how the professionals do it, so some years later I went and audited a whole bunch of recursion theory classes, and went to logic seminars for two years so I could follow their version of the thing. It was a painful and frustrating experience. All their results were trivial, and expressed in godawful obsolete language that disguised the triviality!

But at least the recursion theorists understand it, or so I thought. But what I discovered, to my horror, was that with the exception of a very few very senior faculty members, none of the students and precious few of the postdocs or junior faculty actually followed the proof of even a result as elementary as Godel's theorem. This made me very sad, and I didn't know what to do.

The way I discovered this was by giving my proof of the theorem to a graduate student, who understood it. He then asked the (incompetent) junior faculty running the recursion theory class "Can you prove that it is undecidable whether a program runs in exponential time or polynomial time on its input?" The junior faculty fiddled around with the "s-n-m theorem" and the "recursion theorem" and the "fixed point theorem" for a long, long, time, and could not do it. This is unbelievable! It's a trivial thing to prove.

The proof is thusly: Suppose PREDICT(R) predicts whether R runs in polynomial time or exponential time on its input. Let SPITE(N) print its code into the variable R, calculate PREDICT(R), all the while ignoring N, then if PREDICT says "exponential", SPITE runs a polynomial algorithm on N, and if PREDICT says "polynomial", SPITE runs an exponential time algorithm on N.

Why couldn't junior-faculty do it? Becuase the Kleene fixed point theorem puts the source code to SPITE on the god-damn input-stream of the Turing machine. It's then hard to say how long the input is. You need to conceptually separate the input part which is the source-code from the input part which is the input, and junior-faculty got confused. This sorry story is still repeating itself in every recursion theory department in the country and in the world.

So here's wikipedia. That's what wikipedia is for--- for disseminating knowledge that's well known. As far as a proper proof, stop kidding yourself. The proof I wrote and that is linked is more rigorous than anything else in the world, and everybody knows it.Likebox 19:02, 7 November 2007 (UTC)

Thank you for putting your work at User:Likebox/Gödel modern proof so I can look at it. Bill Wvbailey 21:55, 7 November 2007 (UTC)

Cool, I'll get a look at it there too. The critical point - and I missed it the first time through myself, is L's proof does not assume CT or Halting. Rather, it proves it so quickly you might miss it. SPITE() is designed to defy a test of halting, H. It feeds itself (using the 'quining' key to self-reference) into H, and does the opposite of what H predicts. Spiteful, that function.

Get Russell a hanky. Conceptually, to my way of thinking, the proof is as simple as this :

a) a statement (S-expression in LISP, piece of code, whatever) can output its own source. (quining.) Try it in any language, it's fun and non trivial.

This gives the key to self-reference. Rather than printing, the output string could be assigned to a variable named Myself. This is counter-intuitive as hell but within the grasp of any student eager to experiment. The point is source code can mention 'Myself' or 'This source code' in a very real and executable way.

b) We can now defeat any proposed Halting test for source code. The function Spite() deliberately breaks the H-test, by using the self-reference trick in a) to feed itself into H, peek at the result, and either hang or crash - whichever makes a liar out of H.

c) It is then a reasonably short trip from Halting to Incompleteness (see main article.)

Whatever one's view of Likebox, the simplicity and clarity of this exposition is stunning. Given this outline, any 'ordinary' mathematician could fill in the gaps to reconstruct a proper proof without, I believe, any notable insight. Any undergraduate, with an affinity for such matters, can grasp the key insights and defend the main thesis. Amazing. The Theory of General Relativity was once hopelessly inaccessible even to many professional scientists, as was Galois Theory. They are not so today. Over time the conceptual landscape changes and new paths are sought to the peaks. Entirely new hills rise and new perspectives emerge from which formerly obfuscated landmarks can be clearly seen. This process is to the greater good.

Any one who doubts this is encouraged to try to extract F=MA from Newton's Principia.

I believe if the reader carefully steps thru L's proof, and ignores trivial matters of terminology (they are easily remedied), s/he will see that it is a) self-contained and b) free of significant gaps. Erdos used to say, when a proof has gotten to the crux od the matter with maximum simplicity, that it was in God's book. If there is a God and He has a book, this proof is in it. updated CeilingCrash 06:55, 8 November 2007 (UTC)

Nobody disagrees that a proof of the first incompleteness theorem can be obtained using computability; this proof is in the article at this moment. The problem is that Likebox's actual exposition is unsuitable for the encyclopedia, as numerous people have pointed out. I'm sure some compromise wording can be found. — Carl (CBM · talk) 13:51, 8 November 2007 (UTC)

When people of good faith compromise with narrow-minded people with a language agenda, the result is an incomprehensible piece of junk. One must defend good exposition from such attacks.Likebox 18:18, 8 November 2007 (UTC)

Reference - Kleene 1943

Since the question of original research came up, I looked up a reference for this proof. It dates back at least to Kleene, 1943, "Recursive predicates and quantifiers". Theorem VIII states:

"There is no complete formal deductive theory for the predicate

(x){\bar {T}}_{1}(a,a,x)

."

As the T is Kleene's T predicate, and the bar indicates negation, this is exactly a statement about the halting problem. Kleene explicitly says: "This is the famous theorem of Gödel on formally undecidable propositions, in a generalized form." This paper is available in the book The Undecidable as well. — Carl (CBM · talk) 12:49, 6 November 2007 (UTC)

Dude, this argument was never about content. It was about language.Likebox 19:15, 7 November 2007 (UTC)

Created Archive 03

The talk page was getting very long, so I have moved the discussion prior to the current active one (about the new 'proof') to Archive03 and added a link in the Archive infobox. Zero sharp 16:17, 6 November 2007 (UTC)

Semantic proofs

We now have three proof sketches in the article: the main sketch of the syntactic proof, the section on computability, and the section on Boolos' proof. I pulled Boolos' article today, and it does seem worth mentioning briefly. I think we should rearrange things so that all the proofs are in one section. Within that, the first subsection should concern arithmetization, then the syntactical proof sketch, then a section on semantic proofs including the computability proof and Boolos' proof. Boolos points out in his paper that Goedel gives another semantic proof in the intro to his paper on the incompleteness theorems. The current organization is less than ideal. — Carl (CBM · talk) 16:42, 8 November 2007 (UTC)

Seeking a peace accord

Let me apologize for the length of this. I wrote this for several reasons, not the least of which is that I was first to delete Likebox's proof (then reversed my view), and feel like i sparked off a contentious disagreement which led to a temporary edit-block and some ill feeling.

Also, I have spent roughly equal time in both schools of thought (my dad was a logician), and appreciate both the austere beauty of formal mathematics and the abstract dynamism of the computational view. The conflict between the two schools is visible on any university campus, but in the end it is illusory as both schemas are ultimately bound by an isomorphism.

I have a mixed background in math and comp sci, and I think the discord here is just a result of different perspective. First of all, let me say that L's proof is by no means a formal, mathematical proof (nor a sketch of one) satisfactory in the sense of mathematical rigor. The proof offends the formalist sensibilities, and seems a strangely worded reiteration of points already made elsewhere.

But let me back up a bit. We all know that any real, published proof is not a formal proof but an abbreviation. An actual formal proof of even the simplest theorem would be tedious and impossibly long (in Principia, Russell famously takes 106 pages to get to 2+2=4.) Except for proofs in Euclidean geometry, mathematicians opted long ago for proofs which are really roadmaps to proofs. They serve a social function; whereby a researcher announces to his peers how to do a formal proof. A good proof contains only the non-obvious bits, and omits everything obvious. This is by no means laziness but necessary, else our journals would be filled with obvious explications and one would have to scan 100's of pages of text to get at the crucial ideas.

But obviousness is relative to the audience (even among mathematicians, this changes from generation to generation.) Don't get me wrong - Godel's proof, historically, belongs to the mathematicians and the formalist, mathematical perspective should get top billing. But other audiences are worthy of our attention as well.

Godel's Theorems and CT were written prior to the first real computer program (a credit to their author's inventiveness.) Many young people today have grown up writing computer programs (I wrote my first at 12, which may be been unusual in 1978, it certainly is not so now.) With mathematics, we require our young to spend much time learning to do arithmetic and algebra. It is only through this direct doing that we can internalize these ideas, and develop intuition to guide us in with new problems. It is this training that defines our sense of the 'obvious'.

A person who has been writing programs for many years develops a similar intuitive sense about computing machines, what is possible, what is easy, what is hard, what is obvious. The lambda calculus and turing machine are their native ground. So, to a programmer certain things seem obvious which are not so to a pure mathematician (and vice-versa, i'm sure.) We can see this from the discussion. For instance, at one point an editor objects to Likebox's claim that, basically, 'quining' (the term is due to Hoefstadter) and variations thereof are easy and self-evident. The editor objects - correctly - that Likebox is is really pulling in the recursion theorem. Likebox responds - also correctly - that a person who has actually written quines instinctively knows this to be true and can write such a program in a few minutes. Both Likebox and the other editor know how to make this 'quine'. They simply disagree on whether the reader can be expected to or, even if the reader senses it, does he demand proof anyway. They disagree on the reader's expectations.

It comes down to a question of what is obvious to whom, and this is mostly a function of background. The complete, unexpurgated proof will never be written. What comprises a meaningful proof-map is dependent on the intended audience's background and demand for rigor. The mathematicians certainly come first and foremost, but I think it's OK to provide proof-maps for different audiences in wikipedia. In fact I think it is a very good idea to do so, provided we make clear we are shifting gears in a major way.

For a programmer, several things (which are monumental and visionary unto themselves) are going to be obvious for the simple reason he has already worked with them. The arithmetization of a symbol system is automatic; symbols are routinely coded into integers, and often there are multiple layers to such a mapping. The ability to create 'quines' and variations thereof are going to be evident (after the reader works a few problems on it.) Even the connection from Halting to Incompleteness - while not obvious - is well within the range of mere mortals to fill in. In short, a reader with lots of training in programming is already 1/2 way to intuitively grasping godel's proof. To provide this reader the proof-map for the rest of the trip seems to me a valuable contribution to an article on godel's proof, and doesn't detract from the more formal and historical proof-map.

It's not that programmers have some superior abstract perspective. It is precisely due to mathematicians like Turing and Von Neumann that these computational abstractions were refined, simplified and made real such that any kid can (and does) play with a computer, that certain of these abstractions are now common ground to a new generation. And what could be better than that?

So I advocate we tighten up the wording in L's proof, maintaining the current structure but substituting or clarifying certain language - while granting L a certain license to opt for plain explanations rather than terms familiar to a mathematician. Also we should give some kind of forward about whom the section is intended for, and that it is not in competition with the traditional treatment.

"Yes, I know the garden very well. I have worked in it all my life.

It is a good garden and a healthy one ...

there is plenty of room in it for new trees and new flowers of all kinds ...

I am a very ... serious gardener." - Chance, Being There

CeilingCrash 17:13, 8 November 2007 (UTC)

I don't see even a theoretical benefit to the use of quines and specific programs. It obscures the general phenomenon, which is the relation between provable membership in a set vs. the recursive enumerability of the set. (This is still ignoring the nonexistence of the "quine lemma" etc.) Could you comment on the current wording, explaining what you think is unclear about it? It's exactly the same idea, just expressed more reasonably.

Sure, there is nothing unclear about the present wording on its own terms; it's just a matter of terminology. By "theoretical benefit" i take it you mean 'hypothetical benefit', as we're not claiming an improvement to theory. I'll be more specific in a little while, but the mathematical perspective comes from a higher level of abstraction, where we speak of 'provable membership in a set' and 'recursive enumerability of the set'. The programmer doesn't think in terms of sets, but rather algorithms and their outputs. The programmer would not say a set is recursively enumerable, rather he would say "any of these will be eventually produced by this program." To give a simpler example, a mathematician defines a prime number as having no (non trivial) divisors. A programmer sees it as the output of the sieve of erastothones, or perhaps "what's left out when you multiply everything by everything else." It's a dynamic view. To be sure, the static view is the more formally satisfying because the dynamic view can be seen as shorthand for what really is a static sequence of steps. (Set theory came first. One wonders, however, how things might have gone differently had Church continued with the original intent of Lambda Calculus, which was to ground mathematics on functional, rather than set-theoretic terms.)

From the dynamic view - which very admittedly smuggles in a great number of results formally belonging to recursion theory and other areas - the key ideas are "you can make a quine" and "no algorithm can decide haltingness." These are totally non obvious. All the rest is by no means formally trivial, it is just of little surprise to the reader coming from this view. CeilingCrash 17:57, 8 November 2007 (UTC)

CeilingCrash has said many wise and correct things. But he assumes that the reason I am trying to incorporate CS language in the recursion theory pages is because I am unfamiliar with the methods of mathematicians or do not appreciate their "austere beauty". That is not true. He also assumes that the reason that some recursion theorists erase the proof is because they honestly think that the language I am using is confusing. That is also probably not true. It would take a truly illiterate person to not understand that the proof that I gave is correct. Even if the person thought it was a sketch, there is nothing preventing them from presenting another proof alongside.

But they insist on either deleting the proof or replacing it with language which makes it incomprehensible to a coder.

The real reason is that the people who enter the recursion theory world are forced, by a systematically constructed power structure, to adopt a certain language for their algorithms. This language is inferior in every way to any modern computer language. But if you do not adopt it, you are not politically allowed to call your algorithm a proof, no matter how precise and no matter how clear. You could even write out the code explicitly, and it is not a proof. You could run the code on a computer and have it work, and it is not a proof. It is only a proof if you use the recursion theoretic language to the letter, with all the

\phi _{e}

and

\phi _{\phi _{e}}

. If it ain't got the

\phi

s it ain't no proof.

To understand why this inferior language dominates, one must look to the academic structures in the 1950s when the modern recursion theory departements were constructed. The people who created these departments wanted a divide between their field and that of theoretical computer science, with Knuth and Minsky on one side, and Nerode and Woodin on the other side. They wanted to establish their field as legitimate pure mathematics, not as a branch of applied mathematics.

To facilitate this artifical division, the recursion theorists constructed a wall of terminology to prevent "code-monkeys" from claiming algorithmic proofs for recursion theoretic theorems. This means that the recursion theoretic world will not accept as legitimate any algorithm which is not written on a Turing machine in Turingese. In order to get a paper accepted in a recursion journal, even to this day, one must write the algorithm so that it is not readable by a person who codes. This is not an accident. It is there by design, and this motivation was explicitly stated by the founders of the respective fields. It was to prevent pseudo-code from infecting mathematics journals.

This division, I am certain, cannot survive in the open marketplace of ideas provided by the internet. But to help along its demise, I try to provide clear proofs in modern computational language of all the classic theorems of recursion theory. The proofs are so much simpler in the natural language of computer programs, that I think recursion theory language will be about as popular in the future as latin.Likebox 19:24, 8 November 2007 (UTC)

It remains the case that Wikipedia is not a forum for correcting historical injustices, real or perceived. That should be done elsewhere. Perhaps you could publish a paper somewhere about the faults of recursion theory and its notation. — Carl (CBM · talk) 19:34, 8 November 2007 (UTC)

At least you have finally admitted your position. Now we have a real conversation.Likebox 19:46, 8 November 2007 (UTC)

I have been quite frank about my position. "Wikipedia is not the place to right the wrongs of the world." [6] — Carl (CBM · talk) 20:04, 8 November 2007 (UTC)

(deindent) Now that we understand the issues, I would like to admit a little white lie. I never expected the proof to stay on this page. Nor did I expect the quine proof of the Halting theorem to stay on the Halting problem page. In the first few weeks, I had about a 75% confidence level that it would be deleted by somebody who has a recursion theory PhD, and that this person would attack the proof as illegitimate on language grounds.

It took a lot longer than I expected, mostly because it takes a while for the political sides to emerge. But now that the battle is fought, I would like to ask a more profound question. What is the purpose of Wikipedia, really? Why can anyone edit any page, even a person who does not have a PhD, like myself? Why is an expert opinion, rendered by a tenured professor of equal value to the opinion of a lay-reader?

The reason, I believe, is the oft-stated principle of radical inclusiveness. It is to make sure that ideas to not stay hidden, even if there are well established power structures that strive to make sure that they stay hidden. This is the reason for my additions, and this is why I defend them from the academic powers that line up to attack them.

This is also the reason that I am optimistic about Wikipedia. Because even when the additions are not incorporated, the resulting debate exposes the power structure, and, over the long term, will right the historical wrongs. It has already happened for Ernst Stueckelberg, and it is happening for Wolfgang Pauli, whose genetic ideas were decades ahead of their time.

Historical wrongs were put right long before the internet existed. Look to the history of reconstruction in the U.S., or the history of the conquest of the Americas. But the internet makes the process much faster. I am pretty sure that anyone who has been following this debate will abandon the recursion theoretic proofs. Not everyone. But enough to make a difference.

So I remain optimistic, whatever happens here. For the interested reader, here's the only real proof of Godel's theorem you're going to find on Wikipedia:User:Likebox/Gödel modern proof. Likebox 20:08, 8 November 2007 (UTC)

I have a merge in the works to suggest of Carl's and Likebox's exposition (the key difference being only that Likebox's version sketches Halting (and points to a construction which defies a given halt-detector H), collapses some of Carl's finer points for brevity, and inserts some narrative explication of my own. I may not be making sense right now as i'm very tired :) In any case, I hope to arrive at a hybrid acceptable to consensus that is helpful to computer-oriented folk. I am quite sure Likebox will scream bloody murder, but my goal is really to improve the article for the theory-impaired but algorithm savvy. Once editors here take another pass at it, i am sure we can pin it down. In any case, one hell of an interesting discussion and I, for one, have learned immensely. By the way, I had come here by way of the Lambda Calculus article; the introduction to that article had been, er ... plagiarized so had to be deleted. This left a headless article, so i rapidly put together an intro. I am not an expert in this area, so would appreciate some extra eyes on it Lambda_calculus Thanx —Preceding unsigned comment added by 24.128.99.107 (talk) 04:46, 9 November 2007 (UTC)

Oh, and to respond briefly to Likebox, I don't think he is acting out of a lack of understanding of formal math. I believe Likebox is of the view that godel's proof is attainable in a considerably more direct (thus conceptually superior) way, and that his proof is as complete as any of Godel's.

My personal and currently indefensible view is that he right in this, that Godel can be reformulated more clearly from newer ground. However, I am not prepared to enter that debate, haven't thought carefully enuf about it, and in any case that issue is beyond the scope of a mere tertiary source as wikipedia. The reasons I claim for inclusion here are pedagogical, in that the train of reasoning is tractable to coder people. So I'm sticking to that. 24.128.99.107 05:03, 9 November 2007 (UTC)

Note that one of the issues iwth Likebox's proof was brevity; if you remove the unneeded restatement of the incompleteness theorem, the resulting "proof" was far too short, ignoring many important details. But I'll be glad to look at rewrites and we can find some compromise language. I still haven't gotten any actual feedback about the language that is in the article right now, which is the same proof that Likebox wanted, just written up better. — Carl (CBM · talk) 13:23, 9 November 2007 (UTC)

Oh my god! It's too clear! Look, just leave it alone, and put your sketch in another section. As I said, it leaves out no details at all, and is more rigorous than anything else in the world.Likebox 19:17, 9 November 2007 (UTC)

There is no need to have large numbers of different proof sketches in the article. There are already three of them!

And none of them (including yours) are self-contained and complete. Mine is self-contained, complete, more rigorous, and shorter than all of the others.Likebox 23:01, 9 November 2007 (UTC)

As for unclear parts of your proof, you might begin with the phrase "axioms will follow its operation". Axioms, like all other formulas, are immobile.

Could you explain what parts of the current wording you dislike, if you are amenable to compromise, or refrain from commenting here if you have no desire to compromise? Wikipedia is not the place to push your POV about how proofs should be written. — Carl (CBM · talk) 19:26, 9 November 2007 (UTC)

What part of the current wording I dislike: first there is no computer program. You don't describe a computer program, so you can't have a proof. Second there is no mention of the Rosser version. That is unacceptable when the Rosser proof is a minor tweak, and the Rosser version is just as easy. Third, it is written obscurely, and cannot be read and understood by a layperson or an undergraduate. Taken together, these objections are fatal.

"Axioms will follow its operation" is explained later in the sentence. It is no more unclear than "Axioms will describe a standard model of computation" in your rewrite.

I have no problem with compromise, so long as the compromiser will read the proof, understand it, and think about it before rewriting it, preserving the ideas and the explicit exactness of the discussion. I think I have already gotten it to the point of no-further improvement possible, but I might be wrong.Likebox 23:01, 9 November 2007 (UTC)

Wait a minute - the quote you give ("Axioms will describe a standard model of computation") is not in the article at all, and it has not been edited since your comment. If you want to give feedback about the article, it would help if you only quote things that are actually there. I agree that the current version could use a little more detail about arithmetization; this is one of the places where your original writeup is particularly weak. Another place where both are weak is on the role of ω-consistency, because of a lack of detail about the T predicate.

The article as it stands doesn't spend any time on the Rosser version; if you would like the article to cover that, it will need to do it in more than just one section, but the previous consensus was not to cover it.

The claim it is written obscurely is likely just your opinion that all standard terminology is obscure. Which particular part do you feel is obscure? It is not necessary to give actual code to have a precise proof, as was established by Rogers' book in the 1960s. — Carl (CBM · talk) 02:58, 10 November 2007 (UTC)

Obscurity is a matter of---can a person who is not familiar with your field read this and understand what is going on? This requires a taste-test of the presentation. I have taste-tested my presentation on lay-people, and they understand it.Likebox 06:45, 11 November 2007 (UTC)

(deindent) I did not delete anybody else's text, so I am not imposing a view. I just added a different style of proof, which is short and to the point. I tried to be clear, but maybe I wasn't perfect. I tried to be accessible, maybe I fell short. I don't know.

Request for comments

The issue is the wording of the section about the relationship of the theorem with computability theory. For details, see above. — Carl (CBM · talk) 19:30, 9 November 2007 (UTC)

also see User:Likebox/Gödel modern proof for the alternate exposition. The main difference is that I used explicit spelled-out computer programs.Likebox 23:03, 9 November 2007

(UTC)

I think, i am pretty sure, i have some tenuous handle on both party's perspectives. The improvements I see for the current section are as follows. Again, i am speaking in terms of pedagogy, not precision. When I say "language X is better" I only mean "language X will be more groovy to programmers.") I put some bolding for skim readers, not for emphasis.

The undecidability of haltingness is invoked from CT. This result is rather shocking to programmers. Likebox does not invoke CT, but gets at un-halting with 'quines' and shows how to construct a counterexample. The programmer is no longer shocked, and given this part of proof, can actually go off to construct a counter-example generator to defy any proposed-halting-detector. He understands. To a mathematician, it seems bizarre because 'quining' sneaks in vast areas of recursion theory, all sorts of other stuff seem left out, it's 'hand-waving' in all the wrong spots. To the coder, who is at heart a constructionist who understands in terms of process, it shows what to do, and that's his mode of understanding. He doesn't want an existence proof of 'quines' (there is one), he wants to know how to make them, which is easy to show. All the rest he sees as details that can be looked up. We should give more references to these 'waved-over' details, which i shall try to do.

The undecidability of halting is really the heart of the matter, to me.

Computational people find intuitive that the Undecidability of Halting implies Incompleteness of Number Theory. They know that a computer is governed by mathematical laws. They think, "you can do mathematical proofs as to whether a certain program halts. If there is a hole in 'haltingness', there is a hole in math." Hand waving, absolutely. That is how these people wave tho. In short, I think we should expand the part on Halting, compress the part on Halting->Godel, shoot up the middle in terms of style between Likebox's more casual style and CBM's more formal, and whatever i forgot to list just now.

Let me take a crack at this, as i have assertions to back up. I am quite sure i wont make the final exposition, but probably a way-point most of which is discarded. But lemme try. I'd urge all editors (myself included) to not get too attached to early drafts. We are (i think) aiming for an effective pedagogy on this directed at coders. To say "we don't think coders will groove on X" does impune the quality of X, and each exposition is beautiful within it's own domain, and we are very much guessing as to what coders groove on.

Oh, and the title of the section, i think shd change. I really have to log off else my partner is going to eject me into the night in a very real and formally decidable way ! Let me take a crack tomorrow (my version will steal heavily from both.) CeilingCrash 01:05, 10 November 2007 (UTC)

I disagree that there is any established consensus for a proof aimed primarily at "coders". I'm not even sure what that means. This is, first and foremost, an article about mathematics. — Carl (CBM · talk) 02:50, 10 November 2007 (UTC)

The incompleteness theorem is not a PhD level recursion theory subject as Likebox seems to imply. It's a basic theorem from mathematical logic, taught in any self-respecting introductory undergraduate course in that subject. I think it's best if the presentation stays in standard mathematical terminology instead of computer terminology, though the article should (and does) link to related results in computability theory. It's true that some computer-inspired proofs (like the one Likebox cited) have been published, so Likebox's proof is not OR. It's also true that logic has been redone from the ground up many times (see sequent calculus, categorical logic, type theory, or ludics for yet more examples), so there are many ways to look at the subject. But my impression is that most introductory logic textbooks use the traditional approach (predicate calculus, FOL, etc), as is natural because the incompleteness theorem is presented along with other basic theorems (completeness, compactness, Lowenheim-Skolem, some model theory, maybe some set theory) that don't fit so well into the computer presentation. See, for example, "A Mathematical Introduction to Logic" by Herbert Enderton. The class I took in college used that book, and it covers the topics listed above and should be pretty readable to anyone who made their way through Gödel Escher Bach.

Basically I agree with CBM that Likebox's proof is better off in an expositional wikibook that wikipedia could link to. I don't understand Likebox's insistence on putting the computer proof into the encyclopedia article (especially the main article about the theorem) and I think devoting much space to its presentation goes against the "undue weight" principle of following what the majority of sources (in this case logic textbooks) do, with a shorter mention of less common approaches. I actually think the article's "proof sketch" section should be shortened a lot further, since it links to another article with a longer proof sketch (perhaps the computer proof could be presented there somehow). It's enough for the main article to explain informally what the theorem says, its significance, its historical context, etc, plus a brief summary of the proof's main ideas. The article is currently too cluttered and should be streamlined in general. —Preceding unsigned comment added by 75.62.4.229 (talk) 05:05, 10 November 2007 (UTC)

Further comment: maybe an expert can correct me on this but I think I see the error in Likebox's references to "language that should have been retired decades ago". It's that Likebox is mostly interested in computer science, and not more traditional (but definitely non-obsolete) areas of mathematics like analysis, topology, probability, etc. Those areas are all based on set theory, and logic (at least as taught in undergraduate math classes, which is as far as I got) is mostly motivated by having to develop axiomatic set theory as the foundation of the rest of mathematics. Set theory is used in math because of (e.g.) all the uncountable structures in subjects like functional analysis that have to be put on a rigorous footing. Computer scientists generally don't care about uncountable structures and they're more interested in decision problems on countable languages, which they study using a somewhat different vocabulary than mathematicians use. The language that Likebox complains about is in fact still necessary and still very actively being used by mathematicians who are nowhere near ready to retire. I.e. if Likebox wants to rework mathematical logic, he or she should also be willing to rework the rest of mathematics starting from set theory the same way, and I don't see that about to happen. So I think we're seeing some cultural chauvinism and/or ignorance on Likebox's part, in what comes across as an attitude that computer theory is the only part of mathematics that really matters and that no one should care about, say, Hilbert space operators (hint: physicists use those all day long). Logic in textbooks is presented the way it is because that's what works best for traditional mathematics even if it's not so great for computer theory. Likebox might like reading Enderton's book that I mentioned above. It gives a much grander view about logic and models than the computer-based approach does. —Preceding unsigned comment added by 75.62.4.229 (talk) 06:03, 10 November 2007 (UTC)

I am skeptical that the comments above are sincere. Since this is a political discussion, perhaps we should limit it to users who do not hide behind a veil of anonymity?Likebox 21:36, 10 November 2007 (UTC)

Actually, on closer reading, maybe they are sincere! Likebox has already reformulated all of mathematics to his own satisfaction from the ground up only using computers and not referencing uncountably infinite sets except as rhetorical devices. It doesn't take as much work as you think. It was essentially done by Godel (closely following Hilbert), when he constructed L. L is defined as the class of all objects predicatively constructed by computer programs deducing from the axioms and running for an ordinal number of steps. It forms a model of Zermelo Frenkel set theory, all of usual mathematics. This seems like a strange idea, but when the ordinals are countable, the computer programs just have lots of while loops which run a countable number of steps. If you take V=L for sets, define proper classes corresponding to what are normally called the "true" power sets, declare that all infinite power classes are Lebesgue measurable, and take as an axiom either that all well-orderable collections are measure zero if you feel conciliatory, or that all ordinals are countable if you are feeling incendiary, you get a good-enough model of mathematics that certainly includes everything any non-logician ever does, including most small large cardinals. It just does not have any truly uncountable sets. These are all proper classes.

Likebox does not care if you agree or disagree with his formulation of mathematics, because Likebox did it only to satisfy himself that it can be done. But he is happy to contribute his decade old proof of Godel's theorem, because it is not original. The only arguably new thing about it is using quining to sidestep Kleene, and that has almost certainly been thought of before.Likebox 22:54, 10 November 2007 (UTC)

The comments are sincere, though it's quite possible that they're incorrect and/or not well-informed, since I'm not an expert on this stuff (that's why I said maybe an expert can correct me). But if you're such an expert, why do you have such trouble with the usual textbook presentation? It worked ok for me (I had a one-semester class using the book that I mentioned). Also, I'm not the anonymous one here: I'm disclosing my personal IP address instead of making up a meaningless nickname like you did (not that there's anything wrong with that).

Dude, I'm not an expert in any way. I just have my opinion. I'm not trying to impose it on other people. I just told you my way of doing math.Likebox 00:46, 11 November 2007 (UTC)

Also, as I tried to make clear, everyone has a problem with the usual textbook presentations. They are incredibly hard to decipher, even for the so-called experts. To see, try to get them to prove that it is undecidable whether a program runs in polynomial or exponential time (without using Rice's theorem).Likebox 00:48, 11 November 2007 (UTC)

But I think trying to jam an unorthodox proof into the article against other editors' judgment (some of whom are experts) counts as trying to impose your views on other people. Otherwise there wouldn't be an RFC. And I don't see what the textbook presentation of the incompleteness theorem has to do with the running time of programs--this isn't a complexity theory article and it's irrelevant that complexity theorists working on complexity topics tend to use different tools than what logicians use on logic topics. Finally I personally thought the incompleteness theorem presentation in Enderton's book was fine. It's a popular book and I think most users (teachers and students) are happy with it. So I can't go along with the claim that "everyone" has a problem with the usual textbook presentations. I can go with "there exists a user with such a problem" which is entirely different, but even if everyone has a problem: as CBM says, Wikipedia is not the place to right the wrongs of the world. Maybe your best bet is to write your own textbook and get it published. —Preceding unsigned comment added by 75.62.4.229 (talk) 06:24, 11 November 2007 (UTC)

(deindent) The theorem I was stating about running time is most definitely not a complexity theorem, but a recursion theoretic one, even though it superficially sounds like a complexity theoretic theorem. The theorem is about undecidability of running time, but it really is a version of Rice's theorem, that it is undecidable whether a computer program's output has any definite property. For example, it is undecidable whether a program outputs 1 or 0, and it is undecidable whether a program's output depends on its input. All these things are undecidable for the simple reason that you can SPITE them, but the method in the textbooks is made murky by mixing the input stream with the variable where you print the code. Not to mention unreadable by a nonspecialist.

The proof of Godel's theorem is a single sentence: No computer program P can output all theorems of arithmetic, because then a program which runs P looking for statements about its own behavior can easily and explicitly make a liar out of P. If we are not allowed to say this on this page, there is something wrong.Likebox 06:45, 11 November 2007 (UTC)

As mentioned I'm ok with having a computer proof sketch in the proof sketch article, though the one currently in your user page needs some reorganiztion and style adjustment (e.g. a theory proof shouldn't describe things in terms of techno-artifacts such as cd-roms). CBM and others have made further suggestions that seem good. The computer proof should get less space than the traditional proof by the undue weight principle. I don't think it should go in the main article.

As I said, I will keep the proof on User:Likebox/Gödel modern proof, and not touch this page at all.Likebox 19:07, 12 November 2007 (UTC)

moved Adler's response to next section for continuity. Wvbailey 21:28, 14 November 2007 (UTC)

Response to RFC

I came to this page in reaction to an RFC. I've spent an hour or so reading through this discussion, and can't claim to understand every point. Some years ago I could have claimed to understand at least one proof of Gödel's incompleteness theorems but it would take me longer than I'm prepared to devote to this to regain that understanding.

What I think I do still understand well is what Wikipedia is supposed to be. I would simply urge all participants in this debate to consider whether their view of what should be in this article complies with policies on original research, reliable resources, not being a text book and verifiability, the last of which opens with: "The threshold for inclusion in Wikipedia is verifiability, not truth". Phil Bridger 21:58, 12 November 2007 (UTC)

Nobody is arguing about verifiability of correctness. The key issue is whether it is appropriate to use explicit computer programs in a proof, and whether such language is simpler and clearer.Likebox 01:23, 13 November 2007 (UTC)

My point is that the decision on that has to be made on the basis of Wikipedia policies. If the use of an explicit computer program in a proof can be sourced to a verifiable reliable source then let's have it in the article. Otherwise leave it out. Wikipedia is not the place to argue philosophical issues about what constitutes a valid proof. Phil Bridger 10:10, 13 November 2007 (UTC)

The use of explicit programs has a long history, and this debate is a mirror of an old and longstanding debate in academia. I have left the editing of the article to others, and placed a suggested compromise on the page User:Likebox/Gödel modern proof.

Wikipedia is a place where certain questions need to be resolved. What constitutes a valid recursion theory proof is one of those questions. It is not a peripheral issue--- it determines whether simple proofs can be presented on a whole host of other pages, or whether proofs are going to be be cut-and-paste from textbook presentations or absent altogether. Textbook proofs are reworked by secondary authors, and they are, as a rule, the worst proofs in the literature. They are verbose, confused, and inaccurate. It would be a shame if the policy of "no original research" was expanded to "no simplified exposition", because then it will be hard to find anyone to write any proofs of any nontrivial result. In its day, Brittanica included up-to-date discussion of current research, and was not a mirror of the contemporary textbooks. This is part of the reason it was so valuable. Issues of accuracy are easier to adress on Wikipedia, since there are thousands of referees for any discussion. Issues of clarity, however, are more insidious, because they have no unique right answer.Likebox 19:41, 13 November 2007 (UTC)

I'm sorry but Wikipedia is not the place to resolve the issue of what constitutes a valid proof. As you say this is a long-standing debate in academia, and that is where the debate needs to be, not in an encyclopedia. Phil Bridger 20:10, 13 November 2007 (UTC)

How are you going to write the encyclopedia? It won't get written. If there is more than one way to do something accepted in academia, there should be several presentations on your encyclopedia.Likebox 23:02, 13 November 2007 (UTC)

There is not actually a longstanding debate in recursion theory about what is a valid proof. In particular, since the 1960s it has been very common to avoid writing recursion equations or pseudocode in proofs, and the style developed by Rogers is used by virtually all publications in recursion theory today. I don't understand the claim that textbook proofs are verbose, confused and inaccurate; they are typically much improved from the original proofs in research papers, which are often myopic, focused solely on obtaining a particular result. — Carl (CBM · talk) 20:36, 13 November 2007 (UTC)

You have already made your position clear. Many people believe that you are wrong on this matter, but there is no need for everyone to agree. Write textbook stuff, and let others write review paper stuff. Criticize on notability and verifiability, not on language or style.Likebox 23:05, 13 November 2007 (UTC)

It's perfectly reasonable for editors to be concerned about the way articles are worded. I see no need to have duplicate expositions in the article, and I don't see much support so far in the RFC for duplication. You continue to claim that there is more than one way this is done in academia - could you present a math or computer science text that you are claiming as a model for your sort of exposition? Could you present any evidence that there is a long-running dispute on this issue in academia? — Carl (CBM · talk) 23:16, 13 November 2007 (UTC)

Nope, I am not going to do any of that. I nevertheless maintain my position.Likebox 02:19, 14 November 2007 (UTC)

Sorry, the reason I do not do this is because I do not believe in the authority of experts.Likebox 02:33, 14 November 2007 (UTC)

There is no duplication. You do not prove Rosser, I prove Rosser. Your presentation is imprecise, mine is precise. There is no contest. Your presentation is inferior in every way. That does not mean it should go. That means it should stay, but not overwrite mine.Likebox 02:29, 14 November 2007 (UTC)

I'm sorry, I know we are supposed to comment on content, not on editors, but how much longer are we going to suffer the ravings of this LUNATIC, who has stated repeatedly that he is _not_ interested in consensus, _not_ interested in compromise and who has nothing (it seems) to contribute but bloviating ramblings about how 'his' proof (oh, but it's not OR) is THE BEST PROOF IN THE WORLD EVAR? Is there no recourse for an editor being so C L E A R L Y disruptive? —Preceding unsigned comment added by 71.139.31.151 (talk) 07:46, 14 November 2007 (UTC)

An exposition like User:Likebox/Gödel modern proof is not adequate for an encyclopedia article on a mathematical theorem. It does have the advantage of connecting several topics that are generally considered cool on slashdot.org. It has the disadvantage of being vague to the point that it would be almost impossible to point out an error in the proof without actually disproving the incompleteness theorem. Phrased as an outline of an existing, peer-reviewed proof this would be OK. Unfortunately, exposing something clearly so that laypeople can understand it is not the same thing as conjuring up an illusion of comprehension. Unfortunately, it seems that only mathematicians understand the difference, after many years of having the mistakes in their own proofs pointed out to them by tutors.

The problem is aggravated by the fact that this article has a relatively high profile. In fact, in the past it has been a target of crackpot edits. Too many people have wasted too much time on this discussion. --Hans Adler 20:48, 14 November 2007 (UTC)

spacers added Wvbailey 21:32, 14 November 2007 (UTC)

section break

Thanks to Hans Adler for belling the cat. I added a cite of the Charlesworth article to the proof sketch section. Can we say we are done now? —Preceding unsigned comment added by 75.62.4.229 (talk) 15:09, 15 November 2007 (UTC)

The 'proof sketch' section is not meant to be a trivia section with every published proof included. The section on Boolos' proof already needed to be merged elsewhere. I'll work on that later today. — Carl (CBM · talk) 15:15, 15 November 2007 (UTC)

The proof Charlesworth gives on p. 118 is quite close to the text here (and it's worth noting the Charlesworth does not use quines, but uses a proof of the undecidability of the halting problem similar to the one currently in that article). So I moved the reference up to the section on computability. It's a good reference for an undergrad, and spends a great deal of time on arithmetization. — Carl (CBM · talk) 15:36, 15 November 2007 (UTC)

Sounds good to me. 75.62.4.229

The cat is alive and well. He will only speak more once someone who has not already spoken agrees with him.Likebox (talk) 06:43, 27 November 2007 (UTC)

DNFTT —Preceding unsigned comment added by 71.139.26.69 (talk) 06:56, 27 November 2007 (UTC)

Of course I'm not a troll! I believe sincerely in what I write. Do not attack others personally because you have a different position. I am shutting up until someone else (preferably more than one person) is willing to agree with me in public, because while I think that I am right, I also am feeling very lonely on this page.Likebox (talk) 20:25, 27 November 2007 (UTC)

So you're open to 'consensus' and 'compromise' as long as people agree with you. That's obviously some bold, new meaning of those words I'm not familiar with. You claim here you believe what you write, yet above you say:

"never expected the proof to stay on this page. Nor did I expect the quine proof of the Halting theorem to stay on the Halting problem page. In the first few weeks, I had about a 75% confidence level that it would be deleted by somebody who has a recursion theory PhD, and that this person would attack the proof as illegitimate on language grounds. It took a lot longer than I expected, mostly because it takes a while for the political sides to emerge. But now that the battle is fought, I would like to ask a more profound question. What is the purpose of Wikipedia, really? Why can anyone edit any page, even a person who does not have a PhD, like myself? Why is an expert opinion, rendered by a tenured professor of equal value to the opinion of a lay-reader?"

If _ever_ there was a case of WP:POINT, this is it. Whether or not you have anything valid to contribute (and I am most pointedly _not_ weighing in on this either way) it is so HOWLINGLY obvious to me that you have some kind of axe to grind with the Super Secret Cabal of Recursion Theorists, and that you insist, despite numerous, repeated attempts to counsel you otherwise, that WP is the place for it. It isn't. Either participate in the discussion calmly, constructively and NON-DISRUPTIVELY or someone will have to refer you to the appropriate venues for mediation and probably (it is hoped) sanction. —Preceding unsigned comment added by 67.118.103.210 (talk) 22:28, 27 November 2007 (UTC)

You're right that I don't give a rats ass about consensus or possible sanctions. But I am sincere in what I write. I think it would be super-duper-great if a proof of GIT can appear in Wiki. It can't? Too bad. I did my best.

I didn't expect the proof to stay, not because I was making any sort of *point*, but because it is simple, correct, well-understood and clear, and despite all that, it's not in the books. This means that recursion theorists are politically supressing this type of argument. It's not conspiracy, it's more like a blend of elitism and incompetence. While I think I am ethically obliged to present the proof and defend it to a degree (otherwise people might think that there is a mathematical problem with it), I do not feel ethically obliged to come to a compromise. You folks sort it out, I'll be outie.Likebox (talk) 02:25, 28 November 2007 (UTC)

Likebox, I nearly replied to the anonymous poster who referred to DNFTT, and to your reply. Here is why I didn't. 1. He was obviously right in that the best strategy in this situation was to treat you in the same way that one treats trolls. 2. You were obviously right in that you are not a troll. 3. These two points seemed so bleedingly obvious to me, that I hoped everybody would refrain from replying, because it just wasn't necessary.

As you seem to have accepted, grudgingly, we have sorted out what to do with your proof, and I appreciate your commitment to wait for a day when you think your chances are better. I sympathise with you. Once one has become obsessed with something like that, just doing something else and not thinking about it is the best thing one can do, but it is also very hard. In case you find it impossible (but only then), I would suggest that you spend part of the time improving your presentation of the proof (orthography, fix the obvious mistakes like explicitly assuming that there are quines and then using the stronger implicit assumption that there is a quine which can do a certain thing, ...) and then looking for an alternative way to make your proof known.

Since you probably have a background in computer science rather than mathematics it may also help you to remind yourself that many papers in theoretical computer science and theoretical physics would never have got their mathematical parts (as published) through peer review in a decent mathematical journal. So what you are trying to do can be seen as an intercultural project like trying to defend the whales in a Japanese Wikipedia article on whale meat. I would love to be proved wrong in my example, but I think there is no chance. You may find it hard to make your peace with the fact that that is how Wikipedia is supposed to work. I know that I do. --Hans Adler (talk) 09:54, 28 November 2007 (UTC)

You are right in all your points, except for two: 1. I do not have any background whatsoever in anything, not in math nor in CS, and I do not believe in peer review. 2. The obvious mistake that you mention is not a mistake at all. It is trivial to turn any program into a quine.Likebox (talk) 22:36, 28 November 2007 (UTC)

translation in van Heijenoort book

This article and the separate article On Formally Undecidable Propositions of Principia Mathematica and Related Systems both say that the translation in van Heijenoort's book was done by van Heijenoort himself, but I think that is wrong. Could someone who has the book please check?

On p. 595, V.H. says "The translation of the paper is by the editor,...". — Carl (CBM · talk) 22:17, 15 November 2007 (UTC)

Hmm, thanks. I must have been thinking of one of the other translations in the book, probably the Begriffsschrift. —Preceding unsigned comment added by 75.62.4.229 (talk) 22:26, 15 November 2007 (UTC)