Skip to main content
added 2 characters in body
Source Link
Asaf Karagila
  • 39.8k
  • 8
  • 135
  • 283

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}$$L_{\omega_1^{CK}}$.

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

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

Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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