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

Archive 1

Archive 2

Archive 3

Archive 4

Archive 5

Because of their length, the previous discussions on this page have been archived. If further archiving is needed, see Wikipedia:How to archive a talk page.

Previous discussions:

• Archive 1 ( - 2005-11-14):

---

More Understanding

"This easy corollary of the second incompleteness theorem shows that there is no hope of proving e.g. the consistency of first order arithmetic using finitistic means provided we accept that finitistic means are correctly formalized in a theory the consistency of which is provable in PA."

What?

Is this what is meant?:

"This easy corollary of the second incompleteness theorem shows that if we accept that the finite means are correct in a consistent theory proved by PA then there is no hope of proving the consistency of PA using these finite means." 129.186.18.149 22:00, 13 June 2006 (UTC)

Or rather, is what the whole of Godel's second incompleteness theorem is trying to say, is: a model can't prove its consistency, but a bigger model that includes it that may or may not be inconsistent can prove the included model consistent, but not itself.

If so, what is all the other crap in that section?! X_X 129.186.18.149 22:04, 13 June 2006 (UTC)

Is it possible for this entire article to be rewritten? Many of the sentences are gramatically complicated and are embedded with lots of mathematical jargon. I have taken university topics in real analysis, set theory, etc, and after reading this rather lengthy article, I am more confused than when I started. 41.243.112.40 18:55, 2 January 2007 (UTC)

Although a single author (who was paid for the substantial amount of work involved) might be able to rewrite this to make it flow better, it would never be easy to understand. A lot of qualifications and careful wording are necessary because this is an inherently difficult topic. A sloppy presentation would leave you with something like "it is not what it is" which is impossible, of course. JRSpriggs 08:56, 3 January 2007 (UTC)

Evolution

If "the human mind is inconsistent", would it be an 'adaptive' trait?

IMHO If it is inconsistent it is because it would not be possible for a mind to be consistent and it would be in a way not relevant for the evolution. --Mandelum 20:50, 21 May 2006 (UTC)

Understanding

I'm just putting myself in the shoes of someone who doesn't know a lot of the terminology behind this article. Do you really think they can understand even a simple sentence like this?

The theory obtained by adding quantifier free transfinite induction to primitive recursive arithmetic proves the consistency of first order arithmetic but is not stronger than first order arithmetic.

Perhaps it would be best to insert some pages for the public to read before they read this? Fephisto 21:32, 21 December 2005 (UTC)

The sentence is indeed full of technical jargon. However, I would expect a layman to get the gist of it, namely that in order for a theory T to prove the consistency of an another theory T' it is not necessary for T to be stronger than T'. Perhaps it would be advisable to make this point more explicit, though I personally think it's quite clear already. However, there's now something more horrible in the article, namely the statement of Gödel's theorem:

To every ω-consistent recursive class κ of formulae there correspond recursive class signs r, such that neither v Gen r nor Neg(v Gen r) belongs to Flg(κ) (where v is the free variable of r).

I utterly fail to see the point of including this. The above doesn't mean anything even to logicians and to decipher its meaning one has to read Gödel's original paper and find out what are "recursive class signs" or what v Gen r means. It also appears in MathWorld where it is equally pointless, unless, perhaps, the point is to make Gödel's theorem sound more intimidating and impenetrable. Aatu 13:04, 9 February 2006 (UTC)

" Bob Layman here to let you know that we laymen are having some trouble with the jargon - both examples in this discussion page are incomprehensible outside the community of guys who read about mathematical logic. And let's be honest, anybody who knows about this stuff wouldn't look it up on wiki except to have fun editing. In other words, I read about the theorem, wanted some basics, and had an awefully hard time getting them from this page. Yeah, I know, mathematical logic is complex, but somebody here has clearly found a way to explain at least the first example sentence in a less jargon-y way. Thanks. Bob "well educated but not a logistician" Layman.

Needs clarification

I don't understand this passage:

For example, first order arithmetic (Peano arithmetic or PA for short) can prove that the largest consistent subset of PA is consistent. But since PA is consistent, the largest consistent subset of PA is just PA, so in this sense PA "proves that it's consistent". What PA does not prove is that the largest consistent subset of PA is, in fact, the whole of PA. (The term "largest consistent subset of PA" is rather vague, but what is meant here is the largest initial segment of the axioms of PA ordered according to some criteria, e.g. by "Gödel numbers", the numbers encoding the axioms as per the scheme used by Gödel mentioned above).

• The proof that a consistent subset is consistent is trivial.

Indeed it is! - Aatu

• The statements 'the largest consistent subset of PA is just PA' and 'What PA does not prove is that the largest consistent subset of PA is, in fact, the whole of PA.' seem to be a contradiction.

The largest consistent subset of PA is just PA. What is PA does not prove that if a sentence P belongs to the largest consistent subset of PA iff P is one of the canonical axioms of PA (i.e. P is one of the recursive equations defining multiplication or addition, P is a successor axioms or P is an instance of the induction axiom). PA does not prove this fact, just like it fails to prove e.g. that ZFC is consistent or that any primitive recursive ordering of naturals of order-type epsilon-0 is a well-ordering. Something can be true without PA proving it and PA itself being the largest consistent subset of PA is one of those things. - Aatu

• How can a well defined concept like 'largest consistent subset' be "vague"?

In general, for a set of sentences T there is no consistent subset of T containing (as subsets) all consistent subsets of T (which is what "largest consistent subset" means). If T is consistent then T itself is the largest consistent subset of T, but if it isn't, then there won't usually be any such thing as the largest consistent subset of T. However, if we order sentences in T in a list A_1,..,A_n,... then there will always be a unique longest consistent initial segment A_1,..,A_m,... as explained in the passage later on. - Aatu

The wording is certainly problematic in any case. The language of first-order arithmetic, in which PA is expressed, is not expressive enough to talk about (general) subsets of PA, so the claim "the largest consistent subset of PA is consistent" is not the sort of thing susceptible to proof by PA. PA, roughly speaking, can't even say it, much less prove it. The parenthetical remark at the end of the paragraph attempts to clarify matters, but I think the damage has been done by that point. --Trovatore 17:34, 21 November 2005 (UTC)

Well, I'm not really convinced any damage has been done. But if you feel the wording is misleading, there's nothing to stop you from rephrasing the passage. -- Aatu

