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?


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.


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.