Chapter 4

Index

References

Chapter 5 : The fallacy in Gödel’s proof of undecidability

5-01   Gödel’s Theorem V

In his Theorem V Gödel proposes the hypothesis - and supports it with an argument by induction - that :

a)   every n-ary arithmetical primitive recursive relation is expressible constructively as a formula of his formal system S in an intuitionistically unobjectionable way (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) ;

b)   every n-ary arithmetical primitive recursive relation can be Gödel-numbered - also constructively and in an intuitionistically unobjectionable way - 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 :

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

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

Now we note firstly that the PREDICATE r postulated by Gödel is a specific natural number, constructible in an intuitionistically unobjectionable way, that is defined as the unique Gödel-number of some formal expression (formula) RS(x1,, xn) which Gödel postulates as always corresponding in S to the intuitive primitive recursive relation R(x1,, xn)  [Gödel 1931 : p22 footnote 38].

We also note that r is a FUNCTION of arbitrarily prescribed FREE VARIABLES u1,, un, but independent (i.e. not a function) of the given free variables x1,, xn  [Gödel 1931 : p22 footnote 38].

This means that if (a1,, an), (b1,, bn), (c1,, cn), … are any set of valid values for (x1,, xn) then, by Gödel’s hypothesis, we have that :

R(a1,, an)  ®  Bew [Sb ( r : ( (u1, z(a1)), … , (un, z(an)) ) )]

~R(a1,, an)  ®  Bew [Neg Sb ( r : ( (u1, z(a1)), … , (un, z(an)) ) )]

R(b1,, bn)  ®  Bew [Sb ( r : ( (u1, z(b1)), … , (un, z(bn)) ) )]

~R(b1,, bn)  ®  Bew [Neg Sb ( r : ( (u1, z(b1)), … , (un, z(bn)) ) )]

R(c1,, cn)  ®  Bew [Sb ( r : ( (u1, z(c1)), … , (un, z(cn)) ) )]

~R(c1,, cn)  ®  Bew [Neg Sb ( r : ( (u1, z(c1)), … , (un, z(cn)) ) )]

For every primitive recursive relation R(x1,, xn), Gödel is thus postulating the existence of a unique PREDICATE r, and that of some function Sb ( r : ( (u1, z(x1)),…, (un, z(xn)) ) ) of r and the free variables x1, xn, both of which are constructible in an intuitionistically unobjectionable way and where the latter, for any given set of values (a1,, an), yields the corresponding Gödel-number Sb ( r : ( (u1, z(a1)), … , (un, z(an)) ) ) of the formal expression RS(a1,, an) corresponding in S to the intuitive primitive recursive relation R(a1,, an).

In §5-12(a) we note the consequences for Gödel’s reasoning if the PREDICATE r is also assumed similarly to be a function of the given  free variables  x1,, xn.

5-02   Gödel’s reasoning in Theorem V

(a)  Now, in his proof of the above theorem, Gödel considers ‘… all relations R(x1,, xn) of the form x1 = φ(x2,, xn) where φ is a primitive recursive function’ [Gödel 1931 : p22-23].

(b)  Applying complete induction on the rank of φ, Gödel notes that ‘… the theorem is trivial for functions of rank one (i.e. constants  and the functionx + 1’ )’.

(  Using the Gödel-numbering system defined by Gödel in Davis 1965 : p53 we can easily determine in the first case, for say the formal expression corresponding to the primitive recursive relationx = 2’, that r = 216. 33. 52. 72. 111 ; in the second, for the formal expression corresponding to the primitive recursive relation  x1 = x + 1’, that r = 219. 33. 52. 716 .

We note that, in each case, the PREDICATE r is a specific natural number which is independent - i.e. it is not a function - of the concerned free variables such as x1 and x.

We presume that what Gödel intends to convey here by trivial is that the PREDICATE Sb ( r : ( (u, z(x)) ) ) in the first case, and Sb ( r : ( (u, z(x)), (u1, z(x1)) ) ) in the second, are constructively DECIDABLE  in S for any given values of x, x1 by a mechanical, finite procedure in an intuitionistically unobjectionable way.)

