# Show that a formula $\phi(v)$ is $\Sigma_2$ iff the following holds

So the question is from Ralf Schindler's set theory.

Let our language be the language of Set-theory.

Show that a formula $\phi(v)$ is $\Sigma_2$ iff there is a formula $\phi'(v)$ such that

$\textbf{ZFC}\vdash\ \forall v(\phi(v)\iff\ \exists\ \alpha\ R(\alpha) \models\ \phi'(v))$

My question is are there any natural choices for $\phi'(v)$.

My (best) attempt was to let $\phi'(v)$ = $\exists\ \alpha\$Sat$(R(\alpha), \phi(v))$, but was still unsuccessful.

("Sat" is the formalization of the notion of satisfaction in language of set theory)

Hence any help or insight is appreciated

Cheers

• My office mate has brought to my attention that my argument doesn't work. I will correct my answer shortly (and provide more details). But first let me make sure that there isn't an issue with my revised proof. Feb 24 '18 at 13:45
• I've updated my answer. The new argument is arguably a bit more complicated but it has the major advantage of being correct ;-) Feb 24 '18 at 15:13

I assume you already know why $$\exists \alpha \in \mathrm{Ord} R(\alpha) \models \phi'(v)$$ is $\Sigma_2$. I will show the converse:

Let $$\phi'(v) \equiv \phi(v) \wedge \omega \text{ exists } \wedge \chi,$$

where $\phi(v) \equiv \exists a \forall b \bar{\phi}(v,a,b)$ with $\bar{\phi} \in \Sigma_0$ and $\chi$ says 'strong choice holds and there is no largest cardinal'. More precisely $$\chi \equiv \forall x \exists f \exists \alpha \in \mathrm{Ord} \colon f \colon \alpha \overset{\text{onto}}{\to} x \wedge \forall \beta \in \mathrm{Ord} \exists \gamma \in \mathrm{Ord} \forall f \colon \beta \to \gamma \colon \gamma \neq f" \beta.$$ I claim that, for any given $v$, $$\phi(v) \iff \exists \alpha \in \mathrm{Ord} \colon R(\alpha) \models\phi'(v).$$

Suppose that $\phi(v)$ holds for $v \in V$. Let $\alpha > \omega$ be a Beth fixed point such that $v \in R(\alpha)$ and such that for all $a \in R(\alpha)$, if there is some $b$ such that $\neg \bar{\phi}(v,a,b)$ holds, then there is some such $b$ in $R(\alpha)$. A straightforward computation shows: $$R(\alpha) \models \phi'(v).$$ (Use that $\alpha$ is a Beth fixed point + choice in $V$ to conclude that $R(\alpha)$ satisfies strong choice. Since $\alpha$ is a limit of $V$-cardinals, it trivially holds that $R(\alpha)$ has no largest cardinal. Finally use the closure of $R(\alpha)$ under the $b$'s as above to conclude that $R(\alpha) \models \phi(v)$.)

The converse is where I got it wrong the first time. I had essentially the right idea (ensuring that $R(\alpha)$ is closed under certain witnesses) but my previous formula $\phi'(v)$ didn't manage to ensure that. The new formula does and here is why:

Let $v \in V$ be such that $\neg \phi(v)$ and let $\alpha \in \mathrm{Ord}$ be such that $v \in R(\alpha)$ and $R(\alpha) \models \chi \wedge \omega \text{ exists}$. We show that $R(\alpha) \models \neg \phi(v)$.

Let $a \in R(\alpha)$ and fix $\omega \le \beta < \alpha$ such that $a,v \in R(\beta)$. Then (by assumption) $$V \models \exists b \colon \neg \bar{\phi}(v,a,b).$$ Let $H \subseteq V$ be a $\Sigma_{1}$-elementary substructure of size $\mathrm{card}(R(\beta))$ such that $R(\beta) \subseteq H$. Let $\bar{H}$ be the transitive collapse of $H$. Observe that $$\bar{H} \models \exists b \colon \neg \bar{\phi}(v,a,b).$$ If $\bar{H} \subseteq R(\alpha)$ $(\dagger)$ then, by $\Sigma_{0}$-absoluteness, the same witness $b \in \bar{H}$ shows that $$R(\alpha) \models \exists b \colon \neg \bar{\phi}(v,a,b).$$ Hence it suffices to show to verify $(\dagger)$: We have $\bar{H} \in H_{\beth_{\beta}^+} \subseteq R(\beth_{\beta}^+)$. So we only need to show that $\alpha \ge \beth_{\beta}^+$. It suffices to prove that $\alpha$ is a Beth fixed point (since this implies that $\alpha$ is a limit cardinal). But this is straightforward: For $\beta < \alpha$ we have that $R(\omega + \beta)^{R(\alpha)} = R(\omega + \beta)$ and, by our choice of $\phi'(v)$, $$R(\alpha) \models \exists \gamma \in \mathrm{Ord} \exists f \colon \gamma \overset{\text{onto}}{\to} R(\omega + \beta).$$ It follows that $\beth_{\beta} \le \gamma < \alpha$. Q.E.D.