Jump to content

Talk:Gödel's incompleteness theorems/Archive 8

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
Archive 5Archive 6Archive 7Archive 8Archive 9Archive 10Archive 11

"Incompleteness theorems" redirects here?

The topic incompleteness theorems currently redirects to this article, which, unfortunately is missing a large part of the story. How can this be remedied? 68.65.169.201 (talk) 21:57, 12 April 2010 (UTC)

That depends greatly on exactly which material you're concerned about. — Carl (CBM · talk) 00:56, 13 April 2010 (UTC)
There would seem to be several considerations:
  • assumptions used in incompleteness proofs
  • whether incompleteness entails inconsistency
  • role of metatheory in proofs of incompleteness
  • etc.
64.9.240.145 (talk) 03:02, 14 April 2010 (UTC)
Could you explain what you have in mind for the third one? The article certainly already discusses the assumptions of the theorems, and the answer to "does incompleteness entail inconsistency" is "no", since the whole point of the theorems is that consistent theories with certain properties must be incomplete. — Carl (CBM · talk) 03:06, 14 April 2010 (UTC)
It's as those you have never heard of the work of Wittgenstein, Routely, Priest, etc. I know that Wikipedia hates Hewitt, but Incompletness Theorems has a concise overview. What do you think?68.65.169.149 (talk) 23:57, 15 April 2010 (UTC)
I don't believe it's accurate to say anyone here hates Hewitt. I have always advocated including, not removing, a link to his paper on paraconsistent logic. Recently, some collection of West-coast IP addresses added a very poorly written "proof sketch" to the article, which anyone could tell was not going to fit in. But the reference to Hewitt's paper is still in the article as I write this.
I do think this article could use a "history" section, which could mention Wittgenstein's remarks and the near-universal opinion that they are not of the same acuteness as Wittgenstein's other writings. I recently looked at the new book An Introduction to Goedel's theorems by Peter Smith, the philosopher at Cambridge. This is a 360pp book on the theorems that is quite comprehensive; I was unable to find a mention of Wittgenstein in it. In mathematical logic references, Wittgenstein is essentially never mentioned. So Wikipedia is far from the only place that does not emphasize Wittgenstein in its coverage of the incompleteness theorems. — Carl (CBM · talk) 03:12, 16 April 2010 (UTC)

There are two prominent points of view on the matter:

  • In the box: The traditional one of Hilbert, Gödel, Peter Smith etc.
  • Out of the box: Starting with Wittgenstein [1930] through his later writings along with Routley, Priest, etc.

You are firmly stuck in the POV "in the box" and completely deny the existence of the POV "out of the box."17.244.70.121 (talk) 15:55, 16 April 2010 (UTC)

From time to time I ask myself whether the article really covers enough. I didn't write most of it, although I fixed some issues. But when I actually look at what's in the article, it seems pretty reasonable for a general-level encyclopedia article. I can think of some topics that could be covered in more depth (e.g. inexhaustibility and formalization), and the "discussion" section could use work, but all the major topics are included in the article as it stands. — Carl (CBM · talk) 03:28, 14 April 2010 (UTC)

It may not be such a terrible article on "Gödel's incompleteness theorems" with the emphasis on Gödel. But current article is not adequate for the topic of Incompleteness theorems in general.68.65.169.149 (talk) 00:06, 16 April 2010 (UTC)
Could you point me to an printed reference for "incompleteness theorems" in general? I can think of Smullyan's book on self-reference as one possibility, but I doubt that that is what you have in mind. — Carl (CBM · talk) 03:12, 16 April 2010 (UTC)
You might try reading the following from Wittgenstein's Philosophy of Mathematics,
After the initial, scathing reviews of RFM [Remarks on the Foundations of Mathematics], very little attention was paid to Wittgenstein's (RFM App. III) and (RFM VII, §§21-22) discussions of Gödel's First Incompleteness Theorem (Klenk 1976, 13) until Shanker's sympathetic (1988b). In the last 11 years, however, commentators and critics have offered various interpretations of Wittgenstein's remarks on Gödel, some being largely sympathetic (Floyd 1995, 2001) and others offering a more mixed appraisal [(Rodych 1999a, 2002, 2003), (Steiner 2001), (Priest 2004)]. Recently, and perhaps most interestingly, (Floyd & Putnam 2000) and (Steiner 2001) have evoked new and interesting discussions of Wittgenstein's ruminations on undecidability, mathematical truth, and Gödel's First Incompleteness Theorem [(Rodych 2003, 2006), (Bays 2004), (Sayward 2005), and (Floyd & Putnam 2006)].
In addition there are many other published papers on the POV "out of the box."17.244.70.121 (talk) 15:55, 16 April 2010 (UTC)