(c)  Assuming φ to have the rank m, Gödel notes further that ‘… φ results from functions of lower rank φ1, φ2, … φk by the formal operations of substitution or recursive definition’ [Gödel 1931 : p10-17].      

(  We note the premise in Gödels mathematical induction hypothesis is that  m  and  k  are  given, but unspecified, natural numbers.)

(d)  Gödel then argues that ‘… since, by inductive hypothesis, everything is already proved for φ1, φ2,  φk, there exist corresponding PREDICATES r1, r2,, rk for which §5-01(i) and §5-01(ii) hold’.

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

(  We need to emphasise here that this imitation holds only for given, if unspecified,  m  and  k’.

Further, that the aim of Gödels reasoning in his Theorem V is to eventually establish that the imitation in the  formal system  S  of the above procedure also holds for undetermined - i.e. free variable - m  and  k’.)

(f)  He concludes that one must therefore obtain ‘… from  r1, r2,rk a new PREDICATE r for which one can prove without difficulty the validity of §5-01(i) and §5-01(ii) by using the inductive hypothesis’.

(  We note that Gödel here assumes the constructibility of such a PREDICATE 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 footnote 38].

We further note that by without difficulty Gödel presumably intends to convey the DECIDABILITY of the PREDICATE Sb ( r : ( (u1, z(x1)), … , (un, z(xn)))) in S as following constructively for each set of substitutions by a mechanical, finite procedure in an intuitionistically unobjectionable way.)

5-03   A Lemma

It then follows that :

Lemma :    For any primitive recursive relation R(x) of a single free variable x, there is always a CLASS EXPRESSION r (with the FREE VARIABLE u) such that, for all x, we have :

R(x)  ®  Bew [Sb ( r : ( (u, z(x)) ) )]

~R(x)  ®  Bew [Neg Sb ( r : ( (u, z(x)) ) ) )]

By Gödel’s hypothesis, the CLASS EXPRESSION r is here the unique Gödel-number of some formal expression RS(x) of S corresponding to the primitive recursive relation R(x) and is, by definition, of the form :

r = 2 w1. 3 w2. 5 w3. 7 w4. 11 w5. …  pl-1 wl -1. pl wl ,

where :

a)   l is a unique natural number - constructible in an intuitionistically unobjectionable way - that corresponds to the (necessarily finite) number of primitive symbols  needed to represent the primitive recursive relation R(x) as the formal expression RS(x) of S ;

(  It follows from the above that r can only be determined for a specific l’, and not for a free variable l’.)

b)   pl is the l’th prime ;

c)   each wi, for 1 i l, is some natural number that is the Gödel-number corresponded uniquely by definition to one of the primitive logical symbols of Gödel’s formal system S as follows (for convenience of exposition in these paragraphs, we use the Gödel-numbering system defined by Gödel in Davis 1965 : p53) :

‘0’ « 1;  N« 2;  =« 3;  ~« 4;  v« 5;  &« 6;  « 7;  « 8;  Õ« 9;  Σ« 10;  Є« 11;  (« 12;  )« 13;  x« 16 ;

d)   the CLASS EXPRESSION r - the Gödel-number of the formal expression RS(x) of S corresponding to the primitive recursive relation R(x) - necessarily contains one, and only one, FREE VARIABLE u which is, in this case, actually the Gödel-number 16 that is corresponded by definition to represent the free variable x of S ;

e)   wi = 16 for some values 1 i l (depending on the values at which the free variable x, represented (i.e. Gödel-numbered) by the FREE VARIABLE 16, occurs in the formal expression RS(x) of S corresponding to the primitive recursive relation R(x)) ;

