Talk:Gödel's incompleteness theorems

Please place discussions on the underlying mathematical issues on the Arguments page. Non-editorial comments on this talk page may be removed by other editors.

Section: First incompleteness theorem

The text of the section "First incompleteness theorem" was getting out of hand. I have added a section header for some of the new material on truth, and arranged the section generally as follows:

• Statement of the theorem
• First mention of "Godel sentence" , and two existing paragraphs that mention what happens when you add the Gödel sentence as an axiom, and on the general idea of the proof. The latter paragraph needs help.
• Form of the incompleteness sentence - see below
• Truth of the Gödel sentence - note: refers to the idea of the proof mentioned already
• Existing section: "Meaning of the first incompleteness theorem" - note: refers to the truth of the sentence
• Existing section: "Relation to the liar paradox"
• Existing section: "Extensions of Gödel's original result" - on Rosser's trick

It is hard to rearrange the first three bullets into a different order, because each depends on things mentioned in the previous one. — Carl (CBM · talk) 23:04, 12 July 2016 (UTC)

still needs some shaping but, yes, this was a very good idea...68.48.241.158 (talk) 23:16, 12 July 2016 (UTC)

Following a suggestion of Trovatore I added a paragraph on the form of the Gödel sentence. There are many references on this point. — Carl (CBM · talk) 23:29, 12 July 2016 (UTC)

The section on the "Meaning of the first incompleteness theorem" needs work. It is a mixture of several ideas, and not in a sensible order either. — Carl (CBM · talk) 23:55, 12 July 2016 (UTC)

definite improvements overall..and I agree that next section is/has been problematic as well..68.48.241.158 (talk) 00:11, 13 July 2016 (UTC)

The smaller, more direct to the point sections at the beginning of the article are a big improvement...with such a big rewrite/restructuring there are at least many small style tweaks that will have to be worked out slowly....some later sections that seem a little not to the point and perhaps a bit repetitive of information include "EXAMPLES OF UNDECIDABLE STATEMENTS"/"FOUR VARITIES OF THEORIES"...68.48.241.158 (talk) 13:41, 13 July 2016 (UTC)

References

Would anyone mind terribly if I changed the referencing style to that in e.g. Cayley–Hamilton theorem? (Signature added after original post.) YohanN7 (talk) 10:02, 14 July 2016 (UTC)

(responding to proposal above..posted by YohanN7, I think): it certainly looks better and reads easier that way..so I would certainly support unless there's a particular reason why not..68.48.241.158 (talk) 13:34, 13 July 2016 (UTC)

It is mostly a policy, WP:RETAIN, that basically says don't fix it if it ain't broken (The link talk only about US vs British English, but the same principle is rather global.) YohanN7 (talk) 13:39, 13 July 2016 (UTC)

I'm confused...you want to change it, right?

Of course. I'll begin with what can be done without protests, templetizing the reference list. This opens up for having clickable citations, whether they are explicit (like (Franzén 2004, p. 112)) or ordinary footnotes.

One huge advantage of having references in this way is that it is so much easier to add citations. YohanN7 (talk) 13:48, 13 July 2016 (UTC)

yes, sounds good to me (I think you need to resign your first comment in this thread as it went away...so it kind of looked like I posted it)..68.48.241.158 (talk) 13:53, 13 July 2016 (UTC)

I'm sorry, I thought you were referring to the article's in-text citations...so nevermind..but I'm sure what you did is good and fine...68.48.241.158 (talk) 14:44, 13 July 2016 (UTC)

Yes, I would mind. This article uses regular Harvard-style referencing, which is a common style in actual published writing. It makes the citation for each sentence clear without having to look elsewhere (i.e. at a glance the reader knows which source is used). I would not support changing to the style of Cayley–Hamilton theorem. Also, I have found that, in general, the "clickable" references tend to be very fragile, and don't work as advertised except in very simple cases. — Carl (CBM · talk) 16:20, 13 July 2016 (UTC)

I'm all confused by this...I think he did something with the references at the bottom, after the article text..??68.48.241.158 (talk) 16:24, 13 July 2016 (UTC)

