Section 2

Index

Section 4

 

Section 3 : Is Mendelson’s use of the Gödel β-function valid?

B. S. Anand

We derive a simple inconsistency from Mendelson’s proof of Gödel’s Theorem VI. We trace the source of the inconsistency to an invalid application of the Gödel β-function for constructing a formula of the formal system that would strongly represent a recursive function.

1 Gödel’s Theorem VI

In his version[1] of Gödel’s Theorem VI[2], Mendelson defines a primitive recursive relation W1(u, y) which he postulates as holding if and only if u is the Gödel-number of a well-formed formula A(x1), of his formal system[3] S, containing the free variable x1, and y is the Gödel-number of a proof in S of A(u)[4].

Since the relation W1(u, y) is primitive recursive, by Mendelson’s postulation[5] W1 is expressible in S by a well-formed formula W1(x1, x2) with two free variables x1, x2, i.e. if W1(k1, k2), then ├S W1(k1, k2) [6], and, if not-W1(k1, k2), then ├S ~W1(k1, k2).

Mendelson then considers the well-formed formula :

(i)         (x2) ~W1(x1, x2)

Assuming m to be the Gödel-number of the well-formed formula §1(i), he substitutes the numeral m for x1 in §1(i) to obtain the well-formed formula :

(ii)        (x2) ~W1(m, x2)

Since m is the Gödel-number of the well-formed formula §1(i), and §1(ii) comes from §1(i) by substituting the numeral m for the variable x1, he concludes that :

(iii)       W1(m, y) holds if and only if y is the Gödel-number of a proof in S of the well-formed formula §1(ii)[7].

2 Mendelson’s version of Gödel’s proof

Mendelson then argues that :

(1) Assume S is consistent, and assume that ├S (x2) ~W1(m, x2). Let k be the Gödel-number of a proof in S of this well-formed formula. By §1(iii) above, W1(m, k) holds. Since W1 expresses W1 in S, we have ├SW1(m, k). From (x2)~W1(m, x2) we deduce ~W1(m, k) [8]. Thus, W1(m, k) and ~W1(m, k) are provable in S, contradicting the consistency of S.[9]

(2) Assume S is ω-consistent[10], and assume that ├S ~ (x2) ~W1(m, x2), i.e., ├S~§1(ii). Since S is consistent, we have that not-├S §1(ii). Therefore, for every natural number n, n is not the Gödel-number of a proof in S of §1(ii), i.e., by §1(iii), for every n, W1(m, n) is false. So, for every n, ├S ~W1(m, n). If we let A(x2)[11] be ~W1(m, x2), then, by the ω-consistency of S, it follows that not-├S (Ex2) ~ ~W1(m, x2); hence not-├S (Ex2) W1(m, x2). But this contradicts our assumption that ├S (Ex2) W1(m, x2).[12]

Mendelson thus concludes that the sentence §1(ii) is undecidable in S.

3 Why is this reasoning ignored?

However, Mendelson also[13] ignores the following straightforward reasoning that leads from his preceding premises to a simple inconsistency in S.

We consider the well-formed formula :

(i)         ~W1(x1, x2)

Assuming r to be the Gödel-number of the well-formed formula §3(i), we substitute the numeral r for x1 in §3(i) to obtain the well-formed formula :

(ii)        ~W1(r, x2)

Since r is the Gödel-number of the well-formed formula §3(i), and §3(ii) comes from §3(i) by substituting the numeral r for the variable x1, we conclude that :

(iii)       W1(r, y) holds if and only if y is the Gödel-number of a proof in S of the well-formed formula §3(ii).

We now note that :

(1) Assume S is consistent, and assume that ├S ~W1(r, x2). Let k be the Gödel-number of a proof in S of this well-formed formula. By §3(iii) above, W1(r, k) holds. Since W1 expresses W1 in S, we have the contradiction ├SW1(r, k). Hence we have not-├S ~W1(r, x2), i.e. ~W1(r, x2) is not provable in S.[14]

(2) We thus have that ~W1(r, n) is not provable in S for every n[15]. Since W1 expresses W1 in S, and W1 is primitive recursive, we also have that if ~W1(r, n) holds for every natural number n, then ~W1(r, n) is provable in S for every n[16]. It now follows that if ~W1(r, n) is not provable in S for every n, then ~W1(r, n) does not hold for all n. Since W1 is primitive recursive, we thus have that W1(r, l) holds for some l. By §3(iii), it follows that some l is then a proof of §3(ii), and so we have the contradiction ├S ~W1(r, x2).[17]

4 The inconsistency in S

We thus have the inconsistency in the meta-theory M of S :

The primitive recursive formula ~W1(r, x2) is provable in S M The primitive recursive formula ~W1(r, x2) is not provable in S, and

The primitive recursive formula ~W1(r, x2) is not provable in S M The primitive recursive formula ~W1(r, x2) is provable in S.

5 Every primitive recursive formula is not expressible formally in a consistent S

Since S is assumed consistent, the above establishes that the primitive recursive formula W1(u, y) cannot be expressed in S.

Mendelson’s assertion in his Proposition 3.23[18], mirroring Gödel’s implicit postulation in his Theorem V that every primitive recursive formula is strongly[19] representable in S, is thus invalid.

