Why do new real numbers show up in Gödel's constructible hierarchy
In the "fat" cumulative hierarchy of sets, all the real numbers appear on level $\omega+1$. In Gödel's constructible hierarchy, some real numbers appear at that level, but (if I'm not mistaken) more real numbers show up at later levels. While it is clear to me why not all the reals (of the fat hierarchy) can be defined at level $\omega+1$ of the constructible hierarchy, I need some help understanding exactly why some of them show up later.
Specifically:
Since there are only countable many reals at level $\omega+1$ of the constructible hierarchy, one can diagonalize on them to define a new real. But to do so in the constructible hierarchy, a bijection between those reals and $\mathbb N$ would have to be definable in there. Is it?
At higher levels one can define the least upper bound of some (non-empty, bounded) set of reals from earlier levels. But this real number might be among the reals already defined. Are there any least upper bounds that are new real numbers?
What exactly are the mechanisms that produce new real numbers at higher levels?
(If there are multiple such mechanisms, I am interested in hearing about several of them. References to relevant literature would also be very much appreciated.)
UPDATE
I'm still looking for some help understanding this. As far as I can tell, the answer below focuses on why there are levels where now real numbers do not show up. I'm trying to understand the opposite. To make it as concrete as possible: why do new real numbers show up at level $\omega+2$?
This is a question with a long history. As I mentioned in a comment, I think the best reference to get started on these matters is
MR0373902 (51 #10102). Marek, W.; Srebrny, M. Gaps in the constructible universe. Ann. Math. Logic 6 (1973/74), 359–394.
The paper does not require knowledge of fine structure, it is directly concerned with the question, provides a detailed list of references (some I mention below) directly addressing it and, once one sees the sort of arguments and techniques relevant here, using fine structure is then seen as natural. In fact, one of the motivations of fine structure theory is precisely this question.
MR0309729 (46 #8834). Jensen, R. Björn. The fine structure of the constructible hierarchy. With a section by Jack Silver. Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443.
The Marek-Srebrny paper studies the question that concerns us—what is it that makes new reals appear at higher levels of the constructible hierarchy?—by addressing the complementary problem—when is it that no new reals appear?
Let's be more precise. Their paper begins
What does it mean to say that at step $\alpha + 1$ in the constructible hierarchy no new set of natural numbers is constructed?
Notice that, indeed, no new reals appear at limit stages since $L_\alpha$, for $\alpha$ limit, is simply the union of the $L_\beta$ with $\beta<\alpha$. As the authors indicate, the problem was solved by Leeds and Putnam, who proved, using recursion-theoretic ideas, that if $\alpha$ is a gap ordinal, that is, $(L_{\alpha+1}\smallsetminus L_\alpha)\cap\mathcal P(\omega)=\emptyset$, then $L_\alpha\cap \mathcal P(\omega)$ is closed under the hyperjump operation.
MR0419200 (54 #7232). Leeds, Stephen; Putnam, Hilary. An intrinsic characterization of the hierarchy of constructible sets of integers. In Logic Colloquium '69 (Proc. Summer School and Colloq., Manchester, 1969), pp. 311–350. North-Holland, Amsterdam, 1971.
This condition can be rephrased as saying that $$(\omega,\mathcal P(\omega)\cap L_\alpha,0,S,+,\cdot,<,\in)$$ (in short, $\mathcal P(\omega)\cap L_\alpha$) is a model of second-order arithmetic $\mathsf{Z}_2$. This is the theory consisting of the second-order version of Peano arithmetic, together with the comprehension scheme that states that for any formula $\varphi(n)$, $\{m:\varphi(m)\}$ exists.
This result is reproved by using set-theoretic techniques in section 2 of the paper. Note that if $\alpha$ is a gap ordinal, then obviously $\mathcal P(\omega)\cap L_\alpha$ satisfies comprehension. To see that induction holds as well is argued indirectly, using prior results of Zbierski and a characterization of constructibility due to Addison. The point is that Zbierski proved that $\mathcal P(\omega)\cap L_\alpha\models\mathsf{Z}_2$ precisely when the reals of $L_\alpha$ code a model of $\mathsf{ZF}^-+V={\rm HC}$.
But I think that not going beyond this result is somewhat unsatisfactory, as it seems that we have simply rephrased the question. In fact, Marek and Srebrny have much more to say and in particular bring matters relevant to fine structure to the forefront. For instance, say that $A\subseteq\omega\times\omega$ is an arithmetical copy of $L_\alpha$ if and only if, letting $F_A=\{n:\exists m\,((n,m)\in A\lor(m,n)\in A)\}$, $$ (F_A,A)\cong (L_\alpha,\in). $$ Note that there is at most one such $\alpha$ and that the isomorphism, if it exists, is unique as well, being the Mostowski collapse. Marek and Srebrny recall a result of Boolos, that can be found in
MR0239977 (39 #1331). Boolos, George; Putnam, Hilary. Degrees of unsolvability of constructible sets of integers. J. Symbolic Logic 33 1968 497–513.
The result states that $\alpha$ is not a gap ordinal, that is, $$(L_{\alpha+1}\smallsetminus L_\alpha)\cap\mathcal P(\omega)\ne\emptyset,$$ if and only if this set contains an arithmetical copy of $L_\alpha$.
Although they say much more (and so do all the other references I have listed), I think this is the key result, since it gives us a "canonical witness" and a concrete way of verifying that some levels of the constructible hierarchy admit new reals. Fine structure theory goes more deeply and studies the complexity of the definition of these mastercodes. For example, it is a good exercise to check that no $\alpha<\omega^2$ is a gap ordinal by directly verifying that there are arithmetical copies of $L_\alpha$ in $L_{\alpha+1}$ (see a bit more on this below). This is not the only way. Studying Zbierski's argument (or the version of this result given by Marek) shows explicit ways how new reals must appear (related to the codes I mentioned above) if $\mathcal P(\omega)\cap L_\alpha\not\models\mathsf{Z}_2$.
MR0307907 (46 #7022). Zbierski, P. Models for higher order arithmetics. (Russian summary) Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 19 (1971), 557–562.
In his answer, Noah essentially mentioned the key to getting started in the "exercise" I suggested. Note first that $L_n=V_n$ for all $n<\omega$ and so $L_\omega=V_\omega$ as well. But $(V_\omega,\in)$ is essentially the same as the standard structure of first-order arithmetic, $\mathbb N=(\omega,0,S,+,\cdot,<)$. So, the reals in $L_{\omega+1}$ are simply the subsets of $\omega$ that are first-order definable in arithmetic. In recursion theoretic terms, these are the sets Turing reducible to the iterated Turing jumps $0^{(n)}$ for some $n<\omega$. The uniformity of the definition of the jump gives us then that $0^{(\omega)}$ is indeed a member of $L_{\omega+2}$, and it is not hard to see that $0^{(\omega)}$ codes true arithmetic (the theory of $\mathbb N$) and so the theory of $(L_\omega,\in)$, from which one can easily obtain a code for $L_{\omega+1}$.
This is probably worth emphasizing: Each $L_{\alpha+1}$ is just the collection of subsets of $L_\alpha$ definable over $L_\alpha$, and as long as things are fairly concrete, this readily gives us that the theory of $L_\alpha$ can be reshaped as a code for $L_{\alpha+1}$ itself.
Now, you get reals in $L_{\omega+2}$ significantly more complicated than $0^{(\omega)}$, since you can define not just $0^{(\omega)}$ but also its iterated jumps $0^{(\omega+n)}$, $n<\omega$. This should suggest how to continue. As long as we are working on a very concrete small ordinal, the pattern persists (so, one manages to define this way new reals at all $L_{\alpha+1}$ not just for $\alpha<\omega^2$ but for a much longer initial segment of the ordinals.
Fine structure theory gives us the tool to one sees how this pattern persists and generalizes, with an emphasis on the complexity of the definitions. In particular, we get that as soon as a new unbounded subset of some ordinal $\alpha$ is added at some stage $L_{\beta+1}$, $L_{\beta+1}$ actually sees a surjection from $\alpha$ onto $L_\beta$.
As desired, here is a simple example of a real in the $L_{\omega+2}$ but not in $L_{\omega+1}$:
There is a natural way to interpret $L_\omega$ as $\mathbb{N}$; via this, we can treat elements of $L_\omega$ as Godel numbers for sentences. Then it's not hard to show that, for $\alpha\ge\omega$ and $n\in\omega$, the real coding $Th_n(L_\alpha; \in)$ (the $n$-quantifier fragment of the theory of the structure $(L_\alpha; \in)$ is an element of $L_{\alpha+1}$. And we can "piece together" these fragments if we go up one level: for $\alpha\ge\omega$, the real coding the full theory of $(L_\alpha; \in)$ is an element of $L_{\alpha+2}$.
Moreover, since every element of $L_\omega$ is definable in the structure $(L_\omega; \in)$, it is also not hard to show that every real in $L_{\omega+1}$ is computable from the real coding $Th_n(L_\omega; \in)$ for some $n\in\omega$. This means:
The real coding the full theory of $(L_\omega;\in)$ is an element of $L_{\omega+2}\setminus L_{\omega+1}$.
Via the Ackermann interpretation noted above, this also tells us:
The real coding the full theory of $(\mathbb{N}; +,\times)$ is in $L_{\omega+2}\setminus L_{\omega+1}$.
Speaking computability-theoretically, yet another way to say this is:
The real $0^{(\omega)}$ is in $L_{\omega+2}\setminus L_{\omega+1}$.
Note that this does not work for every level of $L$ - there is no reason we can't have the real coding $Th(L_\alpha;\in)$ in $L_\alpha$ already, in general (although of course it can't be a definable element of $(L_\alpha; \in)$). But it does show how new reals can show up.
If you like this picture, you may enjoy reading the beginning of Hodes' paper on the mastercode hierarchy.
Here's yet another way we can see new reals appear in $L$; although this one is less direct, it is still pretty cool in my opinion - it uses elementary submodels and absoluteness.
Note that this is very closely related to Asaf's answer; it's really the same thing, phrased differently.
For $\alpha<\omega_1^L$, $L_{\omega_1^L}\models$"$\alpha$ is countable" - that is, there is an injection $f:\alpha\rightarrow\omega$ in $L_{\omega_1^L}$. By "pushing $\alpha$ through this injection," we get in $L_{\omega_1^L}$ a real coding an isomorphic copy of the linear order $(\alpha; \in)$ with domain $\omega$.
Alright, fix $\alpha<\omega_1^L$; I claim there is a real in $L_{\omega_1^L}\setminus L_\alpha$.
Via Lowenheim-Skolem and the Mostowski collapse, let $M$ be a countable transitive model of ZFC with $L_\alpha\subseteq M$. (If you'd rather not assume the existence of a well-founded model of ZFC, just note that we'll only need a finite fragment of ZFC for what follows, and apply the reflection theorem.)
Let $\beta=M\cap Ord$ be the height of $M$, and note that $\alpha<\beta<\omega_1^L$. Note that being an ordinal is a bounded-quantifier property, so absolute: $(i)$ everything $M$ thinks is an ordinal is an ordinal and $(ii)$ everything in $M$ which is an ordinal, $M$ thinks is an ordinal. That is, $Ord^M=M\cap Ord$.
Since $\beta<\omega_1^L$, we must have some real $r\in L_{\omega_1^L}$ coding an isomorphic copy of $(\beta;\in)$ with domain $\omega$; I claim $r\not\in M$, hence $r\not\in L_\alpha$.
To see this, suppose $r\in M$. Coding a well-ordering is a $\Pi^1_1$ fact, so by Mostowski absoluteness $M$ also thinks $r$ codes a well-ordering. Now ZFC proves that every well-ordering is in order-isomorphism with some ordinal; let $\gamma\in M\cap Ord$ be such that $M$ thinks there is an order-isomorphism from the linear order coded by $r$ to $\gamma$. Being an order-isomorphism is a bounded-quantifier property, so absolute between $M$ and $V$; hence we have $\gamma=\beta$. But this is a contradiction: no transitive model can contain its own height.