Talk:Gödel's incompleteness theorems

From Wikipedia, the free encyclopedia

This is the talk page for discussing changes to the Gödel's incompleteness theorems ARTICLE. Please place discussions on the underlying mathematical issues on the Arguments page. Non-editorial comments on this talk page may be removed by other editors.
Please sign your comments using four tildes (~~~~). Place comments that start a new topic at the bottom of the page and give them == A Descriptive Header ==. If you're new to Wikipedia, please see Welcome to Wikipedia and frequently asked questions.	Talk page guidelines Please respect Etiquette, assume good faith and be nice.

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	A-BB+ Class	Top Priority	Field: Foundations, logic, and set theory
One of the 500 most frequently viewed mathematics articles.
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Needs proper introduction, and consider breaking up lengthy sections. Tompw 18:58, 7 October 2006 (UTC)

	Philosophy Portal This article is within the scope of the WikiProject Philosophy, which collaborates on articles related to philosophy. To participate, you can edit this article or visit the project page for more details.
???	This article has not yet received a rating on the quality scale.
???	This article has not yet received an importance rating on the importance scale.
Additional information: Related task forces (core areas): Epistemology Logic

Gödel's incompleteness theorems was a good article, but it has been removed from the list. There are suggestions below for improving the article to meet the good article criteria. Once these are addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake. Delisted version: May 8, 2006

Archives

/Archive01 /Archive02 /Archive03

Contents 1 complete and consistent 2 JR Lucas is Inconsistent 3 No need for photo of Goedel 4 Confusing to laymen/laywomen 5 A rather difficutl question 6 Trying to falsify Godel 7 second incompleteness theorem 8 Theorem #1

[edit] complete and consistent

Double check the following sentence:

• Furthermore if the system can prove that it is consistent, then it is inconsistent.

Shouldn't that be

• Furthermore if the system can prove that it is complete, then it is inconsistent. —Preceding unsigned comment added by 131.111.16.20 (talk) 14:01, 13 December 2007 (UTC)

You are right that if the system proved itself complete, it would be inconsistent. Goedel's second incompleteness theorem establishes that a particular sentence expressing the consistency of the theory cannot be proven in the theory itself, if the theory is consistent and meets the other hypotheses of the incompleteness theorem. That is what the first bullet above is referring to. — Carl (CBM · talk) 14:44, 13 December 2007 (UTC)

Hmm? An inconsistent theory is "complete" by most definitions (not only does it prove every sentence or its negation; it proves every sentence and its negation), and it's certainly possible for a consistent theory to prove itself inconsistent. So for example PA+¬Con(PA) is consistent, but proves that it's inconsistent, and therefore complete. --Trovatore (talk) 18:11, 13 December 2007 (UTC)

My comment that a theory that proves itself complete is inconsistent is only correct for theories satisfied by the standard model. — Carl (CBM · talk) 18:16, 13 December 2007 (UTC)

Which are the inconsistent theories satisfied by the standard model:-) ? --Trovatore (talk) 18:17, 13 December 2007 (UTC)

Indeed; it seems there isn't much content there. But hopefully you can see the argument I had in mind. — Carl (CBM · talk) 18:19, 13 December 2007 (UTC)

A less content-free way of saying it would be: a theory that proves itself complete will be ω-inconsistent. — Carl (CBM · talk) 18:21, 13 December 2007 (UTC)

What's the "standard model"? Wiki's standard model has to do with physics and particles. Bill Wvbailey (talk) 23:08, 13 December 2007 (UTC)

I think we're discussing theories of arithmetic here, so the standard model would be the genuine natural numbers with addition and multiplication. A "nonstandard model" would be one that satisfied many (or even all) of the same first-order sentences as the genuine naturals, but which contained fake natural numbers that can't be matched up with any of the true ones. --Trovatore (talk) —Preceding comment was added at 23:15, 13 December 2007 (UTC)

So it's more or less what Enderton calls "first order logic" (i.e. more or less Goedel's system: propositional logic, PA, predicate logic's ∀, identity =, enough recursion theory to form + and * )? Is this a "common phrase in the industry"? Should this phrase be disambiguated? Thanks. Bill Wvbailey (talk) 23:46, 13 December 2007 (UTC)

(←) The standard model is a structure, not a logical system. It's the intended model of the Peano axioms: {0,1,2,3,...}. We don't need the phrase in our articles, which is why I think it has no article. — Carl (CBM · talk) 23:50, 13 December 2007 (UTC)

[edit] JR Lucas is Inconsistent

The argument given by Russell and Norvig (Artificial Intelligence: A Modern Approach) is an excellent refutation of J. R. Lucas' supposition that because computers are essentially limited Turing machines, which being formal systems 'stronger' than arithmetic, and are thus limited by their own 'Godelian statement' - J. R. Lucas further draws the conclusion that this limitation precludes 'machine intelligence'.

The refutation Russell and Norvig use states thus:

p = J.R. Lucas cannot consistently assert that this statement is true.

