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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$).

Improve this answer
$\endgroup$
7
  • $\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
    Commented 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$
    – Fedor Pakhomov
    Commented 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
    Commented 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$
    – Fedor Pakhomov
    Commented 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$
    – Fedor Pakhomov
    Commented Jun 16, 2019 at 18:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .