Roger Penrose's book Shadows of the Mind may be purchased
from Amazon.Com

Penrose's Gödelian Argument
A Review of Shadows of the Mind by Roger Penrose


Solomon Feferman
Department of Mathematics
Stanford University
Stanford, CA 94305-2125
U.S.A.

sf@csli.stanford.edu

Copyright (c) Solomon Feferman 1995

PSYCHE, 2(7), May 1995
http://psyche.cs.monash.edu.au/v2/psyche-2-07-feferman.html

KEYWORDS: Gödel incompleteness theorems, Turing machines, consistency statements, ordinal logics, proof theory, Platonism.

REVIEW OF: Roger Penrose (1994) Shadows of the Mind. New York: Oxford University Press. 457 pp. Price: $25.00. ISBN 0-19-853978-9.

1. Penrose Redux

1.1 In his book Shadows of the Mind [SOTM below], Roger Penrose has turned in another bravura performance, the kind we have come to expect ever since The Emperor's New Mind [ENM] appeared. In the service of advancing his deep convictions and daring conjectures about the nature of human thought and consciousness, Penrose has once more cut a wide swath through such topics as logic, computation, artificial intelligence, quantum physics and the neurophysiology of the brain. Moreover, along the way, without condescension, he has done a brilliant job of explaining difficult mathematical and scientific ideas in a broadly appealing fashion <1>. While the aims and a number of the topics in SOTM are the same as in ENM, the focus here is much more on the two axes Penrose grinds in earnest. Namely, in the first part of SOTM he argues anew and at great length against computational models of the mind and more specifically against any account of mathematical thought in computational terms. Then in the second part, he argues that there must be a scientific account of consciousness but that it will require a (still to be found) non-computational extension or modification of present-day quantum physics.

1.2 I am only competent to say something substantive about the first part of the new effort, resting as it does to a considerable extent on a version of Gödel's (first) incompleteness theorem. Penrose had advanced that previously in ENM, but the line of argument was much criticized, as it had been in the past when advanced by others (e.g. J.R. Newman and E. Nagel, and J.R. Lucas) <2>. So now Penrose has gone to great lengths in SOTM to lay out his Gödelian argument and to try to defend it against all possible objections. I must say that even though I think Gödel's incompleteness theorems are among the most important of modern mathematical logic and raise fundamental questions about the nature of mathematical thought, and even though I am convinced of the extreme implausibility of a computational model of the mind, Penrose's Gödelian argument does nothing for me personally to bolster that point of view, and I suspect the same will be true in general of readers with similar convictions. On the other hand, I'm sure that those whose sympathies lie in the direction of a computational model of mind will find reasons to dismiss the Gödelian argument quickly on one ground or another without wading through its painful elaboration. If I'm right, this effort -- diligent as it is -- is largely wasted. Nevertheless, since Penrose has done it, I feel obliged to address at least the more technical aspects of his argument.

1.3 While I have disavowed competence concerning Part II of SOTM, I can't help registering my impression that the effort there is entirely quixotic. What Penrose aims to do is substitute one "nothing but" theory for another: in place of "the conscious mind is nothing but the action of a computer" he wishes to have "the conscious mind is nothing but the manifestation of sub-atomic physics". Can we really ever expect a completely reductive theory of one sort or another of human cognition? Surely, no one theory will serve to "explain" the myriad aspects of this phenomenon. As with any other scientific study of human beings -- inside and out -- such an enterprise will need to continue to make use of psychology, psycho-physics, physiology (neuro- and otherwise), biochemistry, molecular biology, physics (macro- and micro-) and who knows what all else (including computational models of all kinds). In my opinion Penrose's "missing science of consciousness" is a mirage.

2. The Logical Facts

2.1 While Penrose's formulation of Gödel's theorem is by itself unexceptionable, his subsequent discussion of it -- especially in relation to Gödel's own formulation and various of its generalizations -- is unfortunately marred by a number of errors. I assume here some familiarity with mathematical logic and the relevant material from Kleene (1952); the reader who does not have that familiarity should skim the following before proceeding to the next section of this review. Unless otherwise indicated, pagination or section references (e.g. '2.5') are to SOTM.

