◄ Index |
Section 4 : Does Gödel’s implicit intuitionist meta-thesis demolish strong AI?
Gödel’s proof of undecidability implicitly presumes an intuitionist meta-thesis, and postulates as a Theorem that every recursive relation is representable in his formal system S. We explicitly postulate such a meta-thesis, and use it to construct a simple recursive relation that is not representable in S. Though this does not negate Gödel’s postulation that there are undecidable sentences in consistent formal systems, his particular constructions of such sentences do collapse. In this paper we attempt to highlight significant questions of contemporary interest concerning the value and validity of a Platonist philosophy, the limitations of machine intelligence, and the basis for strong AI that arise if some recursive relation is not formally representable in a consistent S.
1 Gödel’s startling hypothesis
In 1931 Gödel put forth the startling hypothesis - supported by astonishing mathematical constructions and arguments - that ‘… there exist relatively simple problems of the theory of ordinary whole numbers which cannot be decided on the basis of the axioms. … More precisely, there exist undecidable sentences in which, other than the logical constants ‘~ (not)’, ‘Ú (or)’, ‘(x) (for all x)’, ‘= (identical with)’, the only concepts occurring are ‘+ (addition)’ and ‘. (multiplication)’ of natural numbers, and where the prefix ‘(x)’ refers only to natural numbers.’.[1]
2 Significance of Gödel’s hypothesis
The significance of Gödel’s remarkable, yet deceptively simple, claim, lay in the dilemma that philosophers and mathematicians considered themselves to be in as an innocuous 2000 year old paradox was re-constructed by Bertrand Russell and others in logical, mathematical and linguistic settings during efforts[2] to establish stable foundations for scientific thought and reasoning.
The earlier paradox, loosely ascribed to Epimenides, arises obviously if we postulate by definition that a ‘Liar’ sentence, which reads as ‘The ‘Liar’ sentence is a lie’, is a valid sentence within the language in which the sentence is constructed.[3]
Clearly the grammar of an ordinary language, which governs the construction of words and sentences of the language for use as a means of general unrestricted communication, does not contain the specification necessary to prohibit the creation by definition of such self-referential sentences that are devoid of both communicative content and meaning.
The traditional view of this paradox as a minor linguistic anomaly was rudely shaken by Russell’s postulation by definition, within Set Theory, of an equally obvious paradoxical set ‘Russell’ whose elements are all, and only, those sets of the Theory that do not belong to themselves.[4]
To the consternation of mathematicians and philosophers, the axioms and logical rules of inference of Set Theory, which governed the construction of sets for use in a more restricted and precise language of mathematical communication, also did not contain the specification necessary to satisfactorily prohibit the creation by definition of such inconsistent entities - now seen to harbour concealed concepts involving unruly infinite sets.
Classically, definitions had been treated as arbitrary assignments of mnemonically convenient names within a language or Theory for expressing complex reasoning in a compact, more readable, and easier to grasp form.
The paradoxes uncovered a hitherto hidden power of definitions to create inconsistent entities within the language or Theory.
6 Gödel’s constructive formal system S
Gödel thus proposed construction of a formal system S with in-built specifications that would prevent the creation of inconsistent entities through unrestricted definition.[5]
He began by rigorously formalising both the logic and Peano’s axioms of the theory of ordinary numbers in an intuitionistically unobjectionable manner[6] that permitted the creation through definition of only finitely constructive[7] entities.
7 Gödel’s arithmetisation of S
Gödel recognised the significance[8] of the fact that, due to the constructive and rigorously formal character of S, the primitive symbols and well-formed formulas[9] of S, together with all finite sequences of such formulas, formed a well-defined denumerable set.
He could thus put these into a well-defined 1-1 Gödel-numbering correspondence with a proper sub-set of the natural numbers[10], which latter were already represented as a denumerable sub-set of formulas (numerals) within S.
8 Gödel’s remarkable insight
With remarkable insight, Gödel
recognised that if y
is the Gödel-number
corresponding to the formula Y, and x the Gödel-number
corresponding to any finite sequence X of formulas Y_{1},
Y_{2}, Y_{3},
…, Y_{n}, then it was possible to constructively define (using recursive arithmetic
functions well-known to mathematicians[11]) a purely numerical relation ‘xBy’ that held if and only if X
was a proof sequence for the formula Y in S[12].
Since ‘xBy’ could clearly be formalised within
S for any
pair of non-negative integers x, y, various meta-statements about S could now be expressed within S.
In an astonishing series of ingenious constructions, Gödel
defined 46 statements of, and meta-statements about, S as purely numerical relations (45 of them recursive)[13]. These could clearly be formalised
within S for any given set of non-negative integer values for the variables contained in them.
9 Gödel’s explicit
thesis
Gödel then postulated in his Theorem V, on the basis of a briefly-sketched argument appealing to induction on the rank of recursive functions[14], the thesis that every recursive function[15] could itself[16] be constructively represented formally as a formula within S in an intuitionistically unobjectionable manner, and so Gödel-numbered.[17]
10 Gödel’s implicit
intuitionist thesis
Now we note that, although the raison d’etre of Gödel’s rigorously defined formal system S lay in the ‘mechanically constructive and intuitionistically unobjectionable nature’ of his meta-reasoning in the meta-theory M of S, reflected strikingly in his arithmetisation of the meta-concept of a formal ‘proof’ in S, Gödel was apparently content to let the ‘mechanically constructive and intuitionistically unobjectionable nature’ of ‘provable’ open formulas (infinitely-compound sentences) of his formal system S remain implicit[18].
The question we now consider is whether Gödel’s formal system S, and its meta-theory M, are as completely defined as needed to reflect Gödel’s explicitly stated ‘mechanically constructive and intuitionistically unobjectionable’ intentions[19].
We therefore see how we can explicitly capture the essence of the ‘constructive and intuitionistically unobjectionable nature’ of the concept implicit in the ‘provability’ of an open formula (infinitely-compound sentence) of S.
One alternative would be to specify as Gödel’s Implicit Intuitionist Meta-thesis, in the meta-theory M of S, that a formula be provable in S if and only if it is provable in S for all non-negative integer (numeral) values of the variables contained in it.
If R(x) is a recursive formula (of a single variable), for
instance, and we denote the meta-statement ‘R(x) is a provable
formula of S’ by
‘├_{S} R(x)’, the above would meta-postulate that :
├_{S} R(x) ≡_{M} (n)├_{S} R(n).[20]
Such a meta-thesis ensures that
the provable open formulas of S, starting with
the axioms of S, translate into
denumerably-many statements under interpretation, i.e. it acts as a meta-axiom
for identifying and determining the denumerable models of S satisfying Peano’s axioms.
We conjecture that the absence of such specification results in the formal system S being inadequately defined, and that this 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 then be denumerable under interpretation.
More importantly in the present instance, we note that 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 within S to the meta-concept ‘├_{S}’ in the meta-theory M of S) - cannot be assumed to be well-defined over an extended, transfinite, range, since these are defined[21] only through an interpretation over the non-negative integers.
Thus we now consider whether Gödel’s definitions and reasoning are valid, and significant, in those interpretations of his formal system S that are denumerable domains, and where some thesis such as Gödel’s Implicit Intuitionist Meta-thesis holds.
11 Gödel’s undecidable proposition
We note that Gödel
next considered the purely numerical recursive relation defined by ‘~ [ x B [ Sb ( y : (19, z(y)) ) ] ]’[22], which held if and only if :
‘The formula (sequence) X, whose Gödel-number is x, is not a proof-sequence[23] in S of the formula (n-ary predicate[24]) obtained from the formula (n-ary predicate) Y, whose Gödel-number is y, when we substitute the numeral z(y)[25] for the formula (free variable) whose Gödel-number is 19[26] in the formula (n-ary predicate) Y whose Gödel-number is y.’[27]
By Gödel’s thesis §9, this relation could be constructively represented formally by some formula (binary predicate) Q within S in an intuitionistically unobjectionable manner, and so Gödel-numbered by some constructible number q.
Applying closure to Q, Gödel
then considered the purely numerical relation defined by ‘(x) [ ~ [ x B [ Sb ( y : (19, z(y)) ) ] ] ]’[28].
If Q is a formula (binary predicate) of S, this relation can be constructively represented formally by some formula (class expression) P within S in an intuitionistically unobjectionable manner, and so Gödel-numbered by some constructible number p.
After suitable substitutions, Gödel finally considered the purely numerical relation defined by ‘(x) [ ~ [ x B [ Sb ( q : (19, z(p)) ) ] ] ]’[29].
If P is a formula (class expression) of S, then clearly this relation can also be constructively represented formally by some formula (sentence[30]) G within S in an intuitionistically unobjectionable manner.
Gödel then showed by simple reasoning that, although the relation defined by ‘(x) [ ~ [ x B [ Sb ( q : (19, z(p)) ) ] ] ]’ clearly holds, G is an undecidable sentence in S since neither G nor ~G are provable in a consistent S.[31]
12 The path Gödel ignored
Following Gödel’s reasoning, we now
consider the purely numerical recursive relation ‘~ [ x B [ Sb ( q : (19, z(q)) ) ] ]’, which holds if and only if :
‘The formula (sequence) X, whose Gödel-number is x, is not a proof-sequence in S of the formula (n-ary predicate) obtained from the formula (binary predicate) Q, whose Gödel-number is q, when we substitute the numeral z(q) for the formula (free variable) whose Gödel-number is 19 in the formula (binary predicate) Q whose Gödel-number is q.’[32]
If Q is a formula (binary predicate) of S, then this relation too can be constructively represented formally by some formula (class expression) R within S, and so Gödel-numbered by some constructible number r.
It is easy now to see that the path Gödel chose diverged at this point by ignoring the Implicit Intuitionist Meta-thesis underlying his reasoning since, by arguments identical to those showing the undecidability of G in S, we arrive at the inconsistency in the meta-theory M of S :
R is provable in S →_{M} R is not provable in S, and
R is not provable in S →_{M} R is provable in S.[33]
13 Was Gödel wrong?
Clearly, if Gödel’s Implicit Intuitionist Meta-thesis holds, then his Theorem V is invalid. Since Gödel did not provide[34] a rigorous proof of his thesis that every recursive function could be constructively represented formally in S in an intuitionistically unobjectionable manner, and so Gödel-numbered, it is not prima facie clear where, or even whether, his reasoning was wrong.
However, his argument ran as follows. If (x+y) is the recursive function of rank two[35] defined by ‘sum(x, 0) ≡ x; sum(x, y+1) ≡ sum(x, y)+1’, then it can be imitated[36] in the formal system S by ‘sum(x, 0) ≡ x; sum(x, Ny) ≡ Nsum(x, y)’, where ‘Nx’ is the successor function[37] of rank one in S.
14 ‘sum(x, y)’
cannot be expressed directly in S
Now, if we define N ^{[y]}0 ≡ y so that, for example, N ^{[}^{3}^{]}0 ≡ NNN0 and ‘sum(x, N^{[y]}0)’ denotes the formal function ‘sum(x, y)’, we see that sum(x, y) ≡ N ^{[y]}x.
For any given k, sum(x, k) is obviously expressible formally in terms of only the primitive symbols ‘N’ and ‘x’ of S. Also, for a given k, the unique Gödel-number r_{k} of the formal expression corresponding to sum(x, k) is r_{k} = 2^{2}. 3^{2}. 5^{2}. 7^{2}. 11^{2}. … p_{k}^{2}. p_{k}_{+}_{1}^{16}, by Gödel’s 1-1 correspondence, where p_{i} is the i’th prime.[38]
However, for a variable y, we clearly cannot express sum(x, y) - or the equivalent N^{[y]}x - in terms of only the primitive symbols of S[39]. Similarly, for a variable y, r_{y }too cannot be enumerated so as to yield a unique Gödel-number r of a formal expression in S that corresponds to sum(x, y).
So a formal expression consisting of only the primitive symbols of S and corresponding to the recursive function ‘sum(x, y)’, i.e. ‘x+y’, cannot be constructively built up[40] from the recursive formal function ‘Nx’ by formally ‘imitating’[41] the operations of substitution or recursive definition within S.[42]
15 Platonist creation through definition
Now Gödel’s thesis was that, from the Gödel-number r_{1}=2^{2}.3^{16} of ‘Nx’[43], one could obtain a unique Gödel-number r for a formal expression consisting of only the primitive symbols of S that corresponds to the formal recursive function ‘sum(x, y)’, where r is constructively defined by the purely formal structure of the formal expression corresponding to ‘sum(x, y)’.[44]
Thus Gödel’s thesis critically depends on the indirect existence through definition[45] of a formal expression in terms of only the primitive symbols of S that is formally equivalent to the formal recursive function ‘sum(x, y)’.
Such existence through definition is strongly reminiscent of the Platonist postulations, and creations by definition, of the anomalous ‘Liar’ sentence and ‘Russell’ set.
Despite the absence of a rigorous proof in his paper in support of his postulation by definition, Gödel, reportedly a ‘…very strong Platonist.’[46], was apparently comfortable[47] that this lacuna in his reasoning would not yield an inconsistency.[48]
Now formal number theory, such as developed in Mendelson[49], does attempt to justify Gödel’s reasoning by using the stratagem of a ‘Gödel β-function’[50]. However, this only permits sequences of determinate, if undetermined, length to be represented by formulas of a formal system S', where addition is an undefined primitive symbol.[51]
Despite Mendelson’s claim - also without a rigorous proof[52] - the Gödel β-function cannot be used to validly construct a formula strongly[53] representing a primitive recursive function, which is essentially an infinite sequence of indeterminate length.
Moreover, as we show in detail in companion papers[54], inconsistencies arise not only in Gödel’s formal system as above, but also in Mendelson’s formal system out of the postulation that every primitive recursive function can be strongly represented in these systems.
17 Why did Gödel choose the path he chose?
The questions arise :
a) How could Gödel overlook straightforward reasoning leading to the kind of inconsistency that he was actually trying to avoid, and which is obvious, and put his faith in, and authority behind, the subtlety of an argument that is anything but obvious?
b) What are the insights that his reasoning has given to a generation of mathematicians, scientists and philosophers, which are so rich and powerful that the obvious remains obscured behind the obscure?
c) Are any of the developments directly or indirectly fueled by Gödel’s work significantly affected - or diminished - if his specific conclusions collapse?
18 Gödel’s Theorems from a wider perspective
There can be no doubt that had Gödel not chosen[55] to focus entirely on and develop the path that he did follow, he would have found the reasoning leading to an inconsistency in his system S. So why did he stray, and stay, off this path?
Considering Gödel’s strongly Platonist philosophy, his interpretation of the significance of his Theorems to scientific thought, which may have influenced the direction he took, could have been that they appeared to him to postulate in principle the existence of abstract entities whose essence cannot be totally grasped by us, in some ‘absolute’ sense, even theoretically.
An obvious parallel would be the development of the various Quantum Theories in Physics, culminating in Schroedinger’s work and Heisenberg’s Uncertainty Principle, postulated about the same time, whose philosophical implications indicated that there exist physical entities whose essence cannot be totally grasped by us, in some ‘absolute’ sense, even theoretically.[56]
However, although Schroedinger’s work and Heisenberg’s postulation continue to be part of the founding bedrock of the physical sciences, and a significant factor in the continuing enquiry as to the relationship between Intelligence and Cosmos, it is debatable whether the postulation of a parallel principle underlying Gödel’s Theorems retains any meaning or content in the absence of a Platonist platform lying beyond personal choice.
19 The relative significance of Gödel’s reasoning
If we assess the significance of the above two anomalous sentences and Gödel’s sentences within their respective disciplines, we see that :
a) ‘The ‘Liar’ sentence is a lie’ can be seen as :
* linguistically significant, since it is a declarative sentence that has a well-defined linguistic ‘form’, but no communicative ‘content’,
* logically significant, since, being neither true nor false, it violates the dictates of a two-valued logic and highlights the essential inconsistency of any ordinary language used as a means of general, unrestricted, communication,
* philosophically significant, since it characterises ‘intelligence’ by the ability to perceive a subjective ‘meaning’ in an objective ‘form’, and to recognize, and ‘meaningfully’ utilise, a sub-language of ‘ordered’ communication whilst operating within an essentially inconsistent ‘disorderly’ language.
b) The sentence ‘The ‘Russell’ set belongs to itself.’ can be seen as :
* mathematically significant, since it can be expressed in a well-defined mathematical ‘form’;
* logically significant, since, being neither true nor false, it violates the dictates of a two-valued logic and highlights the essential inconsistency of unrestricted set theory when used as a means of mathematical communication;
* ontologically significant, since it establishes the power to construct, by postulating through definition the (Platonist?) ‘existence’ of, an inconsistent element[57] in an abstract system;
* philosophically also significant otherwise, since it characterises ‘intelligence’ by the ability to construct and operate consistently within an essentially inconsistent abstract system.
c) Gödel’s assertion that in every formal system S there is a formula G with Gödel-number g which translates as ‘The formula G with Gödel-number g is not provable in S.’ can be seen as :
* logically significant, reflecting an ‘inadequacy’ in definition of the formal system S, and highlighting the role of, and need for, meta-specifications regarding the nature of the permissible range for the variables of the system;
* ontologically significant as this also constructs, by postulating through definition the (Platonist?) ‘existence’ of, an inconsistent element[58] of an abstract system;
d) The fact that there are recursive relations that cannot be represented formally in ‘constructive’ formal systems can be seen as :
* philosophically significant since it indicates that formal-system based Artificial Intelligence (AI) may be limited in its ability to ‘imitate’ natural intelligence.
20 So what does Gödel’s reasoning actually achieve?
Gödel's thesis was that there are true sentences that are expressible formally but not provable. If there are recursive functions that are not expressible formally, Gödel's sentence would still be true, but not necessarily expressible formally, and still not provable. So the collapse of his theorem need not negate his thesis[59] - only his particular proof of it and the part postulating the formal expressibility of every recursive function.
However, his reasoning does establish that there are decidable[60] recursive relations which cannot be constructively expressed formally within a consistent system in an intuitionistically unobjectionable manner.
Can we then conjecture that the development of significant AI may involve the challenge of designing machines with an inconsistent logical basis, and a ‘psycho-cybernetic’ ability to recognise illogical directions, possibly through distributed computing (which raises the question of whether any single entity can develop intelligence)?
21 Addressing Platonism : What is Mathematics?
Regarding the question of ‘existence’ and Platonism, a strikingly curious feature of the paradoxes is that they do not seriously threaten, or even partially paralyse, any of the sciences. They only inconvenience a small body of purists in the logical and ontological area.
Could this be because scientists are unconsciously familiar with their own inconsistent creations, and can co-exist with, and function effectively despite, them! Could the issue of abstract existence really then involve the philosophical question of what, precisely, is Mathematics?
Is Mathematics an abstract Platonist universe in itself, an ‘internal’ one with contents ‘reflecting’ an ‘external’ universe, where the various mathematical disciplines contribute jointly and severally to the contents of this abstract world?
Or, is Mathematics a collection of increasingly precise, increasingly powerful and continuously evolving languages (such as algebra, number theory, etc.), developed ‘internally’ through distinctively different dialects (such as modular forms, analytic methods and summation formulas, etc.), for communicating experiences and content ‘relating’ to an ‘external’ universe?
In practice, at a personal level, it does appear that we address and answer the above queries sub-consciously, and quite inconsistently, reflecting both situational needs and conveniences, determined overall by issues of personal predilection and individual taste.
We appear to opt for the Platonist viewpoint as the more rewarding when we need to ‘internally’ build up a 'mental picture' that we would loosely term as our 'understanding' of mathematical structures within ourselves; the linguistic view where we need or desire to ‘externally’ communicate our 'understanding' and 'vision' to others.
If this is significantly so, do we really need to commit to one over the other? Could our present personal predilections and individual tastes, which strongly determine our individual output and effectiveness but generally reflect powerful influences of the environment we nurture and are nurtured in, be overly biased towards the Platonist viewpoint?.
Could such a bias be detrimental to the unleashing of the full power and potential of individual human creativity - whether in expression or in discovery? Could a bias be addressed and balanced at the ‘system’ level, by balancing the way we approach, follow, practice and teach the various disciplines constituting mathematics?
Instead of addressing the question of what there is classically (i.e. seek the totality of existence in an ‘objective’, absolute abstraction), does Gödel's reasoning indicate that we can as significantly ask the question of how, in a given situation, we should view what there is (i.e. seek only a means of expressing partially, through ‘subjective’, relative abstraction, that which we believe to ‘exist’ externally)?
Although Gödel himself believed that he had significantly established the existence of formally undecidable sentences, does his reasoning actually establish, far more significantly, the limitations of machine intelligence; and does it in fact weaken - if not demolish - the basis for both Platonism and strong AI by giving substance to some of the above queries? [61]
Notes (Why05ct.doc : 4/7/01 7:17:17 AM)
[1] That Gödel intention of reasoning in a ‘mechanically constructive and intuitionistically unobjectionable’ way requires the range of the variables of the formal system S to be denumerable under interpretation is reflected here. [Gödel 1931: p6]
[2] Such as Russell and Whitehead’s attempt to equate mathematics and logic in their monumental work Principia Mathematica.
[3] Is the ‘Liar’ sentence true or false?
[4] Is the ‘Russell’ set a member of the ‘Russell’ set?
[5] Gödel developed the formal system S as ‘ … 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 : p10]
[6] i.e. without use, vaguely speaking, of existence proofs such as arguments that depend, for example, on the use of the Law of the Excluded Middle. [Gödel 1931 : p26 footnote 45a]
[7] i.e. entities constructible by a finitely terminating procedure. [Gödel 1931 : p26 footnote 45a].
[8] See also Anand 2000 : chapter 4.
[9] Gödel defined 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.
[10] Gödel
described 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]
[11] ‘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(x_{1}, x_{2}, … , x_{n})
is called recursive if there exists a recursive function φ(x_{1}, x_{2}, … , x_{n})
such that, for all x_{1}, x_{2}, … , x_{n}, R(x_{1}, x_{2}, … ,
x_{n}) ≡ [φ(x_{1}, x_{2}, … , x_{n})
= 0 ].’ [Gödel
1931 : p14-15]
[12] [Gödel 1931 : p22-definition 45]
[13] [Gödel 1931 : p17-22-definitions 1- 46]
[14] [Gödel 1931 : p23]
[15] Such as ‘xBy’.
[16] As distinct from expressions such as ‘aBb’ that it yielded for any set of numerical values a, b of the variables contained in it, which are clearly representable formally as formulas within S in a constructive and intuitionistically unobjectionable manner,
[17] ‘For every recursive relation R(x_{1}, … , x_{n}) there is an n-ary PREDICATE r (with the FREE VARIABLES u_{1}, … , u_{n}) such that, for all n-tuples of numbers (x_{1}, … , x_{n}), we have :
R(x_{1},
… , x_{n}) ® Bew [Sb ( r : ( (u_{1}, z(x_{1})), … , (u_{n}, z(x_{n})) ) )]
~ R(x_{1},
… , x_{n}) ® Bew [Neg Sb ( r : ( (u_{1}, z(x_{1})), … , (u_{n}, z(x_{n})) ) )]’. [Gödel
1931 : p22]
Gödel noted that his Theorem V above is a 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]
[18] [Gödel 1931: p6]
[19] [Gödel 1931 : p26 footnote 45(a)]
[20] By Gödel’s thesis in his Theorem V, if r is the Gödel-number of the class expression R(x), and 17 is the Gödel-number assigned to x, this meta-postulate can be formally expressed in S as the formal expression of the relation ‘Bew r ≡ (n) Bew [Sb ( r : (17, z(n)) )]’. In this paper, we show that if ‘Bew r ≡ (n) Bew [Sb ( r : (17, z(n)) )]’ holds, then Theorem V does not hold, and argue that the validity of Theorem V has not been unequivocally established by either Gödel or current Formal Number Theory.
[21] [Gödel 1931: p14 footnote25]
[22] [Gödel 1931 : p24 (8.1)]
[23] We define 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]
[24] ‘…
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]
[25] The numeral
z(y) being recursively defined to be the
formal representation of the integer y in S
[Gödel
1931 : p19 definition 17]
[26] In Gödel’s particular arithmetisation in the cited paper, each variable in a formula could be arbitrarily, but uniquely, correlated to some prime number > 13. [Gödel 1931 : p13]
[27] In Gödel’s
terminology, the recursive arithmetical relation Q would actually translate more
accurately 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]
[28] [Gödel 1931 : p25 (11)]
[29] [Gödel 1931 : p25 (12)]
[30] ‘A sentence is a formula in which no free variables occur …’ [Gödel 1931 : p11]
[31] [Gödel
1931 : p25-26]
[32] This relation, and the class expression R representing it in S, are, in a sense, closer, and more natural, reflections of the ‘Liar’ sentence than Gödel’s sentence G.
[33] This argument is expanded upon in the accompanying paper ‘Why did Gödel ignore this reasoning?. For a more detailed and mathematically rigorous symbolic exposition of the simple reasoning leading to this contradiction see Anand 2000 : chapter 5. However, the possible source of Gödel’s error was misleadingly based there on a misunderstanding of his definition of the ‘rank’ of a recursive function - as pointed out by Professor Rohit Parikh, of the City University of New York, in correspondence with the author. This has been suitably amended in the present papers.
[34] See note 44 below.
[35] Functions of rank one being constants and the successor function x+1. [Gödel 1931 : p23]
[36] [Gödel 1931 : p23]
[37] [Davis 1965 : p46]
[38] We use here the Gödel-numbering system as defined by Gödel in Davis 1965 : p53.
[39] What we have shown here is that although §3(b) does define a formal recursive function ‘sum(x, y)’ of S, this function cannot be directly expressed as a formal expression in S in terms of only the primitive symbols of S.
[40] Dr. Chetan Mehta first pointed this out to the author in private correspondence.
[41] [Gödel
1931 : p23]
[42] Thus, though the function ‘Nx’ is a formal expression of S and easily Gödel-numbered, a recursive definition of the form of the function ‘sum(x, Ny)’ is essentially self-referential. Clearly, the form of ‘sum(x, Ny)’ - as represented by some formal expression of S and distinct from its recursively defined formal value - is Gödel-numberable if and only if the form of the function ‘sum(x, y)’ - as represented by some formal expression of S - is Gödel-numberable.
[43] We use here the Gödel-numbering system as defined by Gödel in Davis 1965 : p53.
[44] We note that Gödel here assumed the constructibility of such a Gödel-number r without proof. Thus he remarked that ‘… when this proof is rigorously carried out, r will naturally not be defined by this shortcut through the intuitive interpretation, but rather by its purely formal structure.’ [Gödel 1931 : p22 footnotes 38 and 41]
[45] In the absence of a rigorous proof, Gödel’s conclusion appears to be based on the intuitive belief that since every recursive definitional procedure yielding numerical values could be formally imitated to yield a formal recursive definitional procedure that yields corresponding formal numeral values in S, hence every recursive definition must be formally representable within S.
[46] [Penrose 1990 : p147]
[47] Although Gödel did, perhaps, have some reservations about the validity of his argument and conclusion, for he noted in subsequent lectures that ‘ … this proof is not necessary for the demonstration of the existence of undecidable arithmetic propositions in the system considered. For, if some recursive function were not ‘represented’ by the corresponding formula constructed on pages 58-59, this would trivially imply the existence of undecidable propositions unless some wrong proposition on integers were demonstrable’. [Davis 1965 : p59 footnote 21]
[48] Perhaps since he depended on Whitehead and Russell’s ‘… theory of types as our means for avoiding paradox.’. [Davis 1965 : p46]
[49] [Mendelson 1964 : chapter 3, p102]
[50] [Mendelson 1964 : chapter 3, p131]
[51] Strictly speaking, Mendelson’s Gödel β-function cannot even be defined in Gödel’s formal system S, since addition is not a primitive symbol of S, and itself needs recursive definition.
[52] [Mendelson 1964 : p134]
[53] [Mendelson 1964 : p118]
[54] ‘Is Gödel’s Platonist creation through definition valid?’, ‘Why did Gödel ignore this reasoning?’ and ‘Is Mendelson’s use of the Gödel β-function valid?’.
[55] A case could be made out - and probably will be made out, both by critics in the immediate future and by more serious students of various disciplines in a suitably distant future - that Gödel not only knew of the inconsistency, but deliberately chose to ignore - if not consciously suppress - it. Perhaps he did, and perhaps he was guilty on all counts in this respect wherever he can be held to account. More rewarding issues to be addressed in this area, however, would be :
a) Did Gödel choose not to follow that path as he instinctively felt the one he did choose would lead to more fruitful and rewarding developments of path-breaking concepts needed for the mathematicians, scientists and philosophers of the day?
b) Did Gödel feel that arriving at an inconsistency or other similarly definitive results would have distracted him from, and perhaps diminished the significance of, the revolutionary ideas that were becoming visible to him in his particular choice - even if history were to disprove his specific conclusions?
c) If so, would Gödel’s
instincts stand vindicated, since his remarkable new ideas and concepts have
triggered and sustained the dynamic growth of mathematical, scientific and
philosophical debates on wide-ranging and esoteric subjects (as is visible
most vividly on the Internet in the various dialogues generated by Douglas
Hofstadter’s popularisation of Gödel’s Theorems in his book ‘Gödel, Escher and Bach’)?
[56] This possibly has had a significant influence on the almost-instant receptivity and continuing acceptance of the content, import and validity of Gödel’s Theorems by scientists of various disciplines over the years, without the accompanying impulse for aggressively critical, and exhaustively microscopic, examination, verification and substantiation that such a startling thesis normally would attract.
[57] Somewhere between ‘Pegasus’ and a ‘square circle’.
[58] Equivalent to the postulation of a ‘square circle’.
[59] As detailed in note 47 above, this was noted by Gödel himself.
[60] In the sense of [Gödel 1931 : p23 footnote 39]. It is a curious fact that although Gödel considered this possibility, as detailed in note 47 above, he chose not to develop it further explicitly.
[61] This question presumes some acceptable degree of agreement on what would constitute both ‘AI’ and ‘strong AI’.
◄ 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)