Ordinal no recursivo

En matemáticas, particularmente en teoría de conjuntos, los ordinales no recursivos son ordinales contables grandes mayores que todos los ordinales recursivos y, por lo tanto, no se pueden expresar utilizando notaciones ordinales recursivas .

El ordinal Church-Kleene y variantes

El ordinal no recursivo más pequeño es el ordinal Church-Kleene, , llamado así por Alonzo Church y SC Kleene ; su tipo de orden es el conjunto de todos los ordinales recursivos . Dado que el sucesor de un ordinal recursivo es recursivo, el ordinal Church–Kleene es un ordinal límite . También es el ordinal más pequeño que no es hiperaritmético , y el ordinal admisible más pequeño después (un ordinal se llama admisible si ). Los subconjuntos -recursivos de son exactamente los subconjuntos de . ^[1] ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KP}}}$ ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega }$ ${\displaystyle \Delta _{1}^{1}}$ ${\displaystyle \omega }$

La notación se refiere a , el primer ordinal incontable , que es el conjunto de todos los ordinales contables, de manera análoga a cómo el ordinal de Church-Kleene es el conjunto de todos los ordinales recursivos. Algunas fuentes antiguas utilizan para denotar el ordinal de Church-Kleene. ^[2] ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}}$

Para un conjunto , un conjunto es -computable si es computable desde una máquina de Turing con un estado de oráculo que consulta . El ordinal de Church-Kleene relativizado es el supremo de los tipos de orden de las relaciones -computables. El teorema de Friedman-Jensen-Sacks establece que para cada ordinal contable admisible , existe un conjunto tal que . ^[3] ${\displaystyle x\subseteq \mathbb {N} }$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \omega _{1}^{x}}$ ${\displaystyle x}$ ${\displaystyle \alpha }$ ${\displaystyle x}$ ${\displaystyle \alpha =\omega _{1}^{x}}$

${\displaystyle \omega _{\omega }^{\mathsf {CK}}}$, definido por primera vez por Stephen G. Simpson ^{[ cita requerida ]} es una extensión del ordinal de Church-Kleene. Este es el límite más pequeño de ordinales admisibles, pero este ordinal no es admisible. Alternativamente, este es el α más pequeño tal que es un modelo de -comprensión . ^[1] ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle \Pi _{1}^{1}}$

Ordinales recursivos

El ordinal admisible n se denota a veces por . ^{[4] [5]} ${\displaystyle \alpha }$ ${\displaystyle \tau _{\alpha }}$

Los ordinales recursivos " x" , donde "x" normalmente representa una propiedad cardinal grande , son tipos de ordinales no recursivos. ^[6] Rathjen ha llamado a estos ordinales las "contrapartes recursivamente grandes" de x , ^[7] sin embargo, el uso de "recursivamente grande" aquí no debe confundirse con la noción de que un ordinal es recursivo.

Un ordinal se llama recursivamente inaccesible si es admisible y un límite de admisibles. Alternativamente, es recursivamente inaccesible si y solo si es el ordinal admisible n° , ^[5] o si y solo si , una extensión de la teoría de conjuntos de Kripke-Platek que establece que cada conjunto está contenido en un modelo de la teoría de conjuntos de Kripke-Platek. Bajo la condición de que ("cada conjunto es hereditariamente contable "), es recursivamente inaccesible si y solo si es un modelo de -comprensión . ^[8] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KPi}}}$ ${\displaystyle L_{\alpha }\vDash {\textrm {V=HC}}}$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle \Delta _{2}^{1}}$

Un ordinal se denomina recursivamente hiperinaccesible si es recursivamente inaccesible y un límite de recursivamente inaccesibles, o donde es el recursivamente inaccesible. Al igual que en el caso del "cardinal hiperinaccesible", diferentes autores discrepan sobre esta terminología. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Un ordinal se llama recursivamente Mahlo si es admisible y para cualquier función -recursiva hay un admisible tal que (es decir, está cerrado bajo ). ^[2] Reflejando la jerarquía de Mahloness , es recursivamente -Mahlo para un ordinal si es admisible y para cualquier función -recursiva hay un ordinal admisible tal que está cerrado bajo , y es recursivamente -Mahlo para todo . ^[6] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle f:\alpha \rightarrow \alpha }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \left\{f(\gamma )\mid \gamma \in \beta \right\}\subseteq \beta }$ ${\displaystyle \beta }$ ${\displaystyle f}$ ${\displaystyle \alpha }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle f:\alpha \rightarrow \alpha }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \beta }$ ${\displaystyle f}$ ${\displaystyle \beta }$ ${\displaystyle \delta }$ ${\displaystyle \delta <\gamma }$

