Talk:Gödel's incompleteness theorems

This is the talk page for discussing improvements to the Gödel's incompleteness theorems article. 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.
Please sign and date your posts by typing four tildes (~~~~). Put new text under old text. Click here to start a new topic. New to Wikipedia? Welcome! Ask questions, get answers. This is not a forum for general discussion about the article's subject.	Be polite Assume good faith No personal attacks Be welcoming	Article policies No original research Neutral point of view Verifiability
Archives: Index, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

online book

Per Lindström (1997). Aspects of Incompleteness. Lecture Notes in Logic. Vol. Volume 10. Berlin: Springer-Verlag. {{cite book}}: |volume= has extra text (help)

It's a bit too technical for this article but online books are always good. 69.228.170.24 (talk) 08:34, 25 April 2010 (UTC)

I added it; sorry for the delay. — Carl (CBM · talk) 12:39, 30 June 2010 (UTC)

retrospective article -- alternative incompleteness proofs

Another article giving several different proofs. Appears to be a write-up of a talk given at a Tarski memorial conference. Paper is dated 2003, but the centenary of Tarski's birth would have been 2001, so maybe the conference was actually in 2001.

Kotlarski, Henryk "The incompleteness theorems after 70 years." Ann. Pure Appl. Logic 126 (2004), no. 1-3, 125-138.

69.228.170.24 (talk) 08:01, 8 May 2010 (UTC)

I can't get this paper unless I pay $31 or trudge to the library. Let's make a list. Can you list the various proofs? Add any others you know? Kleene 1967 concots the proofs using his T-predicate. So that's one alternative:

#1: Proof using Kleene's T-predicate (Kleene 1967:247-260)

#2 ?? Kleene 1952:427 lists "The Löwenheim theorem, since it leads to Skolem's "paradox" can be regarded as the first of the modern incompletness theorems" (Skolem 1938).

BillWvbailey (talk) 16:58, 8 May 2010 (UTC)

I'll see if I can find that paper again. I had found a reference to it and then went to some trouble to get a copy, but it wasn't as interesting as I'd hoped. I don't remember the specific proofs listed. Calling the Löwenheim–Skolem theorem an incompleteness theorem is a bit of a stretch; it's more about the limitations of first-order logic than about effective theories. For example, it says that true arithmetic, a non-effective theory not subject to the incompleteness theorems, has uncountable models. The 19th century Peano axioms were given in second order logic (the induction axiom uses a second-order quantifier) and have only one model, the "true" natural numbers. Löwenheim–Skolem says that it's impossible to do the same thing with purely first-order logic. 69.228.170.24 (talk) 02:20, 10 May 2010 (UTC)

Good explanation re Löwenheim–Skolem; I'll defer to your expertise. I found it in Kleene and put it down as a straw-dog. BTW I support your ANI, below. Bill Wvbailey (talk) 02:40, 10 May 2010 (UTC)

Heh, deferring to my expertise is ill-advised since I don't have any. The articles about Löwenheim–Skolem and Skolem's paradox are pretty good though. 69.228.170.24 (talk) 01:42, 12 May 2010 (UTC)

In Boolos, Burgess, and Jeffrey 2002 Computability and Logic: Fourth Edition chapter 17 "Indefinability, Undecidability, Incompleteness", they first prove the diagonal lemma and follow up with "Tarski's theorem", "Undecidability of arithmetic", "Essential undecidability theorem", "Goedel's first incompleteness theorem", and two "unprovability" theorems. Then in section 17.3 "Undecidable Sentences without the diagonal lemma" (pages 227-230) they offer up 4 versions (keeping my numbering from above):

#3: "a version of the incompleteness theorem ... without the diagonal lemma" [but it] still using the diagonal argument. This appears as "Problem 17.1: Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of Q fails to prove some true ∀-rudimentary sentence".

They then offer up three versions that use neither the diagonal lemma nor a diagonal argument, but rather versions built on self-referential semantic paradoxes (the various names such as "Goedel-Grelling formula" are their monikers):

#4.1: a heterological version using "Goedel-Grelling formula" and the notion of self-applicability of a number

#4.2: a naming/defining paradox using a "Goedel-Berry formula" and the notion of a "number being denominable [written out] in Q" (a theory of arithmetic). Given the fact that we can "denominate" any number n by the formula x = n, where n is the numeral 0 followed by n "successor"-accent-marks, i.e. x = 0 ' ' ' ... ' ' ', this requires n + 3 symbols. However, maybe we can concoct a formula to write a big number (B-B-J uses super-exponentiation as an example) in far fewer symbols. So then they construct their Goedel-Berry formula GB(x,y) expressing "x is the least number not denominable by a formula with fewer than y ⇑ y symbols". And from this they generate a sentence known to be true but not provable in Q.

#4.3: a version that extends #4.2 into a "Goedel-Chaitin formula" and the notion of the complexity of the "denomination".

I don't pretend to be conversant in any of these, especially #4.3 which is involved. As the authors note in the lead paragraph of section 17.3, all of these "depend on the apparatus of the arithmetization of syntax and the representability of recursive functions". To me #4.1 seems the easiest, but there is something peculiar about #4.2 (B-B-J's proof-sketch is sketchy). A version also appears in Martin Davis's 1980 Mathematics Today where he writes "Chaitin later showed how his ideas could be used to obtain a dramatic extension of Goedel's incompleteness theorem ..." (p. 265). I need to study this and Chaitin's 2005 Meta Math! The Quest for Omega to figure out where my discomfort derives from. Bill Wvbailey (talk) 15:09, 12 May 2010 (UTC)

You might like: C. Calude and H. Jürgensen, "Is complexity a source of incompleteness?"[1] I discussed this with CBM some time back but never got around to adding it to the article. I haven't seen Boolos et al's book yet but have been wanting to get it from the library sometime. 69.228.170.24 (talk) 05:32, 13 May 2010 (UTC)

I've printed out your paper. Chaitin in his Meta Math! (the man loves exclamation points! where where his editors!) adds another proof sketch! (He has boxed these sentences on the pages to emphasize them!):