Also see April 23, 2010: Carl Hewitt: Wittgenstein versus Gödel on the Foundations of Logic (Cordura 100 from 12:00 to 1:30:

This talk (in four parts) explains how some of the writings of Ludwig Wittgenstein can be interpreted as precursors of important developments in the foundations of mathematical logic for information systems applications. Wittgenstein's writings stand in almost exact opposition to the views of Kurt Gödel.
  • FIRST PART: The current state of foundations of mathematical logic for information systems applications is overviewed with regard to issues of expressiblity, incompleteness, and inconsistency tolerance.
  • SECOND PART: The above developments have precursors in writings of Wittgenstein.
  • THIRD PART: The above views are contrasted with the almost opposite ones of Gödel.
  • FOURTH PART: How do the above views provide framework and guidance for the further development of logic for information systems applications?
FURTHER READING: Common sense for concurrency and inconsistency tolerance using Direct Logic ArXiv:0812.4852

17.244.70.121 (talk) 15:55, 16 April 2010 (UTC)

Above material mysteriously disappeared. But I found a way to bring it back so I could comment that the following quotes by Wittgenstein are relevant:

  • Let us suppose I prove the unprovability (in Russell'ssystem) of P [where P is the Gödel sentence of the system], then by this proof I have proved P. Now if this proof were one in Russell's system-I should in this case have proved at once that it belonged and did not belong to Russell's system.-That is what comes of making up such sentences. But there is a contradiction here!-Well, then there is a contradiction here. Does it do any harm here?
  • Indeed, even at this stage, I predict a time when there will be mathematical investigations of calculi containing contradictions, and people will actually be proud of having emancipated themselves from consistency.

Necessary elements for a Goedelian incompleteness proof

This addresses both questions (1) and (2):

N.B. This is in no way intending to address incompleteness proofs in paraconsistent logic. This has to do with Goedelian inconsistency proofs as framed in the logic derived from Principia Mathematica.

With respect to the necessary elements required before incompleteness can be demonstrated for a "Goedelian system", Goedel listed 5 criteria:

  • (1) The "target system" (as opposed to the metamathematical framework around the target system) is "formal" [in the modern syntactic sense of generating well-formed strings by concatenation of symbols using finite and fixed-at-the-outset formation rules], in particular the notion of "provability" is defined. This system is to be constructive ["... a rule's being constructive, that is, of there existing a "finite procedure" for carring out the rule" cf Davis's commentary in his The Undecidable 1965:39]. With the exception of constructive he defines the notion of formal system elegantly in two paragraphs at the outset of his 1934 Princeton lectures (cf Martin Davis 1965:41 and 61-62). To satisfy the notion of constructive he offers us his [primitive] recursion. Note in particular Goedel specifies a "proof" and "provable" as wholly-mechanical operation(s) in his formal system, and this notion has no roots in "truth" or "falsity" (i.e. a semantic notion from outside the formal system).
  • (2) The formal system permits forming the positive integers into "meaningful formulas zn" for the positive integers, i.e. expressions such as the Goedelization from his 1934 (this is different than his 1931, here the star represents arithmetic multiplication. At this point the "formula" has passed from a concatenation of symbols to its encoding into a number):
0 => 1, 1 => N(0) => 22*312*51*713, 2 => N(N(0)) => 22*312*52*712*111*1313*1713, . . .
  • (3) The formal system contains the symbol ~ (NOT) and two symbols v and w for variables, such that the relation with their numerals (defined in (2) i.e. for v => zp and w => zq and R(zp, zq)) is provable if the relation R(v, w) is provable, and that the relation ~R(zp, zq) is provable when the relation of R(v, w) is not provable.
  • (4) The formal system contains the symbol Π with its significance to be the logical product of the form ΠxF(x)( i.e. for for all positive integers x, x satisfies F(x) ). If this is provable then the formula F(zk) must be provable for all positive integers k (here again zk is the numeral that represents the positive integer k).
  • (5) The formal system is "free of contradiction" [i.e. it is either hypothesized to be both simply- and omega-consistent, or shown to be free of contradiction by metamathematical arguments from outside the formal system]-- he defines this in terms of both the expressions in (3) (simple consistency) and (4) (omega-consistency).

Later he goes on to state the well-known observation that "There is no algorithm for deciding relations in which both + and x occur." This derives from his proof that "There exists no formalized theory that answers all Diophatine questions of the form (P)[F=0)". (cf pages 69 and 72 in Davis: 1965).

I haven't thought through what a minimal formal system would look like that satisfies the above 5 stipulations. Clearly it needs at least a few symbols: 0, s (successor), ~, Π, x, y. This seems close to the minimal symbol- and instruction- set that a register machine would embody: 0, increment x, jump-if-equal x, y, jump-if-not-equal x, y; x is a register, y is a register. There must be someone out there who's noodled this out in detail. (emended and demarcated) BillWvbailey (talk) 21:04, 21 April 2010 (UTC)

"Incompleteness theorems" redirects here? PART II

You are stuck hacking in the weeds. All you need is roundtripping.17.244.70.121 (talk) 15:55, 16 April 2010 (UTC)
For those who are unfamiliar, roundtripping proposition P is that ⌊⌈P⌉⌋ ⇔ P, i.e. P is logically equivalent to abstraction of reification of P.98.210.236.39 (talk) 12:58, 17 April 2010 (UTC)


It seems tht it is Arthur Rubin who has been deleting material from this discussion.99.29.247.230 (talk) 20:53, 17 April 2010 (UTC)

General reply: The only place that seems to mention any of this is Hewitt's work. None of the main references on Goedel's theorems gives weight to Wittgenstein, paraconsistent logic, or "roundtripping". Hewitt is doing the right thing by making his argument in seminars and papers. Once people are convinced enough that the overall literature changes to reflect these things, then this article should be changed. In the meantime, continuing to raise the same points is not productive, so I will bow out at this point from addressing them if they are raised again. — Carl (CBM · talk) 03:51, 18 April 2010 (UTC)

Hewitt was by no means the first to give respectful consideration of Wittgenstein's work on incompleteness and the consequence of inconsistency. There is an extensive published literature going back many years continuing to the present time. See the following (among others):
  • Richard Routley. “Dialectical Logic, Semantics and Metamathematics” Erkenntnis 14. 1979.
  • Stuart Shanker. “Wittgenstein's Remarks on the Significance of Gödel's Theorem,” in Gödel's Theorem in Focus 1988.
  • Steve Gerrard. "Wittgenstein's Philosophies of Mathematics" Synthese 87. 1991.
  • Victor Rodych. "Wittgenstein on Mathematical Meaningfulness, Decidability, and Application" Notre Dame Journal on Formal Logic Vol. 38. No. 2. 1997.
  • Victor Rodych. "Wittgenstein's Inversion of Gödel's Theorem" Erkenntnis 51. 1999.
  • Juliet Floyd, “Prose versus Proof: Wittgenstein on Gödel, Tarski and Truth” Philosophia Mathematica Vol. 3. No. 9. 2001.
  • Victor Rodych. "Wittgenstein on Gödel: The Newly Published Remarks" Erkenntnis 56. 2002.
  • Victor Rodych. "Misunderstanding Gödel: New Arguments about Wittgenstein and New Remarks by Wittgenstein" Dialectica Vol. 57. No. 3. 2003.
  • Graham Priest. “Wittgenstein’s Remarks on Gödel's Theorem” in Wittgenstein's Lasting Significance Routledge. 2004.
  • Timothy Bays, “On Floyd and Putnam on Wittgenstein on Gödel" The Journal of Philosophy CI,4. 2004.
  • Graham Priest. In Contradiction: Second Edition Clarendon Press. 2006.
  • Robert Hadley. "Consistency, Turing Computablity and Gödel's First Incompleteness Theorem" Minds and Machines 18. 2008.
  • Juliet Floyd and Hilary Putnam. "Wittgenstein’s ‘Notorious’ Paragraph About the Gödel Theorem: Recent Discussions" ("Wittgenstein's ‚berüchtigter’ Paragraph über das Gödel-Theorem: Neuere Diskussionen") in Prosa oder Besweis? Wittgenstein's ›berüchtigte‹ Bemerkungen zu Gödel, Texte und Dokumente Parerga Verlag. 2008.
  • Francesco Berto. "The Gödel Paradox and Wittgenstein's Reasons" Philosophia Mathematica 17. 2009.

98.210.236.39 (talk) 12:40, 18 April 2010 (UTC)

... and I thought "roundtripping" was Likebox's invention. I knew it was someone's invention, not generally accepted. — Arthur Rubin (talk) 06:31, 18 April 2010 (UTC)
Of course, roundtripping is just a variant of the T-scheme that is well known to be able to be used to derive an inconsistency from the Gödelian sentence (see [Graham Priest. In Contradiction: A Study of the Tranconsistent 2006]).98.210.236.39 (talk) 13:10, 18 April 2010 (UTC)


Responding to the IP: yes, I know. However, at the moment the discussion seems to be limited to the study of Wittgenstein, rather than to the study of the incompleteness theorems. That is, the discussion is in literature about Wittgenstein, and what he might have said, rather in literature whose main purpose is to describe the incompleteness theorem.
Now the people who are studying Wittgenstein are trying to make sense of his comments, but at the moment there is nothing like agreement in the literature. The papers I have looked at are all very tentative ("this is one possible way to read Wittgenstein that might make sense"). For another viewpoint see "Wittgenstein as his Own Worst Enemy: The Case of Gödel's Theorem", Mark Steiner, Philosophia Mathematica 2001.
However, this Wikipedia article is not the place to cover the detailed analysis of Wittgenstein, particularly when all the references about the incompleteness theorem (even new ones such as Smith 2009) don't seem to find Wittgenstein's comments important. The only motivation I see for the interest here in Wittgenstein is that Hewitt interprets Wittgenstein's remarks as supporting the use of paraconsistent logic; but we do not need to go into depth explaining the motivations for Hewitt's work in this article. The incompleteness theorems are extremely well understood with or without Wittgenstein, and they are fundamentally about first-order logic, not paraconsistent logic.
In the language of "in the box" and "out of the box", this article is very much "in the box" of the existing literature, and that is where it is intended to be. This is not a criticism of Hewitt's work, which I find interesting, nor a criticism of Wittgenstein scholarship, which I find more interesting. It is simply a reflection of the goal of this article, which is to summarize the incompleteness theorems as they are usually understood. — Carl (CBM · talk) 13:22, 18 April 2010 (UTC)
In hopes of moving things forward,I will ask a specific question: please give a concrete, specific change that you would like to see in the article. General discussion of Wittgenstein is fine and good but doesn't directly translate into editing. What about this article would you like to change? Where in the article should the change go? — Carl (CBM · talk) 13:29, 18 April 2010 (UTC)

Start a new article on "Incompleteness and Inconsistency Theorems"?

One way to proceed would to be start a new article on Incompleteness theorems that would cover both major points of view:

  1. Consistency Required initiated with Gödel
  2. Inconsistency Tolerant initiated with Wittgenstein at about the same time

Both of above have large published literatures. But they differ radically in their technical results.17.244.70.121 (talk) 04:02, 19 April 2010 (UTC)

I can't find anyone, even Hewitt, who thinks that Wittgenstein's comments are sufficiently well-defined to provide the basis of a theory. Perhaps Hewitt's work on paraconsistent theories is accepted as a modern approach, but we would need evidence that it's appropriate. And, since Hewitt and his students have been inserting Hewitt's approach on articles where it is not accepted or relevant, this would be difficult to verify that the sources are acceptable. — Arthur Rubin (talk) 06:03, 19 April 2010 (UTC)
No, we do not need a different article. There is no large published literature on "inconsistency tolerant" theories, just a large literature on Wittgenstein's interpretation of Goedel's theorem and a literature on paraconsistent logic, neither of which is about "incompleteness theorems". I keep asking for research literature on "incompleteness theorems" in general, but instead I am just presented with Wittgenstein scholarship. So I'll ask again: where can I actually find these "radically different technical results" (and I do not count philosophical discussion of Wittgenstein as a technical result)? For example, I did a quick scan through the table of contents of Priest's book, and his article on the SEP, and the only "incompleteness theorem" they seem to contain is Goedel's. Can you actually state one of these "radically different incompleteness theorems" that is not just a reworking of Goedel's theorem, along with a reference for its publication? — Carl (CBM · talk) 11:35, 19 April 2010 (UTC)
It starts with a proposition P in a theory T that states "P is not provable in T" After that the controversies begin! For example,
  • Does logical undecidability of P entail that T is inconsistent? Gödel said "No" (hopefully). Wittgenstein said "Yes" (happily), thereby offending Gödel.
  • Does proving the logical undeciability of P involve the use of "metatheories"? Gödel said "Yes" (following Tarski). Wittgenstein said "No" (theories about theories are just like theories about chess), which offended Gödel even more.
  • Gödel's proof of incompleteness used proof by contradiction. But now we have inconsistency tolerant proofs of incompleteness that do not rely on the assumption of consistency.
Of course in an article about Incompleteness theorems, the main subject matter is the theorems and mathemacal apparatus. Gödel and Wittgenstein appear at the end in the history section.17.244.70.121 (talk) 19:59, 19 April 2010 (UTC)
I am asking for a particular "incompleteness theorem" that the article might cover, other than Goedel's incompleteness theorem, along with a reference for it in the literature. I am not asking about Wittgenstein's interpretation of Goedel's theorem. If, as you say, the main topic would be the theorems, then we need to start by identifying what theorems those actually are. — Carl (CBM · talk) 20:16, 19 April 2010 (UTC)
Also, talk of "controversies" is overblown. There is no controversy about "Does logical undecidability of P entail that T is inconsistent?" – in the context of first-order logic, everyone agrees on the answer, while in the context of paraconsistent logic the answer may be different. This is no more controversy about this than about the question whether "every function from the real line to the set {0,1} is constant". — Carl (CBM · talk) 20:30, 19 April 2010 (UTC)

First-order logic is incredibly improverished--can't even axiomatize the continuum, etc. (See Common sense for concurrency and inconsistency tolerance using Direct Logic and the Actor Model) Wittgensten wrote about incompleteness for Principia Mathematica (as did Gödel's original paper) whose aim was to provide foundations for all of mathematics. Gödel had a horror of inconsistency--so he badmouthed Wittgenstein on a personal basis and refused to address the issues. 171.66.85.59 (talk) 00:55, 20 April 2010 (UTC)

Perhaps, but this evades my question. You are advocating a new article on incompleteness theorems other than Goedel's, but decline to state any theorem that might be covered by that article. Instead you are continue to write about historical issues with Wittgenstein, and then about paraconsistency, and then again cite Hewitt's work. It appears the main motivation for all this is to add additional material on Hewitt's work – which would not be appropriate for this article, although an appropriate reference to Hewitt's work is already included. As I pointed out above, even Graham Priest's writings about paraconsistency seem to deal only with Goedel's incompleteness theorem, not with "incompleteness theorems" in general. — Carl (CBM · talk) 03:50, 20 April 2010 (UTC)

Gödel thought that the incompleteness theorems (apart from Rosser's minor extension) were basically his property. Never mind Wittgenstein with his rejection of "meta-theories" so that incompleteness leads straight to inconsistency via a proof other than Gödel's! In addition to the publications already mentioned, you can find incompleteness theorems in the following and their references:

  • Richard Routley “Dialectical Logic, Semantics and Metamathematics” Erkenntnis 14. 1979.
  • Graham Priest "In Contradiction" Oxford University Press. 2006
  • Stewart Shapiro. "Incompleteness and Inconsistency" Mind. 111. 2002.
  • Priest, Beall, and Armour-Garbs (eds). "The Law of Non-Contradiction: new philosophical essays" Oxford University Press. 2004.

98.210.236.39 (talk) 13:28, 20 April 2010 (UTC)

Please give a concrete, page number reference to an incompleteness theorem other than Goedel's theorem in Priest's In contradiction. Thanks, — Carl (CBM · talk) 13:32, 20 April 2010 (UTC)
Let's turn to Shapiro's article, which is on JSTOR [1]. It isn't about incompleteness. On one hand, Shapiro's own conclusion (page 831) is phrased in terms of the unsoundness, not incompleteness, of a particular formal system PA*. This seems to be necessary: Shapiro does not establish that any system is incomplete. What he shows is that PA* proves both a Goedel-type sentence and the negation of that Goedel-type sentence. An "incomplete" system is one that has a formula φ such that neither φ nor the negation of φ is provable. Showing that both φ and its negation are provable does not demonstrate "incompleteness", it only demonstrates inconsistency.
Maybe the new article should be called "Incompleteness and Inconsistency Theorems"  ;-) 17.244.70.121 (talk) 16:14, 20 April 2010 (UTC)
On the other hand, Shapiro appears to have priority over Hewitt for formalizing the proof of Goedel's theorem into paraconsistent logic to show that certain theories of arithmetic are necessarily inconsistent. I would need to read more to see if this was known to Priest already in 2001. — Carl (CBM · talk) 13:53, 20 April 2010 (UTC)
Try Routley [1979] 17.244.70.121 (talk) 16:19, 20 April 2010 (UTC)

I added a paragraph on dialethism to the discussions section. — Carl (CBM · talk) 14:24, 20 April 2010 (UTC)

stacked metalanguages

From "discussion and implications", this paragraph looks bogus:

There are some who hold that a statement that is unprovable within a deductive system may be quite provable in a metalanguage. And what cannot be proven in that metalanguage can likely be proven in a meta-metalanguage, recursively, ad infinitum, in principle. By invoking such a system of typed metalanguages, along with an axiom of Reducibility — which by an inductive assumption applies to the entire stack of languages — one may, for all practical purposes, overcome the obstacle of incompleteness.

Should something be done about it? 69.228.170.24 (talk) 06:56, 24 April 2010 (UTC)

I can only guess at that that is trying to say. I'll remove it for now, and we can add it back if we figure out how to rewrite it. In the past, when I have proofread the article, I have been much lighter on the "discussion" section than the preceding parts; it has a lot of problems like this one. — Carl (CBM · talk) 11:39, 24 April 2010 (UTC)
I removed that paragraph, along with a lot of other text that seemed to just repeat stuff that already occurs higher in the article. That leaves a short and choppy section. We should think about what discussion should go into this section. — Carl (CBM · talk) 11:44, 24 April 2010 (UTC)
I think some of the stuff Bill has written in the history draft above, about Gödel's view of mind and mechanism, could go in the discussion section. Torkel Franzén's book about the incompleteness theorem is also a good place to look for ideas, since it discusses what kinds of questions people ask all the time. 69.228.170.24 (talk) 13:25, 24 April 2010 (UTC)
We have a long article Axiom of reducibility (it is from Principia Mathematica) which doesn't have any obvious bearing on the removed paragraph. There's a concept of autonomous progressions of theories that I'm sure you (fixed error:) understand much better than I do, and I wondered if the paragraph had something to do with that. This article on that subject looks good (a little too advanced for me though) and maybe we can use it in some way, under "generalizations of the incompleteness theorem". I guess you referred to Franzén's related book "Inexhaustibility" further up. The book and article are both reviewed here. 69.228.170.24 (talk) 08:44, 26 April 2010 (UTC)

Wittgenstein versus Gödel

Wittgenstein on Incompleteness and Inconsistency

  • Indeed, even at this stage, I predict a time when there will be mathematical investigations of calculi containing contradictions, and people will actually be proud of having emancipated themselves from consistency.
  • There can’t in any fundamental sense be such a thing as meta-mathematics. . . . Thus, it isn’t enough to say that p is provable, what we must say is: provable according to a particular system.
  • “true in PM [Principia Mathematica]” is identical with, and therefore can be supplanted by,“proved in PM.”
  • Let us suppose I prove the unprovability (in Russell’s system [Principia Mathematica]) of P; then by this proof I have proved P. Now if this proof were one in Russell’s system—I should in this case have proved at once that it belonged and did not belong to Russell’s system.—That is what comes of making up such sentences. But there is a contradiction here!—Well, then there is a contradiction here. Does it do any harm here?
  • Can we say: ‘Contradiction is harmless if it can be sealed off’? But what prevents us from sealing it off?
  • Let us imagine having been taught Frege’s calculus, contradiction and all. But the contradiction is not presented as a disease. It is, rather, an accepted part of the calculus, and we calculate with it.
  • For might we not possibly have wanted to produce a contradiction? Have said-with pride in a mathematical discovery: “Look, this is how we produce a contradiction."

Since Principia Mathematica (PM) aims to be the foundation of all of mathematics, it proves incompleteness of PM. Consequently, as Wittgenstein noted, PM is therefore inconsistent. But this is OK because the inconsistency can be sealed off.

Gödel on Wittgenstein

  • It is clear from the passages you [Carl Menger] cite that Wittgenstein did “not” understand it [1st incompleteness theorem] (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite, namely a mathematical theorem within an absolutely uncontroversial part of mathematics (finitary number theory or combinatorics).

It seems that Gödel has made an (unannounced) shift away from PM where Wittgenstein grounded his argument. Does this mean that he is pretending not to understand Wittgenstein?

  • He [Wittgenstein] 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.

Gödel doubted that it would be possible to develop a logic in which "you can’t derive everything from a contradiction.” 17.244.70.240 (talk) 01:26, 27 April 2010 (UTC)

Gödel's theorem doesn't prove ¬Prov(G) in PM. It instead proves (Con(PM) => ¬Prov(G)). Since Con(PM) is itself not a theorem of PM, there is no inconsistency. I think I got that right. It is a pretty basic confusion that almost everyone trips over when they get started. That Gödel understood this clearly when everyone else didn't is why they paid him the big bucks, or something like that. 69.228.170.24 (talk) 02:07, 27 April 2010 (UTC)
It's Wittgenstein who wrote: PM proves that the Gödelian proposition for PM is not provable in PM.17.244.70.240 (talk) 02:26, 27 April 2010 (UTC)
But of course PM does not in fact prove that. --Trovatore (talk) 02:44, 27 April 2010 (UTC)
Yes, this was indeed the bone of contention between Wittgenstein and Gödel. Of course, you are are aware that there are logics in which each theory self-proves that its own Gödelian propositon is unprovable in the theory.63.249.91.253 (talk) 04:31, 27 April 2010 (UTC)
PM does not prove the fact. Period. Now, sure, if you diddle the logic, you can make it do anything. But then this is no longer the correct notion of proof. --Trovatore (talk) 04:39, 27 April 2010 (UTC)
As Trovatore is saying, PM is (as far as anyone knows) consistent. If you change the logic, you arrive at something that is no longer Principia Mathematica.
Moreover, pretty much all discussion of PM is anachronistic. As early as his 1934 Princeton lectures, Goedel had replaced PM in his proofs with the usual effectiveness conditions (he had alluded to this possibility in the original paper). The incompleteness theorems have nothing much to do with PM, apart from the fact that PM is one of the theories that meets their hypotheses. The mention of PM in the original paper is just a historical footnote. — Carl (CBM · talk) 11:14, 27 April 2010 (UTC)
Correct. Goedel listed PM and "set theory" even in his 1931 (first page, first paragraph). Even before his 1934 Princeton lectures, in his 1931a "Postscript" (Collected Works Vol. I:203-205, with commentary by Dawson on pages 196-199) that he wrote for the journal Erkenntnis, he lists those formal systems that were known at the time [Post/Turing machines and lambda-calculus coming 5-6 years later] -- "in all the well-known formal systems of mathematics -- for example Principia mathematica (together with the axioms of reducibility, choice and infinity), the Zermelo-Fraenkel and von Neumann axiom systems for set theory, and the formal systems of Hilbert's school--there are undecidable arithmetical propositions." Whether Wittgenstein didn't read the literature, or chose to ignore it, is unknown, but the evidence points to Wittgenstein's philosophy that is very close to the argument that Plato had with Euthydemus over the notion of; see contradiction for a piece of the dialog. There is some useful commentary about the philosophic differences that infused the (one-sided) debate in Goldstein 2005:188-205 including a funny footnote about Wittgenstein's attempts (in 1939 he was a lecturer at Cambridge at the same time as Turing was also lecturing) to recruit Turing to the dark side: "When Wittgenstein remained adamant that a contradiction in a system was no cause for concern, since everything reduced ultimately to the arbitrariness of language-games, Turing stopped attending the lectures. Soon after this, Turing produced his metamathematical proof [Systems of Logic Based on Ordinals]." (footnote 10 page 196 in Goldstein; for an expanded discussion of W. and Turing, with a transcript of Turing arguing with W. about this very point see Hodges 1983:153-154 and the footnote #39 p. 547-8). BillWvbailey (talk) 16:26, 27 April 2010 (UTC)
As Rodych explains on the SEP [2], at least some of Wittgenstein's remarks on the incompleteness theorems appear to be have been written before Wittgenstein had actually read Goedel's full paper. Other remarks remained unpublished until Wittgenstein's Nachlass was released in 1998. It also seems that Wittgenstein, like Zermelo, had prior philosophical commitments that were difficult to reconcile with the incompleteness theorems. — Carl (CBM · talk) 16:53, 27 April 2010 (UTC)

According to Common sense for concurrency and inconsistency tolerance using Direct Logic(TM) and the Actor Model:

Wittgenstein (ca. 1939) said “No one has ever yet got into trouble from a contradiction in logic.” to which Alan Turing responded “The real harm will not come in unless there is an application, in which case a bridge may fall down.”[Holt 2006] It seems that we may now have arrived at the remarkable circumstance that we can’t keep our systems from crashing without allowing contradictions into our logic.71.198.220.76 (talk) 18:26, 27 April 2010 (UTC)
Wittgenstein did not accept the "metatheories" that Gödel needed as a work around to avoid inconsistency. Consequently, inconsistency could be derived from the Gödelian proposition for Principia Mathematica independent of the details of Gödel's paper.71.198.220.76 (talk) 18:31, 27 April 2010 (UTC)
I have no idea what you (or Wittgenstein?) could mean by "accept" there. For example, one can avoid C* algebras by working in a different area of mathematics, but one cannot decide that C* algebras simply do not exist based on a personal dislike of functional analysis. Similarly, regardless of Wittgenstein's affinity for metatheories, there is no way to make them pop out of existence. — Carl (CBM · talk) 20:32, 27 April 2010 (UTC)

Wittgenstein wrote that proving theorems about theories is just like proving theorems about chess. Therefore "metatheories" are nonsense ;-) 63.249.99.129 (talk) 20:56, 27 April 2010 (UTC)

Principia Mathematica (PM) was important in the context in which Wittgenstein worked in the early 1930's because PM was the "top dog" theory that was supposed to be a foundation for all of mathematics. Thus Incompleteness must be a theorem in PM. Gödel probably realized that this leads immediately to inconsistency and so needed a work around. Hence the backtracking.98.210.236.39 (talk) 17:12, 27 April 2010 (UTC)

Actually, Goedel apparently realized what is actually true: that if PM is consistent, it does not prove its own consistency. Nothing in Goedel's theorem establishes that PM is inconsistent, although it does show that there is no single consistent theory meeting the hypotheses of the incompleteness theorems that can prove every mathematical truth. — Carl (CBM · talk) 20:32, 27 April 2010 (UTC)
Wittgenstein wrote that it is just about proving theorems. This is why he wrote that "true" in Principia Mathematica (PM) just means "proveable" in PM. It looks like you have been drinking Gödel's Platonic kool-aid and liking it :-) 63.249.99.129 (talk) 20:56, 27 April 2010 (UTC)

Summary of controversy

The controversy between Wittgenstein can be summarized as follows:

  • Gödel
  1. Objective truth is the basis of mathematics
  2. Incompleteness can be proved using roundtripping but (hopefully) inconsistency does not follow
  3. Consistency should be proved for each theory
  • Wittgenstein
  1. Communities of practice are the basis of mathematics
  2. Inconsistency follows from proof of incompleteness
  3. Inconsistency tolerant reasoning should be used for theories

98.210.236.39 (talk) 12:32, 29 April 2010 (UTC)

Internet information reasoning

The following sentence keeps disappearing:

Direct Logic [ Hewitt 2008, 2009] is a powerful logic for reasoning about inconsistent Interent information systems in which every theory can prove its own incompleteness and consequently is inconsistent.

It is more accurate than what was there before which incorrectlly labeled it "Dialethism."17.226.15.239 (talk) 21:40, 29 April 2010 (UTC)

Yes; it is not appropriate for this article to include a section specifically on Direct Logic. The reference to Hewitt's paper is already more than adequate given the lack of any coverage of Direct Logic or even paraconsistent logic in the reference literature on the incompleteness theorems. — Carl (CBM · talk) 21:48, 29 April 2010 (UTC)

I improved the paragraph:

Direct Logic [ Hewitt 2008, 2009] is a powerful logic for reasoning about inconsistent Interent information systems in which every theory can prove its own incompleteness and consequently is inconsistent. This branch of computer science differs from dialethism (above) in that incompleteness and inconsistency are proved entirely proof theoretically without recourse to a "truth predicate" and so harks back to earlier work by Wittgenstein. The aim instead is to reason about Internet information with millions of inconsistencies although only a small fraction of the inconsistencies have been identified.68.65.169.140 (talk) 23:49, 29 April 2010 (UTC)
The quality of the writing is not important. The existence of the paragraph is undue weight to give to a fringe interpretation. It has to go. --Trovatore (talk) 23:53, 29 April 2010 (UTC)
I removed it. 69.228.170.24 (talk) 00:44, 30 April 2010 (UTC)
68.65.169.180 restored it[3] so I removed it again. 68.65.169.180, please stop edit warring. I will request ANI intervention if the material is re-inserted (in any form) without consensus. 69.228.170.24 (talk) 01:09, 30 April 2010 (UTC)
I restored CBM's version. 69.228.170.24 (talk) 01:24, 30 April 2010 (UTC)

---

Isn't there another home for this paragraph, such as Direct logic, or Paraconsistent logic, or Carl Hewitt or Dialethism or Wittgenstein, or some combination of these? On this talk page some of us are struggling with how to best present Goedel's incompleteness theorems -- those found in the 1931 paper and 1934 lectures per Collected Works Vol. 1 -- to a general audience that may have little or no background in the topic. Do you honestly, in your heart of hearts, truly believe an inclusion of the above about Hewitt and Wittgenstein helps these folks understand Goedel's theorems (e.g. numbers I - XI in Goedel's 1931)? BillWvbailey (talk) 01:11, 30 April 2010 (UTC)
Please no new articles related to this; the last thing we need is more vanity articles. Self-promotion of this sort shouldn't go in any of the other articles either. There is already some mention of the topic at Carl Hewitt. 69.228.170.24 (talk) 01:24, 30 April 2010 (UTC)

I think that a one-sentence pointer to Hewitt's work is appropriate (just), but a paragraph is too much. Particularly if it focuses on "direct logic", a subject that is unknown in the mathematical logic literature. Our basic guides for what this article should focus on are Smorynski's article in the Handbook of mathematical logic, Franzen's book, Peter Smith's new book, and similar references that focus directly on the incompleteness theorems. Applications of the incompleteness theorems to computer science are already a marginal topic for this article; proposed applications using paraconsistent logic are even more so. There are quite a few things that should be added to the article in more detail, but Hewitt's work isn't among them.

Also, for the record, Wikipedia does not "hate" Hewitt. His problems here predated me, but the descriptions I have seen refer to excessive self-promotion with numerous IP addresses, which is not unlike the edits that have happened today. — Carl (CBM · talk) 02:02, 30 April 2010 (UTC)

Paraconsistency is a very weak form of inconsistency tolerant logic

Paraconsistency is a very weak form of inconsistency tolerant logic in which an inconsistency does not infer every proposition. For example, adding the rule that for all propositions p: 

            p,¬p⊢GreenCheese[Moon]

preserves paraconsistency because not all propositions are inferred from an inconsistency.17.244.70.240 (talk) 03:16, 30 April 2010 (UTC)

As far as I can tell, "inconsistency tolerant" is simply a synonym for "paraconsistent". Prove me wrong. — Carl (CBM · talk) 03:45, 30 April 2010 (UTC)
It's pretty simple: The rule above is clearly not inconsistency tolerant although it is paraconsistent because it does not prove every proposition from an inconsistency.98.210.236.39 (talk) 15:19, 30 April 2010 (UTC)

Wikipedia lunacy

Folks at Stanford must be laughing off their chairs. Also, why is the guy from Oakland so bitter?64.9.238.118 (talk) 01:59, 6 May 2010 (UTC)

The root cause is a long-running rivalry between Cal and Stanford. —Preceding unsigned comment added by 68.65.169.145 (talk) 01:44, 7 May 2010 (UTC)
I don't understand either of those comments. — Arthur Rubin (talk) 03:54, 7 May 2010 (UTC)

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?"[4] 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

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)

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.

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 ε0.”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:

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 [5], 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 [6].
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)

