# $\Pi^1_1$ singletons and $\Delta^1_2$ wellorders on $\omega$ in $L$

I have been trying to show the supremum $\delta^1_2$ of ordinals that are $\Delta^1_2$ wellorders on $\omega$ is exactly equal to the least ordinal $\delta$ such that $L_\delta$ contain all $\Pi^1_1$ singletons. It is easy to see $\delta^1_2 \ge \delta$. I have been trying to show the converse.

I know how to construct, given a $\Delta^1_2$ wellorder $R$ on $\omega$, a $\Pi^1_1$ singleton $f \in \omega^\omega$ such that $R \le_T f$, by appealing to Kondo-Addison theorem. This intuitively shows that for any $\gamma < \delta^1_2$ there is a $\Pi^1_1$ singleton at least as complex as $\gamma$. However, I do not know how to proceed to get the inequality between the associated ordinals.

How can one do this?

• I suggest you to read the book by CT and me. – 喻 良 Oct 26 '15 at 14:28

Recall that $\alpha$ is an admissible ordinal if and only if $L_\alpha \models \mathsf{KP}$.

$\mathsf{KP}$ is a small fragment of $\mathsf{ZFC}$ capable of performing many set theoretic construction and in particular, you can do Mostowski collapses in models of $\mathsf{KP}$.

$\delta_2^1$ is a limit of admissible ordinals.

To see this: Let $R$ code a $\Delta_2^1$ well ordering. By what you mentioned, let $f$ be a $\Pi_1^1$ singleton such that $R \leq_T f$. $\omega_1^f$ is an admissible ordinal (by Sacks' Theorem) which is greater than $\text{ot}(R)$. Recall $\omega_1^f$ is the supremum of the $f$-recursive well-orderings. So you can check that $\{S : S \in \text{WO} \wedge \text{ot}(S) = \omega_1^f\}$ is $\Delta_2^1(f)$. $\Delta_1^1(f)$ is a basis for all $\Sigma_2^1(f)$ nonempty sets. So the above set has a $\Delta_2^1(f)$ member. Since $f$ is $\Pi_1^1$, you can show that is member is a $\Delta_2^1$. So $\omega_1^f$ is an admissible ordinal and a $\Delta_2^1$ well-ordering.

Then if $\alpha < \delta_2^1$ and is an admissible ordinal, by what you mentioned, there is a $\Pi_1^1$ singleton $f$ such that $R \leq_T f$, where $R$ is a real coding $\alpha$. The claim is that $f \notin L_\alpha$. Suppose $f \in L_\alpha$. Then since $R$ is hyperarithmetic in $f$ and $L_\alpha$ is an admissible set, $R \in L_\alpha$. Then using the Mostowski collapse in $L_\alpha$, one would have that $\alpha \in L_\alpha$. This is a contradiction.

So it has been shown that for an unbounded set of ordinals below $\delta_2^1$, $L_\alpha$ is missing a $\Pi_1^1$ singleton. Hence $\delta_2^1$ is less than the least $\delta$ such that $L_\delta$ has all $\Pi_1^1$ singletons.

• The proof that $\delta_2^1$ is a limit of admissible ordinals is eluding me at the moment, but I do think it is true. I will add a proof or reference later if I can find something. – William Oct 26 '15 at 3:56
• Thank you for your help. Isn't it possible for the proof of admissble ordinals being cofinal in $\delta^1_2$ to depend on the very proposition I started with? – Pteromys Oct 26 '15 at 4:08
• @Pteromys I added a proof. I hope I did the complexity calculations correcly. – William Oct 26 '15 at 4:44
• Can I ask the name of the basis theorem you used? – Pteromys Oct 26 '15 at 5:31
• @Pteromys Moschovakis' book does not give it a name. We just say $\Delta_2^1$ is a basis for $\Sigma_2^1$. It follows from $\Sigma_2^1$ uniformization. This uniformization may have a name. – William Oct 26 '15 at 6:00