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

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

show that, and why—unlike in the case of the paradoxical ‘Liar’ sentence: ‘This sentence is a lie’—Gödel’s proposition 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, , which is true if, and only if, is the Gödel-number (GN) of a formula of PA.

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

(3) Gödel also defines a primitive recursive relation #44, , which is true if, and only if, 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 , (3) allows us to effectively determine whether, or not, the natural number is the GN of a proof sequence in PA.

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

(6) Gödel then defines a primitive recursive relation, say , such that, for any :

is true if, and only if, happens to be a GN that can be decomposed into a proof sequence whose last member is some PA formula , and happens to be a GN that decomposes into the PA-formula with only one variable .

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

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

**C: Gödel’s reasoning in Peano Arithmetic**

(8) Now, by Gödel’s Theorem VII (a standard representation theorem of arithmetic), can be expressed in PA by some (formally well-defined) formula such that, for any :

(a) If is true, then is PA-provable;

(b) If is true, then is PA-provable.

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

(a) If is true, then is PA-provable; and is a PA-proof of ;

(b) If is true, then is PA-provable; and is not a PA-proof of .

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

(a) Let be the GN of the formula defined in (8).

(b) Let be the GN of .

(c) Let be the GN of .

(d) Let be the GN of .

(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., —PRA functions and relations that he defines are all bounded, and therefore effectively decidable as true or false over the domain 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 , 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 .

(12) If we now substitute for , and for , in (9) we have (since is the GN of ) that:

(i) If is true, then is PA-provable; whence is a PA-proof of ;

(ii) If is true, then is PA-provable; whence is not a PA-proof of .

**Hence answers Query 1 affirmatively.**

**D: Gödel’s conclusions**

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

By (12)(i), if is true for some , then both and are PA-provable—a contradiction since, by Generalisation in PA, the latter implies that is provable in PA.

Hence , whose GN is , is not provable in PA if PA is consistent.

(14) Moreover, if PA is assumed to also be -consistent (which means that we cannot have a PA-provable formula such that is also provable in PA for any given numeral ) then:

By (13), is not a PA-proof of for any given ; whence is PA-provable for any given by (12)(ii).

Hence , whose GN is , is not provable in PA.

**E: Gödel’s does not refer to itself**

We note that Gödel’s formula —whose GN is — does not refer to itself since it is defined in terms of the natural number , and not in terms of the natural number .

**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 -consistent (Corollary 8.4 of this paper), the above entails that:

There can be no interpretation of Gödel’s definition of his formally undecidable arithmetical proposition over the domain of the natural numbers—whether expressed mathematically or in any language of common discourse—that could lead to a contradiction;

Gödel’s is not a formally undecidable arithmetical proposition, since is PA-provable (see Corollary 8.2 of this paper).

## 2 comments

Comments feed for this article

December 3, 2018 at 4:02 am

Abel PeraltaDear Bhup:

Excuse me, but someone who maintains that the undecidable sentence produces the omega-inconsistency of the system, cannot ignore the “latent contradiction”, which is not a persistent suspicion, but a textual reference: Gödel states openly in the introduction to the 1931 paper (pg 175) -176 original / 598-599 van Heijenoort: “The analogy between this result and Richard’s antinomy leaps to the eye; there is also a close relationship with the” liar “antinomy, since the undecidable proposition [R (q); q] states precisely that q belongs to K, ie according to (1), that [R (q); q] is not provable. We are therefore confronted with a proposition which asserts its own unprovability “).

More obvious evidence than this, I do not see possible …

Best regards.

Abel

December 5, 2018 at 3:22 pm

Bhupinder Singh AnandDear Abel,

You are absolutely right in concluding that:

(i) Gödel’s semantic definition of ‘‘, and therefore of ‘‘, is not only:

(a) self-referential under interpretation—in the sense of your citation (pp.597-598, van Heijenoort) from Gödel’s Introduction in his 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’ (pp.596-616, van Heijenoort);

but that:

(b) neither of the definitions can be verified by a deterministic Turing machine as yielding a valid formula of PM.

However, this non-constructiveness is a well-known and unremarkable characteristic of any set-theoretical system in which PM is interpreted, and we cannot conclude from this that:

(ii) Gödel’s formally undecidable P-formula, say —whose Gödel-number is defined as in Gödel’s proof of his Theorem VI (on pp.607-609 of van Heijenoort)—also cannot be verified by a deterministic Turing machine to be a valid formula of Gödel’s Peano Arithmetic P.

Reason: The axioms of set-theoretical systems such as PM, ZF, etc. would all admit—under a well-defined interpretation, if any—infinite elements, in the putative domain of any such interpretation, which are not Turing-definable.

I think it is Gödel who must be held responsible for the lack of a clear-cut distinction between the non-constructivity implicit in his semantic proof in (i), and the constructivity that he explicitly ensures for his syntactic proof in (ii).

