Gödel’s Incompleteness Theorem
Page last updated 25 Sept 2020
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 this incompleteness theorem by Kurt Gödel, a proponent of intelligent design (see Statements by Kurt Gödel)? 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 taken to be any statement that says that for every formal mathematical system, (Footnote: 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.) 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.
It is called Gödel’s incompleteness theorem because it was Kurt Gödel who first came up with the idea. Gödel has often been referred to as the greatest logician of the 20th century, indeed by some as the greatest logician of all time. If you want to see why this accolade might be somewhat questionable, see Statements by Gödel - the ‘great logician’.
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, rather than specifically to the statement noted above. 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) is not a rigorous proof. (Footnote:
There are other proofs that are claimed to be proofs of incompleteness, but these “proofs” can also be shown to have fundamental logical errors, see Errors in Incompleteness Proofs and Analysis of Incompleteness Proofs. See also the section Contradiction on this page.)
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, saying in his paper: “We content ourselves here with indicating the proof of this proposition in outline, since it offers no difficulties of principle and is somewhat involved.” In so doing he makes a leap of faith that is completely unacceptable in a proof that is to be considered as a rigorous mathematical proof. (Footnote:
Peter Smith, although he is a staunch advocate of Gödel’s proof, acknowledges in his paper, Expounding the First Incompleteness Theorem, 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.”
See also Gödel Without (Too Many) Tears - Or Not? and A Fundamental Flaw in an Incompleteness Proof by Peter Smith.) The failure of Gödel to furnish a fully detailed proof is surprising in view of Gödel’s insistence elsewhere on clarity and precision.
So, you might ask, why has Gödel’s proof been accepted by mathematicians as proving 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; every postulated 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 incompleteness paper is not the only paper where he made a completely unproven assertion which almost everyone simply assumed to be correct because of Gödel’s esteemed reputation. In that other paper Gödel made a similar intuitive assertion, but it was eventually proved (some 50 years later) that Gödel’s intuitive assumption stated precisely the opposite of what was actually the case. For details of this see Gödel’s Intuitive Error No.2. Not many mathematicians are aware of this - Gödel’s reputation is still so honored today that most discussions of Gödel’s work skip over this inconvenient detail.
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: 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.)
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: 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.) 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. See also Gödel’s 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 at Gödel’s original proof. 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”, and which has clickable cross-reference links, you can view it at Gödel’s Proof - English translation. Meltzer’s translation was freely available online for many years but it now seems that many sites want you to pay for it, and hide it behind a pay wall, but you may find it online at AltExploit - Meltzer’s translation and Minnesota State University - Meltzer’s translation. There is a more recent English translation by Martin Hirzel, available online at Hirzel’s translation of Gödel’s Incompleteness paper, but I do not recommend it because, unlike all other versions, it does not use the original German names for various relations. Since articles on Gödel’s proof almost invariably use Gödel’s original German names, trying to follow the article while using Hirzel’s translation would be rather tiresome.
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 at From Frege to Gödel: A Source Book in Mathematical Logic.
It might be noted that there are abstruse 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.
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 Incompleteness Proof
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 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. A particularly naive attempt a “proof” can be seen at the World’s shortest explanation of Gödel’s theorem?
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:
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 The Halting Problem) 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
- A Fundamental Flaw in Incompleteness Proofs by S. C. Kleene
- A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin
- A Fundamental Flaw in an Incompleteness Proof by George Boolos
- A Fundamental Flaw in an Incompleteness Proof by Stanisław Świerczkowski
- An Error in a Computer Verified Proof of Incompleteness by John Harrison
- An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor
- An Error In A Computer Verified Proof of Incompleteness by Natarajan Shankar
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 formal papers to them, so there is a web-page Oh no ! Yet Another Flawed Incompleteness Proof that deals with them.
The Reception of Gödel’s Incompleteness Proof
Von Neumann, a mathematician viewed in great esteem, said of Gödel’s proof in a 1951 speech:
“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: 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.)
“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: 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).) (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 Wittgenstein was correct all along. Wittgenstein referred to Gödel’s result as a result given by ‘logical tricks’, and this is indeed 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 euphoric; and because they were euphoric, 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 85 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 naive 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 an 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.
Interested in supporting this site?
As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.
Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous usernames for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.
Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.
Note: a password enables editing of comments, an email enables notification of replies