f)    if wi ≠ 16, then wi is necessarily the Gödel-number of some one of the other primitive symbols ‘0’, ‘N’, ‘=’, ‘~’, ‘v’, ‘&’, ‘’, ‘’, ‘Õ’, ‘Σ’, ‘Є’, ‘(’, ‘)’, of S (or the Gödel-number of a BOUND VARIABLE that occurs in the formal expression RS(x) of S corresponding to the primitive recursive relation R(x)) i.e. wi then necessarily takes one of the values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12  or 13 (or a value that is the Gödel-number of a BOUND VARIABLE that occurs in the formal expression RS(x) of S corresponding to the primitive recursive relation R(x)).

Clearly we have that :

RS(x)  [w1][w2][w3][w4][w5] [wl-1][wl]

where [wi] represents the primitive symbol of S corresponding to the Gödel-number wi.

We also have that, by Gödel’s hypothesis :

R(0)  ®  Bew [Sb ( r : ( (u, z(0)) ) )]

~R(0)  ®  Bew [Neg Sb ( r : ( (u, z(0)) ) ) )]

R(1)  ®  Bew [Sb ( r : ( (u, z(1)) ) )]

~R(1)  ®  Bew [Neg Sb ( r : ( (u, z(1)) ) ) )]

R(2)  ®  Bew [Sb ( r : ( (u, z(2)) ) )]

~R(2)  ®  Bew [Neg Sb ( r : ( (u, z(2)) ) ) )]

R(3)  ®  Bew [Sb ( r : ( (u, z(3)) ) )]

~R(3)  ®  Bew [Neg Sb ( r : ( (u, z(3)) ) ) )]

5-04   Applying Gödel’s reasoning to x!

(a)  We now apply Gödel’s reasoning to the primitive recursive relation R(x) of the form ‘40320 = φ(x)’ where φ is the primitive recursive function defined by  φ(x) = x! [Gödel 1931 : p22-23].

(b)  Following Gödel, we use complete induction on the finite rank k of φ.

(c)  We note that φ results from a finite number of primitive recursive functions of lower rank φ0, φ1φk-1 by the formal operations of substitution or recursive definition [Gödel 1931 : p10-17; p18 definition 4].      

(d)  Gödel’s argument is that as everything is already proved for φ0, φ1, … φk-1  by inductive hypothesis for any given value k, there exist corresponding PREDICATES r0, r1,r k-1 for each of which §5-01(i) and §5-01(ii) hold.

5-05   The basis of Gödel’s induction

Now we note that the basis for any induction argument on r k is that, for any given value k:

