Chapter 4                                                                 Index                                                                 Chapter 6

Beyond Gödel

Simply consistent constructive systems of first order Peano’s Arithmetic that do not yield undecidable propositions by Gödel’s reasoning

(A compiled copy of Chapters 1 to 6 can be downloaded as a .pdf file from http://arxiv.org/abs/math/0201059.)

Chapter 5.  Gödel’s argument for undecidable propositions

Contents

 

5.0.  Introduction

5.1.  Every recursive function can be constructively represented in any Arithmetic

5.2.  Every representation of a recursive function has a unique Gödel-number

5.3.  Gödel’s recursive definition of provability

5.4.  Gödel’s Turing-computable q(x, y)

5.5.  Gödel’s constructive self-reference lemma

5.6.  Hilbert and Bernay’s representation lemma

5.7.  The Gödelian premise

5.8.  G$ is not provable

5.9.  ~G$ is not provable

5.10.  The essence of Gödel’s reasoning

5.11.  Gödel’s undecidable proposition GUS

5.12.  Gödel’s reasoning in PA

5.13.  Gödel’s reasoning does not establish his conclusions in most Arithmetics

5.14.  The Palimpsest syndrome in standard PA : Overview of the argument

5.15.  The Extended Representation Lemma

5.16.  The Palimpsest syndrome in standard PA : The proof

5.17.  Conclusion

5.0.  Introduction

We have argued in this paper that though Gödel’s reasoning for the formal undecidability of true propositions is valid in all the above systems of Arithmetic, the inferences that can be validly drawn from it depend on the choice of the particular system.

We now highlight the conditional nature of Gödel’s conclusions in a general Arithmetic GA.

We also argue that Gödel’s undecidable formulas have the form of palimpsests that translate as ill-defined sentences in every interpretation

5.1.  Every recursive function can be constructively represented in any Arithmetic

We note that, by a lemma of Hilbert and Bernays, if f(x, y) is a recursive function, then it can be constructively represented in GA by the well-formed formula F(x1, x2, x3), as defined in §2.2 above.

Specifically, this means that, in any of the above systems, we can construct Turing machines to verify that, for every set of natural numbers k, m, n, if f(k, m) = n then:

(i)      GA proves: F(k, m, n).

(ii)     GA proves: (Az)(~(z=n) => ~F(k, m, z)).

5.2.  Every representation of a recursive function has a unique Gödel-number

Since every recursive function, by definition, is built up from only a finite number of recursive functions of lower rank, we can further construct a Turing machine so that F(x1, x2, x3) can be expressed in only the primitive symbols of GA, and so uniquely coded and Gödel-numbered by some natural number F#.

5.3.  Gödel’s recursive definition of provability

Such a process of coding allows us, following Gödel, to define a recursive arithmetic relation prf(x, y), constructed out of 44 'simpler' recursive arithmetic functions and relations (Gödel 1931 p182), such that prf(x, y) is constructively true if and only if x is the Gödel-number of a finite proof sequence X in GA for some well-formed formula Y in GA whose Gödel-number is y.

In other words, for any given natural numbers k, m, we can construct a Turing machine T(prf(k, m)) to write out the finite expression of GA whose Gödel-number is k, check if this is a valid proof sequence of GA, extract the last element of the sequence, and check if the Gödel-number of this element is m, returning the value T(prf(k, m))=0 if prf(k, m) is true and 1 if prf(k, m) is false.

5.4.  Gödel’s Turing-computable q(x, y)

We can now define a Turing-computable function q(x, y) which is true if and only if x is the Gödel-number of a well-formed formula K(z) of GA with a single free variable z, and y is the Gödel-number of a proof of K(x) in GA.

In other words, given any numbers K#, M#, we can establish a Turing machine T(K#, M#) which will decode K# to yield the string K$ of GA, check if K$ is a well-formed formula in GA of the form K(z), decode and check if the string M$ is a valid proof sequence in GA, and then check if the last well-formed formula of the sequence is K(K#).

If so, it establishes that q(K#, M#) is true; if not, it establishes that q(K#, M#) is false.

5.5.  Gödel’s constructive self-reference lemma

Hence the constructive self reference involved in Gödel's argument is:

q(K#, M#) is true <=> M$ is a proof in GA of some well-formed formula K(K#) of GA.

5.6.  Hilbert and Bernay’s representation lemma

Now, by §5.1, since q(x, y) is recursive, there is a well-formed formula Q(x, y) of GA such that, for any natural numbers K#, M#:

(i)      q(K#, M#) is true => Q(K#, M#) is provable in GA, and

(ii)     q(K#, M#) is false => ~Q(K#, M#) is provable in GA.

5.7.  The Gödelian premise

We assume now that the well-formed formula P$ given by (Ay)(~Q(x, y)), and the well-formed formula G$ given by (Ay)(~Q(P#, y)), are well-formed formulas of a simply consistent GA.

5.8.  G$ is not provable

Assuming G$ is provable in GA, let M$ be the proof of (Ay)(~Q(P#, y)) in GA.

We then have that q(P#, M#) is true by definition.

Hence Q(P#, M#) is provable in GA, and so (Ey)Q(P#, y) is provable in GA.

Hence ~(Ay)(~Q(P#, y)) is provable in GA, i.e. ~G$ is provable in GA

We conclude that (Ay)(~Q(P#, y)) is not provable in GA if GA is simply consistent, i.e. G$ is not provable in GA if GA is simply consistent

5.9.  ~G$ is not provable

Assuming ~G$ is provable in GA, it follows that G$ is not provable in GA if GA is simply consistent.

Hence q(P#, y) is false for all y.

It follows that ~Q(P#, y) is provable in GA for all y.

So, in every interpretation of GA, ~Q(P#, y) translates as a true proposition for all y.

However, since ~G$ is provable in GA, then ~(Ay)(~Q(P#, y)) is provable in GA.

We then have the contradiction, in every interpretation of GA, that Q(P#, M#) translates as true for some M#, thus implying that GA is inconsistent.

We conclude that ~G$ is not provable in GA if GA is simply consistent.

5.10.  The essence of Gödel’s reasoning

What we have above is that, if G$ is a well-formed formula in GA, then:

(i)      [(GA proves: G$)  =>  (GA proves: ~G$)]  =>  ~(GA proves: G$)

(ii)     [(GA proves: ~G$)  =>  (Every interpretation of GA is inconsistent)]  =>  ~(GA proves: ~G$)

5.11.  Gödel’s undecidable proposition GUS

We consider now the well-formed formula G$ of GA, given by (Ay)(~Q(P#, y)), under interpretation.

We argue below, in §5.14, that if (Ay)(~Q(P#, y)) translates as a false sentence under any interpretation, then Q(P#, L#) translates as a true assertion for some L$.

However, we then have the contradiction that (Ay)(~Q(P#, y)) translates as a true sentence under the interpretation.

We conclude that, if G$ is a well-formed formula in GA, then G$ translates into a true proposition in every interpretation of GA, even though both the well-formed formulas G$ and ~G$ are not provable in GA, i.e. in every interpretation of GA, G$ yields a Gödelian, formally undecidable but true, proposition GUS.

5.12.  Gödel’s reasoning in PA

Since, by §2.13, the well-formed formula F(x1, x2, x3) is well-defined in PA for any primitive recursive function f(x, y), the above reasoning yields Gödel’s proof of undecidability as a non-trivial assertion in PA.

5.13.  Gödel’s reasoning does not establish his conclusions in most Arithmetics

However, in all the other systems of Arithmetic defined above, Gödel’s reasoning does not establish his conclusions significantly since the well-formed formula F(x1, x2, x3) is not obviously well-defined in these systems for every primitive recursive function f(x, y).

In systems of Arithmetic with an omega-constructive rule, in particular, the assumption §5.7 yields the meta-inconsistency:

(i)      [(GA proves: G$)  =>  (GA proves: ~G$)]  =>  ~(GA proves: G$)

(ii)     [~(GA proves: G$)  =>  (GA proves: G$)]  =>  (GA proves: G$)

Ipso facto, both G$ and ~G$ are not well-defined, well-formed formulas in any systems of Arithmetic with an omega-constructive rule.[1]

They are thus trivially unprovable, and Gödel’s formally undecidable proposition GUS trivially true, in every interpretation of a system of Arithmetic with an omega-constructive rule.

5.14.  The Palimpsest syndrome in standard PA : Overview of the argument

We now argue that GUS essentially formalises the Liar sentence in standard PA by means of a “palimpsest”.[2]

We argue that, by virtue of its roots in the finite construction, through Gödel-numbering, of the primitive recursive relation q(P#, y), every interpretation of Gödel’s undecidable formula (Ay)(~Q(P#, y)) can constructively be well-defined over the entire domain of any interpretation M in such a way that it is equivalent to the assertion:

"For all y, the formula Y, whose Gödel-number is y, is not the interpretation of a finite proof sequence in standard PA for the formula (Ay)(~Q(P#, y)), whose Gödel-number is P#, from the given set Axm of recursively defined axioms, and the given set Inf of recursively defined rules of inference, of standard PA."

If standard PA is assumed consistent, this means either that the sentence (Ay)(~Q(P#*, y)) (where P#* is the interpretation in M of the numeral P#) can be interpreted as true in every interpretation M of standard PA (since the set Axm of axioms, and set Inf of rules of inference, of Gödel’s formal system of standard PA, are defined recursively), or the expression (Ay)(~Q(P#*, y)) treated as an ill-defined sentence in every M under interpretation.

In other words, even if (Ay)(~Q(P#, y)) is a well-defined formula in standard PA, there can be no consistent, non-standard model M of standard PA in which its interpretation (Ay)(~Q(P#*, y)) is uniquely false.

(The latter would imply the contradiction that we can write out a finite proof sequence in standard PA for the unprovable formula (Ay)(~Q(P#, y)) using only the given set Axm of axioms and the given set Inf of rules of inference of standard PA.)

By virtue of Gödel’s completeness theorem for first order predicate calculus, it then follows that even if, like Russell's paradoxical set, the formula (Ay)(~Q(P#, y)) appears to be a valid construction in standard PA, it must translate as an ill-defined sentence under every interpretation.

In other words, there is an essential element in the definition of the formula (Ay)(~Q(P#, y)) such that, as in the case of the Liar sentence, we cannot constructively ascribe, or even non-constructively assume, either truth or falsity to/for the sentence (Ay)(~Q(P#*, y)) in an interpretation without inconsistency.

It is a moot point whether we choose to treat (Ay)(~Q(P#*, y)) as an ill-defined “sentence” in every interpretation, or to treat standard PA as an inconsistent system.

5.15.  The Extended Representation Lemma

To give the argument in detail, we note the following meta-properties of recursive arithmetical relations f(y) where, if M is any interpretation of standard PA then, for all natural numbers n, and their representations n and interpretations n* in standard PA and M respectively:

f(n) is true in the standard interpretation

=> F(n) is provable in standard PA

=> F(n*) is true in the interpretation M

f(n) is false in the standard interpretation

=> ~F(n) is provable in standard PA

=> F(n*) is false in the interpretation M

From this we conclude that, for every natural number n:

f(n) is true in the standard interpretation  <=>  F(n*) is true in the interpretation M

If we extend the definition of f(x) in the standard interpretation SI so that f(x) is false if x is not a natural number, then we have the Extended Representation meta-Lemma for recursive arithmetical functions f(x):

  f(x) is true in the standard interpretation  <=>  F(x) is true in the interpretation M

5.16.  The Palimpsest syndrome in standard PA : The proof

We note that Gödel’s undecidable formula ~(Ay)(~Q(P#, y)) now translates as a well-defined sentence over the entire domain of any interpretation M.

The significance of the Extended Representation meta-Lemma is that, by virtue of Goedel’s original definition of the primitive recursive relation q(P#, y) - involving only finite Gödel-numbers of finite sets of well-formed, well-defined finite formulas and finite proof sequences of standard PA - its representation Q(P#, y) in standard PA is well-defined only over the denumerable domain of the numerals n in standard PA, corresponding to the denumerable natural numbers n.[3]

It follows that, in any interpretation M of standard PA, the sentence ~