Oh no ! Yet Another Flawed Incompleteness Proof

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 PDF 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:

⊢ X

to signify “X is a theorem in N ” (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:

“X 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 B₁(n), B₂(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 1, 2, 3, … , so the general form of this enumeration is B_m(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) ⊢ B_k(n) ↔ ¬P(B_n(n))

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

(ii) ⊢ ∀n(B_k(n) ↔ ¬P(B_n(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(B_k(n) ↔ ¬P(B_n(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 B_k(n) ↔ ¬P(B_n(n)), then n is a free variable in B_k(n) ↔ ¬P(B_n(n)), which means that B_k(n) ↔ ¬P(B_n(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:

⊢ A ↔ ¬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:

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 PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System 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.

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 Dan Gusfield

An Incompleteness Proof by Byunghan Kim

An Incompleteness Proof by Dennis Müller

An Incompleteness Proof by Sebastian Oberhoff

An Incompleteness Proof by Antti Valmari