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

Assume that $(P,\le)$ is a notion of forcing. There are several ways to define what it means for $P$ being proper and I would like to know: What is the complexity (in terms of the Levy-Hierarchy) of the statement 'P is proper'?

share|cite|improve this question
up vote 5 down vote accepted

Properness is observable in any sufficiently large $V_\alpha$, and therefore has complexity $\Sigma_2$. In oktan's answer, it suffices to consider sufficiently large $\lambda$, rather than all $\lambda$. I think this is proved in some of the standard accounts of proper forcing.

share|cite|improve this answer
Shelah's "proper and improper forcing", Jech's "multiple forcing" and the chapter on proper forcing in the Handbook all have proofs of this result. – Andrés E. Caicedo Nov 3 '10 at 14:28
Could you expand on that? Any property of anything is observable in a sufficiently large $V _{\alpha}$ (if I'm understanding you correctly), that's just the Reflection Theorem. But it's not the case that any property is $\Sigma _2$. – Amit Kumar Gupta Nov 5 '10 at 2:45
Every statement of the form "$\exists\alpha V_\alpha\models\psi$" is equivalent to a $\Sigma_2$ statement, regardless of the complexity of $\psi$, and conversely all $\Sigma_2$ statements can be expressed in this form. One direction is easy. For the other direction, you do a little Lowenheim-Skolem argument. (You can use $H_\kappa$ instead of $V_\alpha$ if you prefer, and the argument may be more attractive that way.) I can post the argument here later, if you like. – Joel David Hamkins Nov 5 '10 at 12:49
Which formulation of properness are you using that says $P$ is proper iff "$\exists \alpha V _{\alpha} \vDash \psi$" – Amit Kumar Gupta Nov 5 '10 at 16:04
Andres, sorry if I'm being dense, but I've looked through those three sources and can't seem to find this result or something obviously equivalent to it in them. Any chance you can specify where in one of those books/articles this result can be found? Thanks. – Amit Kumar Gupta Nov 5 '10 at 20:16

I think that I might have found a solution to this rather dispensable question. I will sketch it:

Consider the following characterization of properness:

$P$ is proper iff for all $\lambda > 2^{|P|}$ there is a club $C$ of elementary submodels $M \prec (H_{\lambda},...)$ such that $\forall p \in P \, \exists q \le p$ ($q$ is $ (M,P)$-generic). The latter statement will be denoted by $\psi(P)$

Now the part ..there exists a club $C$... can be written as $\exists C \in P(H_{\lambda})$ $\varphi(C,...)$, moreover '$C$ is a club' is $\Delta_0$, hence this part doesn't increase the order of $\psi(P)$. Further the formula $x= tc(y)$ is a $\Delta_1$ formula, hence $ C \in P(H_{\lambda})$ is $\Pi_1$.

Next the statement $M \prec (H_{\lambda},..)$ can be written as a $\Pi_1$-formula with $\lambda, M$ as parameters so this doesn't increase the complexity.

Last the statement '$p$ is $(M,P)$-generic' can be written as a formula with paramters $M,P,p$ by the following characterization:

$p$ is $(M,P)$-generic iff $\forall \dot{\alpha}$ $\in M$ $\forall r \le p$ $\exists s \le r$ $\exists \beta \in M$ $s \Vdash \dot{\alpha} = \beta$.

The relation $ s \Vdash \dot{\alpha} = \beta$ is $\Delta_0$ with parameter $P$ hence '$p$ is ($M,P$)-generic' is a $\Delta_0$ formula again.

Thus '..there exists a club $C$...' is $\exists C \in P(H_{\lambda}) \varphi(C,..)$ which is a $\Sigma_2$ formula. Thus '$P$ is proper' can be written as $\forall \lambda > 2^{|P|}$ $\sigma(P, \lambda)$ with $\sigma$ a $\Sigma_2$-formula, which is a $\Pi_3$ formula.

share|cite|improve this answer
oktan, your last formulation is more complex than $\Pi_1$, because saying that $\lambda\gt 2^P$ has a complexity cost. – Joel David Hamkins Nov 3 '10 at 11:31
Ah thank you very much – Stefan Hoffelner Nov 3 '10 at 11:33
Also, in general bounding a quantifier by a power set does not count as a bounded quantifier, and so does not retain $\Delta_0$ complexity. – Joel David Hamkins Nov 3 '10 at 14:49
I made even more mistakes in my answer. I will fix it soon – Stefan Hoffelner Nov 3 '10 at 15:48
Hi oktan, why is $M \prec (H_{\lambda}, \dots)$ a $\Pi _1$ relation? Also don't your $M$ have to be countable? I haven't thought about it, would that increase the complexity? It's probably the case that the particular formulation you're working with here isn't optimal for computing the complexity of '$P$ is proper'. – Amit Kumar Gupta Nov 5 '10 at 3:08

How about the Proper Game formulation?

$(P, \leq, 1)$ is proper iff

$\exists > \Sigma \\ \forall \pi \\ \forall p \in > P :$

  • IF $\forall x \in \pi [x$ is an ordered pair $(x_1, x_2)$, $x_1$ is natural, and $1 \Vdash _P\\ (x_2$ is an ordinal$)]$
  • THEN $\Sigma (p, \pi)$ is an ordered pair $(q, \sigma)$ such that:
    1. $\forall y \in \sigma\\ [y$ is an ordered pair $(y_1,y_2)$, $y_1$ is natural, and $y_2$ is an ordinal$]$
    2. $q \in P\\ $ is such that:
      i. $q \leq p$
      ii. $\forall x \in \pi\\ [q\\ \Vdash _P\\ \left ( \exists y \in > \sigma \right )\left (x_2 = > y_2\right )] $

In other words this is saying there's a strategy $\Sigma$ for player II such that for any play from player I, consisting of a condition $p$ and a (partial) $\omega$-sequence of $P$-names for ordinals $\pi$, $\Sigma (p, \pi)$ produces a condition $q$ extending $p$, and a (partial) $\omega$-sequence of ordinals $\sigma$ such that $\forall n \in \mathrm{dom} (\pi),\\ q \Vdash \exists k \in \mathrm{dom} (\sigma) (\pi (n) = \sigma (k))$.

share|cite|improve this answer
I considered this formulation first when I tried to answer the question, but I wasn't sure how to write : 'II has a winning strategy' in a correct way. However the formulation which I chose for my answer above isn't optimal as it leads to a $\Pi_3$ formula, which isn't best posssible according to Joel. I think that the first formulation of properness from theorem 2.8. in chapter III in Shelahs Proper Forcing book leads to a $Sigma_2$ formulation too, but it's rather annoying to really check it step by step. – Stefan Hoffelner Nov 6 '10 at 9:03

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.