tag:blogger.com,1999:blog-3722233.post538283051254228068..comments2023-02-04T08:48:36.553-06:00Comments on Computational Complexity: Why did 1+1=2 take Russell and Whitehead 300 pages?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger44125tag:blogger.com,1999:blog-3722233.post-10676276805498633182021-11-01T12:23:11.148-05:002021-11-01T12:23:11.148-05:00What the "right way" is depends on what ...What the "right way" is depends on what you're trying to achieve.<br /><br />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.<br /><br />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.<br /><br />https://mathoverflow.net/q/376839<br /><br />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.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36759425383796994762021-11-01T11:53:08.911-05:002021-11-01T11:53:08.911-05:001) So is ZFC (or perhaps ZF but lets not get into ...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?<br />2) Since ZF was already out in 1908, why did PM come out-- it seems like<br />the goal of reducting math to a few axioms and logic was already done.<br />3) Most comments on old blog posts are spam- so I am glad yours was not!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20919463922993693202021-11-01T11:43:38.345-05:002021-11-01T11:43:38.345-05:00I have come very late to this discussion, but I th...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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />https://cs.nyu.edu/pipermail/fom/2011-July/Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5055436762906405992021-05-24T22:32:33.412-05:002021-05-24T22:32:33.412-05:00hey bill gasarch. I know it's a bit of grave d...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.<br />https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_philosophy<br /><br />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.<br />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 discussionschadicousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36398643582572973812021-05-24T12:30:06.958-05:002021-05-24T12:30:06.958-05:00To prove 1+1=2, you have to define what is 1,+,= a...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.<br /><br />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?<br /><br />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.<br /><br />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.<br /><br />That's enough meth.Jhttps://www.blogger.com/profile/10551394966298424604noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85972669975609965302019-11-15T05:34:30.451-06:002019-11-15T05:34:30.451-06:00I have proof of 1+1=2, only 64 pages, & in my ...I have proof of 1+1=2, only 64 pages, & in my 2nd proof only 15 pages, Anonymoushttps://www.blogger.com/profile/14446938103980700220noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56529350657446211612019-10-02T10:44:35.153-05:002019-10-02T10:44:35.153-05:00Not sure who you are addressing here.
I (Bill Gasa...Not sure who you are addressing here.<br />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.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73041130494609910042019-10-02T07:36:35.166-05:002019-10-02T07:36:35.166-05:00Taking 300 pages to prove 1+1=2, and claiming ZFC ...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.Charlie-Boohttps://www.blogger.com/profile/03253832629640675379noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10479473899294017262019-04-06T09:46:02.447-05:002019-04-06T09:46:02.447-05:00Tell What method they had used to prove it? Why th...Tell What method they had used to prove it? Why they took so much of page?Anonymoushttps://www.blogger.com/profile/08100300508374750643noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59711577416776849202018-02-17T23:19:10.933-06:002018-02-17T23:19:10.933-06:00I'm about to undertake russell & whitehead...I'm about to undertake russell & whitehead, PM 2nd edition 1927? unless someone can suggest other? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87482155717955630362018-02-06T15:41:39.779-06:002018-02-06T15:41:39.779-06:00Is there a textbook that would teach the basics of...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?Annahttps://www.blogger.com/profile/04659973911134189924noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2989015024776569862017-11-26T01:26:52.808-06:002017-11-26T01:26:52.808-06:00Anonymoushttps://www.blogger.com/profile/12368778918799029256noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15771428848823615482017-04-05T06:53:42.109-05:002017-04-05T06:53:42.109-05:00I come from philosophy and (i) Quine wrote his dis...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.HenningShttps://www.blogger.com/profile/09989327109380649680noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70656577494395646152016-12-16T17:27:46.281-06:002016-12-16T17:27:46.281-06:001=(a pencil I hold in my hand)
There is no way to ...1=(a pencil I hold in my hand)<br />There is no way to duplicate its molecular structure down to infinity, therefore there is no 1+1 as I have defined 1<br />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.<br />Can we even know, since we donâ€™t know infinity?<br />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 = 2Anonymoushttps://www.blogger.com/profile/00328176738196347189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7080389164814612252016-07-26T16:08:58.397-05:002016-07-26T16:08:58.397-05:00However, Socrates soon came to the conclusion that...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.....Chuckhttps://www.blogger.com/profile/05238615891442189866noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6753023676581649532016-06-15T18:45:19.596-05:002016-06-15T18:45:19.596-05:00Ok...if 1 + 1 does not equal 2 then how want child...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...Anonymoushttps://www.blogger.com/profile/05789176067213866285noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34581886290689817462016-01-11T14:58:27.231-06:002016-01-11T14:58:27.231-06:00from the introduction to Principia Mathematica, wr...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."Moiseshttps://www.blogger.com/profile/17820950882286476615noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10581323603178609682015-12-03T20:08:42.230-06:002015-12-03T20:08:42.230-06:00I have proof of Equation 1+1=2 shorter, with beaut...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.gerry pajarillonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67479762960290835462015-11-29T16:19:20.276-06:002015-11-29T16:19:20.276-06:00Actually, even in modulo 2, 1+1=2. It just also ha...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 2Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11878436773217586372015-10-06T02:04:09.987-05:002015-10-06T02:04:09.987-05:00The empty set is a subset of every set. That's...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50684610095749696542015-08-11T11:53:06.073-05:002015-08-11T11:53:06.073-05:00Sorry, but 1+1=2 only in some cases. It is not tru...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. :-)<br /><br />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).<br /><br />Insisting that "the math works" is to deny the source of some of the most profound insights ever made in mathematics.<br /><br />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.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56477119420920028332015-03-21T09:32:42.567-05:002015-03-21T09:32:42.567-05:00Yes, and that's why Logic and Set Theory are n...Yes, and that's why Logic and Set Theory are not exactly suited to express 1+1=2<br />My approach is: you don't need + because it postpones the operation of addition, which is immediate.<br />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`.<br />A story that has `2` = 11 in the beginning.<br />Enjoy my old blog, with work in progress: http://iteror.blogspot.nl/<br />And my new blog too: https://exwaan.wordpress.com/<br />YouAnonymoushttps://www.blogger.com/profile/10538920755118262226noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68630244783468718612014-12-12T16:03:09.988-06:002014-12-12T16:03:09.988-06:00PM is flawed. There is an error early on (p7 or p3...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).Sleeypsloonoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7918285687197080722014-11-09T07:17:06.837-06:002014-11-09T07:17:06.837-06:00Actually this is not the real demonstration. It on...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55216008338377267392014-07-26T19:11:09.032-05:002014-07-26T19:11:09.032-05:00Another opinion from someone who never read the bo...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.Anonymousnoreply@blogger.com