Ordinal contable grande

Ordinales en matemáticas y teoría de conjuntos

En la disciplina matemática de la teoría de conjuntos , hay muchas maneras de describir ordinales contables específicos . Los más pequeños pueden expresarse 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 todavía 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 disponibles varias formas más concretas de definir ordinales que definitivamente tienen notaciones.

Dado que sólo 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 ω^CK
₁(no debe confundirse con el primer ordinal incontable, ω ₁ ), que se describe a continuación. Números ordinales debajo de ω^CK
₁son los ordinales recursivos (ver más abajo). Aún se pueden definir ordinales contables mayores que este, pero no tienen notaciones.

Debido al enfoque en los ordinales contables, la aritmética ordinal se utiliza en todo momento, excepto que se indique lo contrario. Los ordinales aquí descritos no son tan grandes como los descritos en cardenales grandes , pero sí lo son entre los 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 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; entonces, esencialmente, un ordinal es recursivo cuando podemos presentar el conjunto de ordinales más pequeños de tal manera que una computadora ( la 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 el 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 el orden es computable; sin embargo, el conjunto O de notaciones ordinales en sí es altamente no recursivo, debido a la imposibilidad de decidir si una máquina de Turing dada produce realmente una secuencia de notaciones); un ordinal recursivo es entonces un ordinal descrito mediante alguna notación ordinal.

Cualquier ordinal más pequeño 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).

Es tentador olvidarse de las notaciones ordinales y hablar sólo de los ordinales recursivos propiamente dichos: y se hacen algunas afirmaciones sobre los ordinales recursivos que, de hecho, se refieren a las notaciones de estos ordinales. Sin embargo, esto genera 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 de aritmética.

Existe una relación entre los ordinales computables y ciertos sistemas formales (que contienen 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 ser dados por una cierta notación ordinal o , un sistema formal dado podría no ser lo suficientemente poderoso como para demostrar que o es, de hecho, una notación ordinal: el sistema no muestra inducción transfinita para tales grandes ordinales.

Por ejemplo, los axiomas habituales de Peano de primer orden no prueban la inducción transfinita para (o más allá) ε : mientras que el ordinal ε ₀ puede describirse aritméticamente fácilmente (es contable), los axiomas de Peano no son lo suficientemente fuertes como para demostrar 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 ), por lo que según el segundo teorema de incompletitud de Gödel , los axiomas de Peano no pueden formalizar ese razonamiento. (Esto es la base del teorema de Kirby-Paris sobre las secuencias de Goodstein ). Dado que la aritmética de Peano puede demostrar que cualquier ordinal menor que ε ₀ está bien ordenado, decimos que ε ₀ mide la fuerza de la teoría de 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 prueba de la teoría de conjuntos de Kripke-Platek 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 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 infinito de letras, es mejor usar una notación más robusta: definir 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, se define como el -ésimo punto fijo común de para todos . Esta familia de funciones se conoce como 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 for : esto esencialmente simplemente 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 }$

Ordenar: si y sólo 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 que se conoce como ordinal de Feferman-Schütte y generalmente se escribe . 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 suma. 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 sistemas como la " recursión aritmética transfinita ". ${\displaystyle \varphi _{\alpha }(0)=\alpha }$ ${\displaystyle \Gamma _{0}}$

De manera más general, Γ _α enumera los ordinales que no se pueden obtener a partir de ordinales más pequeños mediante 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 lleva a la definición de los ordinales de Veblen " pequeños " y " grandes ". ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$

Ordinales impredicativos

Para ir mucho más allá del ordinal de Feferman-Schütte, es necesario introducir nuevos métodos. Desafortunadamente, todavía no existe una forma estándar de hacer esto: 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 Buchholz, Takeuti (diagramas ordinales), Feferman (sistemas θ), Aczel , Bridge, Schütte y Pohlers describieron diferentes extensiones y variaciones del mismo. . Sin embargo, la mayoría de los sistemas utilizan la misma idea básica: construir nuevos ordinales contables utilizando la existencia de ciertos ordinales incontables. A continuación se muestra un ejemplo de dicha definición, que se describe 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 suma, multiplicación y exponenciación, y ψ a ordinales previamente construidos (excepto que ψ solo se puede aplicar a argumentos menores que α , para asegurar que esté bien definido).

