Contents

Index

Section 2

 

Section 1 : Is Gödel’s Platonist creation through definition valid?

B. S. Anand

Gödel argues that every recursive function can be expressed in his formal system of Arithmetic S in terms of the primitive symbols of S. We argue, however, that the recursive function ‘x+y’ cannot be expressed formally in terms of the primitive symbols of S.

1 Gödel’s Theorem V

In Theorem V[1] of his seminal 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’, Gödel proposes the hypothesis - and supports it with an argument by induction - that :

a) every n-ary arithmetical recursive[2] relation is constructively[3] expressible as a formula[4] of his formal system[5] S in an intuitionistically unobjectionable way[6];

b) every n-ary arithmetical recursive relation can be constructively associated with a unique Gödel-number[7] in an intuitionistically unobjectionable way.[8]

2 Gödel’s reasoning in Theorem V

(a) In his proof of the above theorem, Gödel considers ‘… all relations R(x1,, xn) of the form x1 = φ(x2,, xn) where φ is a recursive function.[9]

(b) Gödel’s argument is that if we apply complete induction on the rank of φ, then ‘… the theorem is trivial for functions of rank one (i.e. constants and the functionx + 1’)’.[10]

(c) Further, assuming φ to have the rank m,[11] Gödel notes that ‘… φ results from functions of lower rank φ1, φ2, … φk by the formal operations of substitution or recursive definition’.[12]

(d) Gödel then argues that ‘… since, by inductive hypothesis, everything is already proved for φ1, φ2, … φk, there exist corresponding PREDICATES[13] r1, r2,rk for which …’ §1(a) and §1(b) hold.[14]

(e) He notes that ‘… the definitional procedures by which φ arises[15] from φ1, φ2, … φk (substitution and recursive definition) can both be formally imitated in the system …’ S.[16]

(f) He concludes that one must therefore obtain ‘… from r1, r2,rk a new PREDICATE r for which one can prove[17] without difficulty the validity of …’ §1(a) and §1(b) by using the inductive hypothesis.

3 Applying Gödel’s reasoning to x+y

(a) We now apply Gödel’s reasoning to the recursive relation R(x, y) of the form ‘x1 = sum(x, y)’ where sum(x, y) x+y is the recursive function of rank two defined by sum(x, 0) x; sum(x, y+1) ≡ sum(x, y)+1’.

(b) We note that the definition of sum(x, y) can be formally imitated[18] in the formal system S by ‘sum(x, 0) x; sum(x, Ny) ≡ Nsum(x, y)’, where ‘Nx’ is the successor function[19] of rank one in S.

(c) Now Gödel’s thesis is that a formal expression consisting of only the primitive symbols of S and corresponding to the formal recursive function ‘sum(x, y)’, of rank two, can be constructively built up from the formal expression ‘Nx’, of rank one, by the formal operations of substitution or recursive definition.[20]

(d) Gödel’s conclusion then is that, from the Gödel-number r1=22.316 of ‘Nx[21], one can obtain a unique Gödel-number r for which §1(a) and §1(b) can easily be shown to hold, where r is defined by the purely formal structure of the formal expression corresponding to ‘sum(x, y)’.

4 ‘sum(x, y)’ cannot be directly expressed in S

We define N [y]0 y so that, for example, N [3]0 NNN0 and ‘sum(x, N [y]0)’ denotes the formal function ‘sum(x, y)’. If we now try to express sum(x, y) as a formula of S in terms of only the primitive symbols of S, we see that :

sum(x, y)sum(x, N [y]0) Nsum(x, N [y-1]0)N [y]x

For any given k, sum(x, k) is clearly expressible formally in terms of only the primitive symbols ‘N’ and ‘x’ of S. Also, for a given k, the unique Gödel-number rk of the formal expression corresponding to sum(x, k) is rk = 22. 32. 52. 72. 112. … pk2. pk+116, where pi is the i’th prime[22].

However, for a variable y, we cannot obviously express sum(x, y) - or the equivalent N[y]x - in terms of only the primitive symbols of S[23]. Similarly, for a variable y, ry too cannot be obviously enumerated so as to yield a unique Gödel-number r of a formal expression in S that corresponds to the definition §3(b).

5 Platonist creation through definition

Hence a formal expression consisting of only the primitive symbols of S and corresponding to the recursive function ‘sum(x, y)’, i.e. ‘x+y’, cannot be constructively built up[24] from the recursive formal function ‘Nx’ by ‘imitating’ the formal operations of substitution or recursive definition within S.[25]

Thus Gödel’s thesis in §3(c) and his conclusion[26] in §3(d) assert, and critically depend on, the indirect existence through definition of a formal expression in terms of only the primitive symbols of S that is formally equivalent to the formal recursive function ‘sum(x, y)’ defined in §3(b) above.

Such existence through 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’.

Despite the absence of a rigorous proof in his paper in support of his postulation by definition Gödel, reportedly a ‘…very strong Platonist.’[27], was apparently comfortable that this lacuna in his reasoning[28] would not yield an inconsistency.

6 Formal Number Theory

Although formal number theory, such as developed in Mendelson[29], attempts a justification for Gödel’s reasoning by using the stratagem of a ‘Gödel β-function’, this only permits sequences of determinate, if undetermined, length to be represented by formulas of a formal system S' where addition is an undefined primitive symbol.

Despite Mendelson’s claim - also without a rigorous proof[30] - the Gödel β-function cannot, however, be used to validly construct a formula strongly[31] representing a primitive recursive function, which is essentially an infinite sequence of indeterminate length.

Moreover, in companion papers[32], we show how inconsistencies can arise in both Gödel’s and Mendelson’s formal systems out of the postulation that every primitive recursive function can be strongly represented in their systems.

