tag:blogger.com,1999:blog-3722233.post6058308463228924948..comments2024-06-13T23:23:44.643-05:00Comments on Computational Complexity: Voting on Mathematical Truths: The Axiom of Det.Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-53261114236209614832010-01-12T09:52:40.543-06:002010-01-12T09:52:40.543-06:00The strategy DOES NOT need to satisfy any property...The strategy DOES NOT need to satisfy any property<br />such as computable or anything of that sort.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8805795955188453222010-01-11T01:42:02.841-06:002010-01-11T01:42:02.841-06:00bill, since the games could be infinite, i am not ...bill, since the games could be infinite, i am not sure if your definition of strategy is sufficient in my cs-ey mind.<br /><br />is the strategy needs to be computable? decidable? enumerable?kamal jainnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6292465920374069842010-01-07T10:15:51.700-06:002010-01-07T10:15:51.700-06:00Strategy is a function that,
given the game so far...Strategy is a function that,<br />given the game so far, outputs<br />a move. Winning strategy means<br />that if you use this to guide<br />your play you will win.<br /><br />bill gasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89363483427036046892010-01-05T12:44:28.505-06:002010-01-05T12:44:28.505-06:00The axiom uses the term "strategy" witho...The axiom uses the term "strategy" without definition. I'd naively think of a strategy as a recursive function from game states to moves, otherwise you couldn't carry it out. But you can't have that definition in mind, because then the axiom would be provably false (uncountably many games, but only countably many strategies). So what notion of "strategy" are you using?Gareth Reeshttps://www.blogger.com/profile/15405124248006286547noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87000230398654564012010-01-05T07:11:58.020-06:002010-01-05T07:11:58.020-06:00Although I like AD much better than AC, I would st...Although I like AD much better than AC, I would still vote for AC just because it is at least simpler to state and, to me, more intuitive. It's also a bit more axiom like than AD (maybe again due to its simpler statement).Shahabhttps://www.blogger.com/profile/15635159089551928063noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90534857080331946152010-01-04T22:45:48.417-06:002010-01-04T22:45:48.417-06:00My quick intuition is that AD is false. Finite gam...My quick intuition is that AD is false. Finite game trees have a unique value because one can start at the leaves and work upwards, evaluating each node as a min or max, but in an infinite tree where does one start?<br /><br />I'm less sure about consequence 3, that every subset of the plane is measurable; considerations related to those for <a href="http://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry" rel="nofollow">Freiling's axiom of symmetry</a> suggest it might be true.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16495681374479924712010-01-04T20:41:35.502-06:002010-01-04T20:41:35.502-06:00@Qiaochu Yuan: Extending your reasoning about how ...@Qiaochu Yuan: Extending your reasoning about how you expect computer scientists to think, you would expect all computer scientists to be some brand of intuitionists. Yet, as someone who has been in both math and CS, I know very few true intuitionists, in either math or CS.<br /><br />Most computer scientists with any mathematical bent learned their mathematics in the same undergrad (or sometimes grad) courses that mathematicians did, and (hence?) most have inherited the views that are either implicit or explicit in their teachers' teachings.Joshhttps://www.blogger.com/profile/12723950176543566251noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10617375662111015162010-01-04T19:18:16.558-06:002010-01-04T19:18:16.558-06:00Axiom: Santa Claus is the objectification of the s...Axiom: Santa Claus is the objectification of the spirit of Christmas. <br /><br />Therefore, Santa Claus is real.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62425350412759209592010-01-04T16:15:42.729-06:002010-01-04T16:15:42.729-06:00Are we allowed to vote "Set theory is not a n...Are we allowed to vote "Set theory is not a natural model for mathematics"?<br /><br />The point being, a mathematical universe that is known to contain Conway's "Surreal Numbers" might perhaps contain even stranger (and possibly friendlier) mathematical beasts ...<br /><br />Perhaps some person---who is very definitely not me---might say something sensible and/or provide a reference about surreal numbers, set theory, ZFC, and AC?John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2161264967599977572010-01-04T16:03:07.346-06:002010-01-04T16:03:07.346-06:00I'm surprised people who read a computer scien...I'm surprised people who read a computer science blog think the axiom of choice is obviously true. I would think that computer scientists prefer to work in a constructive topos - in other words, it's not the size of a Cartesian product that matters but whether any of it is accessible to a Turing machine!Qiaochu Yuanhttp://qchu.wordpress.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37800745592977603462010-01-04T13:58:29.457-06:002010-01-04T13:58:29.457-06:00Seems less intuitively reasonable to me than the a...Seems less intuitively reasonable to me than the axiom of choice.<br /><br />Briefly: set theory and theory-of-computation and so on are minefields of stuff like the russell paradox, goedel-type incompleteness results, the halting problem, and so on.<br /><br />Thus I get nervous taking as an axiom that, essentially, a particular class of questions always has a determined answer; I understand that the meaning of the AD is subtler than that but on such a short consideration I'm only going by analogy here.<br /><br />By comparison the AC seems reasonable; if in the course of a proof you've shown that such-and-such set-of-sets exists it seems silly not to allow you to proceed to take out a representative member of each set...what issues I might have with the AC have more to do with which sets-of-sets it is or isn't "reasonable" to allow in a particular context, which I suspect is what really bothers people when they claim to be bothered by the AC. <br /><br />(VIZ banach-tarski: is it really "reasonable" to unquestioningly accept that you "can" (in some sense) decompose S2 into uncountably many orbits, each of which is "dense" in S2? I accept banach-tarski as saying "if you could make that decomposition AND if you can then draw a representative point from each orbit THEN you can duplicate the sphere", but depending on which side of the bed i got up on that day sometimes my intuition balks much more at the notion of distinguishing the various dense orbits from each other than at subsequently choosing members from said orbits.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58040070522630198342010-01-04T12:35:32.877-06:002010-01-04T12:35:32.877-06:00Anon4 again. I'd just like to note that I tota...Anon4 again. I'd just like to note that I totally agree with cody's formalist position here, I just wanted to play along with GASARCH's platonist game.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60054194951650424892010-01-04T12:31:19.623-06:002010-01-04T12:31:19.623-06:00Even among set theorists, most don't believe t...Even among set theorists, most don't believe the axiom of choice is true. The idea is usually that AD should be true in L(R), not the actual universe. L(R) is the sets that are definable in some broad sense. So what this says is that any pathological sets - non meaurable, without the property of baire, etc., must be inherently very undefinable.<br /><br />If certain large cardinals exist, than AD is actually true in L(R). Not just consistent, but actually true.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27926306641764572902010-01-04T12:26:49.838-06:002010-01-04T12:26:49.838-06:00I'm very reluctant to call axioms true, and I ...I'm very reluctant to call axioms <i>true</i>, and I consider both <i>obviousness</i> and <i>reasonableness</i> to be unsatisfying metrics to rate an axiom. I think the only measure should be the "<i>interesting-ness</i>" of the consequences (and of course consistency is of utmost importance).<br /><br />I have three reasons for this view: 1, history is scattered with conclusions that weren't obvious (nor felt reasonable) until enough time passed to find more comprehensible descriptions; 2, there is no real need for mathematics to represent reality (and many interesting conclusions are the result of toy models that are very much not real); 3, the "interesting-ness" of the consequences of an axiom are the best motivators for researchers to research.<br /><br />That said, I'm a physicist, and I only know enough CS and set theory to get myself in (uncountable) trouble.<br /><br />Regardless, if voting is still important, I would vote that we have some people accept AC and others reject it, (based on their own personal intuitions about which is more interesting to study), which I believe is the status quo. So I am most likely no help at all.codyhttps://www.blogger.com/profile/11407919985914326282noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40241340201841691722010-01-04T12:19:41.205-06:002010-01-04T12:19:41.205-06:00My vote: It is not reasonable at all. I'm not ...My vote: It is not reasonable at all. I'm not a set theorist, and I don't see any reason why it should be true. A good argument could probably convince me, but then we must extract another, more reasonable axiom from that argument, and go with it instead of AD.<br /><br />...I even have problems with the formalization of the Axiom, specifically, the definition of 'strategy'. Isn't it possible that the implications of the Axiom slightly depend on the exact formalization of the notion of strategy?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47724563753686599042010-01-04T11:56:09.509-06:002010-01-04T11:56:09.509-06:00Vote yes for AD.Vote yes for AD.Joshua Hermanhttps://www.blogger.com/profile/15916260498573855412noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64038005268399502152010-01-04T11:54:42.490-06:002010-01-04T11:54:42.490-06:001) Thats a NO vote.
2) The Banach-Tarski paradox
...1) Thats a NO vote.<br /><br />2) The Banach-Tarski paradox<br />makes me at least question AC.<br /><br />bill gasarchGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10472280167704892912010-01-04T11:40:22.466-06:002010-01-04T11:40:22.466-06:00The axiom of choice is obviously true. The cartesi...The axiom of choice is obviously true. The cartesian product of nonempty sets isn't just <i>nonempty</i> -- it is <b>very large</b>.Anonymousnoreply@blogger.com