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 13 Jun 2023
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.
Other obviously flawed incompleteness proofs can be seen at:
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. 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. However, 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: 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.)
“Next, we define the function from the positive integers to {0, 1} as:
( 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, Gusfield simply assumes that there is such an enumeration function f ( i, x ) that can eneumerate all the functions in A. But the function f ( i, x ) is an expression which consists of symbols for the free variable i, 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 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 Non-Diagonal Proofs: Enumerations in different language systems. It can be noted that the notion of the function 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:
Also see Errors in incompleteness proofs and Analysis of incompleteness proofs.
Other obviously flawed incompleteness proofs can be seen at:
An Incompleteness Proof by Francesco Berto
An Incompleteness Proof by Bernd Buldt
An Incompleteness Proof by Byunghan Kim
An Incompleteness Proof by Dennis Müller
An Incompleteness Proof by Arindama Singh
An Incompleteness Proof by Sebastian Oberhoff
An Incompleteness Proof by Antti Valmari
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 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 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 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 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 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.
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 Dan Gusfield
Rationale: Every logical argument must be defined in some language, and every language has limitations. Attempting to construct a logical argument while ignoring how the limitations of language might affect that argument is a bizarre approach. The correct acknowledgment of the interactions of logic and language explains almost all of the paradoxes, and resolves almost all of the contradictions, conundrums, and contentious issues in modern philosophy and mathematics.
Site Mission
Please see the menu for numerous articles of interest. Please leave a comment or send an email if you are interested in the material on this site.
Interested in supporting this site?
You can help by sharing the site with others. You can also donate at
where there are full details.