Gödel's Incompleteness Theorem

What is Gödel's Incompleteness Theorem?

Well, first we need to know what a theorem is. So ...

What is a Theorem?

First of all, a theorem should not be confused with a theory; they are quite distinct concepts. A theory usually means a scientific hypothesis as to how something in the real world operates. The term theory is also used to mean the study of a particular area of interest with a view to providing scientific ideas about that area of interest, for example, music theory.

In mathematics, a theorem is intended to be a term for a very precise and definite concept - a theorem is a statement that is proved, using rigorous mathematical reasoning, to follow according to a set of logical rules, from a set of initial statements. These initial statements are usually called axioms, and these are statements that are accepted without being proven. The set of logical rules which determine how one statement can follow form another are usually called the rules of inference.

Obviously, since any mathematical proof is completely dependent on the acceptance of these initial axiomatic statements and the rules of inference, for any rigorous proof it should be possible to define what those initial axiomatic statements are, and what the the rules of inference are.

Gödel's Incompleteness Theorem

So, given that we know what a theorem is, what is Gödel's Incompleteness Theorem? If you aren't sure what the term 'incompleteness' means in this context, first see Completeness and Incompleteness

Well, first you need to know what the term 'incompleteness' means.

Basically, Gödel's Incompleteness Theorem is any statement that says that for every formal language mathematical system [1], there are sentences that cannot be proved to be true or false in that system. You also need to know that most proofs of incompleteness also appear to show that there are, in every formal language mathematical system [2], statements that cannot be proved in that system, but are nonetheless 'true'. For convenience we will call this Gödelian incompleteness.

But you should also be aware that the phrase "Gödel's Incompleteness Theorem" has also been used for many years to refer to Gödel's proof of incompleteness . Usually it is quite obvious by the context which meaning is intended, but see Pedantic Objections.

A Proof of Incompleteness?

Since Gödel's Incompleteness Theorem is called a theorem, then you would expect it be like any other theorem - that it has been rigorously proved, according to readily definable logical rules, from a set of readily definable initial statements.

So where is such a proof? Good question.

Despite the many claims to the contrary, Gödel's proof is not a rigorous proof. The key part of Gödel's proof is the part that he calls his Fifth Proposition. The entire result of his theorem depends on this Fifth Proposition. But Gödel only provides a brief outline of how you might create a proof - and thereby makes a leap of faith that is not acceptable for a proof to be considered a rigorous mathematical proof.

So, you might ask, why has Gödel's proof been accepted by mathematicians as a theorem? That's another good question. There are several possible reasons:

• Some mathematicians will actually say that Gödel's outline is so obviously correct that it could not possibly be wrong. That, of course, is not acceptable; a theorem should be proved in a completely rigorous manner.
• Very few mathematicians are actually familiar with Gödel's proof. They accept Gödel's proof, not because they have seen it and concluded that it is a rigorous mathematical proof, but because they assume that, because the mathematical community accepts it as correct, then some mathematician must have checked that it is a rigorous mathematical proof.
• Most mathematicians take the stance that, in the years since Gödel wrote his proof, many other proofs of Gödelian incompleteness have been written, and so, they say, there cannot be any doubt that it is correct. Here mathematicians confuse quantity with quality. The fact that there are numerous proofs of Gödelian incompleteness means nothing unless they are rigorous mathematical proofs. There are a plethora of such 'proofs'. If anyone cares to examine them in detail, they will find that they contain elementary logical errors which should be easily discovered by any competent mathematician. But the problem is that mathematicians don't see these errors - because they aren't looking for them. Articles demonstrating the errors in such proofs on this website can be found at Errors in incompleteness proofs and Analysis of incompleteness proofs. Note that this includes demonstrations in the errors in proofs which the authors claim have been verified as correct by a computer program.

Gödel's proof of incompleteness

Gödel's proof defines a formal language, and produces a specific mathematical sentence. Gödel's proof states that although this sentence can be expressed in that formal language, the sentence cannot be proved by that formal language, but nevertheless the sentence is true. And the proof says that this applies to any formal mathematical language that includes sentences about numbers.

Up to now, Gödel's proof of his Incompleteness Theorem has been perhaps one of the most celebrated proofs in the entire history of mathematics. It has been considered to be a tour-de-force in the generation of a result by logical derivation. But in fact Gödel's result is only achieved by confusion and ambiguity at the key points in his proof. Gödel's result relies on hidden assumptions that under rigorous examination are seen to have no logical basis.

Gödel's proof leads many people to the question:

"What does it mean to say that a sentence is 'true'?"

and to the conclusion that:

"If you can say that a sentence must be 'true', then surely you must have proved it to be 'true'?"

So the result is: "For every formal language, there is a sentence of that formal language which is not provable by the formal language, but it is provable."[2]

And if you have proved it rigorously, then you must have proved it according to a definite set of initial axiomatic assumptions, and a definite set of logical rules of inference (see also rules of inference). And if Gödel's proof was correct, since it applies to all formal languages, that would appear to indicate a fundamental difference between every possible formal language and the language of Gödel's proof, where that fundamental difference must be at least one rule or assumption. That would appear to say that every formal language must lack at least one rule or assumption that the language of Gödel's proof possesses - or else it includes at least one additional rule or assumption that prevents it from generating Gödel's result.

