7
$\begingroup$

Let $\mathrm{ZF^-}$ be $\mathrm{ZF}$ minus power set, and let $\beta_0$ be the ordinal for ramified analysis so that $\mathrm{L}_{\beta_0}$ is the least $\mathrm{L}$-model of $\mathrm{ZF}^-$. Clearly, set theory $\mathrm{ZF^-+V=L_{\beta_0}}$ only has countably many sets, which are all countable.

What is the least ordinal $\chi$ such that $\mathrm{L}_\chi$ has a surjection from $\omega$ to $\mathrm{L}_{\beta_0}$?

For $\beta_0$, cfr. P. D. Welch The Ramified Analytical Hierarchy using Extended Logics, pp. 3-4.

Improve this question
$\endgroup$
8
  • 5
    $\begingroup$ Won't it be $\beta_0+1$? I thought these things come right away whenever something new happens like that. But I'll let the fine-structure experts correct me... $\endgroup$
    – Joel David Hamkins
    Commented Jul 18 at 15:06
  • 9
    $\begingroup$ @JoelDavidHamkins's guess is also my first guess, and if it turns out to be wrong then my second guess is $\beta_0+2$. $\endgroup$
    – Andreas Blass
    Commented Jul 18 at 15:18
  • 5
    $\begingroup$ I guess there’s no surjection at $\beta_0+1$ since replacement says every definable function on $\omega$ is bounded. But there is one at the next level, as Andreas says, because the satisfaction predicate appears there (in some awful coding) and $L_{\beta_0}$ is pointwise definable. The details are probably not that nice though $\endgroup$
    – Gabe Goldberg
    Commented Jul 18 at 15:54
  • 2
    $\begingroup$ @GabeGoldberg Ah yes, of course! I don't think the encoding is so bad, since we are going to get the $\Sigma_n$ truth predicate arriving at $L_{\beta_0+1}$ for each $n$, and so you just have to recognize these as satisfying the Tarski recursion and put them together. So the truth predicate arrives at $\beta_0+1$, and since it must be pointwise definable (by minimality), this gives the surjection. Basically, you map $n$ to the unique thing fulfilling the $n$th formula in the unique truth predicate covering that formula, if there is such a thing, and a default value otherwise. $\endgroup$
    – Joel David Hamkins
    Commented Jul 18 at 17:52
  • 2
    $\begingroup$ @FrodeAlfsonBjørdal I'll write within a day $\endgroup$
    – Gabe Goldberg
    Commented Jul 18 at 18:21

2 Answers 2

Reset to default
9
$\begingroup$

By replacement in $L_{\beta_0}$, there is no function from $\omega$ to $L_{\beta_0}$ that is definable over $L_{\beta_0}$ from parameters. Therefore no such function is in $L_{\beta_0+1}$. On the other hand, there is such a function in $L_{\beta_0+2}$. To see this, note that $L_{\beta_0}$ is pointwise definable in the sense that every element of $L_{\beta_0}$ is definable (without parameters) in $L_{\beta_0}$. This yields a partial surjection $f : \omega\to L_{\beta_0}$: let $(\varphi_n)_{n< \omega}$ be a recursive enumeration of all formulas in the language of set theory with one free variable, and define $f(n)$ to be the unique $a\in L_{\beta_0}$ such that $L_{\beta_0}\vDash \varphi_n(a)$ if such an $a$ exists, and $f(n) = \emptyset$ otherwise.

The function $f$ is definable over the structure $(L_{\beta_0},S)$ where $S$ is the satisfaction predicate for $L_{\beta_0}$, which for convenience let's take to be the set of pairs $(n,a)\in \omega\times L_{\beta_0}$ such that $L_{\beta_0}\vDash \varphi_n(a)$. Note that $S\in L_{\beta_0+2}$: each of its finite restrictions $S\cap (n\times L_{\beta_0})$, for $n < \omega$, is in $L_{\beta_0+1}$, and therefore $S$ can be defined in $L_{\beta_0+2}$ by Tarski's celebrated recursion. It follows that $f$ is in $L_{\beta_0+2}$ (i.e., is definable over $L_{\beta_0+1}$), since $f$ is definable over $L_{\beta_0}$ using the predicate $S$, which is itself definable over $L_{\beta_0+1}$.

Improve this answer
$\endgroup$
0
9
$\begingroup$

As a precoda to Gabe's answer, it's worth noting that $\beta_0$ is in fact the first ordinal $\alpha$ which "starts a gap," i.e. such that $L_{\alpha+1}\models$ "$\alpha$ is uncountable." (To be precise, "$\alpha$ starts (or continues) a gap" means "$L_{\alpha+1}\cap\mathbb{R}=L_\alpha\cap\mathbb{R}$" - however, these turn out to be equivalent.)

The other half of Gabe's answer shows that the gap started by $\beta_0$ is only of length $1$, and indeed we have to wait a long while for the first "length $2$ gap" ordinal since if $L_\alpha$ is pointwise-definable then $L_{\alpha+2}\models\vert\alpha\vert=\omega$. In fact, the smallest ordinal starting a length $2$ gap is the limit of itself-many ordinals starting length 1 gaps, basically for the same reason.

Madore has a nice survey of this sort of thing; see 2.17 in particular. For a published source, Marek/Srebrny, Gaps in the constructible universe has relevant information (both on $\beta_0$ being the first gap ordinal and on the size of the smallest length-2 gap ordinal). Finally, while only slightly related I really like the exposition in Gostanian, The next admissible ordinal.

Improve this answer
$\endgroup$
11
  • 2
    $\begingroup$ I'll be honest, I mostly wrote this as an excuse for "precoda." $\endgroup$
    – Noah Schweber
    Commented Jul 18 at 19:22
  • 1
    $\begingroup$ @FrodeAlfsonBjørdal No, not at all. $\beta_0$ being uncountable in $L_{\beta_0+1}$ does not imply that $\beta_0$ is uncountable in reality - remember, "uncountable in $L_\alpha$" just means "has no injection to $\omega$ in $L_\alpha$." $\endgroup$
    – Noah Schweber
    Commented Jul 18 at 19:52
  • 1
    $\begingroup$ @FrodeAlfsonBjørdal I'm using the standard set theory notation here: $\omega_1$ is the first uncountable (in reality) ordinal, and $\omega_2$ is the first ordinal not in bijection with $\omega_1$ (again in reality). These are of course galactically bigger than their (countable) effective analogues $\omega_1^{CK}$ and $\omega_2^{CK}$. $\endgroup$
    – Noah Schweber
    Commented Jul 18 at 20:02
  • 4
    $\begingroup$ Incidentally, old texts do often write "$\omega_1$" for "$\omega_1^{CK}$," which has obviously never caused confusion ever; I mean, when do we ever discuss higher recursion theory and set theory in the same breath? :P $\endgroup$
    – Noah Schweber
    Commented Jul 18 at 20:03
  • 3
    $\begingroup$ @NoahSchweber I think you forgot the <sarcasm> </sarcasm> delimiters... $\endgroup$
    – Joel David Hamkins
    Commented Jul 19 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .