Section 1

Index

Section 3

 

Section 2 : Why did Gdel ignore this reasoning?

B. S. Anand

In his Theorem VI, Gdel ignores the natural translation of the Liar paradox into a recursive relation, and overlooks a simple proof invalidating his reasoning in Theorem V that every recursive relation is expressible in S.

1 Gdels Theorem VI

In his seminal 1931 paper On Formally Undecidable Propositions of Principia Mathematica and Related SystemsI, Gdel rigorously defines a formal system[1] S and, in Theorem VI[2], considers a recursive[3] arithmetical relation Q(x, y)[4], which translates equivalently[5] as :

The formula[6] (sequence) X, whose Gdel-number[7] is x, is not a proof-sequence[8] in S of the formula (n-ary predicate[9]) obtained from the formula (n-ary predicate) Y, whose Gdel-number is y, when we substitute the numeral z(y)[10] for the formula (free variable) whose Gdel-number is 19[11] in the formula (n-ary predicate) Y whose Gdel-number is y.[12]

2 Gdels Theorem V

Earlier, in his Theorem V, Gdels thesis is that every recursive relation (and function) F can be formally represented in, and defined[13] as, a formula F[14] of the formal system S[15], and so uniquely Gdel-numbered by some constructible integer f, which latter, in turn, is representable in S as the numeral z(f)[16].

Accordingly, the above recursive relation Q(x, y) in Theorem VI can also be defined as a formula (binary predicate) Q(x, y) of S, which has a unique Gdel-number q.

3 The formula (R, r)

Now, for any recursive formula (n-ary predicate) F of say n free variables, either F or ~F is always provable on the basis of the axioms of the system S[17] for any given n-tuples of numbers for the n variables contained in F.[18]

Hence the recursive formula (class expression) R(x) - obtained by substituting the numeral z(q) for y in Q(x, y) - also has some unique Gdel-number r, is decidable[19] in S for every formula (X, x)[20], and translates as :

The formula (sequence) (X, x) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(q) for the formula (numerical variable) whose Gdel-number is 19 in the formula (binary predicate) (Q, q).[21]

4 (R, r) is not provable in S

Suppose, now, that the formula (sequence) (N, n) is a proof-sequence in S of the recursive formula (class expression) (R, r).[22]

The formula (R, r) is then provable in S for every formula (sequence) (X, x) [23].

In particular, for the formula (sequence) (N, n), we have that :

The formula (sequence) (N, n) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(q) for the formula (numerical variable) whose Gdel-number is 19[24] in the formula (binary predicate) (Q, q).[25]

However, the recursive formula (class expression) (R, r) is by definition also the formula (class expression) in S obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(q) for the formula (numerical variable) whose Gdel-number is 19 in the formula (binary predicate) (Q, q).[26]

The contradiction[27] establishes that there is no formula (sequence) (N, n) which is a proof-sequence in S of the recursive formula (class expression) (R, r).

5 (R, r) is provable in S

However, we then have that the recursive formula (class expression) (R, r) holds by definition in S for every formula (X, x)[28].

Further, since the formula (class expression) (R, r) is recursive, it then follows that the formula (class expression) (R, r) is provable in S for every formula (X, x), and so the recursive formula (class expression) (R, r) is provable in S[29].

So some formula (sequence) (N, n) can be constructed which is a proof-sequence in S of the formula (class expression) (R, r).

6 Gdels Theorem V is invalid

We thus have that :

The formula (class expression) (R, r) is provable in S The formula (class expression) (R, r) is not provable in S, and

The formula (class expression) (R, r) is not provable in S The formula (class expression) (R, r) is provable in S.

The contradiction[30] establishes that the formula (binary predicate) Q(x, y) in Theorem VI cannot be defined in S, and so it cannot be associated with a unique Gdel-number q.

Gdels thesis in his Theorem V, that every recursive formula F can be formally defined as some formula (n-ary predicate) F of his formal system S, and that the latter is uniquely Gdel-numberable by some integer f, is thus invalid.

7 Gdels formula (G, g)