#5 "Turing: Halting Problem Implies Incompleteness!" (p. 32). He offers a simple proof sketch of this. I think we can grant him its validity. Unfortunately he commits, again and again (e.g. on p. 167), the historical gaffe that "Turing solved the halting problem", the original halting proof being the work of Martin Davis following a proof-sketch to be found in Kleene 1952:382 -- Davis told me where to find the page in Kleene, etc. Chaitin's version is entirely different from Turing's original proof; the proof sketch Chaitin uses I found in Minsky 1967:148-149; whether Minsky's is a version of Davis's proof I dunno .... Martin Davis in Mathematics Today 1980:260-263 gives this same proof sketch, stating "Turing's work ... made it possible to see Goedel's discovery from a different, and indeed a more general, perspective".

#3 ? "Turing: Uncomputability Implies Incompleteness!" (p. 33). Here Chaitin invokes Emil Post and Post's "generated sets" that Chaitin wants to call "recrusively enumerable" but feels compelled to call "computably enumerable". So I suspect that this is a version of #3 above.

#4.3 "My approach: Randomness Implies Incompleteness!" (p. 34). I have yet to read Chaitin's account.

There is something humorous, and possibly useful to this article, in Chaitin's complaint about how much he dislikes Goedel's proof, first encountered by him -- in Nagel and Newmann's Goedel's Proof -- as a teenager in 1958: "I wasn't an idiot, so why couldn't I understand Goedel's proof? . . . I just plain didn't like Goedel's proof of his fabulous result. ... I disliked Goedel's proof, but I loved Turing's alternative approach to incompleteness using the idea of the computer. ... I loved incompleteness, but not Goedel's proof. Why? ... [because it is] a clever proof that only permitted you to have a superficial understanding of what was going on" (p. 27). Bill Wvbailey (talk) 16:18, 16 May 2010 (UTC)

I haven't read Chaitin's book so I don't know what his issue is, but you need a Gödel-like encoding to show that the halting problem can be encoded as an arithmetic statement using addition and multiplication. That is not totally obvious. For example, Tarski's proof of the decidability of real closed fields shows that you can't encode the halting problem as a statement in plane geometry. Presberger arithmetic shows you can't do it in arithmetic with just addition and no multiplication. By the time Chaitin explains why arithmetic with multiplication is different, he's presumably retraced Gödel. I also wonder whether Chaitin doesn't like Cantor's diagonalization proof of the uncountability of the reals. The halting problem itself though has a poetic proof that you might like. 69.228.170.24 (talk) 08:16, 26 May 2010 (UTC)

RE Chaitin's objection in Meta Math! The Quest for Omega: In his book he has an appendix that treats the Goedel incompleteness theorem fairly, but briefly. My take on it is his objections are personal/philosophic ones – he believes that Goedel's proofs of incompleteness based on diagonalization and arithmetization of syntax, although clever, "obscure" the deeper underlying "philosophic" issues (basically: if the axiom-set is finite, then nothing arrived at via the computer/computer "running" the axiom set through all the axioms is or ever can be "creative"; ergo the particular axiom-set + machinery is incomplete with respect to ALL mathematical truths ... and it doesn't matter which (finite) axiom-set you pick, "arithmetical" or not; different axiom-sets will result in different truths, but a single finite axiom set can never be used to arrive at ALL truths.)

RE "arithmetization of syntax" and "diagonalization" as tacit assumptions in Chaitin's proof: It's occurred to me, too, that Chaitin's proof might possibly have diagonalization and arithmetization embedded in it, somewhere, but I haven't spent enough time on it to figure it out. I'm in the process of (trying to) synopsize his argument. This much I know: he derives his incompleteness theorem "backwards" from considerations of maximally-compact "elegant programs" that are limited w.r.t. string-randomness, to the undecidability of the halting problem, to the halting probability "omega", to incompleteness. It appears to me that his argument is so different from Goedel's that the Goedel methods aren't applicable, but we shall see.

Also, I found this: Kolmogorov complexity#Chaitin's incompleteness proof, but I've not studied it, yet. Also: In his book Chaitin credits "Borel's paradox", not Berry's -- nowhere does the Berry paradox appear in his index. I need to study this more. Bill Wvbailey (talk) 23:49, 26 May 2010 (UTC)

This "Borel's paradox" so beloved by Chaitin is not the Borel-Kolmogorov paradox. It is related to the infinite monkey theorem. Bill Wvbailey (talk) 23:58, 26 May 2010 (UTC)

Chaitin's proof of Goedel's incompleteness theorem is only superficially different than the proof via the halting problem. The set 0' that represents the halting problem has the same Turing degree as the Kolmogorov complexity function K that Chaitin's proof uses, and both the proofs rely on a simple diagonalization technique. "Chaitin's incompleteness theorem" is also interesting but it's slightly different than Goedel's theorem. The article on Kolmogorov complexity is worth reading; it's intersting material. (As an aside, you have to take Chaitin's actual writings with a grain of salt. For one thing, the field is rife with priority disputes. Apart from that, Chaitin often writes popularizations in which he has more freedom to express his personal opinion about things than is usual in the professional literature.) — Carl (CBM · talk) 00:17, 27 May 2010 (UTC)

Feferman 1984

Is the reference

• Solomon Feferman, 1984, Toward Useful Type-Free Theories, I, Journal of Symbolic Logic, v. 49 n. 1, pp. 75–111.

doing the article any good right now? Nothing refers to it. I think it was originally inserted during one of the paraconsistency outbreaks that later got rolled back. I looked at the paper at that time. It is interesting, but more philosophical than mathematical. 69.228.170.24 (talk) 05:39, 24 May 2010 (UTC)

I think that the paraconsistency section is adequately sourced with inline sources at the moment. So if this one is in the references list but not referred to from the body of the article, I agree we can remove it. — Carl (CBM · talk) 21:14, 25 May 2010 (UTC)