I think he converted some references to use citations. I don't really like that idea, either - the article mostly does not use templates, so probably the one or two that were added with templates should be changed to match the majority, rather than vice-versa. The citation templates also turn out to be inflexible except in simple cases; if there are reprints, multiple editions, etc., the citation templates can become an obstacle rather than a tool. — Carl (CBM · talk) 16:28, 13 July 2016 (UTC)

The templates are flexible enough.

1. A formal system is said to be effectively axiomatized (also called effectively generated) if its set of theorems is a recursively enumerable set (Franzén 2004).
2. A formal system is said to be effectively axiomatized (also called effectively generated) if its set of theorems is a recursively enumerable set .

• Franzén, T. (2004). An Incomplete Guide to its Use and Abuse. A.K. Peters. ISBN 1-56881-238-8. MR 2007d:03001. {{cite book}}: Check |mr= value (help); Invalid |ref=harv (help)

Editions, reprints and the like can be handled. One will get into trouble if one wants to list the translators brother in law and his wife, but there is nothing to prevent you from writing arbitrary text after the template or after the citation template in the footnote. Then, if one still has trouble, one should probably reconsider what belongs in the reference list and what does not.

Templates standardize the way references appear. Without them, a complete mess will result, especially with many references since most people don't know how to format a reference.

Moreover, they facilitate adding new inline citations that don't clutter the source text. They are clickable. A click takes you first to the right entry in the reference list and then (if the reference is complete in this respect), you can click your way to an online copy or a place to buy the item in question. As seen above, footnotes is not the only option.

Naturally, it should be used uniformly. I begun yesterday with the reference list (didn't touch the main body), and intended to do all of them, but that was reversed by CBM along standard info such as isbn numbers and editors. I truly don't understand why it is better to have the current "system". It sucks. YohanN7 (talk) 09:59, 14 July 2016 (UTC)

I do know the arguments for templates; I just don't find them as compelling as I once did. There's no general policy in favor of templates, and I think the current system is serving the article perfectly well. It has the benefit of being easy to type, and easy for other editors to pick up. In the end it's just a matter of preference, though, and so when there is a disagreement the usual rule of thumb is to keep the original version, which in this article was to have citations without templates.

At the same time I have no problem with adding ISBN numbers, and I'll go back and re-add any that I inadvertently removed. — Carl (CBM · talk) 12:12, 14 July 2016 (UTC)

Fair enough. I should have waited longer for replies after posting this thread. YohanN7 (talk) 12:23, 14 July 2016 (UTC)

arithmetic

I think the lede should specifically reference that we're talking about "arithmetical" relations here in a couple of those sentences...for a long while it had that parenthetical "(arithmetic)"...I suppose it's true that any relationship between them is inherently arithmetical...but for the sake of the general reader..

Also, this notion should probably be explained briefly somewhere as I don't think it's touched upon at all...these are Gödel's words from the Metzger translation:

"..there are in fact relatively simple problems in the theory of ordinary whole numbers which cannot be decided from the axioms." "theory of ordinary whole numbers" is synonymous with "arithmetic" here...his footnote for this sentence states, "ie, more precisely, there are undecidable propositions in which, besides the logical constants, there are no other concepts beyond addition and multiplication, both referred to natural numbers and where prefixes can also only refer to natural numbers." later in the paper he briefly states, "a relation is called arithmetical if it can be defined solely by the means of addition and multiplication applied to natural numbers.." (keep in mind that the inverses (division and subtraction) can be stated via the concepts of addition and multiplication in these systems..) 68.48.241.158 (talk) 16:35, 13 July 2016 (UTC)

"all truths about the natural numbers" seems vague...there are probably truths that aren't arithmetical...idk, a really dumb example is that the symbol for the number 5 can be found on my mailbox...idk, point is the general reader might not no what this means..68.48.241.158 (talk) 16:47, 13 July 2016 (UTC)

(^^I'm operating under the assumption that I'm basically talking to two other editors who understand the article edit activity that led to these threads...so these threads are likely incomprehensible to the uninitiated...I can clarify the issue better for others, if requested)..68.48.241.158 (talk) 19:04, 13 July 2016 (UTC)

Role of Self-Reference and Franzen

This section needs to go imo...it adds little or nothing and the individual it's quoting is simply not particularly notable (ie his opinion, whether right or wrong isn't notable enough to include...unlike Wittgenstein whose opinions in this area (though mostly wrong) are most certainly notable...he's an obscure academic who wrote yet another fairly obscure book that attempted to explain the theorems to the general reader...idk how much he should even be cited in the article itself...I think the article can simply cite Gödel's paper itself for most of it's content/assertions...or is this against the rules?...like the above quotes from his paper about arithmetic...could we just cite him or do we have to cite someone else explaining it?? (I don't mind him being referenced briefly in the section just above along with Rebecca Goldstein etc, however)...68.48.241.158 (talk) 17:38, 13 July 2016 (UTC)

