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

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?

• I think I answered this before. Commented Aug 26, 2020 at 17:35
• Okay, not exactly, but close enough, so it might be helpful: math.stackexchange.com/questions/3707515/… Commented Aug 26, 2020 at 17:39

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.