teoría de la recursión alfa

En la teoría de la recursión , la teoría de la recursión α es una generalización de la teoría de la recursión a subconjuntos de ordinales admisibles.${\displaystyle \alpha }$Un conjunto admisible es cerrado bajo${\displaystyle \Sigma _{1}(L_{\alpha })}$funciones, donde${\displaystyle L_{\xi }}$denota un rango de la jerarquía constructible de Gödel .${\displaystyle \alpha }$es un ordinal admisible si${\displaystyle L_{\alpha }}$es un modelo de la teoría de conjuntos de Kripke-Platek . En lo que sigue${\displaystyle \alpha }$se considera fijo.

Los objetos de estudio en${\displaystyle \alpha }$la teoría de la recursión son subconjuntos de${\displaystyle \alpha }$Se dice que estos conjuntos tienen algunas propiedades:

• Un conjunto${\displaystyle A\subseteq \alpha }$Se dice que${\displaystyle \alpha }$-recursivamente enumerable si es${\displaystyle \Sigma _{1}}$definible sobre${\displaystyle L_{\alpha }}$, posiblemente con parámetros de${\displaystyle L_{\alpha }}$en la definición. ^{[ 1 ]}
• A es${\displaystyle \alpha }$-recursivo si tanto A como${\displaystyle \alpha \setminus A}$(su complemento relativo en${\displaystyle \alpha }$) son${\displaystyle \alpha }$-recursivamente enumerable. Cabe destacar que${\displaystyle \alpha }$-los conjuntos recursivos son miembros de${\displaystyle L_{\alpha +1}}$por definición de${\displaystyle L}$.
• Miembros de${\displaystyle L_{\alpha }}$se llaman${\displaystyle \alpha }$-finitos y desempeñan un papel similar al de los números finitos en la teoría clásica de la recursión.
• Miembros de${\displaystyle L_{\alpha +1}}$se llaman${\displaystyle \alpha }$-aritmética . ^{[ 2 ]}

También existen algunas definiciones similares para funciones de mapeo.${\displaystyle \alpha }$a${\displaystyle \alpha }$: ^{[ 3 ]}

• Una función parcial de${\displaystyle \alpha }$a${\displaystyle \alpha }$es${\displaystyle \alpha }$-recursivamente enumerable , o${\displaystyle \alpha }$-parcialmente recursivo , ^{[ 4 ]} si y solo si su grafo es${\displaystyle \Sigma _{1}}$-definible en${\displaystyle (L_{\alpha },\in )}$.
• Una función parcial de${\displaystyle \alpha }$a${\displaystyle \alpha }$es${\displaystyle \alpha }$-recursivo si y solo si su gráfico es${\displaystyle \Delta _{1}}$-definible en${\displaystyle (L_{\alpha },\in )}$. Al igual que en el caso de la teoría de la recursión clásica, cualquier total${\displaystyle \alpha }$-función recursivamente enumerable${\displaystyle f:\alpha \rightarrow \alpha }$es${\displaystyle \alpha }$-recursivo.
• Además, una función parcial de${\displaystyle \alpha }$a${\displaystyle \alpha }$es${\displaystyle \alpha }$-aritmético si y solo si existe algún${\displaystyle n\in \omega }$de tal manera que la gráfica de la función sea${\displaystyle \Sigma _{n}}$-definible en${\displaystyle (L_{\alpha },\in )}$.

Se pueden establecer conexiones adicionales entre la teoría de la recursión y la teoría de la recursión α, aunque es posible que aún no se hayan escrito definiciones explícitas para formalizarlas:

• Las funciones${\displaystyle \Delta _{0}}$-definible en${\displaystyle (L_{\alpha },\in )}$desempeñan un papel similar al de las funciones recursivas primitivas . ^{[ 3 ]}

Decimos que R es un procedimiento de reducción si es${\displaystyle \alpha }$recursivamente enumerable y cada miembro de R es de la forma${\displaystyle \langle H,J,K\rangle }$donde H , J , K son todos α-finitos.

Se dice que A es α-recursivo en B si existen${\displaystyle R_{0},R_{1}}$procedimientos de reducción tales que:

${\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],}$

${\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}$

