Logic and Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2020 https://www.jamesrmeyer.com

Note: Full functionality of this website 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 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 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 1, 2, 3, … , 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:

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:

 

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

section divider

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

section divider

 

 

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 usernames for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong 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.

 

Note: a password enables editing of comments, an email enables notification of replies

HashOver logoBased on HashOver Comment System by Jacob BarkdullHashOver logo

Copyright   James R Meyer   2012 - 2020
https://www.jamesrmeyer.com