This page is keyboard accessible:
• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• 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.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.
 

Errors in Incompleteness Proofs

Several people have responded to the demonstration of a flaw in Gödel’s original proof of incompleteness (see Demonstration of the flaw in Gödel’s proof: 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 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:

  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. A Fundamental Flaw in an Incompleteness Proof by Stanisław Świerczkowski PDF
  6. An Error in a Computer Verified Proof of Incompleteness by John Harrison PDF
  7. An Error in a Computer Verified Proof of Incompleteness by Russell O’Connor PDF
  8. An Error in a Computer Verified Proof of Incompleteness by Natarajan Shankar PDF

 

You can find further information on these papers Analysis of Incompleteness Proofs: here.

 

There is also a web page on the errors in four different proofs of what is called the ‘Diagonal Lemma’, see The Diagonal Lemma.

 

There is now also a webpage on incompleteness proofs that rely on arguments based around the Halting Problem, see The Halting Problem and Incompleteness Proofs.

 

There is also a webpage Church’s “An Unsolvable Problem” which 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 page to deal with incompleteness proofs that are so obviously flawed that it is not worth devoting a web page to 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 Analysis of Incompleteness Proofs: here and the 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 0123, …), 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 0s0ss0sss0, …, representing 0123, … .
  • 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  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 “ 6 + 3” is not equivalent to the term “ 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.

 

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 mind-set, see note below - Platonism and number -theoretic expressions.

 

See also the page Representability for more on this subject.

 

A similar error involving language confusion

This error occurs in Gödel’s original proof, and I have demonstrated how the error operates The flaw in Gödel’s proof: here and Simplified - the flaw in Gödel’s proof: here. 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: here and Simplified - the flaw in Gödel’s proof: here.

 

 

The confusion of a variable value and a non-variable 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 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 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. 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 The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System (PDF).

 

For details about the errors in two ‘incompleteness proofs’ of this type, see A Fundamental Flaw in an Incompleteness Proof by George Boolos PDF and A Fundamental Flaw in Incompleteness Proofs by Gregory Chaitin PDF. See also the webpage The Diagonal Lemma - the ‘Diagonal Lemma’ is often used in incompleteness proofs and it relies on the erroneous assumption that a formula of a formal system can refer unambiguously to its own formulas. 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?

 

 

Footnotes:

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.

 

 

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

 

NEWS

Peter Smith’s ‘Proof’

It has come to my notice that, when asked about the demonstration of the flaw in his proof (see A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF), Smith refuses to engage in any logical discussion, and instead attempts to deflect attention away from any such discussion. If any other reader has tried to engage with Smith regarding my demonstration of the flaw, I would be interested to know what the outcome was.

 

 

There’s something about Gödel by Francesco Berto

There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.

 

 

Easy Footnotes

I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).

 

 

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 Constant

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

 

Previous Blog Posts  

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

31 Mar 2015 Cranks and Crackpots

 

30 Apr 2015 The Chinese Room

 

Links  

 

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:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

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.


Note: for some browsers JavaScript must be enabled for this to operate correctly.

 

Comments

 

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.

 


Copyright © James R Meyer 2012 - 2017  
www.jamesrmeyer.com