Teoría de la recursión alfa

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

Definiciones

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

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

También existen algunas definiciones similares para funciones que se asignan a : ^[3] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

• Una función parcial de a es -recursivamente-enumerable , o -parcialmente recursiva , ^[4] si y solo si su gráfico es -definible en . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle (L_{\alpha },\in )}$
• Una función parcial de a es recursiva si y solo si su gráfico es definible en . Como en el caso de la teoría de la recursión clásica, cualquier función total recursivamente enumerable es recursiva. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \Delta _{1}}$ ${\displaystyle (L_{\alpha },\in )}$ ${\displaystyle \alpha }$ ${\displaystyle f:\alpha \rightarrow \alpha }$ ${\displaystyle \alpha }$
• Además, una función parcial de a es -aritmética si y solo si existe alguna función tal que el gráfico de la función sea -definible en . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle n\in \omega }$ ${\displaystyle \Sigma _{n}}$ ${\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 -definibles juegan un papel similar al de las funciones recursivas primitivas . ^[3] ${\displaystyle \Delta _{0}}$ ${\displaystyle (L_{\alpha },\in )}$

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

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

${\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 . Según esta definición, A es recursivo en (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 \scriptstyle A\leq _{\alpha }B}$ ${\displaystyle \scriptstyle \varnothing }$ ${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$

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

Trabajar en recursión α

Teorema de desdoblamiento de Shore: Sea A recursivamente enumerable y regular. Existen recursivamente enumerables tales que ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle B_{0},B_{1}}$ ${\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 , C conjuntos α-regulares recursivamente enumerables tales que entonces existe un conjunto α-recursivamente enumerable regular B tal que . ${\displaystyle \scriptstyle A<_{\alpha }C}$ ${\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}$

Barwise ha demostrado que los conjuntos -definibles en son exactamente los conjuntos -definibles en , donde denota el siguiente ordinal admisible por encima de , y es de la jerarquía de Levy . ^[5] ${\displaystyle \Sigma _{1}}$ ${\displaystyle L_{\alpha ^{+}}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \alpha ^{+}}$ ${\displaystyle \alpha }$ ${\displaystyle \Sigma }$

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

Existe una interpretación computacional de la recursión, que utiliza " máquinas de Turing" con una cinta de dos símbolos de longitud , 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 , un conjunto es recursivo si y solo si es computable por una máquina de Turing, y es recursivamente enumerable si y solo si es el rango de una función computable por una máquina de Turing. ^[7] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle A\subseteq \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle A}$ ${\displaystyle \alpha }$

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 admisibles , los automorfismos de los grados de enumeración se incrustan en los automorfismos de los grados de enumeración. ^[8] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Relación con el análisis

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

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

Referencias

• 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 construible (p. 38), North-Holland Publishing, 1974
• J. Barwise, Conjuntos y estructuras admisibles . 1975

Referencias en línea

1. P. Koepke, B. Seyfferth, Ordinal machines and admissible recursion theory (preimpresión) (2009, p.315). Consultado el 12 de octubre de 2021
2. R. Gostanian, El siguiente ordinal admisible, Annals of Mathematical Logic 17 (1979). Consultado el 1 de enero de 2023.
3. Srebrny, Marian, Relatively construible transitive models (1975, p.165). Consultado el 21 de octubre de 2021.
4. W. Richter, P. Aczel, "Definiciones inductivas y propiedades reflectantes de ordinales admisibles" (1974), pág. 30. Consultado el 7 de febrero de 2023.
5. T. Arai, Teoría de la prueba para teorías de ordinales - I: ordinales recursivos de Mahlo (1998). p.2
6. SG Simpson, "Teoría de grados sobre ordinales admisibles", pp.170--171. Publicado en J. Fenstad, P. Hinman, Teoría de la recursión generalizada: Actas del Simposio de Oslo de 1972 (1974), ISBN 0 7204 22760.
7. P. Koepke, B. Seyfferth, "Máquinas ordinales y teoría de la recursión admisible". Anales de lógica pura y aplicada, vol. 160 (2009), págs. 310-318.
8. D. Natingga, Teorema de incrustación para el grupo de automorfismos de los grados de enumeración α (p.155), tesis doctoral, 2019.
9. PD Welch, La jerarquía analítica ramificada utilizando lógicas extendidas (2018, p. 4). Consultado el 8 de agosto de 2021.
10. GE Sacks, Teoría de la recursión superior (p. 152). "Perspectivas en lógica", Asociación para la lógica simbólica.
11. P. Odifreddi, Teoría de la recursión clásica (1989), teorema IV.3.22.