This is a good point, but there's something problematic going on here. The language of second-order arithmetic (I'll use PA1 and PA2 to talk about the two systems), is obviously sophisticated enough to talk about these maximal consistent sets, but it is just a two-sorted first-order theory, which can be coded in PA1 and its theory talked about in PA1: this is precisely a means of talking about these sets in the first-order language of arithmetic. Offhand, I'm not sure how we should be putting the notion of PA not being able to talk about these sets. --- Charles Stewart 20:46, 21 November 2005 (UTC)

That strikes me not as a means of talking about the sets, but of talking about talking about the sets. --Trovatore 21:17, 21 November 2005 (UTC)

There is no way in PA to speak about sets in general. But one can code talk about sets of bounded complexity (in the arithmetical hierarchy) using truth predicates applying to formulae of bounded complexity, e.g. to say that "for all recursive sets, ..." or "there is a Delta_3 set, such that" or even that "the largest consistent axiomatizable subtheory of PA is consistent" (you can't prove in PA that there is such a thing, of course, since that amounts to PA being consistent). Talking about second order arithmetic (the two sorted first order theory referred to by Charlest) in PA is in no way "talking about sets in PA", as you note. -- Aatu

Imprecise use of word "system"

I don't understand the meaning of the word system in the following.

Gödel's first incompleteness theorem shows that any such system that allows you to define the natural numbers is necessarily incomplete: it contains statements that are neither provably true nor provably false.

The existence of an incomplete system is in itself not particularly surprising. For example, if you take Euclidean geometry and you drop the parallel postulate, you get an incomplete system (in the sense that the system does not contain all the true statements about Euclidean space). A system can be incomplete simply because you haven't discovered all the necessary axioms.

Does it mean axiom set + all theorems?

Thanks to anyone who will clarify.

Allows humans to "see"...

Sometimes it's claimed that the proof of Gödel's first incompleteness theorem somehow allows humans to "see" the truth of the Gödel sentence of some theory. This is not at all correct. If we know the theory to be consistent, then it trivially follows from the incompleteness theorem that the Gödel sentence is also true. But in general we have no idea whether or not a theory is consistent and consequently no way of "seeing" whether the corresponding Gödel sentence is true or false.

Why has this statement been removed without even discussing it? This is perhaps one of the most common misconceptions about the Incompleteness Theorem. - Sikon 17:04, 24 November 2005 (UTC)

I removed it because it boils down to saying "Lucas is wrong", a POV assertion. Lucas' argument, and the objections to it, are discussed elsewhere in the article. --Trovatore 17:15, 24 November 2005 (UTC)

It's not a "point of view", it's a trivial observation to the effect that Gödel's 1st incompleteness theorem proves the implication "T is consitent --> the Gödel sentenced of T is true", not the Gödel sentence of any particular theory. Consider the theory T = PA + Goldbach's conjecture. The truth of the Gödel sentence of T is equivalent to Goldbach's conjecture (because T is consistent iff GC is true). Yet there is nothing in Gödel's proof that gives us any insight into whether there are natural numbers > 2 that can't be expressed as the sum of two primes. I don't see anything controversial in this. I would perhaps amend my original formulation by adding "... by perfectly ordinary mathematical reasoning." to the end of the sentence beginning "If we know the theory to be ..."

And while we're at it, I think the following "misconception about Gödel's theorems"

The theorem only applies to systems that are used as their own proof systems. Gentzen's work shows the consequences of using a proof theory that is not the same theory, but a more powerful one.

should be removed. It appears rather confused and does nothing to clear up any misconceptions about Gödel's theorems (in fact, quite the opposite). -Aatu

That's what "misconceptions" sections usually do. I'd just as soon nuke the whole section. We should concentrate on clearly presenting what is true and accepted; wording aimed at clearing up misconceptions presents two distinct opportunities for creating more misconceptions: One when the reader tries to figure out what the alleged misconception is, and a second when he tries to understand the fix.

As regards the "Lucas/POV" thing: Interpreted literally, of course the original wording should be noncontroversial. But when I read it, I didn't see it as intended to be read literally, but rather as intended to refute Lucas. Perhaps I was wrong about that, but I suggest that that's how the passage came across. --Trovatore 18:37, 29 November 2005 (UTC)

I was under the impression it was aimed against Penrose... - Sikon 08:56, 22 December 2005 (UTC)

Could be. Clearly that would be just as bad, in terms of being POV. --Trovatore 09:16, 22 December 2005 (UTC)

A question about common practice and some whining

When I first took a look at what Wikipedia has to say about Gödel's incompleteness theorems I recoiled in horror; the entry was full of non-sense and confusion. I then took the time to rewrite the first three sections, which resulted in something approximately like http://en.wikipedia.org/w/index.php?title=G%C3%B6del%27s_incompleteness_theorem&diff=18326634&oldid=18326416". I didn't do anything to the rest of the sections apart from explaining the two different senses the term "undecidable" is used in logic. I also wrote a section "A major overhaul needed?" in the discussion section, pointing out various errors and inaccuracies and offered to rework the whole article. This received no comments. Since then I have mostly watched the article slowly detoriate, making a few corrections now and then. The detoriation has not been only because new inaccuracies have been introduced, but also because people have introduced various clarifications that in reality just add confuse, reworded awkward sentences subtly changing their meaning and seem to have felt the need to introduce more technical details than I originally deemed appropriate. Of course, there's nothing wrong in introducing technicalities per se, but when it is done in an ad hoc fashion in middle of explanations on a more general level, I feel the result is confusing to potential readers. And the sections on implications and signifance of Gödel's theorem are still, on the whole, a haphazard collection of more or less relevant, accurate or comprehensible musings.

Now, this being Wikipedia there's no reason for me to expect anyone to hold my contributions sacrosant. But if I undertake the effort to completely rework this article - as I suggested in the now archived discussion entry "A major overhaul needed?" - I would find it encouraging if upon noticing an apparent inaccuracy or an awkwardly worded phrase instead of editing it right off, people would discuss it here. But, being new to Wikipedia, I've no idea whether this is a reasonable expectation or not. If not, then I'll just crawl back into my hole and leave the article as it is. Perhaps there are some notes or instructions on writing and editing a Wikipedia article on a highly technical topic such as Gödel's incompleteness theorems?

A simple example of detoriation is the evolution of the statement of the first incompleteness theorem. The way I originally worded the first incompletness theorem was not merely a result of my poor English, but because of an important technical distinction. Consider this wording

Gödel's 1st incompleteness theorem gives us a method to produce from any theory T proving basic arithmetical facts a sentence G_T such that G_T is true and undecidable in T iff T is consistent.

Now, numerous times the statement of the first incompleteness theorem essentially like the above was reformulated into something like:

Gödel's 1st incompleteness theorem gives us a method to produce from any consistent theory T proving basic arithmetical facts a sentence G_T which is true and undecidable in T.

A seemingly innocent change improving readability. However, this rewording considerably weakens the theorem to the point of being actually incorrect. For if T is inconsistent, the latter version gives us no information about the truth or falsity of G_T while the former does. Similarly, a well-intending person added a clarification to the note that the sentence G_T produced by the mechanism provided by Gödel's 1st incompleteness theorem is called "the" Gödel sentence of the theory, explaining that there are infinitely many formulas having the stated property of being true but undecidable in the theory. But this property is not at all what entitles a statement to be called a Gödel statement of T! The relevant property is that of the statement's being provably equivalent to its own unprovability in T or a suitable variation thereof (e.g. of Con(T)-->G being provable in T).

Also, someone apparently thinks that "provable in T" should be replaced by "included in T". If a theory is defined to be a deductively closed set of sentences, this is of course technically correct. A statement being included in a theory is not a concept people in general would be familiar with and the people who know that for a deductively closed set of sentences it means same as provability wouldn't use that phrase in any case. So I think "included in T" is in no way an improvement over "provable in T".

Someone has added a statement explaining the scope of Gödel's theorems

Gödel demonstrated the incompleteness of a theory of arithmetic, but it is clear that the demonstration could be given for any theory and language of a certain expressiveness.

Why is this necessary? How does e.g. "for any formal theory, it's possible to construct an arithmetical statement..." lead a potential reader to assume the theorem only applies to theories of arithmetic? Of course, if Gödel's original result was discussed it would be in place to mention that it generalized, but as the article is, the remark comes out of nowhere. Etc. Etc. But enough of this whining for now.

-- Aatu

Some comments:

1. Major rewrites of highly-visible and much-edited articles need to be undertaken more delicately and transparently than ordinary edits. It would be good to put an outline of your proposed changes here first. Then you might do the rewrite as a subpage of your user page, ask for comments, and copy it over once it's accepted. (That's what I did at definable number, except I didn't actually get any comments on the rewrite, so I just copied it after a decent interval. Article still has problems, BTW, but at least it's talking about a well-defined concept now.)
2. Your point on "G_T iff T is consistent" is certainly correct, but I'm not convinced it's the better way to say it. From the point of view of the foundational implications, such as the near-refutation of Hilbert's program and the consequent difficulties for the formalist school, it's not the interesting half of the theorem. If our foundational theories are inconsistent, who cares what happens to their Gödel sentences?
3. I still don't think the "maximal consistent subset" stuff is useful (don't know if that was yours or not). Independently of what sorts of subsets we can talk about, I just can't see any reason anyone would think a formalization of "the maximal consistent subset of T is consistent" is even a candidate for a formalization of "T is consistent".
4. Why don't you sign in? Have you forgotten your password? You could try the "e-mail new password" button at the login screen. --Trovatore 16:50, 1 December 2005 (UTC)

