Misplaced Pages

Revision as of 03:57, 29 January 2007

Mathematics Unassessed High‑priority

This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics ??? This article has not yet received a rating on Misplaced Pages's content assessment scale. High This article has been rated as High-priority on the project's priority scale.

Gödel's incompleteness theorems was a good article, but it was removed from the list as it no longer met the good article criteria at the time. There are suggestions below for improving the article. If you can improve it, please do; it may then be renominated. Review: No date specified. To provide a date use: {{DelistedGA|insert date in any format here}}.

Archives

/Archive01 /Archive02

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)

Word. Ruakh 21:26, 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 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 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 Misplaced Pages, 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 Misplaced Pages. 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 is not an argument against the validity of the incompleteness theorem, and does not belong in the arguments section. This is a question about the incompleteness theorem and what it means in its own terms. What the theorem says about itself in its own terms is important to the discussion of the article.

The question is, according to the terms of the incompleteness theorem, does the incompleteness theorem apply to itself, and if so, does that make the theorem itself complete, or incomplete? Secondly, if the incompleteness theorem is itself complete, does that make it consistent, or inconsistent? Lastly, how do we really know? I would appreciate it if somebody could give me a straight answer because it is important to the discussion of the article and what it says about itself in its own terms.

• Unassessed mathematics articles
• High-priority mathematics articles
• Delisted good articles