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?

  • $\begingroup$ I suggest you to read the book by CT and me. $\endgroup$ – 喻 良 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.

  • $\begingroup$ 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. $\endgroup$ – William Oct 26 '15 at 3:56
  • $\begingroup$ 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? $\endgroup$ – Pteromys Oct 26 '15 at 4:08
  • $\begingroup$ @Pteromys I added a proof. I hope I did the complexity calculations correcly. $\endgroup$ – William Oct 26 '15 at 4:44
  • $\begingroup$ Can I ask the name of the basis theorem you used? $\endgroup$ – Pteromys Oct 26 '15 at 5:31
  • $\begingroup$ @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. $\endgroup$ – William Oct 26 '15 at 6:00

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.