Ordinal contable grande

Los ordinales en matemáticas y teoría de conjuntos

En la disciplina matemática de la teoría de conjuntos , existen muchas formas de describir ordinales contables específicos . Los más pequeños se pueden expresar de manera útil y no circular en términos de sus formas normales de Cantor . Más allá de eso, muchos ordinales relevantes para la teoría de la prueba aún tienen notaciones ordinales computables (ver análisis ordinal ). Sin embargo, no es posible decidir efectivamente si una notación ordinal putativa dada es una notación o no (por razones algo análogas a la insolubilidad del problema de la detención ); hay varias formas más concretas de definir ordinales que definitivamente tienen notaciones.

Dado que solo hay un número contable de notaciones, todos los ordinales con notaciones se agotan muy por debajo del primer ordinal incontable ω ₁ ; su supremo se llama Church–Kleene ω ₁ o ω^CK1
_​(no debe confundirse con el primer ordinal incontable, ω ₁ ), descrito a continuación. Números ordinales inferiores a ω^CK1
_​son los ordinales recursivos (ver abajo). Los ordinales contables mayores que este pueden definirse, pero no tienen notación.

Debido al enfoque en los ordinales contables, se utiliza aritmética ordinal en todo el texto, excepto cuando se indique lo contrario. Los ordinales descritos aquí no son tan grandes como los descritos en cardinales grandes , pero son grandes entre aquellos que tienen notaciones constructivas (descripciones). Se pueden definir ordinales cada vez más grandes, pero se vuelven cada vez más difíciles de describir.

Generalidades sobre los ordinales recursivos

Notaciones ordinales

Los ordinales computables (u ordinales recursivos) son ciertos ordinales contables: en términos generales, aquellos representados por una función computable . Hay varias definiciones equivalentes de esto: la más simple es decir que un ordinal computable es el tipo de orden de algún ordenamiento recursivo (es decir, computable) de los números naturales; por lo tanto, esencialmente, un ordinal es recursivo cuando podemos presentar el conjunto de ordinales más pequeños de tal manera que una computadora ( una máquina de Turing , por ejemplo) pueda manipularlos (y, esencialmente, compararlos).

Una definición diferente utiliza el sistema de notaciones ordinales de Kleene . Brevemente, una notación ordinal es el nombre cero (que describe el ordinal 0), o el sucesor de una notación ordinal (que describe al sucesor del ordinal descrito por esa notación), o una máquina de Turing (función computable) que produce una secuencia creciente de notaciones ordinales (que describen el ordinal que es el límite de la secuencia), y las notaciones ordinales están (parcialmente) ordenadas de modo que el sucesor de o sea mayor que o y el límite sea mayor que cualquier término de la secuencia (este orden es computable; sin embargo, el conjunto O de notaciones ordinales en sí mismo es altamente no recursivo, debido a la imposibilidad de decidir si una máquina de Turing dada produce de hecho una secuencia de notaciones); un ordinal recursivo es entonces un ordinal descrito por alguna notación ordinal.

Cualquier ordinal menor que un ordinal recursivo es en sí mismo recursivo, por lo que el conjunto de todos los ordinales recursivos forma un cierto ordinal (contable), el ordinal de Church-Kleene (ver más abajo).

Resulta tentador olvidarse de las notaciones ordinales y hablar únicamente de los ordinales recursivos en sí mismos; y se hacen algunas afirmaciones sobre los ordinales recursivos que, de hecho, se refieren a las notaciones para estos ordinales. Sin embargo, esto conduce a dificultades, ya que incluso el ordinal infinito más pequeño, ω, tiene muchas notaciones, algunas de las cuales no se puede demostrar que sean equivalentes a la notación obvia (el programa más simple que enumera todos los números naturales).

Relación con los sistemas aritméticos

Existe una relación entre los ordinales computables y ciertos sistemas formales (que contienen la aritmética , es decir, al menos un fragmento razonable de la aritmética de Peano ).

Ciertos ordinales computables son tan grandes que, si bien pueden expresarse mediante una determinada notación ordinal o , un sistema formal dado podría no ser lo suficientemente potente para demostrar que o es, de hecho, una notación ordinal: el sistema no muestra inducción transfinita para ordinales tan grandes.

Por ejemplo, los axiomas de Peano de primer orden usuales no prueban la inducción transfinita para (o más allá de) ε : mientras que el ordinal ε ₀ puede describirse aritméticamente fácilmente (es contable), los axiomas de Peano no son lo suficientemente fuertes como para mostrar que es de hecho un ordinal; de hecho, la inducción transfinita en ε ₀ prueba la consistencia de los axiomas de Peano (un teorema de Gentzen ), así que por el segundo teorema de incompletitud de Gödel , los axiomas de Peano no pueden formalizar ese razonamiento. (Esto está en la base del teorema de Kirby-Paris sobre sucesiones de Goodstein .) Puesto que la aritmética de Peano puede probar que cualquier ordinal menor que ε ₀ está bien ordenado, decimos que ε ₀ mide la fuerza teórica de la prueba de los axiomas de Peano.