Since Gödel's proof only uses a finite amount of language, then there can only be a finite method of referring to such rules or assumptions referred to by Gödel's proof language, and it would be surprising indeed if these rules or assumptions could not be discovered.  So if Gödel's proof actually is a logically coherent argument, we should be able to pin down exactly what those additional rules or assumptions are. So, what is this additional information? You can search through Gödel's proof and all similar proofs of incompleteness, but you won't find this information anywhere.

What a pity. For if that information was available, we could create a formal language with that additional information. And then, if Gödel's proof was correct, we could use that formal language to state Gödel's proof about that language itself.[3] Then that formal language would appear to be stating that there is a sentence that is not provable by that formal language, but which has to be true. But the formal language itself is asserting that the sentence has to be true. And the only way it can logically assert that it is true is by proving that it must be true. So the formal language is stating that there is a sentence in that language which is not provable by that language, but which is provable to be true by that language.

This result would be a contradiction. So something has to be wrong in our path to the contradiction. It is quite remarkable that there have been so many misguided and illogical attempts to explain away this contradictory result of Gödel's proof, rather than attempting to seek out the root source of the contradiction.

The belief that Gödel's proof represents some sort of mathematical 'truth' is completely and utterly wrong. Gödel's result is, unsurprisingly, just the same as all other proofs - it is a result that depends on the assumptions and rules used to generate it.

It can be shown (see below) that Gödel's proof cannot be considered to express some sort of indispensable universal fundamental '"truth"', since the assumptions involved in generating Gödel's result are completely unacceptable by any commonly accepted standards of logic.

It is indeed ironic that Gödel's result has been heralded as demonstrating that formal languages and formal reasoning are inferior to natural languages and intuitive reasoning, when it can be shown (see below) that the entire basis of Gödel's result is itself due to ambiguous natural language and flawed intuition, and actually demonstrates the pitfalls that can result from the uncritical use of intuition.

English translations of Gödel's Proof

Gödel's proof was written in German; you can see it online here (PDF). If you want to see an English translation of Gödel's original paper, which was entitled, "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", the first English translation of Gödel's paper, as translated by B Meltzer, can be seen online at

http://www.geier.hu/GOEDEL/Godel_orig/godel3.htm.

There is a more recent English translation by Martin Hirzel, at

http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf (PDF).

Another translation often referred to is one by Jean Van Heijenoort. It is not available online; it can be found in the book: From Frege to Gödel: A Source Book in Mathematical Logic, pub Harvard University Press, details here.

It might be noted that there are arguments as to which English translation is the 'best' and most faithful to the German original. The differences between the translations are minor. None of this makes any difference to the fact that is an inherent fundamental flaw in Gödel's paper.

A simplified explanation of Gödel's Proof

If you are not familiar with the details of Gödel's proof, you may like to read about Gödel's proof which is given in a simplified form in accessible terms in the novel The Shackles of Conviction, or you can read a simplified explanation of Gödel's proof here.

The flaw in Gödel's Proof of his Incompleteness theorem

The details of the demonstration of the flaw in Gödel's Proof are given here.

Other 'versions' of Gödel's proof of Incompleteness

There are a huge number of so-called 'proofs' which are asserted to be 'versions' of Gödel's proof. At this moment in time, you should be aware that none of the these 'versions' of Gödel's proof can be said to really understand it, since they do not understand the fundamental flaw inherent in the proof.

For that reason, other reading material or web links cannot be recommended, but for your information, there is a page on this site with links to web pages on Gödel and his theorem, see Gödel Links.

However, if you do read other accounts of Gödel's 'proof' of Incompleteness, there are several things that you should be aware of:

Many of these accounts mistakenly assume that the brief argument that Gödel presents in the preface of his paper is basically the proof described in detail in the main part of the part. A great many of the so-called 'versions' of Gödel's proof are based on some version of Gödel's introductory argument. The argument in the preface is not basically the same as the main argument and can be very easily shown to be wrong (as shown in my book and paper (PDF)).

And many other so-called 'versions' of Gödel's proof do not give a Gödelian incompleteness - an expression of which it can be claimed that is 'not provable by the formal language, but it is true (or provable)'. Hence they cannot really be considered to be a 'version' of Gödel's proof. Typical of these so-called 'versions' are those that are based on Turing's 'halting' argument (for example see here) that there cannot be a computer program that can tell if any computer program will stop or continue to run forever. Assertions that these 'versions' are essentially the same as Gödel's proof fail to understand the distinction - Turing's argument does not give a sentence which is shown to be true but not provable.

Flaws in other Incompleteness Proofs

Papers demonstrating the flaws in some other proofs of incompleteness are available here:

