Section 2 : Why did Gödel ignore this reasoning?
In his Theorem VI, Gödel ignores the ‘natural’ translation of the ‘Liar paradox’ into a recursive relation, and overlooks a simple proof invalidating his reasoning in Theorem V that every recursive relation is expressible in S.
1 Gödel’s Theorem VI
In his seminal 1931 paper ‘On Formally Undecidable Propositions of Principia Mathematica and Related SystemsI’, Gödel rigorously defines a formal system[1] S and, in Theorem VI[2], considers a recursive[3] arithmetical relation Q(x, y)[4], which translates equivalently[5] as :
‘The formula[6] (sequence) X, whose Gödel-number[7] is x, is not a proof-sequence[8] in S of the formula (n-ary predicate[9]) obtained from the formula (n-ary predicate) Y, whose Gödel-number is y, when we substitute the numeral z(y)[10] for the formula (free variable) whose Gödel-number is 19[11] in the formula (n-ary predicate) Y whose Gödel-number is y.’[12]
2 Gödel’s Theorem V
Earlier, in his Theorem V, Gödel’s thesis is that every recursive relation (and function) F can be formally represented in, and defined[13] as, a formula F[14] of the formal system S[15], and so uniquely Gödel-numbered by some constructible integer f, which latter, in turn, is representable in S as the numeral z(f)[16].
Accordingly, the above recursive relation Q(x, y) in Theorem VI can also be defined as a formula (binary predicate) Q(x, y) of S, which has a unique Gödel-number q.
Now, for any recursive formula (n-ary predicate) F of say n free variables, either F or ~F is always provable on the basis of the axioms of the system S[17] for any given n-tuples of numbers for the n variables contained in F.[18]
Hence the recursive formula (class expression) R(x) - obtained by substituting the numeral z(q) for y in Q(x, y) - also has some unique Gödel-number r, is decidable[19] in S for every formula (X, x)[20], and translates as :
‘The formula (sequence) (X, x) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(q) for the formula (numerical variable) whose Gödel-number is 19 in the formula (binary predicate) (Q, q).’[21]
4 ‘(R, r)’ is not provable in
S
Suppose, now, that the formula (sequence) (N, n) is a proof-sequence in S of the recursive formula (class expression) (R, r).[22]
The formula (R, r) is then provable in S for every formula (sequence) (X, x) [23].
In particular, for the formula (sequence) (N, n), we have that :
‘The formula (sequence) (N, n) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(q) for the formula (numerical variable) whose Gödel-number is 19[24] in the formula (binary predicate) (Q, q).’[25]
However, the recursive formula (class expression) (R, r) is by definition also the formula (class expression) in S obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(q) for the formula (numerical variable) whose Gödel-number is 19 in the formula (binary predicate) (Q, q).[26]
The contradiction[27] establishes that there is no formula (sequence) (N, n) which is a proof-sequence in S of the recursive formula (class expression) (R, r).
5 ‘(R, r)’ is provable in S
However, we then have that the recursive formula (class expression) (R, r) holds by definition in S for every formula (X, x)[28].
Further, since the formula (class expression) (R, r) is recursive, it then follows that the formula (class expression) (R, r) is provable in S for every formula (X, x), and so the recursive formula (class expression) (R, r) is provable in S[29].
So some formula (sequence) (N, n) can be constructed which is a proof-sequence in S of the formula (class expression) (R, r).
6 Gödel’s Theorem V is invalid
We thus have that :
The formula (class expression) (R, r) is provable in S → The formula (class expression) (R, r) is not provable in S, and
The formula (class expression) (R, r) is not provable in S → The formula (class expression) (R, r) is provable in S.
The contradiction[30] establishes that the formula (binary predicate) Q(x, y) in Theorem VI cannot be defined in S, and so it cannot be associated with a unique Gödel-number q.
Gödel’s thesis in his Theorem V, that every recursive formula F can be formally defined as some formula (n-ary predicate) F of his formal system S, and that the latter is uniquely Gödel-numberable by some integer f, is thus invalid.
7 Gödel’s formula ‘(G, g)’
Now we note that Gödel ignores the above straightforward reasoning which closely parallels the ‘Liar’ paradox[31] in the formal system S.
Instead, in his Theorem VI (where he establishes his undecidable sentence in S as below) he applies closure to the recursive formula (binary predicate) (Q, q) and defines the (not necessarily recursive) formula (class expression) (P, p)[32], which translates as :
‘For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (n-ary predicate) obtained from the formula (n-ary predicate) (Y, y) when we substitute the numeral z(y) for the formula (numerical variable) whose Gödel-number is 19 in the formula (n-ary predicate) (Y, y).’[33]
He then defines the recursive formula (phrase) (R', r')[34], which translates as :
‘The formula (class expression) obtained from the formula (binary predicate) Q, whose Gödel-number is q, when we substitute the numeral z(p) for the formula (numerical variable) whose Gödel-number is 19 in the formula (binary predicate) Q whose Gödel-number is q.’
Gödel finally considers the provability in S of the formula (sentence) G, whose Gödel-number g is easily constructed from r'[35], which translates as :
‘For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(p) for the formula (numerical variable) whose Gödel-number is 19 in the formula (binary predicate) (Q, q).’[36]
This is equivalent to the formula (sentence) that translates as :
‘For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (sentence) (G, g).’[37]
8 Gödel’a proof : ‘(G, g)’ is not provable in S
Gödel then concludes that the formula (sentence) (G, g) is not provable in S for, if some formula (sequence) (N, n) is a proof sequence of the formula (sentence) (G, g) in S, then it would also follow from the provability of the formula (sentence) (G, g) in S that :
‘For all formulas (sequences) (X, x), the formula (X, x) is not a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(p) for the formula (numerical variable) whose Gödel-number is 19 in the formula (binary predicate) (Q, q).’
In particular, this would then yield the contradiction :
‘The formula (sequence) (N, n) is not a proof-sequence in S of the formula (sentence) (G, g).’
9 Gödel’s proof : ‘(~G, g')’ is not provable in S
Gödel next considers and concludes that the formula (sentence) ~G, whose Gödel-number we denote by g'[38], is also not provable in S for, if the formula (sentence) (~G, g') were provable in S, then the formula (sentence) (G, g) too would be provable in S as it would follow from the provability of the formula (sentence) (~G, g') that :
‘For some formula (sequence) (X, x), the formula (X, x) is a proof-sequence in S of the formula (class expression) obtained from the formula (binary predicate) (Q, q) when we substitute the numeral z(p) for the formula (numerical variable) whose Gödel-number is 19 in the formula (binary predicate) (Q, q).’
This is equivalent to, and yields, the contradiction :
‘Some formula (sequence) (N, n) is a proof-sequence in S of the formula (sentence) (G, g).’
In conclusion, we raise the intriguing questions :
a) Why did Gödel ignore the straightforward, natural translation of the ‘Liar’ paradox into the formal system S as outlined in §1 - §3?
b) How did Gödel overlook the simple proof invalidating his Theorem V as outlined in §4 - §6?
c) What areas of mathematics and logic are affected if every recursive function is not expressible formally in terms of the primitive symbols of the formal system S?
Notes (Why02ct.doc : 4/7/01 3:22:26 AM)
[1] Gödel develops in great detail the formal system S that he intends to consider, noting that this is ‘ … essentially the system which one obtains by building the logic of PM (Principia Mathematica) around Peano’s axioms (numbers as individuals, successor relation as undefined primitive concept).’ [Gödel 1931: p9-13]
[2] ‘For every w-consistent recursive class k of FORMULAS, there exists a recursive CLASS EXPRESSION r such that neither vGenr nor Neg(vGenr) belongs to Flg(k) (where v is the FREE VARIABLE of r).’ [Gödel 1931: p24]
[3] ‘A
number-theoretic function φ is said to be recursive if there exists a finite sequence of
number-theoretic functions φ1, φ2,
… φn
which ends with φ and has the property that each
function φk of the sequence either is defined
recursively from two of the preceding functions, or results from one of the
preceding functions by substitution, or, finally, is a constant or the
successor function x
+ 1. The length of the shortest sequence of φi's belonging
to a recursive function φ is called its rank. A relation
between natural numbers R(x1, x2, … , xn) is called recursive if there
exists a recursive function φ(x1, x2, … ,
xn) such that,
for all x1, x2, … , xn, R(x1, x2, … ,
xn) ≡ [φ(x1, x2, … , xn)
= 0 ].’ [Gödel
1931 : p14-15]
[4] Where the context is unambiguous, we shall refer to relations (functions) such as ‘Q(x, y)’ as ‘Q’, and formulas such as ‘Q(x, y)’ as ‘Q’.
[5] i.e. the
translation holds if and only if the recursive arithmetical relation Q(x, y) holds.
[6] Gödel defines the primitive symbols of S as consisting of various constants and variables; combinations of certain symbols as terms; and combinations of certain symbols and terms as the various types of formulas of S. [Gödel 1931: p11]
For convenience of exposition in translations, we sometimes
use the word ‘formula’ to also refer to any formal expression consisting of a
finite sequence of the primitive symbols of S, or - as
here - to a finite sequence of formal expressions.
[7] Gödel
describes in detail how every primitive symbol of S, every
formal expression consisting of a finite sequence of such symbols of S,
and every sequence of formal expressions can be arithmetised and correlated
uniquely to some natural number - which we define as the Gödel-number
of the formal expression in question. [Gödel
1931: p10-11 & p13-14]
[8] Gödel defines a ‘proof sequence’ as a finite sequence of formulas such that each is either an axiom of S, or a formula that is an immediate consequence of the axioms of S and some of the preceding formulas in the sequence by the formal rules of inference of S. [Gödel 1931: p14 & p22 definition44]
[9] ‘A
sentence is a formula in which no free variables occur (free variables being
defined in the usual way). A formula with exactly n free variables (and otherwise no
free variables) is called an n-ary predicate, for n = 1 also a class expression.’ [Gödel
1931: p11]
[10] z(y) is recursively defined to be the formal representation of
the integer y
in S [Gödel
1931: p19 definition 17]
[11] In Gödel’s particular arithmetisation in the cited paper, each variable in a formula can be arbitrarily, but uniquely, correlated to some prime number > 13. [Gödel 1931: p13]
[12] The
equivalent recursive arithmetical relation Q(x, y) is a relation between only the various
Gödel-numbers
occurring in the translation, and is expressed in Gödel’s
terminology by ‘~ [ x B [ Sb ( y : (19,
z(y)) ) ] ]’. [Gödel
1931: p14 & p17-22]
In Gödel’s terminology, the
recursive arithmetical Q(x, y) relation actually
translates as ‘The FORMULA x is not a PROOF
SEQUENCE of the FORMULA obtained from the FORMULA y
when we substitute the NUMERAL z(y)
for the VARIABLE 19 in the FORMULA y.’ [Gödel
1931: p13-14]
[13] i.e.
expressed equivalently using only the primitive symbols of the formal system S.
[14] We use bold italic letters to denote the formulas such as F of the formal system S that correspond equivalently to the arithmetical formulas such as F.
[15] Gödel notes that his Theorem V is the rigorous expression of the ‘ … fact which can be vaguely formulated as the assertion that every recursive relation is definable within the system S (under its intuitive interpretation) … without reference to the intuitive meaning of the formulas of S.’ [Gödel 1931: p22]
[16] [Gödel
1931: p19 definition 17]
[17] i.e. there
is some proof sequence in S
such that either F
or ~F is the last
formula in the sequence.
[18] Gödel
notes this as the ‘… fact that, for a recursive relation F, it is
decidable (provable) on the basis of the axioms of the system S whether or not F holds for
any given n-tuple
of numbers’. [Gödel 1931: p23 footnote 39]
[19] i.e. either
R(x) or ~R(x) is provable.
[20] From here
on we use the notation ‘(X, x)’ to denote the phrase ‘X, whose Gödel-number
is x’.
[21] The
formula (class expression) R(x) is the formal representation of the recursive
arithmetical relation R(x) between the
various Gödel-numbers
occurring in the translation, the relation itself being expressed in Gödel’s
terminology by ‘~ [ x B [ Sb ( q : (19, z(q)) ) ] ]’. [Gödel
1931: p14 & p17-22]
[22] In Gödel’s
terminology, this supposition is equivalently expressed by ‘n B r’. [Gödel
1931: p14 & p22 definition 45]
[23] This
inference, and its converse, follow from a particular case where we explicitly
express Gödel’s
implicit requirement (necessary for the hypothesis postulated by him in his
Theorem V) that recursive relations (and functions) be meaningfully
definable within S
in a constructive and intuitionistically unobjectionable manner. In this case
we meet such a requirement by explicitly postulating, in the meta-theory M of S, Gödel’s
Implicit Intuitionist Meta-thesis that a recursive formula be provable
in S if and only if
it is provable in S
for all non-negative integer values of the variables contained in it. In this
instance, if we denote the meta-statement ‘R(x) is a provable formula of S’ by ‘├S R(x)’, it would
mean that :
├S R(x) ≡M (n)├S R(n).
Such a thesis ensures that the provability of a recursive formula of S is always determined by its provability in a denumerable sub-domain of S. We conjecture that it is the absence of such specification that permits the surreptitious entry of arguably ill-defined, Platonistic, ‘elements’ into S, such as those leading to a paradox, since the domain of ‘x’ need not be denumerable under interpretation.
Also, the representations in S of some, if not all, of Gödel’s
46 definitions [Gödel 1931: p17-221] - such as those of, for
instance, ‘x/y’ of divisibility,
Prim(x) of primality
and ‘Bew(x)’of provability
(equivalent to that of the notation ‘├S’)
- cannot be assumed to be well-defined over an extended, transfinite, range,
since these are defined [Gödel 1931: p14] only through an interpretation over
the non-negative integers. Thus we may reasonably conclude that Gödel’s
definitions and reasoning are valid, and significant, only in those
interpretations of his formal system S
that are denumerable domains, and where some specification such as Gödel’s
Implicit Intuitionist Meta-thesis holds.
[24] We note
that the formula (numerical variable) whose Gödel-number
is 19 in the formula (n-ary
predicate) (Q,
q) is ‘y’.
[25] This
sentence is the translation of, and equivalent to, the arithmetical relation
between the Gödel-numbers
of the various components contained in it, expressed in Gödel’s
terminology [Gödel 1931: p14 & p17-22] by ‘~ [ n B [ Sb ( q : (19, z(q)) ) ] ]’.
[26] In Gödel’s
terminology, this fact is equivalently expressed by ‘r = Sb ( q : (19,
z(q)) )’. [Gödel
1931: p24-25]
[27] In Gödel’s
terminology, we have the contradiction ‘n B
r →
~ ( n B r)’. [Gödel
1931: p24-26]
[28] If we define ‘╟A R(n)’ as the meta-statement ‘The sentence R(n) holds in the model (interpretation) A of S’, this meta-statement can be expressed as ‘(n)╟All A R(n)’, where n ranges over the non-negative integers.
[29] Based on 23above, this meta-reasoning can be expressed (loosely) as :
R(x) is recursive →M [ (n)╟ All A R(n) →M (n)├S R(n) →M ├S R(x) ].
[30] In Gödel’s
terminology, we have ‘(Bewr → ~Bewr) & (~Bewr → Bewr)’. [Gödel 1931: p22]
[31] The paradox
that arises if we define the ‘Liar’ sentence as “The ‘Liar’
sentence is a lie’. [Davis 1965: p63-64]
[32] In Gödel’s
terminology, this formula (class expression) P(y) is determined
by defining its Gödel-number by ‘p = 17Gen q’. [Gödel
1931: p14 & p24-26]
[33] The formula (class expression) P(y) is the formal representation of the arithmetical relation between Gödel-numbers expressed in G