# Finding, for each $\alpha < \omega_1$, an ordinal $\beta > \alpha$ such that $L_{\beta + 1} \models \beta \text{ is countable}$

I would like to prove the following statement:

Assume $$V = L$$. Then for each ordinal $$\alpha < \omega_1$$, there exists an ordinal $$\beta > \alpha$$ such that $$L_{\beta + 1} \models \beta \text{ is countable}$$.

For my first pass at a proof, I considered a countable elementary substructure $$M$$ of $$L_{\omega_1}$$ such that $$\alpha \subseteq M$$. Since $$L_{\omega_1} \models \text{all ordinals are countable}$$, $$M \models \text{all ordinals are countable}$$; further, since it can be shown via a condensation argument that $$M$$ is transitive, there exists a limit ordinal $$\beta < \omega_1$$ such that $$\alpha < \beta$$ and $$M = L_{\beta}$$. Thus, in $$L_{\beta}$$, all ordinals $$\beta'$$ are countable, and so for each $$\beta'$$, there exists a surjection $$f_{\beta'} : \omega \rightarrow \beta'$$. My hope was then to combine these $$f_{\beta'}$$ into a definable subset $$f$$ of $$L_{\beta}$$ such that $$f : \omega \rightarrow \beta$$ is surjective. Then this $$f$$ would belong to $$L_{\beta + 1}$$, and so $$L_{\beta + 1}$$ would think that $$\beta$$ is countable. However, because the union over the $$f_{\beta'}$$ is not necessarily a function and because I can't come up with any other way to combine the functions, I am stumped. Is there a better way to use the $$f_{\beta'}$$? Is there a better way to approach this question entirely?

Having $$L_{\alpha+1}\models$$ "$$\alpha$$ is countable" is a strong countability property - this means that we don't want $$\alpha$$ to be $$\omega_1$$-like, so we emphatically don't want to look at things like elementary submodels of $$L_{\omega_1}$$. In particular, a club of countable ordinals will not have the desired property (take e.g. set of Mostowski collapse images of $$\omega_1^M$$ for $$M$$ a countable transitive model of $$L_{\omega_2}$$).

Instead, note that the desired condition is the same as "$$L_\alpha$$ has a definable bijection between $$L_\alpha$$ and $$\omega$$" (since the stuff in $$L_{\alpha+1}$$ is exactly the stuff definable in $$L_\alpha$$, and $$L_\alpha$$ has a bijection between itself and $$\alpha$$). One nice way for a level of $$L$$ to see its own countability is for it to$$^1$$ be the first level of $$L$$ satisfying some sentence with hereditarily countable parameters:

Suppose $$L_\eta$$ satisfies enough of $$\mathsf{ZFC}$$, $$a\in \mathsf{HC}^{L_\eta}$$, and there is a formula $$\varphi$$ such that $$L_\eta$$ is the least level of $$L$$ containing $$a$$ as an element and satisfying $$\varphi(a)$$. Let $$f_1,...,f_n$$ be definable-over-$$L_\eta$$ Skolem functions for $$\varphi(a)$$, and - in $$L_\eta$$ - let $$C$$ be the Mostowski collapse of the closure of $$tc(\{a\})$$ under the Godel operations and the $$f_i$$s We have that $$C$$ is definable (scince we've only used bounded-quantifier-rank "tools" to build $$C$$ - regardless of how complicated $$\varphi$$ is, there are only finitely many Skolem functions we need), $$a\in C$$ (since we folded in the transitive closure), and $$L_\eta\models$$ "$$C$$ is countable" (since $$a\in\mathsf{HC}^{L_\eta}$$), so by assumption we get $$C=L_\eta$$.

And we can now apply this in a very silly way:

For each $$a\in L_{\omega_1}$$ consider the least level of $$L$$ which sees that $$a$$ is hereditarily countable.

$$^1$$Actually, we also need $$L_\eta$$ to satisfy a small fragment of $$\mathsf{ZFC}$$ as well. But I do mean a small fragment - we just need $$L_\eta$$ to be able to perform basic recursive constructions, a la Lowenheim-Skolem and Mostowski. So in partcular, $$\mathsf{KP}$$ is enough.

• Thank you for your helpful answer. Just to check my own understanding -- the set $C$ that you construct is a definable subset of $L_{\eta}$ and not an element of $L_{\eta}$, right? Commented Sep 7, 2020 at 4:10
• @gaiuscassiuslonginus Yup. It's definable because it's the closure of a definable set (indeed an element) under finitely many definable operations, and it's not an element of $L_\eta$ since if it were it would be a smaller level of $L_\eta$ (containing $a$ as an element and) satisfying $\varphi(x)$, which can't happen by assumption on $\eta$. Commented Sep 7, 2020 at 4:52
• Thank you for the clarification! One more question (sorry) -- since I'm not very familiar with Gödel functions, I'm trying to adapt your proof to avoid mentioning them: Let $a \in L_{\omega_1}$, and let $\eta$ be least such that $L_{\eta}$ sees $a$ is hereditarily countable. Let $M$ be a countable elementary submodel of $L_{\eta}$ such that $\text{tc}(\left\{a \right\}) \subseteq M$, and let $N$ be its transitive collapse. Then by minimality of $\eta$, $N = L_{\eta}$, and $N$ is countable in $L_{\eta + 1}$ by a definability argument. Is this equivalent to your proof? Commented Sep 7, 2020 at 5:51
• @gaiuscassiuslonginus no, it's not - all that gives us is that $L_\eta$ is externally countable. We need $L_\eta$ to be internally countable. The issue with the argument in your comment is that in order to get what we want we would need $M$, or $M$'s Mostowski collapse more accurately, to be definable in $L_\eta$ - which a priori it isn't. This is what the argument in my answer does: it explicitly builds the desired object in a definable way. The spirit is the same, but we need to do more work. Commented Sep 7, 2020 at 6:00
• I see! Thank you again; this has been very helpful. Commented Sep 7, 2020 at 6:04

Here is another argument that migth be more more straightforward (Noah's answer is very insightful though).

Let us write $$\alpha_0 = \alpha$$ and define inductively $$\alpha_{n+1}$$ to be least so that $$L_{\alpha_{n+1}} \models$$ "$$\alpha_n$$ is countable". This means that $$L_{\alpha_{n+1}}$$ contains the $$<_L$$-least bijection $$f_n$$ between $$\alpha_n$$ and $$\omega$$. Now take $$\beta = \sup_{n \in \omega} \alpha_n$$. Then we see that in $$L_{\beta}$$ the sequence $$\langle \alpha_n : n \in \omega \rangle$$ is definable (from the parameter $$\alpha$$) since we could have carried out the whole inductive construction (which is absolute between levels of the $$L$$ hierarchy) in $$L_\beta$$. Also the sequence $$\langle f_n : n \in \omega \rangle$$ is definable over $$L_\beta$$. Now it is easy (say, using Cantor's diagonal argument) to use these functions to define a bijection $$f$$ between $$\beta$$ and $$\omega$$. $$f$$ is then definable over $$L_\beta$$.

Note that according to Noah's argument, $$\alpha_1$$ will already work for "most" (club many) $$\alpha$$. But this will always be a successor ordinal. Here we got a limit ordinal.