^as stands, I feel it's basically exactly analogous to Hewitt's desire for commentary by whoever it is he wants commentary by.....68.48.241.158 (talk) 17:53, 13 July 2016 (UTC)

Generally secondary sources are better for our purposes than primary. Certainly Gödel's own views are relevant, especially for the historical angle, but ideally what we're looking for is the conclusions that experts have come to in the intervening decades, with lots of time to think about it and polish their formulations.

Franzén is a useful source because he was a very smart guy who spent a lot of time analyzing the import of the theorems and making them accessible, but unlike the popularizers, he was personally an expert in the field.

I don't entirely like his take on this aspect, as I don't think the theorems are self-referential in the first place, so there is no need to strain to find formulations that are not. But I do think he's a good source. --Trovatore (talk) 18:50, 13 July 2016 (UTC)

depends what you mean, I guess..the notion of self-reference plays in with the meta-analysis from outside the system that discovers the truth of the proposition...in any event, this stand-alone section seems entirely dedicated to a fairly unimportant, idiosyncratic opinion of a fairly non-notable person...68.48.241.158 (talk) 19:10, 13 July 2016 (UTC)

The more I look at that section, the odder and more inappropriate it looks to me...it's an undeveloped stand alone section dedicated to an idiosyncratic opinion statement by a contemporary, non-notable academic...I'm going to delete it...per my reasoning and apparent at least soft support of Trovatore....if CBM or someone else wants to reinsert it please come here and explain....68.48.241.158 (talk) 00:10, 14 July 2016 (UTC)

I "approved" the edit, but that term was a bad choice by the software engineers. In general, I will approve edits even when if I have no opinion or possibly even disagree with them, so just because I "approved" them should not be taken as a comment other than that I don't want to see them "pending". (This is why sometimes I may "approve" a revision and then undo parts of it.) — Carl (CBM · talk) 00:38, 14 July 2016 (UTC)

fair enough, thanks..68.48.241.158 (talk) 00:48, 14 July 2016 (UTC)

I'm not sure I agree with the cavalier dismissal of Franzen by 68/anonymous editor. Franzen was a well-regarded expert in the field who wrote several books on the subject, both in terms of addressing a general audience and in terms of a mathematical one. I would put him on par with Raymond Smullyan in terms of reliability. The entire tone above sounds to me like "I don't like this quote. Since I've never heard of him, he is not a notable source and this should be deleted." The comments on self-reference are at least somewhat relevant (probably more), especially when you have folks in this talk page who imply and argue that the statements are self-referential and hence should be "disallowed". Magidin (talk) 03:29, 14 July 2016 (UTC)

