Errors in Incompleteness Proofs
Page last updated 03 Mar 2023
‘Incompleteness has been proved many times using several different methods, including proofs that have been checked by computer. So even if there was an error in Gödel’s proof, it doesn’t matter.’
In response to this comment an analysis of several incompleteness proofs has been carried out; these incompleteness proofs, like Gödel’s proof, claim to prove incompleteness and also claim that there is a formula of the formal system that is ‘true’ but unprovable in the formal system. These proofs all have obvious errors of logic, or make unfounded assumptions, or both. Papers demonstrating the flaws in some of these proofs are available here:
- PDF 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
You can find further information on these papers at Analyses of Incompleteness Proofs. In addition:
There is a web page on the errors in four different proofs of what is called the ‘Diagonal Lemma’, see The Diagonal Lemma.
There have been claims of incompleteness proofs based on the so-called “MRDP theorem”, the proof of this by Yuri Matiyasevich is easily shown to be erroneous, relying on a conflation of levels of language that is a feature of most incompleteness proofs, see the page Hilbert’s tenth problem.
There is now a web-page on incompleteness proofs that rely on arguments based around the Halting Problem, see The Halting Problem and Incompleteness Proofs.
The web-page Church’s “An Unsolvable Problem” outlines the error in a proof by Alonzo Church. While this is itself not a proof of incompleteness, you may find proofs of incompleteness that rely on Church’s results.
I have now included a section to deal with incompleteness proofs that are so obviously flawed that it is not worth devoting lengthy papers dealing with them, you can see them at Yet Another Flawed Incompleteness Proof.
Below I give brief outlines of the flaws that are present in various incompleteness proofs. Please note that this page is only intended as an explanatory text, and is not intended to be read as a detailed analysis. For the detailed logical analyses of incompleteness proofs please refer to Analyses of Incompleteness Proofs and the papers above, where there is a full logical analysis.
Some preliminary observations
- The domain of a variable is the complete set of all allowable values of that variable - the values that may be substituted for that variable.
- In a formal system where the only things that the system refers to are natural numbers (the positive whole numbers 0, 1, 2, 3, …), in any expression of the formal system, the free variables may only be substituted by natural numbers. In the formal system, these are commonly in a form such as 0, s0, ss0, sss0, …, representing 0, 1, 2, 3, … .
- A number-theoretic expression is an expression which is an expression about natural numbers, and not about any other things. The objects of the expression are natural numbers, and the variables of the expression are variables whose domain is natural numbers. With number-theoretic expressions, you can substitute a variable by a natural number, but you can also substitute a variable by an expression which is not an actual number, but which is itself a number-theoretic function. As an example, take a simple number-theoretic statement:
x - 3
If we substitute the x by the number-theoretic statement z + 3z + 5, we get:
z + 3z + 5 - 3
which is a number-theoretic statement - provided the domain of the variable z is natural numbers. And again, if we substitute the z by the number-theoretic statement y - 2 we get:
(y - 2) +3(y - 2) + 5 - 3
which, again, is a number-theoretic statement, if the domain of the variable y is natural numbers.
So we can see that for number-theoretic expressions, the variables of such expressions have the domain of natural numbers or number-theoretic functions. And it can be seen that when a free variable of a number-theoretic expression is substituted by a number-theoretic function, the resultant expression is also a number-theoretic expression. Because the resultant expressions are also number-theoretic expressions, then it can be said that given any number-theoretic function (of a certain type, see also primitive recursive), then there is a corresponding expression in the formal language that expresses that function. Many incompleteness proofs use this assertion as part of the proof; there is nothing intrinsically wrong with that - problems only arise when the definition of ‘number-theoretic’ is not rigorously observed.
So - what if we try to substitute the x in x - 3 by something else, such as GN(w), where GN(w) is a function that gives different values depending on what is substituted for w? Now, GN(w) is simply a name for a function - and unless we define what that function is, it is impossible to state whether GN(w) is a number-theoretic function. Let’s suppose that this function GN(w), instead of evaluating an expression such as 7 ‑ 6 + 3 according to number theory (where 7 ‑ 6 + 3 is the same value as 4) it operates on an entirely different basis. It assigns values to the symbols in an expression such as 7 ‑ 6 + 3 according to a simple table where each symbol is given a value. For example, “7” is assigned as 13, “-” as 4, “+” as 16, “6” as 73, and “3” as 37. The rules of the definition of this GN(w) are that these values are simply concatenated, so that GN(7 ‑ 3), according to these rules, gives a value of 13437. And by the same rules, GN(7 ‑ 6 + 3) gives a value of 134731637.
So - is GN(w) a number-theoretic function? No !
The reason should be obvious, because it refers to “-” and “+” as things, whereas in a purely number statement, symbols like “-” and “+” are referring to numbers; usually they are called operators. GN(w) is itself not a number-theoretic statement; while it does evaluate number-theoretic statements, and produces number values, it does not evaluate number-theoretic statements according to the rules of number theory. For example, with GN(w) the term “7 ‑ 6 + 3” is not equivalent to the term “7 ‑ 3”, whereas in number theory, these terms are always equivalent - and interchangeable.
And because expressions like GN(w) are not number-theoretic expressions, they do not belong to the domain of variables of number-theoretic expressions - and therefore to substitute such a variable by an expression such as GN(w) is mathematically incorrect.
See also the page Representability for more on this subject.
Now, on to the main subject – errors in incompleteness proofs. The two errors that I have found to be most prevalent in incompleteness proofs are:
- the illegal substitution of a variable of a number-theoretic expression by a value that does not belong to the domain of that variable, and
- the assumption that if two expressions have the same numerical value then certain other properties must also be identical. Such properties to which this erroneous assumption applies include the property that both expressions are number-theoretic expressions - which would mean that the variables of both expressions have the same allowable values (i.e: the same domain).
The use of such illegal substitutions and associated assumptions is the point where many incompleteness proofs and elementary logic part company. It is quite amazing how many incompleteness proofs make the elementary error of claiming that if you substitute the variable x of a number-theoretic expression A(x) by a function such as GN(w) above, then the resultant expression B must also be a number-theoretic expression. This is an elementary logical error - because such a substitution is mathematically prohibited. If the expression A(x) is a number-theoretic expression, then its variables have the domain only of natural numbers, and therefore cannot logically be substituted by terms that are not natural numbers - and GN(w) is neither a natural number nor a number-theoretic function.
Of course, there could be another function that is similar to the number-theoretic expression A(x), let’s call it C(x), and which has variables that have a domain that includes terms that are not natural numbers. And this function C(x) could even give the same values as the expression A(x) for values of x that are natural numbers. But simply because the two expressions A(x) and C(x) have this one property in common, that does not imply that their other properties are the same. They aren’t. C(x) is not and cannot be a number-theoretic function.
Many incompleteness proofs simply ignore the elementary fact that if an expression is defined as being a number-theoretic expression, then by definition, its variables have a precisely defined domain, and those variables cannot logically be substituted by values that lie outside that domain.
Mathematical rigor demands that the domain of variables be always scrupulously observed; if we want our proofs to be logically and mathematically rigorous, we cannot turn a blind eye to the prohibited substitution of variables. Logically, a proof cannot contain, at the same time, a function that is a number-theoretic function and the substitution of the variables of that function by non-number-theoretic terms.
The above error is obscured in various ways in incompleteness proofs. In many cases this concealment is simply due to the use of natural language where there is insufficient explicit precision and rigor. The resultant confusion is used to conclude that there must be some expression of the formal system that can express precisely the entire information in an expression such as the function GN(w). That, of course, is complete twaddle, since a formal system that does not include the definition of the function GN(w) cannot evaluate any expression that includes that function - it cannot, for example, refer to the values of symbols such as “=” or “+”. In some incompleteness proofs, the error is hidden because the author fails to provide a sufficiently detailed argument, and so the error is not made plainly evident. Some incompleteness proofs refer to a concept of ‘extensional equivalence’, but this is simply referring to a definition, and this does not make the illegal substitution of variables by values outside their domain mathematically or logically acceptable.
Quite why mathematicians fail to detect this elementary error is a mystery. Perhaps it is like the case of the ‘invisible gorilla’, where mathematicians fail to see the error because they are not looking for it, but are looking at other aspects of the proof. But that does not explain why, when the error is pointed out to the author of such a proof, they refuse to accept that there is any error - or refuse to accept that any mathematical proof must be absolutely rigorous. The blindness might be due to a Platonist mind-set, see note below - Platonism and number -theoretic expressions.
See also the page Representability for more on this subject.
This error occurs in Gödel’s original proof, and I have demonstrated how the error operates The flaw in Gödel’s proof and Simplified - the flaw in Gödel’s proof. This is where there is a confusion of language, where a number-theoretic expression is asserted as being equivalent to an expression of a language which is a meta-language to number-theoretic expressions. This sort of proof is much more intriguing, as it is much subtler than the above attempts at an incompleteness proof.
What is happening in these proofs is that, instead of actual substitution as above, there is an assertion such as ‘the variable x of a number-theoretic expression A(x) is the value GN(w)’, or simply something such as x = GN(w). While subtler than the above error, this is still logically incorrect in the same way as substitution is incorrect, because x is by definition a variable with the domain of natural numbers or number-theoretic functions. For a fuller explanation of this type of error see The flaw in Gödel’s proof and Simplified - the flaw in Gödel’s proof. Also see Gödel’s 1934 Undecidability lectures, which, although by then Gödel had three years to reflect on his methods of proof, rather ironically allow a much simpler demonstration of the inherent confusion of language that is involved.
This error occurs in Natarajan Shankar’s computer coded proof, a proof that Shankar claims has been checked as correct by computer software. But at a crucial point in the proof Shankar introduces a statement which includes a fixed non-variable value as one of its values, whereas the value should be a variable value, since Shankar is referring at that point to formulas of the formal system in general, not to one specific formula. The details of the error are given in the paper PDF An Error in a Computer Verified Proof of Incompleteness By Natarajan Shankar.
It is quite startling how many ‘proofs’ of incompleteness you will find that rely on a quite audacious unproven assumption. One of the most common such assumptions is the assumption that the formal system can ‘express’ certain self-referential statements. The absurdity of this approach should be obvious - it throws mathematical rigor out of the window. One might as well simply say:
Here is my proof of incompleteness:
Let’s assume that the formal system is incomplete.
Therefore the formal system is incomplete.
End of proof.
Because once the assumption is made that a formal system can state a certain type of self-referential statement, it is a trivial matter to create a formal formula that appears to refer to itself and appears to say ‘This statement is not provable in this system’ and so appear to prove incompleteness of the formal system. You will find that many of these incompleteness proofs go into great detail over the creation of such a formula, but skate over the assumption that this creation relies on. The impossibility of a formula of a formal system that corresponds to a Gödel numbering function where the formula itself can refer unambiguously to formulas of that formal system itself is proved in the paper PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System.
The classic instance of such an assumption can be seen in the so-called “Diagonal Lemma” which is often used in incompleteness proofs; it purportedly proves how a formal system can self-reference, but in fact the step where the hidden assumption is slipped in to make it appear that the formal system references itself is easily demonstrated, see the page The Diagonal Lemma.
Another case of an untenable assumption is to be found in books by Kleene and Rogers, where they make the egregious error of assuming that because they have been unable to discover a proof of a particular assertion, then the negation of that assertion must be true, see Errors in incompleteness proofs by Kleene and Rogers.
And for details about the errors of somewhat different assumptions in two other ‘incompleteness proofs’, see PDF A Fundamental Flaw in an Incompleteness Proof by George Boolos and PDF A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin. Furthermore, most proofs of incompleteness that rely on arguments based around the Halting Problem also have explicit or implicit assumptions of self-reference, see The Halting Problem and Incompleteness Proofs.
Why such ‘proofs’ have gained such widespread acceptance is a mystery. Why are mathematicians and logicians so willing to abandon all principles of mathematical rigor when dealing with proofs of incompleteness?
Extensional equivalence: A common definition of extensional equivalence is that two functions are extensionally equivalent if and only if they always evaluate to the same value, when any value of the domain of their variables is substituted for their free variables. This obviously cannot be the case for two functions, where one is a number-theoretic function and the other is not a number-theoretic function; then the variables of the two functions do not have the same domains, and one function is undefined for terms outside the domain of its variables. Note that an alternative definition of extensional equivalence can be defined – but simply creating such a definition does not alter the fact that number-theoretic functions and non-number-theoretic functions are essentially different.
Platonism and number-theoretic expressions: For someone with a Platonist mind-set, numbers are ‘real’ non-physical things. A Platonist considers that it isn’t important how he refers to these ‘real’ non-physical things, because he believes that regardless of how he refers to them, there is a ‘real’ thing that he is always referring to. So, for a Platonist, the GN(7 ‑ 6 + 3) that we saw above refers to the same ‘real’ thing as 134731637. For a Platonist, if the domain of a variable is natural numbers, then anything that refers to a natural number belongs to that domain.
But if an expression is defined as a number-theoretic expression, for example x + 3 > 89, and its variable x is substituted by, for example, GN(7 ‑ 6 + 3), then we get a new expression, GN(7 ‑ 6 + 3) + 3 > 89. This new expression contains the expression GN(7 ‑ 6 + 3). When someone assumes that this is also a number-theoretic expression, that may be due to the Platonist habit of considering expressions only as convenient labels for the ‘real’ things that the Platonist believes actually exist. That may lead the person to overlook the fact that the new expression does not satisfy the definition of a purely number-theoretic expression. See also Platonism, The Myths of Platonism, Numbers, chairs and unicorns, Platonism’s Logical Blunder, and the posts Moderate Platonism and Descartes’ Platonism.