Pero podemos hacer esto para sistemas que van mucho más allá de los axiomas de Peano. Por ejemplo, la fuerza de la teoría de conjuntos de Kripke-Platek en términos de prueba es el ordinal de Bachmann-Howard y, de hecho, simplemente agregar a los axiomas de Peano los axiomas que establecen el buen orden de todos los ordinales por debajo del ordinal de Bachmann-Howard es suficiente para obtener todas las consecuencias aritméticas de la teoría de conjuntos de Kripke-Platek.

Ordinales recursivos específicos

Definiciones predicativas y la jerarquía de Veblen

Ya hemos mencionado (ver forma normal de Cantor ) el ordinal ε 0 , que es el más pequeño que satisface la ecuación , por lo que es el límite de la secuencia 0, 1, , , , ... El siguiente ordinal que satisface esta ecuación se llama ε ₁ : es el límite de la secuencia ${\displaystyle \omega ^{\alpha }=\alpha }$ ${\displaystyle \omega }$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \omega ^{\omega ^{\omega }}}$

${\displaystyle \varepsilon _{0}+1,\qquad \omega ^{\varepsilon _{0}+1}=\varepsilon _{0}\cdot \omega ,\qquad \omega ^{\omega ^{\varepsilon _{0}+1}}=(\varepsilon _{0})^{\omega },\qquad {\text{etc.}}}$

