Logic and Language

Copyright   James R Meyer    2012 - 2023 https://www.jamesrmeyer.com

# Oh no ! Yet Another Flawed Incompleteness Proof

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

## A Flawed Incompleteness Proof by Dan Gusfield

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

This critique addresses a revised version (version 3) of the paper posted on Arxiv by Dan Gusfield, a professor of Computer Science at the University of California. Gusfield has modified his paper considerably in response to my original critique of his paper (PDF Gödel for Goldilocks (v1)). My original critique is included Critique of Gusfield’s original paper version 1: below.

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 fi 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 i. Of course, normally we would write f ( i ) rather than fi to indicate the function and its free variable.

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 f  from the positive integers to {0, 1} as: (Footnote: Here the f should appear with a bar over it. If no bar is showing, your browser is not displaying the content as intended. Perhaps you have the CSS styling turned off in your browser.)

f ( i ) = 1 − fi( i )

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

Since f  is defined in terms of the list function and it is well-defined, it must be the case that the f  function and the list function f  are in the same language. The list function f  has one free variable. Conventionally, if a function has one free variable, when that variable is substituted by some specific value, the function then has no free variables.

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 i, and then he asserts that, whenever that free variable is substituted, the function then gains another free variable, so that it appears that the function actually has two free variables (which we normally write in the format f ( i, j ), but Gusfield writes it in the format fi ( j ) ).

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 also at the same time an expression that is part of the syntax of the language. It’s hardly surprising that Gusfield can prove that such a function is not computable, since if it was computable, it would be self-referential, because it would be one of the values of the list function f, and that self-reference leads to a contradiction.

Gusfield asserts that his incompleteness proof applies to a language if it is a formal language that can express either f ( x ) = 1 or f ( x ) = 0 for every value of x. Then he assumes that there is such a formal language that is both:

1. consistent
and
2. can prove the correct value of either f ( x ) = 1 or f ( x ) = 0 for every value of x.

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

Well, since the f  function is not computable, it’s questionable as to how any consistent formal system could prove a ‘correct’ value for f ( x ) for every value of x. In any conventional formal system, if there is a proof that some function has a particular value for a given value of its free variable, then the formal system is also capable of computing the value of the function. And since Gusfield proffers no explanation as to how a consistent formal system might prove a ‘correct’ value for f ( x ) without also computing the value of f ( x ), the only logical conclusion is that Gusfield’s proof does not apply to any conventional formal system.

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:

### Appendix

#### Original critique of Gödel for Goldilocks

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

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 naively claims that his proof applies to any formal system that can express his f  function - and if you are wondering what that might mean, Gusfield goes on to say that his proof applies to any formal system that “can form any statement about integers ”. Well, that is a very sweeping statement, and unfortunately Gusfield does not at any point clearly define what he means by “can form any statement about integers”. Does this include, for example, a statement such as, “The number 3 as an English word has 5 letters ”? Clearly, such a formal system would be as prone to paradoxes as English is, and it would not be surprising if you could produce paradoxical statements like the liar paradox in such a system. One might as well state that any formal system that can be paradoxical will have undecidable statements - but why would anyone be interested in that rather obvious claim?

However, one presumes that is not what Gusfield intended. In his proof, he claims that the f  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 f  function.

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 f  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 f  in purely number-theoretic terms. So we really have no idea of what Gusfield intends by a formal system that “can form any statement about integers ”.

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.

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at where there are full details.

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.

Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.

Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

Based on HashOver Comment System by Jacob Barkdull

Copyright   James R Meyer   2012 - 2023
https://www.jamesrmeyer.com