◄
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
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:
(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.
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 ~