Constructivity05

◄ 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(x₁, x₂, x₃), 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(x₁, x₂, x₃) 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(x₁, x₂, x₃) 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(x₁, x₂, x₃) 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 ~(Ay)(~Q(P#*, y)) - which is equivalent to the assertion (Ey)Q(P#*, y) - is well-defined if and only if the relation Q(P#*, a*) is satisfied for some value a* in the domain of M that is an interpretation of some numeral a of standard PA. However, we cannot conclude from this that Q(P#*, a*) is well-defined - and so decidable - for every value a* in the domain of M that is not an interpretation of some numeral a of standard PA.

This lacuna is now filled by the Extended Representation meta-Lemma, which ensures that the range over which the relation Q(P#*, a*) is well-defined covers the entire domain of M, and that Q(P#*, a*) is not satisfied by any value a* in the domain of M that is not an interpretation of some numeral a of standard PA.

This follows immediately since (Ay)(~Q(P#*, y)) in M is now equivalent to:

"For all y, the formula Y, whose Gödel-number is y, is not the interpretation in M 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."

In other words, the sentence ~(Ay)(~Q(P#*, y)) is well-defined in M, and Q(P#*, a*) is necessarily false for all values a* in the domain of M that are not interpretations of some numeral a of standard PA.

(The argument here is that the relation Q(x, y) can always be well-defined in every interpretation M of standard PA in such a way that it mirrors the “palimpsest” that is embedded in the definition of the relation q(x, y) of the standard interpretation SI.)

We thus argue that there is no interpretation in which the formula ~(Ay)(~Q(P#, y)) of standard PA uniquely translates as a well-defined sentence ~(Ay)(~Q(P#*, y)) that can be true for some value a* in the domain of M that is not an interpretations of some numeral a of standard PA.

Hence the truth of the sentence ~(Ay)(~Q(P#*, y)) in any interpretation M of standard PA can always be defined so as to imply the truth of Q(P#*, n*) for some n* in M, where n* is the interpretation of the numeral n in M.

This, of course, implies the truth of q(P#, n) for some natural number n in the standard interpretation SI by the Extended Representation meta-Lemma. This in turn, by Gödel’s Self-reference Lemma for q(P#, y), implies that n is a proof of the sentence (Ay)(~Q(P#, y)) in standard PA, contradicting the unprovability of the formula (Ay)(~Q(P#, y)) in standard PA.

Hence the sentence ~(Ay)(~Q(P#*, y)) can be falsified in every interpretation M of standard PA, so that the sentence (Ay)(~Q(P#*, y)) is true in every interpretation M of standard PA.

However, by Gödel’s completeness theorem for first order predicate logic, this again implies that the formula (Ay)(~Q(P#, y)) is provable in standard PA.

5.17. Conclusion

The contradiction establishes that, if standard PA is consistent, then Gödel’s undecidable formulas, (Ay)(~Q(P#, y)) and ~(Ay)(~Q(P#, y)), translate as ill-defined sentences under interpretation[4].

◄ Index ◄ Contents ◄ Chapter 1 ◄ Chapter 2

◄ Chapter 3 ◄ Chapter 4 ▲ Chapter 5 Conclusions ► Web_links ►

(Updated : Friday 11th January 2002 2:37:10 AM by re@alixcomsi.com)

References

Burbanks, Andrew. (e-seminar) Fast-Growing Functions and Unprovable Theorems.

<Ord’ls : http://www.maths.bris.ac.uk/~maadb/research/seminars/online/fgfut/fgfut09.html>

Davis, M (ed.). 1965. The Undecidable. Raven Press, New York.

Franzén, Torkel. Provability and Truth.

< Home page : http://www.sm.luth.se/~torkel/>

Friedman, Harvey. 1997. Unprovable theorems in discrete mathematics.

Gödel, Kurt. 1931. On formally undecidable propositions of Principia Mathematica and related systems I. Also in M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

<1931 Paper : http://www.ddc.net/ygg/etext/godel/godel3.htm>

< Beta-function : http://www.ddc.net/ygg/etext/godel/godel3.htm - LEMMA1>

< See remarks on p189 : http://www.ddc.net/ygg/etext/godel/godel3.htm - 16>

<Eqn. 8.1 : http://www.ddc.net/ygg/etext/godel/godel3.htm - EQ8.1>

<cf. Recursive definition #17 : http://www.ddc.net/ygg/etext/godel/godel3.htm - DEF17>

<cf. Proposition V : http://www.ddc.net/ygg/etext/godel/godel3.htm#PROP-V>

Gödel, Kurt. 1934. On undecidable propositions of formal mathematical systems. In M. Davis (ed.). 1965. The Undecidable. Raven Press, New York.

Lucas, J. R. The Gödelian argument.

<Gödelian argument : http://www.leaderu.com/truth/2truth08.html>

Mendelson, Elliott. 1964. Introduction to Mathematical Logic. Van Norstrand, Princeton.

Parikh, Rohit. 1973. On the length of proofs. In Trans. AMS, 177, 29-36

Parsons, Charles D. 1995. Platonism and mathematical intuition in Kurt Gödel's thought. In The Bulletin of Symbolic Logic, Volume 1, Issue 1, March 1995.

<1995 Article : http://www.math.ucla.edu/~asl/bsl/0101-toc.htm>

Peregrin, Jaroslav. 1997. Language and its Models: Is Model Theory a Theory of Semantics?

< cf. also Models : http://www.hf.uio.no/filosofi/njpl/vol2no1/models/models-html.html>

<cf. also Quantifier : http://www.hf.uio.no/filosofi/njpl/vol2no1/models/node8.html>

<cf. also Basis : http://www.hf.uio.no/filosofi/njpl/vol2no1/models/node5.html>

< cf. also Consequence : http://www.hf.uio.no/filosofi/njpl/vol2no1/models/node11.html>

< cf. also Truth : http://www.hf.uio.no/filosofi/njpl/vol2no1/models/node3.html>

< cf. also Language : http://www.hf.uio.no/filosofi/njpl/vol2no1/models/node2.html>

Podnieks, Karlis. 2001. Around Goedel's Theorem.

<Goedel's Incompleteness Theorem : http://www.ltn.lv/~podnieks/gt5.html - BM5_3>

<Formula-number : http://www.ltn.lv/~podnieks/gt5.html - BM5_2>

<Self-reference lemma : http://www.ltn.lv/~podnieks/gt5.html - BM5_2>

Rosmaita, Brian J. Minds, machines, and metamathematics: constraints on the mathematical objection to mechanism.

Web resources

Free On-line Dictionary of Computing.

<cf. constructive : http://lgxserve.ciseca.uniba.it/lei/foldop/foldoc.cgi?query=constructive>

<Cmprhn. axiom : http://ase.isu.edu/ase01_07/ase01_07/bookcase/ref_sh/foldoc/99/8.htm>

Free On-line Dictionary of Philosophy.

Glossary of First-Order Logic.

<cf. Meta... : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - metalanguage>

<Intrprttn. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - interpretation>

<Omega-comp. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - omegacom>

<Denum. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - denumerableset>

<Rcrsv. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - recursivefunction>

<Cptbl. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - computablefunction>

<Std. set theory : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - settheory>

<Gödel-number : http://www.earlham.edu/~peters/courses/logsys/glossary.htm#gnumbering>

<Well-formed formula : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - wff>

<Rprsntn. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - repfunction>

<Exstnc. pr. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - existenceproof>

<Cnst. pr. : http://www.earlham.edu/~peters/courses/logsys/glossary.htm - constructiveproof>

Internet Encyclopedia of Philosophy

Larry Hauser’s Mostly Modern Philosophical Glossary.

MacTutor History of Mathematics archive

MathPages

Stanford Encyclopedia of Philosophy.

<cf. also Non-constructive : http://plato.stanford.edu/entries/mathematics-constructive/ - 2>

<cf. also Constructive : http://plato.stanford.edu/entries/mathematics-constructive/ - 1>

<cf. also Platonism : http://plato.stanford.edu/entries/mathphil-indis/ - 1>

Web Dictionary of Cybernetics and Systems

xrefer

<cf. Formalism : http://www.xrefer.com/entry/552091>

[1] We note that Russell’s anomalous set R, defined by {x | ‘x is a member of R’, ‘x is not a member of x’} as the set of all sets that are not members of themselves, can also be expressed in terms of the primitive symbols of an axiomatic set theory S. However, the assumption that the well-formed formulas ‘R is a member of R’ and ‘R is not a member of R’ are well-defined, well-formed formulas of S is inconsistent with the axioms of S.

[2] The intention here is to translate the formula ‘(Ay)(~Q(P#, y))’ from standard PA into English in order to argue the point that the truth of this assertion, under any interpretation, does not depend on the interpretation into which it is translated, but on the truth of a factual assertion, pertaining to standard PA specifically, that is embedded in the formula ‘(Ay)(~Q(P#, y))’ itself in the form of a “palimpsest”.

For example, albeit at an explicit level, the statement “The English word ‘tree’ contains four letters of the English alphabet” must remain true no matter into which language - standard PA, Sanskrit, sign-language etc. - it is translated; it contains an assertion of fact that cannot be altered by the language into which it is translated.

If the destination-language contains the source-language, then it may indeed be able to determine the truth of factual assertions such as the above. If not, such assertions would be factually undecidable, at least until enough of the source-language is suitably adjoined.

The thesis here is that every interpretation of Gödel’s formal system of standard PA in another language implicitly preserves the logical content of “named” entities; moreover, it subsumes standard PA and so contains the necessary wherewithal to determine the truth or falsity of factual assertions pertaining to the formal system of standard PA.

[3] The central issue in these papers actually concerns the relationship of the formally represented elements to the elements that they seek to represent. Thus, if standard PA is to serve as the formal representation of intuitive arithmetic IA, then the questions that must be addressed are whether every element of intuitive arithmetic IA is represented in standard PA, and whether there are elements of standard PA that are not reflected in intuitive arithmetic IA.

If we assume that our intuitive arithmetic IA is what we define as the standard interpretation SI of standard PA, then the question is whether every element of the standard interpretation SI is represented in standard PA, and whether there are elements of standard PA that are not reflected in the standard interpretation SI.

In the former case, standard PA must be judged as inadequate to our intent; in the latter, as containing elements extraneous to our intent.

Applying the same measure to the representation of, say, a function f(x) of the standard interpretation SI by some formula F(x, y) of standard PA, it follows that if f(x) is an intuitively well-defined function, then F(x, y) too must be a well-defined representation, i.e. F(x, y) cannot be considered to represent f(x) in some respects only, but must be taken to represent it entirely.

We argue that Gödel’s interpretation of undecidability actually violates this basic integrity. It implies that the truth of some propositions cannot be reflected in the formalisation, whilst the undecidability of some formulas cannot be reflected in the assertions that they represent.

We argue that this interpretation is subjective, and that a more objective interpretation implies that the undecidability of some formulas in standard PA reflects assertions in the standard interpretation SI that cannot be ascribed any truth-value, and are thus ill-defined assertions similar to the Liar sentence, and not true sentences as concluded by Gödel.

[4] The cause of such ill-definedness apparently lies in the formal definition of Q(x, y) as the representation of q(x, y) in standard PA through use of the Gödel Beta function. By definition, Q(x, y) thus represents, in standard PA, an infinity of “recursive” functions of every interpretation (cf. §2.9).

Hence the PA provability of Q(k, m) may be intuitively viewed as corresponding, in any interpretation M, to the intuitive assertion that, for any interpretations k* and m* in M of the numerals k and m, we can always construct some (non-unique) pair of values u*, v* such that we can define a “Beta-function” β*(u*, v*, i) in M that represents the first m* terms, i.e. q'(k*, 0*), q'(k*, 1*), ... , q'(k*, m*), which are common to an infinity of “primitive recursive relations” of M, such as q'(x, y), that are formally represented in PA by Q(x, y)..

Clearly, in this view, the provability of the formula Q(x, y) for variable x and y does not interpret similarly into a unique, well-defined proposition that can be asserted as true in M. It follows that the provability of ~Q(x, y) in PA interprets as a true proposition in M by virtue of its ill-definedness (i.e. although we may not intuitively assert an ill-defined proposition as true in M, we may yet assert that it is not a true proposition in M).

◄ Index ▲ Chapter 5 Bibliography ► Web_links ►

(Updated : Friday 11^th January 2002 2:38:02 AM by re@alixcomsi.com)