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)

Contents

2 Meaning of Gödel's theorems

3 Discussion and Implications

4 Philosophical Implications and Interpretations

4.1 Objectivism
4.2 Penrose Interpretations
4.3 John Lucas

5 Proof Sketch and Discussion of Proof Method

6 Unclassified Metadiscussion

7 Self-verifying systems

8 Bad/useless/uninformative link?

9 Tone

10 real numbers complete?

11 Removed content which makes no sense to me

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

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

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

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 (http://www.cs.albany.edu/profiles/willard.htm) 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] (http://en.wikipedia.org/w/wiki.phtml?title=G%F6del%27s_incompleteness_theorem&curid=50942&diff=0&oldid=0) deleted the following link:

The confusions of Gödel (http://www.abelard.org/metalogic/metalogicA1.htm), 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)

Retrieved from "https://academickids.com:443/encyclopedia/index.php/Talk:G%F6del%27s_incompleteness_theorem"