R(0)  ®  Bew [Sb (r'0 : ( (u, z(0)) ) )]

~R(0)  ®  Bew [Neg Sb (r'0 : ( (u, z(0)) ) ) )]

R(1)  ®  Bew [Sb (r'1 : ( (u, z(1)) ) )]

~R(1)  ®  Bew [Neg Sb (r'1 : ( (u, z(1)) ) ) )]

R(2)  ®  Bew [Sb (r'2 : ( (u, z(2)) ) )]

~R(2)  ®  Bew [Neg Sb (r'2 : ( (u, z(2)) ) ) )]

R(3)  ®  Bew [Sb (r'3 : ( (u, z(3)) ) )]

~R(3)  ®  Bew [Neg Sb (r'3 : ( (u, z(3)) ) ) )]

R(k-1)  ®  Bew [Sb (r'k-1 : ( (u, z(k-1)) ) )]

~R(k-1)  ®  Bew [Neg Sb (r' k-1 : ( (u, z(k-1)) ) ) )]

where :

(a)  r'0 is the Gödel-number :

22. 32. 52. 72. 112. … p403202. p403211. p403223. p403232.  p403241

of the primitive recursive relation R(0) - defined as ‘40320 = 0!’ -  when this is expressed formally as :

N403200 = N0

(  denoted by RS(0)) using only the primitive symbols of the formal system S [Davis 1965 : p53]. For convenience of exposition, we use the notation N3to represent the formal expression NNN’.)

(b)  r'1 is the Gödel-number :

22. 32. 52. 72. 112. …  p403202. p403211. p403223. p403232.  p403241

of the primitive recursive relation R(1) - defined as ‘40320 = 1!’ -  when this is expressed formally as :

N403200 = N0

(  denoted by RS(1)) using only the primitive symbols of the formal system S [Davis 1965 : p53]. We note that R(0) and R(1) are indistinguishable when expressed formally. This raises the question of whether there are possible nuances in classical systems of Arithmetic that are not formalisable.)

(c)  r'2 is the Gödel-number :

22. 32. 52. 72. 112. …  p40320 2. p403211. p403223. p403232.  p403242. p403251 

of the primitive recursive relation R(2) - defined as ‘40320 = 2!’ -  when this is expressed formally as :

N403200 = NN0

(  denoted by RS(2)) using only the primitive symbols of the formal system S [Davis 1965 : p53].)

(d)  r'3 is the Gödel-number :

22. 32. 52. 72. 112. …  p40320 2. p403211. p403223. p403232.  p403242. p403252.  p403262. p403272.  p403282. p403291 

of the primitive recursive relation R(3) - defined as ‘40320 = 3!’ -  when this is expressed formally as :

N403200 = N60

 ( denoted by RS(3)) using only the primitive symbols of the formal system S [Davis 1965 : p53].)

(d)  r'k-1 similarly represents the Gödel-number of the formal expression RS(k-1) (corresponding to the primitive recursive relation R(k-1) defined as ‘40320 = (k-1)!’) for any given, if unspecified, value k.

5-06   x!  is not expressible constructively

So Gödel’s inductive reasoning, when applied to the primitive recursive function x!,  is essentially the following argument :

Since 1!, 2!, 3!, can all be expressed formally as FORMULAS of S by corresponding PREDICATES r'1, r'2, r'3, …, hence the primitive recursive function x! must also be expressible formally as a FORMULA of S by some corresponding PREDICATE r - necessarily of a single FREE VARIABLE such as 16 - that is constructible in an intuitionistically unobjectionable way and is independent (i.e. not a function) of x.

However the expressibility of the arithmetical functions 1!, 2!, 3!, … as FORMULAS of S arises from their formal expressibility as the formulas of S [Davis 1965 : p46] :

(N0), (NN0), (NNNNNN0), …,

which immediately yield the corresponding (Gödel-numbers) PREDICATES [Davis 1965 : p53] :

(r'1 = 22.3), (r'2 = 22. 32.5), (r'3 = 22. 32. 52. 72. 112. 132.17), …. ,

where the PREDICATE function corresponding to the primitive recursive function x! is the arithmetical function :

rx = 22. 32. 52. 72. 112. …  px! 2. px!+1.

Clearly, given such a PREDICATE function, we can easily recover the formal expression within S for the arithmetical primitive recursive functionx!’ for any given value of x constructively and in an intuitionistically unobjectionable way.

For an undetermined (free variable) x, however, we cannot recover (constructively and in an intuitionistically unobjectionable way) a corresponding formal expression (formula) for ‘x!within S from this PREDICATE function such that it consists of only the primitive undefined symbols of S - i.e. it does not yield a specific Gödel number for ‘x!’.

It follows that, for an undetermined (variable) x, Gödel has not established that the primitive recursive functionx!can be, constructively and in an intuitionistically unobjectionable way, reduced to a form that can be expressed as a formula of S in terms of only the primitive undefined symbols of S [Gödel 1931 : p13].

Hence the primitive recursive functionx!cannot be assumed to be Gödel-numberable constructively in an intuitionistically unobjectionable way for an undetermined (variable) x so as to yield a specific CLASS EXPRESSION r in S (with, for instance, the FREE VARIABLE 16) that is independent (i.e. not a function) of x.

5-07   Gödel’s reasoning is non-constructive

Gödel’s application of the principle of mathematical induction is thus based on a non-constructive argument.

5-08   The fallacy in Gödel’s reasoning

For the primitive recursive function x!Godel’s argument can be summarised as follows :

(a)  The formal expression (numeral) corresponding to the arithmetical constant '0!' can be constructively Godel-numbered ... TRUE.

(b)  If, for a given (natural number) value 'n' of x, the arithmetical function 'x!' can be formally expressed (as a numeral) in S and constructively Godel-numbered, then the arithmetical function '(n+1)!' can also be formally expressed (as a numeral) in S and constructively Godel-numbered ... TRUE.

From this Godel’s reasoning then invalidly concludes :

(c)  Hence, even for an undetermined, variablex’, the arithmetical function 'x!' can be formally expressed in S (not as a numeral!) and constructively Godel-numbered ... FALSE,

whereas the principle of mathematical induction only establishes that :

(d)  For every (any given) natural number 'n', the arithmetical function 'x!' can be formally expressed in S (as a numeral) and constructively Godel-numbered ... TRUE.

5-09   Applicability of Gödel’s Theorem V

We thus see that, whereas Gödel clearly believes Theorem V  applies to every primitive recursive relation, his proof only applies to those  primitive recursive relations  which can be constructively built up by a finite, mechanical procedure in an intuitionistically unobjectionable way from the specifically defined primitive symbols of his formal system S using the specific rules given by him for construction of the formulas of the formal system S.

5-10   Gödel’s Theorem VI

We now look at Theorem VI, where Gödel considers the specific primitive recursive relation [Gödel 1931 : p24-26] :

Q (x, y )   º   ~ [ x B [ Sb ( y : (19, z(y)) ) ] ]

and - concluding by Theorem V that Q (x, y ) can be constructively Gödel-numbered by a PREDICATE q that is a FUNCTION of the two FREE VARIABLES 17 and 19, but independent of the two free variables x and y - argues that this 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).

(  We note that the formal system used above by Gödel, and the correspondence between natural numbers and  free numerical variables for the purposes of Gödel-numbering, differs merely in minor detail from that used by Gödel in  Davis 1965.)

5-11   Gödel’s reasoning in Theorem VI

(a)  Now Gödel’s reasoning in Theorem VI follows from his hypothesis in Theorem V, allowing him to conclude that there is always a PREDICATE q (a specific natural number, constructible in an intuitionistically unobjectionable way, as the Gödel-number of the primitive recursive relation~ [ x B [ Sb ( y : (19, z(y)) ) ] ] and which is a FUNCTION of the two FREE VARIABLES 17 and 19) such that the relations :

~ [ x B [ Sb ( y : (19, z(y)) ) ] ]  ®  Bew [ Sb ( q : ((17, z(x)), (19, z(y))) ) ]

x B [ Sb ( y : (19, z(y)) ) ]  ®  Bew [ Neg Sb ( q : ((17, z(x)), (19, z(y))) ) ]

hold in S for all pairs of values (x, y).

(b)  He can thus validly define a specific natural number p as the CLASS EXPRESSION with the FREE VARIABLE 19 by :

p  =  17Genq,

and a specific natural number r as the primitive recursive CLASS EXPRESSION with the FREE VARIABLE 17 by :

r  =  Sb (q : (19, z(p)) ).

(c)  He reasons from these definitions that :

Sb (p : (19, z(p)) )  =  Sb ( (17Genq) : (19, z(p)) )

=  17Gen[ Sb (q : (19, z(p)) )]

=  17Genr

Sb ( q : ((17, z(x)), (19, z(p))) )  =  Sb (r : (17, z(x)) ).

(d)  Substituting the specific natural number p for y in Q(x, y), he uses Theorem V as above and various substitutions to conclude that the relations :

~ [ x B (17Genr)]  ®  Bew [ Sb ( r : (17, z(x)) )]

x B (17Genr)  ®  Bew [ Neg Sb ( r : (17, z(x)) )]

hold in S for all values of x.

(e)  From the above Gödel finally concludes, meta-mathematically, that 17Genr and Neg(17Genr) are not PROVABLE [Gödel 1931 : p25-26] in an w-consistent  S, and 17Genr is UNDECIDABLE in S.

5-12   The breakdown of Gödel’s proof

(a)  However, as shown above, Gödel’s reasoning in his Theorem V actually allows him to conclude only that there is a PREDICATE function qx,y such that the relations :

~ [ x B [ Sb ( y : (19, z(y)))]]  ®  Bew [ Sb (qx,y : ((17, z(x)), (19, z(y))))]

 [ x B [ Sb ( y : (19, z(y)) )]]  ®  Bew [ Neg Sb (qx,y : ((17, z(x)), (19, z(y))))]

hold in S for all pairs of values (x, y).

(  Gödels assertion here is that there always exists a natural number q independent of x and y, constructible in an intuitionistically unobjectionable way,  for which the above two relations hold for all pairs of values of x and y. )

(b)  If we then define the arithmetical function px,y by :

px,y  =  17Gen qx,y,

and the arithmetical function rx,y by :

rx,y  =  Sb (qx,y : (19, z(px,y)) ),

we have that, for all pairs of values (x, y) :

px,y  =  qx,y,

and :

rx,y  =  qx,y

since :

qx,y is a PREDICATE function that yields the Gödel-number of the primitive recursive function  ~ [ x B [ Sb ( y : (19, z(y)) ) ] ]  for any given x and y.

Thus, given any set of values such as x = a and y = b, the Gödel-number qa,b of the primitive recursive function ~[a B [ Sb ( b : (19, z(b)) )]] does not contain any FREE VARIABLE and so, treating  ~ [ a B [ Sb ( b : (19, z(b)) ) ] ] and (x)[~ [ a B [ Sb ( b : (19, z(b)) ) ] ] ] as essentially the same function, we have that :

17Gen qx,y  =  qx,y,

Sb (qx,y : (19, z(px,y)) )  =  qx,y,

for all pairs of values (x, y).

(c)  If we now substitute the variable px,y (=  qx,y) for y in Q (x, y ), by Theorem V we can only conclude that the relations :

~ [ x B [ Sb (qx,y : (19, z(qx,y)) ) ] ]  ®  Bew [ Sb (qx, qx,y : ((17, z(x)), (19, z(y))) ) ]

[ x B [ Sb (qx,y : (19, z(qx,y)) ) ] ]  ®  Bew [ Neg Sb (qx, qx,y : ((17, z(x)), (19, z(y))) ) ],

hold in S for all pairs of values (x, y).

(d)  However, the above reduce to the relations :

~ [ x B qx,y]  ®  Bew (qx, qx,y )

 [ x B qx,y]  ®  Bew [ Neg (qx, qx,y ) ],

which hold trivially in S for all pairs of values (x, y), and do not yield the consequences needed to establish the existence of an UNDECIDABLE SENTENCE as postulated by Gödel in the statement of his Theorem VI!

5-13   Conclusions

In his Theorem V, Gödel has not established that every n-ary arithmetical primitive recursive relation is constructively expressible as a valid formula of a formal system of Arithmetic such as the Principia Mathematica.

Gödel’s Theorem V is thus unproven, and his Theorem VI on the existence of formally UNDECIDABLE SENTENCES in such  formal systems, and its consequences, reduce to unproven hypotheses.

Gödel’s construction of his UNDECIDABLE SENTENCE ‘17Genr’ thus essentially highlights in a formal system the invalidity underlying Epimenides paradoxical remark ‘This sentence is a lie’.

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)