About $\omega_1^{CK}$

Question

Here we use $\omega_1^{CK}$ to denote the least nonrecursive ordinal. The following theorem is well known.

$\mathbf{Theorem}$ $\omega_1^{CK}$ is an admissible ordinal.

But its proof seems weird. The usual proof uses a nonstandard technique. I wonder whether there exists a pure standard proof. Or, to negate it, whether there is an $\omega$-model $M$ of $KP$ so that $$M\models \omega_1^{CK}\mbox{ exists but is not admissible ?}$$

If there exists such a model, then it means that $KP$ is not enough to prove the theorem. So one has to use some assumptions beyond $KP$ and probably requires the existence of Kleene's $O$. So nonstandard techniques can be applied.

---

It seems there is no such model. The ideal of the following proof is inspired by Philip.

$\mathbf{Theorem}$: There is no $\omega$-model of $KP$ in which $\omega_1^{CK}$ exists, but is not admissible.

Here is an outline of the proof.

$\mathbf{Proof}$: Suppose not, fix such an model $M$. Through out the proof, all the notions are relative to $M$. So they may be nonstandard.

Since $\omega_1^{CK}$ exists in $M$, so does Kleene's $\mathscr{O}$. Let\begin{multline*}WO=\{e\mid R_e \mbox{ is a recursive linear order over }\omega \\ \wedge \mbox{ there is no an infinite descending chain on }R_e\}\end{multline*} and $$WO^*=\{e\mid R_e \mbox{ is a recursive linear order over }\omega \mbox{ isomorphic to an ordinal} \}.$$

Clearly $M\models WO^*\subseteq WO$. It is routine to prove that $M\models WO^*\leq_m \mathscr{O}$. Now for any $e\not\in WO^*$, there must be some $n_0$ so that $R_{e_{n_0}}=\{(m_0,m_1)\mid R_e(m_0,n_0)\wedge R_e(m_1,n_0)\wedge R_e(m_0,m_1)\}$ and $e_{n_0}\notin WO^*$. Repeat this, we may $\mathscr{O}$-recursively obtain an $R_e$-descending sequence $\{n_i\}_{i\in \omega}$. So $e\not\in WO$. In other words, $WO\subseteq WO^*$ and so $M\models WO=WO^*$.

Now it is clear that $WO$ is a $\Pi^1_1$-complete set in $M$. So is $\mathscr{O}$. Using this fact, Gandy basis holds in $M$.I.e. every nonempty $\Sigma^1_1$set contains a real $x\leq_T \mathscr{O}$ and $\omega_1^x=\omega_1^{CK}$, where $\omega_1^x$ is the least non-x-recursive ordinal.

Let $\mathscr{N}=\{N=(\omega,E)\mid N\mbox{ is an }\omega \mbox{-model of }BS+V=L \wedge \forall \alpha(\alpha<\omega_1^{CK}\rightarrow \alpha\in N)\},$ where $BS$ is the corrected Basic set theory as developed in Devlin book. In $M$, $\mathscr{N}$ is a $\Sigma^1_1$-set. Clearly $\mathscr{O}$ hyperarithmetically computes a copy of $(L_{\omega_1^{CK}})^M$. So by the existence of $\mathscr{O}$, $\mathscr{N}$ is nonempty in $M$.

Now by the Gandy basis, there is some $N\in \mathscr{N}$ so that $\omega_1^N=\omega_1^{CK}$. Let $N'=(L_{\omega_1^{CK}})^N$. Since $N$ is a theory of $BS$, we have that $N'=(L_{\omega_1^{CK}})^M$. Also note that $N'\in M$.

We claim that $N'\models KP$. Otherwise, let $f$ be a $\Sigma_1^{N'}$ total function from $\omega$ to $\omega_1^{CK}$. Then, by the totality, it is also $\Sigma_1^N$. In other words, we have that $\omega_1^{CK}$ is recursive in $N$, a contradiction.

This finishes proof.

---

So the question I asked may not be a right formalization to get rid of the nonstandard argument.

Answer 1

I claim there is no $\omega$-model $M\models KP$ such that

$$M\models \,\,"\omega_1^{ck} \mbox{ exists, but is not admissible ''.} $$

(In other words if $(\eta =\omega_1^{ck})^M$ then $(L_\eta \nvDash KP)^M$. Suppose $M$ were such a model; by truncating it, if need be, we may assume also that $\omega$ is the only admissible ordinal of $M$. The definition of Kleene's $\mathcal{O}$ is by way of a $\Sigma_1^{KP}$ recursion, and has the special property that for any $b\in \mathcal{O}$ we have $B=\{a|a<_{\mathcal{O}}b\}$ is r.e. Moreover at the stage that $b$ is put into $\mathcal{O}$ by the recursion, so have all elements of $B$.

For $M$ the recursion requires $On^M$ many steps to complete. But we do not need to establish the existence of $\mathcal{O}^M$ as a set. This would indeed go beyond $KP$, and is really the point of this answer. We only need, roughly speaking, the $\eta$'th iterate of this positive monotone recursion, and indeed by KP, the graph of any initial segment of the recursion is an element of $M$. We thus find eventually a $b\in \omega$ with $|b|_{\mathcal{O}^M}=\eta$, and the recursion up to $\eta$ is an element of $M$. By the comments above if $(B=\{a|a<_{\mathcal{O}}b\} )^M$ then $B$ is contained in the $\eta$'th iterate of the recursion in $M$ and so is a set in $M$, and is moreover r.e. in the sense of $M$. Letting $f:\omega \rightarrow B $ be a recursive bijection in $M$, we then define $n\prec m \leftrightarrow f(n) <_{\mathcal{O}^M} f(m)$, and then $((\omega, \prec) $ is recursive with $o.t.(\omega, \prec)= \eta \geq \omega_1^{ck} )^M$, a contradiction.