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.

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

Oh no ! Yet Another Flawed Incompleteness Proof

From time to time I get asked to comment on an incompleteness proof. Many of these proofs are so obviously flawed that it is easy to demonstrate where the flaw is. It is not worth having a separate web page for each such proof, so I decided to start this page to deal with proofs of incompleteness that are so obviously flawed that the flaw can be explained in a few paragraphs, and if I have time, I will populate this page with suitable examples. It seems to be the case that in many such proofs, the quality of the proof seems to be in inverse proportion to the esteem with which the authors view their own work.


The proofs so far dealt with are:


An Incompleteness Proof by Francesco Berto

Francesco Berto is a professor of philosophy at the University of Amsterdam and is a member of the Institute for Logic, Language and Computation (ILLC). He has written a book that he claims is “The Complete Guide to the Incompleteness Theorem”. (Footnote: Francesco Berto: There’s Something about Gödel: The Complete Guide to the Incompleteness Theorem, ISBN: 978-1-4051-9766-3, Wiley-Blackwell, 2009 Details.) When I was asked to if I could see anything wrong with Berto’s argument, I took a quick look at the book and within a few minutes I found the error in it. It was easy because Berto essentially just rehashes the content of Nagel & Newman’s book, (Footnote: E Nagel and J Newman. Gödel’s Proof. New York University Press, revised edition, 2001. ISBN: 0814758169 Gödel’s Proof: Details.) without actually understanding it. (Footnote: The content of Nagel & Newman’s book is analyzed on another web-page Nagel & Newman’s Book: Gödel’s Proof.) As such Berto’s book is not by any stretch of the imagination any sort of reliable guide to Gödel’s Incompleteness Theorem, never mind a ‘complete’ guide. For Berto to call his book a complete guide when it is boils down to a rehash of a 50 year old informal exposition of Gödel’s proof is, quite frankly, ridiculous. But, worse than that, Berto demonstrates that he does not even understand the subtleties involved in Nagel & Newman’s account.


In Section 3, “Arithmetizing substitution” in Chapter 6, “I Am Not Provable”, Berto defines a number-theoretic function as follows:

Let us now consider an arithmetic function, Sub(m, n, p), such that, if m is the Gödel number of a TNT formula α, and n is the Gödel number of a variable x, its value is the Gödel number of the formula α[x/p]. This is the formula one obtains from α (whose code is m), by replacing in it the free occurrences of the variable x (whose code is n) with the term p, that is, with the numeral of number p.


Berto then goes on to say:

We can read “Sub(m, n, p)” as: “the code of the formula obtained from the formula whose code is m, by substituting in it the free occurrences of the variable whose code is n with the numeral of p. And one can show that Sub is primitive recursive”


But in the very next paragraph, Berto gives a quite different definition of that very same function, referring to:

v = Sub(t, 31, t)

and stating that v is the Gödel number that corresponds to the formula one obtains from the formula whose Gödel number is t, when the free variable in that formula (which corresponds by Gödel coding to 31) is substituted by “the numeral of the Gödel number of t itself”.


Note the discrepancy here - in the first definition, the definition that asserts that the function Sub is purely number-theoretic, the corresponding substitution is simply by the numeral of a given number. But in the second definition, the corresponding substitution is by the numeral of the Gödel number of a given number. And it is the second definition that Berto uses to “prove” incompleteness, by assuming that the formal system TNT can express the second definition. But the second definition is not a purely number-theoretic expression and it can be proved that there cannot be an expression in the formal system TNT that can express the second definition. (Footnote: See The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System (PDF).)


Clearly, Berto has simply copied snippets of the content of Nagel & Newman’s book without subjecting it to any sort of critical logical analysis, and without understanding precisely what he is doing. He does not seem to be aware that he has used two different definitions of the same function. It has to be said that Nagel & Newman’s description of their Sub function is vague and verbose and in places contradictory, and one has to read it carefully to ascertain that Nagel & Newman are including the implicit assumption that the formal system can refer to the Gödel coding function - which it cannot. (Footnote: See The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System (PDF).) But if Berto is asserting that he has produced a complete guide to Gödel, then it was incumbent of him to critically analyze what he was writing. Berto’s error is so obvious that it would seem that Berto is incompetent or careless or dishonest - or some combination of these attributes.


