Question So, it's my understanding that Russell and Whitehead's project of logicism in the Principia Mathematica didn't work out. I understand that two reasons for this are (1) that some of their axioms don't seem to be derivable from pure logic and (2) Gödel's incompleteness theorems. However, particularly since symbolic logic and the philosophy of mathematics are not my area, it's hard for me to see how 1 & 2 work and defeat the project.

Accepted:
July 29, 2010

Comments

In the Principles of Mathematics, Russell boldly asserts

"All mathematics deals exclusively with concepts definable in terms of a very small number of logical concepts, and ... all its propositions are deducible from a very small number of fundamental logical principles."

Principia, a decade later, is an attempt to make good on that programmatic "logicist" claim.

Now, one of the axioms of Principia is an Axiom of Infinity which in effect says that there is an infinite number of things. And you might very well wonder whether that is a truth of logic. (If someone thinks the number of things in the universe is finite, are they making a logical mistake?)

Another axiom is the Axiom of Reducibility, which I won't try to explain here, but which is even less obviously a logical law -- and indeed Russell himself argued that we should accept it only because it has nice mathematical consequences in the context of the rest of Principia's system.

Still, there is some room for argument about what principles, exactly, deserve the honoric "logic". And it would still be very interesting if Principia succeeded in showing that all elementary mathematics -- or at least, all arithmetic! -- can be reduced to a handful of laws of a very general kind.

But unfortunately, it doesn't even show that. Gödel's incompleteness theorems show that there are truths expressible in the language of elementary arithmetic which can't be proved in Principia. And the argument generalizes: well-behaved extensions of Principia will be arithmetically incomplete too.

So, in sum, Principia doesn't even seem successfully show that all propositions of arithmetic "are deducible from a very small number of fundamental logical principles" (the principles invoked arguably don't all belong to logic, and the system is certainly incomplete and incompletable).

I think it's important to distinguish the two sources of "failure", not so much as regards Principia but as regards logicism quite generally. I'll stick, as Prof Smith did, to arithmetic.

Here's a way to put Gödel's (first) incompleteness theorem: the set of truths expressible in the language of first-order arithmetic cannot be listed by any algorithmic method, i.e., it is not (as we say) "recursively enumerable". Now why is that supposed to show that logicism fails? Because the set of theorems of any first-order formal theory is recursively enumerable. This is a consequence of Gödel's first great theorem, the completeness theorem for first-order logic (and also of what we mean by a "formal" theory). So the truths aren't r.e. and the theorems are—you can list the theorems but not the truths—so the theorems can't exhaust the truths.

Now why is this a problem for logicism? Obviously, as the argument has been stated, it depends critically upon the assumption that the proposed logical basis for arithmetic is a first-order theory. In fact, of course, the argument can be generalized. Here is what George Boolos has to say about it in an unpublished (but soon to be published) paper from the early 1970s:

The argument convinces me, at any rate, that there is no reduction of arithmetical truth to logical truth, where the logic in "logical" is understood to be elementary, or ﬁrst-order, logic, or indeed, any system of logic whose theses form an effectively generable set [that is, that are recursively enumerable]. (Gödel’s theorems of 1931 and the improvements and related results that followed soon afterwards meant the death of more philosophies of mathematics than just Hilbert’s formalism.)

That is Boolos summarizing a general form of the argument we just outlined: If the facts about some variety of logical deducibility are r.e. (as they are with first-order logic), then the theorems of any formal theory understood as subject to that form of logical deducibility will also be r.e. (because of what we mean by a "formal" theory), and the argument will go through. But then he goes on to say more.

The possibility of a significant reduction of arithmetic to something that might be called a system of logic is left open by our argument, however. What is excluded is that there be an effective method which identifies all and only the theses of the system: a proof procedure. It may seem that it is essential to a system of logic that it have a proof procedure, and that logics without proof-procedures are so called only laughingly or by courtesy. I think that this essentialist claim is wrong, however, and that second-order logic deserves its name. [Some ellipses omitted.]

The logical truths (what Boolos is calling "theses") of second-order logic are not r.e., so second-order logic is not subject to the argument. And there are formal second-order theories to which arithmetic can be "reduced", in the sense that their logical consequences include all arithmetical truths (and no arithmetical falsehoods). So, as Boolos says, the critical question is whether second-order "logic" is really logic, and that is what his paper is about.

Of course, none of this touches the other question asked, which in the present context will take the following form: Consider one of these formal second-order theories to which arithmetic can be reduced; is it really plausible that all of its axioms are going to be logical truths? Prof Smith gestures at one response. Since there are infinitely many numbers, any theory to which arithmetic can be reduced will have to imply the existence of infinitely many things. But surely logic doesn't imply that, so the principles can't be logical. I don't know if Prof Smith would endorse this sort of argument (Boolos did, at least sometimes), but it doesn't seem very impressive to me. At least, it doesn't really engage the logicist impulse. You can't argue against a view by pointing out that the premises assumed imply the conclusion.

Now, this isn't to say that a principle simply asserting that there are infinitely many things (like Russell's) should be regarded as an acceptable basis for a reduction of arithmetic to logic. One might well think that no such principle can be a primitive logical truth. If it's a logical truth, that has to be because it is a logical consequence of some simpler principle or principles. And I think that's correct. But there are simpler principles whose claim to logical truth (or something relevantly like it) is a good deal more plausible and that do imply the existence of infinitely many things (in fact, quite directly, of infinitely many numbers). But that is a much longer story. If you're interested, have a look at some of the papers on my web site, starting with this one.

To follow on some of Richard's observations: I have never found it at all a compelling argument against logicism that it would have the existence of infinitely many natural numbers be a logical truth. That is not an argument against logicism so much as a restatement of the claim that it is incorrect.

Richard's discussion of Boolos reminds me of Gödel's own caution with regard to what his Incompleteness Theorems establish with respect to Hilbert's Program (roughly, Hilbert's attempt to show that if a basic, or finitary, proposition of mathematics can be established using the powerful, or infinitary, methods of classical mathematics, then it could already have been established using very basic, or finitary, reasoning). [For more on Hilbert's Program, you might see here or here.] I don't myself think that the phenomenon of incompleteness puts paid to Hilbert's project (as divorced from certain other beliefs that Hilbert may have held, such as the belief that all true mathematical propositions are knowable). But the second Incompleteness Theorem much more directly challenges it – indeed many have felt that it directly shows Hilbert's Program to be unachievable. But Gödel himself was more cautious in his original paper. For he noted there that (for all he has said) there may be some finitary forms of reasoning (in particular, those deployed in a proof of consistency) that are not captured within a formal system that formalizes the principles of classical mathematical reasoning.

Richard notes that the impact of the first incompleteness theorem for logicism depends on how one understands "logical". The point here (Gödel's point) is that the impact of the second incompleteness theorem for Hilbert's Program depends on how one understands "finitary".

I agree with Richard's and Alex's general remarks about "logicism" and what counts as "logical". It would indeed be far too quick to reject every form of logicism just because it makes the existence of an infinite number of objects a matter of "logic".

Still, it is perhaps worth reiterating (as Richard indeed does) that Principia gets its infinity of objects by theft rather than honest toil: it just asserts an infinity of objects as a bald axiom rather than trying to conjure them out of some more basic logical(?) principles in a more Fregean way. So I'd still want to say that, whatever the fate of other logicisms, Russell and Whitehead's version -- given it is based on theft! -- can't really be judged an honest implementation of the original logicist programme as e.g. described in the Principles, even prescinding from incompleteness worries.

But for all that, three cheers for Principia in its centenary year!