Si A es recursivo en B, esto se escribe${\displaystyle \scriptstyle A\leq _{\alpha }B}$. Por esta definición A es recursivo en${\displaystyle \scriptstyle \varnothing }$(el conjunto vacío ) si y solo si A es recursivo. Sin embargo, que A sea recursivo en B no es equivalente a que A sea${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$.

Decimos que A es regular si${\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}$o en otras palabras, si cada porción inicial de A es α-finita.

Teorema de división de Shore : Sea A${\displaystyle \alpha }$recursivamente enumerable y regular. Existen${\displaystyle \alpha }$enumerable recursivamente${\displaystyle B_{0},B_{1}}$de tal manera que${\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}$

Teorema de densidad de Shore: Sean A y C conjuntos recursivamente enumerables α-regulares tales que${\displaystyle \scriptstyle A<_{\alpha }C}$entonces existe un conjunto B α-recursivamente enumerable regular tal que${\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}$.

Barwise ha demostrado que los conjuntos${\displaystyle \Sigma _{1}}$-definible en${\displaystyle L_{\alpha ^{+}}}$son exactamente los conjuntos${\displaystyle \Pi _{1}^{1}}$-definible en${\displaystyle L_{\alpha }}$, dónde${\displaystyle \alpha ^{+}}$denota el siguiente ordinal admisible superior${\displaystyle \alpha }$, y${\displaystyle \Sigma }$es de la jerarquía de Lévy . ^{[ 5 ]}

Existe una generalización de la computabilidad límite a parcial${\displaystyle \alpha \to \alpha }$funciones. ^{[ 6 ]}

Una interpretación computacional de${\displaystyle \alpha }$-la recursión existe, usando "${\displaystyle \alpha }$-Máquinas de Turing" con una cinta de dos símbolos de longitud${\displaystyle \alpha }$, que en los pasos de cálculo límite toman el límite inferior del contenido de la celda, el estado y la posición de la cabeza. Para admisible${\displaystyle \alpha }$, un conjunto${\displaystyle A\subseteq \alpha }$es${\displaystyle \alpha }$-recursivo si y solo si es computable por un${\displaystyle \alpha }$- Máquina de Turing y${\displaystyle A}$es${\displaystyle \alpha }$-recursivamente enumerable si y solo si${\displaystyle A}$es el rango de una función computable por un${\displaystyle \alpha }$-Máquina de Turing. ^{[ 7 ]}

Un problema en la teoría de la α-recursión que está abierto (a partir de 2019) es la conjetura de incrustación para ordinales admisibles, que es si para todos los ordinales admisibles${\displaystyle \alpha }$, los automorfismos de la${\displaystyle \alpha }$-los grados de enumeración se incrustan en los automorfismos de la${\displaystyle \alpha }$-grados de enumeración. ^{[ 8 ]}

Algunos resultados en${\displaystyle \alpha }$La teoría de la recursión se puede traducir en resultados similares sobre la aritmética de segundo orden . Esto se debe a la relación${\displaystyle L}$tiene con la jerarquía analítica ramificada, un análogo de${\displaystyle L}$para el lenguaje de aritmética de segundo orden que consiste en conjuntos de enteros. ^{[ 9 ]}

De hecho, cuando se trata solo de lógica de primer orden , la correspondencia puede ser lo suficientemente estrecha como para que algunos resultados en${\displaystyle L_{\omega }}$, las jerarquías aritméticas y de Lévy pueden volverse intercambiables. Por ejemplo, un conjunto de números naturales se puede definir mediante una${\displaystyle \Sigma _{1}^{0}}$fórmula si y solo si es${\displaystyle \Sigma _{1}}$-definible en${\displaystyle L_{\omega }}$, dónde${\displaystyle \Sigma _{1}}$es un nivel de la jerarquía de Lévy. ^{[ 10 ]} De manera más general, la definibilidad de un subconjunto de ω sobre${\displaystyle L_{\omega }}$con un${\displaystyle \Sigma _{n}}$La fórmula coincide con su definibilidad aritmética utilizando una${\displaystyle \Sigma _{n}^{0}}$fórmula. ^{[ 11 ]}

• Gerald Sacks , Teoría de la recursión superior , Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
• Robert Soare , Conjuntos y grados recursivamente enumerables , Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465
• Keith J. Devlin , Introducción a la estructura fina de la jerarquía constructible (p. 38), North-Holland Publishing, 1974
• J. Barwise , Conjuntos y estructuras admisibles . 1975