Talk:Gödel's incompleteness theorems

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Mathematics (Rated B+ class, Top-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
A-BB+ Class
Top Importance
 Field: Foundations, logic, and set theory
One of the 500 most frequently viewed mathematics articles.
WikiProject Philosophy (Rated B-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 


Untitled[edit]

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.

Hawking[edit]

Godel has been endorsed by Hawking. Hawking draws far-reaching conclusions from Godel's theorems of 1931. See http://www.hawking.org.uk/godel-and-the-end-of-physics.html — Preceding unsigned comment added by 88.150.234.8 (talk) 08:47, 27 June 2014 (UTC)

Hawking says that "The Godel number of 2+2=4 is *." The asterisk is apparently a permanent part of Hawking's text, not a computer error. — Preceding unsigned comment added by 88.150.234.8 (talk) 08:52, 27 June 2014 (UTC)
Hi, 88.150.234.8. Please be aware that article talk pages are not for general discussion of the subject matter, but for discussing what the article should say and how it should say it. Is there something from the page you linked that you think could be used to improve this article? If so, could you be more specific? Thanks, --Trovatore (talk) 09:10, 27 June 2014 (UTC)
Hawking's article of 2002 is already mentioned three times in Wikipedia. See Quantum mechanics, Theory of everything and History of electromagnetic theory. — Preceding unsigned comment added by 88.150.234.8 (talk) 09:40, 27 June 2014 (UTC)

Apocryphal quote?[edit]

Dear all,

There's a quote by Stephen Kleene (Kleene 1967, p. 250) on Gödel's incompleteness theorem which supposedly clarifies Gödel's VI (so called "first") theorem. Kleene's more "accessible" statement is now quoted left, right and center throughout the interwebs (It's even in published books!). The quote is below:

“Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory” (Kleene 1967, p. 250).

I have Kleene's book (Mathematical Logic, 1967), and the quote is nowhere to be found!

Can anyone please verify this? — Preceding unsigned comment added by Akineton (talkcontribs) 03:16, 6 July 2014 (UTC)

I am not interested in fake maths from Godel and Kleene. — Preceding unsigned comment added by 2.98.54.17 (talk) 15:11, 13 December 2014 (UTC)
This does not seem to be on p. 250 of Kleene 1967. I am not a mathematician, but Gödel's 1931 paper had a note added to it in 1963, which states:
"...it can be proved rigourously that in every consistent formal system that contains a certain amount of finitary number theory there exist undecidable propositions and that, moreover, the consistency of any such system cannot be proven in the system." [Kurt Gödel: Collected Works: Volume 1: Publications 1929-1936, p. 195]
Hope this helps.(Edited to fix bungled indentation). Astrakhan4 (talk) 00:38, 15 January 2015 (UTC)
Yes, the same quote can also be found at van Heijenoort 1967:616 (addendum added by Gödel in 1963). I hunted through Turing 1936-7 but didn't find it there. A hint in the quote is "effectively generated", a notion that was defined after Gödel 1931 and Turing 1936-7 in the work by Kleene and Rosser (1938 and after). I'm still searching. Bill Wvbailey (talk) 23:07, 16 January 2015 (UTC)
There's a theorem in Kleene 1952:208 that states that " . . .if the system is consistent then it is (simply incomplete) with [a particular formula Aq(q)] as an undecidable formula". Kleene names this "Rosser's form of Gödel's theorem". The formula is a diagonalization of something, but I don't know what that something is. The search continues. BillWvbailey (talk) 23:44, 16 January 2015 (UTC)
Here are some "Informal" statements of Gödel's Incompleteness Theorems, quoted from Franzen; it's clear that the quote-in-question is an amalgam of Gödel and Rosser:
First Incompleteness Theorem (Gödel-Rosser): Any consistent formal system S within which a certain amount of elementary arithmetic can be carried out is incomplete with regards to statements of elementary arithmetic: there are statements which can neither be proved, nor disproved in S. (Franzen 2005:16)
Second Incompleteness Theorem (Gödel): For any consistent formal system S within which a certain amount of elementary arithmetic can be carried out, the consistency of S cannot be proved in S itself. (Franzen 2005:34)
Franzen observes that Gödel never formally proved his "second" incompleteness theorem, and this was left to David Hilbert and Paul Bernays in their 1939 Grundlagen der Mathematik (Foundations of mathematics). If someone has a cc of this in English this would be an interesting place to search for the quote. [Note to self -- have searched early Rosser and Kleene a few times, Kleene 1952, also Nagel and Newman. Tarski? not in my Tarski. ]. BillWvbailey (talk) 17:50, 17 January 2015 (UTC)

---

Here is the reason we cannot find the quote. Read on:

So I went back (this took a while) through the history, starting at the beginning, dividing and conquering, until I lit on how this "quote" came to be referenced. Here is a selection of versions that show its evolution over the years. By middle of 2009 editor CBM was in the midst of a major re-write, and that when the paragraph was first tagged as needing a reference, and then referenced by CBM to Kleene 1967:250:

end Dec 2007
Gödel's first incompleteness theorem, perhaps the single most celebrated result in mathematical logic, states that:
For any consistent formal, computably enumerable theory that proves basic arithmetical truths, an arithmetical statement that is true, but not provable in the theory, can be constructed.(refactored from 1) That is, any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.
end June 2008:
Gödel's first incompleteness theorem, perhaps the single most celebrated result in mathematical logic, states that:
For any consistent formal, recursively enumerable theory that proves basic arithmetical truths, an arithmetical statement that is true, but not provable in the theory, can be constructed.(refactored from 1) That is, any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.
end Dec 2008:
Gödel's first incompleteness theorem, states that:
Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,[1] but not provable in the theory.
13:05 20 July 2009
Gödel's first incompleteness theorem states that:
Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,[1] but not provable in the theory.[citation needed]
13:07 20 July 2009, CBM edit: (→‎First incompleteness theorem: ref)
Gödel's first incompleteness theorem states that:
Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,[1] but not provable in the theory (Kleene 1967, p. 250).

The reference did not appear before this time, and it has been there ever since. I suspect that the reference is being used "disquotationally", i.e. as a "cf" or "see, for example Kleene 1967:250). However, Kleene 1967:250 is not a very good place to land. Propose we change the "quote" to that of Franzen quote, above:

First Incompleteness Theorem (Gödel-Rosser): Any consistent formal system S within which a certain amount of elementary arithmetic can be carried out is incomplete with regards to statements of elementary arithmetic: there are statements which can neither be proved, nor disproved in S. (Franzen 2005:16)

The use of "proved" here makes me queasy (it's not defined: does it mean "derived from" using modus ponens and substitution?) but I prefer this because it does make it very, very clear that this statement of the theorem is the result of work by Rosser as well as Gödel. I am not sure what to do with the "disquotational" footnote [1] however; the word "true" complicates the matter. I have a cc of Goldstein and cannot find the quote there either (CBM added both Kleene 1967 and Goldstein as references in an earlier edit).

Any thoughts out there about this? I'm going to remove the reference to Kleene, but I'm not going to do anything else for a little while. BillWvbailey (talk) 17:29, 18 January 2015 (UTC)

My key sticking point is that, whatever we do, we must continue to make clear that the Goedel (or Rosser) sentence of a consistent theory (considered as a statement about arithmetic, not about the objects of discourse of the theory) is true. There is far too much obfuscation on this point in the popularizations. We need to put this right out front, and let there be no confusion about it.
The bit about which version is due to Goedel and which to Rosser strikes me as more of a historical detail, and the distinction between them more of a technical detail. Both are certainly important enough to deal with in the article, and we ought to get them right, which I am grateful to Will for on his attention to these details. But I don't care as much about exactly how or where they are presented. --Trovatore (talk) 21:54, 18 January 2015 (UTC)
I hear you about true, and Gödel-Rosser. Are you okay with what's there now in the article? If so let's just leave the wording as it is (as a précis, but not a quote). What about the footnote, is that satisfactory? (BTW: When I googled the quote I was surprised at how widely travelled the spurious Kleene reference has become. As long as the "précis" is okay technically I don't think there's much to worry about here.) BillWvbailey (talk) 22:20, 18 January 2015 (UTC)
Yes, I think it's OK, though I'm not sure "précis" is the exact word I would have chosen, partly because I'm not sure exactly what it means. In school it seems to me that a précis was a summary of an essay, sort of like an abstract. Is that what you were trying to get at? --Trovatore (talk) 22:42, 19 January 2015 (UTC)
Yes, that would be my intent. I admit "précis" is an unusual word. My trusty Webster's 9th defines précis as "a concise summary of essential points, statements, or facts" (first usage approx 1760). I suppose the other word (you used it, too) would be plain-vanilla, simple old "summary". Bill Wvbailey (talk) 23:34, 19 January 2015 (UTC)

College Publications[edit]

I was unable to find the book

Carl Hewitt (2014). "Inconsistency robustness in foundations: Mathematics self proves its own consistency and other matters". In Carl Hewitt and John Woods assisted by Jane Spurr. Inconsistency Robustness. College Publications. ISBN 978-1-84890-159-9. 

at the College Publication site http://collegepublications.co.uk/about/ or anywhere else. John Woods is a widely published author many of whose articles are reviewed at MathSciNet. It should be possible to mention this at the talkpage. Tkuvho (talk) 10:08, 15 April 2015 (UTC)

Disquotationally??[edit]

In the Note, it is asserted that the use "here" of "true" is disquotational. First, the link fails to provide any clear insight about wtf the editor is attempting to say. Second, my Shorter Oxford English dictionary has no entry for that word. Speak English, please! Third, the link is to the Redundancy Theory and no longer to Disquotationalism. Fourth, what does "here" mean? Does it mean the editor will on a minute by minute basis check that any future change in this article will comply with his (its gotta be a guy, I think) demands on how "true" must be used in all cases? Or does it mean "in this section"? paragraph? moment? Fifth, How does this "note" contribute to this article? It doesn't as far as I can see. Sixth, it would be nice for the various types of "truth" to be distinguished...I don't think its possible to have only one kind of "true" when discussing a theory of true statements - am I wrong? (There is true, meta-true, meta-meta-true, etc.). My general comment (and based on the arguments page, this is going to be lost on the fan-boys here) is that if a topic is presented in needlessly obfuscatory language, then most of its utility is lost. And this article is clearly needlessly obfuscatory. I suggest the editors, prior to starting their editing session, look in the mirror and repeat "Oh, what a clever, intelligent, witty boy I am!" until its out of their system. Then try to write clearly for the audience that Wikipedia is intended for. Like, by always distinguishing statements (propositions) IN a system from statements ABOUT a system and clearly indicating when a statement is one, the other, or both. Oh, what a smart boy I am!173.189.79.42 (talk) 22:31, 17 May 2015 (UTC)

Just taking one point: You say "I don't think its possible to have only one kind of "true" when discussing a theory of true statements - am I wrong? (There is true, meta-true, meta-meta-true, etc.)".
Answer: Yes, you are wrong. Hope this helps. --Trovatore (talk) 18:09, 18 May 2015 (UTC)