De manera más general, el -ésimo ordinal tal que se llama . Podríamos definir como el ordinal más pequeño tal que , pero como el alfabeto griego no tiene un número transfinito de letras, es mejor usar una notación más robusta: definamos los ordinales por inducción transfinita de la siguiente manera: sea y sea el -ésimo punto fijo de (es decir, el -ésimo ordinal tal que ; así, por ejemplo, ), y cuando es un ordinal límite, definamos como el -ésimo punto fijo común del para todo . Esta familia de funciones se conoce como la jerarquía de Veblen (hay variaciones no esenciales en la definición, como dejar que, para un ordinal límite, sea el límite del para : esto esencialmente solo desplaza los índices en 1, lo cual es inofensivo). se llama función de Veblen (a la base ). ${\displaystyle \iota }$ ${\displaystyle \omega ^{\alpha }=\alpha }$ ${\displaystyle \varepsilon _{\iota }}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \varepsilon _{\alpha }=\alpha }$ ${\displaystyle \varphi _{\gamma }(\beta )}$ ${\displaystyle \varphi _{0}(\beta )=\omega ^{\beta }}$ ${\displaystyle \varphi _{\gamma +1}(\beta )}$ ${\displaystyle \beta }$ ${\displaystyle \varphi _{\gamma }}$ ${\displaystyle \beta }$ ${\displaystyle \varphi _{\gamma }(\alpha )=\alpha }$ ${\displaystyle \varphi _{1}(\beta )=\varepsilon _{\beta }}$ ${\displaystyle \delta }$ ${\displaystyle \varphi _{\delta }(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \varphi _{\gamma }}$ ${\displaystyle \gamma <\delta }$ ${\displaystyle \delta }$ ${\displaystyle \varphi _{\delta }(\alpha )}$ ${\displaystyle \varphi _{\gamma }(\alpha )}$ ${\displaystyle \gamma <\delta }$ ${\displaystyle \varphi _{\gamma }}$ ${\displaystyle \gamma ^{th}}$ ${\displaystyle \omega }$

Ordenación: si y solo si ( y ) o ( y ) o ( y ). ${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$ ${\displaystyle \alpha =\gamma }$ ${\displaystyle \beta <\delta }$ ${\displaystyle \alpha <\gamma }$ ${\displaystyle \beta <\varphi _{\gamma }(\delta )}$ ${\displaystyle \alpha >\gamma }$ ${\displaystyle \varphi _{\alpha }(\beta )<\delta }$

El ordinal Feferman-Schütte y más allá

El ordinal más pequeño, conocido como ordinal de Feferman–Schütte, se escribe generalmente como . Puede describirse como el conjunto de todos los ordinales que pueden escribirse como expresiones finitas, comenzando desde cero, utilizando únicamente la jerarquía de Veblen y la adición. El ordinal de Feferman–Schütte es importante porque, en un sentido que es complicado de precisar, es el ordinal más pequeño (infinito) que no puede describirse (" predicativamente ") utilizando ordinales más pequeños. Mide la fuerza de tales sistemas como " recursión transfinita aritmética ". ${\displaystyle \varphi _{\alpha }(0)=\alpha }$ ${\displaystyle \Gamma _{0}}$

De manera más general, Γ _α enumera los ordinales que no pueden obtenerse a partir de ordinales más pequeños utilizando la suma y las funciones de Veblen.

Por supuesto, es posible describir ordinales más allá del ordinal de Feferman-Schütte. Se podría continuar buscando puntos fijos de una manera cada vez más complicada: enumerar los puntos fijos de , luego enumerar los puntos fijos de ese , y así sucesivamente, y luego buscar el primer ordinal α tal que α se obtenga en α pasos de este proceso, y continuar diagonalizando de esta manera ad hoc . Esto conduce a la definición de los ordinales de Veblen " pequeños " y " grandes ". ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$

Ordinales impredicativos

Para ir más allá del ordinal de Feferman-Schütte, es necesario introducir nuevos métodos. Desafortunadamente, todavía no hay una forma estándar de hacerlo: cada autor en el tema parece haber inventado su propio sistema de notación, y es bastante difícil traducir entre los diferentes sistemas. El primer sistema de este tipo fue introducido por Bachmann en 1950 (de manera ad hoc ), y diferentes extensiones y variaciones del mismo fueron descritas por Buchholz, Takeuti (diagramas ordinales), Feferman (sistemas θ), Aczel , Bridge, Schütte y Pohlers. Sin embargo, la mayoría de los sistemas utilizan la misma idea básica, la de construir nuevos ordinales contables utilizando la existencia de ciertos ordinales incontables. Aquí hay un ejemplo de dicha definición, descrita con mucho más detalle en el artículo sobre la función de colapso ordinal :

• ψ( α ) se define como el ordinal más pequeño que no se puede construir comenzando con 0, 1, ω y Ω, y aplicando repetidamente la suma, la multiplicación y la exponenciación, y ψ a ordinales construidos previamente (excepto que ψ solo se puede aplicar a argumentos menores que α , para garantizar que esté bien definido).

Aquí Ω = ω ₁ es el primer ordinal incontable. Se incluye porque, de lo contrario, la función ψ se queda "atascada" en el ordinal σ más pequeño, de modo que ε _σ = σ : en particular, ψ( α )= σ para cualquier ordinal α que satisfaga σ ≤ α ≤Ω. Sin embargo, el hecho de que hayamos incluido Ω nos permite superar este punto: ψ(Ω+1) es mayor que σ . La propiedad clave de Ω que utilizamos es que es mayor que cualquier ordinal producido por ψ.

Para construir ordinales aún más grandes, podemos ampliar la definición de ψ añadiendo más formas de construir ordinales incontables. Hay varias formas de hacerlo, que se describen en cierta medida en el artículo sobre la función de colapso ordinal .

El ordinal de Bachmann-Howard (a veces llamado simplemente ordinal de Howard , ψ ₀ (ε _Ω+1 ) con la notación anterior) es importante, porque describe la fortaleza de la teoría de la demostración de la teoría de conjuntos de Kripke-Platek . De hecho, la principal importancia de estos grandes ordinales, y la razón para describirlos, es su relación con ciertos sistemas formales como se explicó anteriormente. Sin embargo, sistemas formales tan poderosos como la aritmética completa de segundo orden , y mucho menos la teoría de conjuntos de Zermelo-Fraenkel , parecen fuera de nuestro alcance por el momento.

Más allá incluso del ordinal de Bachmann-Howard

Más allá de esto, existen múltiples ordinales recursivos que no son tan conocidos como los anteriores. El primero de ellos es el ordinal de Buchholz , definido como , abreviado simplemente como , utilizando la notación anterior. Es el ordinal de demostración teórica de , ^[1] una teoría de primer orden de la aritmética que permite la cuantificación sobre los números naturales así como sobre conjuntos de números naturales, y , la "teoría formal de definiciones inductivas finitamente iteradas". ^[2] ${\displaystyle \psi _{0}(\Omega _{\omega })}$ ${\displaystyle \psi (\Omega _{\omega })}$ ${\displaystyle \Pi _{1}^{1}-CA_{0}}$ ${\displaystyle ID_{<\omega }}$

Dado que las hidras del juego de hidras de Buchholz son isomorfas a la notación ordinal de Buchholz, los ordinales hasta este punto se pueden expresar utilizando hidras del juego. ^{[3] p.136} Por ejemplo corresponde a . ${\displaystyle +(0(\omega ))}$ ${\displaystyle \psi (\Omega _{\omega })}$

A continuación se encuentra el ordinal Takeuti-Feferman-Buchholz , el ordinal de prueba teórica de ; ^[4] y otro subsistema de aritmética de segundo orden: - comprensión + inducción transfinita, y , la "teoría formal de - veces definiciones inductivas iteradas". ^[5] En esta notación, se define como . Es el supremo del rango de funciones psi de Buchholz. ^[6] Fue nombrado por primera vez por David Madore. ^{[ cita requerida ]} ${\displaystyle \Pi _{1}^{1}-CA+BI}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle ID_{\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$

El siguiente ordinal se menciona en un fragmento de código que describe ordinales y números contables grandes en Agda, y "AndrasKovacs" lo define como . ${\displaystyle \psi _{0}(\Omega _{\omega +1}\cdot \varepsilon _{0})}$

El siguiente ordinal se menciona en el mismo fragmento de código que el anterior y se define como . Es el ordinal de prueba teórica de . ${\displaystyle \psi _{0}(\Omega _{\omega ^{\omega }})}$ ${\displaystyle ID_{<\omega ^{\omega }}}$

El siguiente ordinal se menciona nuevamente en este mismo fragmento de código, definido como , es el ordinal de prueba teórica de . En general, el ordinal de prueba teórica de es igual a —nótese que en este caso particular, representa , el primer ordinal distinto de cero. ${\displaystyle \psi _{0}(\Omega _{\varepsilon _{0}})}$ ${\displaystyle ID_{<\varepsilon _{0}}}$ ${\displaystyle ID_{<\nu }}$ ${\displaystyle \psi _{0}(\Omega _{\nu })}$ ${\displaystyle \Omega _{0}}$ ${\displaystyle 1}$

El siguiente es un ordinal sin nombre, al que David Madore se refiere como el colapso "contable" de , ^[5] donde es el primer cardinal inaccesible (= -indescriptible). Este es el ordinal de la teoría de conjuntos de Kripke-Platek, aumentado por la inaccesibilidad recursiva de la clase de ordinales (KPi), o, en el lado aritmético, de la -comprensión + inducción transfinita. Su valor es igual a usar una función desconocida. ${\displaystyle \varepsilon _{I+1}}$ ${\displaystyle I}$ ${\displaystyle \Pi _{0}^{1}}$ ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle \psi (\varepsilon _{I+1})}$

El siguiente es otro ordinal sin nombre, al que David Madore se refiere como el colapso "contable" de , ^[5] donde es el primer cardinal de Mahlo . Este es el ordinal de prueba teórica de KPM, una extensión de la teoría de conjuntos de Kripke-Platek basada en un cardinal de Mahlo. ^[7] Su valor es igual a usar una de las diversas funciones psi de Buchholz. ^[8] ${\displaystyle \varepsilon _{M+1}}$ ${\displaystyle M}$ ${\displaystyle \psi (\varepsilon _{M+1})}$

El siguiente es otro ordinal sin nombre, al que David Madore se refiere como el colapso "contable" de , ^[5] donde es el primer cardinal débilmente compacto (= -indescriptible). Este es el ordinal de prueba teórica de la teoría de conjuntos de Kripke-Platek + Π3 - Ref. Su valor es igual a usar la función Psi de Rathjen. ^[9] ${\displaystyle \varepsilon _{K+1}}$ ${\displaystyle K}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Psi (\varepsilon _{K+1})}$

El siguiente es otro ordinal sin nombre, al que David Madore se refiere como el colapso "contable" de , ^[5] donde es el primer cardinal indescriptible. Este es el ordinal de prueba teórica de la teoría de conjuntos de Kripke-Platek + Πω-Ref. Su valor es igual a utilizando la función Psi de Stegert, donde = ( ; ; , , 0). ^[10] ${\displaystyle \varepsilon _{\Xi +1}}$ ${\displaystyle \Xi }$ ${\displaystyle \Pi _{0}^{2}}$ ${\displaystyle \Psi _{X}^{\varepsilon _{\Xi +1}}}$ ${\displaystyle X}$ ${\displaystyle \omega ^{+}}$ ${\displaystyle P_{0}}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

El siguiente es el último ordinal sin nombre, al que David Madore denomina el ordinal de prueba teórica de Estabilidad. ^[5] Este es el ordinal de prueba teórica de Estabilidad, una extensión de la teoría de conjuntos de Kripke-Platek. Su valor es igual a usar la función Psi de Stegert, donde = ( ; ; , , 0). ^[10] ${\displaystyle \Psi _{X}^{\varepsilon _{\Upsilon +1}}}$ ${\displaystyle X}$ ${\displaystyle \omega ^{+}}$ ${\displaystyle P_{0}}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

A continuación hay un grupo de ordinales sobre los que no se sabe mucho, pero que aún son bastante significativos (en orden ascendente):

• El ordinal demostrativo-teórico de la aritmética de segundo orden .
• Un posible límite de la notación ordinal C de Taranovsky. (Conjetural, suponiendo que el sistema de notación esté bien fundamentado)
• El ordinal de prueba teórica de ZFC .

Ordinales recursivos "irrecursables"

Al eliminar el requisito de tener una descripción concreta, se pueden obtener ordinales contables recursivos aún más grandes como los ordinales que miden las fortalezas de varias teorías fuertes; en términos generales, estos ordinales son los tipos de orden más pequeños de notaciones ordinales "naturales" que las teorías no pueden probar que están bien ordenadas. Al tomar teorías cada vez más fuertes como la aritmética de segundo orden , la teoría de conjuntos de Zermelo , la teoría de conjuntos de Zermelo-Fraenkel o la teoría de conjuntos de Zermelo-Fraenkel con varios axiomas cardinales grandes , se obtienen algunos ordinales recursivos extremadamente grandes. (Estrictamente hablando, no se sabe que todos estos sean realmente ordinales: por construcción, la fortaleza ordinal de una teoría solo se puede probar como un ordinal de una teoría aún más fuerte. Entonces, para los axiomas cardinales grandes, esto se vuelve bastante confuso).

Más allá de los ordinales recursivos

El ordinal Church-Kleene

El supremo del conjunto de ordinales recursivos es el ordinal más pequeño que no se puede describir de forma recursiva. (No es el tipo de orden de ningún ordenamiento recursivo correcto de los números enteros). Ese ordinal es un ordinal contable llamado ordinal de Church-Kleene , . Por lo tanto, es el ordinal no recursivo más pequeño, y no hay esperanza de "describir" con precisión ningún ordinal a partir de este punto; solo podemos definirlos . Pero sigue siendo mucho menor que el primer ordinal incontable, . Sin embargo, como sugiere su símbolo, se comporta en muchos sentidos de forma bastante similar a . Por ejemplo, se pueden definir funciones ordinales colapsables utilizando en lugar de . ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ${\displaystyle \omega _{1}}$

Ordinarios admisibles

El ordinal de Church–Kleene se relaciona nuevamente con la teoría de conjuntos de Kripke–Platek , pero ahora de una manera diferente: mientras que el ordinal de Bachmann–Howard (descrito anteriormente) era el ordinal más pequeño para el cual KP no prueba la inducción transfinita, el ordinal de Church–Kleene es el α más pequeño tal que la construcción del universo de Gödel , L , hasta la etapa α , produce un modelo de KP. Tales ordinales se denominan admisibles , por lo tanto es el ordinal admisible más pequeño (más allá de ω en caso de que el axioma de infinito no esté incluido en KP). ${\displaystyle L_{\alpha }}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

Por un teorema de Friedman , Jensen y Sacks , los ordinales contables admisibles son exactamente aquellos construidos de manera similar al ordinal de Church-Kleene pero para máquinas de Turing con oráculos . ^{[11] [12]} A veces se escribe para el -ésimo ordinal que es admisible o un límite de admisibles más pequeños. ^{[ cita requerida ]} ${\displaystyle \omega _{\alpha }^{\mathrm {CK} }}$ ${\displaystyle \alpha }$

Más allá de los ordinales admisibles

${\displaystyle \omega _{\omega }^{\mathrm {CK} }}$es el límite más pequeño de ordinales admisibles (mencionado más adelante), aunque el ordinal en sí no es admisible. También es el más pequeño tal que es un modelo de -comprensión. ^{[5] [13]} ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\cap P(\omega )}$ ${\displaystyle \Pi _{1}^{1}}$