Truth of Gödel sentence

Yesterday I twice had to revert editors who were squeamish about using the word "true" for the Gödel sentence of a consistent theory satisfying the hypotheses of the theorem. These editors were probably (understandably) confused by the expositions of popularizers (not really blaming the popularizers either; they have a difficult task).

Executive summary: The Gödel sentence is a claim about the natural numbers. If you believe in the natural numbers as "real" objects, "out there", independent of our reasoning about them, then you must believe that the Gödel sentence is either really true or really false, whether or not we can prove it–the Gödel theorems, from this perspective, show the disconnect between truth and provability.

Now if you don't believe that, that's fine; there are many other possible philosophical perspectives. However, there is no more reason to be shy about discussing the Gödel sentence as something that's either true or false, than there is for timidness about the meaning of saying the theory is really consistent, and that's one of the hypotheses of the theorem. So if you want to take a formalist, or otherwise anti-realist, approach, you can, but if you apply it to the conclusion of the theorem, you should also apply it to the hypotheses. If you do that, and take the claim that T is consistent as some sort of circumlocution, then you can equally well do it for the Gödel sentence --Trovatore 20:06, 31 December 2005 (UTC)

Your reverts are an inappropriate promoting of a POV. The editors are right to be squeamish; whether or not the Gödel sentences are true is a very controversial philosophical point. -- Walt Pohl 02:39, 1 January 2006 (UTC)

Nonsense. You can be skeptical about whether they're true, but then you have to be just as skeptical about the meaningfulness of the hypothesis of the consistency of the theory, which has the same form (Π⁰₁). --Trovatore 02:56, 1 January 2006 (UTC)

You really don't see why it's POV? Philosophically, you can consider a statement to be true if it is a provable theorem. Then the Gödel sentence is not true. -- Walt Pohl 07:18, 1 January 2006 (UTC)

It's a provable theorem that, if T is consistent, then the Gödel sentence corresponding to T is true. So even by the philosophical position you propose, the text I restored is still fine, because it asserts the truth of the Gödel sentence only for a consistent theory. --Trovatore 07:29, 1 January 2006 (UTC)

Debateable. I'm not sure a strict formalist would accept your argument, since it requires either an intended model, or a metamathematical notion of truth. (Just to clarify, I don't particularly object to your argument; I just consider it POV.) -- Walt Pohl 16:13, 1 January 2006 (UTC)

You seem to think that formalists have a theory of truth that identifies truth with provability. That's not correct. Formalists simply dispense with a theory of truth altogether. They do make use of a linguistic convention where they refer to things as "true" when provable in some understood theory (so do non-formalists, for that matter), but it is clearly not that convention that controls here, but rather a disquotational one where "G_T is true" means exactly the same thing as G_T.

Now disquotationalism is a theory of truth, but you don't have to accept that theory to recognize what's meant here; it's just the obvious thing.