Now we note that Gdel ignores the above straightforward reasoning which closely parallels the Liar paradox[31] in the formal system S.

Instead, in his Theorem VI (where he establishes his undecidable sentence in S as below) he applies closure to the recursive formula (binary predicate) (Q, q) and defines the (not necessarily recursive) formula (class expression) (P, p)[32], which translates as :

For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (n-ary predicate) obtained from the formula (n-ary predicate) (Y, y) when we substitute the numeral z(y) for the formula (numerical variable) whose Gdel-number is 19 in the formula (n-ary predicate) (Y, y).[33]

He then defines the recursive formula (phrase) (R', r')[34], which translates as :

The formula (class expression) obtained from the formula (binary predicate) Q, whose Gdel-number is q, when we substitute the numeral z(p) for the formula (numerical variable) whose Gdel-number is 19 in the formula (binary predicate) Q whose Gdel-number is q.

Gdel finally considers the provability in S of the formula (sentence) G, whose Gdel-number g is easily constructed from r'[35], which translates as :

For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(p) for the formula (numerical variable) whose Gdel-number is 19 in the formula (binary predicate) (Q, q).[36]

This is equivalent to the formula (sentence) that translates as :

For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (sentence) (G, g).[37]

8 Gdela proof : (G, g) is not provable in S

Gdel then concludes that the formula (sentence) (G, g) is not provable in S for, if some formula (sequence) (N, n) is a proof sequence of the formula (sentence) (G, g) in S, then it would also follow from the provability of the formula (sentence) (G, g) in S that :

For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(p) for the formula (numerical variable) whose Gdel-number is 19 in the formula (binary predicate) (Q, q).

In particular, this would then yield the contradiction :

The formula (sequence) (N, n) is not a proof-sequence in S of the formula (sentence) (G, g).

9 Gdels proof : (~G, g') is not provable in S

Gdel next considers and concludes that the formula (sentence) ~G, whose Gdel-number we denote by g'[38], is also not provable in S for, if the formula (sentence) (~G, g') were provable in S, then the formula (sentence) (G, g) too would be provable in S as it would follow from the provability of the formula (sentence) (~G, g') that :

For some formula (sequence) (X, x), the formula (X, x) is a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(p) for the formula (numerical variable) whose Gdel-number is 19 in the formula (binary predicate) (Q, q).

This is equivalent to, and yields, the contradiction :

Some formula (sequence) (N, n) is a proof-sequence in S of the formula (sentence) (G, g).

10 In conclusion?

In conclusion, we raise the intriguing questions :

a) Why did Gdel ignore the straightforward, natural translation of the Liar paradox into the formal system S as outlined in 1 - 3?

b) How did Gdel overlook the simple proof invalidating his Theorem V as outlined in 4 - 6?

c) What areas of mathematics and logic are affected if every recursive function is not expressible formally in terms of the primitive symbols of the formal system S?

Notes (Why02ct.doc : 4/7/01 3:22:26 AM)

 

 



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



[1] Gdel develops in great detail the formal system S that he intends to consider, noting that this is essentially the system which one obtains by building the logic of PM (Principia Mathematica) around Peanos axioms (numbers as individuals, successor relation as undefined primitive concept). [Gdel 1931: p9-13]

[2] For every w-consistent recursive class k of FORMULAS, there exists a recursive CLASS EXPRESSION r such that neither vGenr nor Neg(vGenr) belongs to Flg(k) (where v is the FREE VARIABLE of r). [Gdel 1931: p24]

[3] A number-theoretic function φ is said to be recursive if there exists a finite sequence of number-theoretic functions φ1, φ2, φn which ends with φ and has the property that each function φk of the sequence either is defined recursively from two of the preceding functions, or results from one of the preceding functions by substitution, or, finally, is a constant or the successor function x + 1. The length of the shortest sequence of φi's belonging to a recursive function φ is called its rank. A relation between natural numbers R(x1, x2, , xn) is called recursive if there exists a recursive function φ(x1, x2, , xn) such that, for all x1, x2, , xn, R(x1, x2, , xn) [φ(x1, x2, , xn) = 0 ]. [Gdel 1931 : p14-15]