Un ordinal que es a la vez admisible y un límite de admisibles, o equivalentemente tal que es el -ésimo ordinal admisible, se llama recursivamente inaccesible , y el menos recursivamente inaccesible puede denotarse . ^[14] Un ordinal que es a la vez recursivamente inaccesible y un límite de recursivamente inaccesibles se llama recursivamente hiperinaccesible . ^[5] Existe una teoría de ordinales grandes de esta manera que es altamente paralela a la de los cardinales grandes (pequeños) . Por ejemplo, podemos definir recursivamente ordinales de Mahlo : estos son los tales que cada subconjunto no acotado cerrado -recursivo de contiene un ordinal admisible (un análogo recursivo de la definición de un cardinal de Mahlo ). La 1-sección del funcional de Harrington es igual a , donde es el ordinal de Mahlo menos recursivo. ^{[15] p.171} ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \omega _{1}^{E_{1}}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle {}^{2}S^{\#}}$ ${\displaystyle L_{\rho }\cap {\mathcal {P}}(\omega )}$ ${\displaystyle \rho }$

Pero tenga en cuenta que todavía estamos hablando de ordinales posiblemente contables aquí. (Si bien la existencia de cardinales inaccesibles o de Mahlo no se puede probar en la teoría de conjuntos de Zermelo-Fraenkel , la de ordinales recursivamente inaccesibles o recursivamente de Mahlo es un teorema de ZFC: de hecho, cualquier cardinal regular es recursivamente de Mahlo y más, pero incluso si nos limitamos a ordinales contables, ^{[ aclaración necesaria ]} ZFC prueba la existencia de ordinales recursivamente de Mahlo. Sin embargo, están más allá del alcance de la teoría de conjuntos de Kripke-Platek).

Reflexión

Para un conjunto de fórmulas , un ordinal límite se denomina -reflectivo si el rango satisface una cierta propiedad de reflexión para cada -fórmula . ^[16] Estos ordinales aparecen en el análisis ordinal de teorías como KP+Π ₃ -ref , una teoría que amplía la teoría de conjuntos de Kripke-Platek mediante un esquema de -reflexión. También pueden considerarse "análogos recursivos" de algunos cardinales incontables como los cardinales débilmente compactos y los cardinales indescriptibles . ^[17] Por ejemplo, un ordinal que es -reflectivo se denomina recursivamente débilmente compacto . ^[18] Para finito , el ordinal menos -reflectivo es también el supremo de los ordinales de clausura de definiciones inductivas monótonas cuyos gráficos son Π m+1 . ^[18] ${\displaystyle \Gamma }$ ${\displaystyle \alpha }$ ${\displaystyle \Gamma }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \Gamma }$ ${\displaystyle \phi }$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \Pi _{3}}$ ${\displaystyle n}$ ${\displaystyle \Pi _{n}}$

