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.

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.

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?

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.

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.

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.

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.

1. Tell What method they had used to prove it? Why they took so much of page?

2. To prove 1+1=2, you have to define what is 1,+,= and 2. They are all simple literals that can mean anything. Without definition, 2 doesn't have to be the number of eyes a person has. I can mean one, or five. Similarly, you could also define mathematics using alphabets instead of numbers. Think of hexadecimals for example. Everything is only true within a framework. In Principia, they were trying to define the framework that built conventional mathematics.

It's like, if 1 is one and 2 is two, and two is the successor of one - why is 1+1 equal to 2? What is addition? After all, two is just an arbitrary value just like one. How do you get from one to two just using one, without involving two?

When that is defined, you have to make sure that operation is valid under all conditions where you place 1+1. All this simply defines addition of 1 to get 2. All this makes it complicated.

Further, you have to go about defining it for all numbers, and make sure that everything follows through. But I don't know if it'll be harder to do that since we already defined 1+1=2, or if more problems come with introducing more numbers.

That's enough meth.

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

-anirban

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

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

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?

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)

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.

1. from the introduction to Principia Mathematica, written by Russell: "the chief reason in favour of any theory theory on the principles of mathematics must always be inductive, i.e. it must lie in the fact that theory in question enables us to deduce ordinary mathematics. In mathematics, the greatest degree of self-evidence is usually not to be found quite at the beginning, but at some later point; hence, the early deductions, until they reach this point, give reasons rather for believing the premisses because true consequences follow from them, than for believing the consequences because they follow from the premisses."

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?

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.

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.

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."

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!”

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.

1. Sorry, but 1+1=2 only in some cases. It is not true when working in arithmetic modulo 2, for example. In that case, 1+1=0. :-)

I see this as akin to Euler's quest to remove the fifth axiom from his geometry. The nett effect, eventually, was to discover spherical and hyperbolic geometries (as well as proving that the fifth axiom was indeed necessary to plane geometry).

Insisting that "the math works" is to deny the source of some of the most profound insights ever made in mathematics.

Take another example: a polynomial of degree n has "up to n roots" when all we know are real numbers, but "the math works and has been right for many years". Explore it, and we discover complex numbers.

2. Actually, even in modulo 2, 1+1=2. It just also happens to equal 0, since 0 = 2 modulo 2. 1+1=2=0 mod 2

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?

19. Another opinion from someone who never read the book: I'd think the first 300 pages develop a number of ideas unrelated to proving 1+1=2 and that they could have rearranged the presentation to prove it faster if that were the goal. Or maybe they even put it off as long as possible for dramatic effect, and it was after 300 pages that they could no longer avoid proving 1+1=2.

20. Actually this is not the real demonstration. It only occurs in volume two. In that number he just proves that if we take two different classes with only one element, we can form their sum, which is a class with two elements, that's all. Pay attention, he says "when arithmetical addition has been defined". I suggest you be careful about what people say of Principia: as all topics of knowledge, mathematics is divided into schools of thought, being Zermelo's the most used in modern times; so mathematicians tend to dislike Principia. The axiom of reducibility that causes the problem was fixed by Quine, which produced the New Foundations. If you want a modern account of Principia, just read Quine or Rosser. Just put in your mind the following: none of the schools is so successful as they think, nor unsuccessful as the adversaries think. Most of mathematics comes to opinion, and Russell's didn't please a lot of scholars. Read the introduction to the second edition of https://archive.org/details/principlesofmath005807mbp.

21. PM is flawed. There is an error early on (p7 or p3 perhaps, I can't quite recall). They assume that 'All sets are a sub set of some other set'. However they completely forgot that there is an exception: The Empty Set. Thus the whole of PM fails to establish that Mathematics is reducible to Logic. (it isn't, as the existence of Proof by Induction should already indicate).

1. The empty set is a subset of every set. That's why it's always included in the power set. A subset is a set which only contains elements from another specified set. That says nothing about having to contain any of those elements.

22. Yes, and that's why Logic and Set Theory are not exactly suited to express 1+1=2
My approach is: you don't need + because it postpones the operation of addition, which is immediate.
Naturally write 11 and there you have it. Of course if you want to you can put a decimal system on top of the natural numbers 1.. But that is another story.
A story that has 2 = 11 in the beginning.
Enjoy my old blog, with work in progress: http://iteror.blogspot.nl/
And my new blog too: https://exwaan.wordpress.com/
You

23. I have proof of Equation 1+1=2 shorter, with beauty and great, yes first I proof it in 64 pages, and my second proof is 15 pages and in my 3rd proof is 3 pages etc.

24. Ok...if 1 + 1 does not equal 2 then how want children do I have that I can claim tax benefits for...I am kind of hoping that one of you can give an answer of say..10? I could then safley quit work and live off the benefits...

1. I have proof of 1+1=2, only 64 pages, & in my 2nd proof only 15 pages,

25. However, Socrates soon came to the conclusion that he was not right for this sort of inquiry: his speculations so confused him that he began to unlearn everything he had previously thought he knew. For instance, Socrates no longer knows even how to give an account of how one and one equals two. He finds it hard to believe that the reason for their becoming two is simply the fact that they were brought together. Nor can he believe that when one is divided in two, the reason for its becoming two is the division. In the first case, one becomes two through addition, in the second case, one becomes two through division: how can both addition and division be the reasons for one becoming two? Utterly confused, Socrates rejected these explanations, seeking a method of his own instead.....

