• 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 get back to the top of the page anytime, press the Home key.

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

# Oh no ! Yet Another Flawed Incompleteness Proof

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

## A Flawed 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:

X

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.

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

An Incompleteness Proof by Byunghan Kim

An Incompleteness Proof by Antti Valmari

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

## NEWS

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

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

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.