Thanks. I took it out but maybe it can be used in some other article. It does seem significant to the broader question of what kinds of natural-language statements can be usefully formalized. 69.228.170.24 (talk) 07:30, 26 May 2010 (UTC)

another book

There's Something About Gödel: The Complete Guide to the Incompleteness Theorem

By Francesco Berto. Wiley-Blackwell. 256pp,. ISBN 9781405197663 and 97670. Published 6 November 2009

Review

Appears to be a popularization with emphasis on philosophy, but the review (written by a mathematician) is favorable. 69.228.170.24 (talk) 07:12, 24 May 2010 (UTC)

According to a review by Tony Mann (head of the department of mathematical sciences, University of Greenwich, and president of the British Society for the History of Mathematics):

In his [Berto] final section, he discusses the case of Ludwig Wittgenstein, whose response to Gödel has seemed puzzling. Here he shows that some recent ideas in logic seem to make Wittgenstein's position more plausible than it has sometimes seemed. This discussion of paraconsistent logical systems, in which some statements can simultaneously be both true and false, but which avoid the disastrous consequence that all propositions are true within the system, provides a stimulating conclusion to this fascinating book.

67.169.144.115 (talk) 17:59, 30 June 2010 (UTC)

epsilon calculus

Here is another article by Zach on the epsilon calculus; it may be similar to the content of the paper in Grattan-Guinness's book, in which case it's preferable since it's online.

• Zach, Richard (2003), "The Practice of Finitism: Epsilon Calculus and Consistency Proofs in Hilbert's Program" (PDF), Synthese, 137 (1), Berlin, New York: Springer-Verlag: 211–259, ISSN 0039-7857

Also, this article about von Neumann is good: http://www.infoamerica.org/documentos_pdf/neumann01.pdf

69.228.170.24 (talk) 09:54, 24 May 2010 (UTC)

I added the Zach 2003 reference and also left the 2006 reference to Grattan-Guinness's book in place. The 2003 article is pretty good, but only briefly discusses von Neumann's counterexample. 69.228.170.24 (talk) 07:49, 26 May 2010 (UTC)

Simpler Initial Summary Suggestion

“Gödel proved that no (non-trivial) system can be both complete and consistent. The rules of a “consistent” system are, logically, mutually-consistent, as one might guess from the name. A “complete” system has a rule set that can prove the truth value of each and every statement about the system.

“However, for every unprovable (category of) statement about a consistent system, there exists a rule that can evaluate the statement, and is consistent with all preceding rules. In other words, no finite set of rules can determine the truth value of every possible statement about any self-consistent system.”

No need to mention natural numbers since every true and finite statement can be expressed by some set of natural numbers. Michael McGinnis (talk) 06:48, 30 June 2010 (UTC)

There are non-trivial systems that are complete and consistent. For example, the axioms for an algebraically closed field of characteristic 0 are complete and consistent, and describe the field of complex numbers. That is certainly a non-trivial system.

I don't fully understand what the first sentence of the second paragraph is saying. But the last sentence isn't correct; there are finite axiom systems that are complete and consistent (but which do not interpret the natural numbers). One example is the axioms for a dense linear order without endpoints. — Carl (CBM · talk) 11:22, 30 June 2010 (UTC)

Pending changes

I changed the protection of this page so that, instead of being semiprotected, it is under pending changes protection. This allows non-registered users to edit the page, but their edits will not be displayed to the general public until the edits are marked as "reviewed" by another editor with "reviewer" privileges. Registered users can edit the article as usual.

All established editors in good standing are eligible to become reviewers on request. Simply contact me or another administrator. — Carl (CBM · talk) 12:36, 30 June 2010 (UTC)

Archiving

I archived a lot of older discussions today. I moved Wvbailey's monumental history research to its own page, so that it would not be hidden among the numbered archives. It will be a great reference for anyone editing this article. I don't know if there is a provision for "timeline" articles, but if there is, most of the research would be done for a timeline on Goedel. — Carl (CBM · talk) 12:51, 30 June 2010 (UTC)

  Nonstandard models

What I’m trying to say is a shot in the dark and relates to a fragment of Nagel and Newman’s “little masterpiece of exegesis”:  “The possibility of constructing a finitistic absolute proof of consistency for arithmetic is not excluded by Gödel’s results. Gödel showed that no such proof is possible that can be represented within arithmetic. His argument does not eliminate the possibility of strictly finitistic proofs that cannot be represented within arithmetic. But no one today appears to have a clear idea of what a finitistic proof would be like that is not capable of formulation within arithmetic.”Thanks for your comment Trovatore. Indeed I’m imagining a theory that has its objects of discourse the literal natural numbers and some other “stuff”, that is, the conception that ‘zero is the immediate successor of not a number’ which can be seen as an extension of the conception of arithmetic over the non-arithmetical plane, or better, an extrapolation of the conception of the observable arithmetical component onto the non-observable arithmetical component. This “stuff” causes an amalgamation of two of the Peano axioms into the statement ‘the immediate successor of anything is a number’ which can be called “a very weak mathematical assumption” (is this the term Hilbert used?). Accordingly, this statement incorporates both an observable and a non-observable arithmetical component. Also, the suggested extension or extrapolation leads to a simplification of the Peano axioms and not to a complexification like for example ZFC. This all lies within the field of mathematical logic and the limits of Hilbert’s program. Conversely, it could be possible to build up a deductive system (that incorporates observable and non-observable arithmetical components) from a very weak mathematical assumption that encompasses the Peano axioms (the observable arithmetical component). The possibility of a strictly finitistic proof of consistency of this deductive system within itself could still be possible because such a proof cannot be expressed within the formalism of arithmetic and is (according to Nagel and Newman) therefore excluded from Gödel’s theorem. Sarahcroft (talk) 15:21, 15 July 2010 (UTC)

Fascinating.  Could you please clarify how much of this is in Nagel-Newman, and how much is speculation?  Tkuvho (talk) 07:28, 16 July 2010 (UTC)

