Question

I don't known the correct credit for the following: every non-empty $\Pi^1_1$ set of reals contains some $X \in L_{\alpha}$ for some $X$-recursive $\alpha$. (Addison-Kondo?)

So, my question is: what is the least $\beta$, s.t. $\mathcal{P}(\omega) \cap L_\beta$ is a basis for all non-empty $\Pi^1_1$ sets?

Answer 1

I can't access the full paper at the moment, but I'm pretty sure this is exactly the question addressed in the paper "A Note on the Kondo-Addison Theorem" by D. Guaspari

Answer 2

The least such ordinal is the least ordinal which cannot be a $\Delta^1_2$-well-ordering over natural numbers.

Let $$\delta^1_2=\mbox{ supremum of the }\Delta^1_2 \mbox{ wellorderings of } \omega,$$ and $$\delta=\min\{\alpha\mid L\setminus L_{\alpha}\mbox{ contains no }\Pi^1_1 \mbox{ singleton}\}.$$

We claim that $\delta=\delta^1_2$.

$\mathbf{Proof}$: If $\alpha<\delta$, then there is a $\Pi^1_1$ singleton $x \in L_{\delta}\setminus L_{\alpha}$. Since $x\in L_{\omega_1^x}$ and $\omega_1^x$ is a $\Pi^1_1(x)$-wellordering, it must be that $\alpha<\omega_1^x<\delta^1_2$. So $\delta\leq \delta^1_2$.

If $\alpha<\delta^1_2$, there is a $\Delta^1_2$ wellordering relation $R\subseteq \omega\times \omega$ of order type $\alpha$. So there are two arithmetical relations $S, T\subseteq (\omega^{\omega})^2\times \omega^2$ so that $$R(n,m)\Leftrightarrow \exists f \forall g S(f,g,n,m), \mbox{ and}$$ $$\neg R(n,m)\Leftrightarrow \exists f \forall g T(f,g,n,m).$$ Define $\Pi^1_1$ sets $$R_0=\{(h,\langle n,m\rangle)\mid h(0)=0\wedge \exists f\forall g (S(f,g,n,m)\wedge \forall n(f(n)=h(n+1)))\}$$ and $$R_1=\{(h,\langle n,m\rangle)\mid h(0)=1\wedge \exists f\forall g (T(f,g,n,m)\wedge \forall n(f(n)=h(n+1)))\}.$$ By $\Pi^1_1$-uniformization Theorem, they both can be uniformized by $\Pi^1_1$ partial functions $p_{R_0}:\omega\to \omega^{\omega}$ and $p_{R_1}:\omega\to \omega^{\omega}$. Let $p=p_{R_0} \cup p_{R_1}$. Then $p$ is a $\Pi^1_1$ total function and can viewed as a $\Pi^1_1$-singleton. Then $R$ is recursive in $p$ and so $\alpha<\omega_1^p<\delta$.

Thus $\delta^1_2=\delta$.