Sigfpe

Sigfpe has a nice blog post about provability logic:

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:

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 [7] 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 [1st incompleteness theorem] (or pretended not to understand it). He interpreted it as a kind of logical paradox, while in fact is just the opposite.
  • He [Wittgenstein] 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 [ John Dawson 2006 emphasis in original]:

  • "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 [ Common sense for concurrency and inconsistency robustness using Direct Logic(TM) and the Actor Mode ] 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." [Dawson 2006] 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 talk 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 talk 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 talk 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, GPA is true exactly in the case that PA cannot prove GPA. That's just how the construction works.
But then, assuming PA is consistent, PA really cannot prove GPA. Therefore GPA 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 GPA, 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 GPA 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 talk 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 talk 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 talk 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 (Wikipedia: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 talk 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 (Talk | email) 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 Wikipedia 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)

O'Connor thesis

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)

There is a whole conference at Stanford this summer challenging the view of the incompleteness theorem in this article -- see Inconsistency Robustness 2011.71.198.220.76 (talk) 06:26, 20 June 2011 (UTC)
Please note that article talk pages are intended only for discussing the article itself, not as a place to advertise things that have been posted elsewhere. Carl Hewitt is welcome to post whatever he likes on his own pages, of course. — Carl (CBM · talk) 18:42, 19 June 2011 (UTC)
Please note that you suppressed from this page the discussion of what the article should say about the controversy between Goedel and Wittgenstein over the incompleteness theorem, Now the controversy has showed up in other prominent sources that you do not want to be mentioned in the article. In fact, the reference to which you object above is actually a quotation by Professor Hewitt of material that was suppressed by you from this very page! Are you not abusing your power as an administrator since you are engaged in a controversy with Professor Hewitt?71.198.220.76 (talk) 20:49, 19 June 2011 (UTC)
Actually, CBM is not "anonymous", while "Untalker" and 71.198.220.76 are, unless they are Carl. That being said, I generally believe Feferman (misspelled) to be level-headed, so I would be interested in his opinion on whether there is a controversy. — Arthur Rubin (talk) 02:04, 20 June 2011 (UTC)

