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

  • 3
    $\begingroup$ In your question, are you using "interpretability power" in a technical sense? If not, what do you mean? Since ${\cal P}_{DF}(\omega)$ consists of exactly the arithemtically definable sets, whereas $L_{\omega_1^{CK}}$ has all hyperarithmetic sets, doesn't this reflect a fundamental difference in strength? After all, ${\cal P}_{DF}(\omega)$ is essentially $L_{\omega+1}$, and clearly the rest of the constructibility hierarchy between $\omega+1$ and $\omega_1^{CK}$ is nontrivial and important. $\endgroup$ – Joel David Hamkins Aug 27 '15 at 7:39

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

| cite | improve this answer | |

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

| cite | improve this answer | |

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.