Precise interpretability strength of $\mathcal P_{DF}(\omega)$ and $L_{\omega_1^{CK}}$

Question

I am curious about the relationship between the definable power set of $\omega$ and the $\omega_1^{CK}$th level of the constructible sets $L$.

In short, $\omega_1^{CK}$ is the least nonrecursive ordinal (that is, the first ordinal with no recursive description in Kleene's $\mathcal O$, a hyperarithmetical set), and $L$ is a model of $ZFC$ constructed by a weakening of the power set axiom in the following manner:

Let $\mathcal P_{DF}(S) := \{X_i \subseteq S: {X_i}$ is definable from first-order parameters in ${S}\}$. To construct $L$, we have:

$L_0$ := $\varnothing$

$L_{\kappa+1}$ := $\mathcal P_{DF}(L_\kappa)$

$L_\lambda$ := $\bigcup\limits_{\kappa < \lambda} L_\kappa$ ($\lambda$ = limit ordinal).

and $L$ := $\bigcup\limits_{\kappa \in ORD} L_\kappa$

It has been remarked that $\mathcal O$ is the existential theory of $L_{\omega_1^{CK}}$. Clearly, $\omega \models PA$, so it is natural that $\mathcal P_{DF}(\omega) \models PA$ since all the recursive sets are contained in the standard system of first-order definable sets, denoted $SSY(\omega)$, and thus would appear at some countable level in $L$ by definition. Furthermore, we can see that $\mathcal P_{DF}(\omega) \subseteq L_{\omega_1^{CK}}$ follows also by definition of $L$.

My question is this: Can we say that $\mathcal P_{DF}(\omega)$ has the same relative interpretability power as $L_{\omega_1^{CK}}$ by virtue of its first-order definable closure of the recursive sets, in the same way that $\mathcal O$ is the existential theory of $L_{\omega_1^{CK}}$ as it preserves all "$\mathbf \Sigma^{1}_{1}$ -canonical" properties of the recursive sets at the $\omega_1^{CK}$th level in $L$?

If not, it would appear that $L_{\omega_1^{CK}}$ is "just above" $\mathcal P_{DF}(\omega)$ in its interpretability strength, but I am unsure how to make this notion of being "just above" anymore precise without a vague reference to $\mathcal O$ being the existential theory of $L_{\omega_1^{CK}}$.

Answer 1

I'm not sure exactly what you're asking, since I don't know what you mean by "interpretability power," but let me take a stab at this:

The structure $\mathcal{P}_{DF}(\omega)$ is precisely $L_{\omega+1}\cap\mathbb{R}$; this is vastly smaller than $L_{\omega_1^{CK}}\cap\mathbb{R}$, which is the set of all hyperarithmetic sets.

"Smoothing" things out via interpretability doesn't help: $L_{\omega_1^{CK}}$ is still vastly bigger. The usual definition of "interpretation" is the following:

A structure $\mathcal{A}$ is interpretable in a structure $\mathcal{B}$ if there are formulas $\varphi_i$ in the language of $\mathcal{B}$ (with parameters in $\mathcal{B}$) such that, if we interpret $\varphi_0^\mathcal{B}$ as the domain of a structure and the $\varphi_{i+1}$s as the symbols in the language of $\mathcal{A}$, we get a structure isomorphic to $\mathcal{A}$.

Using this definition, there is no interpretation of $(L_{\omega_1^{CK}}, \in)$ in $(L_{\omega+1}, \in)=\mathcal{P}_{DF}(\omega)$. This follows from the more general fact that, for any ordinal $\alpha$, there is no interpretation of $(L_{\alpha+2}, \in)$ in $(L_{\alpha}, \in)$. This is because interpretations are definable, so we can't go more than one level up the $L$-hierarchy. This means that there are many, many layers of interpretability between $\mathcal{P}_{DF}(\omega)$ and $L_{\omega_1^{CK}}$.

Answer 2

I am not certain what you mean by the "interpretability power" either, perhaps definability? But to give you some intuition on how much "stronger" $L_{\omega^{CK}_1}$ is than $L_{\omega+1}$, here are some facts:

1. $\omega_1^{CK}$ is the first admissible ordinal after $\omega$ meaning that $L_{\omega^{CK}_1}$ is an admissible structure. An ordinal $\alpha$ is admissible iff for every $\Sigma^1$-definable function $F$ over $L_\alpha$ it is true that for all $\beta < \alpha$: if $F(\beta)$ is defined, then $F(\beta)<\alpha$. This gives you a very strong closure property: $\omega^{CK}_1$ is closed under ordinal addition, multiplication, exponentiation, etc. But taking $\omega+1$, note that not even $\omega+\omega=\omega \cdot 2$ is in $L_{\omega+1}$. So I would rather measure the strength of an ordinal $\alpha$ and its universe $L_\alpha$ not merely by how large it is, but rather by which axioms (or their weakenings) of $ZFC$ are satisfied by $L_\alpha$. As you correctly observed $L_{\omega^{CK}_1}$ does not satisfy the powerset axiom, but it satisfies by an alternative definition of admissibility all the axioms of Kripke-Platek set theory.

2. From Sacks, Higher Recursion Theory: Let $\Sigma^{\omega_1^{CK}}_1$ be the class of subsets of $\omega^{CK}_1$ which are a domain of a function $\Sigma_1$-definable over $L_{\omega_1^{CK}}$. Let $Q \subseteq \mathcal{O}$ be a $\Pi^1_1$ set of unique notations of computable ordinals. Let $n:\omega_1^{CK} \to Q$ take each computable ordinal to its unique notation. Let $A \subseteq \omega_1^{CK}$. Then:

i) $A \in L_{\omega_1^{CK}} \iff n[A] \in \Delta^1_1$.

ii) $A \in \Sigma^{\omega_1^{CK}}_1 \iff n[A] \in \Pi^1_1$.

iii) $A \in \Delta_1^{\omega^{CK}_1} \iff A \in \Sigma^{\omega_1^{CK}}_1 \land \omega_1^{CK} - A \in \Sigma^{\omega_1^{CK}}_1$.

iv) Assume $A \subseteq \omega$. Then $A \in \Sigma^{\omega_1^{CK}}_1 \iff A \in \Pi^1_1$ and $A \in L_{\omega_1^{CK}} \iff A \in \Delta^1_1 \iff A \in \Delta_1^{\omega_1^{CK}}$

v) $f:\omega^{CK}_1 \to \omega^{CK}_1 \in \Sigma^{\omega_1^{CK}}_1 \iff \{\langle n(\gamma), n(f(\gamma)) \rangle : \gamma < \omega_1^{CK}\} \in \Pi^1_1$.

There is just no way that $L_{\omega+1} \cap 2^{\omega}$ would contain all the hyperarithmetic (i.e. $\Delta^1_1$) subsets of $\omega$.