2.2 Penrose's form of Gödel's incompleteness theorem is stated in terms of Turing machine computations as follows (pp. 74-75):
Theorem 1: Suppose A is a Turing machine which is such that whenever A halts on an input (q,n) then C_q(n) does not halt. Then for some k, C_k(k) does not halt, yet A does not halt on (k,k). In other words, if the halting of A is a sufficient condition for the non-halting of Turing machines then it is not a necessary condition for that; still more briefly: soundness of A implies incompleteness of A.
2.3 The proof of Theorem 1 is just a variant of the standard diagonal argument, originating with Turing in 1937, that the halting problem for Turing machines is not effectively decidable. As a form, though, of Gödel's incompleteness theorem, it is very close to Kleene's generalized form of that result, established in 1943 and exposited in Kleene (1952) p. 302 as Theorem XIII. That makes use of a very general notion of formal system F, the main condition for which is that the set of "provable formulas" is effectively enumerable. Suppose in particular that F contains effectively given "formulas" phi(q,n) which are supposed to "express" the predicate P(q,n) which holds just in case C_q(n) does not halt. F is said to be sound or correct for P if whenever F proves phi(q,n) then P(q,n) holds, and it is said to be complete for P if the converse is true. In slightly weakened form, Kleene's theorem (loc. cit.) is then as follows:
Theorem 2: If F is a formal system (in the general sense) which is sound for the predicate P then it is not complete for it. In particular, there is a k such that C_k(k) does not halt though F does not prove phi(k,k).
2.4 Assuming Church's Thesis, Theorem 2 follows Theorem 1, since every recursively enumerable set of pairs (q,n) is the same as the set of inputs on which a Turing machine halts. Conversely, to obtain Theorem 1 from Theorem 2, simply take the "formula" phi(q,n) to be the pair (q,n) and the set of "provable formulas" of F to be the set of pairs on which A halts.

2.5 We must now examine the relationship of these results with the usual formulation of Gödel's incompleteness theorems. Here we deal with formal systems in the logical sense, i.e. systems F whose formulas are built up from basic arithmetical (and possibly other) relations by means of the propositional connectives and quantifiers and whose provable formulas are obtained from a given set of axioms (both logical and non-logical) by closing under certain rules of inference. Moreover, F is assumed to be effectively given, i.e. the set of axioms of F and its rules of inference are supposed to be effectively decidable, so that its set of provable formulas is effectively enumerable. Finally, F is supposed to be "sufficiently strong", i.e. contain a modicum F_0 of elementary number theory (or arithmetic). Over the years, the statement of Gödel's incompleteness theorems has been steadily strengthened by a steady weakening of what is assumed for F_0. In 1931, Gödel had taken it to be a version of simple type theory over a number-theoretical base, but he soon weakened that to a form of the first-order system of Peano Arithmetic PA. Subsequently, for Gödel's first incompleteness theorem, this was further weakened considerably to R.M. Robinson's fragment Q of arithmetic, and for the second incompleteness theorem to the subsystem Sigma_1-IA of PA based on induction applied only to Sigma_1 formulas. For details, see Gödel's 1931 and related papers in the original and in translation, with an introductory note by Kleene, in Gödel (1986), pp. 126ff, and the expositions in Kleene (1952), pp. 204-213 and Smorynski (1977). For simplicity, we assume throughout the following that F_0 is PA, and that F is an (effectively given) formal system in the logical sense which contains PA.

