Forcing over set theory versus forcing over arithmetic - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T04:52:34Z http://mathoverflow.net/feeds/question/100792 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100792/forcing-over-set-theory-versus-forcing-over-arithmetic Forcing over set theory versus forcing over arithmetic Timothy Chow 2012-06-27T17:17:31Z 2012-06-28T01:24:51Z <p>I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some papers where they prove results such as, for certain \$M\$ and certain \$G\$, if \$M[G]\$ doesn't satisfy Buss's \$S_2\$, then NP ≠ co−NP. Krajíček's book <i>Bounded Arithmetic, Propositional Logic, and Complexity Theory</i> also touches on this topic, showing how to recast some lower-bound proofs in complexity theory as forcing arguments.</p> <p>These connections are intriguing but I don't understand them well enough yet to be able to make up my mind whether this is mostly a curiosity or whether it has the potential to lead somewhere new and interesting. One thing that I'd like to know is the degree to which constructions in set theory carry over (or are likely to carry over) to arithmetic. Perhaps a slightly more precise phrasing is,</p> <blockquote> <p>Where and how does the parallel between forcing over set theory (ZFC, say) and forcing over arithmetic (or bounded arithmetic) break down?</p> </blockquote> <p>Another way to put it might be, is there any sketch of a program (even if a wildly optimistic one) for carrying over ideas from set theory to arithmetic in such a way as to prove new lower bounds in complexity theory? A result like the theorem by Takeuti and Yasumoto that I cited above is a start, but doesn't quite count in my mind unless we have some reason to think that insights from set theory will help us understand the properties of \$M[G]\$. Can we hope for this or are there some basic obstacles that make this approach highly unpromising?</p> http://mathoverflow.net/questions/100792/forcing-over-set-theory-versus-forcing-over-arithmetic/100829#100829 Answer by Ali Enayat for Forcing over set theory versus forcing over arithmetic Ali Enayat 2012-06-28T01:24:51Z 2012-06-28T01:24:51Z <p>Forcing in set theory is usually performed to <em>extend</em> a model of set theory to another model \$M[G]\$ of set theory in which this or that statement of set theory (such as the continuum hypothesis) changes its truth-value. On the other hand, forcing over a model of arithmetic \$M\$ does not produce an extension of \$M\$, but a rather an <em>expansion</em> \$(M,G)\$. </p> <p>A serious stumbling block for the application of forcing in \$PA\$ (Peano Arithmetic) to obtain independence results is a theorem of Gaifman that states that if \$M\$ and \$N\$ are models of \$PA\$ such that \$M\$ is cofinal in \$N\$, then \$M\$ is an <em>elementary submodel</em> of \$N\$, and in particular, \$M\$ and \$N\$ satisfy the same set of arithmetical sentences. Gaifman's proof, by the way, heavily relies on the so-called MRDP theorem (which states that every r.e. set is Diophantine).</p> <p>Forcing has had an enormous success in clarifying definability questions in both arithmetic and set theory, but in comparsion, it has had rather limited efficacy so far in complexity theory, certainly not due to lack of effort or expertise: I know more than one expert in computational complexity whose résumé includes first rate papers on set-theoretical forcing. </p>