Of course, what is between quotations comes from Nagel and Newman (Gödel’s proof 1958, page 76). The view that Hilbert’s program has to be extended is shared with, for example, Kurt Gödel. This can be found in Torkel Franzén (Gödel’s Theorem 2005, page 39) “It is often said that the incompleteness theorem demolished Hilbert’s program, but this was not the view of Gödel himself. Rather, it showed that the means by which acceptable consistency proofs could be carried out had to be extended.” The idea that there are two ways of extension, that is, in quantity or in quality (not quantity) is both common sense and logic. For example, to accept that ‘Russell’s teapot exists’ is true can be seen as an extension in quantity. In order to accept that ‘existence exists’ is true one first must be willing to accept this as something that can be reasoned about (non ignorabimus) and then extrapolate the meaning of the term ‘exist’ onto itself, that is, accept a more profound conception of the term ‘exist’ which can be seen as an extension in quality. In order to keep this all relevant to the Wikipedia project, the view expressed above does not appear to contradict with what is said on the wikipage ‘Hilbert’s problems’ under ‘table of problems’; “There is no consensus on whether results of Gödel and Gentzen give a solution to the problem as stated by Hilbert. Gödel's second incompleteness theorem, proved in 1931, shows that no proof of its consistency can be carried out within arithmetic itself. Gentzen proved in 1936 that the consistency of arithmetic follows from the well-foundedness of the ordinal ε₀.”On this page in the intro it says “The two results are widely interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all of mathematics is impossible, thus giving a negative answer to Hilbert's second problem.” which technically speaking might be correct, yet still gives a misleading impression. It would be nice at least to mention that there is no consensus. Sarahcroft (talk) 14:13, 17 July 2010 (UTC)

Sarah, I think the only reason no one has responded to you with a clear "no" is that we're not quite sure we know what you're asking.  If you would ask a specific question concisely, rather than in wall-of-text style, I'm 95% confident you'll get a clear answer of "No, you can't do that, and here's why".

What I think you may be missing is that the content of the theory being studied does not need to be formalized into arithmetic to make Goedel's argument go through.  All you have to formalize into arithmetic are methods of proof, which are the same for all first-order formal theories, irrespective of their content.  So you can't evade the theorem by going to the "non-arithmetical plane".

The reason there's no consensus on Hilbert's second is simply that it's not clear exactly what Hilbert's second problem was. --Trovatore (talk) 19:52, 17 July 2010 (UTC)

It would be nice to include sourced dissent on interpreting Goedel's theorems as "negative answer" to Hilbert's program.  The more appropriate place for this would probably be Hilbert's program rather than here.  One text I am thinking of is an insightful report by Avigad and Reck from a decade ago.  Tkuvho (talk) 20:18, 17 July 2010 (UTC)

Well, we don't have to go overly subtle on that point, as there should be plenty of sources referring to Gentzen's work as a positive answer.  --Trovatore (talk) 20:32, 17 July 2010 (UTC)

Oh, sorry, you said Hilbert's program (I was still thinking of Hilbert's second problem).  Right, that's a different question entirely. --Trovatore (talk) 20:33, 17 July 2010 (UTC)

Well, it is hard to comprehend that it is possible to give a negative answer to Hilbert’s second problem and simultaneously accept that it’s not clear exactly what Hilbert’s second problem was. However, I’ll trust your expertise on this topic and humbly withdraw myself from this talk page. I’ll try to express my point of view on the arguments page because you were polite enough to give me a 5% change. Sarahcroft (talk) 11:51, 18 July 2010 (UTC)

Done, 'A non-mathematical understanding of a mathematical crisis' can be found on the arguments page of this talk page (see header). Sarahcroft (talk) 17:35, 20 July 2010 (UTC)

His argument does not eliminate the possibility of strictly finitistic proofs that cannot be represented within arithmetic. But no one today appears to have a clear idea of what a finitistic proof would be like that is not capable of formulation within arithmetic. I thought Gentzen's consistency proof can be presented as precisely that: a finitistic combinatorial (but not arithmetic) proof of CON(PA). It is not an arithmetic proof because it uses structural induction on trees, rather than arithmetic induction on a set generated by coinduction on a successor function starting from zero. But it is finitistic because the trees themselves are finite. It can also be presented as an arithmetic proof using induction on transfinite ordinals, but that version could be called infinitistic. 67.122.211.208 (talk) 00:29, 31 July 2010 (UTC)

Moving comments on Wittgenstein to arguments subpage

I have moved yet more discussion to the Arguments subpage. As with the previous n discussions, this was devolving into arguments about historical minutiae that had little or nothing to do with concrete improvements to our Wikipedia article. —David Eppstein (talk) 03:41, 31 July 2010 (UTC)

Interesting that Wikipedia has decided to suppress from the article the published work by Professors Berto, Hewitt, Priest, and Routley (later Sylvan) on Wittgenstein's role in the incompleteness theorem controversy. Wonder how long this will last? 99.29.247.230 (talk) 17:56, 31 July 2010 (UTC)

The article does mention paraconsistent logic, in the section titled "paraconsistent logic". It directly cites Priest, Shapiro, and Hewitt. — Carl (CBM · talk) 19:38, 31 July 2010 (UTC)

You evaded the complaint that the professors have written that Wittgenstein was treated unfairly and that you have taken the side against Wittgenstein. 64.165.100.82 (talk) 17:31, 1 August 2010 (UTC)

Given your apparent admission here of violating the ban imposed by Wikipedia:Requests for arbitration/Carl Hewitt, I'm semi-protecting this talk page. —David Eppstein (talk) 17:51, 1 August 2010 (UTC)

Recent long videos on Incompleteness and Inconsistency

Two recent long videos on incompleteness and inconsistency:

• Dangerous Knowledge BBC Documentary by David Malone. June 2008.
• Wittgenstein versus Gödel on Foundations of Logic Stanford Logic Seminar by Professor Carl Hewitt. May 2010.

63.112.0.74 (talk) 23:44, 9 August 2010 (UTC)

These were inserted into the article and accepted as reviewed edits but I think the Hewitt video should have been rejected based on all the previous debate about Hewitt's stuff. I have no opinion about the BBC doc. 75.62.4.94 (talk) 07:32, 11 August 2010 (UTC)