2.6 As Penrose notes, the class of PI_1 formulas is of special significance in connection with the Gödel theorems. These are ones of the form $forall(x) R(x)$, where R expresses an effectively decidable (recursive) property of the natural numbers and the intended range of 'x' is the set of natural numbers. Dual to this class is the class SIGMA_1 of formulas of the form $exists(x) S(x)$ where S is effectively decidable; in classical logic, these are equivalent to negations $not forall(x) not S(x)$ of PI_1 formulas. We may consider similarly PI_1 and SIGMA_1 formulas with free variables such as $forall(y) R(x,y)$ and $exists(y) S(x,y)$ with decidable R, S, resp.

2.7 The following examples are particularly relevant to the Gödel theorems:

(i) We have a decidable relation Proof_F(x,y) which expresses that y is (the Gödel number of) a proof in F of the formula (with number) x; then

(ii) the SIGMA_1 formula Prov_F(x):=$exists(y) Proof_F(x,y)$ expresses that the formula (with number) x is provable in F, while the PI_1 formula $forall(y) not Proof_F(x,y)$ expresses that x is not provable in F; in particular,

(iii) if c is the number of the formula $0=1$, the PI_1 formula Con(F) := $forall(y) not Proof_F(c,y)$ expresses that F is consistent. Next, (following Kleene), we have

(iv) a decidable relation T(z,x,y) which expresses that y is (the number of) a terminating computation at input x on the Turing machine C_z; so

(v) the SIGMA_1 formula $exists(y) T(z,x,y)$ expresses that C_z(x) halts, and

(vi) the PI_1 formula $forall(y) not T(z,x,y)$ expresses that C_z(x) does not halt; in particular,

(viii) for each k, the PI_1 sentence $forall(y) not T(k,k,y)$ expresses that C_k(k) does not halt.

2.8 The system F is said to be sound for a class S of sentences if whenever F proves phi with phi in S then phi is true in the structure N of natural numbers; F is said to be complete for the sentences in S if the converse holds. F is said to be omega-consistent if there is no formula phi(x) such that F proves $not phi(n)$ for each natural number n, and yet F proves $exists(x) phi(x)$. It is said to be 1-consistent if this condition holds for decidable phi. It is obvious that if F is omega-consistent then it is 1-consistent, and that in turn implies that it is consistent, since an inconsistent system proves all formulas. Under our general assumption that F is sufficiently strong (i.e. contains PA as a subsystem), we have:
Lemma 3: (i) F is complete for SIGMA_1 sentences. (ii) F is 1-consistent if and only if F is sound for SIGMA_1 sentences. (iii) F is consistent if and only if F is sound for PI_1 sentences.
2.9 The idea for the proof of (ii) is that if F is 1-consistent and proves $exists(x) S(x)$ where S is decidable then there must exist an n such that S(n) holds, since otherwise we could prove $not S(n)$ for each n. The converse is immediate by definition. The idea for the proof of (iii) is that if F is consistent and proves $forall(x) R(x)$ with R decidable, then for each n, F proves R(n), hence R(n) must be true, for otherwise $not R(n)$ would be provable in F as a special case of (i).

2.10 The result (iii) of Lemma 3 is a fundamental observation due to Hilbert, since it shows that any success of his consistency program for a system F would establish the correctness of F for the "real" (i.e. PI_1) sentences.