En particular, los ordinales -reflectivos también tienen una caracterización que utiliza funcionales de tipo superior en funciones ordinales, lo que les da el nombre de ordinales 2-admisibles . ^[18] Un artículo inédito de Solomon Feferman proporciona, para cada finito , una propiedad similar correspondiente a la -reflexión. ^[19] ${\displaystyle \Pi _{3}}$ ${\displaystyle n}$ ${\displaystyle \Pi _{n}}$

No proyectabilidad

Un ordinal admisible se llama no proyectable si no hay una función inyectiva -recursiva total que se asigne a un ordinal más pequeño. (Esto es trivialmente cierto para los cardinales regulares; sin embargo, estamos principalmente interesados ​​en ordinales contables). Ser no proyectable es una condición mucho más fuerte que ser admisible, recursivamente inaccesible o incluso recursivamente Mahlo. ^[13] Por el método de Jensen de projecta, ^[20] esta afirmación es equivalente a la afirmación de que el universo de Gödel , L , hasta la etapa α, produce un modelo de KP + -separación. Sin embargo, -separación por sí sola (no en presencia de ) no es un esquema axiomático lo suficientemente fuerte como para implicar no proyectabilidad, de hecho hay modelos transitivos de + -separación de cualquier altura admisible contable . ^[21] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle V=L}$ ${\displaystyle KP}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle >\omega }$

