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

This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

This archive page covers approximately the dates upto 2005-11-14.

1

From Eginhart Biedermann, biedermann@clix.pt 15.9.2005 Biedermann 12:39, 13 October 2005 (UTC)

                      ==THE GAP IN GÖDELS PROOF==
                                             or
                        ==Gödels Incompleteness==

Hello to all the Gödel-experts in this Wiki-world ! Somewhat amused by your detailed discussion about the best wording and interpretation of the Incompleteness Theorem, I wonder whether anyone of you has ever taken a closer look at Gödel’s original paper ( or any word-for-word English translation, or even the exposition in the Nagel-Newman booklet). To my understanding, the technical details of Gödels way of putting together his Unprovable Formula deserve just as much attention. It is not difficult at all to spot there what I would like to call

                       ‘Gödels Incompleteness’ !

If you are interested, please follow me through the following lines: In the long sequence of the some 40 definitions which Gödel introduced for the construction of his famous Unprovable Formula, we find under numbers 16. - 17. the definitiion of Z(n) as the Gödel-number of the presentation of any whole number n which is given in Gödels Formal System through n-fold positioning of the symbol f in front of the symbol 0, so Z(4) is the Gödel-number of ‘ffff0’. So far so good. Further on however Gödel introduces, ( I follow here Nagel-Newman’s way of writing the formulae to get them on a single line of typing) after having defined the Gödel-number of the symbol y to be 13, the formula

(1)         (x)~Dem(x,sub(y,13,Z(y))) ,

of which he claims to be able to determine the Gödel-number n, by means of which he then proceeds, by substitution of n for y, to his famous formula

(G): (x)~Dem(x,sub(n,13,Z(n)))

with its self-fullfilling interpretation of its own non-derivability.

However: what is Z(y)? From what we read above, it should be the Gödel-number of the symbol-sequence that results from the y-fold positioning of f in front of the symbol 0. But nobody, not even Gödel, is capable of putting the symbol f y-times on a sheet of paper, not even in thought. Equally, we all are incapable of determining the Gödel-number of a non-existing symbol-sequence. Consequently no Gödel-number of formula (1) can exist, and formula (G) operates with a non-existing number n. So, my conclusion: this so nice looking formula (G) simply does not exist as a sequence of symbols of System S! That is what I dare to call

     GÖDELS  INCOMPLETENESS     or     THE  GAP  IN  THE  PROOF

In all the so abundant Gödel-literature I have never found any remark on this point. P. Bernays, the then assistant to Hilbert, who evidently talked him into accepting this proof as correct, was all too happy to get, with this help of Gödels, out of the trap of never finding a set of axioms as his master had been asking for!. Hilbert himself, at his old age, certainly never worked his own way through all of Gödels paper! That’s what you have assistants for! And evidently up to these days nobody was ever interested in, or dared questioning Hilberts acceptance of Gödels paper.

Another questionable aspect of Gödels reasoning shows up in the word-for-word definition of what the abreviation sub(y,13,Z(y)) is standing for: it reads (due to the definition of ‘13’ to be the Gödel-number for the symbol y !):

‘’The Gödel-number of the term that results from the term with Gödel-NUMBER y via substitution of the VARIABLE y by the representation of the NUMBER y ‘’!!!

To my understanding the symbol y appears here in two clearly different identities, yet, whoever wants to obtain consistent results in mathematics should not start with such inconsistent definitions! I am sure, any properly built checking program would detect this bug in a matter of seconds on my desktop! Yet this inconsistency is crucial to Gödels selfreferent construct ! My conclusion to all of this Gödel-story simply reads: No wonder this formula cannot be derived from the axioms and

                paper is just too pacient

and even the best human brains may all too easily be misled ! And never forget: to construe selfreferent sentences of any kind always means a nonsensical violation of what language has basically been developed for: the meaningful communication between individuals by meaningful propositions.

From Eginhart Biedermann, e-mail: biedermann@clix.pt 15.9.2005

Walt Pohlis making some important rearrangements to organize the material in a nice progression that also includes identified sections on the import on the theorem, what people make of it, and how it is misinterpreted. I am not going to tromp on that, but it looks like this Talk needs new organization too. So I will make a start. --Orcmid 17:39, 20 Mar 2004 (UTC)