2.11 For his completeness results, Gödel constructed a PI_1 sentence G(F) equivalent (in PA) to $forall(y) not Proof_F(g,y)$, where g is the Gödel number of G(F). Thus G(F) provably expresses of itself (via its Gödel number) that it is not provable in F.
Theorem 4. (Gödel's 1st incompleteness theorem).
(i) If F is consistent then G(F) is not provable in F.
(ii) If F is omega-consistent then $not G(F)$ is not provable in F.
2.12 Now the hypothesis in (i) is equivalent by Lemma 3 to the soundness of F for PI_1 sentences, and since under this hypothesis the sentence $forall(y) not Proof_F(g,y)$ is true and hence G(F) is true, we conclude from the first part of the 1st incompleteness theorem that:
Corollary 5. If F is sound for PI_1 sentences then F is not complete for them.
2.13 In this form, the first part of Gödel's 1st incompleteness theorem is of the same character as Theorem 1 (Turing-Penrose) as well as Theorem 2 (Kleene). Note that the hypothesis of the second part of Theorem 4 can be replaced immediately by the assumption that F is 1-consistent. For if $not G(F)$ is provable in F then so also is $exists(y) Proof_F(g,y)$. But that sentence is false by the first part of the theorem. Note also that if $not G(F)$ is added to F as an axiom, and F is consistent, the resulting system is still consistent (by the first part of Theorem 4) but not 1-consistent, hence not omega-consistent.

2.14 In 1937, Rosser constructed a PI_1 sentence R(F) which is such that if F is consistent neither R(F) nor $not R(F)$ is provable in F. However, R(F) is less useful than G(F), as the following shows:
Theorem 6. (Gödel's 2nd incompleteness theorem).
(i) PA proves $Con(F) -> G(F)$.
(ii) Hence, if F is consistent then F does not prove Con(F), i.e. F does not prove its own consistency.
2.15 The idea of a proof of $Con(F) -> G(F)$ in (i) is to formalize in PA the proof of the first part of the 1st incompleteness theorem. The converse, that $G(F) -> Con(F)$, is trivial, since if any sentence is not provable in F then 0=1 is not provable in F.

3. Penrose's (Mis)treatment of the Logical Facts

3.1 After this extensive, but, as we shall see, necessary excursus, we can finally return to Penrose's SOTM.

3.2 pp. 74-75 (sec. 2.5). The idea of a computational procedure A being sound is explained here by the statement that if A halts on input (q,n) then C_q(n) does not halt. As we have seen, the conclusion is equivalent to the PI_1 sentence $forall(y) not T(q,n,y)$, and soundness of A is a special case of soundness of a formal system for PI_1 sentences. However:

3.3 pp. 90-92 (sec. 2.8). In Penrose's account of Gödel's incompleteness theorem, he says (p. 91) that if a formal system is sound then "it is certainly omega-consistent". This is a different notion of soundness from that on pp. 74-75, since omega-consistency is stronger than consistency, i.e. than soundness for PI_1 sentences. Penrose does not explain here what is meant by this new notion of soundness, but implicit in what he says is soundness for all (arithmetical) sentences [cf. the discussion of p. 112 below]. At any rate, the notion of soundness required for Penrose's further discussion is ambiguous between that of pp. 74-75 and that of p. 91.

3.4 Next on p. 91, Penrose introduces the notation 'Omega(F)' for the [formal] assertion that the system F is omega-consistent. He says that "Gödel's famous incompleteness theorem tells us that Omega(F) is not a theorem of F... provided that F is actually omega-consistent." As we have seen, Gödel's 2nd incompleteness theorem tells us that Con(F) is not a theorem of F provided F is simply consistent, a fortiori Omega(F) is not a theorem of F under the same conditions. The hypothesis of omega-consistency of F (or its weakening, 1-consistency) is needed only if we want also to conclude that $not Con(F)$ (or equivalently, $not G(F)$) is not a theorem of F.

3.5 Penrose further says here that he will use the notation 'G(F)' for the [formal] assertion that F is consistent. He then says that Rosser's theorem tells us that if F is consistent then G(F) is not a theorem of F; but that is what Gödel's 2nd incompleteness theorem tells us, not Rosser's. Penrose further muddies the picture by saying that he will "not bother to draw a clear line between consistency and omega-consistency" in most of his discussions, but that "the version of the Gödel theorem that I [Penrose] have actually presented in section 2.5 is essentially the one that asserts that if F is omega-consistent, then it cannot be complete, being unable to assert Omega(F) as a theorem." Instead, as we have seen, what he showed in section 2.5 is a version of the first part of Gödel's incompleteness theorem, that if F is sound for PI_1 sentences [-> consistent] then G(F) is not a theorem of F.

3.6 On p. 92, Penrose says that in order to discuss the actions of Turing machines, F must contain the minimum operator (mu) symbol. It is true that, in Kleene's normal form theorem, the value of C_q(n) is of the form U(mu y.T(q,n,y)) when $exists(y) T(q,n,y)$ holds; but the statement of halting or non-halting of C_q(n) does not require the explicit presence of mu among the symbols of F.

3.7 p. 96. It is stated here that "...both Omega(F) and G(F) are PI_1 sentences." This is correct for G(F) but not for Omega(F) which is, instead, a sentence in PI_3 form, i.e. of the form $forall(x) exists(y) forall(z) R(x,y,z)$ with R decidable [work it out]. Even 1-consistency is a PI_2 sentence, which is not equivalent to a PI_1 sentence.

3.8 p. 108. Penrose says here that if F* and F** are obtained from F by adjoining G(F) and $not G(F)$ resp. as axioms, and if F is consistent then F* and F** are both consistent. This is correct for F** by ordinary logic, but not for F*. The following is a counter-example: let F be obtained from PA by adjoining $not G(PA)$ or, equivalently, $not Con(PA)$ as an axiom. Thus F is PA** in Penrose's notation, and so F is consistent. But in this case, since F* includes $Con(F)$ and PA is contained in F, we have that F* proves $Con(PA)$, so F* is inconsistent. What is needed to insure that F* is consistent is the assumption that F is 1-consistent (which is not the case for F=PA**); as it happens, it can be shown that if F is 1-consistent so also is F*.

3.9 pp. 109-110. The discussion of the non-categoricity of the first-order version of PA of Peano's axioms vs. the categoricity of the second-order version of those axioms is misleading since it lumps together first-order quantification with second-order quantification. What the latter does is allow one to quantify over properties P in the induction axiom, namely as $forall(P) [P(0) and forall(x) (P(x) -> P(Sx)) -> forall(x) P(x)]$. However, Penrose is right in saying that for this second-order axiom to guarantee categoricity we need to regard it semantically, i.e. to interpret the variable 'P' in 'forall(P)' as ranging over arbitrary subsets of the first-order domain of interpretation, and there is no effective formal system complete for this semantics (by Gödel's incompleteness theorem).

3.10 p. 112. In the discussion of Q18 it is asserted that we cannot "properly encapsulate 'soundness' or 'truth' within any formal system -- as follows by a famous theorem of Tarski". This settles definitely the earlier ambiguity between the notions of soundness used on pp. 74-75 and that of p. 91, i.e. here soundness is taken as truth of all sentences (at least all arithmetical ones); then Tarski's theorem on the non-definability of truth certainly applies provided the system F under consideration is consistent. Penrose goes on to say that for restricted notions of soundness we can prove in F, or even PA, that if F is sound then G(F) holds. In particular, he says that PA proves $Con(F) -> G(F)$. This is strange, because on p. 91 he said that he will use 'G(F)' for the formal statement that F is consistent, i.e. for 'Con(F)': but for that identification the implication is trivial. The implication $Con(F) -> G(F)$ is only of interest if one takes G(F) to be Gödel's sentence that expresses of itself that it is not provable in F (cf. Theorem 6(i) above). The next strange statement on p. 112 is that one can prove that 'F omega-consistent' implies 'Omega(F)', since on p. 91 Penrose defined Omega(F) to be the formal statement of the omega-consistency of F; on that identification the implication is once more trivial.

3.11 p. 114: The description of my results on Turing's ordinal logics is incorrect. First of all, the reference given is to Feferman (1988), which contains a historical exposition of Turing's seminal work (1939) and subsequent work on this subject (under the new name, transfinite recursive progressions of formal systems). The appropriate reference for my own original work there should have been Feferman (1962). It was Turing (not me) who showed in his 1939 paper that the ordinal logic obtained by iteration of adjunction of consistency statements starting with PA and proceeding through the recursive ordinals is complete for PI_1 statements (in fact at a surprisingly low level); Turing had hoped to improve this to completeness for PI_2 sentences. In my 1962 paper I proved that: (i) Turing's ordinal logic is incomplete for PI_2 sentences; (ii) the same holds for progressions based on transfinite iteration of the so-called local reflection principle; but (iii) one obtains completeness for all arithmetical sentences in a progression based on the transfinite iteration of the so-called global or uniform reflection principle. However, the following comments by Penrose about the significance of Turing's and my work are correct: "...there is no algorithmic procedure that one can lay down beforehand which allows one to do this systematization for all recursive ordinals once and for all", and that "...repeated Gödelization...does not provide us with a mechanical procedure for establishing the truth of PI_1 sentences."

3.12 I have not detailed all the occurrences of technical errors that Penrose makes in connection with Gödel's incompleteness theorems in Ch. 2, many of which also propagate through Ch. 3. Given the weight that Penrose attaches to his Gödelian argument, all these errors should give one pause. One has here lots more of the "slapdash scholarship" that Martin Davis complained about in his commentary on ENM (1993, p.116), and they suggest that Penrose may stretch that scholarship perilously thin in areas distant from his own expertise. The main question, though, is whether these errors undermine the conclusions that he wishes to draw from the Gödelian argument. I don't think that they do, at least not by themselves. That is, I think that the extended case Penrose makes from section 2.6 on through the end of Ch. 3 would be unaffected if he put the logical facts right; but the merits of that case itself are another matter.

4. What Follows From Gödel's Incompleteness Theorem?

4.1 Here I shall be less systematic in tracking Penrose. It must be emphasized again that what his case really rests on is the first half of Gödel's 1st incompleteness theorem (Theorem 4(i) above)-- that if a suitably strong formal system F is consistent then the PI_1 sentence G(F) is not provable in F -- combined with Hilbert's observation (Lemma 3(iii) above) that F is consistent if and only if F is sound for PI_1 sentences. Finally, we have by Gödel's 2nd incompleteness theorem (Theorem 6 above) that G(F) is equivalent in a base system (e.g. PA) to Con(F). The omega-consistency of F and statement Omega(F) are simply red herrings for Penrose's argument and should be ignored.

4.2 The reformulation of incompleteness in terms of Turing machines in section 2.5 is of course important if one is to argue that mathematical thought is not mechanical, but it is just a reformulation as Penrose brings out: every theorem-generating machine can be recast as a formal system and vice-versa. However, it is the model of mathematical thought in term of formal systems that is closer to the nature of that thought itself, i.e. to its concepts and modes of reasoning. What is misleading in the equivalence between Turing machines and formal systems is the way theorems are actually obtained in the working experience of mathematicians. On the algorithm model, one starts with an input (q,n) on machine A in an effort to establish that C_q(n) does not halt, i.e. one starts with the "statement" possibly to be established and plugs away mechanically following the algorithm that determines A in the hopes that it will end by "proving it". The analogue for a formal system F would be to start with a statement phi, possibly to be established, and mechanically generate, one after another, all proofs in F, looking to see if one of them ends with phi. But it would be ridiculous to think that anything like such a search through proofs takes place in the activity of working mathematicians. How it is that they actually arrive at proof is through a marvelous combination of heuristic reasoning, insight and inspiration (building, of course, on prior knowledge and experience) for which there are no general rules, though some patterns have been discerned by Polya and others: there is no formula for mathematical success. It is only when one finally arrives at a proof that one can check (mechanically, in principle, but not in practice) that it does indeed establish the theorem in question.

4.3 So on the face of it, mathematical thought as it is actually produced is not mechanical; I agree with Penrose that in this respect, understanding is essential, and it is just this aspect of actual mathematical thought that machines cannot share with us. Beyond that, his entire drive is to nail down this conviction by showing that mathematical thought cannot even be re-represented in mechanical terms, as a result of the Gödel theorem. In my view, instead of increasing this conviction, this effort raises more questions than it answers and leads into dead-end dialectics. Here are some reasons.

4.4 Penrose begins by stating as the main conclusion G from the Gödel-Turing incompleteness theorem: "Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth" (p. 76). More specifically, in terms of formal systems: if mathematicians can come to know that a system F is sound, then F cannot be used to ascertain the truth of the true PI_1 statement G(F). Now, as I have noted, there is an ambiguity in Penrose's use of the notion of soundness between that for PI_1 sentences and that for all sentences. All that the Gödel incompleteness theorem requires of F is the former, since that is equivalent to the consistency of F. But Penrose tends to emphasize the global notion of soundness and to tie it to his Platonistic philosophy of mathematics. The argument goes something as follows: how could we know that F is sound if we did not understand what F is about -- its intended interpretation -- and see that the axioms of F are all true of that interpretation and that its rules of inference all preserve truth? It is by such means, the argument continues, that we recognize the soundness of systems from PA all the way up to ZF set theory and beyond. And once we recognize the soundness of a system F and accept it as part of the principles on which we can rely, we see that G(F) is true and must accept it too, and so by Gödel's theorem, we are required to accept something that goes beyond F.

4.5 Two problems with this argument are that (i) there may be other ways of recognizing the truth of G(F) than through a global notion of truth for F, and (ii) the assumption of an intended interpretation for set-theoretical formalisms is highly problematic. The first is what is achieved by proof theory. While it is generally agreed that Hilbert's program to establish the consistency of stronger and stronger formal systems by purely finitary proof-theoretical methods cannot be carried through as a result of Gödel's 2nd incompleteness theorem, a relativized form of Hilbert's program has been successful by these means (cf. Feferman (1988a)). Relativized proof theory yields verification of the consistency of a system F by reduction to the consistency of another system F', and progress is achieved thereby when one has more compelling reasons for accepting F' than F to begin with. In particular, various prima-facie non-constructive systems have been reduced in this way to constructive systems, and systems of analysis based on impredicative set-existence principles have been reduced to predicative systems. Indeed, it has been shown that the bulk of everyday mathematics can be formalized in such relatively weak systems, and it appears that all of scientifically applicable mathematics can be formalized in a system which is proof-theoretically reducible to PA (cf. Feferman (1993)). While mathematicians may conceive of what they are talking about in Platonistic set-theoretical terms, these results show that such a conception is not necessary to secure confidence in the body of mathematical practice.

4.6 Moving on to the philosophical issues raised by Platonism in set theory, Penrose is right in identifying Gödel as one of the foremost proponents of this position. However, I think it is fair to say that he has few adherents among philosophers of mathematics. Admittedly, every overall philosophy of mathematics has its difficulties, but Penrose make it seem that the Platonistic position is a matter of common consensus. This is not the case for those who have given these questions more than token attention. While one may well agree that questions of truth in the natural numbers are of a determinate character, already the assumption of a supposed definite totality of arbitrary sets of natural numbers is highly problematic. Indeed, Gödel himself, at least for a period in the 1930s, found this deeply troubling. In a previously unpublished lecture (*1933o in Gödel (1995)), he said that: "The result of the preceding discussion is that our axioms [for set theory], if interpreted as meaningful statements, necessarily presuppose a kind of Platonism, which cannot satisfy any critical mind and which does not even produce the conviction that they are consistent." (op.cit. p. 50). And Gödel continued to take proof-theoretical approaches to consistency seriously throughout his life (see also *1938a in Gödel (1995) and the introductory notes to that and *1933o). Incidentally, on p. 116 of SOTM, Penrose says that Paul Cohen, in the last section of his 1966 book on the independence of AC and CH from ZF set theory "reveals himself to be, like Gödel [and Penrose] a true Platonist for whom matters of mathematical truth are absolute and not arbitrary." While that is a reasonable inference from what Cohen said there, shortly after that, at a 1967 conference, he stated: "By now it may have become obvious that I have chosen the Formalist [as opposed to the Platonic Realist] position for set theory" (Cohen 1971, p. 13). As far as I know, that is still his view.

4.7 Penrose reports in section 3.1 on what Gödel took the significance of his incompleteness theorems to be, via a quotation which had circulated some time back from Gödel's unpublished Gibbs lecture of 1951. That piece is now available in full as *1951 in Gödel (1995), with an illuminating introductory note by George Boolos. More cautious than Penrose, Gödel there comes to the conclusion that "either...the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable diophantine problems." (op.cit., p. 310). Boolos' discussion of this is tonic:
"There is a gap between the proposition that no finite machine meeting certain weak conditions can print a certain formal sentence (which will depend on the machine) and the statement that if the human mind is a finite machine, there exist truths that cannot be established by any proof the human mind can conceive.... it is certainly not obvious what it means to say that the human mind, or even the mind of some one human being is a finite machine, e.g. a Turing machine. And to say that the mind (at least in its theorem-proving aspect), or a mind, may be represented by a Turing machine is to leave entirely open just how it is so represented." (Boolos (1995) p. 293).
4.8 The same applies mutatis mutandis to Penrose's Gödelian argument, and with that, enough said for now.

Notes

<1>. Take, as just one example, the vivid mini-"history" in SOTM, pp. 249-256, of the origins of probability theory and complex numbers in the work of the 16th century mathematician and physician, Gerolamo Cardano -- as a prelude to an explanation of Schroedingerian quantum mechanics.

<2>. For earlier critical discussion, see the collection Anderson (1964). For criticism in various of the peer commentaries on ENM (with responses by Penrose), see Behavioral and Brain Sciences 13(1990): 643-705, 16 (1993): 611-622.

References

Anderson, A.R. (1964). Minds and Machines. New Jersey: Prentice-Hall.

Boolos, G. (1995). Introductory note to *1951. In Gödel (1995), pp. 290-304.

Cohen, P. (1966). Set Theory and the Continum Hypothesis. New York: W.A. Benjamin, Inc.

Cohen, P. (1971). Remarks on the foundations of set theory. In Axiomatic Set Theory, Proc. Symp. Pure Math. XIII, Part I. Providence: American Mathematical Society.

Davis, M. (1993). How subtle is Gödel's theorem? More on Roger Penrose. Behavioral and Brain Sciences, 16, 611-612.

Feferman, S. (1962). Transfinite recursive progressions of axiomatic theories. Journal of Symbolic Logic, 27, 383-390.

Feferman, S. (1988). Turing in the land of O(z). In (R. Herken, ed.) The Universal Turing Machine: A Half-century Survey, pp. 113-147. Oxford University Press.

Feferman, S. (1988a). Hilbert's program relativized: proof-theoretical and foundational reductions. Journal of Symbolic Logic, 53, 364-384.

Feferman, S. (1993). Why a little bit goes a long way: Logical foundations of scientifically applicable mathematics. In PSA 1992, Vol. 2, pp. 442-455.

Gödel, K. (1986). Collected Works, Vol. I. Publications 1929-1936, Oxford University Press, 1986.

Gödel, K. (1990). Collected Works, Vol. II. Publications 1938-1974, Oxford University Press.

Gödel, K. (1995). Collected Works, Vol. III. Unpublished Essays and Lectures. Oxford University Press.

Kleene, S.C. (1952). Introduction to Metamathematics. New York: D. van Nostrand Co.

Penrose, R. (1989). The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics. Oxford University Press.

Penrose, R. (1994). Shadows of the Mind: A Search for the Missing Science of Consciousness. Oxford University Press.

Polya, G. (1962). Mathematical Discovery (Two vols.). New York: Wiley.

Smorynski, C. (1977). The incompleteness theorems. In Handbook of Mathematical Logic, pp. 821-865. Amsterdam: North-Holland.

Turing, A. (1939). Systems of logic based on ordinals. Proceedings of the London Mathematical Society, 2, 161-228.


Return to PSYCHE home page