Logic and Language

Logic and Language

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

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.

• Use

• The

• To skip the menu and move to the main content, press

• To get back to the top of the page anytime, press the

• For more information, click here: Accessibility Close this tip.

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

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:

*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*

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.

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**,**s****0**,,*ss*0, …, representing*sss*0**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*- 3If we substitute the

by the number-theoretic statement**x**, we get:*z*+ 3*z*+ 5*z*+ 3*z*+ 5 - 3which is a number-theoretic statement - provided the domain of the variable

is natural numbers. And again, if we substitute the*z*by the number-theoretic statement**z**we get:*y*- 2**(***y*- 2) +3(*y*- 2) + 5 - 3which, 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

So - is ** GN(w)** a number-theoretic function?

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

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

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

Of course, there could be another function that is ** similar** to the number-theoretic expression

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

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.

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: 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*

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.

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

But if an expression is defined as a number-theoretic expression, for example

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 …

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.

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

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.

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.

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

16th Mar 2015 Bishops Dancing with Pixies?

23rd Feb 2015 Artificial Intelligence

31 Mar 2015 Cranks and Crackpots

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.

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

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 - 2016

www.jamesrmeyer.com