5
$\begingroup$

In the second edition of Principia Mathematica Russell attempts to show in a new Appendix B that the Peano postulates for the natural numbers, including the scheme of mathematical induction, can be derived in the absence of the Axiom of Reducibility. But, his proof in the appendix is in error, as was first pointed out by Gödel. Thus, the system of the second edition can only be accounted a complete failure, considered as a foundation for mathematics.

My first question is,

Did Russell ever attempted to make his proof correct? How did he attempted to do it? In particular, what was his response to Gödel when he showed that his proof contained an error?

$\endgroup$
  • $\begingroup$ These are two quite different questions, IMO, and should probably be asked separately. $\endgroup$ – user642796 Jun 11 '15 at 7:30
5
$\begingroup$

Ref to the title's question :

Did Russell correct his proof of Peano Postulates as was in the second edition of Principia Mathematica ?

the answer is no.

We have to look at the detailed treatment in :

The topic of Appendix B is the principle ofmathematical induction which, together with the definition of numbers as classes of equinumerous classes, forms the heart of the logicist account of arithmetic [138].

Theorem ∗89·12 is important for the rest of the appendix, but also problematic, as it seems to violate the theory of types. On the surface it asserts that every inductive or finite class of order 3 is identical with some class of order 2 [...] The argument seems to be that since each finite class can be seen as built up from one individual by a finite number of uses of this operation, that class must itself be definable by a function of order 2. That itself can be seen to be fallacious, using the models later developed by Myhill, but what’s more, the claim of identity of these classes of differing types rather than mere co-extensiveness raises issues about what notion of types is in force in the Appendix. These issues arise from the technical objections to Appendix B by Gödel and Myhill, to be considered below. [147].

The crucial lemmas needed for this most important theorem of Appendix B are ∗89·12 and ∗89·17. The rest, despite the great amount of complication, and the difficulty of the notation, seems to follow directly. It is clearly a sign of the degree to which Gödel and Myhill studied and understood the content of Appendix B that it is precisely those two theorems that drew their attention. As we shall see, the first requires that there be a new use of types in Appendix B, and the second is simply mistaken [148].

The “non-standard” models of arithmetic used in Myhill’s proof should also cast doubt on Russell’s belief, as evidenced in ∗89·16, that sets of finite numbers can always be defined using limited logical resources [...] Reflection on Gödel’s theorems about systems of arithmetic led Hao Wang to assert that the project of Appendix B was impossible already in 1963, well before Myhill’s paper [150].

Myhill’s argument, however, used an obvious and natural semantic interpretation. It is understandable, then, that it became common knowledge that Appendix B had been vitiated. But the reputation of Appendix B had already suffered worse [151].

Kurt Gödel found an error in the proofs of Appendix B in his “Russell’s mathematical logic” (1944,pp.145–6) [151].

Gödel took this objection, and it appears that he wrote to Russell about it. In the only known letter from Gödel to Russell, which survives in draft form among Gödel’s papers but was likely typed and then sent, he expresses the hope that Russell’s decision not to reply to his article is not due to the mistaken impression that nothing in it would be controversial. He writes:

I am advocating in some respects the exact opposite of the development inaugurated by Wittgenstein and therefore suspect that many passages will contradict directly your present opinion. Furthermore I am criticizing the vicious circle principle and the appendix B of Principia, which I believe contains formal mistakes that make the proof invalid. The reader would probably find it very strange if there is no reply.

There is no record of a response from Russell. Indeed, in My Philosophical Development (p.89), written in 1959, Russell still refers to the second edition of PM as successful in showing that the axiom of reducibility is not “indispensible ... in all uses of mathematical induction”. So there is no published reply from Russell [152-53].

It appears, then, that despite the allegations of errors throughout Appendix B, and the proof by Myhill that the main result does not hold, there is really only one definite example of an error in a proof, namely, line (3) in the proof of ∗89·16. That error was first identified by Gödel, then Myhill singled it out as well as one of only two examples of what he suggests are many [153-54].

Gödel says that (3) is “evidently false”. Myhill, as we have seen, seems to follow Gödel, and quotes (3) in full, presenting it as one of the two examples he actually gives of the “many superficial” errors that “can be corrected in various ways”. While Myhill says that he gave up on Appendix B because of these many mistakes, Gödel responds differently. He was interested enough in the argument to still seek some explanation from Russell for what he describes as “formal mistakes”.

What is the mistake? Line (3) of the proof of ∗89·16 is stated without justification, and does not follow from an earlier line in the proof. [...] However, (3) is in fact only true in particular cases. It is easy to find counterexamples to (3) [155].

The history of the Appendix B manuscript is consistent with this assessment of the mistake as being a simple oversight. ∗89·16 is on page 9 of the manuscript of Appendix B. [...] Is this mistake easily corrected? As (3) constitutes the inductive step in a proof by induction, it is crucial to the argument. Could a different inductive property be used? [156].

It is tempting to hypothesize that since Gödel realized that the project of Appendix B was impossible, precisely because of the impossiblity of constructing a categorical theory of arithmetic with only limited orders of quantifiers, in other words, that something like Myhill’s result would be provable. It would be no accident, then, that Gödel found the mistake at line (3) in ∗89·16. There would have to be a mistake somewhere, and someone with the notion of non-standard numbers in mind would have the counter-example to (3) ready to mind.