Los ordinales no proyectables están vinculados al trabajo de Jensen sobre proyectos. ^{[5] [22]} Los ordinales menos proyectables en relación con un conjunto dado están vinculados a la construcción de Harrington de la clase 2 de Spector más pequeña que refleja. ^{[15] p.174}

Ordinales "indemostrables"

Podemos imaginar ordinales aún mayores que sean contables. Por ejemplo, si ZFC tiene un modelo transitivo (una hipótesis más fuerte que la mera hipótesis de consistencia, e implícita en la existencia de un cardinal inaccesible), entonces existe un numerable tal que es un modelo de ZFC. Tales ordinales están más allá de la fuerza de ZFC en el sentido de que no puede (por construcción) probar su existencia. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$

Si es una teoría de conjuntos recursivamente enumerables consistente con V = L , entonces el menor tal que sea menor que el ordinal menos estable, que se deduce. ^[23] ${\displaystyle T}$ ${\displaystyle \alpha }$ ${\displaystyle (L_{\alpha },\in )\vDash T}$

Ordinales estables

Incluso los ordinales contables más grandes, llamados ordinales estables , pueden definirse por condiciones de indescriptibilidad o como aquellos tales que es un submodelo Σ 1 -elemental de L ; la existencia de estos ordinales puede probarse en ZFC, ^[24] y están estrechamente relacionados con los ordinales no proyectables desde una perspectiva de teoría de modelos. ^{[5] : 6} Para contables , la estabilidad de es equivalente a . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\omega _{1}}}$

El nivel menos estable de tiene algunas propiedades relacionadas con la definibilidad. Sea el mínimo tal que : ${\displaystyle L}$ ${\displaystyle \sigma }$ ${\displaystyle L_{\sigma }\prec _{1}L}$

• Un conjunto tiene una definición en si y solo si es un miembro de . ^{[5] p.6} ${\displaystyle \Sigma _{1}}$ ${\displaystyle L}$ ${\displaystyle L_{\sigma }}$
• Un conjunto es si y solo si es miembro de . ^{[5] p.6} ${\displaystyle x\subseteq \mathbb {N} }$ ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle L_{\sigma }}$
• Un conjunto es si y solo si es -recursivamente enumerable, en la terminología de la teoría de la recursión alfa . ^{[5] p.6} ${\displaystyle x\subseteq \mathbb {N} }$ ${\displaystyle \Sigma _{2}^{1}}$ ${\displaystyle \sigma }$

Variantes de ordinales estables

Se trata de variantes debilitadas de los ordinales estables. Hay ordinales con estas propiedades menores que el ordinal menos no proyectable mencionado anteriormente, ^[5] por ejemplo, un ordinal es -estable si y solo si es -reflectivo para todos los ordinales naturales . ^[18] ${\displaystyle (+1)}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle n}$

