Ordinal no recursivo

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

El ordinal Church-Kleene y sus variantes

El ordinal no recursivo más pequeño es el ordinal Church Kleene, que lleva el nombre de 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 de Church-Kleene es un ordinal límite . También es el ordinal más pequeño que no es hiperaritmético y el ordinal más pequeño admisible 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 hace referencia al 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 suelen denotar el ordinal Church-Kleene. ^[2] ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}}$

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

${\displaystyle \omega _{\omega }^{\mathsf {CK}}}$, definido por primera vez por Stephen G. Simpson ^{[ cita necesaria ]} es una extensión del ordinal 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 que es un modelo de comprensión . ^[1] ${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$ ${\displaystyle \Pi _{1}^{1}}$

Ordinales recursivamente

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

Los ordinales recursivamente " 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 tiene un límite de admisibles. Alternativamente, es recursivamente inaccesible si y solo si es el ésimo ordinal admisible, ^[5] o si y solo , 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 llama recursivamente hiperinaccesible si es recursivamente inaccesible y tiene un límite de recursivamente inaccesibles, o si el th es recursivamente inaccesible. Al igual que "cardenal hiperinaccesible", diferentes autores entran en conflicto con esta terminología. ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Un ordinal se llama recursivamente Mahlo si es admisible y para cualquier función recursiva existe 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 todos . ^[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 llama recursivamente débilmente compacto si es -reflectante, o equivalentemente, ^[2] 2-admisible. Estos ordinales tienen fuertes propiedades recursivas de Mahloness, si α es -reflectante entonces es recursivamente -Mahlo. ^[6] ${\displaystyle \alpha }$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Debilitamientos de ordinales estables

Un ordinal es estable si es una subestructura elemental de , denotada por . ^[9] Estos son algunos de los ordinales no recursivos con nombre más grandes que aparecen en un contexto de teoría de modelos, por ejemplo mayores que para cualquier teoría computable axiomatizable . ^{[10] Proposición 0.7} . Hay 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 -stable iff . ${\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 reflectante para todos los finitos . ^[2] ${\displaystyle (+1)}$ ${\displaystyle (+1)}$ ${\displaystyle \Pi _{n}}$ ${\displaystyle n}$
  • En general, un ordinal contable se llama -stable sif . ${\displaystyle \alpha }$ ${\displaystyle (+\beta )}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +\beta }}$
• Un ordinal contable se llama -stable iff , donde es el ordinal más pequeño admisible . El ordinal estable más pequeño es nuevamente mucho más grande 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 -stable iff , donde están los dos ordinales más pequeños admisibles . El ordinal estable más pequeño es mayor que el reflectante 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 llama inaccesiblemente estable iff , donde es el ordinal recursivamente inaccesible más pequeño . El ordinal más pequeño inaccesiblemente estable es más grande que el más pequeño -estable. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle >\alpha }$ ${\displaystyle (^{++})}$
• Un ordinal contable se llama Mahlo-estable sif , donde es el ordinal de Mahlo recursivamente más pequeño . El ordinal estable de Mahlo más pequeño es más grande que el inaccesible más pequeño. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle >\alpha }$
• Un ordinal contable se llama doblemente estable sif . El ordinal doblemente estable más pequeño es más grande que el 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

• El menos 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 es ilimitado 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 modelo más pequeño de comprensión de segundo orden , o , sin 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 menos ordinal tal que . Este ordinal ha sido caracterizado por Toshiyasu Arai. ^[11] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {KP}}+'\omega _{1}{\textrm {exists}}'}$
• El menos ordinal tal que . ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\models {\mathsf {ZFC^{-}}}+'\omega _{1}{\textrm {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 reflectantes de los ordinales admisibles (1973, p.15). Consultado el 28 de octubre de 2021.
3. Sacks, Gerald E. (1976), "Ordinales e hipergrados contables admisibles", Avances en Matemáticas , 19 (2): 213–262, doi :10.1016/0001-8708(76)90187-0
4. PG Hinman, Jerarquías teóricas de recursión (1978), páginas 419-420. Perspectivas de la lógica matemática, ISBN 3-540-07904-1.
5. J. Barwise, Conjuntos y estructuras admisibles (1976), págs.174-176. Perspectivas de la lógica, Cambridge University Press, ISBN 3-540-07451-1.
6. Rathjen, Michael (1994), "Teoría de la prueba de la reflexión" (PDF) , Annals of Pure and Applied Logic , 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, Perspectives in Logic.
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 adelanto de la teoría de la prueba de los ordinales (1997, p.17). Consultado el 28 de octubre de 2021.

• Iglesia, Alonso ; Kleene, SC (1937), "Definiciones formales en la teoría de 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", Toro. América. Matemáticas. 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 , vol. 3, N° 4, 3 (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 del MIT, ISBN 978-0-262-68052-3
• Simpson, Stephen G. (2009) [1999], Subsistemas de aritmética de segundo orden , Perspectives in Logic, 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 reflectantes de los ordinales admisibles , págs. 312–313, 333, ISBN 0-7204-2276-0