Logic and Language

Logic and Language

Copyright © James R Meyer 2012 - 2018 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.

From the collection of obviously flawed incompleteness proofs, here is yet another:

Another example of a flawed incompleteness proof is Gödel for Goldilocks: A Rigorous, Streamlined Proof of Gödel’s First Incompleteness Theorem, Requiring Minimal Background (v3) (PDF).

This critique addresses a revised version (version 3) of the paper posted on Arxiv by Dan Gusfield.

Gusfield has modified his paper considerably in response to my original critique of his paper (Gödel for Goldilocks (v1) (PDF)). My original critique is included Critique of Gusfield’s original paper version 1: below.

*Other obviously flawed incompleteness proofs can be seen at:*

An Incompleteness Proof by Bernd Buldt

An Incompleteness Proof by Francesco Berto

An Incompleteness Proof by Byunghan Kim

In his Section 2, Gusfield says that, given all computer programs of a given language that compute some function, we can “*conceptually order the strings representing the programs that compute the functions in A into a list L*”. Since Gusfield is claiming that his proof is rigorous, we can ignore the appeal to conceptualization and consider what Gusfield is actually defining in his description of the list.

In the description, we find that each symbol string is associated by this list with a specific natural number, where the numbers start at 1 and include all natural numbers. This is a straightforward definition of a function which has one free variable with the domain of natural numbers and the range of the function is a set of symbol strings. Given some natural number, this list function returns the appropriate value, which is some symbol string that is a computer program. Gusfield states:

“*Let f_{i} denote the function in A that appears in position i in L′.”*

In other words, the list function is denoted by ** f**, and the free variable of the list function is

Having defined this list function, Gusfield states that we can now define another function in terms of this list function ** f**, as follows:

“*Next, we define the function from the positive integers to {0, 1} as*: (Footnote: Here the

**( i ) = 1 − f_{i} ( i )**”

and Gusfield claims that this is a well-defined function (See his Section 4: Back to Gödel). He also asserts that the function is not computable.

Since is defined in terms of the list function and it is well-defined, it must be the case that the

But, according to Gusfield, when the free variable of his list function has been substituted by some specific value, another free variable suddenly springs up. Isn’t that convenient? Gusfield has defined a function ** f** with one free variable

In normal mathematics, given a list function whose range is symbol strings with one free variable, when that free variable is substituted by some specific number, the list function has a value of a string of symbols – but it cannot at the same time still have a symbol that is a free variable ** within the syntax of that language**. It can have symbols/symbol strings that are variables in whatever language is chosen for the computer programs, but the language of the list function is necessarily a language that is a meta-language to the language of the computer programs. The value returned by the list function is simply an object seen by the language, and which has no syntax within the language.

But in Gusfield’s definition, the value returned by the function is, ** at the same time**, a symbol string that has no syntax within the language, and

Gusfield asserts that his incompleteness proof applies to a language if it is a formal language that can express either **( x ) = 1** or

- consistent,

and

- can prove the correct value of either
or*(**x*) = 1for every value of*(**x*) = 0.*x*

He then offers an argument that concludes that such a formal system cannot be both consistent and complete.

Well, since the function is not computable, it’s questionable as to how any consistent formal system could prove a ‘correct’ value for

Having conceded that his original version was incorrect to claim that it applied to any formal system that “*can form any statement about integers*”, Gusfield has retreated to a position where his proof only applies to a bizarre non-conventional formal system. In his Introduction, Gusfield proclaims his proof is the “*just-right Goldilocks approach*” to an incompleteness proof. It is difficult to reconcile that assertion with the reality that his proof has no relevance to any conventional formal system.

Footnotes:

*Also see Errors in incompleteness proofs and Analysis of incompleteness proofs.*

*Other obviously flawed incompleteness proofs can be seen at:*

An Incompleteness Proof by Bernd Buldt

An Incompleteness Proof by Francesco Berto

An Incompleteness Proof by Byunghan Kim

This is the content of my critique of Gusfield’s original paper, Gödel for Goldilocks (v1) (PDF)

Gusfield introduces his proof with the claim that he is about to give a complete, rigorous proof of incompleteness. In section 4 of his paper, Gusfield naïvely claims that his proof applies to any formal system that can express his function - and if you are wondering what that might mean, Gusfield goes on to say that his proof applies to any formal system that “

However, one presumes that is not what Gusfield intended. In his proof, he claims that the function he has previously defined is a function from integers to integers, that is, its domain is integers, and its range is integers - and that therefore a suitable formal system can express this

So perhaps Gusfield meant a formal system that is a purely number-theoretic system? But a purely number-theoretic system that can form statements about natural numbers cannot necessarily express a function whose range and domain are natural numbers, when its definition includes entities that are not natural numbers. Gusfield’s function is defined in terms of entities other than natural numbers, and thus the function is not defined in number-theoretic terms. It is in fact defined in terms of a list of computer programs, where the list is defined by taking the programs in order of their length, and, for programs of the same length, by some criterion according to the symbols used for the programs (i.e., in a similar style to a dictionary listing). But Gusfield doesn’t give any alternative definition of this function

The vagueness of Gusfield’s exposition makes a mockery of his claim of “rigorous” in the title of his paper, since his proof is certainly not rigorous by any stretch of the imagination. Despite his claims to the contrary, his paper is worthless since it does not establish any result of any value.

Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked. 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 - any address will do, it does not require verification. Your e-mail will only be used to notify you of replies to your comments - it will never be used for any other purpose and will not be displayed. If you cannot see any comments below, see Why isn’t the comment box loading?.

There is now a new page on a contradiction in Lebesgue measure theory.

There is now a new page Halbach and Zhang’s *Yablo without Gödel* which analyzes the illogical assumptions used by Halbach and Zhang.

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.

13 Jan 2017 Ned Block’s Blockhead

8 Apr 2016 Are we alone in the Universe?

13 May 2015 Good Math, Bad Math?

31 Mar 2015 Cranks and Crackpots

16th Mar 2015 Bishops Dancing with Pixies?

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

www.jamesrmeyer.com