• Use Tab, Shift + Tab, and Arrow keys to traverse the menu. Typing a letter when in a sub-menu moves to the item beginning with that letter.
• The Enter or the Space key opens the active menu item.
• The Esc key closes a submenu if it is open.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.
• For more information, click here: Accessibility Close this tip.
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 from 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 rules of inference are.
You should be aware that while a theorem is defined as a rigorously proven statement, there are many statements that have been given the title of ‘theorem’ even though there is no rigorous proof for the statement. And there have been several instances where a statement was thought to be proven, but it was later discovered that the proof was erroneous. So whenever you see the title ‘theorem’ take it with a pinch of salt. See the page Mathematical Proofs.
Gödel’s Incompleteness Theorem
So, given that we know what a theorem is, what is Gödel’s incompleteness theorem? Well, first you need to know what the term ‘incompleteness’ means, so if you aren’t sure what the term ‘incompleteness’ means in this context, you should first read Completeness and Incompleteness
Basically, Gödel’s incompleteness theorem is any statement that says that for every formal mathematical system[Footnote 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, 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 (see online English translation of Gödel’s original proof or English translation of Gödel’s original proof, PDF file) 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.[Footnote 2]
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.”[Footnote 3]
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. 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.[Footnote 4] 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 Gödel’s original proof in German: here PDF. The first English translation of Gödel’s paper was translated by B Meltzer. 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”, you can view it Gödel’s Proof - English translation: here . You can also see alternative versions of the translation online Gödel’s Proof - Meltzer’s translation: here. There is a more recent English translation by Martin Hirzel, available online Gödel’s Proof - Hirzel’s translation: here 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, publisher: Harvard University Press, details From Frege to Gödel: A Source Book in Mathematical Logic: 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 them makes any difference to the fact that there 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 A simplified account of Gödel’s proof: here.
A step by step walk-through guide to Gödel’s Proof
For anyone who wishes to get to grips with Gödel’s original paper, I have created a walk-through guide to Gödel’s original incompleteness proof, and which is intended to be read alongside the paper. Having looked for such a guide and could find none, I thought it odd that there were no such guides, considering how much other material has been written about Gödel’s proof. So I decided to create this guide to assist anyone else who wishes to become familiar with the details of Gödel’s argument.
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 The flaw in Gödel’s Proof: 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 The Shackles of Conviction: book and The Fundamental flaw in Gödel’s proof: 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 Halting Problem: 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:
- A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF
- A Fundamental Flaw in Incompleteness Proofs by S. C. Kleene PDF
- A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin PDF
- A Fundamental Flaw in an Incompleteness Proof by George Boolos PDF
- A Fundamental Flaw in an Incompleteness Proof by Stanisław Świerczkowski PDF
- An Error in a Computer Verified Proof of Incompleteness by John Harrison PDF
- An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor PDF
- An Error In A Computer Verified Proof of Incompleteness by Natarajan Shankar PDF
In addition, there have been many attempts to provide alternative simple proofs of incompleteness. Most of these are so obviously flawed that it is not worth devoting a separate page to each one, so there is a webpage Oh no! Yet Another Flawed Incompleteness Proof that deals with them.
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.”
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 flawed intuition and illogical assumptions.
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,[Footnote 5]
“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,[Footnote 6] (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. However, such people were surprised by Gödel’s paper - they were surprised because no-one had previously had any notion that logic itself might be able to prove that fully formal logical language will have statements that it cannot prove to be true, even though they are true. That was what was astonishing to these people. And, although they were astonished, they were also overjoyed; and because they were overjoyed, they did not subject Gödel’s paper to a level of rigorous inspection that it would have received if it had demonstrated the converse of what it did appear to demonstrate.
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 over 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.
[Footnote 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. For the detailed conditions that Gödel stated, see the conditions given in Proposition VI of his paper.
[Footnote 2]Peter Smith, although he is a staunch advocate of Gödel’s proof, acknowledges in his paper, Expounding the First Incompleteness Theorem (PDF), that:
“Gödel only sketches a proof by induction on the complexity of the definition of the (characteristic function of the) property or relation in terms of definitions by composition and recursion grounding out in the trivial initial functions. The crucial step is just asserted - ‘the processes of definition … (substitution and recursion) can both be formally reproduced in the system P’ … it certainly isn’t spelt out.”
[Footnote 3]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 on the page True but Unprovable.
[Footnote 4]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.
[Footnote 5]Douglas Hofstadter, Gödel, Escher, Bach, An Eternal Golden Braid, 20th Anniversary edition, 2000, Penguin books
ISBN‑10: 0140289208, ISBN‑13: 978‑0140289206. Gödel, Escher, Bach - An Eternal Golden Braid: Details
[Footnote 6]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)
Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.
If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.
Please wait for comments to load …
The Lighter Side
O’Connor’s “computer checked” proof
I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.
New page on Chaitin’s ConstantThere is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.
Updated: Diagonal Lemma
New page on Quine’s paradox
There is now a new page discussing Quine’s paradox and similar paradoxes.
Previous Blog Posts
For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem
– a page with general links:
– and a page relating specifically to the Gödel mind-machine debate:
All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.
Comments on this site are welcome, please see the comment section.
Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.
If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.
Feedback about site design would also be appreciated so that I can improve the site.