OK, I'm curious! What is the real name of CBM? 166.205.136.112 (talk) 02:48, 20 June 2011 (UTC)

None of your business, unless he chooses to release it. — Arthur Rubin (talk) 09:02, 20 June 2011 (UTC)
So, he is indeed anonymous? 64.134.237.72 (talk) 21:46, 20 June 2011 (UTC)
Please see WP:OUTING. If CBM hasn't chosen to make his identity known on his user page, you shouldn't be asking about it. —David Eppstein (talk) 23:09, 20 June 2011 (UTC)
I don't see really why one can't ask. Personally I don't really agree with WP:OUTING, partly because it requires us to use these coy formulas like "the students" when referring to our IP interlocutor. Anyway I don't think CBM's identity is any big secret, and I speculate that he took it off his user page primarily to avoid automated-web-search-type things. --Trovatore (talk) 23:12, 20 June 2011 (UTC)
How is knowledge of CBM's identity going to improve the article? Bill Wvbailey (talk) 01:31, 21 June 2011 (UTC)
Since he has taken such an active role in suppressing mention of Professor Hewitt's work on Wikipedia, people naturally worry about CBM's qualifications for censoring the article.75.18.229.230 (talk) 17:15, 21 June 2011 (UTC)
Qualifications and credentials are irrelevant here. What matters is the quality and reliability of your sources. —David Eppstein (talk) 17:39, 21 June 2011 (UTC)
Quality and reliability of sources are subject to judgment. And the judgments of CBM have been called into question.71.198.220.76 (talk) 19:32, 21 June 2011 (UTC)

