20
$\begingroup$

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.

$\endgroup$
  • $\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$ – Guozhen Shen Feb 13 '18 at 6:34
9
$\begingroup$

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.

$\endgroup$
  • $\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 '17 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$ – Philip Welch Dec 5 '17 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 '17 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 '17 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$ – Philip Welch Dec 6 '17 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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