Un ordinal se denomina recursivamente débilmente compacto si es -reflectivo o, equivalentemente, ^[2] 2-admisible. Estos ordinales tienen fuertes propiedades recursivas de Mahlón: si α es -reflectivo, entonces es recursivamente -Mahlón. ^[6] ${\displaystyle \alpha }$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Debilitamiento de los ordinales estables

Un ordinal es estable si es una - subestructura elemental de , denotada . ^[9] Estos son algunos de los ordinales no recursivos nombrados más grandes que aparecen en un contexto de teoría de modelos, por ejemplo, mayor que para cualquier teoría axiomatizable computacionalmente . ^{[10] Proposición 0.7} . Existen varios debilitamientos de los ordinales estables: ^[1] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle L}$ ${\displaystyle L_{\alpha }\preceq _{1}L}$ ${\displaystyle \min\{\alpha :L_{\alpha }\models T\}}$ ${\displaystyle T}$

• Un ordinal contable se llama -estable si y solo si . ${\displaystyle \alpha }$ ${\displaystyle (+1)}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +1}}$
  • El ordinal -estable más pequeño es mucho más grande que el ordinal recursivamente débilmente compacto más pequeño: se ha demostrado que el ordinal -estable más pequeño es -reflectivo para todo finito . ^[2] ${\displaystyle (+1)}$ ${\displaystyle (+1)}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle n}$
  • En general, un ordinal contable se llama -estable si y solo si . ${\displaystyle \alpha }$ ${\displaystyle (+\beta )}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +\beta }}$
• Un ordinal contable se llama -estable si y solo si , donde es el ordinal admisible más pequeño . El ordinal -estable más pequeño es a su vez mucho mayor que el -estable más pequeño o el -estable más pequeño para cualquier constante . ${\displaystyle \alpha }$ ${\displaystyle (^{+})}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{+}}}$ ${\displaystyle \beta ^{+}}$ ${\displaystyle >\beta }$ ${\displaystyle (^{+})}$ ${\displaystyle (+1)}$ ${\displaystyle (+\beta )}$ ${\displaystyle \beta }$
• Un ordinal contable se llama -estable si y solo si , donde son los dos ordinales admisibles más pequeños . El ordinal -estable más pequeño es mayor que el -reflectivo más pequeño. ${\displaystyle \alpha }$ ${\displaystyle (^{++})}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{++}}}$ ${\displaystyle \beta ^{++}}$ ${\displaystyle >\beta }$ ${\displaystyle (^{++})}$ ${\displaystyle \Sigma _{1}^{1}}$
• Un ordinal contable se denomina inaccesiblemente estable si y solo si , donde es el ordinal recursivamente inaccesible más pequeño . El ordinal inaccesiblemente estable más pequeño es mayor que el -estable más pequeño. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle >\alpha }$ ${\displaystyle (^{++})}$
• Un ordinal contable se denomina Mahlo-estable si y solo si , donde es el ordinal de Mahlo recursivamente más pequeño . El ordinal de Mahlo-estable más pequeño es mayor que el ordinal inaccesiblemente estable más pequeño. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle >\alpha }$
• Un ordinal contable se llama doblemente estable si y solo si . El ordinal doblemente estable más pequeño es mayor que el ordinal Mahlo-estable más pequeño. ${\displaystyle \alpha }$ ${\displaystyle (+1)}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }\preceq _{1}L_{\beta +1}}$ ${\displaystyle (+1)}$

Ordinales no recursivos más grandes

Los ordinales no recursivos aún más grandes incluyen: ^[1]

