Misplaced Pages

Revision as of 17:53, 19 June 2011

This article has not yet been rated on Misplaced Pages's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Top‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Misplaced Pages. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Top This article has been rated as Top-priority on the project's priority scale. Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details. Philosophy: Epistemology / Logic Mid‑importance This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Misplaced Pages. 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 Misplaced Pages.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy Mid This article has been rated as Mid-importance on the project's importance scale. Associated task forces: /  Epistemology Logic

Gödel's incompleteness theorems was a good article, but it was removed from the list as it no longer met the good article criteria at the time. There are suggestions below for improving the article. If you can improve it, please do; it may then be renominated. Review: May 8, 2006.

Archives

Arguments (Nov 2005–) Archive 1 (Oct 2001–July 2005) Archive 2 (Nov 2005–Nov 2006) Archive 3 (Nov 2006–Nov 2007) Archive 4 (Dec 2007–Aug 2008) Archive 5 (Aug 2008–Oct 2009) Archive 6 (Nov 2009–June 2010) History (Feb 2010–May 2010)

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" 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 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?" 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? ... 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 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)

This book could be used for a very nice informal presentation of Gödel's theorems and even the underlying ideas and techniques used, but by nice I mean, that the author is actually very rigorous with his writing and the 'technical' part of his book is not simplified just to the right level.--77.99.177.192 (talk) 20:20, 16 January 2011 (UTC)