• Un ordinal contable se llama -estable si y solo si ^[5] ${\displaystyle \alpha }$ ${\displaystyle (+\beta )}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\alpha +\beta }}$
• Un ordinal contable se llama -estable si y solo si , donde es el ordinal menos admisible mayor que . ^{[5] [25]} ${\displaystyle \alpha }$ ${\displaystyle (^{+})}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Un ordinal contable se llama -estable si y solo si , donde es el ordinal menos admisible mayor que un ordinal admisible mayor que . ^[25] ${\displaystyle \alpha }$ ${\displaystyle (^{++})}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Un ordinal contable se denomina inaccesiblemente estable si y solo si , donde es el ordinal menos recursivamente inaccesible mayor que . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Un ordinal contable se llama Mahlo-estable si y solo si , donde es el ordinal Mahlo menos recursivo mayor que . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Un ordinal contable se llama doblemente estable si y solo si existe un ordinal -estable tal que . ^[5] ${\displaystyle \alpha }$ ${\displaystyle (+1)}$ ${\displaystyle (+1)}$ ${\displaystyle \beta >\alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$

Han aparecido debilitamientos más fuertes de la estabilidad en publicaciones de teoría de pruebas, incluido el análisis de subsistemas de aritmética de segundo orden . ^[26]

Un pseudo-bien-ordenado

Dentro del esquema de notaciones de Kleene, algunos representan ordinales y otros no. Se puede definir un ordenamiento total recursivo que sea un subconjunto de las notaciones de Kleene y que tenga un segmento inicial que esté bien ordenado con order-type . Todo subconjunto no vacío recursivamente enumerable (o incluso hiperaritmético) de este ordenamiento total tiene un elemento mínimo. Por lo tanto, se parece a un buen ordenamiento en algunos aspectos. Por ejemplo, se pueden definir las operaciones aritméticas sobre él. Sin embargo, no es posible determinar de manera efectiva y exacta dónde termina la parte inicial bien ordenada y dónde comienza la parte que carece de un elemento mínimo. ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

Como ejemplo de un pseudo-buen ordenamiento recursivo, sea S ATR ₀ u otra teoría recursivamente axiomatizable que tenga un ω-modelo pero ningún ω-modelo hiperaritmético, y (si es necesario) extienda conservadoramente S con funciones de Skolem . Sea T el árbol de ω-modelos parciales (esencialmente) finitos de S: Una secuencia de números naturales está en T si y solo si S más ∃m φ(m) ⇒ φ(x _⌈φ⌉ ) (para las primeras n fórmulas φ con una variable numérica libre; ⌈φ⌉ es el número de Gödel) no tiene una prueba de inconsistencia más corta que n. Entonces el orden de Kleene–Brouwer de T es un pseudobuen ordenamiento recursivo. ${\displaystyle x_{1},x_{2},...,x_{n}}$

Cualquier construcción de este tipo debe tener un tipo de orden , donde es el tipo de orden de , y es un ordinal recursivo. ^[27] ${\displaystyle \omega _{1}^{CK}\times (1+\eta )+\rho }$ ${\displaystyle \eta }$ ${\displaystyle (\mathbb {Q} ,<)}$ ${\displaystyle \rho }$

Referencias

La mayoría de los libros que describen ordinales contables grandes tratan sobre teoría de pruebas y, lamentablemente, tienden a estar agotados.

Sobre ordinales recursivos

• Wolfram Pohlers, Proof theory , Springer 1989 ISBN  0-387-51842-8 (para la jerarquía de Veblen y algunos ordinales impredicativos). Este es probablemente el libro más fácil de leer sobre ordinales contables grandes (lo cual no es decir mucho).
• Gaisi Takeuti , Teoría de la prueba , 2.ª edición, 1987, ISBN 0-444-10492-5 (para diagramas ordinales) 
• Kurt Schütte , Teoría de la prueba , Springer 1977 ISBN 0-387-07911-4 (para la jerarquía de Veblen y algunos ordinales impredicativos) 
• Craig Smorynski, The varieties of arboreal experience Math. Intelligencer 4 (1982), núm. 4, 182–189; contiene una descripción informal de la jerarquía de Veblen.
• Hartley Rogers Jr. , Teoría de funciones recursivas y computabilidad efectiva McGraw-Hill (1967) ISBN 0-262-68052-1 (describe los ordinales recursivos y el ordinal de Church-Kleene) 
• Larry W. Miller, Funciones normales y notaciones ordinales constructivas , The Journal of Symbolic Logic , volumen 41, número 2, junio de 1976, páginas 439 a 459, JSTOR  2272243,
• Hilbert Levitz, Ordinales transfinitos y sus notaciones: para los no iniciados , artículo expositivo (8 páginas, en PostScript )
• Herman Ruge Jervell, Verdad y demostrabilidad, manuscrito en progreso.

Más allá de los ordinales recursivos

• Barwise, Jon (1976). Conjuntos y estructuras admisibles: una aproximación a la teoría de la definibilidad . Perspectivas en lógica matemática. Springer-Verlag. ISBN 3-540-07451-1.
• Hinman, Peter G. (1978). Jerarquías recursivas . Perspectivas en lógica matemática. Springer-Verlag.

Ordinales recursivos y no recursivos

• Michael Rathjen, "El ámbito del análisis ordinal", en SB Cooper y J. Truss (eds.): Sets and Proofs . (Cambridge University Press, 1999) 219–279. En el archivo Postscript.

Referencias en línea

1. Buchholz, W. (1 de enero de 1986). "Un nuevo sistema de funciones ordinales demostrativas". Anales de lógica pura y aplicada . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 . ISSN  0168-0072.
2. Simpson, Stephen G. (2009). Subsistemas de aritmética de segundo orden. Perspectivas en lógica (2.ª ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6.
3. W. Buchholz, "Un resultado de independencia para ( Π 1 1 − C A ) + B I {\displaystyle (\Pi _{1}^{1}{\mathsf {-CA}}){\mathsf {+BI}}} . (1987)"
4. Buchholz, Wilfried; Feferman, Solomon ; Pohlers, Wolfram; Sieg, Wilfried (1981). Definiciones inductivas iteradas y subsistemas de análisis: estudios teóricos de pruebas recientes . Apuntes de clase en matemáticas. Vol. 897. Springer-Verlag, Berlín-Nueva York. doi :10.1007/bfb0091894. ISBN. 3-540-11170-0.Sr. 0655036  .
5. "Un zoológico de ordinales" (PDF) . Madore . 2017-07-29 . Consultado el 10 de agosto de 2021 .
6. W. Buchholz, Un nuevo sistema de funciones ordinales demostrativas (1984) (lemas 1.3 y 1.8). Consultado el 4 de mayo de 2022.
7. Rathjen, Michael (1 de enero de 1994). "Funciones colapsantes basadas en ordinales recursivamente grandes: una prueba de ordenación adecuada para KPM". Archivo de lógica matemática . 33 (1): 35–55. doi :10.1007/BF01275469. ISSN  1432-0665. S2CID  35012853.
8. "Notaciones ordinales basadas en un cardinal débilmente Mahlo" (PDF) . Universidad de Leeds . 1990 . Consultado el 10 de agosto de 2021 .
9. "Teoría de la prueba de la reflexión" (PDF) . Universidad de Leeds . 21 de febrero de 1993 . Consultado el 10 de agosto de 2021 .
10. Stegert, Jan-Carl (2010). "Teoría de la prueba ordinal de la teoría de conjuntos de Kripke-Platek aumentada por principios de reflexión fuerte". miami.uni-muenster.de . Consultado el 10 de agosto de 2021 .
11. Friedman, H., Jensen, R. (1968). Nota sobre ordinales admisibles. En: Barwise, J. (eds.) The Syntax and Semantics of Infinitary Languages. Lecture Notes in Mathematics, vol. 72. Springer, Berlín, Heidelberg.
12. Sacks, Gerald E. (1976). "Ordinales contables admisibles e hipergrados". Avances en Matemáticas . 20 (2): 213–262. doi : 10.1016/0001-8708(76)90187-0 .
13. "Subsistemas de aritmética de segundo orden" (PDF) . Penn State Institution . 2006-02-07 . Consultado el 2010-08-10 .
14. FG Abramson, GE Sacks, "Incontables ordinales de Gandy" (1976), p.387. Consultado el 13 de febrero de 2023.
15. A. Kechris, "Clases de segundo orden de Spector y reflexión". Publicado en Generalized Recursion Theory II: Proceedings of the 1977 Oslo Symposium , Studies in Logic and the Foundation of Mathematics vol. 94 (1978), pp.147--183
16. Arai, Toshiyasu (2015). "Un análisis simplificado de la reflexión de primer orden". arXiv : 1907.17611v1 .
17. W. Richter, P. Aczel, Definiciones inductivas y propiedades de reflexión de ordinales admisibles (1973)
18. Richter, Wayne; Aczel, Peter (1 de enero de 1974). "Definiciones inductivas y propiedades reflectoras de ordinales admisibles" (PDF) . Estudios de lógica y fundamentos de las matemáticas . 79 : 301–381. doi :10.1016/S0049-237X(08)70592-5. hdl :10852/44063. ISBN 9780444105455. ISSN  0049-237X.
19. S. Feferman, "Indescriptible Cardinals and Admissible Analogues" (2013, inédito). Consultado el 18 de noviembre de 2022.
20. KJ Devlin, Introducción a la estructura fina de la jerarquía construible, Estudios de lógica y fundamentos de las matemáticas (vol. 79, 1974). Consultado el 4 de diciembre de 2022.
21. "Fred G. Abramson, Locally countable models of Σ 1 {\displaystyle \Sigma _{1}} -separation" (2014). Consultado el 23 de julio de 2022.
22. KJ Devlin, Introducción a la estructura fina de la jerarquía construible (1974). Consultado el 21 de febrero de 2023.
23. 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.
24. Barwise (1976), teorema 7.2.
25. Simpson, Stephen G. (1 de enero de 1978). "Curso breve sobre teoría de la recursión admisible". Estudios de lógica y fundamentos de las matemáticas . 94 : 355–390. doi :10.1016/S0049-237X(08)70941-8. ISBN 9780444851635. ISSN  0049-237X.
26. Arai, Toshiyasu (1996). "Introducción de la línea dura en la teoría de la demostración". arXiv : 1104.1842v1 [math.LO].
27. W. Chan, The countable admisible ordinal equivalence relationship (2017), p.1233. Consultado el 28 de diciembre de 2022.