Thus demonstrating that J. R. Lucas is himself limited by his own 'Godelian Statement' and by his own definition, he has rendered himself as lacking intelligence (Chapter 26 - Philosophical Foundations - AIMA by Stuart Russell and Peter Norvig.)

Shouldn't we include this?

-- 86.129.93.182 (talk) 01:56, 12 January 2008 (UTC)

[edit] No need for photo of Goedel

I see no need for a photo of Goedel at the top of the article. I generally feel images should be used only when they deepen the reader's understanding of the topic. This is particularly true of non-free images, which according to WP:NFCC#3 may be used only when "necessary"; in this case, I believe the photo of Goedel is not permitted by our nonfree image policy. But even if it were a free image of Goedel, I don't see how it contributes to the reader's understanding of the topic, and wouldn't support it without seeing a convincing reason. — Carl (CBM · talk) 18:56, 12 January 2008 (UTC)

Goedel deduced the Goedel Incompleteness Theorems. That's probably why there should be a picture of him. Plus, he's kinda funny looking, and that helps to support my theory that most mathematicians are funny looking people. Niubrad (talk) 01:12, 6 February 2008 (UTC)

[edit] Confusing to laymen/laywomen

Any way the writers/editors could make this article comprehensible to the average reader who does not have a degree in mathematics or physics? I'm not talking about "dumbing it down" just not assuming a lot of knowledge on the part of the reader which one could only get in upper division university classes.

This is a matter of communication more than anything else. I believe the information in this entry can be accurate but also made more understandable to the average user (which I think is the goal of Wikipedia). This is not Encyclopedia Mathematica, this is a reference source used by the general public. I don't mean these comments as a slight to the writers of this entry, more of a challenge to write copy that is both informative and basic to understanding this work.Nwjerseyliz (talk) 21:01, 12 January 2008 (UTC)

There is a complete lay-comprehensible proof on the talk page of this spin-off article. It's in section 8, under the title "Proof of Godel's Theorem". That proof used to be on this page, but it was considered inappropriately written. It was too short and too comprehensible. If you like it, feel free to cut and paste it into the body of the article. I have gone through too much censure to do it again.Likebox (talk) 22:39, 12 January 2008 (UTC)

This is a willful misrepresentation on the part of one aggrieved editor regarding the alternative 'proof' (so-called). Please review the talk page archives for a the full, complete, correct record of the discussion, and the outcome. While the article as it is certainly could be improved, made more accessible, can we please _not_ reignite that particular bonfire? —Preceding unsigned comment added by 65.46.253.42 (talk) 22:52, 30 January 2008 (UTC)

I am not going away. I'm just waiting for the other people here to come to their senses. The only reason I am responding at all is because of the "so called" parenthetical. The proof is complete and correct, and it is equivalent to Kleene's in its logic, but some people here had a hard time following it at first. It's very easy.Likebox (talk) 18:24, 31 January 2008 (UTC)

[edit] A rather difficutl question

I have always been quite put off by Godel's theorem. In the system that I normally use, I used Godel's formulation to find a statement that it could not prove, loaded its inverse as an assumption, and found the inverse could be quickly reduced to a contradiction. Is Godel's theorem sufficiently weak that it only requires that statement to not be reachable from the ruleset (it was not as it contained a reference to itself and would have had infinite length in my notation) or am I completely missing the point here? 75.42.82.54 (talk) 04:21, 15 February 2008 (UTC) JH

Given some adequate formal system T, the statement in Goedel's theorem will not be disprovable in T. If you believe you have done so, there is an error of some sort in your analysis. The statement also will not be infinite; it will be an ordinary, finite formula. — Carl (CBM · talk) 13:36, 17 February 2008 (UTC)

Your difficulties are the usual ones for those who try to understand Godel's theorem. The infinite length of your statement comes from the fact that when you say "P is unprovable" you are unpacking it into "'P is unprovable' is unprovable" etc, etc, which leads to an infinite length statement which is not allowed. This is the central technical difficulty in Godel's proof, how do you construct a sentence of finite length that can talk about itself?

To get around it, you need a finite way of saying "The statement composed of these symbols blah blah blah, copied and manipulated in this way blah blah blah is unprovable", where all the stuff in the sentence is just a tricky way of constructing the same sentence again. In Godel's proof this requires some contortions.

There is a modern shortcut. You can redefine the statements to be about computer programs, so that they are of the form "Program X doesn't halt". Then to get a statement which asserts that it is unprovable, you just move the self-reference into the computer program. If you know how to program a computer, it is pretty obvious that X can construct the sentence "Program X doesn't halt" by printing out it's own code into X and then adding the fluff around that.

X can then look at all the deductions of the axiom system looking for the theorem "Program X doesn't halt", and halt if it finds this theorem. Now the statement "Program X doesn't halt" is asserting its own unprovability.

The reason you came to a quick contradiction from assuming the negation of P is because you are automatically assuming that your axiom systems are consistent (and omega consistent) without hesitation. These assumptions are independent of the axioms you start with, if you are careful to write out everything precisely, as in a computer program. If you are informal about the mathematics, then Godel's statement is obviously true (although unprovable in the original axioms), as Godel pointed out.Likebox (talk) 19:45, 17 February 2008 (UTC)