[4] Where the context is unambiguous, we shall refer to relations (functions) such as Q(x, y) as Q, and formulas such as Q(x, y) as Q.

[5] i.e. the translation holds if and only if the recursive arithmetical relation Q(x, y) holds.

[6] Gdel defines the primitive symbols of S as consisting of various constants and variables; combinations of certain symbols as terms; and combinations of certain symbols and terms as the various types of formulas of S. [Gdel 1931: p11]

For convenience of exposition in translations, we sometimes use the word formula to also refer to any formal expression consisting of a finite sequence of the primitive symbols of S, or - as here - to a finite sequence of formal expressions.

[7] Gdel describes in detail how every primitive symbol of S, every formal expression consisting of a finite sequence of such symbols of S, and every sequence of formal expressions can be arithmetised and correlated uniquely to some natural number - which we define as the Gdel-number of the formal expression in question. [Gdel 1931: p10-11 & p13-14]

[8] Gdel defines a proof sequence as a finite sequence of formulas such that each is either an axiom of S, or a formula that is an immediate consequence of the axioms of S and some of the preceding formulas in the sequence by the formal rules of inference of S. [Gdel 1931: p14 & p22 definition44]

[9] A sentence is a formula in which no free variables occur (free variables being defined in the usual way). A formula with exactly n free variables (and otherwise no free variables) is called an n-ary predicate, for n = 1 also a class expression. [Gdel 1931: p11]

[10] z(y) is recursively defined to be the formal representation of the integer y in S [Gdel 1931: p19 definition 17]

[11] In Gdels particular arithmetisation in the cited paper, each variable in a formula can be arbitrarily, but uniquely, correlated to some prime number > 13. [Gdel 1931: p13]

[12] The equivalent recursive arithmetical relation Q(x, y) is a relation between only the various Gdel-numbers occurring in the translation, and is expressed in Gdels terminology by ~ [ x B [ Sb ( y : (19, z(y)) ) ] ]. [Gdel 1931: p14 & p17-22]

In Gdels terminology, the recursive arithmetical Q(x, y) relation actually translates as The FORMULA x is not a PROOF SEQUENCE of the FORMULA obtained from the FORMULA y when we substitute the NUMERAL z(y) for the VARIABLE 19 in the FORMULA y. [Gdel 1931: p13-14]

[13] i.e. expressed equivalently using only the primitive symbols of the formal system S.

[14] We use bold italic letters to denote the formulas such as F of the formal system S that correspond equivalently to the arithmetical formulas such as F.

[15] Gdel notes that his Theorem V is the rigorous expression of the fact which can be vaguely formulated as the assertion that every recursive relation is definable within the system S (under its intuitive interpretation) without reference to the intuitive meaning of the formulas of S. [Gdel 1931: p22]

[16] [Gdel 1931: p19 definition 17]

[17] i.e. there is some proof sequence in S such that either F or ~F is the last formula in the sequence.

[18] Gdel notes this as the fact that, for a recursive relation F, it is decidable (provable) on the basis of the axioms of the system S whether or not F holds for any given n-tuple of numbers. [Gdel 1931: p23 footnote 39]

[19] i.e. either R(x) or ~R(x) is provable.

[20] From here on we use the notation (X, x) to denote the phrase X, whose Gdel-number is x.

[21] The formula (class expression) R(x) is the formal representation of the recursive arithmetical relation R(x) between the various Gdel-numbers occurring in the translation, the relation itself being expressed in Gdels terminology by ~ [ x B [ Sb ( q : (19, z(q)) ) ] ]. [Gdel 1931: p14 & p17-22]

[22] In Gdels terminology, this supposition is equivalently expressed by n B r. [Gdel 1931: p14 & p22 definition 45]

