# How early do the second-order definable subsets of $\mathbb{N}$ occur in the Constructible Universe?

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

• What If we assume $V=L$? Then what is $\alpha$? – Keshav Srinivasan May 14 at 3:30
• Does $V=L$ imply that $\alpha=\beta_0$, or $\alpha>\beta_0$, or what? – Keshav Srinivasan May 14 at 13:47
• 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$? – Keshav Srinivasan May 16 at 7:06
• @KeshavSrinivasan Addressed. – Noah Schweber May 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.)

• What if we assume $V=L$? What does that imply about the smallest $\alpha$ such you get full comprehension in $L_\alpha$? – Keshav Srinivasan May 14 at 22:02
• 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). – Noah Schweber May 14 at 22:06
• @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.) – Not Mike May 15 at 0:02
• @NoahSchweber Oh! Wow I'm dense. Yeah, you're right. – Not Mike May 15 at 0:46
• @NotMike So what’s the conclusion? What does $V=L$ imply about all this? – Keshav Srinivasan May 15 at 22:17