tag:blogger.com,1999:blog-3722233.post117553656413171294..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: What to make of the Ind of CH ?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-3722233.post-1176264691925135732007-04-10T23:11:00.000-05:002007-04-10T23:11:00.000-05:00The most plausible candidate for settling the Cont...The most plausible candidate for settling the Continuum Hypothesis (Freiling's symmetry axiom) has the disadvantage that, when combined with the plausible assumption that any subset of the reals of cardinal less than c will have measure zero, it will imply that the continuum cannot be well ordered.<BR/><BR/>On the other hand, why should we simultaneously believe both the Power Set Axiom and the Axiom of Choice?Josephhttps://www.blogger.com/profile/17628462611143681921noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175717323756864262007-04-04T15:08:00.000-05:002007-04-04T15:08:00.000-05:00Here is a related question that puzzles me.We do n...Here is a related question that puzzles me.<BR/>We do not know whether ZFC is consistent, but if it is, does that imply that ZFC can only prove statements about the integers that are satisfied by the true integers?<BR/>One could imagine that ZFC is consistent, but that each model has a set of integers which, in addition to the true integers, contains "pathological" objects which make it satisfy equations that are not satisfied in the true integers.<BR/>Can that possibility be ruled out?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175707660578177532007-04-04T12:27:00.000-05:002007-04-04T12:27:00.000-05:00Pascal: This kind of example is what I have mind w...Pascal: This kind of example is what I have mind when I talk about the integers having some kind of minimal model.<BR/><BR/>For a statement of the type "these equations in k variables have no integer solutions" we can for each k-tuple of integers prove that it is not a solution, but the original statement is itself unprovable. So if we add the statement as an axiom we still have the same integers and a new axiom to prove theorems with.<BR/><BR/>However if we, for the same equations, add the axiom "these equations in k variables have an integer solution", then we have a new axiom, and since no k-tuple of ordinary integers satisfy the equations we have also stated that there exists some additional objects which we include among the integers, and they do satisfy the equations.<BR/><BR/>But for the set theoretic axioms it seems harder to talk about smaller and larger models in this way.Klas M.https://www.blogger.com/profile/12139529373633774114noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175696530184565492007-04-04T09:22:00.000-05:002007-04-04T09:22:00.000-05:00Klas: I certainly do not have such an example, but...Klas: I certainly do not have such an example, but perhaps the more knwoledgeable readers of this blog can answer your question?<BR/><BR/>Actually, I can cook up a stupid example: take a diophantine equation which is not satisfiable, and whose unsatisfiability is not provable in ZFC. Add its unsatisfiability as a new axiom.<BR/><BR/>The problem is that this is not a "natural" set-theoretic axiom such as CH, and moreover I can't actually show you the equation (it wouldn't fit on this blog).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175695179017106762007-04-04T08:59:00.000-05:002007-04-04T08:59:00.000-05:00Pascal: Do we have any concrete examples of this k...Pascal: Do we have any concrete examples of this kind where we can say that one choice of "exotic" axiom let us gain more than another choice?Klas M.https://www.blogger.com/profile/12139529373633774114noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175693473703337542007-04-04T08:31:00.000-05:002007-04-04T08:31:00.000-05:00Klas: I guess the issue is, whether by adding "exo...Klas: I guess the issue is, whether by adding "exotic" set-theoretic axioms (such as e.g. CH or large cardinals axioms) you can prove more "combinatorial" results (about e.g. the satisfiability of diophantine equations) ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175688933522510042007-04-04T07:15:00.000-05:002007-04-04T07:15:00.000-05:00Pascal: I am not a set theorist either, I'm in com...Pascal: I am not a set theorist either, I'm in combinatorics, so I shouldn't stick my neck out too far here.<BR/><BR/>My impression is that the integers and set theory in general are slightly different. For the integers there is at least some way of making sense of a "smallest" model for them, in terms of which objects are included in the model, and I guess that would be what most people would call the "real integers". <BR/><BR/>However for set theoretic axioms like the Axiom of Choice or CH there only seems to different models rather than some which are smaller and some which are larger. For example, if we remove AC then we can add the axiom that all sets are measurable, and we suddenly get many new theorems which are not true with AC, like all linear functions being continuous, and if we add AC we get more objects, like non-measurable sets, and fewer theorems about them.Klas M.https://www.blogger.com/profile/12139529373633774114noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175679990999846462007-04-04T04:46:00.000-05:002007-04-04T04:46:00.000-05:00It's all in the red book I guess you mean:http://w...<I> It's all in the red book </I><BR/><BR/>I guess you mean:<BR/><A>http://www.amazon.com/Arithmetic-Propositional-Encyclopedia-Mathematics-Applications/dp/0521452058/ref=sr_1_1/002-5707863-3608822?ie=UTF8&s=books&qid=1175679430&sr=1-1</A><BR/><BR/><BR/>I'll look it up then.<BR/><BR/>ThanksAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175678447299301002007-04-04T04:20:00.000-05:002007-04-04T04:20:00.000-05:00I know almost nothing about set theory, but that d...I know almost nothing about set theory, but that doesn't prevent me from having an opinion about the issue raised by klas m.<BR/><BR/>When we're talking about "exotic" stuff like large cardinals or CH, I would tend to agree that all set theories should be treated on an equal footing (provided that they're not downright inconsistent).<BR/><BR/>However, set theory can in principle have an impact on such "concrete" questions as the satisfiability of diophantine equations:<BR/>By Matyasevitch, we know that there must exist diophantine equations whose satisfiability is independent of ZFC (or o f your favorite alternative system).<BR/>I would argue that one set theory is better than another set theory if it proves more true statements about the satisfiability of diophantine equations (and of course does not prove any wrong statement!)<BR/>This makes sense only if you believe that that there is a "true" set of the integers, but who doesn't?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175676339171161532007-04-04T03:45:00.000-05:002007-04-04T03:45:00.000-05:00I think that the main problem here is that people ...I think that the main problem here is that people assume that there is a "correct" choice of axioms. People used to think the same thing about the parallel postulate, but nowadays we know that this is actually an axiom and that there are essentially different, but equally useful, kinds of geometry depending on which type of parallel axiom one chooses.<BR/><BR/>I can't see why we should treat set theory differently. Just as we have several different geometries to study we have several different kinds of set theory. All of them equally correct.Klas M.https://www.blogger.com/profile/12139529373633774114noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175670514577163232007-04-04T02:08:00.000-05:002007-04-04T02:08:00.000-05:00What's the red book ?What's the red book ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175641702105798742007-04-03T18:08:00.000-05:002007-04-03T18:08:00.000-05:00In a formalization of ZFC you can define the conce...In a formalization of ZFC you can define the concepts of "propositional formula" and "propositional tautology" in a straightforward manner. <BR/><BR/>So, I mean proof system in the Cook-Reckhow sense where you take the input formula \tau, and then convert into its encoding in your formalized ZFC. Then, using some standard first-order proof system with the axioms of set theory, you prove the sentence stating that this particular propositional formula is a tautology.<BR/><BR/>This is proof system in the Cook-Reckhow sense, provided you choose a natural polytime encoding of formulas and tautologies.<BR/><BR/>It's all in the red book.<BR/><BR/>--- Perfesser Nines ToesAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175633539500837712007-04-03T15:52:00.000-05:002007-04-03T15:52:00.000-05:00To #12:what do you mean by propositional tautologi...To #12:<BR/>what do you mean by <BR/><I>propositional tautologies that require superpolynomially large proofs in ZFC</I>?<BR/><BR/>That is, what do you mean by a proof in ZFC (or any other first order system) of a <I>propositional</I> tautology?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175633244421332132007-04-03T15:47:00.000-05:002007-04-03T15:47:00.000-05:00Is a blog post on S^_2 or S^1_2 on the menu?What?<I>Is a blog post on S^_2 or S^1_2 on the menu?</I><BR/><BR/>What?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175630773087363612007-04-03T15:06:00.000-05:002007-04-03T15:06:00.000-05:00Well, we do have all kinds of weird crap going on....Well, we do have all kinds of weird crap going on... for example, the partial consistency stuff of Krajicek and Pudlak shows that if NEXP \neq coNEXP, then there are <I>propositional</I> tautologies that require superpolynomially large proofs in ZFC, but would have polysize proofs in some other system.<BR/><BR/>What that other system is not entirely clear- the natural thing to guess is that it would be ZFC + some large cardinal or determinacy stuff and that somehow yields a proof of soundness for some slick method of proving certain propositional statements. But there's no reason to suspect that, it may be that the extra-ZFC principles that help map out the subsets of the reals are totally different from ones that help us succinctly validate tautologies.<BR/><BR/>Perfesser Nine ToesAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175628818972901392007-04-03T14:33:00.000-05:002007-04-03T14:33:00.000-05:00Is a blog post on S^_2 or S^1_2 on the menu?Is a blog post on S^_2 or S^1_2 on the menu?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175621147051523322007-04-03T12:25:00.000-05:002007-04-03T12:25:00.000-05:00Miki Ajtai ... thinks it will be independent of .....<I>Miki Ajtai ... thinks it will be independent of ... ZFC</I><BR/><BR/>That's quite amazing. <BR/>Maybe a more `feasible' question is:<BR/><BR/>Assuming P!=NP (or other computational hardness conjecture of the kind), is it true that there are no short (ZFC/PA) proofs of P!=NP?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175617972602519622007-04-03T11:32:00.000-05:002007-04-03T11:32:00.000-05:00A propos of Kurt and anonymous' comments on the po...A propos of Kurt and anonymous' comments on the potential independence of P vs NP:<BR/><BR/>Miki Ajtai, who has a record on these kinds of complexity questions that is nonpareil, is among those who think it will be independent. At a DIMACS workshop in 2000 in which a number of leaders in the field gave their opinions about the resolution of open complexity questions, he conjectured that P vs NP was independent. When asked to clarify whether he meant independent of Peano arithmetic, to the surprise of many in the room he clarified that he meant independent of ZFC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175603834189897282007-04-03T07:37:00.000-05:002007-04-03T07:37:00.000-05:00Is there any result along those lines?Yes, I think...<I> Is there any result along those lines?</I><BR/><BR/>Yes, I think there are some results showing the independence of P != NP from considerably weak arithmetic.<BR/>I think that results of A. Razborov and Ran Raz show that "SAT has no poly-size circuits" has no small resolution proofs, which then implies an independent result on a very weak arithmetic formal system of the P!=NP problem. <BR/> <BR/>Razborov has some more results on this I think. If I'm not wrong, he showed that if a plausible cryptographic assumption holds then P!=NP is independent of some weak subsystem of Peano Arithmetic (relativized S^2_2 and relativized S^1_2).<BR/><BR/>Gaisi Takeuti had also some papers from the '90s about forcing and P!=NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175585998396165282007-04-03T02:39:00.000-05:002007-04-03T02:39:00.000-05:00Like all statements of finite combinatorics, PNP i...Like all statements of finite combinatorics, P<>NP is a property of the set of integers which can be written down as a first-order formula in the language of rings (+,*,=).<BR/>We have to figure out whether this formula is satisfied by the set of "true" integers.<BR/><BR/>If one would like to prove an independence result, it seems reasonable to start not with the all-powerful ZFC system but with some weaker system for proving properties of the integers, such as e.g. Peano arithmetic (or perhaps some even weaker system). Is there any result along those lines?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175555024900960532007-04-02T18:03:00.000-05:002007-04-02T18:03:00.000-05:00My advisor, Carl Jockusch Jr., told me that Paul C...My advisor, Carl Jockusch Jr., told me that Paul Cohen himself believed that the CH fails badly--that there are unimaginably many infinities between aleph_0 and 2^{aleph_0}. <BR/><BR/>For what it's worth, I believe this too.<BR/><BR/>Zermelo "observed" his axioms of Set Theory as properties of his mental model of the cumulative hierarchy of sets. It turns out that these axioms are pretty much what you need to prove the validity of definition by transfinite induction, and I don't believe this is an accident. [The exceptional axiom, as usual, is foundation, but this easy to observe -- the witness for a given non-empty set is just an element of minimal rank, and therefore foundation is essentially the hypothesis with the Zermelo model that the ordinals are well ordered.]<BR/><BR/>Frankel's axiom of regularity came afterwards, and it was clearly informed by the notion that setness vs. proper classness is a matter of size -- i.e., if a class can be put into 1-1 correspondence with a set, then it is "small," and therefore gets to be a set too. This, too, is observable in Zermelo's model, as long as you assume that the ordinals don't have a small (set-like) cofinality. <BR/><BR/>Note that Frankel's intuition is radically different here that Zermelo's -- you get to be a Frankel set by being "small," whereas you get to be a Zermelo set by being "finished." It is more startling that people seem to realize that such different views about "what makes a set" seem to be consistent with one another. <BR/><BR/>From a Continuum Hypothesis point of view, ZF says less than it should about the power set operator. Remember, each successor level of the Cumulative Hierarchy consists of the power set of the preceding level, and therefore the power set operator is absolutely central to mental construction, so this is essentially an incompleteness of the model as well as the theory. The CH is merely the assumption that power sets are small, and the standard (V=L) proof of relative consistency proof for ZF+GCH over ZF is little more than a working out of the consequences of having the smallest possible power sets.<BR/><BR/>So why do I stand with Cohen on the CH? The power set is a representation-free version of the exponential function, which enables its extension to the infinite. My experience (based admittedly on the finite) is that the exponential function grows very quickly, and there is a lot of room between successive iterates of the exponential function. I carry this intuition to the infinite, and conclude that the Continuum Hypothesis is false, and badly so.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175550679301010942007-04-02T16:51:00.000-05:002007-04-02T16:51:00.000-05:00Well, if no one else is going to state the obvious...Well, if no one else is going to state the obvious, I guess I will: some people have suggested that P vs. NP is independent of ZFC. A couple of them have evidently even gone so far as to <A HREF="http://www.win.tue.nl/~gwoegi/P-versus-NP.htm" REL="nofollow">prove it</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175549984070785152007-04-02T16:39:00.000-05:002007-04-02T16:39:00.000-05:00Harvey Friedman showed that there are fairly basic...Harvey Friedman showed that there are fairly basic mathematical statements that are not decided in ZFC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175547784422397122007-04-02T16:03:00.000-05:002007-04-02T16:03:00.000-05:00I think two camps in phil of math would accept (2)...I think two camps in phil of math would accept (2), or at least a variation of it: fictionalists and intuitionists. Fictionalists think that asking these questions (or any mathematical questions) about the reals is like asking questions about a fictional story. Some have a "real" answer, e.g. was Huck Finn male or female (it is *true* that he <BR/>is a male, according to the story) but others are simply beyond the scope of the story ("what did Huck Finn have for breakfast the day before he met Tom?"). In my opinion, the debate is pretty boring if we consider mathematical statements <BR/>like CH. It's much more interesting when the statements are used as part of a mathematical theory about empirical phenomena in the world (like physics)... Hartry Field does a lot with this.<BR/><BR/>A fun quote from Michael Dummett:<BR/><BR/>"We are, after all, being asked to choose between two metaphors, two pictures. The platonist metaphor assimilates mathematical enquiry to the investigations of the astronomer: mathematical structures, like galaxies, exists, independently of us, in a realm of reality which do not inhabit but which those of us who have the skill are capable of observing and reporting on. The constructivist metaphor assimilates mathematical activity to that of the artificer fashioning objects in accordance with the creative power of his imagination. ...the activities if the mathematician seem strinkingly unlike those either of the astronomer or of the artist. What basis can exist for deciding which metaphor is to be preferred?...We have first to decide on the correct model of meaning - either an intuitionistic one...or a platonistic one...and then one or other picture of the metaphysical character of mathematical reality will force itself on us."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1175546367442697262007-04-02T15:39:00.000-05:002007-04-02T15:39:00.000-05:00It should be noted that Both Godel's and Cohen's r...It should be noted that Both Godel's and Cohen's results are <I>relative</I> consistency results.<BR/><BR/>Godel prove that if ZF has a model than ZFC + CH has a model.<BR/><BR/>Cohen proved that if ZF has a model that ZFC + not CH has a model. (He also proved ZF + not choice has a model).<BR/><BR/>Godel's Second Incompleteness Theorem says that this is the best you can get unless ZF is actually inconsistent.Anonymousnoreply@blogger.com