tag:blogger.com,1999:blog-3722233.post7923404146102863031..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: It was a stupid question!!!!!!!!!! or...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-80342320435510989132007-11-09T09:06:00.000-06:002007-11-09T09:06:00.000-06:00Bill,Thanks a lot for your interesting post, the w...Bill,<BR/><BR/>Thanks a lot for your interesting post, the write-up and the links. <BR/><BR/>Wikipedia has a short list of mathematical statements that are independent of ZFC on this <A HREF="http://en.wikipedia.org/wiki/List_of_statements_undecidable_in_ZFC" REL="nofollow">page</A>. You may find it interesting. <BR/><BR/>Saharon Shelah's result to the effect that the Whitehead problem is undecidable in ZFC is discussed in <A HREF="http://www.jstor.org/view/00029890/di991617/99p1649q/0" REL="nofollow">this paper</A> by Eklof. Shelah has also shown that the problem is independent of ZFC+CH.Luca Acetohttps://www.blogger.com/profile/01092671728833265127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58404091192224888852007-11-07T17:24:00.000-06:002007-11-07T17:24:00.000-06:00Anonymous 2: You also seem to think independence r...Anonymous 2: <I>You also seem to think independence results are more worthwhile if they're proved by nonlogicians. Why is the result more or less worthwhile depending on who proved it?</I><BR/><BR/>Statements in math that are indep of ZFC are (a priori) more likely to be generally interesting if they were first stumbled upon by nonlogicians. It's not that they were <I>made</I> interesting this way; they were interesting enough already, which made them more likely to be found by nonlogicians.<BR/><BR/>That said, here's a counterexample. Harvey Friedman, a logician, has been developing Boolean relation theory, relating to properties of ordinary mathematical objects like functions on sets of integers. It has natural questions that would interest any combinatoricist, and it has theorems that are provably equivalent to large cardinals. He's written a lot about it on the FOM mailing list. Go to <A HREF="http://cs.nyu.edu/mailman/listinfo/fom" REL="nofollow"><BR/>http://cs.nyu.edu/mailman/listinfo/fom<BR/></A> and search for Boolean Relation Theory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71049095413009983792007-11-07T08:44:00.000-06:002007-11-07T08:44:00.000-06:00This comment has been removed by the author.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15099733629828295922007-11-07T08:32:00.000-06:002007-11-07T08:32:00.000-06:00(This is Bill Gasarch)Anon: I thought the numberof...(This is Bill Gasarch)<BR/><BR/>Anon: I thought the number<BR/>of natural problems ind<BR/>of ZFC was very very small,<BR/>but would be happy to hear<BR/>(and blog) about this.<BR/>Email me privately and<BR/>we'll discuss.<BR/><BR/>Also: good point, its not<BR/>WHO proved the result<BR/>that matters. What I<BR/>was getting at is that <BR/>a problem that someone<BR/>(probably a logician)<BR/>comes up with that nobody<BR/>in math ever heard of<BR/>before, just to find<BR/>something ind (e.g.,<BR/>Large Ramsey Theorem)<BR/>is not as natural as<BR/>a problem that someone<BR/>(prob not a logician)<BR/>was honestly working on<BR/>and found to be ind.<BR/>(CH, and the subject<BR/>of my post).GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6708724475762871002007-11-06T14:14:00.000-06:002007-11-06T14:14:00.000-06:00Are you saying it's a stupid question just because...Are you saying it's a stupid question just because it's independent of ZFC?<BR/><BR/>There are plenty of natural problems that turn out to be ZFC independent. The Whitehead problem is an excellent example. Of course, their density in mathematics as a whole is quite low, but there are plenty of natural examples out there.<BR/><BR/>You also seem to think independence results are more worthwhile if they're proved by nonlogicians. Why is the result more or less worthwhile depending on who proved it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69088691304346399512007-11-06T10:48:00.000-06:002007-11-06T10:48:00.000-06:00Someone was telling me at Dagstuhl that Hugh Woodi...Someone was telling me at Dagstuhl that <A HREF="http://en.wikipedia.org/wiki/W._Hugh_Woodin" REL="nofollow">Hugh Woodin</A> (who was at MIT for a year when Bill and I were both doing logic) has a new argument that CH "ought to be" false -- in fact that the cardinailty of the continuum "ought to be" exactly <I>aleph-two</I> The reference is Notices of the AMS 48 (2001), (6) 567-576 and (7) 681-690..Anonymousnoreply@blogger.com