Monday, July 25, 2011

Why did 1+1=2 take Russell and Whitehead 300 pages?

In my post about the myth that Logicians are crazy I mentioned in passing that Whitehead and Russell spend 300 pages proving 1+1=2 (but were both sane). Two people privately emailed me:
Are you sure Russell and Whitehead weren't a few axioms short of a complete set? How could they take 300 pages to prove 1+1=2. Isn't it... to obvious to be worth proving?
I responded by saying that they had to define 1, +, =, and 2 rigorously. One of them responded Are you a few limit points short of Banach space? That aside, there are some questions the 1+1=2 proof brings up:
  1. How did they spend 300 pages proving 1+1=2?
  2. Is it easier in ZFC?
  3. How important is or was Principia Mathematica? Wikipedia says PM is widely considered by specialists in the subject to be one of the most important and seminal works in mathematical logic and philosophy since Aristotle's Organon. The Modern Library places it 23rd in a list of the top 100 English-Language nonfiction books of the twentieth century. Here is the list they are referring to. The other books look... readable.
  4. I had thought that nobody reads PM anymore; however, its entry on amazon says it has a rank of roughly 294,000. This is far better than a book that truly nobody reads. For example this book has an Amazon rank roughly 5,300,000.
  5. While more people are buying it than I thought, are people actually reading it? Did they ever? My guess is no and no, but I really don't know.
  6. Can a book be influential if few people read it? Yes if they are the right people. Godel read it and I think it inspired him. (Its mentioned in the title of his Incompleteness paper.)
  7. PM was an early attempt to formalize all of math from the ground up. This may be one of those tasks that you are almost destined to do in a clunky way before doing it smoothly.
  8. I am talking in a vacuum here, having never read it. If any of my readers have actually read it and want to comment on what it was really like, you are more than invited to do so.

