Thursday, December 23, 2010

Reducing to logic

Logicism is the idea that mathematics is reducible to logic. Not every believes it, such as Steve Landsburg, who says:
Principia Mathematica, to which Russell had devoted ten years of his life, was his (and co-author Alfred North Whitehead’s) audacious and ultimately futile attempt to reduce all of mathematics to pure logic. It is a failure that enabled some of the great successes of 20th century mathematics. ...

Russell wanted to derive all of mathematics from pure logic, but there was one mathematical fact that defied his every effort — namely the fact that there are infinitely many natural numbers. ...

Aside from dissatisfaction with the Theory of Types and the Axiom of Infinity, there were a couple of other nagging questions left unsettled, though. First: Could all of mathematics be derived from Russell and Whitehead’s logical system? Surely some of it could (though not always easily — R and W notoriously required hundreds of pages to reach the conclusion that 1+1=2) — but could all? And second: Could the Russell/Whitehead system be proven to be free of logical contradictions? The Russell Paradox had been excised by the Theory of Types, but could one exclude the possibility of other paradoxes lurking in the background?

Russell was surely hopeful on both counts. Kurt Godel, the logician of the millennium and the man who would dash those hopes, was four years old in 1910.
Russell is just as famous for having a goal of world peace. Now that is a goal that is impossible! But he was much more successful with his logicist goals.

The introduction to Principia Mathematica states 3 goals: (1) to effect the greatest analysis with the fewest axioms, (2) to use precise and convenient notation, and (3) to solve the paradoxes of set theory. It seems to me that they achieved these goals admirably. It says a couple of pages later that an object of the work is "the complete enumeration of all the ideas and steps in reasoning employed in mathematics".

Kurt GĂ¶del's incompleteness theorem is sometimes alleged to undermine logicism because it shows that no particular axiomatization of mathematics can decide all statements. Nevertheless, all of mathematics has been reduced to logic. And that certainly includes everything Godel did, and everything in published math journals.

Update: Here is some typical nonsense about the book:
Ms. REHMEYER: Well, it certainly has not been forgotten. It's been very influential. But the interesting thing is it's been influential in a kind of unexpected and, in some ways, sort of tragic way.

The book kind of laid the seeds for its own undoing. About 20 years later, a German mathematician named Kurt Godel used what Russell and Whitehead had done in the Principia to show that it actually couldn't do what it aimed to do, that it couldn't contain all of math, that there would be true mathematical statements that were not logical consequences of the axioms that it set out.

And that really, it was completely shocking, and it completely transformed our understanding of what math fundamentally is.

So the interesting thing about it is, on the one hand, it kind of destroyed the whole project, and on the other hand, Godel couldn't have come to that conclusion without the work of the Principia. So it kind of ate its own tail in a funny way.

And in a certain way, at this point, one of the biggest contributions of the book is that it laid the groundwork for computation, even though that was not in Russell or Whitehead's mind at all. Computers had barely been conceived of at that point.