Encyclopedia > Talk:Gödel's incompleteness theorem

Article Content

Talk:Gödel's incompleteness theorem

As I recall the incompleteness theorm is not quite as stated in the opening paragraph and I do consider the paragraph to be misleading. Mindyou - I will need to verify what I am saying here.

The issue stems from the word "or". This can be interpreted in two contexts: (1) one can read the paragraph as saying that (a) one can find unprovable true statements as well as (b)one can show that the axiomatic system is incomplete. the other context is: (2) one can do either (a) or (b) above but not both.

The incompletness therom really is one theorm not two and it states that any system that can prove all assertions is inconstant or alternatively if the system is consitant then there will be true assertions which cannot be proved. Thus - the excluse sense of the word "or" is implied.

I think the opening paragraph permits confusion.

terrell: terr@terralogic.net

There are in fact two incompleteness theorems, and the first incompleteness theorem is to be interpreted in meaning (2) above. I inserted the word "EITHER" to make that clearer, and also repeated the theorem in words. AxelBoldt

I think that fixes it nicely. :-)

terrell

In this new paragraph:

The axiomatic system may consist of infinitely many axioms (as first-order Peano arithmetic does), but for Gödel's theorem to apply, there has to be an effective algorithm which enumerates all the axioms. Otherwise, one could use the "axiomatic system" having all true arithmetical statements as axioms, and would have constructed a counterexample to Gödel's first theorem.

I'm not sure the example is correct. If you take as an axiom every "true" statement in arithmetic (where "true" means valid in every model), then won't the system still be incomplete? There will still be many statements where both P and NOT P are unprovable, because P is true in some models and NOT P is true in others.

A better example would be the following axiom system. Start with an empty axiom set. Sort all possible well-formed expressions by length (then lexicographically). Now go through them in order. For each one, if it can't be proved or disproved from the current axiom set, then add it to the axiom set. I think this procedure defines an infinite axiom system that is both complete and consistent, but it isn't allowable because no algorithm can actually list the axioms in this system. --LC

