# Forcing over set theory versus forcing over arithmetic

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 Bounded Arithmetic, Propositional Logic, and Complexity Theory also touches on this topic, showing how to recast some lower-bound proofs in complexity theory as forcing arguments.

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,

Where and how does the parallel between forcing over set theory (ZFC, say) and forcing over arithmetic (or bounded arithmetic) break down?

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?

-
Can you recommend a good general reference for forcing over models of arithmetic? (for someone who knows the set theory side, but not the arithmetic side very well) – Justin Palumbo Jun 27 '12 at 17:22
Justin: A good place to begin is "The structure of models of Peano Arithmetic" by Kossak and Schmerl. – Andrés Caicedo Jun 27 '12 at 17:28
You might be interested in Krajíček’s “Forcing with random variables and proof complexity”. – Emil Jeřábek Jun 28 '12 at 7:02

Forcing in set theory is usually performed to extend 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 expansion $(M,G)$.
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 elementary submodel 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).
I was re-reading your answer today and realized that I was not sure what you meant by an "expansion." From your next paragraph, I inferred that it meant a model $N$ such that $M$ is cofinal in $N$, but is that correct? – Timothy Chow Jan 1 at 2:52