What is also surprising is that none of the reviews that Berto’s book that I have seen makes any mention of the obvious error of two different definitions of the same function. (Footnote: A review by The Times Higher Education, see here.) (Footnote: A review by Vann McGee, see here. McGee has written a ‘proof’ of the Diagonal Lemma; the analysis of his ‘proof’ is at Vann McGee’s Proof of the Diagonal Lemma.) (Footnote: A review by Peter Smith, see here. Smith has published a book on Gödel’s proof, which contains a fatal flaw; the analysis of the Smith’s book is given at A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF. Smith also has a downloadable cut-down version of his book which is dealt with on the page Gödel Without Tears - Or Not?.) Does the fact that these reviewers were all unable to see this elementary error indicate that they are dim-witted or that they are careless? Or is it just a case of confirmation bias, where the reviewers are not impartial, and simply saw what they wanted to see, rather than subject Berto’s content to logical scrutiny?







An Incompleteness Proof by Arindama Singh

Arindama Singh is a professor in the Department of Mathematics in the Indian Institute of Technology Madras and has written Fundamentals of Logic and Logics for Computer Science. He has also written a paper A Simple Proof of Gödel’s Incompleteness Theorem which includes several elementary logical errors - this paper was published in the Ramanujan Mathematical Society’s Mathematics Newsletter Volume 22. No3, December 2012.


Early on in the paper, Singh refers to the standard turnstile symbol    and acknowledges its standard use when he states, regarding a formal system of arithmetic N, that we write:


to signify “X is a theorem in ” (which means that there is a proof of the formula X in the formal system N). He then goes on to define a function g where, given a formula X of the formal system N, the value of g(X) is a unique number that corresponds to that formula - the Gödel number of the formula X. He then states that there is a formula Pr(y) such that if y is the Gödel number of a formula Y (i.e., y = g(Y)) then if the formula Pr(y) holds in that system N, then there is a proof of the formula Y in that system N.


He then says that P(X) = Pr(g(X)), where P is a ‘provability predicate’ whose arguments are formulas, and where P(X) means that X is provable in N. He also claims that P(X) is a formula in the theory N. But if P(X) means that X is provable in N, then the expression “P(X)” is precisely the same as the expression “X ”. And since both of these expressions are expressions of the meta-language, then P(X) cannot be a formula in N.


Now, Pr(g(X)) is a meta-language expression that is intended to represent a formula of the system N, where g(X) is the Gödel number of a formula X,

i.e., if x = g(X), then Pr(x) is a formula of the system N that corresponds to the assertion:

is provable in N

and also to the assertion P(X).


Singh’s assertion that P(X) = Pr(g(X)) is nonsensical, since they cannot be equal - the left-hand side is a statement in the meta-language, while the right-hand side is a formula of the system N. Singh manages to completely misunderstand the simple matter of the distinction between the different levels of language involved here. He goes on to exacerbate his error by stating that this predicate P has the following properties:

If X then P(X)

This, of course, is arrant nonsense, since P(X) is an expression of the meta-language, then it cannot be proved within the system N. Since the term P(X) is precisely the same as X, the above expression is precisely the same as:

If X then ⊢ ⊢ X

which also serves to demonstrate the absurdity of Singh’s assertion.


The proof continues with a mish-mash of further errors. He goes on to state:

Let B1(n), B2(n), be an enumeration of all formulas in N having exactly one free variable.

But an enumeration is a function with one free variable, and here the free variable of the enumeration is represented by the subscripts 123, … , so the general form of this enumeration is Bm(n), where m is the free variable and therefore n cannot be a free variable in the language of the enumeration. It is a variable of the system N, not a variable of the enumeration, yet Singh treats it as a variable in the subsequent paragraph. Since the enumeration is in the meta-language, it would be more logical to simply write such an enumeration as B(m) and omit the n as it is not a variable of the meta-language.