Reason: Neither in his title, nor elsewhere in his paper, does Gödel categorically state that his goal was:

(iii) not only to demonstrate the existence of formally undecidable propositions in PM, a system which admits non-finitary elements under any putative interpretation;

(iv) but also to prevent the admittance of non-finitary elements—precisely those which would admit conclusions such as (ii)—when demonstrating the existence of formally undecidable propositions in ‘related’ systems such as his Peano Arithmetic P.

He merely hints at this by stating (see citation below from pp.587-589 of van Heijenoort) that his demonstration of (iii) is merely a sketch that lacked the precision which he intended to achieve in (iv) by:

(v) weakening the implicit assumption, of the decidability of the semantic truth of PM-propositions under any well-defined interpretation of PM, which underlies his proof of the existence of formally undecidable set-theoretical propositions in PM; and

(vi) insisting—in his proof of the existence of formally undecidable arithmetical propositions in his Peano Arithmetic P—upon the introduction of a methodology for constructively assigning unique truth values—that are verifiable by a Turing machine—to only those (primitive recursive) quantified number-theoretic assertions (#1 to #45 on pp.603-606 of van Heijenoort) that are bounded when interpreted over the domain N of the natural numbers.

“Before going into details, we shall first sketch the main idea of the proof, of course without any claim to complete precision. The formulas of a formal system (we restrict ourselves here to the system PM) in outward appearance are finite sequences of primitive signs (variables, logical constants, and parentheses or punctuation dots), and it is easy to state with complete precision which sequences of primitive signs are meaningful formulas and which are not….

The method of proof just explained can clearly be applied to any formal system that, first, when interpreted as representing a system of notions and propositions, has at its disposal sufficient means of expression to define the notions occurring in the argument above (in particular, the notion “provable formula”) and in which, second, every provable formula is true in the interpretation considered. The purpose of carrying out the above proof with full precision in what follows is, among other things, to replace the second of the assumptions just mentioned by a purely formal and much weaker one.”

From today’s perspective, one could reasonably hold that—as you contend—Gödel is misleadingly suggesting in the above quote that his definitions of ‘‘ and ‘‘ may be treated as yielding ‘meaningful’ formulas of PM which are well-definable constructively (in the sense of being definable by a deterministic Turing machine).

In my post I detail precisely why such an assumption would be fragile, by showing how the introduction of the boundedness Gödel insisted upon in (vi) distinguishes:

(vii) Gödel’s semantic proof of the existence of formally undecidable set-theoretical propositions in PM (pp.598-599 of van Heijenoort), which admits your contention (1);

from:

(viii) Gödel’s syntactic proof of the existence of formally undecidable arithmetical propositions in the language of his Peano Arithmetic P (pp.607-609 of van Heijenoort), which does not admit the corresponding contention (ii).

Moreover, we note that:

(1) Whereas Gödel can—albeit non-constructively—claim that his definition of ‘‘ yields a formula in PM, we cannot claim, correspondingly, that his primitive recursive formula is a formula in his Peano Arithmetic P.

(2) The latter is a number-theoretic relation defined by Gödel in terms of his primitive recursive relation #45, ‘‘, as:

#46. .

(3) In Gödel’s terminology, ‘‘ translates under interpretation over the domain N of the natural numbers as:

‘ is the Gödel-number of some provable formula of Gödel’s Peano Arithmetic P’.

(4) However, unlike Gödel’s primitive recursive functions and relations #1 to #45, both ‘‘ and ‘‘ are number-theoretic relations which are not primitive recursive—which means that they are not effectively decidable by a Turing machine under interpretation in N.

(5) Reason: Unlike in Gödel’s definitions #1 to #45 (see footnote 34 on p.603 of van Heijenoort, cited below), there is no bound on the quantifier ‘‘ in the definition of .

“Wherever one of the signs , , or occurs in the definitions below, it is followed by a bound on . This bound serves merely to ensure that the notion defined is recursive (see Theorem IV). But in most cases the extension of the notion defined would not change if this bound were omitted.”

Hence, by Turing’s Halting Theorem, we cannot claim—in the absence of specific proof to the contrary—that there must be some deterministic Turing machine which will determine whether or not, for any given natural number , the assertion is true under interpretation in N.

This is the crucial difference between Gödel’s semantic proof of the existence of formally undecidable set-theoretical propositions in PM (which admits your contention), and Gödel’s syntactic proof of the existence of formally undecidable arithmetical propositions in the language of his Peano Arithmetic P (which does not admit your contention).

(6) We cannot, therefore—in the absence of specific proof to the contrary—claim by Gödel’s Theorems V or VII that there must be some P-formula, say (corresponding to the PM-formula ), such that, for any given natural number :

(a) If is true under interpretation in N, then is provable in P;

(b) If is true under interpretation in N, then is provable in P.

Kind regards,

Bhup