Not exactly, but close. Assuming your formulae can be of only finite length, and using a finite number or recursively defined set of characters, then it's trivial to recursively list all possible formulae. The problem is that when you go through that list you can't (again, assuming it's a language rich enough to include arithmetic) generate a method for deciding whether each formula is provable, short of actually proving it; but if you don't have a proof yet you can't in the general case, tell whether that's becaue it's not provable or because you haven't found the proof yet. So you could have an algorithm to construct your list, but not one to decide whether each is or is not provable. That is, the problem of decidability crops up even before incompleteness. (If I'm not mistaken, it's a problem for even first-order predicate calculus--which is consistent, complete but not decidable).

Yes, I was using "true" in the naive sense, assuming that every statement about natural numbers is, in an absolute sense, either true or false, independent of some axiomatization we poor souls come up with. Gödel would have agreed, but modern logicians don't like that notion of "truth" very much, because it's not clear how to define it.

Your example works fine, I'll edit it in. AxelBoldt

Why not formulate Goedel's incompletness theorem as saying that a system of logic strong enough to express statements of arithmetic is undecidable, i.e. there is no finite axiomatization of arithmetic in which all its true formulae can be proved.

Then you would have to define what a "true formula" is... The given formulation avoids that can of worms. AxelBoldt

Goedel's completeness (not "consistency") theorem states that all the true formulas of first order logic are theorems of first order logic. - Andre Vellino (vellino@sympatico.ca)

Yup, it's at Goedels completeness theorem. AxelBoldt

May I suggest that someone also writes another article on Goedels Consistency Theorem[?]?

Thanks a lot for the helpful hints! --AxelBoldt

(Regarding axiom of choice and continuum hypothesis)

[COMMENT: True enough, but not a very good example, for several reasons. That the axiom of choice is independent of the remaining axioms of set theory was generally assumed long before Gödel's theorem.]

I took the axiom of choice out and left the continuum hypothesis in. Should we list another example? --AxelBoldt

COMMENT: Examples from set theory in general are a bit misleading, because Gödel's theorem is specifically about arithmetical statements. The theorem was not used at all in proving the independence of the continuum hypothesis. On the other hand, in recent decades much work has been done on finding combinatorial statements of ordinary mathematics that are undecidable in standard theories, beginning with a result by Paris and Harrington about the unprovability in PA of a version of the finite Ramsey theorem.

[COMMENT: So how is this relevant to Objectivism? Does Objectivism have the aim of proving all mathematical truths?]

I don't even know what Objectivism is :-) --AxelBoldt

Objectivism is a philosophical system created by Ayn Rand. It is heavily based on the work of Aristotle. The two viewpoints are irreconcilable in terms of mathematics (see axiom 1 of the Objectivist page), but then Objectivism is as much a "framework for living" as anything else, and Goedel didn't directly address "self-esteem" in any of his work. - MB

(Regarding "stronger theory needed to prove consistency of some other theory")

[COMMENT: This does not at all follow. What follows is only that the consistency of T cannot be proved in T itself, not that it can only be proved in a stronger theory. As for "questionable", nothing in Gödel's theorem says anything about what is or is not questionable.]

Ok, I removed "stronger" and "questionable". Please double check. --AxelBoldt

[COMMENT: Actually the proof applies to all extensions of a weak subtheory of Peano Arithmetic.]

I don't know what that is. Any suggestion for improvements of my statement "the theory should be at least as strong as Peano's Axioms"? --AxelBoldt

COMMENT: The usual formula is "which includes a certain amount of arithmetic", which leaves the matter conveniently vague.

[COMMENT: What is meant by a "formally correct variant" of a paradox?]

Deleted. --AxelBoldt

[COMMENT: Turing did not use Gödel's construction. He did use diagonalization, which was not Gödel's invention.]

With "diagonalization", you basically mean the Barber's paradox?

How about this: "In the proof, Gödel used a technique called diagonalization, which is a formalization of Barber's paradox and was used earlier by Russell to expose inconsistencies in naive set theory and later by Turing to solve the Entscheidungsproblem." --AxelBoldt

COMMENT: The diagonalization argument was introduced by Cantor, and is usually credited to him.

(Regarding the last sentence of the proof sketch:)

[COMMENT: This is not correct. The Godel sentence for T may be refutable in a consistent T. This is where Rosser's strengthening comes in.]

Where did I cheat? How should the paragraph be improved without obscuring the central proof idea too much? --AxelBoldt

COMMENT: If the Gödel sentence G is refutable in T, T proves "there is a proof in T of G" but also proves "n is not a proof in T of G" for every n. Hence Gödel used the assumption that T is "omega-consistent", meaning that such a situation cannot arise.

Now comes the trick: a statement form F(x) is called self-false if F(G(F)), i.e. the form F applied to its own Gödel number, is not provable. This concept can be defined formally, and therefore we can construct a statement form SF(x) which embodies the concept: SF(x) is provable if and only if x is the Gödel number of a self-false statement form. Then define the statement p = SF(G(SF)). This is the statement p that was mentioned above. [COMMENT: This is not a correct characterization of the Gödel formula. The suggestion seems to be that the Gödel sentence is a fixed point of "x is self-false", but this is incoherent, since the Gödel sentence has no free variable. The Gödel sentence, rather, is a fixed point of "x is not provable". Also note that the Gödel sentence, which is equivalent in T to "T is consistent", may be refutable in T even if T is consistent.]

No, p says that "the property of being self-false, i.e. the statement form SF(x), is itself self-false", or short: p = SF(G(SF)). This sentence p is in fact a fixed point of "x is not provable" (and the most direct way to construct such a fixed point). --AxelBoldt

COMMENT: Yes, you're right, I quite missed that this was an alternative description of Gödel's own construction.

[COMMENT: this assumption is insufficient to support the conclusion that the negation of the Godel statement is not provable.]

Yes, we really need ω-consistency, but I didn't want to interrupt the flow of the proof sketch. A remark earlier in sketch says that there are technical difficulties and that omega-consistency is the key word to look for in Goedel's and Rosser's work.

Suggestions: 1. "sufficiently complex to allow one to do basic mathematics" - much better to replace "mathematics" with "arithmetics" here, it's clearer to a layman reader, more precise, and closer to the technical truth. 2. Presenting the second incompleteness theorem as merely a "consequence" of the first seems wrong to me. Much better to explicitly explain that there are in fact TWO theorems, that "Goedel's incompleteness theorem" usually refers to the first theorem, and that the second theorem works by by formalising the first theorem in its own stead inside an axiomatic system. -- AV

I agree with both points. Do you want to go ahead and make the changes? --AxelBoldt

-- I'll make the first, simple suggestion; no time now to rewrite the whole article to conform to the second suggestion. If noone else does it, I'll come back to this in a day or two and will rewrite. -- AV

This was added to the article:

Roger Penrose claims can be disproved by analyzing the following sentence:

"Roger Penrose is unable to prove that this sentence is true."

If the sentence is false, Roger Penrose is unable to prove that the sentence is false, so it must be true. If the sentence is true the sentence is perfectly consistent. So, it is true, but Roger Penrose is unable to prove it. That means that there are true statements about oneself that one is unable to prove. So, humans are unable to prove at least one true statement and are as imperfect as computers are.

That's a fun logical argument that ought to be written up on its own page, and maybe linked to from the paradox page. It isn't really relevant to either Penrose or Goedel's theorems. Penrose never said humans know everything. So this doesn't refute his claims. It doesn't really address misunderstandings of Goedel's theorems, so it shouldn't be here either. I'd suggest moving this to its own page, under whatever name has traditionally been given this type of sentence. If there is no standard name, I'd recommend something like I cant be proved by X[?]. --LC

I think that it is relevant. It seems to me that it refutes the claim that some philosophers make that there is something special about human beings when it comes to Goedels theorem. The statement can be extended to apply to classes of individuals. Ie 'Human beings are unable to prove that this sentence is true.' is a statement whose truth or falsity can easily be demonstrated by intelligent machines but not by humans.

An analogous statement which is also of interest is the statement that 'Roger Penrose is unable to believe that this statement is true.', a statement which no one but Roger Penrose should have difficulty in believing. -- Derek Ross

I moved this from the main page:

Roger Penrose claims can be disproved by analyzing the following sentence:

"Roger Penrose is unable to prove that this sentence is true."

A couple of things:

This would probably belong on the Penrose article, along with a detailed discussion of his position and criticism.
The part "If the sentence is false, Roger Penrose is unable to prove that the sentence is false" does not make sense. It should read "If the sentence is false, then Roger Penrose would be able to prove its truth, a contradiction". You don't know whether he is also able to prove its falsehood or not.
This argument does not seem to counter his claim, that humans are able to "understand" or "intuit" truths which cannot be proven. He would just say: "I can't prove it, but I can understand that it must be true."

--AxelBoldt

As I understand Penrose's argument, he claims that humans can prove arguments that computers can't because we can prove some true statements that an algorithm can't prove. But Penrose misses the point. He doesn't understand that the true statements that algorithms can't prove are self-referential statements and that humans can't prove similar statements about themselves. That doesn't mean that a computer can't prove similar statements about other computers or about humans. The problem is not that computers can't prove certain things and humans can, the problem is that nobody can prove certain classes of self-referential statements.Joao

Penrose didn't say that humans can prove undecidable statements. He said humans can "know" that it's true even though they can't prove it. He would say that the example we're discussing supports his position. He would say that he knows the sentence is true, even though he can't prove it, and even though it's contradictory for him to hold that belief. --LC

In that case, he needs to prove that a computer can't know undecidable statements. He was only able to prove that an algorithm can't prove undecidable statements. But a computer could use several algorithms, could apply them to other computers and could be abble to know undecidable statements. Joao

I agree. My point was that the existence of the sentence "Penrose can't prove this statement" doesn't contradict his claims. --LC

I'm not really familiar with Penrose's arguments; we should definitely explain and critizise them on the Penrose page. If the above is Penrose's core argument, then it has nothing to do with Goedel's theorem, since Goedel does not talk about computers. --AxelBoldt

Goedel's Theorem is related to the Halting problem. The arguments used are very similar. Joao

Also Penrose would say that a computer is equivalent to a formal mathematical system, so that Goedel was indirectly talking about computers and his theorem is therefore applicable. -- Derek Ross

We should not put these arguments on the Penrose page. Most of them were first made by John Lucas at the beginning of the 1960s. Lucas made a much better case for them and still does. That's not surprising, since he's been defending them against stiff opposition ever since. Take a look at http://www.leaderu.com/truth/2truth08 for an example of his defence. Penrose took the arguments and used them in a fairly careless fashion. Have a look at http://www.interchange.ubc.ca/karigwen/godel for the details.

Joao's points should either remain on the Godel incompleteness theorem page as part of a section on the use which has been made of the theorem for attacking the possibility of machine intelligence or it should be put on the machine intelligence page or, at worst, it should be be put on a page about John Lucas. However, as the points are very much Godelian statements, and as Lucas arguments form one of the most controversial uses of the theorem, my vote would be to leave Joao's points on the Godel incompleteness theorem page in their current position or as part of a section on (ab)use of the theorem. -- Derek Ross

But we can hardly go ahead and critizise Lucas' position without first having explained it in detail. How about explanation and criticism on Lucas page, one-sentence summary and link on this page, link to Lucas from Penrose page? --AxelBoldt

That makes sense to me. Let's add a link from the artificial intelligence page too. I already added a Lucas link on the Penrose page earlier today. -- Derek Ross

Please forgive me and drop a note is I was out of line to move this article. Not sure how theorums should be treated.... --maveric149, Tuesday, April 30, 2002

There's a book by Raymond Smullyan, Forever Undecided: A Puzzle Guide to Godel thatcould be mentioned in the article.

Call me a platonist[?], but is the example of Axiom of choice really undecidable in the same sense as, say, the existence of Diophantine solutions of such-and-such a polynomial which encodes the Godel statement for Peano arithmetic is undecidable?

It seem to me that the former is more like the "undecidablility" of whether or not parallel lines meet at infinity; while the latter has a "real" answer - just not one that can be proven inside the model of Peano. Could someone clarify? Chas zzz brown 18:46 Nov 20, 2002 (UTC)

Both of these statements are undecidable in the technical sense of "you can't prove or disprove them from the given axioms". But I agree that they have a different "feel" to them. I don't know how to make that precise though.

If you were a true platonist, then you would know whether the Axiom of choice is true or false, and the two examples wouldn't be that different anymore. It seems that most of us are platonists when it comes to numbers and formalists when it comes to sets.

Also, you can extend Peano's system in various ways; in some extensions, you will be able to prove Goedel's sentence, and in others you will be able to disprove it. AxelBoldt 22:35 Nov 20, 2002 (UTC)

Juuitchan would LOVE to see a real, actual Goedel sentence. He has seen proofs that they exist, but never a real one written out in mathematical symbols.

Well, it would be pretty long and messy, since you have to come up with a formula P(n) which is true iff the sentence with Goedel number n can be proven from the axioms. And then, when you see the four page result, how does it help? AxelBoldt 23:51 Jan 4, 2003 (UTC)

I don't know. I just think that it would be very fascinating to look at a statement which can neither be proved nor disproved. --Juuitchan

At least one person claims that many scientists are completely mistaken about the limits of their own field because they hold unreasoned positions that are equivalant to logical positivism, which has been disproved by the incompleteness theorem.

Who is that person and why should we care?

Furthermore, I don't see how our definition of logical positivism ("Logical positivism asserts that only empirically-verifiable statements or analytic statements true by definition are meaningful, effectively asserting that all metaphysical statements are meaningless.") is in any way refuted by the incompleteness theorems. Logical positivism doesn't even talk about formal systems which are powerful enough to formalize arithmetic. AxelBoldt 17:43 Feb 11, 2003 (UTC)

That person is Two16 (see village pump).

To be fair, it is a position I've heard before, but I'd like Two16 to come over and explain his view, and give the relevant quotes and suchlike to prove that he's not alone in this. If he doesn't, certainly that section should be deleted. Martin

From Two16

In an Oral Culture I would say "It is on the surface: you should simply address the question. No offence is intended in the way it might read in print. If you find yourself offended: try to read it aloud in a gentle voice.

The reason you should care about is this specific case is that it is the best example that I can present about the existance of logical fallacies at the heart of the Wikipedia:

It is my contention that this is a fully defensible position and as must be accorded the same or greater weight as other defensible positions are. Furthurmore:

- This notion will refactor the entire Wikipedia in accordance to known behaviors of Epistemic Community[?].

- This is the point in the wikipedia that I would have choosen to confront Mathematicians and scientist about this general defect in the Wikipedia. I am capable of defending this postion in any discipline. In the Wikipedia, this is the most exacting place to perform its defence.

- Goedels's Incompleteness Theorum is a work of meta-mathematics which has a fully defensible postion as widely applicable to any system which has tenents. I shall not present arguements here to defend this position. Appeal shall be made to a search of existing literature. If none exists, academic papers shall be written and presented to the appropriate places of the professional Academic Community. Please consult What wikipedia is not

It is the best example because it is readily understandable field which the typical Wikipedia user would believe is based on logic: therefore, proving this specific case about science will have general resonance in the Wikipedia.

Fully defensible means: free of logical fallacy.

General means: including or affecting all, or nearly all parts. In the interests of a non-subtle defence Rambot articles are excluded.

I shall locate the ISBN for the German text and English Translations. The ground maybe prepared by feeding your head:

Francis Bacon and his essays available on-line.
Special attention should be paid to The Four Idols

The True Beauty often mentioned about Godedel's Incompleteness Theorem is in the beauty in the structure of his arguement. It was novel and not obvious: quite often it is described as astonishing. He assigned a unique interger identifier for every grammatical sentence generated within an axiomatic system which was similar, yet not identical to Principia Mathematicia.

Each sentence fulfills certain grammatical criteria for truth within a particular axiomatic system. The particular example utilized in Goedels Phd thesis (<35 pages of Philosophy) was a powerful expression of meta-mathematical reasoning which used as its example, landmark reasoning by Bertrand Russell and Alfred North Whitehead.

These are very short memes which carry the essence of Godel Incompleteness Theorum:

* "Logically, there is a limit to Logic

* I am lying: therefore:

** If false: True

** If True: False

Let's not forget this started on the Village Pump concerning the statement:

Any article whose statement depends on a logical fallacy is inherently POV: the point of view of the ignorant.

It is not my intention to deal with this matter in any fashion other than one compresensible to a 1st year philosophy student, so that every reasonably educated member can follow along.

An example of an Epistemic community is described at talk:EPR paradox The post should still remain unanswered by any member of the community, including those whose edit war it exstinguished. Any comments not directly related to the improvement of this talk article should be placed on my talk page. I am particularly looking forward to hearing from librarians, philosophers and people who write brilliant prose, people who weed, the curious and most importantly the novel and not obvious. I do not care what credentials you may possess: your utility to the community depends on your quality of thought and the quality of your posts.

Richard Stallman's Idea demands Authority through Quality.

 Two16

This is all nice and good. The only thing you have said about the statement at hand is "It is my contention that this is a fully defensible position". Unless there are publications that have indeed defended the position, this would qualify as original research by you, which you should publish. Once you have published it, it will be reported in Wikipedia, but not before. AxelBoldt 21:25 Feb 11, 2003 (UTC)

Indeed. Unless Two16 or somebody else shows that this position is held by a reasonable number of academics and/or experts on the subject I propose we remove the remark. -- Jan Hidders 21:43 Feb 11, 2003 (UTC)

Well I'd say I put the onus on the editors when I promised the ISBN. Anyways if the source is 35 pages long I dare say it important enough for every working mathematician to read. Additionaally if one were to write an encyclopedia article on the mosat astonishing result in logic, it would help to read the source document. The appeal to authority is a logical fallacey little removed from counting hits in google. Let's not forget this whole thing started on the Village Pump concerning the statement:

Any article whose statement depends on a logical fallacy is inherently POV: the point of view of the ignorant.

Two16

I will admit that I have a hard time following you. Above you promised "the ISBN for the German text and English Translations." The German text and the English translations of what? In the paragraph above, you mention a source document. Are you talking about Goedel's paper? AxelBoldt 04:22 Feb 12, 2003 (UTC)

Yes. My archive is in another city, I shall be going to it Friday. I can dig up Goedel paper and its ISBN number. Alternatively, use the best library in you city, or on you're campus or consult AmAzon through this site. If your going to buy it on-line buy it through the wikipedia. Dover reprints have a nice translation. Two16

Goedel's paper is online, and the reference is given in the main article on the incompleteness theorem. We don't need another reference. I was waiting for a reference for your claim that Goedel's theorem somehow refutes Logical Positivism. This claim is not contained in Goedel's paper. AxelBoldt 02:53 Feb 14, 2003 (UTC)

Apologies if this has been suggested previously, but would it not look much nicer if we moved this page to "Gödel's incompleteness theorem" rather than "Goedel's incompleteness theorem"? Tim

Yup, done. AxelBoldt 18:47 Apr 3, 2003 (UTC)

Oh, thanks! I was hoping someone else would do the hard work for me. :-) Tim

Is the statement about axiomatizable correct? As I read the axiomatic system article, it fails to mention that the set of axioms must be recursive. I don't know enough about either the incompleteness theorem or axiomatic systems to do the correction, but surely we've got to have the system being recursive somewhere!? Iwnbap

You're right. Depending on context 'axiomatic system' may be understood to be 'theset of consequences of some set of sentences' or 'the set of consequences of a recursive set of sentences'. Clarified this. Richard Zach

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia

Search over one million articles, find something about almost anything!