I have submitted an edit (not yet approved) removing the Hewitt video. I think it should be approved. 75.62.4.94 (talk) 07:39, 11 August 2010 (UTC)

Alright. Now you need to discuss this, because this thing pops up on pending changes and kinda clogs up the list. Come to a decision and then make an edit. thanks. Choyoołʼįįhí:Seb az86556 ^{> haneʼ} 07:48, 11 August 2010 (UTC)

I made an edit but it looks like it wasn't accepted. I think the link should be removed. If you're not comfortable doing that, it's ok, one of the other participants can do it, it's not any kind of emergency. But if you look in the article's protection log you'll see that the article has been repeatedly semi-protected, and even this talkpage was semi-protected for a while, precisely to keep the excessive Hewitt stuff from getting put back into the article. The article is now under FR (a drastic step) for precisely the same reason. I'm not familiar with FR from the reviewer side--do reviewers have to watchlist the article to get notified of the edits? Any reviewers watchlisting this page should be aware of the situation and reject any Hewitt-related additions that haven't been previously discussed on the talk page. If it's the case that all the edits go to every reviewer including those not generally paying attention to the article, then maybe FR is the wrong mechanism for dealing with this problem. But in that case I think it's not so good for it's wider intention of preventing things like BLP vios. It's possible to do that in rather subtle ways, so anyone reviewing edits to sensitive articles (I guess this isn't one) really should be familiar with the content, the reliability of different possible sources, etc. Thanks. 75.62.4.94 (talk) 08:07, 11 August 2010 (UTC)

Addition: Actually, I think both videos should be removed per WP:EL. The BBC video seems only distantly connected to the incompleteness theorems, it's stream-only, it needs closed-source software for viewing, and (I can't tell) it looks like only a clip is available on the BBC site. 75.62.4.94 (talk) 08:15, 11 August 2010 (UTC)

Per your comments I removed it. Wvbailey (talk) 17:01, 11 August 2010 (UTC)

• Your (Hewitt) edit seems to have been skipped over due to other edits around it. I have accepted it on a purely arbitrary basis. I had looked at it previously but I do not have the technical knowledge to deal with it. Twiceuponatime (talk) 09:52, 11 August 2010 (UTC)

Thanks. A summary of the Hewitt situation is here. I've looked at the FR documentation and it does look like all pending revisions go to a central place, so this can get confusing. 75.62.4.94 (talk) 11:04, 11 August 2010 (UTC)

I watched the Hewitt video, which is a talk he gave. It's a perfectly good talk. My only concern is how closely it is related to the incompleteness theorems. Hewitt emphasized at the beginning and during the questions that the key motivation for the material in his talk is possible applications to computer science. I didn't remove the video link from the article, but I don't have strong feelings about it either way. — Carl (CBM · talk) 23:49, 11 August 2010 (UTC)

Tourlakis book

I noticed this edit [2], which was reversed. I have never looked at Tourlakis' book. Does he actually give a detailed proof of the second incompleteness theorem (more detailed than is usual)? If so, that is something we could use a reference for.

The Hilbert/Bernay book is somewhat old right now, I would feel bad recommending it as a reference unless there is no other option. — Carl (CBM · talk) 11:22, 13 August 2010 (UTC)

I've actually taught from Tourlakis's book, at York — it was the Logic in Computer Science course. But the class was largely Boolean logic; I think we got to predicate logic a little near the end, but we certainly didn't go into detail about the Goedel theorems, so I don't really remember what was said about them. It's possible it's not the same book.

