Logic and
Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2024 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

Page last updated 10 Sep 2024

 

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. Since this page was originally written, Gusfield has published a book “Proven Impossible” (Footnote: Proven Impossible - Elementary Proofs of Profound Impossibility, Cambridge University Press 2024.) which includes the same flawed proof as discussed on this page.

Other obviously flawed incompleteness proofs can be seen at:

By Francesco Berto

By Bernd Buldt

By Byunghan Kim

By Dennis Müller

By Sebastian Oberhoff

By Arindama Singh

By Antti Valmari

 

Gusfield has modified his paper considerably in response to my original critique of version 1 of his paper. (Footnote: You can see version 1 of Gusfield’s paper at PDF Gödel for Goldilocks (v1).) My original critique is included Critique of Gusfield’s original paper version 1: below. I have since updated this page to give a simpler analysis of the version 3 of the paper.

 

In his Section 2, Gusfield talks about functions that have one free variable and which always evaluate to either 0 or 1 when the variable is substituted by any natural number greater than 0.

 

He then says that A is the set of all such functions that are computable, and later on he states that:

“…there is some ordered listing L′ of the functions in A that includes every function in A.”

and that:

 

“Let fi denote the function in A that appears in position i in L′.”

 

In other words, Gusfield is claiming that there is an enumeration function that enumerates all the functions in the set A - and in what follows he also claims that the output of this function, for any specific number for i, is a function with one substitutable free variable, where that variable may be substituted by a natural number in exactly the same way as the i of the enumeration function may be substituted by a natural number. In other words, Gusfield is claiming that there is an enumeration function whose output belongs to the same syntactical system as that enumeration function itself. (Footnote: Gusfield simply assumes that the symbols for syntax of the enumeration function are in the same alphabet as the alphabet of what it is enumerating. By the symbols for the syntax of the enumeration function we mean those symbols that are not objects, such as numbers. As such, Gusfield’s enumeration function is completely different to the notion of a function that constitutes an algorithm that can generate a lexicographical listing of all combinations of a given alphabet, and where the enumeration function is written using symbols for syntax other than that alphabet. For more on this see Enumerations in different language systems.)

 

So, while he refers to the i th item in this enumeration as fi, the actual enumeration function has to be a function with two free variables, one being the enumeration variable i and the other the free variable of any such function fi . Although Gusfield writes it in the format fi (x), for clarity we will write in standard notation as f ( i, x ).

 

Having defined this list function, Gusfield states that we can now define another function in terms of this list function f ( i, x ) as follows: (Footnote: In the following the f should appear with a bar over it. If no bar is showing, your browser is not displaying the content as intended.)

 

“Next, we define the function f  from the positive integers to {0, 1} as:

 

f ( i ) = 1 − f ( i, i )”

 

and Gusfield claims that this is a well-defined function (See his Section 4: Back to Gödel), and we note that it is defined in terms of the enumeration function f ( i, x ).

 

However, as already noted, Gusfield simply assumes that there is such an enumeration function f ( i, x ) that can enumerate all the functions in A where the output of that function when the i is substituted is a function with one free variable x. But the function f ( i, x ) is an expression which consists of symbols for the free variables i and x, symbols for numbers and other symbols, and there can only be a finite quantity of these other symbols. Now, when the free variable i is substituted by some numerical value, there remain only that same finite quantity of other symbols. However, there is no limit on the quantity of such symbols that there can be in any individual function expression. Hence the supposition that there can be such an enumeration function as Gusfield’s assumed enumeration function f ( i, x ) is incorrect.

 

Since the remainder of Gusfield’s proof depends completely on that assumption, the proof has no logical validity and the proof fails. For a more detailed analysis as to why there cannot be such enumeration functions see the page Enumerations in different language systems. It can be noted that the notion of the function f  is simply another variation on the diagonal method as used in Cantor’s Diagonal proof - in the same way as that proof proves that there is no enumeration function that can enumerate all real numbers, we have shown that there is no enumeration function such as Gusfield assumed.

 

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 he simply assumes whatever he needs to arrive at the desired conclusion. 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 relies on a logically untenable assumption.

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 Go Get Funding: Logic and Language 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:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Derogatory comments.
Long-winded comments.
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 - 2024
https://www.jamesrmeyer.com