Amazement

Let me just say that this is amazing. There is an old joke that behavioral psychologists often have unruly dogs. Are logicians at times prone to highly illogical behavior? I would like to advise everyone involved here, and all the other distributed bickering devices, to be more logical. Is this a new invention called "cloud bickering'?

In general, I should say that I have, for long, seen the edits of user:CBM across many pages and he has been a real asset to Wikipedia.

Now, will all grown up logicians with PhDs here avoid acting like children please? Set a good example. There may be undergrads reading these pages and we do not want them to get influenced by the childish side of their professors.

Please use your efforts constructively and avoid personal issues. This type of bickering is really embarrassing to all mathematicians. Time to act like grown ups, please. History2007 (talk) 14:13, 3 July 2011 (UTC)

Gödelian Incompleteness from Chaitin’s Perspective

I recently posted a comment elsewhere about how much easier it is to understand incompleteness from Gregory Chaitin's viewpoint. Gödelian Incompleteness seems to leave you in the dark in terms of its ramifications; Chaitinian Incompleteness, by contrast, makes the concept of incompleteness almost intuitively obvious.

For pedagogic purposes, it might be a good idea to include a bit more of Chaitin’s perspective on incompleteness into this article. Unfortunately I do not have the expertise to this job properly; but no doubt many people here have. I know that this article is on Gödelian Incompleteness, but since many people will come here in order to gain an understanding of mathematical incompleteness, offering readers a taste of the Chaitinian view of this subject would be worthwhile.

Here is part of the comment I posted:

Gregory Chaitin’s Incompleteness Theorem

Gregory Chaitin proved a theorem similar to Gödel’s incompleteness theorems, and the framework of Chaitin’s version makes a lot more intuitive sense, I find. I don’t really understand the technicalities of these incompleteness theorems, but I do feel that Chaitin’s version is more enlightening.

Gödel’s incompleteness theorem says that, in any consistent axiomatic mathematical system, there will always be mathematical statements that can neither be proved true, nor proved false . That is, there will always be mathematical statements whose truth or falsity is undecidable – beyond the ability of the system’s axioms to determine.

However, Gödel never gives any sense of why this might be the case. Gödel does not even hint at the reason why the truth or falsity of some mathematical statements may within the grip of the axioms to determine, but other statements lie beyond the reach of the axioms.

Chaitin considers the algorithmic complexity of the axioms of mathematics. The algorithmic complexity of a string of data is defined as the shortest and most efficient program that can produce the string – ie, the most compressed representation of that data string.

I believe Chaitin showed that a given axiomatic mathematical system can only determine the truth or falsity of a mathematical statement if the algorithmic complexity of that statement is less than or equal to the algorithmic complexity of the set of axioms.

This makes more intuitive sense, and Chaitin’s theorem throws light on why there are mathematical statements that are not decidable: undecidable statements encode more information (algorithmic complexity) than do the axioms themselves; so the “spec” of the axioms is in effect insufficient to cover these mathematical statements of greater information content.

Chaitin says: if you have ten pounds of axioms, and a twenty-pound theorem, then that theorem cannot be derived from those axioms.

Another way I understand this is as follows: When you prove a given mathematical statement to be true with respect to the axioms of a mathematical system, what you are really saying is that this mathematical statement is in accord with the foundational axioms, and this mathematical statement expresses some (but perhaps not all) of the information encoded in the axioms. (And if you prove the mathematical statement false, then you are just saying that the mathematical statement contradicts your axioms – but in either case, you have a definite answer).

However, when a mathematical statement contains more information than is found in the foundational axioms, it’s as if the axioms do not have sufficient “authority” to “adjudicate” upon the truth or falsity of such mathematical statements. Drgao (talk) 01:18, 12 July 2011 (UTC)

Chaitin's theorem was already mentioned once in the article, and I just added a second mention to a different section. Chaitin's theorem is weaker than Goedel's theorem, though, because Chaitin's theorem requires an additional assumption that the theory is satisfied by the standard model. Also, Goedel's proof of the incompleteness theorem was completely constructive and explicitly shows what the unprovable sentence is - in this sense it does give a sense of why the incompleteness theorem is true. — Carl (CBM · talk) 01:32, 12 July 2011 (UTC)
I agree - and I do not really see a pedagogic benefit from Chaitin. But it may be worth mentioning that Goedel's, Chaitin's etc. are generally instances of the same type of fixed point argument. History2007 (talk) 03:14, 12 July 2011 (UTC)
Thanks for those replies. I did not realize that Chaitin's theorem is weaker than Gödel's. This perhaps makes what I suggested above inappropriate. Even so, I do find Gödel formulation harder to grasp intuitively. Admittedly I only understand this subject from a "popular science/math" level, but a Wiki article should cater for that layman level to a degree, even in an area as subtle as this. The thing that make intuitive sense (to me) about Gödel is this idea I read that: once you have formal system of a certain level of complexity, the syntax of that system may become capable enough of making statements about itself; this is how Gödel set up his theorem that effectively says "I am not provable" - self-referential statement. If you have a simpler formal system, such as the predicate propositional calculus of logic [I meant to say the propositional calculus originally], in this case the system syntax is too simple, and is not capable of making self-referential statements about itself, and without such self-reference, you cannot set up a liar paradox. This gives a relatively easy-to-grasp intuitive understanding of why some statements can be undecidable with respect to the axioms of the formal system. But not as much intuitive understanding as Chaitin's theorem provides, at least for me. Drgao (talk) 06:27, 12 July 2011 (UTC)
Pedagogically, the short Nagel and Newman book (referenced in the article) did a good job, so that might be the way to present it. History2007 (talk) 09:35, 12 July 2011 (UTC)

"...in theories that include a small portion of number theory, a complete and consistent FINITE list of axioms can never be created..."

Number theory has infinite list of axioms, because induction scheme includes the infinite count of axioms. --Ruwolf (talk) 21:48, 14 July 2011 (UTC)

That's true; the article even points it out. The second half of the sentence you quoted goes on to talk about infinite theories. — Carl (CBM · talk) 23:23, 14 July 2011 (UTC)
Gödel's incompleteness theorems talk about infinite theories only.--Ruwolf (talk) 14:26, 15 July 2011 (UTC)
Not exactly. vNBG is a theory of set theory which can have a finite set of axioms, and the incompleteness theorems apply. — Arthur Rubin (talk) 14:57, 15 July 2011 (UTC)
Also Robinson arithmetic, of course. — Carl (CBM · talk) 15:46, 15 July 2011 (UTC)

Confusing sentences

The article says: "Some ... argue that it is not a problem for logicism because the incompleteness theorems apply equally to second order logic as they do to arithmetic. They argue that only those who believe that the natural numbers are to be defined in terms of first order logic have this problem." Isn't there an error in the first sentence? Kakila (talk) 08:48, 15 August 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 . — 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)
I'm willing to concede that it's reasonably obvious (I think?) that having a program which can list all axioms, and which can list all rules of inference, is equivalent to having a program which can list all proofs. (The rules of inference would have to be listed in some useful and countable form, e.g. not "if 'P(a)' is a theorem then 'P(x)' is a theorem where x is any real number".) Just having a program which can list all axioms is not, I think, at all equivalent to having a program which can list all proofs, so I think what the article says is wrong. Anyway, shouldn't it be supported by a reliable source? ☺Coppertwig (talk) 17:30, 24 July 2011 (UTC)
Technically, you don't need to be able to list the rules of inference, but only to recognize whether a statement (or line of a proof, if statement turns out not to be the correct word) follows from preceding statements by a rule of inference. But, I agree, there should be a reference, and I don't have texts at the right level to have those references. — Arthur Rubin (talk) 18:49, 24 July 2011 (UTC)
OK, I guess recognizing is enough: but my point remains, just being able to list the axioms is not "equivalent". ☺Coppertwig (talk) 19:16, 24 July 2011 (UTC)

Ambiguity of the Term "Truth"

One other point that I should mention that might conceivably improve the article: it can be very confusing for a beginner when the term "truth" is used in two different senses in the same text, as it often is in writings about Gödelian incompleteness. As I understand it (which I hope is correctly), in one sense, the term "truth" is used to denote whether a statement (theorem), written using the symbols of the formal system, has been proved with respect to the axioms of that system (and likewise, the term "false" denotes when a statement has been proved incorrect with respect to the axioms).

But then a second, different definition of the term "truth" is often simultaneously employed to describe the same statement (theorem). This second definition meaning that the syntax of the statement is correct - that is, the statement correctly follows the rules of grammar for combining the symbols of formal system.

The article says, in this extract: "The true but unprovable statement referred to by the theorem is often referred to as the Gödel sentence for the theory" - in this extract the term "true" is used in its 2nd sense. It might be a better idea to use the term "syntactically correct" instead of "true", for this 2nd definition of "truth". The "true but unprovable" part of this quoted extract is particularly confusing, since by definition "unprovable" means the theorem cannot be shown true or false (in the 1st sense of the term "true"), but then just two words later you are calling this theorem "true" (in the 2nd sense of the term "truth")!!

For a subject that is difficult to grasp anyway, having this double definition of the term "truth" does not make for easy comprehension. I know this ambiguity in definition is found in many other texts on Gödelian incompleteness, but it nevertheless is confusing. Drgao (talk) 06:27, 12 July 2011 (UTC)