Very intriguing. Who does the book attribute the "paraconsistent" interpretation to? If Berto mentions specific authors it may be appropriate to elaborate on this viewpoint in this page. Tkuvho (talk) 06:02, 17 January 2011 (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 Misplaced Pages 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 Misplaced Pages article. —David Eppstein (talk) 03:41, 31 July 2010 (UTC)

Interesting that Misplaced Pages 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 Misplaced Pages: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 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 , 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 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 .

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" . 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 says about itself that it is not provable it follows at once that is true, for 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 . 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 " (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 insists on a sharp distinction between the two realms . '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 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)

Sigfpe

Sigfpe has a nice blog post about provability logic:

• Generalising Gödel's Theorem with Multiple Worlds. Part I.

Not for direct use in article but may be of interest to editors. Part II is up as well, and is mostly Haskell code. I also like this old post of Xor's Hammer:

• What Happens When You Iterate Gödel’s Theorem?

67.117.130.143 (talk) 09:21, 25 December 2010 (UTC)

Stanford symposium that includes this subject

There will be symposium that includes this subject at Stanford next summer. See Inconsistency Robueness 2011]. 63.112.0.74 (talk) 23:34, 26 December 2010 (UTC)

New Video Available

There is a new video available of a Stanford colloquium that discusses this subject available at How to Program the Many Cores for Inconsistency Robustness with slides available at 70.137.165.34 (talk) 20:51, 17 January 2011 (UTC)

What does this have to do with Gödel's incompleteness theorems? — Arthur Rubin (talk) 00:56, 18 January 2011 (UTC)

The video discussed the demonization of Wittgenstein by Gödel and other classical logicians because Wittgenstein dared to point out that proof of incompleteness leads to inconsistency. 64.134.224.220 (talk) 05:56, 18 January 2011 (UTC)

Wittgenstein's comments are already well known by philosophers apart from Carl Hewitt's comments. For whatever reason, Wittgenstein's comments on the incompleteness theorems are, at the moment, not found very important in the mathematical logic literature, and are mostly of interest to philosophers and historians. Paraconsistent logic makes up a tiny part of research in mathematical logic, and the textbook presentations of the incompleteness theorems rarely even mention it.

This article has a short section on Wittgenstein's comments. I can't see that there is much more to say without giving Wittgenstein far too much weight. It would be equally inappropriate for us to spend a long time here on Paul Finsler's opinion on the incompleteness theorem, which is another contradicting opinion that does not have much impact on the mathematical logic community today. Wittgenstein's and Finsler's criticism are of mostly historical interest at this moment in time. — Carl (CBM · talk) 13:05, 18 January 2011 (UTC)

I just looked through Ludwig Wittgenstein and found not a word about Goedel or inconsistency. Would such a discussion be appropriate there? Tkuvho (talk) 13:12, 18 January 2011 (UTC)

The passages the the IP editors are referring to are a short part of Philosophical Investigations. I doubt that they merit a long discussion on the page about Wittgenstein himself; I have the sense that his remarks on consistency are sort of an application of his general philosophy, rather than a key topic of interest. The SEP article also doesn't seem to focus on them. But I am not a Wittgenstein scholar; maybe you should ask at Talk:Philosophical Investigations about it. — Carl (CBM · talk) 13:26, 18 January 2011 (UTC)

Because acceptance of Wittgenstein's publications would be a disaster for classical logic, classical logicians have been intent on diminishing the importance of his work on logic.64.134.233.83 (talk) 17:37, 18 January 2011 (UTC)

What you are proposing is a conspiracy theory. It is impossible to refute a conspiracy theory. This does not mean that what you write is not correct. However, such material cannot be included in a wiki page without sourcing. If the conspiracy theory is correct, this means that, unfortunately, valuable science is not being represented on wiki. If so, it is a regrettable consequence of wiki policies. But the policies are unlikely to be changed to accomodate this particular item. Tkuvho (talk) 20:31, 18 January 2011 (UTC)

How can it be a conspiracy theory when it is all done out in the open?

Gödel had the following to say about Wittgenstein:

• It’s amazing that Turing could get anything out of discussions with somebody like Wittgenstein.

• Wittgenstein did “not” understand it (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite.

• He has to take a position when he has no business to do so. For example, “you can’t derive everything from a contradiction.” He should try to develop a system of logic in which that is true.

24.180.11.235 (talk) 04:03, 19 January 2011 (UTC)

The use of the term "demonisation" seems excessive, which in a way undermines the reliability of the video. If these quotations from Goedel can be sourced in serious secondary materials, it can be documented, say, at Wittgenstein. Tkuvho (talk) 05:36, 19 January 2011 (UTC)

"Demonization" is a strong word. But it is probably appropriate in this case.

Classical logicians believed that they had been completely victorious over Wittgenstein’s heresy. For example, according to :

• "Gödel’s results altered the mathematical landscape, but they did not “produce a debacle”.
• There is less controversy today over mathematical foundations than there was before Gödel’s work."

However, the groundbreaking realignment came later when computer science invented a useable inconsistency tolerant logic because of pervasive inconsistency in computer information systems.

Gödel obfuscated that incompleteness "Showed the untenability of the logistic thesis that all of mathematics is subsumed within one all-embracing system of logic." But computer science needed an all-embracing system of inconsistency robust reasoning. Consequently, just as Wittgenstein said, proof of incompleteness resulted in the logical necessity of inconsistency, which is devastating to classical logic that Gödel defended.68.170.183.198 (talk) —Preceding undated comment added 23:17, 19 January 2011 (UTC).

Query about First Incompleteness Theorem

Does the first incompleteness theorem imply that any axiom scheme that generates undecidable statements can be extended to include the said undecidable statements by fiat? That is, by incorporating the undecidable statements (or their negations) as axioms we can extend the axiom basis? This extension would, of course, generate yet more undecidable statements. -- cheers, Michael C. Price 17:47, 19 January 2011 (UTC)

What do you mean by "generates undecidable statements"? It's, well, obvious that if Φ is an undecidable statement in the theory T then both T + Φ and T + ~Φ are both consistent, and (if subject to the incompleteness theorems) then the each have further undecidable statements. — Arthur Rubin (talk) 17:52, 19 January 2011 (UTC)

It may be obvious to you, but I doubt it is obvious to most readers. And I think a statement in the article to that effect would be helpful. -- cheers, Michael C. Price 18:01, 19 January 2011 (UTC)

It is already stated in the article, in the "First incompleteness theorem" section.—Emil J. 18:17, 19 January 2011 (UTC)

I see. In its present form, it reads:

Gödel's theorem shows that, in theories that include a small portion of number theory, a complete and consistent finite list of axioms can never be created, nor even an infinite list that can be enumerated by a computer program. Each time a new statement is added as an axiom, there are other true statements that still cannot be proved, even with the new axiom. If an axiom is ever added that makes the system complete, it does so at the cost of making the system inconsistent.

I suppose it could be made more specific, but do you (Michael) have any specific suggestions suggestions for improvement? — Arthur Rubin (talk) 19:03, 19 January 2011 (UTC)

That's not what I meant. I meant this paragraph:

Each effectively generated theory has its own Gödel statement. It is possible to define a larger theory T’ that contains the whole of T, plus G as an additional axiom. This will not result in a complete theory, because Gödel's theorem will also apply to T’, and thus T’ cannot be complete. In this case, G is indeed a theorem in T’, because it is an axiom. Since G states only that it is not provable in T, no contradiction is presented by its provability in T’. However, because the incompleteness theorem applies to T’: there will be a new Gödel statement G’ for T’, showing that T’ is also incomplete. G’ will differ from G in that G’ will refer to T’, rather than T.

That's pretty specific, as far as I can see.—Emil J. 19:29, 19 January 2011 (UTC)

Thank you Emil, Arthur. I have another layman's query; if the unprovable propositions can extend the axiom system, why do we call them "true"? Surely they are neither true nor false, but just unprovable? I see there has been a big discussion here, reflected in the article, about what "true" means, but it sounds odd to me, and surely some other readers, that we can extend an axiom system with the negation of a statement that is deemed to be true; i.e. with false statements. -- cheers, Michael C. Price 19:37, 19 January 2011 (UTC)

When people say "true" you should read it as "true in the standard model". This is a widespread convention in mathematics. The article could benefit from a section on the truth of the Goedel sentence, but that requires finding an appropriate source first. — Carl (CBM · talk) 19:59, 19 January 2011 (UTC)

To put it another way, Michael: Fix one formal theory, for example first-order Peano arithmetic (PA). By design, the Goedel sentence for PA, G_PA is true exactly in the case that PA cannot prove G_PA. That's just how the construction works.

But then, assuming PA is consistent, PA really cannot prove G_PA. Therefore G_PA is true. There is really no way around this.

And yes, as you say, it is possible to extend PA with a false statement, namely the negation of G_PA, without making the extended theory inconsistent. But it should not be assumed that, merely because the extended theory is consistent, it's just as good as what you would get if you added G_PA instead of its negation. It's not just as good; it's consistent, but unsound (that is, proves some things that are false). --Trovatore (talk) 20:22, 19 January 2011 (UTC)

Is "unsoundness" fatal? I should've thought so, but just checking... Does the same problem exist with the undecidable statements that are not Goedel sentences? I should've thought not, but just checking (again)... -- cheers, Michael C. Price 23:04, 19 January 2011 (UTC)

It isn't fatal in the sense of making the theory inconsistent, it just means that the theory is no longer true in the standard model. This happens with all sorts of independent sentences. For example the Paris-Harrington theorem is a non-Goedel sentence that is independent of Peano arithmetic. But we can prove in ZFC that the sentence is true; so if we add the negation of the sentence to PA we get a consistent theory that is no longer "sound" in Trovatore's terminology. I call theories true in the standard model "true theories" instead. — Carl (CBM · talk) 23:13, 19 January 2011 (UTC)

To be honest I don't know that the terminology standard model is necessarily all that helpful; it makes something appear technical that's actually direct and intuitive. The Goedel sentence of a theory says that there is no natural number having a certain property, a property checkable in principle by an algorithm; it's true just in case there is no number having that property. To be sure, you could say the same thing about the word disquotationally, which I added some time ago. --Trovatore (talk) 03:06, 20 January 2011 (UTC)

I like your phrasing, The Goedel sentence of a theory says that there is no natural number having a certain property, a property checkable in principle by an algorithm , and think it should go in the article, with some clarifications. Viz, does a certain property, mean some invariant specific certain property, or does it mean that the property is specified within the Goedel sentence, so that we can have a number of permissible, alternative Goedel sentences? -- cheers, Michael C. Price 11:08, 20 January 2011 (UTC)

You mean across different theories, or different Goedel sentences for the same theory? Of course it's a different property for different theories.

If you're talking about a single theory, I think the property in question is going to depend on some arbitrary (and mostly unimportant) choices about how you code up the arithmetization of syntax and so on, so you should still be able to get formally different properties. But I don't think their differences are going to be very interesting — they'll code up the same idea, just using a different coding. --Trovatore (talk) 05:48, 21 January 2011 (UTC)

Okay, I think I follow, but the notion that we can prove things that are "false" needs some clear explanation in the article. -- cheers, Michael C. Price 23:17, 19 January 2011 (UTC)

Well, it's not really any deeper than "if you start with false assumptions, you can prove false conclusions". What else do you want to say?

(There is one slightly subtle point, I have to admit, that is essentially ignored in the article. I hesitate to bring it up because I'm afraid any discussion of it will come across muddled. It's the following: What I said above is assuming that the objects of discourse of the theory are natural numbers, or things that are standardly taken to code natural numbers, like sets in ZFC.

(Well, what if they aren't? What if the objects of discourse of the theory are, say, star-bellied sneetches? The theorems still apply if all the conditions are met. Among those conditions is that there must be a way to code up naturals as sneetches, and then prove certain facts about these translated naturals, using the axioms of sneetch theory.

(Now, the Goedel sentence for sneetch theory, you might say, is a claim about sneetches, not about naturals. It isn't really — what you do is you code up the provability stuff in the naturals, get a Goedel sentence, and then translate it into the language of sneetch theory, using the translation that was assumed to exist. If sneetch theory is consistent, then the Goedel sentence is true, as a claim about naturals. But there is no reason to think it's true as a claim about sneetches. That's why the current language talks about an arithmetical truth that cannot be proved in the theory. I'd really prefer not to dwell on this in the article.) --Trovatore (talk) 06:59, 20 January 2011 (UTC)

Re Michael C Price: could you please summarize exactly what change to the article you are proposing here? — Carl (CBM · talk) 15:27, 22 January 2011 (UTC)

Semiprotected

Given the persistent and obvious block evasion by User:CarlHewitt and/or his friends, from multiple IPs over too wide a range to selectively block all of them, over a very long time span, and given the way they turn every thread here into being about their own idiosyncratic views rather than about anything to do with improvements to the article, I have semiprotected this talk page. Unfortunately, that also locks out legitimate editors who have not yet established a user-id here. If anyone has any less painful solution for dealing with this, please speak up, but I don't think conversing with them has been working very well. —David Eppstein (talk) 05:10, 22 January 2011 (UTC)

As nice as it would be to have a respite from that annoying person (I'm not going to bother to pretend it might be plural) I'm a bit concerned about this. Isn't there a rule that you can't semiprotect both an article and its talk page? Or is the article still on "patrolled revisions" or whatever it's called rather than semiprotection? I suppose that would leave some sort of opening for anons to raise their concerns — edit the article and leave an edit summary in explanation. --Trovatore (talk) 06:27, 22 January 2011 (UTC)

WP:SILVERLOCK says it's ok to apply non-indefinite semiprotection to talk pages "when they have been subject to persistent disruption". I think that clearly applies here. But you're right, it also says that a page and its talk page should not both be protected at the same time. So, I'll undo the talk protection, because the article protection is more important. Perhaps a round of reading WP:DNFTT should be prescribed for all, instead? That means, please stop replying to off-topic discussions here (and I know, I have been guilty of replying myself, so I get to read that again too). —David Eppstein (talk) 06:49, 22 January 2011 (UTC)

The Arbitration case regarding Carl Hewitt explicitly allows for semiprotecting talk pages (Misplaced Pages:Requests for arbitration/Carl Hewitt#Post-case clarification). I have re-semiprotected the talk page for one month and noted it in the enforcement section there.

FWIW I am not convinced the IP editors are all the same person; they seem to have differing levels of (mis)understanding of the incompleteness theorems. However I agree with David Eppstein that it's time to semiprotect the talk page for a while. — Carl (CBM · talk) 14:23, 22 January 2011 (UTC)

Well, we've seen sandbagging before from this source. He makes naive-sounding comments and forces you to explain basic things to him, presumably hoping you'll slip up, or at least say something that gives him an opening to make a point. --Trovatore (talk) 20:31, 22 January 2011 (UTC)

change "Arguments" page to "Questions"

Responding to D. Eppstein's post about DNFTT: one difficulty more generally is that people often use this talk page to ask about aspects of the theorems they don't understand, even when those aspects are already covered in the article. For example, the section started by M. Price above. Those sections always have the property that they might in principle relate to editing the article, but they don't have any concrete suggestions about it, just questions about things that might already be covered in the article.

I think it might be reasonable to move the "Arguments" page to the more friendly name "Questions". Then we might feel less hesitant about moving threads that don't directly relate to any specific changes to the other page. Thoughts? — Carl (CBM · talk) 14:28, 22 January 2011 (UTC)

Just to clarify: there is much I don't understand about this subject, but what I am trying to clarify is what the article is trying to say, which is not the same thing at all. BTW thanks for addressing the clarification tags I placed to in the article (although the 2nd one I'm not sure was completely addressed). -- cheers, Michael C. Price 18:37, 22 January 2011 (UTC)

added "Collected Works" to articles by Goedel

hi, I've added the collected works, as they are the "canonical" source for Goedel's work and the community sanctioned translation into English of the original paper. thanks. Valeria.depaiva (talk) 15:50, 12 March 2011 (UTC)

Thanks. We should add the name of the translator; I'll get a copy from the library. — Carl (CBM · talk) 01:07, 13 March 2011 (UTC)

I have Vol III. I don't think there's going to be a clean answer to "the name of the translator". Some of the texts were English originals; the ones that were not are individually notated as to who the translator was. E.g. for Lecture at Göttingen (*1939b), "the translation was drafted by John Dawson and revised in consultation with William Craig." --Trovatore (talk) 09:21, 13 March 2011 (UTC)

Oh, never mind — I must have been thinking this was Gödel's bio. You're presumably talking about the incompleteness paper. --Trovatore (talk) 09:24, 13 March 2011 (UTC)

As the 1st reference section notes the translator of the incompleteness paper is van Heijenoort -- one side of the page is the original, the other is van H's translation. But I believe that he's not the only translator throughout the 5 volumes. And by the 1940's Goedel was writing in English. Question: Does the reference Some basic theorems on the foundations of mathematics and their implications need to be added to this article as a reference, or as "further reading"? When I return from Oz I can check this out. Bill Wvbailey (talk) 10:30, 15 March 2011 (UTC)

"not unique"

I think the point of the "not unique" language was the following: There are lots of arbitrary choices you can make in implementing the proof, for example in the arithmetization of syntax, or in the construction used to prove the recursion theorem. Make different choices, and you get a different Goedel sentence.

That point has now been removed, which I'm actually fine with — it appears that the meaning was not clear even to us, and the important point is really that you can make all those choices explicitly, and have the proof then give you a byte-for-byte specific sentence for each c.e. theory (or really, I suppose, for each program witnessing that the theory is c.e.). Expanding the sentence so that it was clear would probably distract from the flow. So I'm not sure I have a current suggestion; mostly this is for clarification between us. Secondarily, people could be thinking about whether there's somewhere in the text that the point could be made without distraction, and if so, whether this is desirable. --Trovatore (talk) 20:17, 22 January 2011 (UTC)

A possibly subtle point in that section is that it is talking about an effectively axiomatized theory rather than an effectively axiomatizable theory (cf. "complete separable metric space" and "Polish space"). I kept the uniqueness fact, but I phrased it as "The proof constructs a specific Gödel sentence for each effectively generated theory, but there are infinitely many statements in the language of the theory that share the property of being true but unprovable."

One thing I have in mind here is that, by the proof of the second incompleteness theorem, once you have fixed a predicate Pvbl(n), any φ such that φ↔~Pvbl(#(φ)) is provably (in T) equivalent to the canonical consistency statement ~Pvbl(#(0=1)), and so any two fixed points are provably equivalent to each other. So it doesn't matter which fixed point you take in the first incompleteness theorem, after you have nailed down the provability predicate. The proof of the diagonal lemma constructs a particular fixed point.

Changing to a different provability predicate (a different effective axiomatization) will of course change things dramatically unless you can prove in the theory that the two effective axiomatizations enumerate the same set of axioms. In general that cannot be done.

I could probably work these ideas into the article. The text has simply been silent on the issue of comparing different fixed points so far. — Carl (CBM · talk) 20:42, 22 January 2011 (UTC)

1st theorem explanation

This part didn't seem well written:

"Gödel represented statements by numbers. Then the theory at hand, which is assumed to prove certain facts about numbers, also proves facts about its own statements, provided that it is effectively generated..."

The wording "which is assumed" is not entirely clear to a reader and some steps are unclear as well. As I'm not an expert I would like to offer a rewording of the explanation to see if it improves the article, rather than edit the article directly:

To prove the first incompleteness theorem, Gödel conceived of representing statements by numbers, in effect creating a system comprised of numbers and properties of numbers, isomorphic to the axioms and theorems of the theory at hand. Questions about the provability of statements would be able to be represented as questions about the properties of numbers. If effectively generated, the theory at hand could then be used to prove facts about its own statements. In particular, if the system were complete such questions would be decidable.

Gödel then used proof by contradiction to show that for any system claimed to be complete, one could always construct numbers (known as the Gödel sentence) which stated that no natural number exists with a certain, strange property, and also that a number with this property (if it existed) would be equivalent to a statement encoding a proof of the inconsistency of the theory. If there were such a number then the theory would be inconsistent, contrary to the consistency hypothesis. So, by contradiction, no such number can exist. Hence the claim of completeness is incorrect.

FT2  10:00, 25 March 2011 (UTC)

I'm traveling and can't work on it rght now, but I can try to clarify the paragraph in a couple days if nobody else gets to it first. — Carl (CBM · talk) 10:45, 25 March 2011 (UTC)

"wrote Gödel" vs "wrote to Gödel"

Is this a Yank/Brit thing? If Brits don't like the bare dative for the indirect object of "write", then I think we should probably use "to Gödel" per WP:COMMONALITY, because it's a point of indifference to Americans. --Trovatore (talk) 23:35, 4 April 2011 (UTC)

If that analysis is correct, then, I apologize for reverting the change. Perhaps the sentence could be written to avoid "wrote to (name) to (reason)", which looks particularly bad to me. — Arthur Rubin (talk) 23:51, 4 April 2011 (UTC)

In spoken English (without quotation marks) "wrote (name) to (reason)" is ambiguous in a way that "write to (name) to (reason)" is not. In written English, readers do not always play close attention to punctuation and quotation marks. Logperson (talk) 08:56, 5 April 2011 (UTC)

How is it ambiguous? — Carl (CBM · talk) 11:30, 5 April 2011 (UTC)

He wrote "Gödel" to show his knowledge of the German alphabet.

He wrote Gödel to express his admiration for the great man.Logperson (talk) 16:25, 5 April 2011 (UTC)

Those are only ambiguous if you don't hear the whole sentence. But if that's the standard, then

He dyed his shoes blue.

is ambiguous because it begins with "He died". On the other hand Misplaced Pages is primarily a written medium, rather than an oral one, and we don't need to assume our readers are unable to follow reasonable sentences like "I wrote him to tell him about my theorem". The chance of such things being misinterpreted is vanishingly small. — Carl (CBM · talk) 19:43, 5 April 2011 (UTC)

surprise examination paradox

This is kind of neat, and might be worth mentioning in the article. It proposes that the second incompleteness theorem resolves the surprise examination paradox. One of the authors, Ran Raz, is a well-known CS theorist, FWIW. 69.111.194.167 (talk) 21:58, 16 April 2011 (UTC)

Unstated assumptions about equivalence and consistency

"This is equivalent to the existence of a program that enumerates all the theorems of the theory without enumerating any statements that are not theorems."

In what way is this equivalent? What unstated assumptions or definitions are being used here?

"If all true statements about natural numbers are taken as axioms for a theory, then this theory is a consistent, complete extension of Peano arithmetic ..."

How do we know it's consistent? Isn't this just an assumption? ☺Coppertwig (talk) 10:41, 29 May 2011 (UTC)

No, it's consistent because it's the collection of all true statements about the naturals. The "assumption" involved, if you like, is that there's such a thing as the naturals. --Trovatore (talk) 19:48, 29 May 2011 (UTC)

The "ssumption" is that the collection of all true statements about the naturals is consistent. I think mathematicians have tried and failed to prove this. In most articles I suppose we could assume it, but in this article I think we have to be more careful. I'm not sure whether that's the same thing as there being such a thing as the naturals. ☺Coppertwig (talk) 21:07, 11 June 2011 (UTC)

Truth, obviously, is consistent. I don't think that's an assumption. If there is a set of naturals, then the set of all true statements about them is consistent; that's a logical truth, not part of mathematics. --Trovatore (talk) 22:51, 11 June 2011 (UTC)

Oh, I didn't notice that the statement involved true arithmetic being an extension of PA. Yes, that part of it is an assumption. You worded your question as "how do we know it's consistent?" when what you really should have asked is "how do we know it extends Peano arithmetic?". --Trovatore (talk) 01:31, 12 June 2011 (UTC)

It's the theory of true arithmetic. You're right that we can't prove the consistency of PA in theories weaker than PA - that's what the incompletness theorem says. But the consistency of PA is provable in many other theories (e.g. Gentzen's consistency proof, Dialectica interpretation), and in particular in ZFC one can construct the set of all sentences true in ${\displaystyle \mathbb {N} }$. — Carl (CBM · talk) 21:28, 11 June 2011 (UTC)

Ah, er, oh, OK.

But as for the first sentence I quoted: how is the existence of a program which can list all the axioms of a theory without listing non-axioms equivalent to the existence of a program which can list all the theorems of a theory without listing non-theorems? Sounds rather non-obvious to me. I think the article could use a few words of explanation: a couple of words giving some impression as to who proved this equivalence, and when, and how difficult it was to prove. Or if it is obvious, maybe something like "it can easily be shown that ..." I suppose equivalent means that if one is true, then the other must be true. ☺Coppertwig (talk) 19:54, 12 June 2011 (UTC)

It's not obvious; but one can write a program which lists all proofs, and then modify it to truncate each proof to the conclusion. — Arthur Rubin (talk) 20:54, 12 June 2011 (UTC)

O'Connor thesis

• Incompleteness & Incompleteness: Completeness Formalizing Logic and Analysis in Type Theory

This looks pretty good. It has a bunch of discussion of the formalized proof that we already cite. 67.117.147.144 (talk) 06:41, 1 June 2011 (UTC)

It may look good, but there is little apparent relationship between the thesis and the Gödel's incompleteness theorems in classical logic, which Gödel himself used. — Arthur Rubin (talk) 07:33, 1 June 2011 (UTC)

Controversy concerning Wittgenstein vs. Gödel on the incompleteness theorem has spread further

The controversy on Wittgenstein vs. Gödel has spread further. Evidently, someone told Hewitt about the activities of clasical logicians on this site and he commented here.

Previously at Stanford, they published a video here (with slides) on the controversy in which Feferman and others participated.Untalker (talk) 17:53, 19 June 2011 (UTC)

• All unassessed articles
• Unassessed mathematics articles
• Top-priority mathematics articles
• B-Class Philosophy articles
• Mid-importance Philosophy articles
• B-Class epistemology articles
• Mid-importance epistemology articles
• Epistemology task force articles
• B-Class logic articles
• Mid-importance logic articles
• Logic task force articles
• Delisted good articles