6 Conclusion : The fallacy in Mendelson’s reasoning

The cause of the inconsistency is Mendelson’s invalid use of the Gödel β-function[20] for constructing a formula of the formal system that would strongly represent a recursive function.

Clearly Mendelson’s definition and development of the β-function in his Propositions 3.21-3.23 can be validly used, as explicitly proved by him, to construct a formula representing a finite sequence of undetermined length.

However, it cannot validly be used - as claimed by him without proof[21] - to construct a formula strongly representing a recursive function, which is essentially an infinite sequence of indeterminate length, as such strong representation involves implicitly defining an infinite number of β-functions, a definition of doubtful validity[22].

Notes (Why03bt.doc : 4/3/01 5:24:57 PM)

 

 



The author welcomes correspondence. Requests for copies of the author’s work should be addressed to anandb@vsnl.com.



[1] [Mendelson 1964 : p142-144]

[2] [Gödel 1931 : p22]

[3] Mendelson’s formal system S differs significantly from that considered by Gödel in his seminal 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’ [Gödel 1931 : p9-13], in that he includes addition and multiplication as primitive undefined symbols. [Mendelson 1964 : p102-103]

[4] We use bold lettering to denote the numeral ‘u’ in S that corresponds to the natural number ‘u’.

[5] On the basis of his Propositions 3.22 and 3.23 Mendelson postulates, without a rigorous proof, that every primitive recursive function is strongly representable in S.

[6] We note that Mendelson uses the notation ‘├S W1(k1, k2)’ to express the meta-statement : ‘‘The formula W1(k1, k2)’ is provable in S.’ [Mendelson 1964 : p143]

[7] [Mendelson 1964 : p143]

[8] Proof of proposition 3.31[Mendelson 1964 : p143]

[9] If we define ‘╟AW1(r, n)’ as the meta-statement ‘The relation W1(r, n) holds in the model (interpretation) A of S’, and interpret logical symbols similarly in the meta-theory M of S as in S, Mendelson’s meta-reasoning in this paragraph can be symbolically expressed as follows :

S (x2) ~ W1(m, x2)

M (Ek)╟All A W1(m, k)

M (Ek)├S W1(m, k)

and :

S (x2) ~ W1(m, x2)

MS ~ W1(m, k).

M (k)├S ~ W1(m, k).

[10]S is said to be ω-consistent if and only if, for every well formed formula A(x) of S, if ├S A(n) for every natural number n, i.e. (n)├S A(n),

then it is not the case that ├S (Ex) ~ A(x).’ [Mendelson 1964 : p142]

[11] See note 10 above.

[12] This meta-reasoning can be symbolically expressed as follows :

S ~ (x2) ~ W1(m, x2)

M S (Ex2) W1(m, x2)

M ~S (x2) ~ W1(m, x2)

M (n) ~All A W1(m, n)

M (n)╟All A ~W1(m, n)

M (n)├S ~ W1(m, n)

M ~S (Ex2) ~ ~W1(m, x2)

M ~S (Ex2) W1(m, x2).

[13] The reference here is to ‘Is Gödel’s Platonist creation through definition valid? and ‘Why did Gödel ignore this reasoning?’.

[14] This meta-reasoning can be symbolically expressed as follows :

S ~ W1(r, x2)

M (Ek)╟All A W1(r, k)

M (Ek)├S W1(r, k)

and :

S ~ W1(r, x2)

M (Ek)├S ~ W1(r, k).

[15] This can be expressed symbolically in the meta-theory M of S as ~ (n)├S ~W1(r, n).

[16] We can express this implication by :

‘W1(u, y) is primitive recursive’ →M [(n)╟All A ~W1(r, n) →M (n)├S ~W1(r, n)]

[17] This meta-reasoning too becomes clearer if we express the preceding argument as :

~S ~W1(r, x)

M ~(n)├S ~W1(r, n)

M ~(n)╟ All A ~W1(r, n)

M (El)╟ All A W1(r, l)

MS ~W1(r, x)

[18] [Mendelson 1964 : p134]

[19] [Mendelson 1964 : p118]

[20] [Mendelson 1964 : p131 Proposition 3.21]

[21] [Mendelson 1964 : p134]

[22] Both Gödel’s Theorem V and Mendelson’s Proposition 3.23 implicitly assert, and critically depend on, the postulated existence by definition of formal expressions in S (i.e. functions expressible in terms of only the primitive symbols of S) that are equivalent to the primitive recursive functions of S (i.e. primitive recursive functions whose values are always expressible in terms of only the primitive symbols of S) involved in the two hypotheses.

Such postulated existence by definition is strongly reminiscent of the Platonist postulation and creation by definition of a paradoxical set ‘Russell’ within a Set Theory whose elements are all, and only, those sets of the Theory that do not belong to themselves; or the similar postulation and creation by definition of a paradoxical ‘Liar’ sentence within the English language which reads as ‘The ‘Liar’ sentence is a lie’.

Index       Title       Preface       Contents       Section 1       Section 2

Section 3       Section 4       References       Roots       Bibliography       Web_links

Beyond Gödel (2001)

 (Updated : 10/11/01 1:57:50 AM by re@alixcomsi.com)