◄ Index                                                                                                                                  ◄ Main essay

 

Two presumptions in Gödel’s interpretation of his own, formal, reasoning that are classically objectionable

&

Some significant consequences of interpreting arithmetical ‘truth’ constructively in Gödel’s formal reasoning

 

Bhupinder Singh Anand[1]

(A .pdf file of this essay before the current update is available at http://arxiv.org/abs/math.GM/0703723)

Standard expositions of Gödel’s 1931 paper on undecidable arithmetical propositions are based on two presumptions in Gödel’s 1931 interpretation of his own, formal, reasoning - one each in Theorem VI and in Theorem XI - which do not meet Gödel’s requirement of classically constructive, and intuitionistically unobjectionable, reasoning. We see how these objections can be addressed, and note some significant consequences.

I       Gödel’s first, classically objectionable, presumption

I-1     Introduction

The difficulty in situating an interpretation[2] of Gödel’s first incompleteness theorem - Theorem VI in [Go31] - within the perspectives of classical (pre-Cantorian) reasoning, arises, simply, because standard expositions[3] of Gödel’s formal reasoning in his 1931 paper [Go31] on undecidable arithmetical propositions - which are, essentially, still based on Gödel’s interpretation of his own, formal, reasoning in this paper - have yet to explicitly recognise that:

(a)    the intuitive truth (i.e., truth in the standard model) of Gödel’s unprovable proposition - which, syntactically, is of the form [(∀x)R(x)] - follows strictly from the axioms and rules of inference of Peano Arithmetic;

(b)    all the axioms and theorems of Peano Arithmetic are algorithmically (Turing) computable arithmetical truths (when treated as Boolean functions) under the standard interpretation[4];

(c)    there may be arithmetical relations - such as the one constructed by Gödel in his 1931 paper - which are meta-mathematically provable as instantiationally computable (Turing-decidable) truths, but which may not necessarily be algorithmically computable (Turing-computable) truths.

(d)    Gödel’s presumption that his formal system, P, of Peano Arithmetic can be assumed ω-consistent, without inviting inconsistency, is classically objectionable. Under a constructive introduction of formal, arithmetical, truth in Gödel’s formal reasoning, any first-order Peano Arithmetic is naturally ω-inconsistent, and has no non-standard models (one significant consequence of this is that P ≠ NP[5]).

I-2     The truth of Gödel’s unprovable proposition follows strictly from the axioms and rules of inference of Peano Arithmetic

It is a common misconception that an arithmetical statement - such as the one constructed by Gödel - can be intuitively true, and yet remain formally unproven from the axioms and rules of inference of a first order Peano Arithmetic.[6]

However, the intuitive truth of Gödel's unprovable proposition is formally proven in PA, since it does follow strictly from the axioms and rules of inference of PA.[7]

To see this, we note that the first part of Gödel’s argument in Theorem VI of his 1931 paper [Go31] is, simply, that, if PA is consistent, then we can mechanically[8] construct a PA formula - which, syntactically, is of the form [(∀x)R(x)] - such that:

(i)     the formula [(∀x)R(x)] - when expressed purely as a string of symbols - does not follow mechanically from the axioms of PA as the last of any finite sequence of PA-formulas, each of which is either a PA-axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of PA;

(ii)    for any given numeral [n] - which ‘represents’ the natural number n in PA - the formula [R(n)] - again, when expressed purely as a string of symbols - does follow mechanically from the axioms of PA as the last of some finite sequence of PA-formulas, each of which is either a PA-axiom, or a consequence of one or more of the formulas preceding it in the sequence, by the mechanical application of the rules of inference of PA.

Now, (i) is, essentially, the standard definition (due to Gödel [Go31]) of the meta-assertion:

(iii)   The PA-formula [(∀x)R(x)] is formally unprovable in PA,

whilst (ii) is, essentially, the standard definition (due to Tarski[9]) of the meta-assertion:

(iv)   The PA-formula [(∀x)R(x)] is formally true in PA.

Hence, by definition, the appropriate interpretation of Gödel’s reasoning (i) and (ii) ought to be[10]:

(v)    The PA-formula [(∀x)R(x)] is formally unprovable in PA, but formally true in PA.[11]

However standard expositions of Gödel’s formal reasoning in [Go31] assert only that:

(vi)   The PA-formula [(∀x)R(x)] is formally unprovable in PA, but intuitively true in the standard interpretation of PA.

They, thus, fail to highlight the fact that (i) and (ii), both, actually, follow formally from the axioms and rules of inference of PA, and that, classically, the meta-assertion:

(vii)  The PA-formula [(∀x)R(x)] is intuitively true in the standard interpretation of PA,

is, both, ambiguous and stronger[12] than the meta-assertion:

(viii) The PA-formula [R(x)] is formally true in the standard interpretation of PA.

Further, they fail to recognise that, both, (vii) and (viii), assert the instantiational - but not necessarily algorithmic - PA-provability of a denumerable infinity of arithmetical propositions.

Moreover, they do not explicitly consider the question:

When is a formally true PA-formula, such as, say, Gödel’s [(∀x)R(x)], also a formally provable PA-formula?

At this point, we need to digress a little.

I-3     The axioms and theorems of Peano Arithmetic are algorithmically (Turing) computable truths under the standard interpretation

It follows from Turing’s 1936 paper [Tu36] that if the formula, say, [R'(x₁, x₂, x₃ …, x_n)][13], is either an axiom, or a theorem[14], of a Peano Arithmetic (such as the system P considered by Gödel in his 1931 paper), then, there is always a Turing-machine[15], T, such that, given any set of natural numbers (a₁, a₂, a₃ …, a_n) as input, T will compute the arithmetical proposition R'(a₁, a₂, a₃ …, a_n) as TRUE in a finite number of steps (Appendix A).

In other words, one of Turing’s remarkable, albeit unremarked, achievements - in [Tu36] - is to enable a formal, and constructive, definition (in the best traditions of the standards for mathematical rigour - established in the nineteenth century by mathematicians, such as Cauchy, Weierstrass, etc.[16] - that are to be adopted when the concept of infinity is used in mathematical reasoning) of what is meant, intuitively, by the assertion that the infinity of arithmetical assertions encapsulated in the axioms and rules of inference of Peano Arithmetic are intuitively true[17].

Consequently, one of Gödel’s even more remarkable[18], but equally unremarked, achievements - in [Go31] - lies in his actual construction (using only classically acceptable reasoning) of a formula of one variable, say [R(x)], in his formal system, P, such that:

(iii)   [(∀x)R(x)] is not a theorem of P (assuming that P is consistent);

(iv)   given any natural number a, there is a Turing-machine T_a that will compute the arithmetical proposition R(a) as TRUE in a finite number of steps.

The remarkable, but unremarked, feature of the above is that we cannot assume from it that there must be a Turing machine T' such that, given any natural number a, T' will compute the arithmetical proposition R(a) as TRUE in a finite number of steps.[19]

We now show some significant consequences of explicitly recognising this feature.

I-4     The distinction between Turing-decidability (classical verifiability) and Turing-computability

We note, first, that the precise definition of the algorithmic computability of number-theoretic functions - formalised by Turing in his 1936 paper [Tu36] on computable numbers - allows the following distinction to be made, between the instantiational decidability of number-theoretic relations, and their algorithmic computability (when treated as Boolean functions), as follows:

Definition 1: A total number-theoretical relation, say R'(x₁, x₂, ..., x_n), when treated as a Boolean function, is Turing-decidable in M if, and only if, it is instantiationally equivalent to a number-theoretic relation, S(x₁, x₂, ..., x_n), and there is a Turing-machine T such that, for any given natural number sequence, (a₁, a₂, ..., a_n), T will compute S(a₁, a₂, ..., a_n) as either TRUE, or as FALSE.

Definition 2: A total number-theoretical relation, R'(x₁, x₂, ..., x_n), when treated as a Boolean function, is Turing-computable in M if, and only if, there is a Turing-machine T such that, for any given natural number sequence, (a₁, a₂, ..., a_n), T will compute R'(a₁, a₂, ..., a_n) as either TRUE, or as FALSE.

We note, next, that, although Turing-decidability (which is, essentially, constructive verifiability in the classical sense) of a number-theoretic relation necessarily implies Turing-computability, the converse need not hold[20].

Thus, classically, a number-theoretic relation, such as, say, Gödel’s R(x), would be decidable (Turing-decidable) as true if it were instantiationally equivalent, for any given natural number, to a number-theoretic relation, S(x), which could be interpreted as a Turing-algorithm, and which is Turing-computable as TRUE for any given natural number.

However, we cannot conclude from this that R(x) must also be interpretable as a Turing-algorithm, and be Turing-computable as TRUE for any given natural number.

In other words - as in the case of Turing’s Halting function - the definition of R(x) may involve a, possibly implicit, circular reference to the range of values of R(x).

Consequently, any Turing-machine that computes R(x) could go into a non-terminating loop for some input (i.e., in the language of Turing-machines, an instantaneous tape description could be repeated in the course of the computation for that input).

Now, in his 1931 paper [Go31], Gödel only shows that, if PA is consistent, then his R(x) is Turing-decidable as always TRUE (when treated as a Boolean function).

The Turing-decidability of Gödel’s R(x) follows from the fact that R (x) is defined constructively by Gödel (as a consequence of Theorem VII of [Go31]) so that it is instantiationally equivalent to a primitive recursive relation which, of course, is known to be Turing-computable.

However, the question remains:

Is R(x) also Turing-computable as always TRUE (when treated as a Boolean function)?

If we interpret Gödel’s reasoning with the above distinction in mind, then we have a tentative answer to the question raised at the end of Section I-2:

Gödel’s PA-formula [(∀x)R(x)] may be[21] formally unprovable, but formally true, simply because the arithmetical relation R(x) is a ‘Halting’ type of relation that is Turing-decidable as always TRUE, but not Turing-computable as always TRUE[22].

I-5     Gödel’s first, classically objectionable, presumption

It is intriguing to speculate on why the above distinction was not considered by Gödel even after Turing’s publication of his paper [Tu36] on computable numbers.

A contributing factor may have been his 1931 commitment to the first of his classically objectionable presumptions:

The assumption of ω-consistency for P will not lead to an inconsistency.[23]

This allowed him to meta-mathematically argue further - again, using only classically acceptable reasoning - that the formula [¬(∀x)R(x)] is, also, not a theorem of an ω-consistent P.

Another factor may have been Gödel’s reluctant acceptance, along with Church, of the latter’s 1936 thesis (now known as the Church-Turing Thesis) identifying effectively computable[24] number-theoretic functions with algorithmically computable number-theoretic functions [Ch36].

From the first, Gödel concluded his first incompleteness theorem (Theorem VI of his 1931 paper), to the effect that, if P can be assumed ω-consistent, then the formulas [(∀x)R(x)] and [¬(∀x)R(x)] are, both, not provable in P.

The second may, quite possibly, have prevented him from recognising the possibility, and significance, of number-theoretic relations that are Turing-decidable (i.e., they are effectively computable as true instantiationally), but not Turing-computable (i.e., they are not effectively computable as true algorithmically).

I-6     Why the assumption of ω-consistency in a Peano Arithmetic is classically objectionable, and may invite inconsistency

We now see how, and why, Gödel’s presumption - that P can be assumed ω-consistent without inviting inconsistency - is classically objectionable, and how it obscures the significance of his primary achievement - that of constructing a number-theoretic, arithmetical, relation that may be Turing-decidable (i.e., it is effectively computable as always TRUE instantiationally), but not Turing-computable (i.e., it is not effectively computable as always TRUE algorithmically).

Now, Gödel defines P as ω-consistent if, and only if, there is no P-formula, such as, say, his [R(x)], for which:

(i)   [¬(∀x)R(x)] is P-provable,

and, also:

(ii)  [R(n)] is P-provable for any given numeral [n] of P.

The possible inconsistency in an ω-consistent P surfaces only when we try to interpret the above definition verifiably in our classical arithmetic based on Dedekind’s Peano Postulates (termed as the “standard, intuitive, interpretation of Peano Arithmetic”), which Gödel’s system P was intended to formalise recursively (hence, implicitly, algorithmically).

Now, it is reasonable to suppose that Gödel’s tacit justification for the presumption of ω-consistency as an intuitively natural, and ‘obviously’ consistent, meta-property of P lay in the following argument:

(a)  if [¬(∀x)R(x)] is P-provable, then the meta-proposition, “R(x) is true for all natural numbers x”, is false[25],

and:

(b)  if [R(n)] is P-provable for any given numeral [n] of P, then the meta-proposition, “R(x) is true for all natural numbers x”, is true.

However, note, first, that, even if we strictly apply Tarski’s definitions to the satisfiability, and truth, of the formulas of a Peano Arithmetic under its standard, intuitive, interpretation, the meta-assertion:

(c)   R(x) is true for all natural numbers x,

is ambiguous, and can be taken to mean either:

(d)  R(x) is Turing-computable as always TRUE (i.e., any Turing-machine that computes R(x) will halt on any given natural number x as input and return the value TRUE);

 or:

 (e)  R(x) is Turing-decidable as always TRUE (i.e., R(x) is instantiationally equivalent to a number-theoretic function, say S(x), which is such that any Turing-machine that computes S(x) will halt on any given natural number x as input and return the value TRUE);

and, second, that the latter need not, necessarily, imply the former.

It follows that we can, indeed, have that:

(f) if [¬(∀x)R(x)] is P-provable, then the meta-proposition, “R(x) is Turing-computable as always TRUE”, is false

and, at the same time, that:

(g) if [R(n)] is P-provable for any given numeral [n] of P, then the meta-proposition, “R(x) is Turing-decidable as always TRUE”, is true. 

I-7     A constructive interpretation of ω-consistency implies that Gödel’s (first incompleteness) Theorem VI may be vacuously true

It follows that Gödel’s presumption - that assuming ω-consistency for P will not lead to an inconsistency - is not intuitively unobjectionable.

Hence his argument for the construction of an ‘undecidable’ proposition in P, too, cannot be considered classically constructive, and intuitionistically unobjectionable.

It also follows that we cannot, further, conclude from Gödel’s reasoning that his proposition, [¬(∀x)R(x)], is necessarily P-unprovable.

I-8     Rosser’s argument, too, implicitly assumes that Peano Arithmetic is ω-consistent

Contrary to the accepted view, an analysis of Rosser’s ‘extension’ of Gödel’s argument [Ro36] shows that he also assumes - albeit, implicitly[26] - that P is ω-consistent.

Thus, a formal exposition of Rosser’s proof ([Ro36], Theorem II), such as [Me64], depends upon the argument, at one point[27], that, if we assume that a formula such as, say, [(∃x)F(x)], is provable in a consistent P, then we can assume, further, that there is some P-formula, say [a], such that [F(a)] is provable.

The proof, then, argues that the P-provability of [F(a)] leads to a contradiction, and concludes that [(∃x)F(x)] cannot be P-provable.

Now, if P were ω-inconsistent, then, since, formally, [(∃x)F(x)] is defined as [¬(∀x)¬F(x)], we can, indeed, have, both, that [¬(∀x)¬F(x)] is P-provable, and that [¬F(x)] is also P-provable for all substitutions of a P-formula [a] for [x].

Hence, unless we assume that P is ω-consistent, we cannot conclude, from the P-provability of [¬(∀x)¬F(x)], that there is, necessarily, some P-formula, say [a], such that [F(a)] is provable.[28]

I-9     If Peano Arithmetic is ω-inconsistent, then it may have no non-constructive, non-standard, models

Now, if we cannot conclude that [¬(∀x)R(x)] is necessarily not P-provable, then we cannot conclude that we can add [¬(∀x)R(x)] as an axiom to P and obtain a consistent, extended, system of Peano Arithmetic, which contains numbers that are not natural numbers.

However, it is precisely this unvalidated presumption by Gödel - namely that P+[¬(∀x)R(x)]  is consistent [Go31] - which appears to underpin the postulation of non-standard models[29] of Peano Arithmetic.

These are models that postulate the existence of numbers, satisfying the axioms of Peano Arithmetic, which exist in the domain of an interpretation, and can, possibly, be named, but which are not numerals, and, so, cannot be constructed within the Arithmetic.

In Appendix B we show, however, that all the elements in the domain of any model of PA are necessarily the numerals (which, by definition, are the successors of 0) and so PA has no non-standard models.

Hence, if we cannot add [¬(∀x)R(x)] as an axiom to P without inviting inconsistency, it follows that P is ω-inconsistent.

I-10   A significant consequence of a constructive interpretation of Gödel’s reasoning in Theorem VI of his 1931 paper: P ≠ NP

We are, thus, compelled to seek alternative, and more constructive, interpretations of the significance, and consequences, of Gödel’s reasoning in his 1931 paper.[30]

One of the more significant consequences is that if a total arithmetical relation is Turing-computable as always TRUE, then it is PA-provable.

For, if we assume that there is a total arithmetical relation that is Turing-computable as always TRUE, but which is not the standard interpretation of a PA-provable formula, then this implies that there is a non-standard model of PA.

Another significant consequence follows from the argument that (cf. [Ra02]), if there is no polynomial time algorithm A that gets as input a Boolean formula f and outputs 1 if and only if f is a tautology, then P ≠ NP.

Hence Gödel’s reasoning in Theorem VI of [Go31] - to the effect that there is a total arithmetical relation that is Turing-decidable as always TRUE, but which is not Turing-computable as always TRUE - implies that P ≠ NP!

II     Gödel’s second, classically objectionable, presumption

II-1    Gödel’s reasoning in his (second incompleteness) Theorem XI

The second of Gödel’s classically objectionable presumptions pertains to the reasoning by which he constructs another P-formula, [W] (say, with Gödel-number w), and concludes that, when [W] is interpreted in our intuitive arithmetic of the natural numbers (as covered by Dedekind’s formulations of the Peano Axioms), it intuitively translates as an arithmetical proposition that is true if, and only if, a specified formula of P is unprovable in P.

Now, if there were such a P-formula as [W] which interprets, and intuitively translates, as above, and we could prove [W] in P, then the above would imply that there is a proof sequence in P to the effect that P contains an unprovable formula, and so we would have proved that P is consistent by a proof sequence within P.

This follows since, classically, an inconsistent system necessarily proves every well-formed formula of the system.

However, Gödel shows - again by classical reasoning - that his formula [W] is not P-provable.

From this he concludes his second incompleteness theorem (Theorem XI of his 1931 paper), to the effect that the consistency of a Peano Arithmetic cannot be proven within the Arithmetic.

II-2    Gödel presumes that he has constructed an arithmetical proposition that translates intuitively as true if, and only if, P is consistent

Now, the classically objectionable presumption made by Gödel is that, when the P-formula [W] is interpreted in our intuitive arithmetic of the natural numbers (as covered by Dedekind’s formulations of the Peano Axioms), it intuitively translates as an arithmetical proposition, say W, that is true if, and only if, a specified formula of P is unprovable in P.

To see the classically objectionable step of Gödel’s reasoning in Theorem XI of his 1931 paper, it is necessary to see how Gödel shows, in a constructive, and intuitionistically unobjectionable manner, how meta-propositions of a formal Peano Arithmetic, say P, can be defined by means of primitive recursive functions and relations using only classical reasoning.

II-3    Gödel defines 45 number-theoretic primitive recursive functions and relations

Amongst the 46 such number-theoretic functions and relations defined by Gödel, in a classically constructive manner, are the following:

(#12)  A number-theoretic primitive recursive relation, Var(x), which is true if, and only if, x is the Gödel-number[31] of a variable of P.

(#13)  A number-theoretic primitive recursive function, Neg(x), which is the Gödel-number of the negation of the formula of P whose Gödel-number is x.

(#14)  A number-theoretic primitive recursive relation, xDisy, which is true if, and only if, the disjunction of the formulas of P, whose Gödel-numbers are x and y, is true.

(#15)  A number-theoretic primitive recursive function, xGeny, which is true if, and only if, the generalisation of the formula of P whose Gödel-number is y, by the formula whose Gödel-number is x, is true (assuming that x is the Gödel-number of a formula of P that is a variable).

(#17)  A number-theoretic primitive recursive function, Z(n), which is the Gödel-number of the numeral of P that represents the natural number n.

(#20)  A number-theoretic primitive recursive relation, Elf(x), which is true if, and only if, x is the Gödel-number of an elementary formula of P.

(#22)  A number-theoretic primitive recursive relation, FR(x), which is true if, and only if, x is the Gödel-number of a sequence of formulas of P, each one of which is either an elementary formula of P, or comes from the preceding ones by the operations of negation, disjunction, or generalisation.

(#23)  A number-theoretic primitive recursive relation, Form(x), which is true if, and only if, x is the Gödel-number of a formula of P (i.e., the last term of a sequence of formulas).

(#26)  A number-theoretic primitive recursive relation, vFrx, which is true if, and only if, x is the Gödel-number of a formula of P in which the variable of P, whose Gödel-number is v, is free.

(#29)  A number-theoretic primitive recursive function, A(v, x), which is the number of places at which the variable of P, whose Gödel-number is v, is free in the formula of P whose Gödel-number is x.

(#42)  A number-theoretic primitive recursive relation, Ax(x), which is true if, and only if, x is the Gödel-number of an axiom of P.

(#43)  A number-theoretic primitive recursive relation, Fl(x, y, z), which is true if, and only if, x is the Gödel-number of a formula of P that is an immediate consequence of the formulas of P whose Gödel-numbers are y and z.

(#44)  A number-theoretic primitive recursive relation, Bw(x), which is true if, and only if, x is the Gödel-number of a proof sequence in P (a finite sequence of formulas of P each of which is either an axiom of P, or an immediate consequence of two preceding formulas of the sequence).

(#45)  A number-theoretic primitive recursive relation, xBy, which is true if, and only if, x is the Gödel-number of a proof sequence of P whose last formula has the Gödel-number y.

The classically constructive, and intuitionistically unobjectionable, nature of the 45 representations of various meta-mathematical propositions by primitive recursive functions and relations is assured by Gödel by the following specification (in a footnote):

“Everywhere in the following definitions where one of the expressions ‘(∀x)’, ‘(∃x)’, ‘(There is a unique x)’ occurs it is followed by a bound for x. This bound serves only to assure the recursive nature of the defined concept.”

In sharp contrast to the above 45 definitions, Gödel explicitly defines one further meta-mathematical relation that cannot be asserted to be recursive:

The number-theoretic relation, Bew(x), which is true if, and only if, x is the Gödel-number of a provable formula of P.

Gödel's actual definition of this is:

(#46)  The number-theoretic primitive recursive relation, Bew(x), is true if, and only if, the number-theoretic relation (∃y)yBx[32] is true.

The significance of the distinction, between the first 45 definitions and the 46^th, is that, by Gödel’s Theorem VII (which is independent of his Theorem VI, and should actually have preceded it), it can be shown that any recursive relation, say Q(x), can be represented in P by some, corresponding, arithmetical formula, say [R(x)], such that, for any natural number n:

If Q(n) is true, then [R(n)] is P-provable

If Q(n) is false, then [¬R(n)] is P-provable.

Now, Gödel’s Theorem VI establishes that the above representation does not extend to the closure of a recursive relation, in the sense that we cannot assume:

If (∀x)Q(x) is true (over all the natural numbers), then [(∀x)R(x)] is P-provable.

In other words, we cannot assume that, even though the recursive relation, Q(x), can be represented in P by some arithmetical formula, the number-theoretic proposition (∀x)Q(x) must, necessarily, also be representable similarly.

Now, we note that, in recursive arithmetic - in sharp contrast to formal Peano Arithmetic - the expression ‘(∃x)’ is not an abbreviation for ‘¬(∀x)¬’, but for the intuitive assertion:

There is some (at least one) x such that…

Consequently, although a primitive recursive relation may be instantiationally equivalent to the standard interpretation of a PA-formula (cf. Gödel’s Theorem VII [Go31]), we cannot assume that the existential closure of the relation must have the same intuitive meaning as the standard interpretation of the existential closure of the PA-formula.

However this, precisely, is the, intuitively objectionable, presumption made by Gödel (implicitly, and without offering any justification) in his Theorem XI, where he concludes that the consistency of P is not P-provable.

Thus, he first defines the notion of “P is consistent” in a classically constructive, and intuitionistically unobjectionable, manner, as follows:

P is consistent if, and only if, the number-theoretic relation Wid(P) is true.

Here, Wid(P) is defined by the number-theoretic relation:

(∃x)[Form(x) & ¬(Bew(x)]

The above translates intuitively as:

There is a natural number x such that x is the Gödel-number of a formula of P, and this formula is not P-provable.

That this implies the consistency of P follows from the classical definition of the consistency of any formal axiomatic theory, since, if the theory were inconsistent, then every well-formed formula of the theory would be provable within the theory.

Now, Gödel’s classically objectionable step lies in his presumption that Wid(P) can be represented ([Go31] uses the term “expressed”) by some formula [W] of P, with Gödel-number w, that, under the standard interpretation, maintains its intuitive meaning.

To see why the presumption is objectionable from another perspective, it is sufficient to note that Gödel also presumes in the proof of his Theorem XI [Go31] - again without offering adequate justification - that if the recursive relation, Q(x, p), is represented by the P-formula [R(x, p)], whose Gödel-number is r, then (∀x)Q(x, p) can be “expressed” in P by the formula [(∀x)R(x, p)], whose Gödel-number is 17Genr, in such a manner that the proposition “[(∀x)R(x, p)] is true” has the same intuitive meaning, under the standard interpretation, as “(∀x)Q(x, p) is true”.

As noted earlier, such an assumption does, indeed, follow if R(x, p) is Turing-computable as always TRUE, but it may not follow if R(x, p) is Turing-decidable as always TRUE, but not Turing-computable as always TRUE.[33]

In other words, if [W], too, is unprovable but true in P, then the consistency of P is, in fact, provable instantiationally in P.

Hence, at best, Gödel’s reasoning can only be taken to establish that the consistency of P is unprovable algorithmically in P.

The significance of this is that we can no longer argue that, if the consistency of a system that contains a Peano Arithmetic is, somehow, provable within the system, then the system must be inconsistent.

This conclusion can only be drawn for such a system if it purports to prove its own consistency algorithmically.

However, Gödel’s definition of Wid(P) does not claim this.

Appendix A: The Theorems of PA interpret as Turing-computable truths

Consider the axioms of PA:

(S1)  [(x₁ = x₂) → ((x₁ = x₃) → (x₂ = x₃))];

(S2)  [(x₁ = x₂) → (x₁' = x₂')];

(S3)  [0 ≠ (x₁)'];

(S4)  [((x₁)' = (x₂)') → (x₁ = x₂)];

(S5)  [(x₁ + 0) = x₁];

(S6)  [(x₁ + x₂') = (x₁ + x₂)'];

(S7)  [(x₁*0) = 0]

(S8)  [(x₁*( x₂')) = ((x₁* x₂) + x₁)];

(S9)  For any well-formed formula [F(x)] of PA:
[(F(0) → (∀x)(F(x) → F(x'))) → (∀x)F(x)].

Now, each of the PA axioms - except Induction - can, intuitively, be seen to be Turing-computable as always TRUE in the following sense:

(i) A total number-theoretical relation, R(x₁, x₂, ..., x_n), when treated as a Boolean function, is Turing-computable if, and only if, there is a Turing-machine T such that, for any given natural number sequence, (a₁, a₂, ..., a_n), T will compute R(a₁, a₂, ..., a_n) as either TRUE, or as FALSE.

(ii) If [R] is an atomic formula [R(a₁, a₂, ..., a_n)] of PA, then [R] is Turing-computable as TRUE for the natural number input (a₁, a₂, ..., a_n) if, and only if, the arithmetical relation R(a₁, a₂, ..., a_n) is Turing-computable as TRUE on the natural number input (a₁, a₂, ..., a_n);

(iii) The PA-formula [¬R] is Turing-computable as TRUE for the natural number input (a₁, a₂, ..., a_n) if, and only if, [R] is Turing-computable as FALSE for the natural number input (a₁, a₂, ..., a_n);

(iv) The PA-formula [R => S] is Turing-computable as TRUE for the natural number input (a₁, a₂, ..., a_n) if, and only if, either [R] is Turing-computable as FALSE for the natural number input (a₁, a₂, ..., a_n), or [S] is Turing-computable as TRUE for the natural number input (a₁, a₂, ..., a_n);

(v) The PA-formula [(∀x_i)R] is Turing-computable as TRUE for the natural number input (a₁, a₂, ..., a_n) if, and only if, [R] is Turing-computable as TRUE for any given natural number input (b₁, b₂, ..., b_n) where (b₁, b₂, ..., b_n) differs from (a₁, a₂, ..., a_n) in at most the i’^th component.

(vi) The PA-formula [(∀x_i)R] is Turing-computable as TRUE for the natural number input (a₁, a₂, ..., a_n) if, and only if, [R] is Turing-computable as TRUE for any given natural number input (b₁, b₂, ..., b_n) where (b₁, b₂, ..., b_n) differs from (a₁, a₂, ..., a_n) in at most the i’^th component.

(vii) The PA-formula [R] is Turing-computable as always TRUE if, and only if, [R] is Turing-computable as TRUE for any given natural number input (a₁, a₂, ..., a_n).

(viii) The PA-formula [¬R] is Turing-computable as always FALSE if, and only if, [R] is Turing-computable as TRUE for any given natural number input (a₁, a₂, ..., a_n).

Thus, if we assume, for instance, that axiom (S1) is intuitively true in the Tarskian sense - i.e., that the PA-formula, [(x₁ = x₂) → ((x₁ = x₃) → (x₂ = x