Essentially no one uses a theory of truth that identifies truth with provability in a fixed formal theory, because it's just untenable. Intuitionists, on the other hand, do claim to identify truth with provability, but they get away with it precisely by disidentifying provability with provability in any fixed formal deductive system. --Trovatore 02:35, 2 January 2006 (UTC)

Not true. Identifying truth with provability in a fixed formal theory (usually a ZFC or a fragment) is a reasonably common stance. Many mathematicians are practicing Platonists and professing formalists; from such a stance, if a statement can't be proven, then there's some doubt as to whether it's true.

I don't see how you can seriously contend that there is no POV issue here. The mere fact that we're disagreeing is evidence of it. -- Walt Pohl 03:18, 2 January 2006 (UTC)

I think you're simply wrong that there is any large contingent of serious mathematical logicians who identify truth with provability in a fixed formal system, in a way that would permit them to doubt the proposition "If T is consistent then G_T is true". (Note that this is not the same as saying that they would believe G_T is true without the hypothesis that T is consistent (and the other hypotheses I've left out); that was kind of my point in the third paragraph of my original text in this section.)

You're free to try to find citations, of course, in which case we could mention it as a minority POV. But I'm afraid, not to be rude, that I don't find the fact that you personally are arguing, to be very compelling argument that such a position exists among experts. I find no evidence that you are a mathematical logician, though you do seem to be an informed amateur. --Trovatore 04:22, 2 January 2006 (UTC)

Too late, you've already been rude. I could tell from the general tenor of your comments that it was only a matter of time before you tried to play this sort of game. I'm an algebraist, not a logician. This is Wikipedia, not the Official Website for the Opinions of Logicians. Godel's theorem is not just a theorem in mathematical logic; it is part of the general culture of mathematics. Now, if you were arguing about a question of mathematical fact, that would be a different matter. But we are discussing a philosophical question about the foundations of mathematics, which is not the sole property of mathematical logicians. I know that some mathematicians would object to the characterization of the Godel sentence is true because I experienced it firsthand.

I don't think a lot of space in the article should be wasted on the point of view I outlined. All I want is that the intro be POV-neutral. Maybe your point of view is common among mathematical logicians, but it's still a POV. -- Walt Pohl 05:16, 3 January 2006 (UTC)

Look, it's just a simple fact that "Con(T)→G_T" is a theorem of a very weak metatheory; you don't even need all of Peano Arithmetic. That's not philosophy. Now, how would you translate the above into English? "If T is consistent then G_T blank?" You could say "holds", but then when someone asks "what does 'hold' mean?", what do you say?

Consider your example of a formalist who uses "true" to mean "provable in ZFC"; certainly there are people who do that as a general rule. Such a person would have to admit "Con(ZFC)→G_ZFC" because that's a theorem of ZFC (and indeed of much weaker theories). Now, could this person really deny that under the assumption that ZFC is consistent, G_ZFC is true? If so, how would he phrase it? --Trovatore 05:51, 3 January 2006 (UTC)

I've added a footnote explaining this. --Trovatore 22:16, 5 January 2006 (UTC)

I think the article as it stands is very much misleading. The point is that saying that a sentence in a logic is "true" but not provable (in that logic) is not particularly meaningful. One can say that in a class of models a particlar sentence holds, or even that a sentence holds in all models, so that it is valid or a tautology. For any theory T, the Godel sentence G does not hold in all models. Indeed T + G and T + not G are both consistent extension of T. There are models in which G is true and models in which G is false.

The reason why most people think that G must be true is that they are working in a particular model -- where the Godel encodings are intended to represent statements about provability and well formedness -- so G feels like it ought to be true, but if one were to given a different interpretation of the encoding (which one might in a different model) then G would be false.