My main goal is to break this into manageable sections, and I may have put some material into awkward places. But I did not lose anything, it is only rearranged. --Orcmid 17:39, 20 Mar 2004 (UTC)

Introductory Material

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 inconsistent or alternatively if the system is consistent 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

Meaning of Gödel's theorems

This section starts out with

Gödel's theorems are theorems in first-order logic, and must ultimately be understood in that context. In formal logic, we write both mathematical statements and proofs in a symbolic language, one where we can mechanically check the validity of proofs so that there can be no doubt that a theorem follows from our starting list of axioms. In theory, such a proof can be checked on computer, and in fact there are computer programs that will check the validity of proofs.

There is probably a lot to question in this initial paragraph. I would start by asserting that Gödel's theorems are theorems about first-order logic, but that is even inaccurate. So, how do we put this on firm ground. Maybe "Meaning" is not a good choice in the title either. We are wanting to talk about what are those systems that the theorems apply to, and what is its importance with regard to questions about such such systems. I do think there is too much crammed together in this one paragraph. Much may depend on the quality of supporting articles that can be appealed to here. --Orcmid 17:39, 20 Mar 2004 (UTC)

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

Discussion and Implications

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

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

Actually, it states that all valid formulae of FOL are theorems of FOL (and vice versa). This unqualified use of true is a source of much confusion (truth is meaningful only relative to a given model). AJK 22:21, 11 Mar 2004 (UTC)

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

Thanks a lot for the helpful hints! --AxelBoldt