OK, sorry, but what you hope is the correct understanding is in fact not.
"True" here means just what it normally means. The statement "the apple is red" is true, just in case the apple is in fact red. The Goedel sentence says there is no natural number with such and such a property, and it is true just in case there really is no natural number having that property. --Trovatore (talk) 08:55, 12 July 2011 (UTC)
Well, the thing is, the definition of the term "truth" depends on the discipline you are working with. Broadly speaking, there are two widely-used definitions of the term "truth": deductive truth and inductive truth. For mathematics and logic, deductive reasoning is employed, and in this, a statement is said to be true in when it has been correctly derived from its premises using logical inference. This is very strong type of truth, in that providing the derivation is correct, the truth is unassailable. By contrast, in the sciences inductive reasoning is employed, and in this, a statement is said to be true when it has been repeatedly observed (in the physical world) to be the case. Inductive truth is a statistically based truth; and as every philosopher of science knows, it is not possible to definitively prove something true in science, as scientific truths are, in essence, statistically based, and are always just provisional. You can only prove something definitively false in science. These limitations do not apply to mathematics and logic, where you are able to prove something definitively true (or false) - with of course the exception of Gödelian unprovable statements.
Anyway, that preamble is just to demonstrate that it is important to know the definition of your term "truth". As the deductive definition of truth is used in mathematics and logic, what we mean by saying a statement is true in mathematics and logic is that the statement has been derived from the premises or axioms using deductive logic.
However, as I am suggesting, in addition to this usual deductive definition of truth, the article here is also using another definition of truth, namely that the syntax/grammar of the statement (the Gödel sentence) is correct. This confusion is rife in writings on Gödel's work. It makes the subject more abstruse than it need be. Drgao (talk) 18:17, 12 July 2011 (UTC)
It is not correct that in mathematical logic a proposition is said to be true just when it is provable. That is what the word "provable" is for. The article already explains that the word "true" in the statement of the theorem refers to disquotational truth. This is the only sense in which the word "true" is used in the article. The article never uses the word "true" to mean "syntactically well formed". When the article says "true but unprovable", it means just that: the statement is disquotationally true, and it is not provable in the theory T under consideration. — Carl (CBM · talk) 18:27, 12 July 2011 (UTC)
Drgao, you're confusing ontology with epistemology. When we say that the Goedel sentence is true, we mean there really is no natural number having the property in question. We're not talking about how we know whether there is such a natural number (epistemology) but simply whether there really is one (ontology). --Trovatore (talk) 18:29, 12 July 2011 (UTC)
I think if those questions exist for Drago, then Wikipedia has not done a great job of explaining the term logical truth. I think CBM and Trovatore's points are basically true (whatever that may mean now, pun intended) but perhaps needs to be explained somewhere. As is truth (logics) is a redirect and needs to be expanded at some point. It would be best to do that somewhere as even a stub that will explain it in the future too, rather than on a talk page. The basic issue, as you pointed upfront remains pedagogical and the problem is that this article can not be both in depth and introductory, so an introductory article without details should be suggested somehere. There are, of course, so many other things to do that I do not know when it will be done. History2007 (talk) 18:32, 12 July 2011 (UTC)
That may be, but you have to be careful with the term logical truth, which for some people means analytic truth. One way of viewing the Goedel theorems is precisely that they show that mathematical truth (such as that of certain Goedel sentences) is not entirely analytic, that it has a synthetic component. That's for those who accept the Kantian distinction in the first place. (You may not have meant that we should actually use the term logical truth in the article, but I think it's an important caveat.) --Trovatore (talk) 18:51, 12 July 2011 (UTC)
I did not even know the article Logical truth exists. It is not a bad article, but not great either, given that the section on Logical truth and rules of inference has just one sentence that leads to the Rule of inference article marked as "confusing". What I meant was that the general concepts of truth, provability, satisfaction etc. seem to be less than clear in the questions posed by Drago, regardless of this article. And I do not know of a 3 page "overview of mathematical logic" article that one can tell people to read. I used to tell people to read Nagel and Newman's book as a starter, so I think something like that would have helped Drago's questions and the next 30 users who did not even ask and just clicked away. History2007 (talk) 19:13, 12 July 2011 (UTC)
I am not really asking a question, but more pointing out that you are using a term which you have not clearly defined. You have used the term "true", but you don't seem to be able to provide a basic definition of this term. In discussion here, you are in effect providing circular definitions: "true means true", which is of no use. You need to define the term "true" before you use it. You haven't.
It certainly cannot mean the Gödel statement is true as a proven theorem, as we know by definition that the Gödel statement is unprovable. Drgao (talk) 20:02, 12 July 2011 (UTC)
My apologies, but I am busy with other hings and have to bow out on this one. History2007 (talk) 20:24, 12 July 2011 (UTC)
I am not raising a dispute here, rather just trying to bring this crucial point into focus, by asking you consider this point. I prefer a good-natured debate. Drgao (talk) 20:34, 12 July 2011 (UTC)
Drgao, please read disquotational theory of truth, and then let us know if you have suggestions for making the point clearer. There is no circularity; I think you're just holding on to the "true means provable" idea, which is simply wrong. --Trovatore (talk) 21:28, 12 July 2011 (UTC)
I did read the disquotational theory of truth, and do completely understand the point your are making (which that the use of the term "true" in the above statement is just a tautological end tag to that statement). If you want to say that your use of the term "true" in this instance is just tautological, I can understand that - but then why put the word "true" there at all, if its only function is tautological? That is a rhetorical question, because I am suggesting that the definition of the word true in this instance is not tautological, but confers a specific meaning, namely that the syntax of the mathematical statement is well-formed and syntactically correct. I shall explain why in a moment. I know it does not say that in the article, but I suggest it should.
But first, you must agree that you are also using the term "true" in this article to mean "provable". This definition of true arises implicitly when you use the term "unprovable", as unprovable means "can neither be proved true or false with respect to the axioms". But you have also used "true meaning provable" explicitly a number of times in the article; for example, in this article extract: "Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement".
Well-formed and syntactically correct. Let me see if we can get some perspective to this. First of all, remember that Gödel's theorems apply to the formal system of arithmetic, and Gödel's theorems are perhaps best understood in the context of the whole formalization project of mathematics. Formalization means completely divorcing your system (arithmetic) from physical reality, and only dealing with the elements of the formal system, namely: explicitly defined symbols, the axioms of the system, the grammar/syntax rules for combining those symbols into statements, and some inference rules.
Now, with such a formal system, anyone can write a statement using the defined symbols of the system (symbols such as +, -, x, ÷, 0, 1, 2, etc in the case arithmetic); however, if you don't follow the rules of grammar of the formal system, your statement will not be valid, even before you start to prove whether the statement is true or false with resect to the axioms. So, for example, the arithmetical statement 2 + 2 = 5 is syntactically correct (true), but can be proven false with respect to the axioms by logical inference. By contrast, the arithmetical statement 2 + = ÷ = 7 is gibberish, as it does not follow the syntax rules for combining the symbols of the formal system of arithmetic. So this gibberish statement is syntactically incorrect (false). You cannot do anything further with syntactically incorrect statements.
My view is that when it is said that the Gödel sentence is true, this is not tautological, but rather it is saying that, as a statement, the Gödel sentence is well-formed and syntactically correct. In this sense, the Gödel sentence is a true, valid statement of arithmetic; but as we know, it cannot be proved, in the sense of its import being proved true or false by logical inference from the axioms of arithmetic.
In summary: in any formal system, such as arithmetic, you can make statements by combining the defined symbols of that system. If those symbols are correctly combined according to the syntax rules of that formal system, then you can say your statement is a valid, true statement. Having made such a valid, true statement, then next step is to prove whether the import of this statement is true or false with respect to the axions.
Gödelian incompleteness shows that there are statements of arithmetic that are syntactically correct (and thus true in this sense), but with cannot be proved true or false, in the (different) sense of being proven true or false by logical inference from the axioms.
So: truth/falsity in sense 2 (as used above) means: the arithmetical statement is/isn't well-formed and syntactically correct.
and: truth/falsity in sense 1 (as used above) means: the arithmetical statement is/isn't correct with respect to the axioms.
Truth/falsity in sense 2 deals with the syntax of the statement; truth/falsity in sense 1 deals with the semantics of the statement.
I believe that both usages of truth/falsity are being confusingly employed in not only this article, but in other writing I have read on Gödelian incompleteness. Drgao (talk)
You say My view is that when it is said that the Gödel sentence is true, this is not tautological, but rather it is saying that, as a statement, the Gödel sentence is well-formed and syntactically correct. But you see, your view is wrong. That is not what it is saying. I have tried to explain this but you don't seem to be listening. I would like to make the article harder to misunderstand, but at this point I don't think it's the article's fault. I think you are simply unwilling to revise your incorrect beliefs. --Trovatore (talk) 00:14, 13 July 2011 (UTC)
I will try to dig up a reference that backs up what I just said. I know I read this somewhere, it may have been in the book Gödel, Escher, Bach, or elsewhere. Do you have any refs that show this is a disquotational use of the word truth, as you have claimed? Drgao (talk) 00:31, 13 July 2011 (UTC)
GEB is a great book but a poor reference for the Goedel theorems. Hofstadter is not a mathematician and frankly he made some mistakes. As for references, there are some right in the note itself (I don't know that they use the word disquotational, though, and I don't have the Smoryński one). --Trovatore (talk) 00:36, 13 July 2011 (UTC)
Yes, I originally read Nagel and Newman (the intro half, not proof), but for me I found GEB is good for getting an overview understanding of the nature of formal systems. I am also a fan of Rudy Rucker's books, his "Infinity and the Mind" being a real gem. You may be right, that this may just be a disquotational use of the word truth; I believe I read otherwise somewhere, but I may be wrong. If I cannot find the ref, then I may be wrong on this point. Even so, even if this is indeed a disquotational use, there is still the use of the term "truth" to mean "proven from the axions" in the article, so some confusion may still be possible between these two meaings. Drgao (talk) 01:21, 13 July 2011 (UTC)
Please point me to where in the article "truth" is used to mean "proven from the axioms". If that is there, that's an error that should be fixed.
(By the way, I wouldn't use the word "just" with "disquotational use". The disquotational use of "G is true" is the same as asserting G, but G itself makes a factual claim about the world. It is not a tautology.) --Trovatore (talk) 01:34, 13 July 2011 (UTC)
On reflection, Trovatore, I think you are correct on this: the word "truth" is used in a disquotational context; I've just been looking through my bookshelf, but cannot find any refs to support what I said. However, it does seem that though some writers prefer using a disquotational phrase, such as: "a true statement that is unprovable"; but other writers prefer to focus on the syntactically correct aspect of the statement. For example, Boyer, in the "History of Mathematics" says "within the system, there exist certain clear-cut statements that can neither be proved or disproved"; ref: here. Boyer thus focuses on the clear-cut (well-defined / syntactically correct) nature of the statement.
So really, I do think phrasing such as:
"a well-defined but unprovable statement"
is better than how it is currently expressed in the article, which is:
"a true but unprovable statement".
The latter phrasing, to my mind, has the flavor of an oxymoron, and is confusing. But this is just a matter of personal taste, rather than being wrong or right. My aim is to make a clearer, easier-to-undertand article.
In terms of places within the article where "truth" is used to mean "proven from the axioms" (which is the regular meaning of the word "true" in mathematics, when you say things such as "Fermat's last theorem has been proved true"), here are some article text extracts of this particular use:
"The liar paradox is the sentence "This sentence is false." An analysis of the liar sentence shows that it cannot be true (for then, as it asserts, it is false), nor can it be false (for then, it is true). A Gödel sentence G for a theory T makes a similar assertion to the liar sentence, but with truth replaced by provability: G says "G is not provable in the theory T." The analysis of the truth and provability of G is a formalized version of the analysis of the truth of the liar sentence."
"Undecidability of a statement in a particular deductive system does not, in and of itself, address the question of whether the truth value of the statement is well-defined, or whether it can be determined by other means. Undecidability only implies that the particular deductive system being considered does not prove the truth or falsity of the statement. Whether there exist so-called "absolutely undecidable" statements, whose truth value can never be known or is ill-specified, is a controversial point in the philosophy of mathematics."
But there is nothing wrong with these extracts; they are correct. Rather, I personally think it is the disquotational uses of the the term "true" that should be removed. Such disquotational uses are found here, for example:
"For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system."
"...there are true statements expressible in its language that are unprovable..."
"...there are other true statements that still cannot be proved..."
In the three disquotational use cases above, my feeling is that the article would be rendered clearer if the term "true" was replaced with "well-defined". The above three extracts would then become:
"For any such system, there will always be statements about the natural numbers that are well-defined, but that are unprovable within the system."
"...there are well-defined statements expressible in its language that are unprovable..."
"...there are other well-defined statements that still cannot be proved..."
But just to re-interate, I concede that the term "true" is used in disquotationally. But I also point out that the alternative I have outlined is, to my mind, easier to comprehend, and less likely to confuse. And another advantage in going with this "well-defined" alternative description is that you then remove one of the two different meanings of the word truth in the article, thus eliminating the ambiguous use of this term.
What do others here think? Drgao (talk) 04:11, 13 July 2011 (UTC)
There is no ambiguity. The Goedel sentence of a consistent theory is true. In every relevant sense of the word. It correctly describes the behavior of the natural numbers. We do not serve our readers by quibbling on this point. --Trovatore (talk) 08:15, 13 July 2011 (UTC)
(Possibly to make the point clearer — given a consistent theory T, the negation of its Goedel sentence, ~GT, is also a "well-defined" statement, and it is also neither provable nor disprovable in T. However, ~GT is false. That demonstrates that you can't make the point by replacing true by well-defined.) --Trovatore (talk) 08:46, 13 July 2011 (UTC)
There are not two meanings of "true" in the article, though. It is right that if a sentence is provable that implies it is true, but that does not mean that we ever use "true" to mean just "provable". The quoted passages about the liar paradox are still using "true" in the usual way.
The fact that the Gödel sentence for a theory is both unprovable in the theory and true is a key part of the theorem. The truth of the Gödel sentence is an important factor in the philosophical interpretation of the theorem. It would be much less interesting to just say "there is a sentence that is unprovable", because every consistent theory satisfies that, and the main interest in saying "there is a sentence that is neither provable nor disprovable" would be that either the sentence or its negation has to be true. So it would be a disservice to the article to try to remove all mention of the truth of the Gödel sentence. There are literally dozens of sources that discuss the truth of the Gödel sentence, for example all the common textbooks do. — Carl (CBM · talk) 12:16, 13 July 2011 (UTC)
I thought the whole point of Gödel's (and Chaitin's) work was to show that, contrary to David Hilbert's hopes, in arithmetic, there will always be theorems whose meaning as a statement is precise and completely defined, but for which it impossible to determine whether that theorem is true, or whether it is false. Thus the theorem forever floats in limbo: its truth or falsity can never be known. This I always thought was main import of Gödel's work.
I am going to take short break from this, so that I can think about it a bit more, and hopefully get back to you. Thanks for your inputs in this; they are much appreciated. Drgao (talk) 05:56, 14 July 2011 (UTC)
This is in danger of devolving into a general discussion of the subject matter, which is off-topic for article talk pages, but let me just respond briefly. The Goedel theorems don't tell us whether or not there are statements whose truth values we can't know. They do tell us is that for any (consistent) fixed formal theory, there are statements that that theory does not decide.
As it happens, the Goedel sentence of a consistent formal theory is always true. However it doesn't necessarily follow that we know that it is true, because we may not know that the formal theory is consistent.
Any further discussion should probably take place on user talk pages, unless there is an active proposal for changing the article. --Trovatore (talk) 08:41, 14 July 2011 (UTC)
Yes, what is happening is that you guys got talked into providing a tutorial on the basic concepts. There is no need to modify the article, or discuss this further. This is a very well written article, and an example of good scholarship in Wikipedia. But eventually a simpler page may be a good idea, so that this scenario will not self-repeat in 9 months and efforts can be used for general article improvement rather than tutorials.
In passing let me mention that a brief sentence on how Turing tried to provide (an alas unrealistic) remedy via Ordinal logic may be appropriate, but I will leave that to you guys. History2007 (talk) 13:37, 14 July 2011 (UTC)
This seems to be where some of confusion lies, Trovatore: you said: "The Goedel theorems don't tell us whether or not there are statements whose truth values we can't know. They do tell us is that for any (consistent) fixed formal theory, there are statements that that theory does not decide."
By definition (as I understand it) an undecidable statement is a statement whose truth value you cannot know. For example, some people once speculated that Fermat's last theorem was undecidable; however, now that Fermat's last theorem has been proven true, we know it is decidable (and incidentally, even if it had been proved false, this would have still shown it to be decidable). Drgao (talk) 19:37, 14 July 2011 (UTC)
This discussion has clearly moved on from how to improve the article (which is the scope of talk pages) to the subject matter of the article (which is outside that scope). I'll respond briefly on your user talk page. --Trovatore (talk) 20:23, 14 July 2011 (UTC)
As far as I am aware, this discussion is on just one subject: that the juxtaposition of terms "true but unprovable" used in the article in several places is, in a strict sense, technically incorrect. Notice how Wolfram do not include the word "true" in their description of Gödel's first incompleteness theorem. Drgao (talk) 04:58, 15 July 2011 (UTC)
It is not "in as strict sense, technically incorrect". It is completely correct, strictly, technically, and in every other way. --Trovatore (talk) 06:42, 15 July 2011 (UTC)
To be more precise: when referring to the Gödel sentence, and the methods of Gödel's proof, it IS correct to say "true but unprovable", because the Gödel sentence has been defined as both unprovable and true. However, when you talk about the conclusion and import of Gödel work, that is, what it means in general, then you should not really say "true but unprovable".
This is similar to reductio ad absurdum proofs, where as a technique, in order to prove a theorem false, for example, you temporarily set that theorem to be true, and then you show that this arrives at a contradiction, and thus showing that the theorem must in fact be false. There is a confusion here about statements that are just temporarily set to be true during Gödel's proof process. Drgao (talk) 07:21, 15 July 2011 (UTC)
No. It has not been "defined as unprovable and true". The Goedel sentence of a consistent theory T simply is true as an assertion about the naturals, not necessarily about the objects of discourse of T — see my remarks above on sneetches, and simply is unproveable in T. There is nothing temporary about it. --Trovatore (talk) 08:34, 15 July 2011 (UTC)

As our article says, the Gödel sentence is true because it "asserts its own unprovability and it is indeed unprovable" (Smoryński 1977 p. 825). More specifically, the Gödel sentence for a suitable theory T is of the form where P is a certain quantifier-free formula in the language of arithmetic. Because P(n) is true for every natural number n, the Gödel sentence is true. In order for the Gödel sentence to be false, there would have to be a natural number m such that P(m) is false, but the proof of the incompleteness theorem shows there is no such m. — Carl (CBM · talk) 12:47, 15 July 2011 (UTC)

Fine, I am not disputing the use of "true but unprovable" when referring to the Gödel sentence or the mechanics Gödel's proof. It is perfectly correct to say "true but unprovable" in this context. So in most places where the article uses "true but unprovable", it is used correctly.
However, once you have arrived at Gödel's result, and you start talking not about the mechanics of Gödel's proof, but rather about what this proof means for formalized axiomatic systems in general, then this is different. When you say things like Gödel's result shows that "...there are true statements expressible in its language that are unprovable..." then it is technically wrong (unless you are using "true" in a different sense to the rest of the article).
If you cannot see this, it may be because you don't quite appreciate the the way formalized axiomatic systems work, and why they are so important to mathematics; there is a long history behind the development and understanding of formalized axiomatic systems, which was a remarkable human achievement in clear thinking.
Mathematical statements cannot have any (deductive) truth or falsity unless they are proved true or false WITHIN a formal axiomatic system. There is NO (deductive) truth outside of a formal axiomatic system.
Now, you may say that a mathematic statement has (inductive) truth because that statement captures and expresses something about the real world, sure, I grant you that, but then, as I mentioned before, we are talking about a different type of truth: inductive truth, not deductive truth.
It needs thinking about, but it is not that difficult to understand. Drgao (talk) 16:34, 15 July 2011 (UTC)
When the article says "any consistent formal system that includes enough of the theory of the natural numbers is incomplete: there are true statements expressible in its language that are unprovable..." it is referring to the Gödel sentence for that formal system. But you say, "I am not disputing the use of "true but unprovable" when referring to the Gödel sentence ...". The Gödel sentence for a formal system is both unprovable within that system and true when read as a statement about natural numbers. — Carl (CBM · talk) 16:54, 15 July 2011 (UTC)
In the extract you selected, namely "Gödel's first incompleteness theorem shows that any consistent formal system that includes enough of the theory of the natural numbers is incomplete: there are true statements expressible in its language that are unprovable." it is talking about the result of Gödel's theorem; the fact that during the proof process you temporarily defined the unprovable statement as "true" should be forgotten now.
Think of a reductio ad absurdum proof, where you temporarily set a statement to true in order to obtain a contradiction. Drgao (talk) 18:34, 15 July 2011 (UTC)
(Incidentally, I noticed just now that I did make an error in the very first example extract I gave, right at the start of this section: in that extract, contrary to what I said there, the use of true but unprovable is fine, as that extract refers to the Gödel sentence.) Drgao (talk) 18:34, 15 July 2011 (UTC)

History around the Goedel's use of the words "truth" and "provable"

I went back into the History and found the following exerpts. For Goedel in 1930 "truth" is an absolute (objective) notion, not relative to a particular formal system. As I recall, later in life Goedel's assertions of "Platonic" (absolute) truth were more ambiguous. But at the stage in his life when he discovered his proof he was rebelling against the "Vienna Circle" notion of relative truth. Davis 2000 also commented that at the time the notion of metamathematics was poorly understood. Here are two exerpts from the archived history section:

So in 1930 Gödel set out to provide a positive solution to the second of Hilbert’s problems – to give a finitary consistency proof for the axioms of analysis relative to arithmetic; his goal being “not to destroy Hilbert’s program but to advance it” (Dawson:61)[3]. G-G [Grattain-Guinness] opines that "Apparently Gödel found his theorem when he represented each real number by an arithmetical proposition φ(x) and found that, while 'φ(x) is provable' could also be so treated, 'φ(x) is true' landed him in liar and naming paradoxes” [4]. As reported by Goldstine, von Neumann stated that he was, at the same time, working on Hilbert’s second problem, but he had not recognized the critical “truth-versus-provable” issue that Gödel did recognize (Dawson:71). As to why others had not arrived at the proof first, Gödel would blame "the philosophic prejudices of our times 1. nobody was looking for a relative consistency proof because [it] was considered axiomatic that a consistency proof must be finitary in order to make sense 2. a concept of objective mathematical truth as opposed to demonstrability was viewed with greatest suspicion and widely rejected as meaningless."(Letter to Yossef Balas in Collected Works Vol. IV:10).
Wang was interviewing Goedel so this is a precis of Goedel's words: "In the summer of 1930, Goedel began to study the problem of proving the consistency of analysis. He found it mysterious that Hilbert wanted to prove directly the consistency of analysis by finist methods. His idea was to prove the consistency of number theory by finitist number theory, and prove the consistency of analysis by number theory, where one can assume the TRUTH of number theory, not only the consistency. The problem he set for himself at that time was the relative consistency of analysis to number theory . . . ¶ He represented real numbers by formulas (or sentences) of number theory and found he had to use the concept of truth for sentences in number theory in order to verify the comprehension axiom for analysis. He quickly ran into the paradoxes (in particular, the Liar and Richard's) connected with truth and definability. He realized that truth in number theory cannot be defined in number theory and therefore his plan of proving the relative consistency of analysis did not work" [TRUTH capitalized for emphasis, p. 654].
BillWvbailey (talk) 19:44, 15 July 2011 (UTC)
Thanks for that, BillWvbailey. I understand that Gödel was a pretty hard-core mathematical Platonist - the view that the world of mathematics and logic has a kind of actual existence, separate to the physical world. But you say he softened up a little later. Drgao (talk) 02:00, 16 July 2011 (UTC)
That is not my understanding. I heard Martin Davis on the topic of Goedel's developing Platonism, and according to Davis, he moved further "right" as time went on. (The "left–right" spectrum in this context is also due to Goedel, by the way — it doesn't necessarily have much to do with political views, although it is interesting that many on Godel's "left" were also politically left.)
In any case, what Drgao may not fully appreciate is that there is a convention in mathematics to speak like a Platonist whether you actually are one or not. It just simplifies exposition immensely, especially in contexts like the one we're currently involved in. --Trovatore (talk) 02:11, 16 July 2011 (UTC)