26. 1=(a pencil I hold in my hand)
There is no way to duplicate its molecular structure down to infinity, therefore there is no 1+1 as I have defined 1
We cannot prove anything equals anything and we have to improve beyond infinity, which we dont even have proof of, that the endless 9's after a decimal cannot also be divided and how much.
Can we even know, since we don’t know infinity?
Proofs are all amazingly good for humanity in that they are all subjective, but must be tested to become useful. But cant any proof become questionable in time. And 1+1=2 is less factual than 1+1 doesnt = 2

27. I come from philosophy and (i) Quine wrote his dissertation on PM, so it certainly was a big influence on the most influential American philosopher of the 20th century, and (ii) I believe pretty much all of the logical notation I teach comes from PM.

28. Is there a textbook that would teach the basics of these things in a way someone like me, that is, someone with no background in logic yet solid background in high-school math?

29. I'm about to undertake russell & whitehead, PM 2nd edition 1927? unless someone can suggest other?

30. Taking 300 pages to prove 1+1=2, and claiming ZFC can do it shorter - without giving any details - is one of the stupidest episodes in the history of Mathematical Logic. It violates all common sense and even formal criteria for sanity e.g. Occam's Razor. The Emperor Has No Clothes.

1. Not sure who you are addressing here.
I (Bill Gasarch, who did this post) merely asked if its shorter in ZFC, and others who commented on it seemed to say it was not or didn't know.

31. hey bill gasarch. I know it's a bit of grave digging at this point but i've stumbled upon PM by following a few rabbit holes and the idea of such an extravagent process to prove 1+1=2 reminded my of another rabbit hole I dived down which was the list of unsolvable paradoxes in philosphy, which I will now link before I continue on.
https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_philosophy

The two particular light bulbs that lit off inside my head were in reference to the gettier problem, and the problem of the criterion. Essentially these state that in order for something to be true, it must be justified. But the justification must be justified, which must then be - you get the point.
I understand I might be on the verge of merging concepts and rediscovering the wheel on my own, just thought I'd respark some hopefully enjoyable discussions

32. I have come very late to this discussion, but I think I have something to add. It is important to understand that proving that 1+1=2 was not the goal of PM. Their goal was to demonstrate that all of mathematics could be reduced to logic. Nowadays we take for granted that all of mathematics can be reduced to set theory, and all valid inferences can be captured purely syntactically and checked with a computer, but such claims were far from obvious back then. Part I of PM was devoted entirely to developing the foundations of mathematical logic from scratch, with a view toward all of mathematics, not just 1+1=2. Given this goal, spending a few hundred pages on Part I doesn't seem so extravagant. The proof of 1+1=2 appears near the beginning of Part II, so I would argue that they didn't waste that much time getting around to it.

In terms of a direct comparison to ZFC, one difficulty is that PM was not fully formal in the modern sense. It relied on a theory of types, which was not spelled out in full detail. Indeed, Goedel complained that in terms of syntactic precision, PM had taken a step backwards compared to Frege's work. (There have been modern efforts to formalize PM's theory of types---see for example the work of Randall Holmes---but whether they correctly capture what Whitehead and Russell really intended is partly a matter of opinion.) I think that Russell in particular wanted to strenuously deny that the formal symbols of PM were "meaningless," and hence he blurred the distinction between syntax and semantics that today we recognize as being of paramount importance.

Finally, let me mention an interesting article by Daniel J. O'Leary, "The propositional logic of Principia Mathematica and some of its forerunners." O'Leary tried to reproduce Part I, Section A of PM on a computer. This section of PM avoids many of the notorious ambiguities surrounding type theory that I mentioned above. Nevertheless, O'Leary (not surprisingly) uncovered numerous bugs. So if one really wants to assess the length of a proof of 1+1=2 in the system of PM, I would recommend not attempting to faithfully reproduce the proof in PM; instead, one should first write down a fully formal version of PM and then search for a proof of 1+1=2.

Much of what I write here, I learned from a discussion on the Foundations of Mailing list that took place around the same time that you originally made this blog post.

https://cs.nyu.edu/pipermail/fom/2011-July/

33. 1) So is ZFC (or perhaps ZF but lets not get into that now) the right way of doing it, and PM the wrong way of doing it?
2) Since ZF was already out in 1908, why did PM come out-- it seems like
the goal of reducting math to a few axioms and logic was already done.
3) Most comments on old blog posts are spam- so I am glad yours was not!

34. What the "right way" is depends on what you're trying to achieve.

We have a tendency today to lump together logic and set theory. However, they're not exactly the same, and these sorts of distinctions were important to people like Russell. Russell, remember, had torpedoed Frege's set-theoretic system with his famous paradox, and so the decision to base PM on type theory was probably motivated in part by the feeling that type theory was "safer" than set theory. So the fact that Zermelo had proposed a set-theoretic system in 1908 (by the way, ZF includes the axiom of replacement, which Fraenkel didn't publish until 1922) didn't necessarily settle matters. Back then, it would have been reasonable to take the attitude that Zermelo's system should just be viewed as one proposal of many until one of the competing systems was proved consistent.

Even today, there are legitimate debates about whether type theory or set theory is a "better" foundation for proof assistants. See for example this discussion on MathOverflow.

https://mathoverflow.net/q/376839

And the question of which system is better for a proof assistant is distinct from the question of which system is better for other purposes. For example, if you want to prove that the continuum hypothesis cannot be proved or disproved from "the axioms of mathematics," then ZFC provides a number of technical advantages when it comes to writing down the proof.