(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

But Gentzen's theorem says that. Godel's theorem(s) only proves the negative result, but that's just a special case of Gentzen's.

[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

(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.

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 "undecidability" 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. --User:Juuitchan

Philosophical Implications and Interpretations

Objectivism

[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

Objectivism does not pretend that reason itself is formalizable. Goedel's theorem applies only to formal systems. This is the difference between reason and logic. There are many forms of logic, all equally true in the sense of being consistent, and with varying arenas of applicability or inapplicability. Symbols in logic do not 'mean' anything in reality, they just refer to other logical placeholders. Objectivism, however, is not a logic or formal system, it's manipulation of meaning where there are no placeholders. I have a larger article on this somewhere which I can find and link if there's interest, but suffice it to say that Goedel, if anything, helps to show why Objectivism is right that no logical system can substitute for reason. In any event, at minimum, Objectivists have convinced themselves that Goedel is no problem for them. - JoelKatz

I hear this about this "problem" all the time but I have yet to hear a single decent argument on how the theorem affects Objectivism, much less refutes anything... --WayneMokane 07:16, 19 Dec 2004 (UTC)

Penrose Interpretations

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

The argument put forth by Penrose in Shadows of the Mind goes something like this:

Consider an algorithm A(c,k) that examines if another algortithm C (represented by a number c) given input k stops. If C(k) never stops, then A(c,k) stops immediately. Now consider giving A its own number as input: A(a,a).

To you and me it is obvious that it will run forever - if it didn't we would have a paradox. Therefore you and I know something the algorithm can never know.

Where Penrose is wrong is in concluding that there are problems humans can solve by virtue of being humans, and that these same problems cannot be solved by machines by virtue of not being humans.

But as the example of 'Penrose can't prove this sentence to be true' shows, the truth is that no-one can solve a certain class of self-referential problem. This is the heart of Gödel's theorem. --Spazzm 22:36, 2005 Mar 2 (UTC)

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

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.

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

Segregating 'know' from 'prove' is just mincing words in this context. The sentence may just as well have been:

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

If he did know it, the sentence is false, and his knowledge would be incorrect. See Derek's statement above. --Spazzm 22:36, 2005 Mar 2 (UTC)

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

John Lucas

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.html 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.html 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

Proof Sketch and Discussion of Proof Method

[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.

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.

Unclassified Metadiscussion

This material is in this lump because I was getting tired and the main point is to break this long discussion up into parts so that it can be refined further. --Orcmid 17:42, 20 Mar 2004 (UTC)

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 equivalent 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 User: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 User: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 tenets. I shall not present arguments 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.

User: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.

User: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. User: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!? User: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

This edit I made regarding Minsky and Gödel was my first ever on Wikipedia; please let me know if I should have done something differently.

I have not, in spite of some trying, been able to track down a reference to the information I added. Perhaps someone can ask Dr. Minsky about the incident. He originally reported it in the late eighties or early 90s and I think it was on the old sci.space newsgroup. He addressed the question of whether Gödel's incompleteness theorem limited humanity with Gödel, perhaps it was over lunch. He reported that Gödel stated that humans had an intuitive (or was it noncomputational) method of arriving at truth. Martin Minsky further reported that he had, uncharacteristically, not challenged this statement. He went on to suggest this was because he never remembered Gödel making a conjecture which later turned out to be false. I would love it if someone could come up with the original quote or confirm this with Dr. Minsky.

To use theory of computational language, Gödel was suggesting that humans are more than Turing machines in that they also have an oracle somewhere in their psyche that gives access to absolute truth. Given the Gödel's ontological proof it seems reasonable to expect that Gödel believed this came from God. Mjscud

Could someone explain why Minsky's statement that "human intelligence is capable of error..." is incompatable with Penrose's claim that "human intelligence is not mechanical in nature"? A Venn diagram of this doesn't reveal the answer to me. AnWlover

I heard a story today that inspired me to revise this page. A friend of mine is teaching a history of mathematics course for future high-school teachers. She gave her students the choice of different projects in the history of mathematics. One chose Godel incompleteness. My friend was complaining that her student got it all wrong, and that she got her information from "some website". Nervously, I asked "It wasn't Wikipedia, was it?" Tragically, the answer was yes.

I'm going to revise the topic in pieces. Today I split the intro into two sections, and started a new section on misconceptions. I will come back later and take a look at the rest of the page. -- Walt Pohl 06:36, 14 Mar 2004 (UTC)

What did the Taoist say to Goedel?

"Duh"

Self-verifying systems

Dan Willard showed a few years back that there are a family of consistent systems over the language of first-order arithmetic that are capable of proving their own consistency. I'm afraid there are no good online intrductions to the idea, but I can trace the outline:

The key is to formalise enough of the Goedel machinery to talk about provability internally without being able to formalise diagonalisation;
Diagonalisation depends upon not being able to prove multiplication total (and in the earlier versions of the result, addition also);
Addition and multiplication are not function symbols of the language, instead subtraction and division are, with the addition and multiplication predicates being defined in terms of these. The we can't prove (All x,y)(Exists z) multiply(x,y,z).
Totality of muliplication is a Pi-0-2 sentence;
Provability can be expressed in terms of a tableau search algorithm;
Provability of consistency can then simply be added as an axiom. The resulting system can be proven consistent by means of a relative consistency argument wrt. regular arithmetic.
We can add any valid Pi-0-1 sentence of arithmetic to the theory and still remain consistent.

Given the above result, we have to abandon the claim:

Gödel's second incompleteness theorem, which is proved by formalizing part of the proof of the first within the system itself, states:

No consistent system can be used to prove its own consistency.

I'm busy with proof theory and related pages, and don't want to apply these changes. Any takers? ---- Charles Stewart 08:38, 22 Sep 2004 (UTC)

Bad/useless/uninformative link?

Last edit [1] deleted the following link:

The confusions of Gödel, an analysis of the multiple problems and unsound foundations involved in Gödel's theorems (in four parts)

I think the deleted text is bad POV, but contains useful information. I've not time now to work out a better text, but hoefully I will have time on Wednesday if noone else has. ---- Charles Stewart 16:59, 25 Sep 2004 (UTC)

Tone

It seems to me this entry seriously needs to lose the second person, mostly under Meaning of Gödel's theorems. It seems a little out of place in a mathemetical article such as this.

--WayneMokane 07:21, 19 Dec 2004 (UTC)

real numbers complete?

On the one hand, the article states

"What Gödel showed is that in most cases, such as in number theory or real analysis, you can never discover the complete list of axioms."

On the other hand, it also states

"or example both the real numbers and complex numbers have complete axiomatizations."

Can someone help me resolve these apparently contradictory statements? I was under the impression that the reals could not have a complete axiomatization, since they contain the natural numbers. Lethe | Talk 08:28, Feb 15, 2005 (UTC)

I assume that the reference to complete axiomatisation for reals is to something like Tarski's axiomatisation of elementary geometry. The point is that languages based on the natural tend to need induction or something equivalent to be useful, while there are uses for languages based on the reals without such strong reasoning principles. But the point is misleading: the axiomatisations for real/complex numbers are anything but complete for all the purposes mathematicians make of them. The text should be changed. I'll tackle it if noone else does in the next couple of days. ---- Charles Stewart 11:00, 15 Feb 2005 (UTC)

Removed content which makes no sense to me

I've removed the following passage which makes no sense to me:

"An easy solution for provability in and of itself is to insist that in a truly consistent proof-theorem system each true theorem should actually explicitly contain its own proof. It is obvious that this Prior's solution does not injure completeness.

Paul August ☎ 14:30, Jun 16, 2005 (UTC)

Missing word in first section?

In the first section I read:

Omega-consistency is a technical concept which applies to a theory T if, for no property P, (i) T proves the general proposition that there exists some number with the property P, but (ii) for every specific natural number n, T proves that n does not have the property P.

Shouldn't there be a natural number in the statement after (i), as well as after (ii)? It seems to me that only in this way the definition makes sense. 6/29/05 Irene1949

About computers

Som people (http://science.slashdot.org/comments.pl?sid=154369&cid=12947609) seem to interpret this article as "Gödel's theorem shows that the human brain is beyond what a computer ould possibly be.". Could this be added to the "Misconceptions about Gödel's theorems" section?

There's some content on this in the "Dicussion and Implications" section. While almost all logicians would agree that this is a misconception, I think there's enough debate that we shouldn't label it as one in the article. SpuriousQ 30 June 2005 18:19 (UTC)

I moved the mind/machine stuff into its own section and removed the Minsky stuff which was interesting but seemed superfluous:

"It is worth noting that Marvin Minsky has reported that Gödel told him personally that he believed that human beings had an intuitive, not just computational, way of arriving at truth and that therefore his theorem did not limit what can be known to be true by humans."

"Many other scholars have echoed this view, including Marvin Minsky, who stated that human intelligence is capable of error and of understanding statements which are in fact inconsistent or false."

SpuriousQ 30 June 2005 20:56 (UTC)

A major overhaul needed?

It seems to me that this article is in need of a major overhaul. The sections "Meaning of Gödel's theorems" and "Discussion and Implications" in particular are rather imprecise if not outright incorrect. For example, in the section "Meaning of Gödel's theorems" we read

Gödel's theorems are theorems in first-order logic, and must ultimately be understood in that context.

First of all, Gödel's theorems are about logi, not in first order logic. The most natural reading of "theorem in first order logic" is "logically provable sentence", which surely is not meant. Also, Gödel's theorem does apply to e.g. the type system of Principia Mathematica - Gödel originally proved his theorems w.r.t. a system P obtained from that of Principia Mathematica by adding the Peano postulates as primitives - and to the so-called second order arithmetic studied in reverse mathematics.

We also read that

While an infinite list of axioms may sound strange, this is exactly what's used in the usual axioms for the natural numbers, the Peano axioms: the inductive axiom is in fact an axiom schema - it states that if zero has any property and the successor of any natural number has that property, all natural numbers have that property - it does not specify which property and the only way to say in first-order logic that this is true of all properties is to have an infinite number of statements.

This is of course true, but uninformative and potentially misleading. It suggests that quantification over arbitrary properties can be expressed in FOL using an infinite number of statements, which is of course false. It might also be pointed out that the non-categoricity of the first order axioms stems from the fact that induction is only required to hold for arithmetically definable properties.

Further, we read that

Gödel's theorem has another interpretation in the language of computer science. In first-order logic, theorems are recursively enumerable: you can write a computer program that will eventually generate any valid proof. You can ask if they satisfy the stronger property of being recursive: can you write a computer program to definitively determine if a statement is true or false? Gödel's theorem says that in general you cannot.

This is misleading. The set of theorems being recursive is not about deciding whether a sentence is true or false but about deciding whether it's provable. The above could also be read as claiming that the set of logical validities of first order logic is not recursive. This follows from the negative solution to the Entscheidungsproblem, not directly from Gödel's theorems, although these are of course related.

And we also find that

Gödel himself only proved a technically slightly weaker version of the above theorems; the first proof for the versions stated above was given by J. Barkley Rosser in 1936.

This is already covered in the section about the first incompleteness theorem.

Finally there is a paragraph stating that

Many logicians believe that Gödel's incompleteness theorems struck a fatal blow to David Hilbert's program towards a universal mathematical formalism. The generally agreed upon stance is that the second theorem is what specifically dealt this blow. However some believe it was the first, and others believe that neither did.

This is already covered in the section about second incompleteness theorem in more detail.

In the section "Discussion and Implications" we find an innocous statement

Therefore, in order to establish the consistency of a system S, one needs to utilize some other more powerful system T, but a proof in T is not completely convincing unless T's consistency has already been established without using S.

This is again incorrect. We need a different system, not necessarily stronger than S, as remarked in the section about Gentzen's theorem (which I rewrote as it was nearly unintelligible previously). Also, what is important here is not really formal provability per se, but the fact that to prove the consistency of S we need to utilize some mathematical principles not formalized by S. Of course, this also means that if we want a formal theory in which the consistency of S is provable, it needs to formalize mathematical principles not formalized by S, but the important thing is about actual provability, not about formal provability, which is after all merely a combinatorical property.

We are also told that

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

Which is utterly incorrect. After we have added all finite types, we still get Gödelian incompleteness, which leads to the introduction of the type level omega, which leads to the introduction of type level omega+1, and continuing of omega*2, of omega^omega and so forth. The problem is that in order to formulate this as a formal theory, we need what are known as ordinal notation systems, which assign natural numbers to constructive ordinals. Armed with these notations we can assign notations to type levels. But the general question of whether a natural number is the notation of a constructive ordinal, or whether two natural numbers denote the same contstructive ordinal, is very complex (the set of constructive ordinal (notations) is in the complexity class Pi^1 in the analytical hierarchy). In order to get a formal theory with constructive ordinal notations assigned to the types, we thus need some recursive way of selecting natural numbers which are indeed notations of constructive ordinals. One natural way to do this is to use so called autonomous progressions, in which we start with, say, the omega first levels of the type hierarchy and for every natural number for which it is provable that it is the notation of a constructive ordinal, add the level corresponding to that notation, and iterate the procedure. But this procedure will not exhaust all constructive ordinals, and the result will be a formal system suspect to Gödelian incompleteness. Solomon Feferman has analysed the concept of predicative provability using such autonomous progressions and shown that the so-called Schütte-Feferman ordinal of predicativity, Gamma_0, is the first constructive ordinal which can't be shown to be such by means of predicative reasoning. Friedman has shown that (a finite form of) the Kruskal Tree Theorem can't be proved predicatively.

In fact, one implication of Gödel's theorem - to me the philosophically most significant - is the following "inexhaustibility" phenomenon, first noted by Gödel himself (in his Gibbs lecture)

There can't be a consistent formal theory T accepted as correct in which all informally provable mathematical statements are (formally) provable.

For assume that there were such a formal theory T. Since we accept T as correct, we certainly accept its consistency. But then we can deduce that the Gödel sentence of T is true. But T can't prove its Gödel sentence. Therefore T does not contain all informally provable mathematical statements.

This leads us to the study of proof theoretical reflection and transfinite progressions of theories. Given a T we accept as correct, we should also accept T + Con(T). In fact, we should accept the following (local) reflection principle (which is a statement scheme) Ref_T for T:

If T |- P, then P

which states that for any sentence P, if T proves P, then P is in fact true. Thus acceptance of T leads to acceptance of T_1 = T + Ref_T, which leads to acceptance of T_2 = T_1 + Ref_{T_1} and so forth. Using ordinal notations we can extend this progression of theories first to T_omega = union of all T_i<omega, then to T_{omega+1} and so forth. This procedure is analogous to the one applied to the type hierarchy described above, and so if we are to find anything epistemologically relevant we must restrict the ordinal notation indices to such as can be proved to be notations of constructive ordinals in earlier theories in the progression. Such progressions have been studied first by Turing (under the name ordinal logics) and later by Solomon Feferman. (If we don't restrict the notations to such as can be proved to notations in earlier theories we can get a sequence of theories in which every true arithmetical sentence is provable. However, since the question of whether a natural number is the notation is of complexity Pi^1 (complete) this means that the result is of no epistemological interest whatsoever, since there is no reason to suppose mathematicians have the ability to tell of an arbitrary number whether it's a notation of a constructive ordinal or not. (Actually, we need a stronger principle known as the global reflection principle which says that if for all n, T |- P(n), then for all n, P(n).)). For more information about this kind of reflection and its philosophical significance, consult Torkel Franzen's book Inexhaustibility - a non-exhaustive treatment.

Reading furhter we find that

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 is able to check proofs for correctness. For instance, one might take the set of all first-order sentences which are true in the standard model of the natural numbers. This system is complete; Gödel's theorem does not apply because there is no effective procedure that decides if a given sentence is an axiom. In fact, that this is so is a consequence of Gödel's first incompleteness theorem.

It is indeed a consequence of Gödel's first incompleteness theorem that the set of true arithmetical sentences is not recursively enumerable (and thus not recursive either). However, there are many non-recursive sets of axioms to which Gödel's theorem applies. For example, the set of all true Pi_1 sentences has a Gödel sentence. The crucial difference between e.g. the set of all true Pi_1 sentences and the set of all true sentences is that the former is arithmetically definable while the latter is not. (In fact this result of Tarski's follows from the generalization of Gödel's theorem, since if the set of all true arithmetical sentences were arithmetically definable, it would have a true Gödel sentence which would then be in the set, and it would be inconsistent. It appears that Gödel arrived at his incompleteness theorems by attempting to prove the consistency of analysis by constructing a truth definition and showing that the axioms are true.)

Also, the last three paragraphs seem entirely redundant.

In the section about misconceptions about Gödel's theorems it is stated that

The theorem only applies to systems that allow you to define the natural numbers as a set. It is not sufficient that the system contain the natural numbers. You must also be able to express the concept "x is a natural number" using your axioms and first-order logic. There are plenty of systems that contain the natural numbers and are complete. For example both the real numbers and complex numbers have complete axiomatizations.

The intent here is laudable, but it's not quite clear what "define the natural numbers as a set", "You must also be able to express the concept "x is a natural number" using your axioms and first-order logic" or "the system contain the natural numbers" are to mean exactly. Perhaps a better formulation would be

There are theories that are naturally interpreted in structures which contain natural numbers but to which Gödel's theorems do not apply. For example, the (elementary) theory T of real numbers is naturally interpreted in the structure (R,+,*,/,=,<). The reason Gödel's theorems do not apply to T is that even though the natural domain (R) contains the natural numbers there is no formula P(x) in the language of T, such that P(a) is true only of a is a natural number. Thus we can't express such concepts as "is a natural number coding a proof of contradiction from T" and the proof of Gödel's theorems do not go trough.

Also, it's entirely unclear to me what the following is supposed to tell us

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.

What does it mean to use a "system as its own proof system"? Also, "proof theory" usually refers to a discipline of mathematical logic, not to any formal theory or system and Gentzen's work seems to have nothing to do with using "more powerful proof theory", whatever that means. As I note in the section on Gentzen's theorem, it actually shows that the consistency of PA can be proved in a theory which is incomparable to PA w.r.t. strength. Thus this "correction" seems to me to engender just more confusion.

The proof sketch given in the aptly named section "Proof Sketch for the first theorem" follows, in my opinion, Gödel's original proof too slavishly. I think it's better to first note that all recursive functions are representable in formal systems "in which basic arithmetical facts are provable", prove the diagonal lemma and construct the Gödel sentence as the fixed point of the formula ~Prov_T(x).

I also think that the section on Gödel's second incompleteness theorem I wrote is sufficiently detailed to render the section "Proof sketch for the second theorem" redundant.

I wonder whether examples of undeciable decision problems really belong in this article, which is about another concept of undecidability. I added an explanation about this difference, but I still wonder whether listing such examples in an article about Gödel's incompleteness theorems is not merely confusing.

I've only picked the most egregious paragraphs for more or less detailed criticism. In addition to these, the article seems to lack coherence. As said, a major overhaul is needed. I'd like to rework and rewrite the offending sections from scratch, so if you have any objections or additional issues you wish to be addressed, please speak up.

Grr... I cannot make ω^{ω^ω} render correctly. What gives?

--Aatu 12:29, 15 July 2005 (UTC)