Can we describe any subsets of $\mathbb{N}$ occurring in a late layer of the Constructible Universe? There is a certain large countable ordinal referred to in the literature as $\beta_0$.  It was first discovered by Paul Cohen, and here are some equivalent characterizations of it:


*

*The smallest ordinal $\beta$ such that $L_\beta$ is a model of $ZFC-P$

*The smallest ordinal $\beta$ such that $L_\beta\cap P(\mathbb{N})=L_{\beta+1}\cap P(\mathbb{N})$

*The smallest $\omega$-admissible ordinal
My question is, is it possible to describe an actual example of a subset of $\mathbb{N}$ which is not an element of $L_{\beta_0}\cap P(\mathbb{N})$? Or are all such sets undefinable?
I’m even okay with something like “the set of Gödel numbers of all true statements in language $X$“.  Or will even such descriptions not suffice?
 A: Such an object is complicated to describe, but not too complicated. In general, the appearance of reals throughout $L$ is technical but not mysterious: we sort of keep using the same basic tricks over and over again. Standard go-to's include countability witnesses and first-order theories of countable levels of $L$ and related structures; common techniques include Lowenheim-Skolem, the condensation lemma (and the Mostowski collapse), and the use of the $L$-ordering to eliminate parameters. 

First, there is a general approach that applies more-or-less to every countable ordinal. Whenever $\alpha$ is countable, so is $L_\alpha$, which means there is a (not unique of course) relation $R\subseteq\omega^2$ such that $(\omega; R)\cong (L_\alpha;\in)$ (I'm assuming $\alpha$ is infinite, here). However, it's easy to see that such an $R$ can never, itself, be in $L_\alpha$. That is, for every countable $\alpha$ there are reals which code bijections between $L_{\beta_0}$ and $\omega$, none of which are in $L_\alpha$, and particular this is true for $\alpha=\beta_0$. 
We can further identify a specific such real (using $\alpha$ as a parameter): the least real with respect to the parameter-freely-definable well-ordering of $L$ which codes a bijection between $\omega$ and $L_\alpha$. In case $\alpha$ itself is parameter-freely definable - as $\beta_0$ is - this real is also parameter-freely definable. (We can also give a quick complexity analysis: for ordinals such as $\beta_0$ corresponding to the first level of $L$ satisfying a given first-order theory, the resulting definition is $\Delta^1_2$.)

A more specific argument would be to observe that - conflating a transitive set $A$ with the corresponding $\{\in\}$-structure $(A; \in\upharpoonright A)$ - the structure $L_{\beta_0}$ happens to be a pointwise definable structure; that is, each element in it is definable without parameters in it. This means that $Th(L_{\beta_0})$, the set of Godel numbers of all $\{\in\}$-sentences which are true in $L_{\beta_0}$, is not itself an element of $L_{\beta_0}$.
But this relies on particular properties of $\beta_0$; there are many countable ordinals $\gamma$ such that $L_\gamma$ is not pointwise-definable; indeed, most countable ordinals have this property, in the sense that the set of $\gamma$ such that $L_\gamma$ is not pointwise definable is club. Such an $L_\gamma$ can indeed contain its theory as an element, avoiding Tarski by way of that specific element not being parameter-freely definable. For example, $L_{\omega_1}$ contains every real in $L$, including (since $L$ computes first-order theories correctly) the theory of $L_{\omega_1}$ itself. And we can bring this down to the countable realm too, by applying Lowenheim-Skolem, Mostowski collapse, and condensation to get a countable $\gamma$ such that $L_\gamma\equiv L_{\omega_1}$ and $Th(L_{\omega_1})\in L_\gamma$ (hence $Th(L_\gamma)\in L_\gamma$ since $L_\gamma\equiv L_{\omega_1}$).

Incidentally, if you're not already familiar with it you'll probably be interested in the paper "Gaps in the constructible universe" by Marek and Srebrny.