Notes (Why01et.doc : 4/3/01 5:23:36 PM)

 

 



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



[1] ‘For every recursive relation R(x1,, xn) there is an n-ary PREDICATE r (with the FREE VARIABLES u1,, un) such that, for all n-tuples of numbers (x1,, xn), we have :

R(x1,, xn) ® Bew [Sb ( r : ( (u1, z(x1)), … , (un, z(xn)) ) )]

~ R(x1,, xn) ® Bew [Neg Sb ( r : ( (u1, z(x1)), … , (un, z(xn)) ) )]’. [Gödel 1931 : p22]

We note the implicit implication here that r is a specific natural number - the Gödel-number of an implicitly postulated formal expression corresponding to the recursive formula R(x1,, xn).

[2] ‘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 ] ’. [Gödel 1931 : p14-15]

[3] i.e. by a finite procedure. [Gödel 1931 : p26 footnote 45a].

[4] Gödel 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. [Gödel 1931 : p11]

[5] Gödel develops the formal system S as ‘ … essentially the system which one obtains by building the logic of PM (Principia Mathematica) around Peano’s axioms (numbers as individuals, successor relation as undefined primitive concept).’ [Gödel 1931 : p10]

[6] i.e. without use of existence proofs such as arguments that depend, for example, on the use of the Law of the Excluded Middle. [Gödel 1931 : p26 footnote 45a]

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

[8] §1(a) and §1(b) are, essentially, Gödel’s Theorem V, which he notes as 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.’ [Gödel 1931 : p22]

[9] [Gödel 1931 : p22-23]

[10] Using the Gödel-numbering system as defined by Gödel in Davis 1965 : p53, we determine in the first case the formal expression in Gödel’s formal system S corresponding to say the recursive relation ‘x = 2’ is ‘x = NN0’, and its Gödel-number is r = 216. 33. 52. 72. 111; in the second the formal expression in Gödel’s formal system S corresponding to the recursive relation ‘x1 = x + 1’ is ‘x1 = Nx’, and its Gödel-number is r = 219. 33. 52. 716. In each case, the Gödel-number r is a specific natural number that is independent - i.e. it is not a function - of any specific values given to the concerned free variables such as x1 and x.

[11] We note that the premise in Gödel’s mathematical induction hypothesis is that ‘m’ and ‘k’ are not variables but determinate, even if undetermined, natural numbers.

[12] [Gödel 1931 : p15]

[13] i.e. Gödel-numbers.

[14] i.e. the recursive functions φ1, φ2, … φk can all be firstly constructively expressed as formulas of the formal system S in an intuitionistically unobjectionable way, and secondly constructively associated with unique Gödel-numbers r1, r2,, rk in an intuitionistically unobjectionable way.

[15] Gödel’s implicit belief in the constructibility of such a formula φ within S by such definition is reflected in his initial overview of his paper, where he notes that ‘… as soon as one has obtained the formula φ, one can, of course, also determine the number r, and thereby effectively write down the undecidable proposition itself.’ [Gödel 1931 : p8 footnote 13]

[16] We re-emphasise here that this ‘imitation’ holds only for determinate, if undetermined, ‘m’ and ‘k’. Further, that the aim of Gödel’s reasoning in his Theorem V is to eventually establish that the ‘imitation’ in the formal system S of the above procedure also holds for an indeterminate - i.e. free variable - ‘x’.

[17] We note that Gödel here assumes the constructibility of such a Gödel-number r without proof. Thus he remarks that ‘… when this proof is rigorously carried out, r will naturally not be defined by this shortcut through the intuitive interpretation, but rather by its purely formal structure.’ [Gödel 1931 : p22 footnotes 38 and 41]

[18] [Gödel 1931 : p23]

[19] [Davis 1965 : p46]

[20] [Gödel 1931 : p15]

[21] We use the Gödel-numbering system as defined by Gödel in Davis 1965 : p53.

[22] [Davis 1965 : p53]

[23] What we have shown here is that although §3(b) does define a formal recursive function ‘sum(x, y)’ of S, this function cannot be expressed as a formal expression in S in terms of only the primitive symbols of S.

[24] Dr. Chetan Mehta first pointed this out to the author in private correspondence. We also show elsewhere that every recursive relation is not expressible formally in a simply consistent formal system. [Anand 2000 : chapters 2, 3 & 5]

[25] Thus, though the function ‘Nx’ is a formal expression of S and easily Gödel-numbered, a recursive definition of the form of the function ‘sum(x, Ny)’ is essentially self-referential. Clearly, the form of ‘sum(x, Ny)’ - as represented by some formal expression of S and distinct from its recursively defined formal value - is Gödel-numberable if and only if the form of the function ‘sum(x, y)’ - as represented by some formal expression of S - is Gödel-numberable.

[26] That Gödel had reservations about the validity of his argument and conclusion is reflected in his subsequent lectures, where he notes that ‘ … this proof is not necessary for the demonstration of the existence of undecidable arithmetic propositions in the system considered. For, if some recursive function were not ‘represented’ by the corresponding formula constructed on pages 58-59, this would trivially imply the existence of undecidable propositions unless some wrong proposition on integers were demonstrable’. [Davis 1965 : p59 footnote 21]

[27] [Penrose 1990 : p147]

[28] Perhaps since he depended on Whitehead and Russell’s ‘… theory of types as our means for avoiding paradox.’. [Davis 1965 : p46]

[29] [Mendelson 1964 : chapter 3, p102]

[30] [Mendelson 1964 : p134]

[31] [Mendelson 1964 : p118]

[32]Why did Gödel ignore this reasoning?’ and ‘Is Mendelson’s use of the Gödel β-function valid?’.

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)