$ZFC+V=L$ implies that $P(\mathbb{N})$ is a subset of $L_{\omega_1}$. But I’m wondering what layer of the constructible Universe contains a smaller set.

My question is, what is the smallest ordinal $\alpha$ such that for all formulas $\phi(n)$ in the language of second-order arithmetic, the set $\{n\in\mathbb{N}:\phi(n\}\in L_\alpha$? Does this depend on whether we assume $V=L$?

I’m guessing $\alpha>\omega_1^{CK}$, and that $\alpha$ is greater than the ordinal $\beta_0$ discussed in my question here. But can we say anything more about it?


It is consistent that there is no such $\alpha$.

More precisely, it is consistent with ZFC that there is a formula $\varphi$ in the language of second-order arithmetic such that $\{x:\varphi(x)\}$ is not constructible. For example, $0^\sharp$ if it exists has this property (it's $\Delta^1_3$-definable if it exists).

EDIT: Of course, if V = L then such an $\alpha$ trivially exists. Throughout the rest of this answer we assume V=L.

The key point is that there is a "definable translation" between first-order formulas over $L_{\omega_1}$ and second-order formulas of arithmetic:

  • One direction is immediate: any second-order arithmetic formula can be rephrased in $L_{\omega_1}$ since sets of naturals are already elements of $L_{\omega_1}$.

  • The other direction is the interesting one. Given a well-founded tree $T\subset\omega^{<\omega}$ (note that we can definably conflate subsets of $\omega$ and subsets of $\omega^{<\omega}$, and that the set of well-founded trees is second-order definable), we recursively define a map $Set_T$ from nodes of $T$ to sets, by setting $$Set_T(\sigma)=\{Set_T(\sigma^\smallfrown \langle k\rangle): k\in\omega, \sigma^\smallfrown\langle k\rangle\in T\};$$ for example, if $\sigma$ is a leaf of $T$ then $Set_T(\sigma)=\emptyset$. We then let $Set(T)=Set_T(\langle\rangle)$ be the set assigned to the empty string (= the root of $T$). It's easy to check that the relations "$Set(T_0)=Set(T_1)$" and "$Set(T_0)\in Set(T_1)$" are definable in second-order arithmetic, and this gives us an interpretation of $L_{\omega_1}$ into $\mathcal{P}(\omega)$.

The projectively-definable reals are precisely the parameter-freely definable elements of the first-order structure $(\omega,\mathcal{P}(\omega); +,\times,\in)$, and the translation above identifies these with the set $M$ of parameter-freely definable elements of the first-order structure $(L_{\omega_1}; \in)$ (which I'll conflate with $L_{\omega_1}$).

The final point is that since $L$ has definable Skolem functions, $M$ is in fact an elementary submodel of $L_{\omega_1}$ and hence$^1$ $M=L_\eta$ for some $\eta$. This $\eta$ is exactly our $\alpha$. That is:

Assuming V=L, $\alpha$ is the height of the smallest elementary submodel of $L_{\omega_1}$.

In particular, this is massively bigger than $\beta_0$, since $\beta_0$ is parameter-freely definable in $L_{\omega_1}$.

$^1$This is a cute fact. The Condensation Lemma alone doesn't kill this off: in order to apply Condensation we need to know that $M$ is transitive. But a priori, it's not clear that it needs to be - for example, a countable elementary submodel of $L_{\omega_2}$ obviously can't be transitive, since it must contain $\omega_1$ as an element.

So what's special about $\omega_1$ here? The trick here is the following:

Suppose $A$ is a "sufficiently closed" transitive set (= contains $\omega$ and such that eveyr countable element of $A$ is countable within $A$) - for example, $A=L_{\omega_1}$ - and $B$ is an elementary substructure of $A$ (conflating a transitive set with the corresponding $\{\in\}$-structure as usual). Then the set of countable ordinals in $A$ is closed downwards.

Rough proof: Suppose $\theta$ is a (WLOG infinite) countable ordinal in $A$ and $\gamma<\theta$. Since $A$ computes countability correctly we have in $A$ an $f: \omega\cong\theta$. By elementarity "going down," $B$ contains some $g$ which $B$ thinks is a bijection from $\omega$ to $\theta$; by elementarity "going up," $A$ also thinks $g$ is. So (working in $A$) there is some $n\in\omega$ such that $g(n)=\gamma$; but since $n\in\omega$ we have $n\in B$ (we can't "lose" natural numbers!) and so $g(n)=\gamma\in B$ as well. $\Box$

We can generalize the above observation using further closedness assumptions: e.g. if $B$ is an elementary submodel of a sufficiently closed transitive set $A$ with $\omega_1\subseteq B$ then $B\cap\omega_2$ is closed downwards (running the above argument, we only need that $dom(g)\subset B$).

  • $\begingroup$ What If we assume $V=L$? Then what is $\alpha$? $\endgroup$ – Keshav Srinivasan May 14 '19 at 3:30
  • $\begingroup$ Does $V=L$ imply that $\alpha=\beta_0$, or $\alpha>\beta_0$, or what? $\endgroup$ – Keshav Srinivasan May 14 '19 at 13:47
  • $\begingroup$ Does the fact that $L_{\beta_0}\cap P(\mathbb{N}$ is a $\beta$-model for second-order arithmetic shed any light on whether $V=L$ implies $\alpha=\beta_0$? $\endgroup$ – Keshav Srinivasan May 16 '19 at 7:06
  • 1
    $\begingroup$ @KeshavSrinivasan Addressed. $\endgroup$ – Noah Schweber May 19 '19 at 6:28

What you want is the least $\delta \in \mathsf{On}$ such that $L_\delta \vDash "\mathsf{ZFC}^{-}+V=HC"$ (where $V=HC$ is the assertion that every set is hereditarily countable.) Since the theory "$\mathsf{ZFC}^{-} + V=HC$" is bi-interpretable with second-order arithmetic, you'll get a relativized version of second-order comprehension.

If the relativzed version of $\mathsf{SOA}$ is acceptable to you, then it's possible for $\delta$ to be countable; that said, if you want full comprehension, then as @Noah pointed out, it's consistent that no such $\delta$ exists (countable or otherwise.)

  • $\begingroup$ What if we assume $V=L$? What does that imply about the smallest $\alpha$ such you get full comprehension in $L_\alpha$? $\endgroup$ – Keshav Srinivasan May 14 '19 at 22:02
  • $\begingroup$ I don't think this is right - I think they want the relative-to-$L$ version. I don't see that $L_\delta$ needs to compute projective truth correctly (in fact, it won't, since there is a projectively definable real coding it). $\endgroup$ – Noah Schweber May 14 '19 at 22:06
  • $\begingroup$ @NoahSchweber I don't understand. Are you saying that $(\omega, L_\delta \cap \mathcal{P}(\omega), \ldots)$ won't provide a Henkin model for the many-sorted analogy of $\mathsf{SOA}$? (This is what I intended to convey with the emphasis on it being relativized.) $\endgroup$ – Not Mike May 15 '19 at 0:02
  • $\begingroup$ @NoahSchweber Oh! Wow I'm dense. Yeah, you're right. $\endgroup$ – Not Mike May 15 '19 at 0:46
  • $\begingroup$ @NotMike So what’s the conclusion? What does $V=L$ imply about all this? $\endgroup$ – Keshav Srinivasan May 15 '19 at 22:17

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.