• El menor ordinal tal que donde es el ordinal no proyectable más pequeño. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$
• Un ordinal no es proyectable si es un límite de ordinales -estables, o; si el conjunto no está acotado en . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle X=\left\{\beta <\alpha \mid L_{\beta }\preceq _{1}L_{\alpha }\right\}}$ ${\displaystyle \alpha }$
• El ordinal del análisis ramificado, a menudo escrito como . Este es el más pequeño tal que es un modelo de comprensión de segundo orden , o , que no tiene el axioma del conjunto de potencias . ${\displaystyle \beta _{0}}$ ${\displaystyle \beta }$ ${\displaystyle L_{\beta }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle L_{\beta }\models {\mathsf {ZFC^{-}}}}$ ${\displaystyle {\mathsf {ZFC}}}$
• El menor ordinal tal que . Este ordinal ha sido caracterizado por Toshiyasu Arai. ^[11] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KP}}+{\text{'}}\omega _{1}{\text{ exists'}}}$
• El menor ordinal tal que . ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {ZFC^{-}}}+{\text{'}}\omega _{1}{\text{ exists'}}}$
• El ordinal menos estable.

Referencias

1. D. Madore, Un zoológico de ordinales (2017). Consultado en septiembre de 2021.
2. W. Richter, P. Aczel, Definiciones inductivas y propiedades reflectoras de ordinales admisibles (1973, p.15). Consultado el 28 de octubre de 2021.
3. Sacks, Gerald E. (1976), "Ordinales admisibles contables e hipergrados", Advances in Mathematics , 19 (2): 213–262, doi :10.1016/0001-8708(76)90187-0
4. PG Hinman, Recursion-Theoretic Hierarchies (1978), págs. 419-420. Perspectivas en lógica matemática, ISBN 3-540-07904-1.
5. J. Barwise, Conjuntos y estructuras admisibles (1976), pp.174--176. Perspectivas en lógica, Cambridge University Press, ISBN 3-540-07451-1.
6. Rathjen, Michael (1994), "Teoría de la prueba de la reflexión" (PDF) , Anales de lógica pura y aplicada , 68 (2): 181–224, doi : 10.1016/0168-0072(94)90074-4
7. M. Rathjen, "El ámbito del análisis ordinal" (2006). Archivado el 7 de diciembre de 2023.
8. W. Marek, Algunos comentarios sobre el artículo de Artigue, Isambert, Perrin y Zalc (1976), ICM. Consultado el 19 de mayo de 2023.
9. J. Barwise, Conjuntos y estructuras admisibles (1976), Cambridge University Press, Perspectivas en lógica.
10. W. Marek, K. Rasmussen, Espectro de L en bibliotecas ( catálogo de WorldCat ) (página EuDML), Państwowe Wydawn. Consultado el 1 de diciembre de 2022.
11. T. Arai, Un avance de la teoría de la prueba de los ordinales (1997, p. 17). Consultado el 28 de octubre de 2021.

• Church, Alonzo ; Kleene, SC (1937), "Definiciones formales en la teoría de los números ordinales.", Fundamenta Mathematicae , 28 : 11–21, doi : 10.4064/fm-28-1-11-21 , JFM  63.0029.02
• Church, Alonzo (1938), "La segunda clase numérica constructiva", Bull. Amer. Math. Soc. , 44 (4): 224–232, doi : 10.1090/S0002-9904-1938-06720-1
• Kleene, SC (1938), "Sobre la notación de números ordinales", Journal of Symbolic Logic , 3 (4), vol. 3, n.º 4: 150–155, doi :10.2307/2267778, JSTOR  2267778, S2CID  34314018
• Rogers, Hartley (1987) [1967], La teoría de las funciones recursivas y la computabilidad efectiva , primera edición de bolsillo de MIT Press, ISBN 978-0-262-68052-3
• Simpson, Stephen G. (2009) [1999], Subsistemas de aritmética de segundo orden , Perspectivas en lógica, vol. 2, Cambridge University Press, págs. 246, 267, 292–293, ISBN 978-0-521-88439-6
• Richter, Wayne; Aczel, Peter (1974), Definiciones inductivas y propiedades reflectoras de ordinales admisibles , págs. 312–313, 333, ISBN 0-7204-2276-0