Singh’s illogical subsequent treatment of the n as a free variable in B enables him to derive the expression:

(i) Bk(n) ↔ ¬P(Bn(n))

and then he states that by universal generalization, we have:

(ii) ⊢ ∀n(Bk(n) ↔ ¬P(Bn(n)))

This is illogical nonsense, even if we ignore the fact as shown above that the system N cannot prove anything regarding P. For if n(Bk(n) ↔ ¬P(Bn(n))) is a theorem in N, then it must be a proposition in the system N. And since this is a generalization on the n in Bk(n) ↔ ¬P(Bn(n)), then n is a free variable in Bk(n) ↔ ¬P(Bn(n)), which means that Bk(n) ↔ ¬P(Bn(n)) cannot be a proposition, and hence there cannot be a proof of it in the system N (unless there is something very wrong with the system N !).


It is only by this illogical treatment of the n as a free variable in B that Singh manages to derive the expression:

↔ ¬P(A) (i.e., A↔ ¬ ⊢ A).


To be fair, Singh then states that he will now give what he calls a formal proof of this claim (but that hardly excuses the use of logically absurd statements such as treating a non-variable term as a variable). He goes on to state that:

Let the ‘diagonalization’ of B(x) be the expression

x(B(x)  ∧ (x = g(B(x)))).

Since g is a computable function, the relation

diag(m, n):

n is the Gödel number of the diagonalization of the formula having exactly one free variable with Gödel number m

is recursive and hence representable in N by some binary predicate, say, C(x, y).


This is an elementary error. A computable function can refer to data that are not numbers (such as string data), and in fact the function g must refer to strings that are not numbers - symbol strings of the system N. But Singh has defined his system N to be a purely arithmetical system whose only data is number data. Hence the function g and the function diag(m, n) are not representable in his system N. Of course, one can code symbol strings into numbers, which is what the Gödel numbering function does, and of course those numbers can occur in formulas in the system N, but the system N itself cannot access the information of the coding; see the paper The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System (PDF) for why there cannot be any formula in such a system N that can represent the Gödel numbering function.


Unfortunately, this paper that is replete with so many elementary logical errors is not an isolated example - it appears to be the case that many logicians and mathematicians are so accustomed to manipulating symbols within a single language that they seldom have to consider different levels of language. Because of this, they fail to take into account that whenever you are dealing with different levels of language, you have to be scrupulously careful not to confuse one level of language with another when you are manipulating symbols.


An Incompleteness Proof by Antti Valmari

Antti Valmari, a Professor at Tampere University has published what he calls a “rather easy yet rigorous proof of a version of Gödel’s first incompleteness theorem” on the Arxiv website, see A Simple Character String Proof of the “True but Unprovable” Version of Gödel’s First Incompleteness Theorem.


Valmari bases his proof around a formal system that can make propositions about strings of symbols. He defines what symbols constitute the alphabet of the language of this system. A variable in this language is a string that begins with a lower case letter (a- z) followed by zero or more digits (0-9), e.g., b237 is a variable in this system.


Now, for a formal system to be able to prove anything:

  1. at least one axiom must be defined for the system
  2. at least one rule of inference must be defined for the system

However, Valmari fails to define any axioms or rules of inference that apply to his formal system. The closest he comes to providing such is when he makes remarks regarding the = symbol of the language. In essence he states that "X""Y" = "Z" is a ‘true’ proposition of the system if and only if XY is precisely the same symbol string as Z, and where "X""Y" is the concatenation of the strings "X" and "Y", and XY is the concatenation of the strings X and Y. (Valmari’s actual wording is: "theorem"="theo""rem" is a true atomic proposition, and "theorem"≠"theo""rem" is not.)


So, for the system to be able to prove, for example, "A""B" = "B", for any given symbol strings A, B, C, it must prove that AB is identical to C. This means that the system must be able to reference any symbol string of the system, since A, B and C can represent any symbol string of the system.


