Chapter 2 : Every primitive recursive relation
is not expressible formally
2-01 Introduction
In his 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related Systems I’, Gödel’s primary aim is to :
(a) define a formal system S of Arithmetic rigorously [Gödel 1931 : p9-13] ;
(b) establish a method of Gödel-numbering the primitive symbols ‘0’, ‘v’, ‘(’, ‘f’, ‘Õ’, ‘)’, ‘~’, ‘x1, y1, z1, …’, ‘x2, y2, z2, …’, ‘x3, y3, z3, …’, … [Gödel 1931 : p10] of S by which various intuitive meta-mathematical concepts of, and meta-statements about, S can be formally represented by formulas within S in terms of (only) the undefined primitive symbols of S [Gödel 1931 : p13-14];
(c) define primitive recursive functions and relations [Gödel 1931 : p14-17] ;
(d) formally define and express selected functions and relations as purely arithmetical primitive recursive functions and relations in terms of (only) the undefined primitive symbols of S [Gödel 1931 : p17-22 definitions 1-45 and p29].
In his Theorem V Gödel then argues that every n-ary arithmetical primitive recursive relation in Peano’s Arithmetic A, taken to be the standard model for S, is expressible as a formula of S, and concludes that every such representation can be Gödel-numbered to yield a unique n-ary PREDICATE that is PROVABLE in S under suitable substitutions [Gödel 1931 : p22-23] :
Theorem V : For every primitive 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))))]
In Theorem VI [Gödel 1931 : p24-26], Gödel considers the specific primitive recursive relation :
Q(x, y) º ~ [xB[Sb(y :
(19, z(y)))]]
of A and - concluding by Theorem V that this is expressible as a formula Q(x, y) of S which is Gödel-numbered by a PREDICATE q that is a FUNCTION of the two FREE VARIABLES 17 and 19, but independent of the free variables x and y - shows that Q(x, y) yields an UNDECIDABLE SENTENCE 17Genr in S such that both 17Genr and Neg(17Genr) are not PROVABLE in an w-consistent S :
Theorem VI : For every w-consistent primitive recursive class k of FORMULAS, there exists a primitive recursive CLASS EXPRESSION r such that neither vGenr nor Neg(vGenr) belongs to Flg(k) (where v is the FREE VARIABLE of r).
2-02 The fallacy in Gödel’s reasoning
However, we argue that Gödel’s reasoning, as also that of others such as Herbrand [cf. Davis 1965 : p60 footnote 22] and Mendelson [1964 : p143] who have based similar results of UNDECIDABILITY on his seminal work on the formal expressibility of primitive recursive functions and relations within S, rests on an invalid argument.
Thus, in Theorem V, we hold that Gödel mistakenly concludes that every n-ary arithmetical primitive recursive relation of A is constructively expressible in terms of (only) the undefined primitive symbols ‘0’, ‘v’, ‘(’, ‘f’, ‘Õ’, ‘)’, ‘~’, ‘x1, y1, z1, …’, ‘x2, y2, z2, …’, ‘x3, y3, z3, …’, … of S.
We further hold that in the proof of his Theorem VI on the UNDECIDABILITY of SENTENCES in any formal system S of Arithmetic, Gödel invalidly assumes that the primitive recursive relation Q(x, y) of A is constructively expressible as a formula of S.
2-03 The primitive recursive function ‘Sb(y : (v, x) )’
Now, Sb(y : (v, x) ) is the primitive recursive function defined in A by [Gödel 1931 : p20 definitions 30-31] :
(a) Sb(y : (v, x)) = SbA(v, y)(y : (v, x))
(b) Sb0(y : (v, x)) = y
Sbk+1(y : (v, x)) = Su[Sbk(y : (v, x)) : ((kSt (v, y), x)]
where :
(i) A(v, y) is the primitive recursive function of A that yields the number of places at which the VARIABLE v is FREE in y [Gödel 1931 : p20 definition 29] ;
(ii) Su(y : (v, x)) is the primitive recursive function of A that yields the function arising from y by substituting x in place of the vth term of y [Gödel 1931 : p20 definition 27] ;
(iii) kSt(v, y) is the primitive recursive function of A defined by recursion, that yields value of the (k+1)st place in y at which v is FREE in y [Gödel 1931 : p20 definition 28].
Clearly, from the recursive nature of the particular functions in definition §2-03(b) above, it follows that the purely arithmetical function Sbk(y : (v, x)) of A cannot be expressed in terms of (only) the undefined primitive symbols ‘0’, ‘v’, ‘(’, ‘f’, ‘Õ’, ‘)’, ‘~’, ‘x1, y1, z1, …’, ‘x2, y2, z2, …’, ‘x3, y3, z3, …’, … of S for an indeterminate (free variable) k.
Hence, Sb(y : (v, x)) too can only be expressed in terms of (only) the undefined primitive symbols of S for a determined value of A(v, y), and it cannot be so expressed - and Gödel-numbered - for an indeterminate (free variable) y (and so an indeterminate value of A(v, y)).
2-04 The primitive recursive function ‘xB(y)’
Similarly, the arithmetical relation ~ [xB(y)] of A cannot be expressed in terms of (only) the undefined primitive symbols of S and Gödel-numbered for an indeterminate (free variable) x, as it too is defined by primitive recursive relations and functions such as :
(a) xB(y) º Bw(x) & [((L(x))Gl(x)) = y]
(b) L(x)
= (ew)[(w £ x) & (wPr(x) >
0) & ((w+1)Pr(x) = 0)]
(c) 0Pr(x)
= 0
(w+1)Pr(x)
= (ev)[(v £ x) & Prim(v) & x/v &
(v >
wPr(x))]
where :
(i) xB(y) is the primitive recursive relation of A that holds if and only if x is a PROOF of the FORMULA y [Gödel 1931 : p22 definition 45];
(ii) L(x) is the primitive recursive function of A that yields the length of the sequence of numbers correlated with x [Gödel 1931 : p18 definition 7] ;
(iii) (w+1)Pr(x) is the primitive recursive function of A that yields the wth prime factor of x (according to magnitude) [Gödel 1931 : p18 definition 3], which clearly cannot be expressed in terms of (only) the undefined primitive symbols of S, and Gödel-numbered, for an indeterminate (variable) x, and hence an indeterminate (variable) w.
We conclude that the primitive recursive relation Q(x, y ) of A, defined by :
Q(x, y ) º ~ [xB[Sb(y : (19, z(y)))]],
is not obviously expressible as a formula Q(x, y) of S.
2-05 The primitive recursive function ‘Pr(n)’
We note, incidentally, that if the primitive recursive function Pr(n) of A, defined by :
(a) Prim(z) º ~ ($x)[(x £ z) & (x ¹ 1) & (z ¹ x) & ( z/x) & (z >1)]
(z is a prime number [Gödel 1931 : p17 definition 2].)
(b) Pr(0) = 0
Pr(n+1)
= (ez)[(z £ ((Pr (n))!+1)) & Prim(z) & (z > Pr(n))]
(Pr(n) is the nth prime number in magnitude [Gödel 1931 : p18 definition 5].)
is expressible as a formula of S
which can be Gödel-numbered for an undetermined (free variable) n so as to yield a
specific CLASS EXPRESSION p in S
that is a FUNCTION of one FREE VARIABLE, say 17, then ‘decomposing’ p into (only) the primitive undefined symbols of
S
would yield the long-sought-for
arithmetical formula for the nth prime!
2-06 Can Gödel’s reasoning be salvaged?
We next address the question of whether Gödel’s reasoning in Theorem VI can be salvaged.
An obvious way is to extend [eg. Gödel 1931 : p20 definition 31 and footnote 36] the definitions of Sb(y : (v, x)), and other similarly defined functions such as z(y), naturally so that they can be expressed in terms of (only) the undefined primitive symbols S when any of y, x is an indeterminate free variable.
Thus we may, for example, define, in A :
(a) Sb(y :
(v, x))
= y ;
(b) Sb(x :
(v, y))
= x ;
(c) z(y) = y ;
in case y is a free variable, and we consider the consequences of such extended definitions in the next chapter.
2-07 Conclusions
Meanwhile, we conclude that Gödel has not unequivocally established, in his Theorem V [Gödel 1931 : p22], that every primitive recursive relation and function is constructively both expressible formally, and decidable, in the formal systems considered by him.
◄ Index ◄ Title ◄ Copyright ◄ Dedication ◄ Preface ◄ Contents ◄ Chapter
1 ▲ Chapter 2
Chapter 3
► Chapter
4 ► Chapter 5
► References
► Roots
► Bibliography ► Web_links
►
◄ Questioning Gödel’s
Theorems (Dec 2000) ◄ Beyond Gödel
(Oct 2001)
(Updated : 10/18/01 9:48:48 AM by re@alixcomsi.com)