Finding a countable ordinal $\alpha$ such that the least level of $L$ containing a surjection of $\omega$ onto $\alpha$ satisfies a $\Sigma_1$ formula

Question

While preparing for an upcoming qualifying exam, I came across the following problem:

Work in the constructible universe $L$. For each $\alpha < \omega_1$ let $\beta(\alpha) \geq \alpha$ be least so that $L_{\beta(\alpha) + 1}$ has a surjection of $\omega$ onto $\alpha$. Let $S \subseteq \omega_1$. Let $\varphi$ be a $\Sigma_1$ formula so that $L \models \varphi[S]$. Prove the following: There is an $\alpha < \omega_1$ so that $L_{\beta(\alpha)} \models \varphi[S \cap \alpha]$.

So far, I have shown, using reflection, the Löwenheim-Skolem theorem, and the Mostowski collapsing theorem, that there is a countable transitive set $N$ containing an ordinal $\alpha$ such that $N \models \varphi[S \cap \alpha]$ (this was an earlier part of the same problem). However, I don't see how to finish the argument from here. Also, where is the assumption that $\varphi$ is $\Sigma_1$ being used?

Answer 1

Here is a series of steps to guide your towards a solution.

Step 1: Prove that if $L\models\varphi(S)$, then $L_{\omega_2}\models\varphi(S)$. Here we use that $\varphi$ is $\Sigma_1$.

Step 2: Let $M\prec L_{\omega_2}$ such that $S\in M$, let $\pi$ be the Mostowski collapse of $M$ to some $L_\rho$, and let $\alpha=\pi(\omega_1)$ under the collapse. Argue that $\rho\leq\beta(\alpha)$. Moreover, show that $\alpha=\omega_1^{L_{\beta(\alpha)}}=\omega_1^{L_\rho}$, and that $S\cap\alpha\in L_{\beta(\alpha)}$, and that in fact $\pi(S)=S\cap\alpha=S\cap L_{\beta(\alpha)}$.

Step 3: Use the fact that $\varphi$ is $\Sigma_1$ to finish the proof.