5
$\begingroup$

For an ordinal $\alpha$, let $L_\alpha$ be the $\alpha^{th}$ set of Gödel's constructible hierarchy and let $\omega_1^{\mathrm{CK}}$ be the first non-recursive ordinal or the first admissible ordinal after $\omega$.

Question : does there exists a $\Sigma_2$ formula able to capture that we reached, in Gödel's construction, the $\omega_1^{\mathrm{CK}}$-th stage? That is, is there some $\Sigma_2$ formula $\phi$ such that

  • For all $\alpha < \omega_1^{\mathrm{CK}}$, $L_\alpha \not\models \phi$
  • $L_{\omega_1^{\mathrm{CK}}} \models \phi$

If no, is $\Pi_2$ powerful enough?

$\endgroup$
6
$\begingroup$

This couldn't be achieved even by $\Sigma_3$ sentences. First note that $L_{\omega_1^{CK}}$ (as any other model of $\mathsf{KP}\omega+L=V$) satisfies the scheme of $\Sigma_3$-reflection: $$\varphi(\vec{p})\to \exists a \;(\mathsf{Trans}(a)\land \vec{p}\in a\land (\varphi(\vec{p}))^a),\text{ where $\varphi$ is $\Sigma_3$}.$$ And note that there is a $\Pi_2$ sentence $F$ such that for each transitive set $a$, the sentence $F$ is true in $a$ iff $a$ is of the form $L_{\omega(1+\alpha)}$. Henceforth for any $\Sigma_3$ sentence $\varphi$, if $L_{\omega_1^{CK}}\models\varphi$ then there is a transitive set $a\in L_{\omega_1^{CK}}$ such that $a\models \varphi\land F$ which means that $a$ is of the form $L_{\alpha}$, where $\alpha<\omega_1^{CK}$ and $L_{\alpha}\models \varphi$.

Note that $\omega_1^{CK}$ is the least $\alpha$ such that $L_{\alpha}$ is a model of $\mathsf{KP}\omega-\mathsf{Foundation}$. And the theory $\mathsf{KP}\omega-\mathsf{Foundation}$ could be axiomatized by a single $\Pi_3$ sentence (the only axiom that isn't $\Pi_2$ is the axiom of $\Sigma_1$-collection). Note that everywhere in this answer the classes $\Pi_n$ were understood as consisting of formulas that start with an unbounded quantifier prefex $\vec{\forall}\vec{x}_1\ldots \vec{Q}\vec{x}_n$ followed by a $\Delta_0$ formula. However if we switch to the classes $\hat\Pi_n$ defined in terms of alternation depth of unbounded quantifiers (bounded quantifiers could appear anywhere) the answer changes. The axiom of $\Sigma_1$-collection is a $\hat\Pi_2$-sentence and hence $\mathsf{KP}\omega-\mathsf{Foundation}$ is $\hat\Pi_2$-axiomatizable.

However I don't know whether there is a $\hat\Sigma_2$ sentence that "captures" $L_{\omega_1^{CK}}$. Non-existence of $\hat\Pi_1$ sentence is trivial due to downward-absoluteness. And non-existence of $\hat\Sigma_1$ sentence follows from the fact that $\mathsf{KP}\omega$ proves $\Sigma$-reflection (the class $\Sigma$ is exactly $\hat\Sigma_1$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer ! Could one say, in the same spirit, that there is $a \in L_{\omega_1^{CK}}$ witnessing $L_{\omega_1^{CK}} \models \exists \alpha \, \forall\beta \, \psi_0$ i.e. $L_{\omega_1^{CK}} \models \exists \alpha \in a \, \forall\beta \, \psi_0$ and that since $\omega_1^{CK}$ is a limit ordinal and can be written as a supremum of ordinals, $\omega_1^{CK} = \bigcup_i \alpha_i$, we have $a \in \alpha_k$ for some $k$ and eventually $L_{\alpha_k} \models \varphi$ as $a \in L_{\alpha_k} \subset L_{\omega_1^{CK}}$ ? Is the reflection principle hidden in the witness argument ? $\endgroup$ – Johan Jun 14 '19 at 18:35
  • $\begingroup$ @Johan I am not sure whether I understood your question. What you are describing seems to be a proof of the fact that $L_{\omega_1^{CK}}$ (and actually $L_{\alpha}$ for any limit $\alpha$) satisfies $\Sigma_2$-reflection. And this is enough to provide an answer to your initial question about "capturing" $\omega^{CK}_1$ by a $\Sigma_2$-sentence. $\endgroup$ – Fedor Pakhomov Jun 14 '19 at 19:24
  • $\begingroup$ Oh right, this wasn't so clear. I meant indeed that this was enough for the $\Sigma_2$-case. It is however not enough $\Sigma_3$ or even $\Pi_2$ sentences, do you know a reference about this sentence $F$ used in your proof ? $\endgroup$ – Johan Jun 16 '19 at 15:00
  • $\begingroup$ @Johan I don't know the refrence for exactly the construction of $F$. In Barwise book "Admissible sets and structures" he proved that the $\alpha\longmapsto L_{\alpha}$ is a $\Sigma$-function over $\mathsf{KP}$ (and hence it have $\Sigma_1$-definable graph). Using this definition we construct $\Pi_2$ sentence $F$: $\forall x\exists \alpha\;(x\in L_\alpha)$ and observe that $F$ holds in $L_{\alpha}$ for admissible $\alpha$ and every transitive model of $F$ is a level of $L$. Actually this is enough for the purposes I used $F$ in my comment. $\endgroup$ – Fedor Pakhomov Jun 16 '19 at 18:49
  • $\begingroup$ @Johan Nevertheless to obtain $F$ with the property that I described one need to guarantee that $\Sigma_1$ formula $\exists y\; \varphi(x,y,\alpha)$ ($\varphi$ is $\Delta_0$) that defines the relation $x\in L_{\alpha}$ have the property $\mathsf{KP}\vdash \exists y\; \varphi(x,y,\alpha)\mathrel{\leftrightarrow}\exists x\in L_{\alpha+\omega}$. Which could be done by an examination of how the definitions work. $\endgroup$ – Fedor Pakhomov Jun 16 '19 at 18:49

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.