En la disciplina matemática de la teoría de conjuntos , hay muchas formas 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 de relevancia 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 un tanto análogas a la imposibilidad de resolver el problema de la detención ); Se encuentran disponibles varias formas más concretas de definir ordinales que definitivamente tienen notaciones.
Dado que solo hay muchas notaciones contables, todos los ordinales con notaciones se agotan muy por debajo del primer ordinal incontable ω 1 ; su supremo se llama Church-Kleene ω 1 o ω 1 CK (no confundir con el primer ordinal incontable, ω 1 ), que se describe a continuación . Los números ordinales por debajo de ω 1 CK son los ordinales recursivos (ver más abajo ). Los ordinales contables mayores que esto aún pueden definirse, pero no tienen notaciones.
Debido al enfoque en los ordinales contables, la aritmética ordinal se usa en todas partes, excepto donde se indique lo contrario. Los ordinales descritos aquí no son tan grandes como los descritos en grandes cardenales , pero son grandes entre los que tienen notaciones constructivas (descripciones). Se pueden definir ordinales cada vez más grandes, pero cada vez son más difíciles de describir.
Generalidades sobre ordinales recursivos
Notaciones ordinales
Los ordinales recursivos (u ordinales computables) son ciertos ordinales contables: hablando libremente, 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 algunos recursivos (es decir, computables) bien ordenados 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 ( digamos una máquina de Turing ) pueda manipularlos (y, esencialmente, compararlos).
Una definición diferente usa 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 para hacer que el sucesor de o sea mayor que o y hacer que 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í mismo es altamente no recursivo, debido a la imposibilidad de decidir si una máquina de Turing dada produce efectivamente una secuencia de notaciones); un ordinal recursivo es entonces un ordinal descrito por 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 ordinal determinado (contable), el ordinal de Church-Kleene (ver más abajo).
Es tentador olvidarse de las notaciones ordinales y solo hablar de los ordinales recursivos mismos: y se hacen algunas afirmaciones sobre los ordinales recursivos que, de hecho, se refieren a las notaciones de 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 probar que sean equivalentes a la notación obvia (el límite del 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 puede no ser lo suficientemente poderoso para mostrar que o es, de hecho, una notación ordinal: el sistema no muestra inducción transfinita para tan grandes ordinales.
Por ejemplo, los axiomas de Peano de primer orden habituales no prueban la inducción transfinita para (o más allá) ε 0 : mientras que el ε 0 ordinal puede describirse aritméticamente fácilmente (es contable), los axiomas de Peano no son lo suficientemente fuertes para demostrar que es de hecho un ordinal; de hecho, la inducción transfinita en ε 0 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 está en la base del teorema de Kirby-Paris sobre secuencias de Goodstein ). Decimos que ε 0 mide la fuerza de la teoría de la prueba de los axiomas de Peano.
Pero podemos hacer esto para sistemas mucho más allá de los axiomas de Peano. Por ejemplo, la fuerza teórica de la prueba de la teoría de conjuntos de Kripke-Platek es el ordinal de Bachmann-Howard y, de hecho, basta con agregar a los axiomas de Peano los axiomas que establecen el buen orden de todos los ordinales por debajo del ordinal de Bachmann-Howard. 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, , , , etc. El siguiente ordinal que satisface esta ecuación se llama ε 1 : es el límite de la secuencia
De manera más general, la -th ordinal tal que se llama . Podríamos definir como el ordinal más pequeño tal que , pero dado que el alfabeto griego no tiene muchas letras transfinitivamente, es mejor usar una notación más robusta: definir ordinales por inducción transfinita de la siguiente manera: sea y deja ser el -th punto fijo de (es decir, el -th ordinal tal que ; así por ejemplo,), y cuando es un ordinal límite, define como el -th punto fijo común del para todos . Esta familia de funciones se conoce como la jerarquía de Veblen (hay variaciones no esenciales en la definición, como dejar, por un límite ordinal, ser el límite de la por : esto esencialmente solo cambia los índices en 1, lo cual es inofensivo). se llama el Función Veblen (a la base).
Ordenar: si y solo si ( y ) o ( y ) o ( y ).
El ordinal de Feferman-Schütte y más allá
El ordinal más pequeño tal que se conoce como el ordinal de Feferman-Schütte y generalmente se escribe. Se puede describir como el conjunto de todos los ordinales que se pueden escribir como expresiones finitas, comenzando desde cero, usando solo la jerarquía y la suma de Veblen. 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 se puede describir (“ predicativamente ”) usando ordinales más pequeños. Mide la fuerza de sistemas como la “ recursividad transfinita aritmética ”.
De manera más general, Γ α enumera los ordinales que no se pueden obtener de los ordinales más pequeños usando 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 seguir buscando puntos fijos de una manera cada vez más complicada: enumerar los puntos fijos de, luego enumere los puntos fijos de eso , y así sucesivamente, y luego busque el primer ordinal α tal que α se obtenga en α pasos de este proceso, y continúe diagonalizando de esta manera ad hoc . Esto conduce a la definición de los ordinales de Veblen “ pequeños ” y “ grandes ”.
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 usan la misma idea básica, de construir nuevos ordinales contables usando la existencia de ciertos ordinales incontables. Aquí hay un ejemplo de tal 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 suma, multiplicación y exponenciación, y ψ a ordinales previamente construidos (excepto que ψ solo se puede aplicar a argumentos menores que α, para asegurarse de que esté bien definido).
Aquí Ω = ω 1 es el primer ordinal incontable. Se coloca porque, de lo contrario, la función ψ se "atasca" en el σ ordinal más pequeño de modo 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 usamos es que es mayor que cualquier ordinal producido por ψ.
Para construir ordinales aún más grandes, podemos extender la definición de ψ agregando más formas de construir ordinales incontables. Hay varias formas de hacer esto, descritas 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 la 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 , y mucho menos la teoría de conjuntos de Zermelo-Fraenkel , parecen fuera de alcance por el momento.
Ordinales recursivos "irrecuperables"
Al eliminar el requisito de tener una descripción útil, se pueden obtener ordinales contables recursivos incluso más grandes como los ordinales que miden la fuerza de varias teorías sólidas; En términos generales, estos ordinales son los ordinales más pequeños que las teorías no pueden probar que estén bien ordenados. Mediante la adopción de las teorías más fuertes y 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 grandes cardinales axiomas, uno tiene algunas extremadamente grandes ordinales recursivas. (Estrictamente hablando, no se sabe que todos estos son realmente ordinales: por construcción, la fuerza ordinal de una teoría solo puede probarse que es un ordinal a partir de una teoría aún más fuerte. Por lo tanto, para los axiomas cardinales grandes esto se vuelve bastante confuso).
Más allá de los ordinales recursivos
El ordinal de 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 de los enteros). Ese ordinal es un ordinal contable llamado ordinal 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 todavía es mucho menos que el primer ordinal incontable,. Sin embargo, como sugiere su símbolo, se comporta de muchas maneras más bien como. [ ejemplo necesario ]
Ordinales admisibles
El ordinal de Church-Kleene se relaciona de nuevo 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 que KP no prueba la inducción transfinita, el ordinal de Church-Kleene es el α más pequeño de modo que la construcción del universo de Gödel , L , hasta la etapa α, produce un modelode KP. Tales ordinales se denominan admisibles , por lo que 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).
Según un teorema de Sacks , los ordinales contables admisibles son exactamente aquellos construidos de manera similar al ordinal de Church-Kleene pero para las máquinas de Turing con oráculos . Uno a veces escribe Para el -th ordinal que es admisible o un límite de admisibles menores.
Más allá de los ordinales admisibles
Un ordinal que es admisible y un límite de admisibles, o equivalentemente tal que es el -ésimo ordinal admisible, se llama recursivamente inaccesible . Existe una teoría de los grandes ordinales de esta manera que es muy paralela a la de los (pequeños) grandes cardenales . Por ejemplo, podemos definir recursivamente ordinales Mahlo : estos son los tal que cada -subconjunto ilimitado cerrado recursivo de contiene un ordinal admisible (un análogo recursivo de la definición de un cardenal Mahlo ). Pero tenga en cuenta que aquí todavía estamos hablando de ordinales posiblemente contables. (Si bien la existencia de cardenales inaccesibles o Mahlo no se puede probar en la teoría de conjuntos de Zermelo-Fraenkel , la de los ordinales Mahlo recursivamente inaccesibles o recursivamente es un teorema de ZFC: de hecho, cualquier cardenal regular es Mahlo recursivamente y más, pero incluso si limitamos nosotros mismos a ordinales contables, ZFC demuestra la existencia de ordinales Mahlo recursivamente. Sin embargo, están más allá del alcance de la teoría de conjuntos de Kripke-Platek.)
Reflexión y no proyectibilidad
Para un conjunto de fórmulas , un ordinal límite se llama -reflejando si el rango satisface una cierta propiedad de reflexión para cada -fórmula . [1] Estos ordinales aparecen en el análisis ordinal de teorías como KP + Π 3 -ref , una teoría que aumenta la teoría de conjuntos de Kripke-Platek por 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 . [2]
Un ordinal admisible se llama no proyectable si no hay total-mapeo de función inyectiva recursiva en un ordinal más pequeño. (Esto es trivialmente cierto para los cardenales 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. Es equivalente a la afirmación de que el universo de Gödel , L , hasta la etapa α, produce un modelo de KP + -separación.
Ordinales "no probables"
Podemos imaginar ordinales aún más grandes que aún sean contables. Por ejemplo, si ZFC tiene un modelo transitivo (una hipótesis más fuerte que la mera hipótesis de consistencia, e implicada por la existencia de un cardinal inaccesible), entonces existe una 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.
Incluso los ordinales contables más grandes, llamados ordinales estables , pueden definirse mediante condiciones indescriptibles o como aquellas tal que es un submodelo 1-elemental de L ; la existencia de estos ordinales se puede demostrar en ZFC, [3] y están estrechamente relacionados con los ordinales no proyectables desde una perspectiva de teoría de modelos. [4]
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 es un subconjunto de las notaciones de Kleene y tiene un segmento inicial que está bien ordenado con el 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, se parece a un buen orden en algunos aspectos. Por ejemplo, se pueden definir las operaciones aritméticas en él. Sin embargo, no es posible determinar con eficacia exactamente dónde termina la parte inicial bien ordenada y dónde comienza la parte que carece de un elemento mínimo.
Para un ejemplo de un pseudo-ordenamiento de pozos recursivo, sea S ATR 0 u otra teoría recursivamente axiomatizable que tenga un modelo ω pero no modelos ω hiperaritméticos, y (si es necesario) extienda de forma conservadora S con funciones de Skolem . Sea T el árbol de (esencialmente) modelos ω parciales finitos de S: Una secuencia de números naturalesestá en T iff S más ∃m φ (m) ⇒ φ (x ⌈φ⌉ ) (para las primeras n fórmulas φ con una variable libre numérica; ⌈φ⌉ es el número de Gödel) no tiene prueba de inconsistencia menor que n. Entonces, el orden de Kleene-Brouwer de T es un pseudowellordering recursivo.
Referencias
La mayoría de los libros que describen grandes ordinales contables se basan en la teoría de la prueba y, lamentablemente, tienden a estar agotados.
En 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 grandes ordinales contables (lo que no dice mucho).
- Gaisi Takeuti , Teoría de la prueba , 2a 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 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 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 proceso.
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 teoría de la recursividad . Perspectivas en lógica matemática. Springer-Verlag.
Ordinales recursivos y no recursivos
- Michael Rathjen , "El reino del análisis ordinal". en S. Cooper y J. Truss (eds.): Conjuntos y pruebas . (Cambridge University Press, 1999) 219-279. En el archivo Postscript .
Referencias en línea
- ^ T. Arai, Un análisis simplificado de la reflexión de primer orden (2015)
- ^ W. Richter, P. Aczel, Definiciones inductivas y propiedades de reflexión de ordinales admisibles (1973)
- ^ Barwise (1976), teorema 7.2.
- ^ D. Madore, Un zoológico de ordinales (2017) (p.6). Consultado el 6 de mayo de 2021.