Trove, I think you and I batted this one around a bit on another occasion. I think we're both half right and both half wrong. Here's what I can glean in quick reviews of two later, unpublished papers that he wrote, . These appear in volume III Kurt Goedel Collected Works along with very good commentary before them. The first is titled "Is mathematics syntax of language?" (1953/9) with commentary by Warren Goldfarb. Goldfarb ends with this sentence: "As his discussion of mathematical intuition in *1961/? and in 1964 show, his thinking on the issue continued to evolve over the next few years." (p. 334). In the introductory notes to Goedel's second paper *1961/? "The modern development of the foundations of mathematics in the light of philosophy", the acommentator Dagfinn Foellesdal writes:

"Goedel places the Weltanshauungen and also specific philosophical views on a scale according to their affinity with or distance from metaphysics or religion. On the left, furthest from metaphysics, he places skepticism, materialism, positivism, empiricism and pessimism, on the right, spiritualism, idealism theology, apriorism and optimism. Goedel notes that the development of philosophy since the Renaissance largely has been from the right to the left on this scale. ¶ Goedel makes clear that his sympathies lie with the right. This is in keeping with this statements to various interlocutors . . . This sympathy is muted and qualified in Goedel's publications and lectures; in the present text, Goedel gives more open expression to this attitude than in anything else intended for public presentation. Still, Goedel says that "the truth lies in the middle or consists of a combination of the two conceptions" (page 7), and much of the lecture is a development of that thought." (p. 365)

