# 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$?

• Have you looked at the reference I suggested or at Jensen's fine structure paper? Both explain why (the point being that new reals are the reason why an ordinal is the end of a gap). For instance, you may be able to define a new theory (coding the current level of constructibility). You did not have this theory before, because you can define all elements of the current level from it. Look up the notion of mastercode, for example. Dec 1, 2017 at 15:28
• @AndrésE.Caicedo: I did read the paper you suggested, but I didn't manage to understand what I was hoping to understand. I did not read Jensen's paper, as I got the impression from your comment that it is even more difficult. Should I? That is, do you think there's a decent chance I might understand the latter paper better than the former? Dec 1, 2017 at 15:39
• I don't know, but one of the explicit motivations for the development of fine structure is to answer your question. Dec 1, 2017 at 16:17
• It's a bit rude when someone takes the time to write an answer to your question, and the only interaction is a week later when you edit the question to say "Hey, no, the answer doesn't satisfy me". Dec 1, 2017 at 17:05
• Why is that rude? Is it rude that I didn’t comment on your answer with a “thank you”? I believe that kind of thing is discouraged; that is what upvoting is for, and I did. Is it rude that I took a week? I needed time to read “Gaps in the constructible universe”. Is it rude that I made an update to my post instead of a comment to your answer? I just figured I would ask everybody for help instead of just you specifically. Is it rude that there are things I still don’t understand? Dec 1, 2017 at 17:31

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$.

• Concerning your penultimate paragraph: Do we know exactly which initial segment of the ordinals? That is, what is the first ordinal where no new real number can be defined (in this way)? Dec 3, 2017 at 14:37
• Yes, this is addressed in the Marek-Srebrny paper (theorem 2.7): $\alpha$ starts a gap if and only if $L_\alpha\models\mathsf{ZFC}^-+V=HC$. Dec 3, 2017 at 14:59
• Note in particular that if $X\in L_\alpha\cap\mathcal P(\omega\times\omega)$ is a well-ordering of type $\beta$, then $\beta<\alpha$. For instance, the least such $\alpha$ is strictly larger than $\omega_1^{\mathrm{CK}}$. In fact, $\alpha$ starts a gap if and only if $\alpha$ is $\Sigma_n$-admissible for all $n$ and $L_\alpha$ is locally countable (meaning that each element of $L_\alpha$ can be injected into $\omega$ via a function in $L_\alpha$). Dec 3, 2017 at 17:54

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.

• Ok, I think I understand (at least) the first half of your answer. Can I just check that I got it right: There is a set $N\subset\mathbb{N}$ such that it is both the case that (1) $N$ is the set of G\"odel codes of the sentences that are true of $(L_\omega;\in)$ and (2) $N$ is a new real number at level $\omega+2$ (?) Dec 3, 2017 at 14:31
• Also, where was this proved (first)? Is that one of the papers in Andrés' list? Dec 3, 2017 at 15:30
• @Casper That's correct. As to where this was first proved, I'm not sure it's ever stated specifically. It's certainly implicit in the stronger theorems about gaps, and if you read their proofs you'll see how they are in fact strengthenings of this observation; you might also look at Godel's original paper. Dec 4, 2017 at 20:54
• @MikeBattaglia Yes - look for the term "master codes" (e.g. there's a paper by Hodes on the topic). Apr 23 at 4:38
• @MikeBattaglia The issue is that you need to be able to see that (enough of) the relevant level of $L$ is countable in order to do this diagonalization. So the way these gap ordinals behave is that if $\alpha$ is a gap ordinal then $L_{\alpha+1}$ does not contain a bijection $\alpha\rightarrow\omega$, and we have to wait around for enough information to creep in for us to figure out how to diagonalize. Apr 23 at 5:11