1. A Fundamental Flaw in an Incompleteness Proof By Peter Smith (PDF)
2. A Fundamental Flaw in Incompleteness Proofs By S. C. Kleene (PDF)
3. A Fundamental Flaw in Incompleteness Proofs By Gregory Chaitin (PDF)
4. A Fundamental Flaw in an Incompleteness Proof By George Boolos (PDF)
5. An Error in a Computer Verified Proof of Incompleteness by John Harrison (PDF)
6. An Error in a Computer Verified Proof of Incompleteness by Russell O'Connor (PDF)
7. An Error In A Computer Verified Proof of Incompleteness By Natarajan Shankar (PDF)

The flaws are described briefly here and a brief account of the types of flaws in such proofs is given here.

The Reception of Gödel's Incompleteness theorem

Von Neumann, a mathematician viewed in great esteem, said in a speech in 1951 that Gödel's proof was:

"Kurt Gödel's achievement in modern logic is singular and monumental - indeed it is more than a monument, it is a landmark which will remain visible far in space and time"

Von Neumann also said (letter to Carnap,  June 1931) that:

"there is no more reason to reject intuitionism."

On the contrary, Gödel's proof is a travesty of the principles of logical deduction, an argument where at the crucial point logic is cast aside in favour of intuition - flawed intuition. See also Intuitionism.

The notion that Gödel's proof demonstrates some sort of universal 'truth' that differentiates 'truth' and 'provability' has led to some wonderfully bizarre statements, such as:

"Gödel showed that provability is a weaker notion than 'truth'." Douglas Hofstadter, [4]

"It follows that no machine can be a complete or adequate model of the mind, that minds are essentially different from machines. We can never, not even in principle, have a mechanical model of the mind". J R Lucas, [5] (see also the page Gödel, Minds, and Machines)

The renowned philosopher Wittgenstein was ridiculed because it was believed that he did not understand Gödel's proof - because he refused to accept it as correct. Now it turns out that he was correct all along.  Wittgenstein referred to Gödel's result as a result given by 'logical tricks', and this is the case - the superficial complexities of the main part of Gödel's proof have served to hide the underlying intuitive assumptions inherent in the proof.

It is quite ironic that Gödel has always been considered to be the logician par excellence, while Wittgenstein's writings have frequently been dismissed as being vague and impenetrable, when it is the vagueness and impenetrability of Gödel's proof that has obscured its inherent flaw for so long.

Contrary to popular opinion, Gödel's result was not a revolutionary overthrowing of the commonly accepted philosophy that existed at the time of its publication - it was accepted by the vast majority of philosophers and logicians precisely because it appeared to say what they wanted to hear - in effect, that man is capable of a higher level of reasoning than a formal language, that there are realities that cannot be captured by a formal language, and that human intuition is superior to formal reasoning.

Many logicians have stressed the importance of the fact that Gödel's proof generates a specific formal expression, but in principle this demonstrates nothing. It ignores the blatantly obvious fact that every erroneous proof generates a fallacious expression. Gödel's specific sentence is simply a result that can be generated in an ambiguous language and is simply a reminder of the old adage, "Rubbish in, rubbish out".

It is a sobering thought that 80 years have passed since Gödel's proof was published. In that time, it has been the subject of intense study. The failure to uncover the naïve assumptions that give rise to that result is a failure that is surely the most risible, embarrassing, and deeply worrying failure in the entire history of logic and mathematics.

Pedantic objections to use of the term Gödel's Incompleteness Theorem

Usually it is quite obvious, when someone refers to Gödel's Incompleteness Theorem, whether they mean the statement, or Gödel's proof of it, but you should be aware that there are pedants who insist that Gödel's Incompleteness Theorem can only mean the statement and not Gödel's proof of it - since the technical meaning of theorem is a statement, not a proof.

This is often done in order to deflect an argument, and ignores the common usage of the phrase "Gödel's Incompleteness Theorem". For those pedants, one might wonder why they refer to it as Gödel's Incompleteness Theorem at all, since pedantically it might be pointed out that in Gödel's original paper that Gödel did not actually call what he had proved an incompleteness theorem.

[1]   Subject to certain conditions. The conditions are basically that the formal language is consistent (consistent: means that the language cannot ever make a contradictory statement) and that it includes statements about numbers.

[2]  In an attempt to circumvent this difficulty, some people have suggested that the sentence is not proven by Gödel's proof, but merely demonstrated to be 'true'. This is simply playing games about the meaning of the term 'true' while at the same time refusing to define it. Another attempt to circumvent the difficulty is to claim that Gödel's proof does not actually show that Gödel's 'unprovable' sentence is true. This notion is dealt with at True but Unprovable.

[3]  In fact, we would use that formal language to state Gödel's proof about a formal language that was identical to that formal language, but where the symbols for the languages are different - but both formal languages would be logically and mathematically equivalent.

[4]   Douglas Hofstadter, "Gödel, Escher, Bach, An Eternal Golden Braid", 20th Anniversary edition, 2000, Penguin books, ISBN-10: 0140289208, ISBN-13: 978-0140289206. Details

[5]  Lucas, J.R, Minds, Machines and Gödel, Philosophy, vol. 36 (1961), pp. 112-137. Also in the book 'Minds and Machines', ed. Alan R. Anderson (Englewood Cliffs, NJ: Prentice Hall, 1964) (see also the page Gödel, Minds, and Machines)