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


  • $\begingroup$ 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. $\endgroup$ Feb 24 '18 at 13:45
  • $\begingroup$ I've updated my answer. The new argument is arguably a bit more complicated but it has the major advantage of being correct ;-) $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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