this single opinion/commentary quotation simply doesn't warrant its own stand alone section imo...it's also basically repeating information from an earlier section in the article (as the explanation sentence below the quotation even says...imo work it in up there very briefly, if deemed worthwhile..but not with the whole long quote...nobody's quoted at such long length in the article...not Bertrand Russell, not Wittgenstein, not Godel himself...but "Torkel Franzen"??? It's the same thing as Hewitt wanting some long, also odd quotation by whatever unimportant person he wanted commentary by....68.48.241.158 (talk) 12:19, 14 July 2016 (UTC)

And again, and now scare quotes. Let me just say: just because you don't know who a person is does not mean that person is a nobody or an unknown, or an unreliable source. So, again, thanks for the cavalier dismissal of someone based mainly on your ignorance. I disagree on your analogy with Hewitt; the objections to the additions proffered by Hewitt are on their lack of substantive support of the views espoused. This is not the case with these; and, again: you may have no clue about who Franzen was. That does not make him the nobody you want to pretend he was. Last I checked, Argumentum ad Ignorantium was still a fallacy. Magidin (talk) 16:01, 14 July 2016 (UTC)

The quotations at [1] are substantive and support the views espoused.

Frazen is as authoritative as Smullyan and Hofstadter.

Carl (talk) 16:02, 14 August 2016 (UTC)

I know who the guy is in the sense that I read through his book quickly at a Borders Books nearly a decade ago now..He even has a small Wikipedia page too etc...my objections partly in that he's simply not notable enough to have a stand alone section devoted entirely to a single quotation of his..and partly that the section is itself just sort of odd itself in the context of the rest of the article...68.48.241.158 (talk) 18:25, 14 July 2016 (UTC)

Yes, I think Franzén is a fine source. Not as many people know him as know (say) Hofstadter, and he's not as good a writer (that's a high bar), but he has a much deeper and more solid understanding of the subject matter.

In context he doesn't seem to be saying that the sentences in question are self-referential, just that people perceive them to be and that misunderstandings result from this. I agree that's probably accurate; I just have a different strategy, and would prefer to tackle that misunderstanding at its source, by showing that the sentences are very ordinary (if long-winded) assertions about natural numbers, not about the sentences themselves.

But I obviously can't demand that Franzén follow my strategy. I think the material is reasonable to include. I'm not sure it merits its own section, though. --Trovatore (talk) 04:59, 14 July 2016 (UTC)

I agree it at least doesn't seem to merit its own stand alone section, at least as currently constructed..68.48.241.158 (talk) 11:36, 14 July 2016 (UTC)

Of course there is beaucoup literature that describes the Goedel sentence as self-referential, so it won't work for us to simply claim it isn't. Of course, the self-reference is indirect, just as with the recursion theorem in computability theory. And the Goedel sentence is just a $\Pi _{1}^{0}$ sentence of arithmetic, like the statement of Goldbach's conjecture and like many other statements about elementary number theory. Franzen's text is quite high quality and "mainstream" within the limited number of scholarly secondary sources directly about the incompleteness theorems. In the end, the Goedel sentence relies more on a kind of diagonalization than it does on self-reference, but finding a source that clearly expresses that may be challenging.

I don't mind the current set up, in which the article points out that the Goedel sentence indirectly refers to itself. On the other hand, it would be worth pointing out that the underlying phenomenon does not really depend on self-reference, because when we view the Goedel sentence as just a formula of arithmetic, forgetting its intended meaning, there is no self-reference there. Goedel mentioned this fact in print, as well, in responding to Wittgenstein, as we quote. For that subject, I am sure we can assemble something from a few sources - I suspect Peter Smith's book also comments on the issue. — Carl (CBM · talk) 12:50, 14 July 2016 (UTC)

The indirect reference is for the Gödel number of the string used to create the proposition I'm unprovable using the diagonal lemma. However in general, mathematical propositions do not have Gödel numbers because there are unaccountably many mathematical propositions (as was noted early on by Zermelo).

Carl (talk) 20:44, 14 August 2016 (UTC)

^and some of this speaks to confusions even otherwise learned people like Hewitt have about this topic imo..indeed, perhaps some of the new phrasing in the article along these lines will be helpful to readers..68.48.241.158 (talk) 13:11, 14 July 2016 (UTC)

For those of you interested in the current academic controversy concerning the validity of Gödel's proposition in mathematics, see the YouTube video of the recent SRI seminar [see link on my Google+ homepage (at CarlHewitt-StandardIoT) or go the the SRI International YouTube channel].

Carl (talk) 20:44, 14 August 2016 (UTC)

Language

From a Linguists viewpoint it might be OK, but this is really confusing: "The next step in the proof is to obtain a statement that says it is unprovable." What is "it"? The proof? There's a bit of irony in using self-reference in an argument about the incompleteness of (some?) self-referential logics. 91.66.3.34 (talk)

