# Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence

I am generally interested in the forcing method used by Baker-Gill-Solovay and Cohen. I am looking for as many sources as I can get my hands on concerning either the technique itself or its use. Does anyone have suggestions?

• who points out that its the same technique? – vzn Oct 26 '12 at 5:02

For more uses of forcing (via so-called generic oracles) in complexity theory, see The Oracle Builder's Toolkit (freely available from Fortnow's homepage) by Fenner, Fortnow, Kurtz, and Li. They give a general theory of generic oracles, and show its many applications in complexity.

If you're interested in how oracles in complexity are like independence proofs in set theory, you might be interested in the following papers:

For the uses of forcing in set theory, see the book Set Theory (Set Theory on Amazon) by Jech, especially Parts II and III of the book (not to be confused with "Introduction to Set Theory" by Hrbáček and Jech).

For an excellent introduction to forcing in set theory, there's Timothy Chow's famous USENET post "Forcing for dummies" as well as the more formal paper that arose from it, "A beginner's guide to forcing".

For uses of forcing like techniques in proof complexity you might want to look at:

The method of proof is an arithmetical analogue of forcing (of a kind already used by Paris and Wilkie). More combinatorial (and improved lower bounds) are in J. Krajıcek, P. Pudlak, and A. Woods, Exponential lower bounds to the size of bounded depth Frege proofs of the pigeonhole principle, Random Structures Algorithms, 7 (1995), pp. 15–39. and T. Pitassi, P. W. Beame, and R. Impagliazzo, Exponential lower bounds for the pigeonhole principle, Comput. Complexity, 3 (1993), pp. 97–140.

• Establishing super-polynomial size lower bounds on propositional proofs for a (uniform) family of propositional statements implies the independence of the corresponding first- (or second-) order formula in the corresponding first- (or second-) order formal theory. E.g., the pigeonhole principle is independent (i.e., true in the standard model, but unprovable) of $V^0$, namely, the theory of "$AC^0$ reasoning" which corresponds to constant-depth Frege (this is NOT resolution); (I use here the terminology of Cook & Nguyen, Logical Foundation of Proof Complexity, 2010; See Cor. VII.2.4 there). – Iddo Tzameret Nov 2 '12 at 5:15