7
$\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$

1 Answer 1

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 can't be expressed as a single $\Pi_2$ formula is the schema 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$).

$\endgroup$
6
  • $\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, 2019 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$ Jun 14, 2019 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, 2019 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$ Jun 16, 2019 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$ Jun 16, 2019 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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