Errors in Incompleteness Proofs

Several people have responded to my demonstration of a flaw in Gödel's original proof of incompleteness (see here) by saying something like:

'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 I have undertaken an analysis of several incompleteness proofs that, 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:

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)

You can find further information on these papers here. 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 here and my papers above, where there is a full logical analysis.

Some preliminary observations

Briefly, before we get into the nub of the text, here are a few definitions and concepts that we need to deal with first:

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

The most common errors in incompleteness proofs

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:

1. 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
2. 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, 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 mindset, see note below - Platonism and number -theoretic expressions.

A similar error involving language confusion

This error occurs in Gödel's original proof, and I have demonstrated how the error operates here and here. This is where there is a confusion of language, where a number-theoretic expression is asserted as equivalent to an expression of a language which is a meta-language (which means that it is a language that refers to number-theoretic expressions as objects, not as expressions of that meta-language itself). 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 here and here.

The confusion of a variable value and a non-varaible value

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 shoudl 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 my paper An Error In A Computer Verified Proof of Incompleteness By Natarajan Shankar (PDF).

Proofs that rely on unproven assumptions

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. See A Fundamental Flaw in an Incompleteness Proof by George Boolos (PDF) and A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin (PDF) for details about the errors in two 'incompleteness proofs' of this type.

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?

[*] Extensionally Equivalent Functions 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.

[**] Primitive Recursive Function: For our purposes, we don't need to concern ourselves with the detailed definition of primitive recursive - essentially, a primitive recursive function is a number-theoretic function which, when its free variables are substituted by specific numbers, the function can always be evaluated by a finite amount of calculation.

[***] Meta-language A language that can talk about another language is called a meta-language. We call the language that is talked about a sub-language. Because the meta-language has to be able to refer to every symbol of the sub-language, there will be a variable of the meta-language whose domain (the set of allowable values of the variable) is the set of all combinations of symbols of the sub-language (including 'combinations' that are actually just single symbols). For this reason, no variable of the sub-language can also be a variable in the meta-language, because then it would be both a variable and a member of the domain of the variable at the same time, which would be absurd.

[****] Platonism and number -theoretic expressions For someone with a Platonist mindset, 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.