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.

  • $\begingroup$ In KPI (KP + infinity), let $\omega_1^{CK}$ be the class of all recursive ordinals. In KPI, for a class $A$ (given by a formula of set theory, such as $\omega_1^{CK}$), we can define a formula Adm($A$) to express that "$A$ is admissible". Then, without knowing whether $\omega_1^{CK}$ is a set, we can ask whether Adm( $\bigcup_{\alpha\in\omega_1^{CK}}\mathbf{L}_{\alpha}$ ) is provable in KPI. $\endgroup$ Feb 13, 2018 at 6:34

1 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.

  • $\begingroup$ Thanks. But how to show that it requires $On^M$-many steps to complete the recursion definition of Kleene's $\mathscr{O}$ without using Gandy-basis? It it clear to me that it requires exactly $\omega_1^{CK}$-many steps. $\endgroup$
    – 喻 良
    Dec 4, 2017 at 0:50
  • $\begingroup$ If it took fewer steps, then $\mathcal{O}^M $, and also the $H$ sets, $(\langle H_a \mid a \in \mathcal{O}\rangle)^M$ are in some $(L_\tau)^M$; by Suslin-Kleene in $M$, every $\Delta^1_1$ set is recursive in one of these. As $M$ models there are no admissibles, $(\eta\in ON)^M$ implies $(L_\eta$ has a canonical code in $\Delta^1_1)^M$. (As can be seen by writing out suitable $\Pi^1_1,\Sigma^1_1$ definitions.) But this would imply all such codes are in $L_\tau$! I think this answers your original question (and if I am not mistaken there is no covert use of Gandy Basis Theorem?) $\endgroup$ Dec 5, 2017 at 8:40
  • $\begingroup$ But $KP$ is not enough to prove that every $\Delta^1_1$ is hyperarithmetic. See here: mathoverflow.net/questions/118706/… $\endgroup$
    – 喻 良
    Dec 5, 2017 at 9:09
  • $\begingroup$ Also if only work in $KP$, $\Pi^1_1$-completeness of $WO$ becomes subtle. For example, in $L_{\omega_1^{CK}}$, there is a recursive well ordering which is not isomorphic to any ordinal. This means your statement "$(\eta\in ON)^M$ implies $(L_{\eta}\mbox{ has a canonical code in} \Delta^1_1)^M$" may not hold anymore. $\endgroup$
    – 喻 良
    Dec 5, 2017 at 9:33
  • 1
    $\begingroup$ I think we are misunderstanding one another here. I am talking in $M$: about $N$ that are of the form $L_\eta$; and in $M$, that $\Delta^1_1$ codes of such $L_\eta$ appear "hyperarithmetic". They are not truly hyp. $\endgroup$ Dec 6, 2017 at 23:05

You must log in to answer this question.

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