Russell, on the other hand, working before Gödel’s results, assumed that he could capture the structure of the numbers with limited resources. One can imagine him checking the validity of (3) with a model of initial segments of the numbers, and finding it to be an obvious truth. Line (3) would be correct of the case where it is applied if the goal of the project of Appendix B was true. Seen this way, the proof of ∗89·16 fails because it begs the question. Gödel was not trying to get Russell to confess to having made an error of elementary set theory when he wrote asking Russell to respond to his paper. Instead he pointed to an exact point in a technical proof around which to crystalize the larger question of whether Russell’s project was bound to fail. [157-58]

Gödel’s paper was published in 1944, Myhill’s in 1974. It then took until 1991 for the next discussion of the proof in Appendix B to appear in print. This was in Davoren and Hazen (1991), an abstract of a talk to the Association for Symbolic Logic [166].

In his (1996) and (2007), Gregory Landini also proposes that the logic of the second edition is modified [...] and consequently relaxes the conditions on well-formed formulas. He adds to this a certain axiom of extensionality, and so produces a proof of ∗89·17, thus finally “rectifying induction”, as he describes Russell’s project. [...] Landini is indeed able to “rectify” induction by proving it without using the axiom of reducibility, and with an axiom of extensionality, in the new theory of types that he, Gödel, and Hazen each found in Appendix B. Unfortunately in that system of types the new axiom of extensionality Landini proposes is strong enough to prove the axiom of reducibility. [...] Yet a principle stronger than the axiom of reducibility, which so directly entails the axiom, would hardly seem “less objectionable”, however well it is justified. This does not seem to be a genuine “rectification” of induction in the system of the second edition [166-68].

Gödel was right that there is a mistake at line (3) in the proof of ∗89·16. Russell did not notice the mistake, which survived several revisions of the appendix intact. The error was to cite without proof an assertion of elementary set theory which is not true in general, but which would hold in the situation of the hypothesis of the argument if the theorem were correct. Russell’s error is to beg the question in his proof. Myhill was right to focus on ∗89·12 as problematic. He says that it is either ill formed, or trivial. It is indeed intended in the sense that he finds ill formed, as identifying a class of one order with a class of another order. Other theorems, and a line of comment, in the manuscripts, but not the published version, verify that ∗89·12 is also intended and not a result of a slip or inattention. The explanation is as Gödel suggested, there must be a new theory of types in Appendix B, one which makes ∗89·12 well formed.

Myhill’s result about the system of ramified types in the first edition of PM, with his proposed semantic interpretation, is quite correct. It is impossible to derive a principle of induction using a principle of extensionality but not an axiom of reducibility, in the system of the first edition. It is an open question whether some other plausible extensional system of ramified type theory (or so-called “predicative analysis”) will have such a result [168].

So Gödel is right to say that the issue concerning induction is still open, and that Appendix B as it stands cannot be easily repaired. In particular, the difficulties extend beyond the elementary mistake in line 3 of the demonstration of ∗89·16. [...] The errors in Appendix B were serious, and not easily remediable, but not because they were based on superficial confusions and slipshod notations. Rather, it seems, they represented the state of logic in 1924. The notions needed to understand the logical resources necessary for defining the structure of the natural numbers were not yet developed. It was the notions of model theory and the study of the power of deductive theories of arithmetic in the 1930s that would finally allow a better understanding of these issues. As well, it seem clear that Russell had new ideas about the hierarchy of types, ideas that were not fully worked out. The ideas of extensionality and the more thorough-going atomism from his own earlier “Philosophy of logical atomism”, and Wittgenstein’s Tractatus, had influenced Russell’s ideas of the structure of the hierarchy of types [169].

$\endgroup$
  • $\begingroup$ And the answer to the second question? $\endgroup$ – user 170039 Jun 11 '15 at 13:12
  • $\begingroup$ @user170039 - but where in the paper you have referenced is discussed the issue of induction (see Appendix B) ? $\endgroup$ – Mauro ALLEGRANZA Jun 11 '15 at 13:22
  • $\begingroup$ I have not gone through the whole paper yet. What seems surprising to me is the claim of superiority of the system of PM even if in the second edition there was a mistake. $\endgroup$ – user 170039 Jun 11 '15 at 14:16
  • 1
    $\begingroup$ @user170039 - for what I've understood after a brief glance at it, the point of view of the author is not about PM as a "foundational system" for mathematics (see Logicism) but as a "foundational system" for logic itself, i.e. as "a metatheory of first-order logic"... $\endgroup$ – Mauro ALLEGRANZA Jun 11 '15 at 15:21
  • $\begingroup$ In the last paragraph you quoted-"...As well, it seem clear that Russell had new ideas about the hierarchy of types, ideas that were not fully worked out." What were the new ideas? Did they remove the need of Axiom of Reducibility (as Ramsey's interpretation of propositional function did)? $\endgroup$ – user 170039 Jun 19 '15 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.