Further into the paragraph: "[... the diagonal lemma] says for any sufficiently strong formal system and any statement form F there is a statement p such that the system proves [...]". Nevermind that the term "statement form" isn't introduced before it is used. Maybe it's knowledge that I am expected to know (I get it, you talk about F). The sentence is still hard to parse. If the "system proves", then the system is a proof, which is idiosyncratic language, but the whole paragraph is trying to say in the end that the system cannot prove in this particular case, so it's mathematically misleading. 91.66.3.34 (talk)

"This sentence does not directly refer to itself" The mentioned sentence is not a correct sentence at all, most of all because the quote "when preceded by [...]" is not a syntactically correct statement in English and thus can't become a proven statement. 91.66.3.34 (talk)

Ultimately, all three points I made before concern a section that is covered again in another article Proof_sketch_for_Gödel's_first_incompleteness_theorem. 91.66.3.34 (talk) —Preceding undated comment added 22:24, 24 July 2016 (UTC)

Some of these are easy to resolve; others don't seem to be issues.

The "it" in the first case seems unobjectionable: "it" refers to the previous noun, "a statement". But it would be easy enough to say "says of itself that it is unprovable", so I will make that edit.

The "statement form" language should be rewritten, along with that whole section. But saying that a formal system, or a formal theory, "proves" a certain statement is perfectly normal usage.

In the third point - there is no reason that the content of the quote itself needs to be grammatically correct. For example, "bob purpled jump" when preceded by "blue" becomes "blue bob purpled jump" - and none of the quoted phrases is a sentence. The claim is not that the quoted statement is provable, but rather that the result of performing a certain transformation is provable. Analogy: "+2=4", when preceded by "2", is provable. This is because when "+2=4" is preceded by "2" it becomes "2+2=4".

Similarly

", when preceded by itself in quotes, is unprovable.",

when preceded by itself in quotes, gives exactly the phrase:

", when preceded by itself in quotes, is unprovable.", when preceded by itself in quotes, is unprovable.

which is a grammatical sentence regardless what is in the quotes. — Carl (CBM · talk) 22:26, 24 July 2016 (UTC)

It is worth noting that the Diagonal Lemma can also be used to produce the Liar Proposition: The negation of this proposition holds.

Carl (talk) 21:06, 14 August 2016 (UTC)

Up front: It's far besides the point to argue the lyrical analogue, while I don't understand the mathematical argument and the diagonal lemma.

I am trying to say that the liars paradox, "this sentence is wrong", is not a paradox. The easy way out of the paradox is to forbid this self reference. "this sentence is not a sentence" can be true and wrong depending on the interpretation. It is the most obvious contradiction. You can choose: either it is a sentence and wrong, or it is not a legal sentence but anything else.

I assume, a quote cannot grammatically correctly stand in for a subject. That is the whole sentence would at least have to start introducing the subject. I'll try:

'The quote, "The quote, X, when substituting the first X with the whole quote, is unprovable", when substituting the first X with the whole quote, is unprovable'

Now this seems to come down to saying that a free variable X is unprovable. Which is, depending on the definition of provability, which I'm not sure about, unremarkable.

And what about deduplicating the section and the other article? 31.16.51.96 (talk)

Diagonal Lemma produces the Liar Paradox

Using the Diagonal Lemma, there is a proposition P such that

   P ⇔ ¬P

Of course, the above proposition immediately infers a contradiction.

See Inconsistency Robustness in Foundations

Carl (talk) 16:12, 4 November 2016 (UTC)

I didn't realize propositions could be sentient. (The verb you're looking for is "implies", not "infers".) </pedant> —David Eppstein (talk) 18:15, 4 November 2016 (UTC)

Inference (⊢) is different from entailment (⇒) for inconsistency robust logic ;-)

See Formalizing common sense reasoning for scalable inconsistency-robust information coordination using Direct Logic™ Reasoning and the Actor Model

Carl (talk) 18:52, 4 November 2016 (UTC)

I don't see why what "Inconsistency Robust Logic" or "Direct Logic" (disputed trademark) has to say has any place in this article, except as it relects your expert, but not reliable, opinion. It might, if accepted. — Arthur Rubin (talk) 17:48, 12 November 2016 (UTC)

Classical Direct Logic is highly relevant to strong incompleteness theorems. See Proposals for article on Incompleteness theorem

Carl (talk) 19:07, 12 November 2016 (UTC)