MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The structure $L_{\omega_1^{CK}}$ consists of only HYP sets (I believe) and HYP in this structure is the same as the actual hyperaritmetic sets. Now if I move to the structure $L_{\omega_1^{CK}}[a]$ where $a$ is some non-hyperarithmetic real I add my guess is that HYP remains unaltered simply because HYP has a bottom up definition and won't be affected by the addition of new sets as long as one doesn't move to a non-$\omega$ model or the like.

Is this correct? Any more formal demonstration?

share|cite|improve this question
If $M = L_\alpha[a]$ then $(L_\beta)^M = L_\beta$ for $\beta < \alpha$. So, if $\alpha = \omega^{CK}_1$, then $HYP$ is the set of reals in $L^M$. Is this sufficient? – Wei Wang Jan 12 '13 at 5:18
I think you may have confused the subscript and the superscript. – Asaf Karagila Jan 12 '13 at 15:00
(@Asaf: Fixed.) – Andrés Caicedo Jan 13 '13 at 1:34
You claim that $L_{\omega_1^{CK}}$ consists of only HYP sets. I want to make it clear what is meant by this. The reals (i.e. subsets of $\omega$) which are in $L_{\omega_1^{CK}}$ are exactly the hyperarithmetic sets, but $L_{\omega_1^{CK}}$ of course contains other things. – catrincm Sep 17 '13 at 13:06
Those other sets are nevertheless countable in $L_{\omega_1^{CK}}$ and (hence) are coded by hyperarithmetic reals. – Joel David Hamkins Sep 17 '13 at 13:41

The following is not the answer of your question. But I think it is what you really want.

I guess you might be figuring out Leo's proof of McLaughlin's conjecture and his answer to Question 65 in Harvey's problem collection paper. The point is that by applying a nonstandard ordinal, Leo obtained a nonstandard $\Pi^0_1$-singleton so that it is not hyperarithmetic.

There are several ways to see above. One is by applying Barwise compactness. Another is to use Gandy's basis. By either way, you may obtain a nonstandard $\omega$-model $M$ of KP with $\omega_1^M=\omega_1^{CK}$ in which there is a nonhyperarithmetic (in the real sense) $\Pi^0_1$-singleton $x$ which has the property below.

To see it by Gandy's basis theorem. Just apply it to obtain an $\omega$-model $M\models KP$ in which $\omega_1^{CK}$ is nonstandard. In $M$, fix a nonstandard recursive ordinal $\alpha$, we can perform Leo's proof to produce a nonhyperarithmetic $\Pi^0_1$-singleton $x$so that for any $\beta<\alpha$, those reals computed by $x^{\beta}$ and $\emptyset^{\alpha}$ are precisely those computed by $\emptyset^{\beta}$.

Now take $N=L_{\omega_1^{CK}}[x]$. Since $x\leq_h M$, we have that $N\models KP$. It is not difficult to see that $N\models$ ''$x$ is a $\Pi^0_1$-singleton$"$.

The left is to show $N\models$`` $x$ is not hyperarithmetic".

$\bf{Proof}$: Otherwise, there must be some nonstandard ordinal $\gamma_0$ in $N$ so that $N\models \emptyset^{\gamma_0} $ exists. We may assume that $\gamma_0<\alpha$. Since $\omega_1^x=\omega_1^{CK}$, there must be some standard recursive ordinal $\gamma_1<\gamma_0$ so that $x^{\gamma_1}\geq_T \emptyset^{\gamma_0}$. Via some absoluteness (see below), it is not difficult to see $\emptyset^{\gamma_0}<_T \emptyset^{\alpha}$. Then by the property of $x$, $\emptyset^{\gamma_0}<\emptyset^{\gamma_1}$, a contradiction.[]

To see that $\emptyset^{\gamma_0}<_T \emptyset^{\alpha}$. There is recursive tree $T$ so that $N\models \emptyset^{\gamma_0} \mbox{ is the unique path in } T$. Note that there is also a real $z$, which is $\emptyset^{\gamma_0}$ in $M$, so that $M\models z \mbox{ is the unique path in } T$. If $\emptyset^{\gamma_0}=z$, then we have the conclusion. Otherwise, $\emptyset^{\gamma_0}$ does not belong to $M$. But $\emptyset^{\gamma_0}$ is hyperarithemtic in $x$ and so must belong to $M$, a contradiction.

In fact, by the proof above, every real which is hyperarithmetic in $N$ is actually hyperarithmetic.

share|cite|improve this answer
Well, it's not quite appropriate to say that Leo obtained a non-standard $\Pi^0_1$ singleton that is not hyperarithmetic. Rather in transitioning to the non-standard one obtains a single tree all of whose paths are not hyperarithmetic (indeed subgeneric so any degree computable from $0^{(\alpha)}$ and $g^{(\beta)}$ is also computable from $0^{(\beta)}$). By basic results one couldn't have a $\Pi^0_1$ singleton that failed to he hyperarithmetic. But I see what got me! I failed to use Gandy Basis theorem to yield a path $f$ through $T$ which leaves $\omega_1^f=\omega_1^{ck}. More later. – Peter Gerdes Jan 12 '13 at 23:29
$\Pi^0_1$-singletoness is not a absoluteness notion among the $\omega$-models. Also you have to apply Gandy's basis to get a model not the singleton. I added more details. – 喻 良 Jan 12 '13 at 23:54
Ok, I see how this works. Thanks, Now to figure out what the heck Leo meant in his notes to see if this is the same thing (he couldn't remember what he had meant in his notes when I asked him about it a few days ago). I think this is probably what he meant even if the notes sound more like they only use the nonstandard model to produce a tree with special paths. – Peter Gerdes Jan 13 '13 at 21:16
I fixed an error in the proof. To show that $x$ is not hyperarithemtic in $N$, we really need Leo's proof. – 喻 良 Jan 13 '13 at 21:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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