Herein lies a fundamental problem. It is impossible for a variable of a language to have the domain of all symbol strings of the language, since then it would include itself as a member of its own domain. This is a logical absurdity, since then it would be at the same time a variable, and a value that is substituted for a variable. Valmari seems to be completely unaware of this problem, and provides no argument to show how his nonchalant informal use of " as a delimiter can be replicated within his system - a system that he says can make propositions about strings of symbols.


The result is that he has given an informal description of a formal system that has no apparent means of proving even one proposition of that system. So, as Valmari has described it, his formal system is fundamentally incomplete anyway, because it cannot prove any propositions at all ! As such, the remainder of Valmari’s incompleteness ‘proof’ is utterly worthless, since it is inapplicable to any useful formal system.


An Incompleteness Proof by Dan Gusfield

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.


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


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,


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


An Incompleteness Proof by Byunghan Kim

Byunghan Kim is a university professor of mathematics and his paper, with the title “Complete Proofs Of Gödel’s Incompleteness Theorems, is the basis of a lecture course to students. His paper consists of an impressive looking twenty-three pages with numerous definitions and equations replete with many symbols. In his Section “Step 1: Representability of Recursive Functions in Q” (page 9) Kim defines a function n_ (n underscored) as a string of symbols, where there are n of S symbols, followed by a 0 symbol, i.e., n_ = SS … S0, where there are n S’s in the sequence, e.g. 6_ = SSSSSS0.


Later on, in the Section “Step 2: Axiomatizable Complete Theories are Decidable” (page 13) he calls a language “reasonable” if there is a function h in the language where V_ = h(V) applies, where V is a variable of the language (along with other conditions).


But the only definition of the underscore function n_ is a definition that only applies for n having the domain of natural numbers, that is, n can only take values that are natural numbers. So how can you have a V quantity of S’s if V is not a number? Answer - since V is a symbol that is a variable, not a number - you can’t.


A reader has suggested that the occurrence of an underscore in V_ may indicate that here Kim is introducing a new function using the same terminology as for the previously defined n_, without stating so explicitly. If that is the case, that is extremely bad practice. But even if it is the case, Kim is still saying that a language is “reasonable” if it includes a function h where the free variable has a domain that includes all variable symbols of the language - but then that free variable of h has a domain that includes that variable itself, which is nonsensical. Furthermore, Kim asserts in his Fixed Point Theorem (Section: “Step 3: The Incompleteness Theorems and Other Results”) that since the function dg is recursive, it is representable in Peano arithmetic - but Kim’s prior argument was that a function is representable in Peano arithmetic if it is a recursive and if it is a number-theoretic function –the function dg is not number-theoretic, since it is defined in terms of the h function, whose free variable has a domain that includes symbols that are not natural numbers.


If I was one of Kim’s students I would be questioning why I was attending university lectures to be taught this sort of nonsense. Kim’s definition of a “reasonable” language is a language where there is some variable in the language that can refer to all symbols of the language, including that variable itself - so that definition of a “reasonable” language would just be a definition of a self-referential language, which means that sentences of the language can refer to themselves. And it is not surprising that you will get paradoxes in such a language, in the same way that you can get a ‘liar’ paradox in a self-referential language like English. And if you are going to have a proof that applies to such languages, then you don’t need the vast amount of material that Kim uses to give a proof involving self-reference - all you have to do is apply something like the diagonal lemma, where your proof is only a page long. But it isn’t a proof that is going to apply to any logically valid formal system.


In summary, Kim’s appellation of “reasonable” would seem to be one of the worst misnomers ever. And his paper is just another nonsensical incompleteness proof where the flaw is hidden in page upon page of symbols and equations that may look impressive at first glance, but it is just another case of flash over substance.





Original critique of Gödel for Goldilocks

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





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




The Lighter Side



Recently added pages

How you can tell if someone is a crackpot


Platonism’s Logical Blunder


Richard’s Paradox


Alexander’s Horned Sphere


Curry’s Paradox


A review of Buldt’s The Scope of Gödel’s First Incompleteness Theorem


Lebesgue Measure

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



Illogical Assumptions

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



Easy Footnotes

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



O’Connor’s “computer checked” proof

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.


Previous Blog Posts  




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:

Gödel Links


– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines


Printer Friendly


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