In Barwise's Admissible Sets and Structures, there's an exercise to prove that every nonprojectible ordinal is recursively Mahlo. $\alpha$ is recursively Mahlo if every $\alpha$-recursive function $f:\alpha\to\alpha$ has a witness, and if $\textrm{KP}$ is the fragment of $\textrm{ZF}$ obtained by removing powerset and restricting replacement and separation both to $\Delta_0$ formulae, $\alpha$ is nonprojectible if $L_\alpha\vDash\textrm{KP}+\Sigma_1\textrm{-separation}$. ($\textrm{KP}$ may also omit infinity, depending on who you ask, in which case use $L_\alpha\vDash\textrm{KP+Infinity}+\Sigma_1\textrm{-separation}$.)
However I don't understand the $\Sigma_1$-separation characterization of nonprojectible ordinals, so instead I'm attempting to use Jensen's "strong $\Sigma_1$-collection schema":
- $\alpha$ is nonprojectible if $L_\alpha$ satisfies the schema $\forall u\exists v\forall(x\in u)(\exists y[\phi(x,y)]\implies\exists(y\in v)[\phi(x,y)])$ for all $\Sigma_1$ formulae $\phi(x,y)$ of two free variables. (R. Jensen, The fine structure of the constructible hierarchy)
But this schema doesn't look very different from the usual $\Sigma_1$-collection, which I already know (as mentioned in MO answer #137213) is equivalent to $\Delta_0$-collection. I have failed to come up with an instance of strong $\Sigma_1$-collection that $L_{\omega_1^{CK}}$ fails - there must be one that it fails, since $\omega_1^{CK}$ is not nonprojectible.
I feel like if I know an instance of strong $\Sigma_1$-collection which $L_{\omega_1^{CK}}$ fails, the exercise will be easier. What is such an example?
Here are some attempts that I've tried:
- $\phi(x,y)$ iff $x$ and $y$ are ordinals, and $y=\omega^x$. But we can recover this from $\Sigma_1$-collection as well: as $\forall x\exists y\phi(x,y)$ holds in $L_{\omega_1^{CK}}$, $\Sigma_1$-collection applies.
- $\phi(x,y)$ iff $y$ is the order type of the ordinal notation $x$ (as in Kleene's $\mathcal O$.) I'm not sure if there is such a $\Sigma_1$ formula, but even if there is one, $\exists y[\phi(x,y)]$ may be false in $L_{\omega_1^{CK}}$ so the schema doesn't seem to imply closure under anything.
- $\phi(x,y)$ iff $x$ and $y$ are both ordinals, and $y$ is the least admissible ordinal $>x$. This is a $\Delta_0$-definable function according to Rathjen ("A Proof-Theoretic Characterization of the Primitive Recursive Set Functions", p.968), and yet it seems like it still does not imply $L_{\omega_1^{CK}}$ is closed under any operator in particular: if for some $x\in u$ we do not have a $y\in L_{\omega_1^{CK}}$ such that $\phi(x,y)$, then the right-hand side $\exists(y\in v)\phi(x,y)$ need not be true.
I think your second bulletpoint is exactly what you want, you just have to analyze it more carefully.
Note that strong $\Sigma_1$ collection does not require each element $x$ of the "source set" $u$ to actually have a corresponding $y$! (Put another way, strong $\Sigma_1$ collection is really $\Sigma_1$ collection where the source is an arbitrary $\Sigma_1$ subclass of some set.)
So take the formula $\varphi(x,y)\equiv$ "$x$ is an index for a computable linear order, $y$ is an ordinal, and $y$ is isomorphic to the linear order with index $x$. This is $\Sigma_1$, and when applied to this formula with $u=\omega$ the strong $\Sigma_1$-collection scheme would require the existence of a set containing every computable ordinal - and no such set exists in $L_{\omega_1^{CK}}$. Note that this is really just "reversing" the fact that the $\Sigma_1$-projectum of $\omega_1^{CK}$ is $\omega$.