[23] This inference, and its converse, follow from a particular case where we explicitly express Gdels implicit requirement (necessary for the hypothesis postulated by him in his Theorem V) that recursive relations (and functions) be meaningfully definable within S in a constructive and intuitionistically unobjectionable manner. In this case we meet such a requirement by explicitly postulating, in the meta-theory M of S, Gdels Implicit Intuitionist Meta-thesis that a recursive formula be provable in S if and only if it is provable in S for all non-negative integer values of the variables contained in it. In this instance, if we denote the meta-statement R(x) is a provable formula of S by ├S R(x), it would mean that :

S R(x) M (n)├S R(n).

Such a thesis ensures that the provability of a recursive formula of S is always determined by its provability in a denumerable sub-domain of S. We conjecture that it is the absence of such specification that permits the surreptitious entry of arguably ill-defined, Platonistic, elements into S, such as those leading to a paradox, since the domain of x need not be denumerable under interpretation.

Also, the representations in S of some, if not all, of Gdels 46 definitions [Gdel 1931: p17-221] - such as those of, for instance, x/y of divisibility, Prim(x) of primality and Bew(x)of provability (equivalent to that of the notationS) - cannot be assumed to be well-defined over an extended, transfinite, range, since these are defined [Gdel 1931: p14] only through an interpretation over the non-negative integers. Thus we may reasonably conclude that Gdels definitions and reasoning are valid, and significant, only in those interpretations of his formal system S that are denumerable domains, and where some specification such as Gdels Implicit Intuitionist Meta-thesis holds.

[24] We note that the formula (numerical variable) whose Gdel-number is 19 in the formula (n-ary predicate) (Q, q) is y.

[25] This sentence is the translation of, and equivalent to, the arithmetical relation between the Gdel-numbers of the various components contained in it, expressed in Gdels terminology [Gdel 1931: p14 & p17-22] by ~ [ n B [ Sb ( q : (19, z(q)) ) ] ].

[26] In Gdels terminology, this fact is equivalently expressed by r = Sb ( q : (19, z(q)) ). [Gdel 1931: p24-25]

[27] In Gdels terminology, we have the contradiction n B r ~ ( n B r). [Gdel 1931: p24-26]

[28] If we define ╟A R(n) as the meta-statement The sentence R(n) holds in the model (interpretation) A of S, this meta-statement can be expressed as (n)╟All A R(n), where n ranges over the non-negative integers.

[29] Based on 23above, this meta-reasoning can be expressed (loosely) as :

R(x) is recursive →M [ (n)╟ All A R(n) M (n)├S R(n) →MS R(x) ].

[30] In Gdels terminology, we have (Bewr ~Bewr) & (~BewrBewr). [Gdel 1931: p22]

[31] The paradox that arises if we define the Liar sentence as The Liar sentence is a lie. [Davis 1965: p63-64]

[32] In Gdels terminology, this formula (class expression) P(y) is determined by defining its Gdel-number by p = 17Gen q. [Gdel 1931: p14 & p24-26]

[33] The formula (class expression) P(y) is the formal representation of the arithmetical relation between Gdel-numbers expressed in Gdels terminology by (x) [~ [ x B [ Sb ( y : (19, z(y)) ) ] ] ]. [Gdel 1931: p17-22]

[34] In Gdels terminology, this formula (phrase) R' is determined by defining its Gdel-number by r' = Sb ( q : (19, z(p)) ). [Gdel 1931: p14 & p24-26]

[35] In Gdels terminology g = 17Gen r'.

[36] The formula (sentence) G is the formal representation of the arithmetical relation between the various Gdel-numbers occurring in the translation, expressed in Gdels terminology by (x) [~ [ x B [ Sb ( q : (19, z(p)) ) ] ] ]. [Gdel 1931: p14 & p17-22]

[37] The justification for the legitimacy of this formula as a formula of S, and for its equivalence to the formula (sentence) G after appropriate substitutions, lies in Gdels assertion that, by his definitions and assuming the validity of his Theorem V, the formula G can be assumed to be constructively Gdel-numberable so as to yield a unique Gdel-number g in an intuitionistically unobjectionable way.

[38] In Gdels terminology g' = Neg g.

Index Title Preface Contents Section 1 Section 2

Section 3 Section 4 References Roots Bibliography Web_links

Beyond Gdel (2001)

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