Aquí Ω = ω ₁ es el primer ordinal incontable. Se introduce porque, de lo contrario, la función ψ se "atasca" en el ordinal más pequeño σ tal que ε _σ = σ : en particular ψ( α )= σ para cualquier ordinal α que satisfaga σ ≤ α ≤Ω. Sin embargo, el hecho de que incluyamos Ω 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 ψ agregando más formas de construir ordinales incontables. Hay varias formas de hacer esto, que se describen hasta cierto punto 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 fuerza de la teoría de prueba 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 , por no hablar de la teoría de conjuntos de Zermelo-Fraenkel , parecen fuera de nuestro alcance por el momento.

Más allá incluso del ordinal 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 como just , utilizando la notación anterior. Es el ordinal de la teoría de la prueba de , ^[1] una teoría de la aritmética de primer orden que permite la cuantificación de los números naturales así como de 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 usando hidras del juego. ^{[3] p.136} Por ejemplo corresponde a . ${\displaystyle +(0(\omega ))}$ ${\displaystyle \psi (\Omega _{\omega })}$

El siguiente es el ordinal Takeuti-Feferman-Buchholz , el ordinal teórico de la prueba de ; ^[4] y otro subsistema de aritmética de segundo orden: - comprensión + inducción transfinita, y , la "teoría formal de las definiciones inductivas iteradas -veces". ^[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 necesaria ]} ${\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 grandes ordinales y números contables en Agda, y "AndrasKovacs" lo define como . ${\displaystyle \psi _{0}(\Omega _{\omega +1}\cdot \varepsilon _{0})}$

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

Este siguiente ordinal se menciona, una vez más, en este mismo fragmento de código, definido como , es el ordinal de teoría de prueba de . En general, el ordinal de la teoría de prueba de es igual a - tenga en cuenta que en este caso concreto, 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 está el primer cardinal inaccesible (= -indescriptible). Este es el ordinal teórico de prueba 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 -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 está el primer cardenal Mahlo . Este es el ordinal teórico de prueba 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 al uso de 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 está el primer cardinal débilmente compacto (= -indescriptible). Este es el ordinal de la teoría de prueba de la teoría de conjuntos de Kripke-Platek + Π3 - Ref. Su valor es igual al uso de 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 está el primer cardenal indescriptible. Este es el ordinal de la teoría de prueba de la teoría de conjuntos de Kripke-Platek + Πω-Ref. Su valor es igual al uso de 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 se refiere como el ordinal de estabilidad de la teoría de la prueba. ^[5] Este es el ordinal de la teoría de prueba de la Estabilidad, una extensión de la teoría de conjuntos de Kripke-Platek. Su valor es igual al uso de 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 }$

El siguiente es un grupo de ordinales de los que no se sabe mucho, pero que siguen siendo bastante significativos (en orden ascendente):

• "El ordinal de la teoría de la prueba de la aritmética de segundo orden" .
• Un posible límite de la notación C ordinal de Taranovsky. (Conjetural, suponiendo que el sistema de notación esté bien fundamentado)
• El ordinal de la teoría de la prueba 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 ordinales que miden las fortalezas de varias teorías sólidas; En términos generales, estos ordinales son los tipos de orden más pequeño de notaciones ordinales "naturales" que las teorías no pueden probar que estén bien ordenadas. Al tomar teorías cada vez más sólidas, 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 si todos estos son realmente ordinales: por construcción, sólo se puede demostrar que la fuerza ordinal de una teoría es un ordinal de una teoría aún más fuerte. Por lo tanto, para los axiomas cardinales grandes esto resulta bastante confuso).

Más allá de los ordinales recursivos

El ordinal de la Iglesia-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 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; sólo podemos definirlos . Pero todavía es mucho menor que el primer ordinal incontable . Sin embargo, como sugiere su símbolo, se comporta en muchos aspectos como . Por ejemplo, se pueden definir funciones de colapso ordinales usando 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}}$

Ordinales admisibles

El ordinal de Church-Kleene está nuevamente relacionado 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. Estos ordinales se denominan admisibles , por lo que es el ordinal más pequeño admisible (más allá de ω en caso de que el axioma del infinito no esté incluido en KP). ${\displaystyle L_{\alpha }}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