The commentator notes that "Goedel held realist views on mathematical entities since his student days . . . or more accurately since 1921-22c. [Footnote c Feferman 1984a, pp. 549-552; see, however also Feferman's introductory note to Goedel *1933o in this volume, p. 39, where Feferman comments on Goedel's apparently skeptical statement about Platonism on p. 19 of that manuscript] (p. 368). But the commentator notes a slight variation in wording in the *1961/?: "Goedel does not say straightforwardly that the properties of concepts are objective, but that they are as objective as the physical properties of matter. This brings him close to Husserl . . . Husserl called himself an "idealist". However, his [Husserl's] view is much more realist and Platonist than traditional idealist points of view . . ." (p. 369).

Thus the ambiguity continues (for me) because of all the nuances in these various philosophies. Again reading this I come away with the same impression that I had back when, that the definitive study of Goedel's philosophy of mathematics from the most recent literature hasn't been done successfully. BillWvbailey (talk) 17:04, 16 July 2011 (UTC)

But Feferman's "Introductory note to *1933o" paints it this way: "There is certainly no questioning Goedel's unremitting espousal in print of full-fledged Platonism beginning with his 1944 article on Russel's mathematical logic and continuing (especially in his 1947 article on Cantor's continuum problem) until his death" (p. 40, italics mine). But there are footnotes re "one may take Goedel's retrospective claims about his earlier views cum grano salis, colored as they are by his later firm stance" and one from Martin Davis suggesting that "Goedel's Platonism regarding sets may have evolved more gradually than his later statements would suggest" (this agrees with Trovatore's assertions). Then Feferman posits that maybe Goedel held varieties of Platonism, or perhaps he suffered a "temporary period of doubt about set-theoretical Platonism." Feferman concludes with "Unless further evidence from the Nachlass comes to light that we are not presently aware of, all of this must, unfortunately, remain speculative. ¶ In any case, within the context of this article, Goedel's assertion of the unacceptability of the Platonist postition as justification for the axioms of set theory must be taken at face value." (all quotes p. 40).

This supports Trovatore's assertions, but for me it lacks the philosphical nuances of the later unpublished papers cited above in particular "one of the basic problems of philosophy, namely the question of the objective reality of concepts" (in a Goedel letter to Schilpp 1959, see p. 369), the role of intuition, realism, idealism etc (so many -isms, so little time). Bill Wvbailey (talk) 18:35, 16 July 2011 (UTC)

Although these philosophical angles are very interesting, this does get away from the basic "true or false" truth value that I am referring to, as used within the mechanics of Gödel's proof. When you talk about the nature of "mathematical truth" this is a more nebulous philosophical discussion, much like discussion on say the nature of "mathematical beauty".
What I am talking about is unrelated to this; I am just talking about the simple concept of a truth value - a value that in a computing environment, for example, is either a 0 or 1. Drgao (talk) 23:56, 16 July 2011 (UTC)
Drgao, if I understand right, you want to take sentences such as this in the article: "...there are infinitely many statements in the language of the theory that share the property of being true but unprovable." and replace "true" with "well-defined". If "well-defined" is understood as meaning "syntactically correct", then I think that your proposed change would be correct and not unreasonable, however I oppose it because I think keeping "true" is better. The statement with "well-defined" and the statement with "true" mean two different things.
Goedel did prove that there are statements that are syntactically correct and cannot be proven within the system. This proof was somewhat long and complicated. (Furthermore, I think it was not a theorem within the system! I think he didn't prove that within an axiomatic system of the type we're discussing, but with a meta-argument outside the system.) However, my understanding is that having done that, he then went a step further and made an argument (not a proof within an axiomatic system, but a simple, convincing argument) that, when the Goedel string is interpreted as having meaning according to the usual meanings of the symbols, it is also true. Here true doesn't mean syntactically correct; it means that it says something about numbers and that what it says is actually true.
Here's an analogy: consider a very simple axiomatic system which has no axioms (i.e. the set of axioms is the null set,) and in which "2 + 2 = 4" is syntactically correct, "2 + 2 = 5" is syntactically correct, and "2 + + + 2 = 4" is not syntactically correct. Since there are no axioms, nothing can be proven within this system, so all the statements are unprovable. Therefore in that system, "2 + 2 = 4" and "2 + 2 = 5" are each syntactically correct and unprovable in that system. But we also know things that aren't expressed in that axiomatic system, so if we interpret the symbols as having meaning about numbers in the usual way, then we know that "2 + 2 = 4" is true but not provable within that system, and "2 + 2 = 5" is false but not provable to be false within that system. The way I'm using the word "true" here is, I believe, the same way the word "true" is being used in the article. Note that, as Trovatore pointed out, the fact that ~G is false clearly indicates that there is a difference between the meaning of "true" and the meaning of "syntactically correct".
There may be room for improvement in the article. Would it make sense to say both somewhere in the article? I.e. that there are statements that are syntactically correct and not provable in the system, and that there are statements that are true and not provable in the system, and discuss a bit the relation between these statements. The second doesn't necessarily follow logically from the first; but it follows if the unprovable statement is, for example, the particular string G which can be interpreted as being a meaningful statement (by thinking human beings who can see more than what can be generated within an axiomatic system) which makes a particular statement about numbers that has relevance to whether certain proofs exist.
This is all explained in the book "Goedel, Escher, Bach", which I also read and enjoyed. I didn't notice any mistakes in it, which certainly doesn't prove (!) that there weren't any. ☺Coppertwig (talk) 22:16, 24 July 2011 (UTC)
Retrieved from "https://wiki.riteme.site/w/index.php?title=Talk:Gödel%27s_incompleteness_theorems/Archive_8&oldid=789382724"