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

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]

Accordingly, the above recursive relation Q(*x*, *y*) in *Theorem
VI* can also be defined as a formula (*binary predicate*) ** Q**(

Now, for any recursive formula (*n-ary predicate*) ** F** of say

Hence the recursive formula (*class expression*) ** R**(

‘The formula (*sequence*)
(** X**,

4 ‘(*R*, *r*)’ is not provable in
S

Suppose, now, that the formula (*sequence*) (** N**,

The formula (** R**,

In particular, for the formula (*sequence*) (** N**,

‘The formula (*sequence*) (** N**,

However, the recursive formula (*class expression*) (** R**,

The contradiction[27]
establishes that there is no formula (*sequence*)
(** N**,

5 ‘(*R*, *r*)’ is provable in S

However, we then have that the recursive formula (*class
expression*) (** R**,

Further, since the formula (*class expression*) (** R**,

So some formula (*sequence*)
(** N**,

6 Gödel’s
*Theorem V* is invalid

We thus have that :

The formula (*class
expression*) (** R**,

The formula (*class
expression*) (** R**,

The contradiction[30]
establishes that the formula (*binary predicate*) ** 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

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**,

‘For all formulas (*sequences*) (** X**,

He then defines the recursive formula (*phrase*) (** R'**,

‘The formula (*class
expression*) obtained from the formula (*binary predicate*) ** Q**,
whose Gödel-number
is

Gödel finally considers the
provability in **S** of
the formula (*sentence*) ** G**, whose Gödel-number

‘For all formulas (*sequences*) (** X**,

This is equivalent to the formula (*sentence*) that
translates as :

‘For all formulas (*sequences*) (** X**,

8 Gödel’a
proof : ‘(*G*, *g*)’ is not provable in S

Gödel then concludes that
the formula (*sentence*) (** G**,

‘For all formulas (*sequences*) (** X**,

In particular, this would then yield the contradiction :

‘The formula (*sequence*) (** N**,

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

‘For some formula (*sequence*) (** X**,

This is equivalent to, and yields, the contradiction :

‘Some formula (*sequence*) (** N**,

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
*v*Gen*r* nor Neg(*v*Gen*r*)* *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}*,

[4] Where the
context is unambiguous, we shall refer to relations (*functions*) such as
‘Q(*x*, *y*)’ as ‘Q’, and formulas such
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

[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

[18]** **Gödel
notes this as the ‘*…* fact that, for a recursive relation ** F**, it is
decidable (

[19] i.e. either
** R**(

[20] From here
on we use the notation ‘(** X**,

[21]** **The
formula (*class expression*) ** R**(

[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}** **** R**(

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:

[24] We note
that the formula (*numerical variable*) whose Gödel-number
is 19 in the formula (*n-ary
predicate*) (** Q**,

[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(

[29] Based on **23**above, this meta-reasoning can be
expressed (*loosely*) as :

R(*x*) is recursive
→** _{M}** [ (

[30]** **In Gödel’s
terminology, we have ‘(Bew*r* → **~**Bew*r*) & (**~**Bew*r* → Bew*r*)’. [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**(

[33]** **The
formula (*class expression*) ** P**(

[34] In Gödel’s
terminology, this formula (*phrase*) ** R'** is determined by defining its Gödel-number
by ‘

[35] In Gödel’s
terminology ‘*g*
= 17Gen**
***r'*’.

[36]** **The formula
(*sentence*) ** G**
is the formal representation of the arithmetical relation between the various Gödel-numbers
occurring in the translation, expressed in Gödel’s
terminology by ‘(

[37] The
justification for the legitimacy of this formula as a formula of **S**, and for its equivalence
to the formula (*sentence*) ** G** after appropriate substitutions,
lies in Gödel’s
assertion that, by his definitions and assuming the validity of his

[38]** **In Gödel’s
terminology ‘*g'*
= **Neg ***g*’.

**◄ Index
◄ Title ◄ Preface ◄ Contents ◄ Section 1 ▲ **Section 2

*Section
3* ► *Section 4*
► *References* ► *Roots* ► *Bibliography* ► *Web_links* ►

** ( Updated : 10/11/01 1:57:50 AM by re@alixcomsi.com)**