$\alpha$-computable bounded subset of $\alpha$ is in $L_\alpha$

Question

I would like to prove the proposition 1.12b from Chong, Techniques of Admissible Recursion Theory:

Let $\alpha$ be an admissible ordinal. A subset $K \subseteq \alpha$ is in $L_\alpha$ ($\alpha$-th level of Goedel's Constructible Universe $L$) iff it is bounded and both $A$ and $\alpha - A$ are $\Sigma_1$-definable over $L_\alpha$.

The left to right direction is trivial. But what about the other direction. Suppose that $K \subseteq \gamma < \alpha$ and both $K$ and $\alpha - K$ are $\Sigma_1$-definable over $L_\alpha$. How could I prove that $K$ is in $L_\alpha$?

I was thinking of proving that if $\phi$ is a formula that defines $K$ over $L_\alpha$, then perhaps the same formula defines $K$ over $L_\delta$ for some $\delta < \alpha$. But the problem seems to be to guarantee that the existential witnesses are bounded in some $\delta < \alpha$.

Answer 1

Right to left: suppose $K\subseteq \gamma < \alpha$, and $K, \alpha-K$ are $\Sigma_1$-definable over $L_{\alpha}$. Without loss of generality, we can assume that any parameters in the $\Sigma_1$ definitions are also in $L_{\gamma}$. Then there are $\Delta_0$ formulas $\varphi, \psi$ such that for $x<\gamma$, $$ x\in K \iff (\exists \delta<\alpha)\,\varphi(x,\delta) $$ and $$ y\in \alpha-K \iff(\exists \eta<\alpha)\,\psi(x,\eta). $$ By $\Sigma_0$ collection, there is a set $X\in L_{\alpha}$ such that $$ \text{for all $x < \gamma$, $(\exists \xi\in X)\,[\varphi(x,\xi) \lor \psi(x,\xi) ]$} $$ because the formula $[...]$ is $\Delta_0$. Let $\beta < \alpha$ be such that $x\in L_{\beta}$ and $\beta > \gamma$. Then $K$ is definable over $L_{\beta}$ (with parameters in $L_{\beta}$, too): $$\begin{align} K &= \{x\in L_{\beta}\mid x<\gamma \land L_{\beta}\models (\exists \xi\in X)\,\varphi(x,\xi)\} \\ &= \{x\in L_{\beta}\mid x<\gamma \land (\exists \xi\in X)\,\varphi(x,\xi)\}. \\ \end{align}$$

($\subseteq$) Suppose $x\in K$. Then $x<\gamma$, and there is $\delta<\alpha$ such that $\varphi(x,\delta)$. Thus there is $\xi\in X$ such that $[\varphi(x,\xi)\lor \psi(x,\xi)]$. But if $\psi(x,\xi)$, then $x\in \alpha-K$; so $\varphi(x,\xi)$.

($\supseteq$) is clear.

Thus $K\in L_{\beta+1}\subseteq L_{\alpha}$.

Answer 2

Depending on your definition of an admissible ordinal, this question is either obvious or may require some work.

Usually, $\alpha$ is an admissible ordinal if and only if $L_\alpha$ is an admissible set. An admissible set is a transitive set satisfying some basic things like pairing, union, and $\Delta_1$-separation, and $\Sigma_1$-collection.

Sometimes, an admissible set is defined using only $\Delta_0$ comprehension and collection, but you can prove $\Delta_1$ comprehension and $\Sigma_1$ collection from these axioms.

Back to your problem: Since $K$ is bounded, there is some $\delta < \alpha$ such that $K \subseteq \delta$. $\delta \in L_\alpha$. Since $K$ is $\Sigma_1$ and $\Pi_1$ by your assumption, there are $\Sigma_1$ and $\Pi_1$ formulas $\varphi$ and $\psi$ such that $L_\alpha \models (\forall x)(\varphi(x) \Leftrightarrow \psi(x))$ and $K = \{\beta < \alpha : L_\alpha \models \varphi(x)\} = \{\beta < \alpha : L_\alpha \models \psi(x)\}$. Then by $\Delta_1$, comprehension the set $\{\beta < \delta : L_\alpha \models \varphi(x)\} \in L_\alpha$. But this set is just $K$ since $K$ is bounded by $\delta$.