In any case, it was a good, well-written text, despite my philosophical disagreements with the author (who's a really nice guy though!), and based on that experience I think it's likely to be a good reference. --Trovatore (talk) 19:42, 13 August 2010 (UTC)

negative answer to Hilbert's second

The current lead sentence claims that the theorems gave a negative answer to Hilbert's second. Was this discussed? At Hilbert problems we say that there is no consensus on whether it answers Hilbert's second, which I think is accurate. I'll probably simply remove the claim unless someone comes up with better wording. --Trovatore (talk) 19:59, 7 September 2010 (UTC)

I think that the relationship with Hilbert's second problem should be mentioned somewhere in the lede, even if the wording is improved. It's a relatively important aspect of the theorems.

More generally, I think the lede is too short for the article. We could go up to three paragraphs. I am thinking of something like:

1. Very general intro
2. Summary of the theorems themselves (sections 2-8 of the current article)
3. Summary of the applications / philosophical implications / etc. (sections 9 and 10 of the current article)

— Carl (CBM · talk) 23:11, 7 September 2010 (UTC)

all true statements about the natural numbers?

The page claims that "It is possible to have a complete and consistent list of axioms that cannot be enumerated by a computer program. For example, one might take all true statements about the natural numbers to be axioms (and no false statements). But then there is no mechanical way to decide, given a statement about the natural numbers, whether it is an axiom or not, and thus no effective way to verify a formal proof in this theory." I find this dubious. To have a "list" of all "true" statements about the natural numbers, we first need to know which natural numbers, and which statements are true. The assumption that we know what the natural numbers are and what the true statements about them are may be unproblematic according to some views, but not all mathematicians subscribe to this. Also, the article makes no mention at all of the fact that the statements that are "true but unprovable" may in fact be falsified in a suitable model. Tkuvho (talk) 07:10, 8 September 2010 (UTC)

Why do we need to know which statements are true? That would be necessary for us to write the list; it is not necessary for the list to exist.

There is no ambiguity about which natural numbers. The true but unprovable (in PA, for example?) statements are indeed false in some model of PA — but they are not false in the natural numbers. --Trovatore (talk) 08:06, 8 September 2010 (UTC)

I added a link to the article true arithmetic to that paragraph. The use of the word "true" here is perfectly standard, and you won't be able to read very much logic without it. It's the same sense of "true" as in Tarski's undefinability theorem.

I do think it would be nice to point out that undecidability of a sentence means, by the completeness theorem, that there are models in which the sentence holds and models in which it fails. So in particular there are models where Pvbl(0=1) holds. But I'm afraid that if I write it off the top of my head, any use of the word "standard" or "true" will be criticized... So it will have to wait until I find a good reference for it. I'll be in the office later and can look for one then. — Carl (CBM · talk) 11:37, 8 September 2010 (UTC)

Isn't the use of "true" and "false" purely syntactic here? There is no semantic content at all. It's purely mechanical, as can be seen when you use a Turing machine as the environment in which you express and then perform your proofs. This derives from Emil Post's tautology business that all evaluations (from two mutually exclusive and exhaustive classes K1 and K2) of the variables of a tautology (axiom) always yield one class (e.g. K1). And we (confusingly) have nicknamed this class K1 "truth" and the other class K2 "falsity", two words that have much different meanings in the context of inductive reasoning. And this deductive-reasoning characteristic of tautology is inherited under substitution and modus ponens, purely mechanical operations. BillWvbailey (talk) 13:47, 8 September 2010 (UTC)

No. True and false are semantic. Provable and refutable are syntactic. --Trovatore (talk) 20:25, 8 September 2010 (UTC)

I agree with Provable and refutable. But on what grounds can you assert that anything mathematical is "true"? You probably mean "logically true" and this is exactly what the K1-K2 business is expressing (i.e. it's relative to the logical system. For example: in one system K1 is "interpreted" such that K1 & K1 yields K1; in another system K0 & K0 yields K0). This is wikipedia's take on logical Truth:

However, logic does not deal with truth in the absolute sense, as for instance a metaphysician does. Logicians use formal languages to express the truths which they are concerned with, and as such there is only truth under some interpretation or truth within some logical system.

A logical truth (also called an analytic truth or a necessary truth) is a statement which is true in all possible worlds [ref Ludwig Wittgenstein, Tractatus Logico-Philosophicus /ref] or under all possible interpretations, as contrasted to a fact (also called a synthetic claim or a contingency) which is only true in this world as it has historically unfolded. A proposition such as “If p and q, then p.” is considered to be logical truth because it is true because of the meaning of the symbols and words in it and not because of any facts of any particular world. They are such that they could not be untrue.

Am confused, must be missing something. Others (e.g. Searle the philospher) must be confused, too. Bill Wvbailey (talk) 22:31, 8 September 2010 (UTC)

No, I do not mean logically true. I mean true in the sense of corresponding to the world. The world including real mathematical objects, independent of our reasoning about them. --Trovatore (talk) 22:34, 8 September 2010 (UTC)

In the end, the usual meaning of "true" here is "true in the standard model". From the realist perspective, which Trovatore is expounding, there simply "is" a standard model, and "true" means true in that model.

However, even logicians who are not realists use the word "true" in places like Tarski's theorem and Goedel's theorem. They simply reinterpret the word "true" to fit their preferred meaning when they read it.

For example, you could reinterpret "true" to mean "disquotationally true", at which point "4 is even" is "true" for the same reason that "Germany borders France" is "true": because 4 is even and Germany borders France. This is similar to realism in some respects, but it does not actually require that the number 4 "exists", just that we can recognize some English sentences as "true".

There are other ways of reinterpreting the word "true". I described a couple more in this post [3].

In any case, the convention in logic (actually, mathematics as a whole) is to write "as if you have a realist perspective", and then reinterpret the words to mean something different if you do not actually have a realist perspective. Although there are several different meanings of "true arithmetic", all but a vanishingly small number of logicians would agree that the concept is well defined, even if they differ about how exactly to define it.

By analogy: nobody would respond to "we see that a solution to x^2−1= 0 exists" with a complaint that the quoted phrase is assuming mathematical realism. It's just the way that mathematics is communicated, and we know that we can read "exists" to mean something else if we are not a mathematical realist. — Carl (CBM · talk) 01:03, 9 September 2010 (UTC)

Nicely said. I would quibble that it is not necessary that "the standard model" exist as a completed totality to make sense of what I have said (as it regards the natural numbers); it suffices that the predicate "is a natural number" be well-specified. This is obviously more important when you get to set theory; V does not exist as a completed totality, but the realist take on interpreting set-theoretic statements nevertheless makes sense. --Trovatore (talk) 01:12, 9 September 2010 (UTC)

Yes, I agree. — Carl (CBM · talk) 01:22, 9 September 2010 (UTC)

Okay, I hear your philosophies (and thanks for the link). But I'll argue that the use of "true" and "false", however construed, in the context of Goedel's completeness and incompleteness theorems is, well, how do I say it politely: factually wrong, historically incorrect and unfair to the reader. In both papers he carefully avoided the words "true" and "false", using in their place "provable" and "refutable" (just as Trovatore substituted above), (he did slip once in the completeness proof). There's an excellent essay by Dreben and van Heijenoort in Volume I of Kurt Goedel: Collected Works (pages 44ff) re the problem at the time of Lowenheim's "model-theoretic, that is semantic" treatments and the Hilbert-school "semantic" versus Post's "syntactic" completeness. This is carried forward in Dawson's intro (page 198) where (Goedel is writing in 1967 to Wang): "Goedel speaks of the "prejudice, or whatever you may call it" of logicians of the time against such transfinite concepts as that of "objective mathematical truth", prejudice that Goedel took pains to circumvent by his rigorous syntactic treatment of 1931" [my boldface]. By the way, this syntactic-only K1-K2 treatment isn't me, I found it in Nagel and Newman 1958 "Goedel's Proof 1958:109-113. Oh well, as I'm not a "principal author" on this article, I'll leave it to you guys with my objections: in the spirit of Goedel this article should not contain model theory (tacit or explict, hence no semantic "truth" and "false") unless clearly indicated/warned that this was not Goedel's intent; rather you should be presenting the theorems in their purely mechanical syntactic form as Goedel intented. Bill Wvbailey (talk) 14:17, 9 September 2010 (UTC)

Surely you are aware that Goedel is well known for his views that mathematical statements have objective truth values. Moreover, to quote directly from Goedel's 1931 paper on the incompleteness theorems:

"From the remark that [R(q);q] says about itself that it is not provable it follows at once that [R(q);q] is true, for [R(q);q] is indeed unprovable (being undecidable)." van Heijenoort 1967, p. 599, para 2, emphasis in the original.

Here Goedel explicitly explains why the Goedel sentence is, in his words, "true". You're right that Goedel's proof is entirely syntactic, and that Goedel wrote the paper to to be publishable in a climate where results were expected to be finitistic. But Goedel was not only aware that the incompleteness theorem demonstrated true but unprovable sentences, he thought the point was sufficiently important to mention in the paper. The argument that his intent was to avoid all mention of semantic notions cannot be sustained. — Carl (CBM · talk) 16:01, 9 September 2010 (UTC)

Interesting re his assertion of the "truth" of the [R(q);q]. I'm not convinced we really know what he means here because I'm not convinced he did either. Here's why: Somewhat to your point but more to Goedel's uncertainty (it would dog him his entire life -- see next quotes from his 1953/9 and 1961/?) about his understanding of "truth" at the time he wrote his 1931: "Unlike his paper, his reply [Goedel's reply to Zermelo involved truth-values, and it may have led him to break his self-imposed silence on truth and increase his interest in semantics, which was usually "under cover" in the positivist VC [Vienna Circle]" (Grattain-Guiness 2000:513). Before I agree or disagree with your first assertion about what Goedel believed about "truth" I need to read, in Volume III of Collected Works, a paper + commentary (1953/9)) titled Is mathematics syntax of language?. Indeed in the first sentence Goedel invokes the year 1930 and Carnap, Hahn, and Schlick, his Vienna buddies. 1953/9 is a difficult, murky and long paper and comes in a couple versions (version III is 1953, version V is 1959). For example from the intro: "He [Goedel] insists on a sharp distinction between the two realms [empirical and mathematical]. 'The syntactical point of view as to the nature of mathematics doubtless has the merit of having pointed out the fundamental difference between mathematical and empirical truth. This difference, I think rightly, is placed in the fact that mathematical propositions, as opposed to empirical ones, are true in virtue of the concepts occuring in them' (V, page 2). His disagreement with the positivists lies in his view of the realm of concepts as an independent reality ..."(page 332). Whereas the commentator states that "The heart of Goedel's criticism [of Carnap, Hahn, and Schlick] is an argument based on his Second Incompleteness Theorem", the commentator ends with, "As his discussions of mathematical intution in *1961/? and in 1964, his thinking on the issue continued to evolve over the next few years" (p. 334). Indeed, the commentary to *1961/? notes that Goedel believed that "the truth lies in the middle" between the materialist/positivist and the idealist/spiritualist. This looks like a good read. BillWvbailey (talk) 18:59, 9 September 2010 (UTC)

You may also be interested in Martin Davis's work on Gödel's Developing Platonism. I heard it as a talk; I'm not really sure whether there's a paper by that name, but surely he wrote up something under some title.

Of course how Gödel himself thought of it is not entirely dispositive. This is an article on the theorems, not on Gödel. As Carl has explained, the convention in mathematics is to talk like a Platonist whether you are one or not. The text comes out much cleaner and less muddled that way, especially when metamathematical considerations are around. What would truly be a disservice to the reader would be to let the text devolve into the sort of muddled exposition that you see in the popularizations, when they start talking about "branching" between G and ~G, as though the branches had equal epistemic status. --Trovatore (talk) 19:29, 9 September 2010 (UTC)

possible

I suggest to replace "it is possible to have a list" by "there is a list", which underlines the fact that this is a mere existence statement. We might add that the existence of such a list can be shown in ZFC, or your favorite axiom system for mathematics. --Aleph4 (talk) 16:19, 8 September 2010 (UTC)

I made a change like that; it also removes the "possible" aspect which might have the wrong connotation.

I'm not sure about adding something about the existence being provable in a stronger theory only because that opens a can of worms about the stronger theory itself being incomplete. Even though this shouldn't matter, it opens the door for confusion unless we spend several sentences on it, which would distract from the actual point of the paragraph. — Carl (CBM · talk) 01:35, 9 September 2010 (UTC)

I suppose the change to the statement "there is a list" is an improvement, but it is still unsourced. People might wonder where exactly it is that there is such a list. Those of us in the know, know its precise location in the great Platonic storehouse, protected by angels swinging two-sided swords with names like MO and CM, all the while realizing that it is all a conventional matter of talking accepted in the community. However, outsiders might want a reference. Tkuvho (talk) 05:16, 13 September 2010 (UTC)

The important thing to get across is that the stipulation that the axioms be computably enumerable is an important one; without it the first theorem does not hold (the second one is not necessarily even well-formed). True arithmetic is the natural example to use. I'm not trying to insist that this text assert that true arithmetic exists; that's really beside the point. How about we reword it along those lines? Just say that true arithmetic is a counterexample, and finesse the whole question of whether it exists. --Trovatore (talk) 05:25, 13 September 2010 (UTC)

Actually the link to true arithmetic might be enough. I am still confused about the statement of the first incompleteness theorem itself. Is this a different notion of "truth"? And if it is the same, wouldn't it be appropriate to link it to true arithmetic, as well? Or is this supposed to be the same as saying "disquotational truth"? If so, a reader would have a hard time surmising this. Tkuvho (talk) 05:30, 13 September 2010 (UTC)

Well, it's the same sense of truth, but it's because of the Goedel theorems that we actually know we need to distinguish truth from provability, so I'm not sure I'd want to link to true arithmetic from the statement that the Goedel sentence of a consistent theory is true. Also, the latter is arguably more concrete than true arithmetic in general, because if a statement of the form of the Goedel sentence is false, it can be falsified by exhibiting a finite object and performing computable operations on it; that's not true of arithmetic statements in general. --Trovatore (talk) 06:25, 13 September 2010 (UTC)

article on 2nd incompleteness theorem

http://sammelpunkt.philo.at:8080/1126/1/Bagaria.pdf

Found via this MO thread: http://mathoverflow.net/questions/27279/proof-of-godel-incompleteness

67.117.130.143 (talk) 08:17, 2 December 2010 (UTC)

Inaccurate description of work by Professor Hewitt

I noticed that someone deleted an editor's suggestion of a less inaccurate description of the work of Professor Hewitt that read as follows: "Carl Hewitt has proposed that a powerful inconsistency robust logic (which is inconconsistent becuse theories can prove their own incompleteness) has applications in software engineering and the Internet."

What is the motivation for Wikipedia having an inaccurate description of Hewitt' work? 71.198.220.76 (talk) 19:21, 5 December 2010 (UTC)

The description in the article is, "Carl Hewitt (2008) has proposed that (inconsistent) paraconsistent logics that prove their own Gödel sentences may have applications in software engineering.". Apart from differing adjectives, that's that same as the text you quoted. — Carl (CBM · talk) 23:11, 5 December 2010 (UTC)

User:CBM is being disenguous in trying to cover up controversies that he would prefer to censor.

• The first constroversy is between paraconsistency and and the much stronger criterion of inconsistency robustness. Paraconsistency merely means that not everything can be inferred from an inconsistency. (Thus a theory is paraconsistent even if a rule is added to the effect that an inconsistency infers that the moon is made of green chees.) Inconsistency robustness requires that nonsense cannot be inferred from just an inconsistency.
• A second way that User:CBM is being disengenous is by insulting Professor Hewitt's work by claiming it only "may" have applications to software engineering and omitting discussion of the Internet altogether
• Also, he is trying to censor mention of the published paper referenced above.

There will be a symposium about the subject this summer, see Robustness 2011 at Stanford.

70.137.154.215 (talk) 18:12, 6 December 2010 (UTC)

Accusing fellow editors of "covering up", "censoring", etc. is against wikipedia policy. As far as the specific point concerning applications, if your basis for this is an arxiv post you mentioned above, then such as claim is considered as unsourced by wiki standards and should be deleted altogether. Good luck with the stanford symposium and hopefully it will lead to publications in refereed journals that can be used here. Tkuvho (talk) 18:25, 6 December 2010 (UTC)

I see that the C. Hewitt paper is on its fifty-third version (!), but this does not make it "published", contrary to what you claim above. Tkuvho (talk) 18:28, 6 December 2010 (UTC)

Of course, it's published, and by a reputable publisher! Each of the published versions is immutable and we have the advantage that we can see the evolution of development in a place that is freely accessible as opposed to having to try to to trace development through references in journals and proceedings that are not freely accessible. Would you prefer that previous versions not necessarily be accessible as on Google Knol? 67.169.144.115 (talk) 19:34, 6 December 2010 (UTC)

Arxiv is not a publisher, but a preprint repository with pretty much zero content control. It is not subject to standard peer review, and as such it does not count as a reliable source according to Wikipedia standards.—Emil J. 19:40, 6 December 2010 (UTC)

It is more than zero: submissions can be removed from arXiv for being off-topic or for being substantially below scientific writing standards (e.g. having no references). And many papers on arXiv are also peer-reviewed in other venues. That said, I agree that being on arXiv by itself is not enough to qualify a paper as being reliably published, and that WP:SPS is the appropriate standard to use when judging whether such papers can still be used as sources. —David Eppstein (talk) 19:46, 6 December 2010 (UTC)

The article's critics have considerable science on their side whereas Wikipedia adminstrators have Wikilaw. Hewitt has published an excerpt from his ArXiv article on Knol as Incompleteness Theorems: The logical necessity of inconsistency. The account of imcompleteness there is quite different from the one in the Wikipedia article Incompleteness Theorems. The longer that Wikipedia censors the work, the worse for its reputation. ~~ —Preceding unsigned comment added by 171.66.107.146 (talk) 00:00, 9 December 2010 (UTC)

Maybe this will be the undoing of wikipedia, but those are the rules here. The Knol site seems like a blog page which does not meet the criteria for inclusion here. Personally I think that barring this kind of input is what gives wikipedia its vitality. Tkuvho (talk) 03:51, 9 December 2010 (UTC)

I doubt that this particular censorship will have much effect on Wikipedia. However, this kind of censorship discourages contributions to Wikipedia and causes users to have look eleswhere for information. Google is probably the largest beneficiary of the censorship.13.7.64.111 (talk) 01:43, 10 December 2010 (UTC)

Perhaps, but wikipedia is not a blog page, and most serious contributors here realize this. Tkuvho (talk) 03:47, 10 December 2010 (UTC)

No one is under the illusion that Wikipedia is a blog. However, Wikipedia is inconsistent on the issue of allowing links to ArXiv publications. Sometimes, as in the case of Perelman they are allowed. In other cases, such as this one, they have been banned. 67.169.144.115 (talk) 19:43, 10 December 2010 (UTC)

I'll support liking to Hewitt's arxiv paper, like Perelman's, as soon as Hewitt is awarded the Fields Medal for that paper, like Perelman was. As for Wikipedia's inconsistency, didn't Hewitt prove that it's logically necessary?

Wikipedia often includes references event to blogs, e.g., Arsenic in nucleic acids. So the removal of the reference to Hewitt's ArXiv article in favor of an inferior reference looks like personal animosity against Hewitt on the part of Wikipedia. 63.249.116.52 (talk) 21:40, 19 December 2010 (UTC)

Wikipedia articles often contain all kinds of inappropriate things, that's the nature of the beast, but that's no reason that this article should. Paul August ☎ 22:11, 19 December 2010 (UTC)

The contrast is quite amazing between the Wikipedia article Incompleteness theorems and the Hewitt article Incompleteness Theorems: the logical necessity of inconistency, which is a popularization of Common sense for concurrency and inconsistency robustness using Direct Logic(TM) and the Actor Model arXiv:0812.4852. It will be interesting to see how this controversy develops. 99.29.247.230 (talk) 21:39, 23 December 2010 (UTC)