Según 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 necesaria ]} ${\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), pero el ordinal en sí no es admisible. También es el más pequeño el que constituye 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 sea el -ésimo ordinal admisible, se llama recursivamente inaccesible , y se puede denotar el menos recursivamente inaccesible . ^[14] Un ordinal que es recursivamente inaccesible y un límite de recursivamente inaccesibles se llama recursivamente hiperinaccesible . ^[5] Existe una teoría de los ordinales grandes de esta manera que es muy paralela a la de los cardenales grandes (pequeños) . Por ejemplo, podemos definir recursivamente ordinales de Mahlo : son tales que cada subconjunto recursivo cerrado e ilimitado de contiene un ordinal admisible (un análogo recursivo de la definición de cardinal de Mahlo ). La sección 1 del funcional de Harrington es igual a , donde es el ordinal de Mahlo menos recursivo. ^{[15] pág.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 aquí todavía estamos hablando de ordinales posiblemente contables. (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 los ordinales de Mahlo recursivamente inaccesibles o recursivamente es un teorema de ZFC: de hecho, cualquier cardinal regular es recursivamente Mahlo y más, pero incluso si limitamos Nos referimos a ordinales contables, ^{[ se necesita aclaración ]} ZFC demuestra la existencia de ordinales de Mahlo recursivamente. 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 llama -reflectante 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 aumenta la teoría de conjuntos de Kripke-Platek mediante un esquema de reflexión. También pueden considerarse "análogos recursivos" de algunos cardenales incontables, como los cardenales débilmente compactos y los cardenales indescriptibles . ^[17] Por ejemplo, un ordinal que -reflectante se llama recursivamente débilmente compacto . ^[18] Para finito , el ordinal menos reflectante es también el supremo de los ordinales de cierre de definiciones inductivas monótonas cuyas gráficas 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 reflectantes también tienen una caracterización que utiliza funcionales de tipo superior en funciones ordinales, lo que les da el nombre de 2 ordinales admisibles . ^[18] Un artículo inédito de Solomon Feferman proporciona, para cada finito , una propiedad similar correspondiente a -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 mapee en un ordinal más pequeño. (Esto es trivialmente cierto para los cardinales regulares; sin embargo, estamos interesados ​​principalmente en los ordinales contables). Ser no proyectable es una condición mucho más fuerte que ser admisible, recursivamente inaccesible o incluso recursivamente Mahlo. ^[13] Según el método de proyecto de Jensen, ^[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 separación KP + . Sin embargo, la separación por sí sola (no en presencia de ) no es un esquema de axioma lo suficientemente fuerte como para implicar no proyectabilidad; de hecho, existen modelos transitivos de separación + de cualquier altura contable admisible . ^[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 en projecta. ^{[5] [22]} Los menos ordinales que no son proyectables en relación con un conjunto dado están vinculados a la construcción de Harrington de la clase Spector 2 reflectante más pequeña. ^{[15] pág.174}

Ordinales "indemostrables"

Podemos imaginar ordinales aún más grandes que todavía 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 contable tal que es un modelo de ZFC. Tales ordinales están más allá de la solidez de ZFC en el sentido de que no puede (por construcción) probar su existencia. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$

Si una teoría de conjuntos recursivamente enumerable es consistente con V = L , entonces el menor es menor que el ordinal menos estable, que sigue. ^[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 mediante condiciones de indescriptibilidad o como aquellas que son un submodelo elemental Σ 1 de L ; la existencia de estos ordinales se puede probar en ZFC, ^[24] y están estrechamente relacionados con los ordinales no proyectables desde una perspectiva teórica 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. Dejando ser mínimo tal que : ${\displaystyle L}$ ${\displaystyle \sigma }$ ${\displaystyle L_{\sigma }\prec _{1}L}$

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

Variantes de ordinales estables

Éstas son variantes debilitadas de ordinales estables. Hay ordinales con estas propiedades más pequeñas que el ordinal menos no proyectable mencionado anteriormente, ^[5] por ejemplo, un ordinal es estable si y solo refleja todo lo natural . ^[18] ${\displaystyle (+1)}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle n}$

• Un ordinal contable se llama -stable iff ^[5] ${\displaystyle \alpha }$ ${\displaystyle (+\beta )}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\alpha +\beta }}$
• Un ordinal contable se llama -stable iff , donde el ordinal menos admisible es mayor que . ^{[5] [25]} ${\displaystyle \alpha }$ ${\displaystyle (^{+})}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Un ordinal contable se llama -stable iff , donde el ordinal menos admisible es 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 llama inaccesiblemente estable si , donde el ordinal menos recursivamente inaccesible es mayor que . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Un ordinal contable se llama Mahlo-estable sif , donde el ordinal de Mahlo menos recursivo es 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 hay 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 la prueba, incluido el análisis de subsistemas de aritmética de segundo orden . ^[26]

Un pseudo-bien-ordenamiento

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 tenga un segmento inicial que esté bien ordenado con tipo de orden . Cada subconjunto no vacío recursivamente enumerable (o incluso hiperaritmético) de este orden total tiene un elemento mínimo. Por lo tanto, en algunos aspectos se parece a un buen ordenamiento. Por ejemplo, se pueden definir las operaciones aritméticas en él. Sin embargo, no es posible determinar de manera efectiva exactamente dónde termina la parte inicial bien ordenada y comienza la parte que carece de un elemento mínimo. ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

Para un ejemplo de un pseudo-ordenamiento recursivo, sea S ATR ₀ u otra teoría recursivamente axiomatizable que tenga un modelo ω pero no modelos ω hiperaritméticos y (si es necesario) extienda conservadoramente S con funciones de Skolem . Sea T el árbol de (esencialmente) modelos ω parciales finitos de S: una secuencia de números naturales está en T 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 prueba de inconsistencia más corta que n. Entonces el orden de Kleene-Brouwer de T es un pseudoordenamiento 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 grandes ordinales contables tratan sobre la teoría de la prueba y, lamentablemente, tienden a estar agotados.

Sobre ordinales recursivos

• Wolfram Pohlers, Teoría de la prueba , Springer 1989 ISBN  0-387-51842-8 (para la jerarquía de Veblen y algunos ordinales impredicativos). Este es probablemente el libro más legible sobre ordinales contables grandes (lo cual no dice 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, Las variedades de la experiencia arbórea Matemáticas. Inteligencia 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 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 de la teoría de la recursión" . 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.): Conjuntos y pruebas . (Prensa de la Universidad de Cambridge, 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: Prensa de la Universidad de Cambridge. 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, Salomón ; Pohlers, Wolfram; Sieg, Wilfried (1981). Definiciones inductivas iteradas y subsistemas de análisis: estudios teóricos de prueba recientes . Apuntes de conferencias de matemáticas. vol. 897. Springer-Verlag, Berlín-Nueva York. doi :10.1007/bfb0091894. ISBN 3-540-11170-0. SEÑOR  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 con teoría de prueba (1984) (lemas 1.3 y 1.8). Consultado el 4 de mayo de 2022.
7. Rathjen, Michael (1 de enero de 1994). "Colapso de funciones basadas en ordinales recursivamente grandes: una prueba de buen ordenamiento 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 cardenal 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 . 1993-02-21 . Consultado el 10 de agosto de 2021 .
10. Stegert, Jan-Carl (2010). "Teoría de prueba ordinal de la teoría de conjuntos de Kripke-Platek aumentada por fuertes principios de reflexión". 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) La sintaxis y la semántica de los lenguajes infinitos. Lecture Notes in Mathematics, vol 72. Springer, Berlín, Heidelberg.
12. Sacos, Gerald E. (1976). "Contables ordinales e hipergrados admisibles". 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) . Institución de Penn State . 2006-02-07 . Consultado el 10 de agosto de 2010 .
14. FG Abramson, GE Sacks, "Incontables ordinales de Gandy" (1976), p.387. Consultado el 13 de febrero de 2023.
15. A. Kechris, "Reflexión y clases de segundo orden de Spector". Apareciendo en Teoría de la recursión generalizada II: Actas del Simposio de Oslo de 1977 , Estudios de lógica y fundamentos de las matemáticas vol. 94 (1978), págs.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 reflectantes de los 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, "Cardenales indescriptibles y análogos admisibles" (2013, inédito). Consultado el 18 de noviembre de 2022.
20. KJ Devlin, Una introducción a la fina estructura 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, Modelos localmente contables de Σ 1 {\displaystyle \Sigma _{1}} -separación" (2014). Consultado el 23 de julio de 2022.
22. KJ Devlin, Una introducción a la fina estructura 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). "Introduciendo la línea dura en la teoría de la prueba". arXiv : 1104.1842v1 [matemáticas.LO].
27. W. Chan, La relación de equivalencia ordinal admisible contable (2017), p.1233. Consultado el 28 de diciembre de 2022.