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 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}}}$${\estilo de visualización \omega}$${\estilo de visualización \alpha}$${\displaystyle L_{\alpha}\modelos {\mathsf {KP}}}$${\displaystyle \omega _{1}^{\mathsf {CK}}}$${\estilo de visualización \omega}$${\displaystyle \Delta _ {1}^{1}}$${\estilo de visualización \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}}$${\estilo de visualización x}$${\estilo de visualización x}$${\displaystyle \omega _ {1}^{x}}$${\estilo de visualización x}$${\estilo de visualización \alpha}$${\estilo de visualización 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 )}$$Estilo de visualización: Pi _{1}^{1}}$

El ordinal admisible n se denota a veces por . ^{[4] [5]}${\estilo de visualización \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]${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\displaystyle L_{\alpha}\modelos {\mathsf {KPi}}}$${\displaystyle L_{\alpha }\vDash {\textrm {V=HC}}}$${\estilo de visualización \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 n.º recursivamente inaccesible. Al igual que en el caso del "cardinal hiperinaccesible", diferentes autores discrepan sobre esta terminología. ${\estilo de visualización \alpha}$${\estilo de visualización \alpha}$${\estilo de visualización \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]${\estilo de visualización \alpha}$${\estilo de visualización \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 }$

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 computablemente . ^{[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 denomina 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)}$

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.