Now it is the case that (in PM at least -- I'm not sure if one can prove this in general but I think so) those models in which not G holds (so which model the extension T + not G) have non-standard models of the natural numbers inside them. On that basis one might have a reason to prefer G to not G. But that preference is purely meta-mathematical, if you lived inside the model you would not be able to tell if it was standard or non-standard (by definition). One way of understanding the incompleteness theorem is that it illustrates the impossibility of recognising that one is contained in a non-standard model.

I think its right to say that the extension by not-G is always omega inconsistent and therefore all its models will be non-standard. The way to understand G is it makes a statement about numbers as you understand them, but that T doesn't capture that understanding completely (because it fails to exclude non standard models by definition), so even though G is "true about the natural numbers" which can be part of the real world if that's how you conceptualise them, T doesn't capture that conception (hence "incomplete). Francis Davey 17:12, 20 May 2006 (UTC)

I would prefer not to have the opening of the article state that the Godel sentence is true. I'm not sure even Godel went quite that far.

By the way, I was (at one time) a research fellow in formal logic, and I certainly identify truth with proof (in any particular system). Francis Davey 21:09, 19 May 2006 (UTC)

Self-contradiction in one-to-one correspondence (About the incomplete totality of the set of all prime natural numbers)

Essay moved to User:BenCawaling/Essay. Gandalf61 08:28, 14 April 2006 (UTC)

Why is there a section on Gentzen?

The article is supposed to be about the Gödel theorems; I don't understand why there's a long section on Gentzen's result. This should be split off to a separate article. By the way, Gentzen's consistency proof has been on requested articles for a while. One solution would be to just cut-and-paste the current section to create that article, but when I added it to requested articles I was hoping for a bit deeper treatment than is given here. But in any case the section doesn't belong in this article, though the result should certainly be mentioned and linked to. --Trovatore 23:15, 14 February 2006 (UTC)

Went ahead and did the cut-and-paste. Someone (Chalst?) needs to give Gentzen's consistency proof some serious TLC. --Trovatore 04:37, 15 February 2006 (UTC)

Proposed split

I propose that that part of the content of Gödel's incompleteness theorems that is specific to the first or the second theorem should be split off to Gödel's first incompleteness theorem or Gödel's second incompleteness theorem, respectively (currently these are redirects to the main article). The remainder of the article, the part that's common to both theorems, would stay here, and the individual theorems would retain short sections with a brief exposition and a {{main article}} pointer to the "first" and "second" articles.

Reasons:

• The article is currently too long. Splitting off Gentzen's consistency proof helped, but not enough. This is not just a technical issue (that issue is fading as old browser versions fall into disuse); the length is a problem for readers trying to understand, and editors trying to keep the article in good global shape.
• The theorems are quite different from one another in terms of application. The second theorem can almost be viewed as a corollary of the first, but is the one that is usually more important in actual practice in mathematical logic. On the other hand the first theorem is the one to discuss in an elementary discourse on the limitations of formal deductive systems. --Trovatore 19:58, 28 February 2006 (UTC)

Mere mortal has a request

The topic of Gödel's incompleteness theorems is something I have come across occasionally, and as a Major Theory in the History of Mathematicts it seems something I should have a basic handle on. That said, are there any examples that can be given to speak about? In truth, the article as written doesn't let me get it. My background includes advanced calculus from college where we used a textbook by Spivak, a course in basic number theory, and a course where we were studied the Cantor set and Lebesgue integration. So I'm not exactly a dolt. However, I think I would need a major leap of sophistication to really understand the article as written. Given that this is a general encyclopedia, any idea on how to bridge this? In the spirit of Wikipedia I'd do something myself, but in this case I KNOW I could only damage the article by my efforts. Steve Kd4ttc 01:46, 8 March 2006 (UTC)

You have a good beef, I think. The article should be reorganized to give some context before leaping into the technicalities (in addition to the changes I mention above about splitting out the articles on the two individual theorems). I hope someone will take this on (I'm afraid it isn't going to be me, at the moment). --Trovatore 22:13, 8 March 2006 (UTC)

clarification request

This exists for any system with zero, any finite, or indeed, any infinite number of axioms on which the system is based.

This sentence appears to contradict the paragraph that follows it, specifically the claim that if you start with infinitely many axioms, you'll still have statements available to add to your system as axioms. Dmharvey 13:32, 12 March 2006 (UTC)

The paragraph from which you took that statement is wrong, but it's a little hard to find a good fix. The fact is that you can have a complete and consistent set of axioms for arithmetic, for example the set of all true sentences of arithmetic. What you can't have is a computably enumerable such set of axioms. That's what the following paragraph is trying to explain. Maybe you'd like to have a shot at rewording this. I don't want to just throw "computably enumerable" into the former of the two paragraphs, because that sort of defeats the purpose of finding a non-technical explanation. Perhaps the two paragraphs could be merged in such a way that they don't say anything so blatantly false as they do now. --Trovatore 17:45, 12 March 2006 (UTC)

Took a shot at it. The next paragraph following may be a little redundant now. --Trovatore 18:09, 12 March 2006 (UTC)

Thanks, that makes much more sense now. Dmharvey 20:38, 12 March 2006 (UTC)

Unfortunately, I think the statement of the theorem without mentioning the requirement that the axioms be computably enumberable is misleading: without this condition, anyone can easily prove the theorem wrong, which makes the condition more than a technical afterthought. Refering to a "set" of axioms only makes the matter worse, as most people who have studied some mathematics are familiar with defining sets in very indirect ways. But even if it referred to a "list" of axioms, people might picture the list as being as arbitrary as, say, the decimal for a real number. I think the theorem should be expressed in terms that most people would understand: "Here a theory refers to a computably enumberable list of axioms, i.e. one for which there is a finite computer program that could print out the (possibly infinite) set of axioms."

In addition, the word "true" needs explaining, as it is probably a much misunderstood concept. Would something along the lines of "There is no model of the theory in which the statement is false" be ok? Elroch 13:06, 20 March 2006 (UTC)

Model of which theory? If you mean the original theory you're talking about, no, that would be a false claim; there is a model in which it's false, otherwise you'd be able to prove it from the theory. See Gödel's completeness theorem.

The Gödel sentence is a statement is about the natural numbers (we can code statements about the naturals into the language of the theory; that's one of the hypotheses), and when we say it's true we mean it's true about the natural numbers. The genuine natural numbers, not some model that just happens to satisfy some of the same axioms. But see the footnote about the disquotational sense of the word "true". --Trovatore 15:02, 20 March 2006 (UTC)

Thanks, my statement about models was in error (although I'm not sure why you suggested a model might only satisfy some of the axioms). Would you agree that, in general, any statement for which neither it (nor its converse) is provable within an original theory may be added as an axiom (or its converse added as an axiom) to form a relatively consistent theory, and models of either extended theory would be a model of the original theory as well? And if so, we can create a model for the natural numbers in which the Gödel statement for the original theory is false, despite the fact that it was ""true"" in the original theory? Elroch 18:46, 20 March 2006 (UTC)

Basically right, modulo a few things:

1. Where you say "converse" I think you mean "negation". (Yes. Elroch 02:09, 21 March 2006 (UTC))
2. Yes, if T is consistent, then either its Gödel sentence G_T, or the negation ¬G_T, may be added to T, and the resulting theory will be consistent. However it does not follow that the two possible extensions have equal epistemic status. If you want your theory to say only true things about the natural numbers, you may not add ¬G_T; even though the result would be a consistent theory, it would prove false things about the natural numbers.
3. For the last question, it depends on what you mean by "model for the natural numbers". The natural numbers already are a model. They're a model, say, of Peano arithmetic. Yes, there will be some other model of Peano arithmetic in which the Gödel sentence G_T is false. However that model will not be isomorphic to the genuine natural numbers. --Trovatore 20:44, 20 March 2006 (UTC)

Could you elaborate the concepts of "isomorphic" and "genuine" here? I'm not very happy with the idea that there is an intuitive concept of the natural numbers which is stronger than any axiom scheme. Clearly adding a computable set of axioms would not solve the problem. I am happy with the result that G is independent of our theory, but in what formal system is the result that G is "true" mechanically provable (without adding an axiom that obviously implies it)? Can the procedure of discovering a new "true" but unprovable result and adding it as an axiom be repeated a countable number of times by a computer program? How useful is the natural idea of continuing this process using ordinal recursion? Elroch 02:09, 21 March 2006 (UTC)

"I'm not very happy with the idea that there is an intuitive concept of the natural numbers which is stronger than any axiom scheme." This issue is something that used to bother me a lot, and still would bother me except that I don't really care about this kind of thing much any more :-) I'm too busy trying to learn actual number theory :-) But seriously, I asked someone knowledgeable on these matters once and he replied roughly as follows. (I don't know if I totally believe this argument, but here it is anyway.) What we want to do is assign a boolean value, true or false, to every statement about the natural numbers. So do this by induction on the length of the statement. For example, if your statement is "for all n, P(n) holds", then this statement is declared to be true if and only if P(1) is true, and P(2) is true, and so on. The induction works because P(1) is a shorter statement than "for all n, P(n) holds", etc. I haven't asserted anything at all about the provability of the universal statement within any particular formal system, or whether it can be computationally verified. All you have to believe is that it makes sense to ask "Is it the case that P(1) is true, and P(2) is true, and so on". Similarly for existential qualifiers, and all the various logical connectives. Then you have to believe that it really is justified to carry out induction in this way. If you believe those things, then you should believe that every statement about the natural numbers is either true or false. I'm sure Trovatore can set me straight if I'm spouting crap. :-) Dmharvey 02:26, 21 March 2006 (UTC)

Gödel theorems, realism, formalism

Wow, this section is getting really long. I haven't entirely digested what either Elroch or Dmharvey's saying so I won't try to respond to specific points from what they've said. Let me just say this:

The cleanest and easiest way to understand the Gödel theorems is from a Platonist perspective. Gödel himself was a Platonist, more correctly called an "object realist", ^[1] or at least became one eventually. In his later years he claimed that this had always been his view, but Martin Davis has rather convincingly demonstrated that Gödel's memory on that point was faulty. I would not be at all surprised if it was the incompleteness theorems themselves that had a big part in his "conversion" to realism.

From the realist perspective, the theorems have a very plain meaning, and whether they're surprising or not, they are not at all confusing. They simply say that, while we can assert certain truths about the naturals that we find intuitively clear, and then prove other truths from those, this method is not sufficient to capture all truths about the naturals, and in particular (2nd theorem) is not sufficient to prove the formal consistency of the collection of truths asserted.

On the other hand, for a formalist who would like to reduce the notion of "truth" to provability in some formal deductive system, the theorems are much more troubling. He's faced with a choice between several unpleasant options:

1. Disidentify truth with provability (so then what is truth?)
2. Give up on the notion of truth altogether, and focus only on provability, but call it "truth" when it's not confusing
3. Allow statements to be "neither true nor false"—and then explain, or leave unexplained, why he continues to accept excluded middle as part of his formal deductive system

None of these options really have a happy outcome, with the possible exception of the first one, which is a step towards realism.

My view is that a big part of the massive confusion that we find in popular accounts of the Gödel theorems results from these attempts to explain them while still maintaining a formalist perspective. It can be done, but the pitfalls are many, and trying to get it across in simple language is probably just doomed. --Trovatore 03:45, 21 March 2006 (UTC)

1. ^1 I should say here that Donald A. Martin, who's done a lot of work on the issue and certainly knows much more about it than I do, believes that Gödel was really a "concept realist" rather than an "object realist". My characterization of him as an object realist is based on a questionnaire to which he responded, cited by Davis. I don't remember Martin's evidence, but he gave an impressively researched talk on the subject at a recent ASL meeting.

---

One specific point of Elroch's that's worth responding to, now that I've read it:

I am happy with the result that G is independent of our theory, but in what formal system is the result that G is "true" mechanically provable (without adding an axiom that obviously implies it)?

So given a theory T, the Gödel sentence G_T is formally provable in the theory PA+Con(T), where PA is Peano arithmetic and Con(T) is the arithmetic formalization of the claim "T is consistent". Since the consistency of T is a hypothesis of the theorem, the claim that G_T is true has an interpretation that should be acceptable even to a formalist. That's the point made by the footnote in the main article, about the disquotational sense of the word "true". --Trovatore 07:14, 21 March 2006 (UTC)

One point that seems of interest is the distinction between statements that we know must be true or false, but can't prove either way yet, and statements where this is not so obvious. For example, a statement of the type "every natural number satisfies a certain property (which we could check in finite time for any individual number)" covers many conjectures in number theory, and it seems obvious it must be true or false (finitists might disagree?), but is unclear whether it might be provable either way in an axiomatization of arithmetic. Other statements, (the existence of a particular large cardinal, for example), seem intuitively to have less of a "natural" truth. Given that every (computably enumerable) theory has a countable model, maybe this distinction is not as big as it appears (could we, in principle, iterate through the objects in a Löwenheim-Skolem model in an analogous way?), but many people would feel happier denying the law of the excluded middle in the latter class of statements. Elroch 01:24, 22 March 2006 (UTC)

There are certainly lots of attempts to make such distinctions. Personally I don't think any of them work very well; they all wind up drawing what strikes me as a fairly arbitrary line somewhere between what's taken to be real and what's not. The line can be drawn in many many different places, which is part of what contributes to the sense that it's arbitrary.

But back on topic, the Gödel sentence of a theory, being a Π⁰₁ assertion, is going to be on the "real" side of most such lines. --Trovatore 03:07, 22 March 2006 (UTC)

On reflection, I realised that a better way to put it was that any statement that can be expressed as a halting problem is "obviously" true or false, regardless of whether it is possible to prove it. Many such statements are, of course, independent of the theory in which they occur. My question would be which statements, if any, in theories such as arithmetic and set theory do not fall into this category? (I suspect that a judicious use of a countable model might make it obvious, in this sense, that all statements are true or false, even if they are independent) Elroch 10:43, 22 March 2006 (UTC)

It occurred to me that the sort of statements that might cause problems are ones like the statement $1+1=0\;$ in the theory of algebraically closed fields (ACF). Presumably the Lôwenheim-Skolem model for ACF is a countable model of the complex numbers, in which $1+1\neq 0\;$, but of course there is another model for ACF which is the algebraic closure of the field with 2 elements, in which $1+1=0$. $1+1=0\;$ is not inherently true in ACF, but neither is $1+1\neq 0\;$. Is there a sense in which the Lôwenheim-Skolem model is a minimal one, in that there are neither unnecessary objects, nor unnecessary statements about those objects? Perhaps a more on-topic question would be are there any (more obscure) examples of such statements in arithmetic? I suspect this discussion is not going to lead to any input to the article, so I will attempt to restrain myself from any further excursions. Elroch 12:52, 22 March 2006 (UTC)

...except to say, I should not have been referring to "the" Lowenheim-Skolem model, as its construction uses the axiom of choice. Also, it might be worth mentioning that the existence of models of arithmetic of all cardinalities (discussed at [2]) means the situation is not so different, in a formal sense, in arithmetic. The theorem that any theory that has an infinite model has models of all cardinalities is rather surprising. Elroch 13:20, 22 March 2006 (UTC)

Godel for Dummies, or clarification, or "GIVE ME AN EXAMPLE"

First, i am not a mathmetician, in fact I'm not very good at math, which probably puts me in the majority or at least a very significant minority of the people in the world and of the people who read wikipedia. That said, even in places where the article claims to, i think the exact words are to put it "in plain english," it fails. To put this in mathmatical terms, let me give you a definition. If you understand this article then you are already familiar with the concept. If you do not understand this article then you are not familiar with the concept. If you are not familiar with the concept then you do not understand this article. If you are familiar with the concept then you will understand the article. Someone needs to give a serious paragraph break after each theory and EXPLAIN, it in complete laymens terms. If brian greene can explain string theory in laymen's terms so can this article about godel's incompleteness theorems. —The preceding unsigned comment was added by 24.218.178.198 (talk • contribs) 00:54, 22 April 2006 (UTC)

So out of curiosity, if you don't understand the theorems, then how can you know whether they can be explained to laymen or not?

Just the same, I think you're right that this article could be improved in that wise (and several others, by the way). It's not tops on my personal list. Hopefully someone will get around to it sooner or later. But it's a risky undertaking; most attempts to popularize the theorems are filled with unwarranted philosophical conclusions, if not outright mathematical howlers. --Trovatore 06:18, 22 April 2006 (UTC)

Since everyone who understand's Gödels incompleteness theorem was at some point in their life a layman, it follows that it can be explained. But, as with many existence proofs, that statement does not say exactly how to go about it. An encyclopedia has as its mission explaining things to lay folk. If you are really an expert in a field Wikipedia is not where you go for references for your publications. This article is written at an expert in set theory level. It needs at least a section that is accessible by non-mathematicians. Kd4ttc 14:35, 24 April 2006 (UTC)

Actually, I can think of three quite distinct audiences for this article. (1) Non-mathematicians. (2) Mathematicians with only passing knowledge of logic. (3) Mathematicians with expert knowledge in some area of logic (set theory, model theory, maybe some parts of computer science, etc). I'm in category (2) and I find the article is generally pretty good. I'd be very surprised if the article was intended to be aimed at people in category (3), it would be far more technical if that were the case. (I don't know quite what conclusion to draw from all this.) Dmharvey 15:29, 24 April 2006 (UTC)

(Second that! Kd4ttc 17:19, 24 April 2006 (UTC))

It proves it can be explained, but doesn't prove it can be explained to any particular person. It's still possible that some minds cannot grasp it. Consider a senile person, for example. Furthermore, it doesn't prove that it can be explained with a reasonable amount of Wikipedia reading.

Nonetheless, I have a strong suspicion that it is possible for this article to explain the theorems at least at a surface level to a person with basic mathematical competence (e.g. someone who can do algebra), because they're said to be so important. If they are applicable only in a world in which a handful of specialists live, they wouldn't be touted so highly. I'm not talking about proving the theorems or explaining how to use them, but merely stating what they say. Bryan Henderson 23:55, 26 November 2006 (UTC)

You're more than welcome to give it a shot. This article has needed some serious attention for a long time, and while the issue you're talking about is not the only one that needs to be addressed, it's certainly an important one. If you want to try your wording out on the talk page first, I'm happy to give my opinion. --Trovatore 02:37, 27 November 2006 (UTC)

I find the "existence proof" unconvincing; I don't know anyone who understands the theorems who learned them from an encyclopedia article. We can't expect an article that needs to be kept within 50K characters or so to substitute for study at the graduate level.

On the other hand, I do agree with the criticism. I don't think this is a "good article" at all at the moment; it's poorly organized and motivated (and rambles on about matters that probably should not be in the article at all, like the "minds and machines" stuff).

There are serious obstacles to writing a good article about this topic within the WP framework. The article needs to accomplish so many things. First, it has to explain that the theorems express limits on formal deductive systems. For that to be useful to a non-logician, it needs to say something about what formal deductive systems are, and how they relate to the ways mathematics is done in practice and to mathematical truth. Here we already run into trouble, because these are extremely contentious points. If we try to represent the major viewpoints in a balanced way, the non-logician is likely to lose the thread before we even get to the statement of the theorems, their history, their proof sketches, or their applications.

Splitting out the details of the 1st and 2nd theorems to their own articles, as I suggested a while ago, would help; "minds and machines" should definitely go to its own article. Something about the "meaning of the theorems" needs to come much earlier (but certainly not the whole long-winded section that currently exists), and so does some historical context (discussion of the Hilbert Programs).

Can the WP methodology really produce a coherent, well-organized article on this topic, with everyone throwing in his two cents? I'm skeptical. It's a pity because this is a very good topic, but I'm not sure we'll ever truly have a good article. --Trovatore 16:58, 24 April 2006 (UTC)

I think you just spit out a good plan for the approach. I think it would be reasonable to point readers to some background information first. An introduction could be included indicating the theorums apply to proofs in logical systems and an introductory statement about not applying to all systems would keep folks from overreaching on implications. But an example would still be nice. For example, what statement about integer arithmetic cannot be proven with the axioms of algebra, or what statement cannot be proven about geometry in one of the axiomatic systems of geometry. Such an example would give the reader a sense at what level of sophistication Gödel's theorems operate. I second Dmharvey on the audience issue. Kd4ttc 17:08, 24 April 2006 (UTC)

Well, let's talk about what's meant by an "example". In some sense the article already gives examples. An example of a true statement of arithmetic that cannot be proved in Peano arithmetic is G_PA, the Gödel sentence for PA, which asserts "I cannot be proved in PA". This can be translated into the form "for every natural number n, P(n) holds", where P(n) is some complicated property of natural numbers, not easy to describe, but in principle checkable by a computer program. There's an example for the first incompleteness theorem. Not a very conceptual one, of course.

From your remarks about geometry I'm guessing you'd like to do something like start with a formalization of Euclidean geometry, remove the parallel postulate, and observe that the parallel postulate can neither be proved nor disproved from the remaining axioms. That's an example of independence, but not one that has much to do with the current article. The way we know that that deductive system is incomplete has nothing to do with the proof of the Gödel theorems; I don't think that system (in its usual formalizations) is even strong enough for the Gödel theorems to be applicable. --Trovatore 19:43, 24 April 2006 (UTC)

delisting as "good article"

I've changed the {{GA}} template to {{DelistedGA}}; I don't really think this is a "good article" as it stands. (I'm not terribly optimistic that it ever can be, using WP methodology; I'm afraid it's always going to look like a giraffe, which is a horse designed by committee. But maybe it can. It just isn't now.)

I'm supposed to explain which criterion or criteria I think it fails. The most important criterion that it fails is the very first one; the article is not well written. Specifically:

1. It doesn't have a good lead section (this is the easiest thing to fix)
2. It doesn't follow a clear logical structure.
   1. Rather than starting with (at least a little) motivation and historical context (say, Hilbert's programs), it jumps straight into a quote from Gödel's paper, using notation specific to that paper and not standardly used.
   2. The "meaning", "misconceptions", and "discussion" sections all treat roughly the same topic, but in a disjointed manner; they need to be unified into a single section and mercilessly edited for flow.
   3. The "minds and machines" section does not belong in this article at all; it should be a separate article.
   4. The first and second theorems have their own sections, followed by their own proof sections further down the article; these need to be moved to Gödel's first incompleteness theorem and Gödel's second incompleteness theorem.
   5. The "examples" section is irrelevant and should probably just be removed. These are examples of logical independence, not examples of the Gödel theorems.

I think the article does meet most of the other criteria for being a good article. I think it's mostly factually accurate and verifiable (haven't read the whole thing through recently), has broad coverage (too broad, really), is relatively NPOV and stable, and it's hard to see what images could really be added. But the writing is just so bad that it can't possibly be a GA. This is no one person's fault, which is maybe the heart of the problem. --Trovatore 20:22, 8 May 2006 (UTC)

Gobblygook

I'm a statistics undergraduate student who took a philosophy of mathematics course in which we covered the godel incompleteness theorem. During this course I remember the professor clearly explaining the incompleteness theorem in a way that was relatively easy to understand. (I don't remember what tactic he used, be it simple examples etc or I'd remember the theorem)

And I STILL can't make heads nor tails of this article having forgotten what the theorem means exactly. The language is way more overspecialized then it needs to be.

Since you don't seem to remember how the professor made Gödel simple, may we have his contact address? I'd love to see this article, and all mathematics articles, greatly improved. --DryaUnda 19:51, 28 June 2006 (UTC)

Douglas Hofstadter

In respect of Douglas Hofstadters book Gödel, Escher, Bach: an Eternal Golden Braid I think it could be apropriate to at least mention it! I think it is one of the best laymen explanations of gödel's incompleteness theorems, and about it´s consequences for formal systems in general, and I think many would agree on that! It would also be fair and right in my opinion to quote some of the ideas that Hofstadter presents in his book about the implications of gödel's incompleteness theorems and the mind.Mandelum 20:45, 21 May 2006 (UTC)

First let me say that GEB is a fantastic book. It's marvelously constructed and immensely entertaining. However, for all the justified criticisms that have been leveled at this article in regard to its comprehensibility, I really doubt that GEB is a very good resource for this purpose. At most I could see bringing in the notion of "quining" or the "yields falsehood when preceded by its quotation" predicate, but that would be only in the details of the proof, and currently we don't really get to that level of detail anyway.

As for the "minds" stuff, that doesn't belong in this article at all; it should be a separate one. These are theorems of mathematics. They have implications in philosophy, but philosophy of math, and even these tend to be of the form "such and such a foundational account isn't going to work; better find something else"; the theorems won't tell you what the something else is. Philosophy of mind, in my view, is outside the scope of a mathematical theorem, and while there should be an article about the connections that workers in that field have found or alleged, it's just a distraction in this article. --Trovatore 14:21, 22 May 2006 (UTC)

I completely respect your opinion and your guidlines, and I think you are correct! But I still propose that a small link could be added in the See also section with a discription of the unscientific nature of the book since I think many of the general readers who are interessted in this topic might find GEB a perfect introduction on Gödel and the things that may have led them to this article. But I totally agree on the princpile of keeping things in their separate pages. --Mandelum 19:10, 22 May 2006 (UTC)

Oh, for sure. The book is already in the references section, but given that there's a WP article about it, I can't seem any harm in putting a link to it in "See also". --Trovatore 19:31, 22 May 2006 (UTC)

Incompleteness vs Temporal logic

I would like to ask an expert on Gödel's Incompleteness Theorem in what manner or in what way it regards (respects) and deals with Temporal logic? -- PCE 22:46, 21 May 2006 (UTC)

These theorems have nothing to do with Temporal logic. Paul August ☎ 23:12, 21 May 2006 (UTC)

What form or type of logic then would you classify these theorems as having something to do with? -- PCE 23:52, 21 May 2006 (UTC)

Mathematical logic. Paul August ☎ 00:08, 22 May 2006 (UTC)

As relating to Mathematical logic then would the theorems have anything to do with or cover such issues as the incorrectness or inability or unavailability of constructs such as x=x+1 or y(x(i)) being expressed using conventional mathematical notation? -- PCE 00:30, 22 May 2006 (UTC)

No. Paul August ☎ 00:51, 22 May 2006 (UTC)

--Kikl 21:51, 23 July 2006 (UTC)

Reals and Complexes are sets with complete Axiomatizations ?

This section has been moved to the arguments page; please continue there. --Trovatore 20:31, 27 July 2006 (UTC)

Suggestions for improvement

The article as it stands does not give any complete statement of the hypotheses. The previous section of the talk page shows why this is misleading. Moreover, the article states that the key property necessary is that the theory be recursively enumerable; but the theory of real closed ordered fields is complete, and thus both decidable and recursively enumerable. This ought to be fixed.

Later, the article says

The following rephrasing of the second theorem is even more unsettling to the foundations of mathematics: If an axiomatic system can be proven to be consistent and complete from within itself, then it is inconsistent.

This rephrasing may be unsettling for foundations as Hilbert envisioned them, but it is not unsettling to foundations as they are generally considered nowadays (to the extent that they are considered at all). The sentence confuses foundations in general with Hilbert style foundations.

CMummert 02:33, 24 July 2006 (UTC)

{{talkarchive]]