And here's the answer. My system does in fact allow infinite statements of finite Kolmogorov_complexity. Godel's theorem, however, depends on ZF, while I cannot yet prove that my axiom set is ZF. The fact that the Axiom of Choice should be true but any attempt to use the Banach–Tarski_paradox doesn't work suggests that it isn't. However, I cannot eliminate an error in the proof of that paradox.

Also, allowing infinite statements certainly means that my system is not recursively enumerable. Furthermore, there are unprovable statements; the problem is merely that Godel's construction didn't find one. Thanks for your time. 75.42.82.54 (talk) 22:42, 17 February 2008 (UTC)JH

Goedel's theorem does not require ZF or the axiom of choice; it applies to very weak subsystems of Peano arithmetic. But if your system isn't effective, then there is no reason to expect Goedel's theorem to apply in the first place. — Carl (CBM · talk) 00:20, 18 February 2008 (UTC)

How sure are you that your system is consistent? If it allows infinite statements, how does it avoid Curry's paradox? -- BenRG (talk) 03:12, 18 February 2008 (UTC)

[edit] Trying to falsify Godel

I changed an entry to Godel as it was blatantly trying to hide the facts about Godels proof. The entry said Godels system P was Peano arithmetic this is a blatant falsification. System P is according to godel "By and large, P is the system that you get by building the logic of PM on top the Peano axioms On formally undecidable propositions —Preceding unsigned comment added by Xamce (talk • contribs)

That is not a quote from Goedel, but rather from a translation, as the original is in German. The translation by van Heijenoort is somewhat superior, but I don't think a direct quote is needed anyway, simply the fact that P is obtained by adding the Peano axioms to the logical system of Principia Mathematica. — Carl (CBM · talk) 16:29, 29 February 2008 (UTC)

I made Carl's proposed change. I do want to keep the van Heijenoort quote, however. When I first confronted this topic (and this article) I was very confused about the "first" and "second" incompleteness theorems -- I went searching for them in the translations and couldn't find them. Only after careful reading of the translations was I able to make the connection. The quote also makes it clear that this isn't trivial stuff. Bill Wvbailey (talk) 17:06, 29 February 2008 (UTC)

I meant the quote from Hirzel's translation, sorry. I have never really liked having the original statement of the theorem but I won't argue strongly against it. — Carl (CBM · talk) 17:23, 29 February 2008 (UTC)

[edit] second incompleteness theorem

There is obviously an error in the following. Can someone spot it?

1. An inconsistent system is one that proves a false contradictory statement, like 1=0. (definition). A contradictory statement S is one where both S and not-S are provable.
2. If you can prove a false contradictory statement you can prove any statement. (Principle of explosion).
3. Therefore, in an inconsistent system, all statements are provable. Any system with an unprovable statement (whether true or false) must be consistent. (The converse is not necessarily true, for example the empty theory).
4. The first incompleteness theorem proves that a sufficiently powerful, consistent system contains an unprovable statement, which we'll call G.
5. Further (let's assume for concreteness that the system is PA) the proof that G is unprovable in PA can itself be carried out in PA. (Showing this is the main technical content of the second theorem). (Question: is the proof of the first theorem finitistic in the Hilbert sense?)
6. Thus, PA proves that PA contains a statement G which is unprovable in PA, and therefore (from point 3 above) PA proves its own consistency, the opposite of what the second theorem says.

Is the problem that the principle of explosion can't be proved in PA? That would surprise me since it goes back to ancient Greece. More likely I've missed something different and obvious. Thanks. (Added: the remarkable thing about the first theorem is it shows a statement that is unprovable but true. The above consistency argument would be satisfied by exhibiting a statement that is provably unprovable even if it's false. I'd expect that to be easier--is it?)

Hello. The main mistake is that PA can just prove (an arithmetical statement that is interpretable as) "if PA is consistent then PA cannot prove G". Incidentally also your way to express the principle of explosion is incorrect: they are not "false" statement that imply everything, just contradictions do that.--Pokipsy76 (talk) 12:36, 5 January 2008 (UTC)

Thanks, I fixed "false", I think maybe the article is a bit unclear about G. I'll have to look at it more closely.

[edit] Theorem #1

Wouldn't it be easier to understand (and equivalent to say) that for any theory there exists a statement which is not provable except by using a proof by contradiction?--Loodog (talk) 15:28, 9 April 2008 (UTC)

No, that's not equivalent in any meaningful sense. --Trovatore (talk) 16:56, 9 April 2008 (UTC)

Then I'm misreading this article. I thought it was saying: A statement exists such that either the statement is true or it contradicts the system.--Loodog (talk) 17:21, 9 April 2008 (UTC)

Not exactly. It's more like, either the statement is true, or the system contains a contradiction. The second part is not the same thing as the statement itself contradicting the system. --Trovatore (talk) 17:53, 9 April 2008 (UTC)