MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 E. 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
up vote 16 down vote accepted

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).

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.

share|cite|improve this answer
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
In model theory an expansion of a structure is obtained by adding new relations, functions, or constants to the structure without changing anything else in the structure (and in particular, not changing the domain of discourse of the structure). – Ali Enayat Jan 1 at 9:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.