Es allí cualquier generalización de la hyperarithmetical jerarquía uso de la analítica de la jerarquía de fórmulas pertenecientes a la tercera orden de la lógica y de arriba?

Question

Como yo lo entiendo, hyperarithmetical conjuntos se definen de acuerdo con el analítico de jerarquía, es decir, de segundo orden-la lógica de las fórmulas. Hay una generalización de hyperarithmetic teoría denominada α-la teoría de la recursividad. Hacer esta extensión se generaliza el hyperarithmetical de los conjuntos los conjuntos definibles con cualquier arbitrario de orden superior de la lógica?

NOTA: sé que α-la teoría de la recursividad se extiende la hyperarithmetical conjuntos de ${\omega}_1^{CK} $ a cualquier admisible ordinales, pero no tengo ni idea de lo que significa o lo que es la relación entre los números ordinales y el número de N en N-la lógica de orden). Mi pregunta al final es motivado por el hecho de que el hyperarithmetical conjuntos se pueden definir usando infinitamente iterada de Turing saltos, y me pregunto si esto se puede generalizar a conjuntos definidos por cualquier fórmula (por arbitrarias me refiero a usar cualquier arbitrario de orden superior, la fórmula de la lógica).

Answer 1

Asaf señaló a algunos recursos sobre la principal pregunta que usted me hizo, acerca de la jerarquía de $\Sigma^2_n$ conjuntos. Me temo que no puede ofrecer más ayuda en eso, pero ya que usted también mencionó $\alpha$-recursividad y hyperarithmetic pero que no estaban claros en lo que estaban, pensé que al menos podría dar una breve reseña.

Vamos a comenzar por la revisión de algunas definiciones básicas. Obtenemos la aritmética jerarquía finito de iteraciones de Turing saltar operador, comenzando con el conjunto vacío. El $\Sigma^0_n$ conjuntos son aquellos que son recursivamente enumerables en $0^{(n-1)}$, $\Pi^0_n$ conjuntos de aquellos que son co-recursivamente enumerable en $0^{(n-1)}$, y el $\Delta^0_n$ conjuntos de aquellos que son recursivos en $0^{(n-1)}$ ( $n \geq 1$ ). Un conjunto es aritmética sólo en caso de que se $\Sigma^0_n$ algunos $n \in \mathbb{N}$.

Ahora, supongamos que queremos ir más allá y definir el $\omega$-salto, $0^{(\omega)}$. Este es recursivamente isomorfo a primer orden de la teoría de los números naturales, $Th(\mathbb{N})$. Por Tarski del teorema $Th(\mathbb{N})$ no puede ser definido por ningún aritmético de la frase, por lo $0^{(\omega)}$ no pueden ser aritméticos. Si queremos hablar de la definability de conjuntos como $0^{(\omega)}$ (que es, recuerda, sólo un subconjunto de los números naturales) entonces tendremos necesidad de ir más allá de la aritmética y de la jerarquía en hyperarithmetic.

El hyperarithmetical conjuntos se obtienen como la aritmética son, por iteración Turing saltar. Es sólo que ahora reiteramos, no por números naturales, pero a lo largo recursiva ordinales. Un ordinal $\alpha$ es recursivo ordinal iff existe una relación recursiva $<_c$ $X \subseteq \mathbb{N}$ que es un wellordering de orden de tipo $\alpha$. Y un conjunto $Y \subseteq \mathbb{N}$ es hyperarithmetical iff $Y$ es recursivo en $0^{(\delta)}$ para algunos recursiva ordinal $\delta$.

Usted mencionó que el analítico de jerarquía en el comienzo de su pregunta en relación con hyperarithmetic, pero en realidad la hyperarithmetic conjuntos son muy muy abajo en la jerarquía analítica: son precisamente los $\Delta^1_1$ conjuntos. En términos de definability podemos ir mucho más allá con el análisis de la jerarquía de lo que podemos con hyperarithmetic. Por ejemplo, el conjunto de $\mathcal{O}$ de notaciones para recursiva ordinales es una $\Pi^1_1$ conjunto completo. El supremum de los ordinales que han anotaciones en $\mathcal{O}$$\omega_1^{CK}$, el primer no-recursiva ordinal. Por lo $\omega_1^{CK}$ juega el mismo papel para el hyperarithmetical establece como $\omega$ lo hace para la aritmética establece.

Esto nos lleva a la siguiente generalización, $\alpha$-recursividad. ¿Qué sucede cuando en lugar de $\omega_1^{CK}$ consideramos arbitraria en el ordinal $\alpha$? Claramente no sólo ninguna de las $\alpha$ hará: debe tener alguna de las buenas propiedades para cierre disfrutado por $\omega$$\omega_1^{CK}$. Esto conduce a la noción de un admisibles ordinal: ordinal $\alpha$ tal que $L_\alpha$ es un modelo transitivo de Kripke–Platek la teoría de conjuntos. $\omega$ $\omega_1^{CK}$ son los dos primeros admisible ordinales. Dada la admisión de un ordinal $\alpha$, $\alpha$-recursiva se define como $\Delta^0_1$ $L_\alpha$ mientras $\alpha$-recursivamente enumerable es$\Sigma^0_1$$L_\alpha$. Las definiciones de la relación de recursividad, y el salto de operación son más complejos, así que ahí te dejo con los Sacos del libro.

Answer 2

No sé lo suficiente como para dar una respuesta completa, pero le he preguntado (al menos) dos prominentes conjunto de los teóricos acerca de esto hace un año.

Yo estaba contemplado para los trabajos de Abraham Y Sela acerca de tercer orden-orden de los números reales:

1. Un $\Delta^2_2$ Bien el Orden de los Reales Y Incompactness de $L(Q^{MM})$. Anales de la Pura y Aplicada de la Lógica 59 (1993) 1--32.

2. Martin axioma y $\Delta^2_1$ buen orden de los reales. Archivo de la Lógica Matemática, 35 (1996) 287--298.

3. Codificación con escaleras de un buen orden de los reales. El Diario de la Lógica Simbólica, 67, Número 2 (2002) 579--597.