19 comments:

  1. No. I haven't read it. BTW, the usual version in print is not the full version. I wonder how much longer the full version is.

    You don't mention what I have heard described as the most long-lasting direct contribution of PM: The introduction of type theory which among other things is essential to our understanding of programming languages.

    Don't be fooled by the Amazon sales rank. I heard once from an Amazon insider that below a certain rate of sales, the sales rank is essentially random.

    ReplyDelete
  2. I've often wondered about this question (how they could spend so long proving that 1+1=2). It's quite obvious -- I think, without having tried to check -- that to carry out the proof in ZF would be much much shorter. But there's a question of how much background you insist on proving first. For instance, do we have to define all the positive integers in terms of sets and prove that they satisfy the Peano axioms? Even that seems as though it ought not to be too bad.

    I have two questions that I'd be interested to know the answers to. The first I've basically just asked: how much else is proved in the course of showing that 1+1=2? The second is whether the difficulty for Russell and Whitehead came from having a much more unwieldy set of axioms for set theory, which you've essentially asked above.

    A minimal proof might be this. Define the successor function and then define addition on the finite von Neumann ordinals. Don't bother to prove that the definition makes sense beyond 1+1: just calculate what set 1+1 is and then observe that it's the same set as 2. Was there some reason that R&W couldn't do anything like this?

    ReplyDelete
    Replies
    1. They had to define what the the symbols "1", "+", "2", and "=" were. The symbols had not been as formally defined until the book was written. It took until page 300 to define the symbols and to prove that they could put the symbols 1+1= together before proving that 1+1=2. They went to the basics of basic in this proof. including defining what a "1" is.

      We, in school or at home, learn that 1 is a quantity equivalent to one object but that object is just a representation of a 1 not the definition of it.

      I hope that this makes some sense.

      Delete
  3. I have read parts of the first volume, and had a look on second and third one.

    It is too long because they are formalizing everything, even logic. If I remember correctly they have only two connectives, negation and disjunction. It is like developing mathematics in Coq of the area. Try to imagine how difficult it would be to prove a theorem in a the language of a proof assistant on paper. The simple proof in ZFC without presuming definitions will not be short if you try to develop all mathematical concepts (e.g. what is an and? what is a function?) and their properties (e.g. A and B implies A, composing two functions give a function). It also contains lots of philosophy in it. The axioms are also less handy than ZFC. It is a bad exaggeration that they are prove 1+1=2 in 300 pages.

    ReplyDelete
  4. I suspect they didn't actually "spend 300 pages proving 1+1=2" but rather they "spent 300 pages setting up a lot of background and defining a whole bunch of stuff and then eventually as an afterthought proved 1+1=2" i.e. they could have done it quicker if that was their sole aim.

    Of course it would be great if someone has read the book and knows how exactly they did it.

    ReplyDelete
  5. People say that they needed 300 pages to prove it because in page 379 it says "From this proposition it will follow, when arithmetical addition has been defined, that 1+1=2." – Volume I, 1st edition, page 379 (page 362 in 2nd edition; page 360 in abridged version). They didn't even prove it in the first 300 pages. The proof is actually completed in Volume II, 1st edition, page 86.

    They weren't actually trying to prove just that, but to define and prove the whole of mathematics based only on negation and conjunction, and in such a way that you don't even have a universe of discourse. For example, they said stuff like "x is grandfather of y is equivalent to x is father squared of y" or that "one apple plus one apple equals two apples" which you can't say in ZFC, and which is considered one of the basic flaws of PM (together with the axiom of reducibility, maybe), because it makes things ambiguous and harder to prove.

    ReplyDelete
  6. Although tangential to the discussion, I would like to put a plugin for the brilliant "Logicomix" by Christos and Apostolos.

    -anirban

    ReplyDelete
  7. This is unrelated, but the link to stoc2002.org on your twitter feed is broken.

    ReplyDelete
  8. I posted too soon before the DNS fully propagated.

    ReplyDelete
  9. Would anyone agree with the amazon review statement that any mathematician would call this the most influential book of the 20th century? It did have a big impact on logic, but certain papers like Godel's had a bigger impact, I think. It's a bit tricky because most of the most important works were papers, not books, but was PM more important than Knuth's Art of Computer Programming or Bourbaki? What is on your list?

    ReplyDelete
  10. In modern times, depending on what you mean by "1", "2", and "+", 1+1=2 is either true by definition, or very trivial.

    For example, in ring theory, 2 is *defined* to be 1+1 (where 1 is the multiplicative identity and + is one of the ring operations). In this context, 1+1=2 is true by definition.

    In Peano Arithmetic, 1 might mean S(0) (the successor of 0) and 2 might mean S(S(0)), and proving that S(S(0))=S(0)+S(0) requires a small amount of work: maybe half a page, or maybe 4 lines, depending whether you're allowed to assume commutativity of + or have to prove that too, respectively. (For the 4-line proof where commutativity is assumed, see here)

    ReplyDelete
  11. I suspect the thing that confuses people about the claim that R&W took "300 pages to prove 1+1=2", is that they interpret it to mean that R&W *discovered* 300 pages of nontrivial mathematical machinery underlying our naive intuition that 1+1=2 (in the same way, maybe, that sphere != donut takes several pages to prove despite its intuitive obviousness). But then they wonder what such machinery could possibly look like. And they're right to wonder! Their intuition is correct; there REALLY IS no mathematical demonstration that could make 1+1=2 more secure than it already is. If you don't already know what the positive integers are and how to manipulate them, then you certainly can't do first-order logic.

    So I think the right analogy to understand R&W would be a book on computer organization that spent hundreds of pages painstakingly setting out a specific computer architecture, and that only by page 300 (or Volume II, or whatever) was ready to explain what a simple program calculating 1+1=2 would do when compiled. That might STILL be a little weird, but there's nothing inconceivable about it.

    ReplyDelete
  12. Scott, your answer makes so much more sense if I read R&W as Russell and Whitehead instead of Read&Write. 8) Didn't Whitehead insist on top billing though?

    ReplyDelete
  13. Sam, by "1" I think they mean the class of all unit classes, which if I recall rightly is so big it's not even a set.

    ReplyDelete
  14. I think Russell says in his autobiography that Gödel might have been the only person ever to read the whole book.

    Also, I understand, as Micki mentions, that they define "1" as the class of all unit sets (perhaps all unit classes), where + is some kind of disjoint union, which would allow 1+1 to be equal to 2. Still, I am not sure, but I think that's roughly the idea.

    ReplyDelete
  15. Norm Megill has a complete, hyperlinked formal proof of 2+2=4 from the axioms of predicate calculus and ZFC. Fully-expanded, it consists of about 26,000 elementary steps.

    Norm writes, "One of the reasons that the proof of 2 + 2 = 4 is so long is that 2 and 4 are complex numbers—i.e. we are really proving (2+0i) + (2+0i) = (4+0i)—and these have a complicated construction but provide the most flexibility [...] In terms of textbook pages, the construction formalizes perhaps 70 pages from Takeuti and Zaring's detailed set theory book (and its first-order logic prerequisite) to obtain ordinal arithmetic, plus essentially all of Landau's 136-page Foundations of Analysis."

    ReplyDelete
  16. Hmm. I wonder if Russell and Whitehead toyed with Reductio Ad Absurdum. I mean, if 1+2 does not equal 2, would that not create some contradictions?

    How many hands do you have? Fourteen seems like the wrong answer.

    It must have been a drag for R&W to publish this enormous epic of the intellect, only to have Gödel almost immediately say, “Nope!”

    ReplyDelete
  17. Why bother to prove 1+1=2 when we all know that the maths works and has been right for many years. I feel Russel and Whiteheads exercise was a waste of brain time that could have been put to more constructive uses.

    ReplyDelete
  18. Have you heard of Russell's Paradox? If you have/had then you shouldn't/wouldn't think that what they did was of little importance.
    Russell was a logician, if logic was broken where does that leave him?

    ReplyDelete