A: Is Gödel’s reasoning really kosher?

Many scholars yet harbour a lingering suspicion that Gödel’s definition of his formally undecidable arithmetical proposition [(\forall x)R(x,p)] involves a latent contradiction—arising from a putative, implicit, circular self-reference—that is masked by unverifiable, even if not patently invalid, mathematical reasoning.

The following proof of Gödel’s Theorem VI of his 1931 paper is intended to:

\bullet strip away the usual mathematical jargon that shrouds proofs of Gödel’s argument which makes his—admittedly arcane—reasoning difficult for a non-logician to unravel;

and

\bullet show that, and why—unlike in the case of the paradoxical ‘Liar’ sentence: ‘This sentence is a lie’—Gödel’s proposition [(\forall x)R(x, p)] does not involve any circular self-reference that could yield a Liar-like contradiction, either in a formal mathematical language, or when interpreted in any language of common discourse.

B: Gödel’s 45 primitive recursive arithmetic functions and relations

We begin by noting that:

(1) In his 1931 paper on formally ‘undecidable’ arithmetical propositions, Gödel shows that, given a well-defined system of Gödel-numbering, every formula of a first-order Peano Arithmetic such as PA can be Gödel-numbered by Gödel’s primitive recursive relation #23, Form(x) , which is true if, and only if, x is the Gödel-number (GN) of a formula of PA.

(2) So, given any natural number n , (1) allows us to decompose n and effectively determine whether, or not, n is the GN of some PA formula.

(3) Gödel also defines a primitive recursive relation #44, Bw(x) , which is true if, and only if, x is the GN of a finite sequence of formulas in PA, each of which is either an axiom, or an immediate consequence of two preceding formulas in the sequence.

(4) So, given any natural number n , (3) allows us to effectively determine whether, or not, the natural number n is the GN of a proof sequence in PA.

(5) Further, Gödel defines a primitive recursive relation #45, xBy , which is true if, and only if, x is the GN of a proof sequence in PA whose last formula has the GN y .

(6) Gödel then defines a primitive recursive relation, say Q(x,y) \equiv xBSUBy , such that, for any m,n :

mBSUBn is true if, and only if, m happens to be a GN that can be decomposed into a proof sequence whose last member is some PA formula [F(n)] , and n happens to be a GN that decomposes into the PA-formula [F(u)] with only one variable [u] .

(7) The essence of Gödel’s Theorem VI lies in answering the question:

Query 1: Is there any natural number n for which mBSUBn is true?

C: Gödel’s reasoning in Peano Arithmetic

(8) Now, by Gödel’s Theorem VII (a standard representation theorem of arithmetic), xBSUBy can be expressed in PA by some (formally well-defined) formula [\neg R(x,y)] such that, for any m,n :

(a) If mBSUBn is true, then [\neg R(m,n)] is PA-provable;

(b) If \neg mBSUBn is true, then [R(m,n)] is PA-provable.

(9) Further, by (6) and (8), for any m,n , if n is the GN of F(x) then:

(a) If mBSUBn is true, then [R(m,n)] is PA-provable; and m is a PA-proof of [F(n)] ;

(b) If \neg mBSUBn is true, then [\neg R(m,n)] is PA-provable; and m is not a PA-proof of [F(n)] .

(10) In his Theorem VI, Gödel then argues as follows:

(a) Let q be the GN of the formula [R(x,y)] defined in (8).

(b) Let p be the GN of [(\forall x)R(x,y)] .

(c) Let r be the GN of [R(x,p)] .

(d) Let 17Gen\ r be the GN of [(\forall x)R(x,p)] .

(11) We note that all the above primitive recursive relations are formally well-defined within the standard primitive recursive arithmetic PRA; and all the PA-formulas—as well as their corresponding Gödel-numbers—are well-defined in the first-order Peano Arithmetic PA.

In other words, as Gödel emphasised in his paper, the 46—i.e., 45 + xBSUBy —PRA functions and relations that he defines are all bounded, and therefore effectively decidable as true or false over the domain N of the natural numbers; whilst the PA-formulas that he defines do not involve any reference—or self-reference—to either the meaning or the truth/falsity of any PA-formulas under an interpretation in N , but only to their PA-provability which, he shows, is effectively decidable by his system of Gödel-numbering and his definition of the primitive recursive relation xBy .

(12) If we now substitute p for n , and [(\forall x)R(x,p)] for [F(n)] , in (9) we have (since p is the GN of [(\forall x)R(x,y)] ) that:

(i) If mBSUBp is true, then [R(\neg m,p)] is PA-provable; whence m is a PA-proof of [(\forall x)R(x,p)] ;

(ii) If \neg mBSUBp is true, then [R(m,p)] is PA-provable; whence m is not a PA-proof of [(\forall x)R(x,p)] .

Hence n = p answers Query 1 affirmatively.

D: Gödel’s conclusions

(13) Gödel then concludes that, if PA is consistent then:

By (12)(i), if mSUBp is true for some m , then both [R(\neg m,p)] and [(\forall x)R(x,p)] are PA-provable—a contradiction since, by Generalisation in PA, the latter implies that [R(m,p)] is provable in PA.

Hence [(\forall x)R(x,p)] , whose GN is 17Gen\ r , is not provable in PA if PA is consistent.

(14) Moreover, if PA is assumed to also be \omega -consistent (which means that we cannot have a PA-provable formula [\neg (\forall x)F(x)] such that [F(m)] is also provable in PA for any given numeral [m] ) then:

By (13), m is not a PA-proof of [(\forall x)R(x,p)] for any given m ; whence [R(m,p)] is PA-provable for any given m by (12)(ii).

Hence [\neg (\forall x)R(x,p)] , whose GN is Neg(17Gen r) , is not provable in PA.

E: Gödel’s [(\forall x)R(x,p)] does not refer to itself

We note that Gödel’s formula [(\forall x)R(x,p)] —whose GN is 17Gen\ r — does not refer to itself since it is defined in terms of the natural number p , and not in terms of the natural number 17Gen\ r .

F: Somewhere, far beyond Gödel

The consequences of Gödel’s path-breaking answer to Query 1 are far-reaching (as detailed in this thesis).

For instance, taken together with the proof that PA is categorical with respect to algorithmic computability (Corollary 7.2 of this paper), and that PA is not \omega -consistent (Corollary 8.4 of this paper), the above entails that:

\bullet There can be no interpretation of Gödel’s definition of his formally undecidable arithmetical proposition [(\forall x)R(x),p] over the domain of the natural numbers—whether expressed mathematically or in any language of common discourse—that could lead to a contradiction;

\bullet Gödel’s [(\forall x)R(x,p)] is not a formally undecidable arithmetical proposition, since [\neg (\forall x)R(x,p)] is PA-provable (see Corollary 8.2 of this paper).

Author’s working archives & abstracts of investigations

Bhupinder Singh Anand