Función colapsante ordinal

Función de teoría de conjuntos

En lógica matemática y teoría de conjuntos , una función de colapso ordinal (o función de proyección ) es una técnica para definir ( notaciones para) ciertos ordinales contables recursivos grandes , cuyo principio es dar nombres a ciertos ordinales mucho más grandes que el que se está definiendo, quizás incluso cardinales grandes (aunque pueden reemplazarse con ordinales recursivamente grandes a costa de una dificultad técnica adicional), y luego "colapsarlos" a un sistema de notaciones para el ordinal buscado. Por esta razón, las funciones de colapso ordinal se describen como una manera impredicativa de nombrar ordinales.

Los detalles de la definición de funciones colapsantes de ordinales varían y se vuelven más complicados a medida que se definen ordinales mayores, pero la idea típica es que siempre que el sistema de notación "se quede sin combustible" y no pueda nombrar un ordinal determinado, se traiga un ordinal mucho mayor "desde arriba" para dar un nombre a ese punto crítico. A continuación se detallará un ejemplo de cómo funciona esto, para una función colapsante de ordinales que define el ordinal de Bachmann-Howard (es decir, que define un sistema de notaciones hasta el ordinal de Bachmann-Howard).

El uso y la definición de funciones de colapso ordinal están inextricablemente entrelazados con la teoría del análisis ordinal , ya que los grandes ordinales contables definidos y denotados por un colapso dado se utilizan para describir la fuerza ordinal-teórica de ciertos sistemas formales , típicamente ^{[1] [2]} subsistemas de análisis (como los que se ven a la luz de las matemáticas inversas ), extensiones de la teoría de conjuntos de Kripke-Platek , sistemas de matemáticas constructivas al estilo Bishop o sistemas de teoría de tipos intuicionistas al estilo Martin-Löf .

Las funciones colapsantes ordinales generalmente se denotan utilizando alguna variación de la letra griega ( psi ) o ( theta ). ${\displaystyle \psi }$ ${\displaystyle \theta }$

Un ejemplo que conduce al ordinal de Bachmann-Howard

La elección de la función de colapso ordinal que se da como ejemplo a continuación imita en gran medida el sistema introducido por Buchholz ^[3], pero se limita a colapsar un cardinal para mayor claridad de la exposición. Más adelante se explicará con más detalle la relación entre este ejemplo y el sistema de Buchholz.

Definición

Sea , el primer ordinal incontable o, de hecho, cualquier ordinal que sea un número y que se garantice que es mayor que todos los ordinales contables que se construirán (por ejemplo, el ordinal Church-Kleene es adecuado para nuestros propósitos; pero trabajaremos con él porque permite el uso conveniente de la palabra contable en las definiciones). ${\displaystyle \Omega }$ ${\displaystyle \omega _{1}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \omega _{1}}$

Definimos una función (que será no decreciente y continua ), tomando un ordinal arbitrario como un ordinal contable , recursivamente en , de la siguiente manera: ${\displaystyle \psi }$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\alpha )}$ ${\displaystyle \alpha }$

Supongamos que se ha definido para todos y deseamos definir . ${\displaystyle \psi (\beta )}$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \psi (\alpha )}$

Sea el conjunto de ordinales generado a partir de , , y aplicando recursivamente las siguientes funciones: suma, multiplicación y exponenciación de ordinales y la función , es decir, la restricción de a los ordinales . (Formalmente, definimos y inductivamente para todos los números naturales y sea la unión de los para todos los .) ${\displaystyle C(\alpha )}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \psi \upharpoonright _{\alpha }}$ ${\displaystyle \psi }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle C(\alpha )_{0}=\{0,1,\omega ,\Omega \}}$ ${\displaystyle C(\alpha )_{n+1}=C(\alpha )_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{\beta _{2}}:\beta _{1},\beta _{2}\in C(\alpha )_{n}\}\cup \{\psi (\beta ):\beta \in C(\alpha )_{n}\land \beta <\alpha \}}$ ${\displaystyle n}$ ${\displaystyle C(\alpha )}$ ${\displaystyle C(\alpha )_{n}}$ ${\displaystyle n}$

Entonces se define como el ordinal más pequeño que no pertenece a . ${\displaystyle \psi (\alpha )}$ ${\displaystyle C(\alpha )}$

De una manera más concisa (aunque más oscura):

${\displaystyle \psi (\alpha )}$es el ordinal más pequeño que no se puede expresar a partir de , y utilizando sumas, productos, exponenciales y la función misma (hasta ordinales construidos previamente menores que ) . ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \psi }$ ${\displaystyle \alpha }$

He aquí un intento de explicar la motivación para la definición de en términos intuitivos: puesto que las operaciones habituales de adición, multiplicación y exponenciación no son suficientes para designar ordinales muy lejanos, intentamos crear sistemáticamente nuevos nombres para los ordinales tomando el primero que todavía no tiene nombre, y siempre que nos quedamos sin nombres, en lugar de inventarlos de manera ad hoc o utilizando esquemas diagonales , los buscamos en los ordinales mucho más allá de los que estamos construyendo (más allá de , claro está); así que damos nombres a ordinales incontables y, puesto que al final la lista de nombres es necesariamente contable, los "colapsaremos" a ordinales contables. ${\displaystyle \psi }$ ${\displaystyle \Omega }$ ${\displaystyle \psi }$

Cálculo de valores deψ

Para aclarar cómo la función es capaz de producir notaciones para ciertos ordinales, ahora calculamos sus primeros valores. ${\displaystyle \psi }$

Inicio predictivo

Consideremos primero . Contiene ordinales , etcétera. También contiene ordinales como . El primer ordinal que no contiene es (que es el límite de , , etcétera —menor que por suposición). El límite superior de los ordinales que contiene es (el límite de , , etcétera), pero eso no es tan importante. Esto demuestra que . ${\displaystyle C(0)}$ ${\displaystyle 0,1,2,3,\omega ,\omega +1,\omega +2,\omega \cdot 2,\omega \cdot 3,\omega ^{2},\omega ^{3},\omega ^{\omega },\omega ^{\omega ^{\omega }}}$ ${\displaystyle \Omega ,\Omega +1,\omega ^{\Omega +1},\Omega ^{\Omega }}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \omega }$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \omega ^{\omega ^{\omega }}}$ ${\displaystyle \Omega }$ ${\displaystyle \varepsilon _{\Omega +1}}$ ${\displaystyle \Omega }$ ${\displaystyle \Omega ^{\Omega }}$ ${\displaystyle \Omega ^{\Omega ^{\Omega }}}$ ${\displaystyle \psi (0)=\varepsilon _{0}}$

De manera similar, contiene los ordinales que se pueden formar a partir de , , , y esta vez también , mediante la adición, la multiplicación y la potenciación. Esto contiene todos los ordinales hasta pero no el último, por lo que . De esta manera, demostramos que inductivamente en : la prueba funciona, sin embargo, solo mientras . Por lo tanto, tenemos: ${\displaystyle C(1)}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \varepsilon _{1}}$ ${\displaystyle \psi (1)=\varepsilon _{1}}$ ${\displaystyle \psi (\alpha )=\varepsilon _{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha <\varepsilon _{\alpha }}$

${\displaystyle \psi (\alpha )=\varepsilon _{\alpha }=\varphi _{1}(\alpha )}$para todos , donde es el punto fijo más pequeño de . ${\displaystyle \alpha \leq \zeta _{0}}$ ${\displaystyle \zeta _{0}=\varphi _{2}(0)}$ ${\displaystyle \alpha \mapsto \varepsilon _{\alpha }}$

(Aquí, las funciones son las funciones de Veblen definidas comenzando con .) ${\displaystyle \varphi }$ ${\displaystyle \varphi _{1}(\alpha )=\varepsilon _{\alpha }}$

Ahora bien, pero no es mayor, ya que no se puede construir utilizando aplicaciones finitas de y, por lo tanto, nunca pertenece a un conjunto para , y la función permanece "atascada" en durante algún tiempo: ${\displaystyle \psi (\zeta _{0})=\zeta _{0}}$ ${\displaystyle \psi (\zeta _{0}+1)}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \varphi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }}$ ${\displaystyle C(\alpha )}$ ${\displaystyle \alpha \leq \Omega }$ ${\displaystyle \psi }$ ${\displaystyle \zeta _{0}}$

${\displaystyle \psi (\alpha )=\zeta _{0}}$Para todos . ${\displaystyle \zeta _{0}\leq \alpha \leq \Omega }$

Primeros valores impredicativos

Nuevamente, . Sin embargo, cuando llegamos al cálculo de , algo ha cambiado: dado que se agregó ("artificialmente") a todos los , se nos permite tomar el valor en el proceso. Por lo tanto, contiene todos los ordinales que se pueden construir a partir de , , , , la función hasta y esta vez también a sí misma, utilizando la adición, la multiplicación y la exponenciación. El ordinal más pequeño que no está en es (el número - más pequeño después de ). ${\displaystyle \psi (\Omega )=\zeta _{0}}$ ${\displaystyle \psi (\Omega +1)}$ ${\displaystyle \Omega }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \psi (\Omega )=\zeta _{0}}$ ${\displaystyle C(\Omega +1)}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \varphi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle C(\Omega +1)}$ ${\displaystyle \varepsilon _{\zeta _{0}+1}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \zeta _{0}}$

Decimos que la definición y los valores siguientes de la función tales como son impredicativos porque utilizan ordinales (aquí, ) mayores que los que se están definiendo (aquí, ). ${\displaystyle \psi (\Omega )=\zeta _{0}}$ ${\displaystyle \psi }$ ${\displaystyle \psi (\Omega +1)=\varepsilon _{\zeta _{0}+1}}$ ${\displaystyle \Omega }$ ${\displaystyle \zeta _{0}}$

Valores deψhasta el ordinal Feferman-Schütte

El hecho de que sea igual sigue siendo cierto para todo . (Obsérvese, en particular, que : pero como ahora se ha construido el ordinal, no hay nada que impida ir más allá de esto). Sin embargo, en (el primer punto fijo de más allá de ), la construcción se detiene nuevamente, porque no se puede construir a partir de ordinales más pequeños y aplicando finitamente la función. Entonces tenemos . ${\displaystyle \psi (\Omega +\alpha )}$ ${\displaystyle \varepsilon _{\zeta _{0}+\alpha }}$ ${\displaystyle \alpha \leq \zeta _{1}=\varphi _{2}(1)}$ ${\displaystyle \psi (\Omega +\zeta _{0})=\varepsilon _{\zeta _{0}\cdot 2}}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \zeta _{1}=\varphi _{2}(1)}$ ${\displaystyle \alpha \mapsto \varepsilon _{\alpha }}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \zeta _{1}}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \psi (\Omega \cdot 2)=\zeta _{1}}$

El mismo razonamiento demuestra que para todo , donde enumera los puntos fijos de y es el primer punto fijo de . Entonces tenemos . ${\displaystyle \psi (\Omega (1+\alpha ))=\varphi _{2}(\alpha )}$ ${\displaystyle \alpha \leq \varphi _{3}(0)=\eta _{0}}$ ${\displaystyle \varphi _{2}}$ ${\displaystyle \varphi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }}$ ${\displaystyle \varphi _{3}(0)}$ ${\displaystyle \varphi _{2}}$ ${\displaystyle \psi (\Omega ^{2})=\varphi _{3}(0)}$

Nuevamente, podemos ver que durante algún tiempo: esto sigue siendo cierto hasta el primer punto fijo de , que es el ordinal de Feferman–Schütte . Por lo tanto, es el ordinal de Feferman–Schütte. ${\displaystyle \psi (\Omega ^{\alpha })=\varphi _{1+\alpha }(0)}$ ${\displaystyle \Gamma _{0}}$ ${\displaystyle \alpha \mapsto \varphi _{\alpha }(0)}$ ${\displaystyle \psi (\Omega ^{\Omega })=\Gamma _{0}}$

Más allá del ordinal Feferman-Schütte

Tenemos para todos donde es el siguiente punto fijo de . Entonces, si enumera los puntos fijos en cuestión (que también se pueden notar usando las funciones de Veblen multivaluadas) tenemos , hasta el primer punto fijo de la misma, que será (y el primer punto fijo de las funciones será ). De esta manera: ${\displaystyle \psi (\Omega ^{\Omega }+\Omega ^{\alpha })=\varphi _{\Gamma _{0}+\alpha }(0)}$ ${\displaystyle \alpha \leq \Gamma _{1}}$ ${\displaystyle \Gamma _{1}}$ ${\displaystyle \alpha \mapsto \varphi _{\alpha }(0)}$ ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$ ${\displaystyle \varphi (1,0,\alpha )}$ ${\displaystyle \psi (\Omega ^{\Omega }(1+\alpha ))=\Gamma _{\alpha }}$ ${\displaystyle \varphi (1,1,0)}$ ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$ ${\displaystyle \psi (\Omega ^{\Omega +1})}$ ${\displaystyle \varphi (2,0,0)}$ ${\displaystyle \alpha \mapsto \varphi (1,\alpha ,0)}$ ${\displaystyle \psi (\Omega ^{\Omega \cdot 2})}$

• ${\displaystyle \psi (\Omega ^{\Omega ^{2}})}$es el ordinal de Ackermann (el rango de la notación definida predicativamente), ${\displaystyle \varphi (\alpha ,\beta ,\gamma )}$
• ${\displaystyle \psi (\Omega ^{\Omega ^{\omega }})}$es el ordinal de Veblen "pequeño" (el rango de las notaciones que utilizan de manera predicativa un número finito de variables), ${\displaystyle \varphi (\cdot )}$
• ${\displaystyle \psi (\Omega ^{\Omega ^{\Omega }})}$es el ordinal de Veblen "grande" (el rango de las notaciones que utilizan de forma predicativa un número transfinito pero predicativamente numeroso de variables), ${\displaystyle \varphi (\cdot )}$
• el límite de , , , etc., es el ordinal de Bachmann–Howard : después de esto nuestra función es constante y no podemos ir más allá con la definición que hemos dado. ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega ^{\Omega })}$ ${\displaystyle \psi (\Omega ^{\Omega ^{\Omega }})}$ ${\displaystyle \psi }$

Notaciones ordinales hasta el ordinal de Bachmann-Howard

Ahora explicamos de forma más sistemática cómo la función define notaciones para ordinales hasta el ordinal de Bachmann-Howard. ${\displaystyle \psi }$

Una nota sobre las representaciones base

Recordemos que si es un ordinal que es una potencia de (por ejemplo, él mismo, o , o ), cualquier ordinal puede expresarse de forma única en la forma , donde es un número natural, son ordinales distintos de cero menores que , y son números ordinales (permitimos ). Esta " representación base" es una generalización obvia de la forma normal de Cantor (que es el caso ). Por supuesto, puede muy bien ser que la expresión no sea interesante, es decir, , pero en cualquier otro caso los deben ser todos menores que ; también puede ser el caso de que la expresión sea trivial (es decir, , en cuyo caso y ). ${\displaystyle \delta }$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$ ${\displaystyle \delta ^{\beta _{1}}\gamma _{1}+\ldots +\delta ^{\beta _{k}}\gamma _{k}}$ ${\displaystyle k}$ ${\displaystyle \gamma _{1},\ldots ,\gamma _{k}}$ ${\displaystyle \delta }$ ${\displaystyle \beta _{1}>\beta _{2}>\cdots >\beta _{k}}$ ${\displaystyle \beta _{k}=0}$ ${\displaystyle \delta }$ ${\displaystyle \delta =\omega }$ ${\displaystyle \alpha =\delta ^{\alpha }}$ ${\displaystyle \beta _{i}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha <\delta }$ ${\displaystyle k\leq 1}$ ${\displaystyle \gamma _{1}=\alpha }$

Si es un ordinal menor que , entonces su representación base tiene coeficientes (por definición) y exponentes (debido al supuesto ): por lo tanto, uno puede reescribir estos exponentes en base y repetir la operación hasta que el proceso termine (cualquier secuencia decreciente de ordinales es finita). Llamamos a la expresión resultante la representación base iterada de y los diversos coeficientes involucrados (incluidos los exponentes) las partes de la representación (son todos ), o, para abreviar, las -partes de . ${\displaystyle \alpha }$ ${\displaystyle \varepsilon _{\Omega +1}}$ ${\displaystyle \Omega }$ ${\displaystyle \gamma _{i}<\Omega }$ ${\displaystyle \beta _{i}<\alpha }$ ${\displaystyle \alpha <\varepsilon _{\Omega +1}}$ ${\displaystyle \Omega }$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$ ${\displaystyle <\Omega }$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$

Algunas propiedades deψ

• La función es no decreciente y continua (esto es más o menos obvio a partir de su definición). ${\displaystyle \psi }$
• Si con entonces necesariamente . En efecto, ningún ordinal con puede pertenecer a (de lo contrario su imagen por , que es pertenecería a — imposible); por lo tanto está cerrado por todo bajo el cual está la clausura, por lo que son iguales. ${\displaystyle \psi (\alpha )=\psi (\beta )}$ ${\displaystyle \beta <\alpha }$ ${\displaystyle C(\alpha )=C(\beta )}$ ${\displaystyle \beta '}$ ${\displaystyle \beta \leq \beta '<\alpha }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \psi }$ ${\displaystyle \psi (\alpha )}$ ${\displaystyle C(\alpha )}$ ${\displaystyle C(\beta )}$ ${\displaystyle C(\alpha )}$
• Cualquier valor tomado por es un -número (es decir, un punto fijo de ). De hecho, si no lo fuera, entonces al escribirlo en forma normal de Cantor , podría expresarse utilizando sumas, productos y exponenciación a partir de elementos menores que él, por lo tanto en , por lo que estaría en , una contradicción. ${\displaystyle \gamma =\psi (\alpha )}$ ${\displaystyle \psi }$ ${\displaystyle \varepsilon }$ ${\displaystyle \beta \mapsto \omega ^{\beta }}$ ${\displaystyle C(\alpha )}$ ${\displaystyle C(\alpha )}$
• Lema: Supóngase que es un -número y un ordinal tal que para todo : entonces los -elementos (definidos arriba) de cualquier elemento de son menores que . En efecto, sea el conjunto de ordinales cuyos -elementos son todos menores que . Entonces es cerrado bajo adición, multiplicación y exponenciación (porque es un -número, por lo que los ordinales menores que él son cerrados bajo adición, multiplicación y exponenciación). Y también contiene todo para por suposición, y contiene , , , . Por lo tanto , lo cual se iba a demostrar. ${\displaystyle \delta }$ ${\displaystyle \varepsilon }$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\beta )<\delta }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \Omega }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \delta }$ ${\displaystyle C'}$ ${\displaystyle \Omega }$ ${\displaystyle \delta }$ ${\displaystyle C'}$ ${\displaystyle \delta }$ ${\displaystyle \varepsilon }$ ${\displaystyle C'}$ ${\displaystyle \psi (\beta )}$ ${\displaystyle \beta <\alpha }$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle C'\supseteq C(\alpha )}$
• Bajo la hipótesis del lema anterior, (de hecho, el lema muestra que ). ${\displaystyle \psi (\alpha )\leq \delta }$ ${\displaystyle \delta \not \in C(\alpha )}$
• Cualquier número menor que algún elemento en el rango de está en sí mismo en el rango de (es decir, no omite ningún número). En efecto: si es un número no mayor que el rango de , sea el límite superior mínimo de tal que : entonces por lo anterior tenemos , pero contradeciría el hecho de que es el límite superior mínimo — por lo tanto . ${\displaystyle \varepsilon }$ ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle \varepsilon }$ ${\displaystyle \delta }$ ${\displaystyle \varepsilon }$ ${\displaystyle \psi }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \psi (\beta )<\delta }$ ${\displaystyle \psi (\alpha )\leq \delta }$ ${\displaystyle \psi (\alpha )<\delta }$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\alpha )=\delta }$
• Siempre que , el conjunto consta exactamente de aquellos ordinales (menores que ) cuyos -fragmentos son todos menores que . En efecto, sabemos que todos los ordinales menores que , por lo tanto, todos los ordinales (menores que ) cuyos -fragmentos son menores que , están en . Por el contrario, si suponemos para todos (en otras palabras, si es el menor posible con ), el lema da la propiedad deseada. Por otro lado, si para algunos , entonces ya hemos señalado y podemos reemplazar por el menor posible con . ${\displaystyle \psi (\alpha )=\delta }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \gamma }$ ${\displaystyle \varepsilon _{\Omega +1}}$ ${\displaystyle \Omega }$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \varepsilon _{\Omega +1}}$ ${\displaystyle \Omega }$ ${\displaystyle \delta }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \psi (\beta )<\delta }$ ${\displaystyle \beta <\alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\alpha )=\delta }$ ${\displaystyle \psi (\alpha )=\psi (\beta )}$ ${\displaystyle \beta <\alpha }$ ${\displaystyle C(\alpha )=C(\beta )}$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\alpha )=\delta }$

La notación ordinal

Utilizando los datos anteriores, podemos definir una notación ordinal (canónica) para todo número menor que el ordinal de Bachmann-Howard. Lo hacemos por inducción en . ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Si es menor que , usamos la forma normal iterada de Cantor de . De lo contrario, existe un número mayor menor o igual a (esto se debe a que el conjunto de números es cerrado): si entonces por inducción hemos definido una notación para y la representación base de da una para , por lo que hemos terminado. ${\displaystyle \gamma }$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \gamma }$ ${\displaystyle \varepsilon }$ ${\displaystyle \delta }$ ${\displaystyle \gamma }$ ${\displaystyle \varepsilon }$ ${\displaystyle \delta <\gamma }$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Queda por tratar el caso donde es un -número: hemos argumentado que, en este caso, podemos escribir para algún ordinal (posiblemente incontable) : sea el mayor ordinal posible (que existe ya que es continuo). Usamos la representación base iterada de : queda por demostrar que cada parte de esta representación es menor que (por lo que ya hemos definido una notación para ella). Si este no es el caso, entonces, por las propiedades que hemos demostrado, no contiene a ; pero entonces (están cerrados bajo las mismas operaciones, ya que el valor de at nunca puede tomarse), por lo que , contradiciendo la maximalidad de . ${\displaystyle \gamma =\delta }$ ${\displaystyle \varepsilon }$ ${\displaystyle \delta =\psi (\alpha )}$ ${\displaystyle \alpha <\varepsilon _{\Omega +1}}$ ${\displaystyle \alpha }$ ${\displaystyle \psi }$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$ ${\displaystyle \delta }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle C(\alpha +1)=C(\alpha )}$ ${\displaystyle \psi }$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\alpha +1)=\psi (\alpha )=\delta }$ ${\displaystyle \alpha }$

Nota : En realidad, hemos definido notaciones canónicas no sólo para ordinales inferiores al ordinal de Bachmann-Howard, sino también para ciertos ordinales incontables, es decir, aquellos cuyos fragmentos son menores que el ordinal de Bachmann-Howard (es decir: escríbalos en representación de base iterada y use la representación canónica para cada fragmento). Esta notación canónica se usa para argumentos de la función (que pueden ser incontables). ${\displaystyle \Omega }$ ${\displaystyle \Omega }$ ${\displaystyle \psi }$

Ejemplos

Para ordinales menores que , la notación ordinal canónica definida coincide con la forma normal de Cantor iterada (por definición). ${\displaystyle \varepsilon _{0}=\psi (0)}$

Para los ordinales menores que , la notación coincide con la notación base iterada (las partes se escriben en forma normal de Cantor iterada): p. ej., se escribirá , o, más precisamente, . Para los ordinales menores que , escribimos de manera similar en base iterada y luego escribimos las partes en base iterada (y escribimos las partes de esta en forma normal de Cantor iterada): entonces se escribe , o, más exactamente, . Por lo tanto, hasta , siempre usamos la base de números más grande posible que da una representación no trivial. ${\displaystyle \varepsilon _{1}=\psi (1)}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \omega ^{\omega ^{\varepsilon _{0}+\omega }}}$ ${\displaystyle {\varepsilon _{0}}^{\omega ^{\omega }}}$ ${\displaystyle \psi (0)^{\omega ^{\omega }}}$ ${\displaystyle \varepsilon _{2}=\psi (2)}$ ${\displaystyle \varepsilon _{1}}$ ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \omega ^{\omega ^{\varepsilon _{1}+\varepsilon _{0}+1}}}$ ${\displaystyle {\varepsilon _{1}}^{\varepsilon _{0}\omega }}$ ${\displaystyle \psi (1)^{\psi (0)\,\omega }}$ ${\displaystyle \zeta _{0}=\psi (\Omega )}$ ${\displaystyle \varepsilon }$

Más allá de esto, es posible que necesitemos expresar ordinales más allá de : esto siempre se hace en base iterada, y las piezas mismas deben expresarse utilizando la base de número más grande posible, lo que da una representación no trivial. ${\displaystyle \Omega }$ ${\displaystyle \Omega }$ ${\displaystyle \varepsilon }$

Tenga en cuenta que aunque es igual al ordinal de Bachmann-Howard, esta no es una "notación canónica" en el sentido que hemos definido (las notaciones canónicas se definen solo para ordinales menores que el ordinal de Bachmann-Howard). ${\displaystyle \psi (\varepsilon _{\Omega +1})}$

Condiciones para la canonicidad

Las notaciones así definidas tienen la propiedad de que siempre que aniden funciones, los argumentos de la función "interna" son siempre menores que los de la "externa" (esto es una consecuencia del hecho de que las partes de , donde es el mayor posible tal que para algún número , son todas menores que , como hemos demostrado anteriormente). Por ejemplo, no aparece como una notación: es una expresión bien definida (y es igual a ya que es constante entre y ), pero no es una notación producida por el algoritmo inductivo que hemos esbozado. ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\alpha )=\delta }$ ${\displaystyle \varepsilon }$ ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \psi (\psi (\Omega )+1)}$ ${\displaystyle \psi (\Omega )=\zeta _{0}}$ ${\displaystyle \psi }$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \Omega }$

La canonicidad se puede comprobar recursivamente: una expresión es canónica si y solo si es la forma normal de Cantor iterada de un ordinal menor que , o una representación base iterada cuyas partes son todas canónicas, ya que algún donde está escrito en representación base iterada cuyas partes son todas canónicas y menores que . El orden se comprueba mediante verificación lexicográfica en todos los niveles (teniendo en cuenta que es mayor que cualquier expresión obtenida por , y para valores canónicos el mayor siempre triunfa sobre el menor o incluso sumas, productos y exponentes arbitrarios del menor). ${\displaystyle \varepsilon _{0}}$ ${\displaystyle \delta }$ ${\displaystyle \delta =\psi (\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \Omega }$ ${\displaystyle \delta }$ ${\displaystyle \Omega }$ ${\displaystyle \psi }$ ${\displaystyle \psi }$

Por ejemplo, es una notación canónica para un ordinal que es menor que el ordinal de Feferman–Schütte: se puede escribir usando las funciones de Veblen como . ${\displaystyle \psi (\Omega ^{\omega +1}\,\psi (\Omega )+\psi (\Omega ^{\omega })^{\psi (\Omega ^{2})}42)^{\psi (1729)\,\omega }}$ ${\displaystyle \varphi _{1}(\varphi _{\omega +1}(\varphi _{2}(0))+\varphi _{\omega }(0)^{\varphi _{3}(0)}42)^{\varphi _{1}(1729)\,\omega }}$

En cuanto al orden, se podría señalar que (el ordinal de Feferman–Schütte) es mucho más que (porque es mayor que cualquier cosa), y es en sí mismo mucho más que (porque es mayor que , por lo que cualquier expresión suma-producto-o-exponencial que involucre un valor menor seguirá siendo menor que ). De hecho, ya es menor que . ${\displaystyle \psi (\Omega ^{\Omega })}$ ${\displaystyle \psi (\Omega ^{\psi (\Omega )})=\varphi _{\varphi _{2}(0)}(0)}$ ${\displaystyle \Omega }$ ${\displaystyle \psi }$ ${\displaystyle \psi (\Omega ^{\psi (\Omega )})=\varphi _{\varphi _{2}(0)}(0)}$ ${\displaystyle \psi (\Omega )^{\psi (\Omega )}=\varphi _{2}(0)^{\varphi _{2}(0)}}$ ${\displaystyle \Omega ^{\psi (\Omega )}}$ ${\displaystyle \Omega }$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega ^{\Omega })}$ ${\displaystyle \psi (\Omega )^{\psi (\Omega )}}$ ${\displaystyle \psi (\Omega +1)}$

Secuencias estándar para notaciones ordinales

Para atestiguar el hecho de que hemos definido notaciones para ordinales inferiores al ordinal de Bachmann–Howard (que son todos de cofinalidad contable ), podríamos definir sucesiones estándar que converjan a cualquiera de ellos (siempre que sea un ordinal límite, por supuesto). En realidad, también definiremos sucesiones canónicas para ciertos ordinales incontables, a saber, los ordinales incontables de cofinalidad contable (si esperamos definir una sucesión que converja a ellos...) que sean representables (es decir, todos cuyos fragmentos sean menores que el ordinal de Bachmann–Howard). ${\displaystyle \Omega }$

Las siguientes reglas son más o menos obvias, excepto la última:

• Primero, deshágase de las representaciones base (iteradas): para definir una secuencia estándar que converge a , donde es o (o , pero vea a continuación): ${\displaystyle \delta }$ ${\displaystyle \alpha =\delta ^{\beta _{1}}\gamma _{1}+\cdots +\delta ^{\beta _{k}}\gamma _{k}}$ ${\displaystyle \delta }$ ${\displaystyle \omega }$ ${\displaystyle \psi (\cdots )}$ ${\displaystyle \Omega }$
  • si es cero entonces y no hay nada que hacer; ${\displaystyle k}$ ${\displaystyle \alpha =0}$
  • si es cero y es sucesor, entonces es sucesor y no hay nada que hacer; ${\displaystyle \beta _{k}}$ ${\displaystyle \gamma _{k}}$ ${\displaystyle \alpha }$
  • si es límite, tomar la secuencia estándar que converge a y reemplazar en la expresión por los elementos de esa secuencia; ${\displaystyle \gamma _{k}}$ ${\displaystyle \gamma _{k}}$ ${\displaystyle \gamma _{k}}$
  • si es sucesor y es límite, reescribe el último término como y reemplaza el exponente en el último término por los elementos de la secuencia fundamental que convergen a él; ${\displaystyle \gamma _{k}}$ ${\displaystyle \beta _{k}}$ ${\displaystyle \delta ^{\beta _{k}}\gamma _{k}}$ ${\displaystyle \delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}}}$ ${\displaystyle \beta _{k}}$
  • si es sucesor y es también, reescribe el último término como y reemplaza el último en esta expresión por los elementos de la secuencia fundamental que convergen a él. ${\displaystyle \gamma _{k}}$ ${\displaystyle \beta _{k}}$ ${\displaystyle \delta ^{\beta _{k}}\gamma _{k}}$ ${\displaystyle \delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}-1}\delta }$ ${\displaystyle \delta }$
• Si es , entonces tome lo obvio como la secuencia fundamental para . ${\displaystyle \delta }$ ${\displaystyle \omega }$ ${\displaystyle 0,1,2,3,\ldots }$ ${\displaystyle \delta }$
• Si entonces tomamos como secuencia fundamental para la secuencia ${\displaystyle \delta =\psi (0)}$ ${\displaystyle \delta }$ ${\displaystyle \omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\ldots }$
• Si entonces tomamos como secuencia fundamental para la secuencia ${\displaystyle \delta =\psi (\alpha +1)}$ ${\displaystyle \delta }$ ${\displaystyle \psi (\alpha ),\psi (\alpha )^{\psi (\alpha )},\psi (\alpha )^{\psi (\alpha )^{\psi (\alpha )}},\ldots }$
• Si donde es un ordinal límite de cofinalidad contable , defina la secuencia estándar para que se obtendrá aplicando a la secuencia estándar para (recuerde que es continua y creciente, aquí). ${\displaystyle \delta =\psi (\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \delta }$ ${\displaystyle \psi }$ ${\displaystyle \alpha }$ ${\displaystyle \psi }$
• Queda por manejar el caso donde con un ordinal de cofinalidad incontable (por ejemplo, él mismo). Obviamente no tiene sentido definir una secuencia que converge a en este caso; sin embargo, lo que podemos definir es una secuencia que converge a algún con cofinalidad contable y tal que es constante entre y . Este será el primer punto fijo de una cierta función (continua y no decreciente) . Para encontrarlo, aplique las mismas reglas (de la representación base de ) que para encontrar la secuencia canónica de , excepto que siempre que se requiera una secuencia que converge a (algo que no puede existir), reemplace el en cuestión, en la expresión de , por un (donde es una variable) y realice una iteración repetida (empezando por , digamos) de la función : esto da una secuencia que tiende a , y la secuencia canónica para es , , ... Si dejamos que el elemento n.º (que comienza en ) de la secuencia fundamental para se denote como , entonces podemos expresar esto más claramente usando la recursión. Con esta notación, podemos ver esto con bastante facilidad. Podemos definir el resto de la secuencia mediante recursión: . (Los ejemplos a continuación deberían aclarar esto). ${\displaystyle \delta =\psi (\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$ ${\displaystyle \rho <\alpha }$ ${\displaystyle \psi }$ ${\displaystyle \rho }$ ${\displaystyle \alpha }$ ${\displaystyle \rho }$ ${\displaystyle \xi \mapsto h(\psi (\xi ))}$ ${\displaystyle \Omega }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \Omega }$ ${\displaystyle \Omega }$ ${\displaystyle \alpha =h(\Omega )}$ ${\displaystyle \psi (\xi )}$ ${\displaystyle \xi }$ ${\displaystyle 0}$ ${\displaystyle \xi \mapsto h(\psi (\xi ))}$ ${\displaystyle 0,h(\psi (0)),h(\psi (h(\psi (0)))),\ldots }$ ${\displaystyle \rho }$ ${\displaystyle \psi (\alpha )=\psi (\rho )}$ ${\displaystyle \psi (0)}$ ${\displaystyle \psi (h(\psi (0)))}$ ${\displaystyle \psi (h(\psi (h(\psi (0)))))}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle \delta }$ ${\displaystyle \delta [n]}$ ${\displaystyle \delta [0]=\psi (0)}$ ${\displaystyle \delta [n]=\psi (h(\delta [n-1]))}$

A continuación se muestran algunos ejemplos del último caso (y el más interesante):

• La secuencia canónica para es: , , ... Esto de hecho converge a después de lo cual es constante hasta . ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (0)}$ ${\displaystyle \psi (\psi (0))}$ ${\displaystyle \psi (\psi (\psi (0)))}$ ${\displaystyle \rho =\psi (\Omega )=\zeta _{0}}$ ${\displaystyle \psi }$ ${\displaystyle \Omega }$
• La secuencia canónica para es: , , Esto de hecho converge al valor de en después del cual es constante hasta . ${\displaystyle \psi (\Omega 2)}$ ${\displaystyle \psi (0)}$ ${\displaystyle \psi (\Omega +\psi (0))}$ ${\displaystyle \psi (\Omega +\psi (\Omega +\psi (0))),\ldots }$ ${\displaystyle \psi }$ ${\displaystyle \rho =\Omega +\psi (\Omega 2)=\Omega +\zeta _{1}}$ ${\displaystyle \psi }$ ${\displaystyle \Omega 2}$
• La secuencia canónica para es: Esto converge al valor de en . ${\displaystyle \psi (\Omega ^{2})}$ ${\displaystyle \psi (0),\psi (\Omega \psi (0)),\psi (\Omega \psi (\Omega \psi (0))),\ldots }$ ${\displaystyle \psi }$ ${\displaystyle \rho =\Omega \psi (\Omega ^{2})}$
• La secuencia canónica para es Esta converge al valor de en . ${\displaystyle \psi (\Omega ^{2}3+\Omega )}$ ${\displaystyle \psi (0),\psi (\Omega ^{2}3+\psi (0)),\psi (\Omega ^{2}3+\psi (\Omega ^{2}3+\psi (0))),\ldots }$ ${\displaystyle \psi }$ ${\displaystyle \rho =\Omega ^{2}3+\psi (\Omega ^{2}3+\Omega )}$
• La secuencia canónica para es: Esto converge al valor de en . ${\displaystyle \psi (\Omega ^{\Omega })}$ ${\displaystyle \psi (0),\psi (\Omega ^{\psi (0)}),\psi (\Omega ^{\psi (\Omega ^{\psi (0)})}),\ldots }$ ${\displaystyle \psi }$ ${\displaystyle \rho =\Omega ^{\psi (\Omega ^{\Omega })}}$
• La secuencia canónica para es: Esto converge al valor de en . ${\displaystyle \psi (\Omega ^{\Omega }3)}$ ${\displaystyle \psi (0),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)}),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)})}),\ldots }$ ${\displaystyle \psi }$ ${\displaystyle \rho =\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }3)}}$
• La secuencia canónica para es: Esto converge al valor de en . ${\displaystyle \psi (\Omega ^{\Omega +1})}$ ${\displaystyle \psi (0),\psi (\Omega ^{\Omega }\psi (0)),\psi (\Omega ^{\Omega }\psi (\Omega ^{\Omega }\psi (0))),\ldots }$ ${\displaystyle \psi }$ ${\displaystyle \rho =\Omega ^{\Omega }\psi (\Omega ^{\Omega +1})}$
• La secuencia canónica para es: ${\displaystyle \psi (\Omega ^{\Omega ^{2}+\Omega 3})}$ ${\displaystyle \psi (0),\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)}),\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)})}),\ldots }$

A continuación se muestran algunos ejemplos de otros casos:

• La secuencia canónica para es: , , , ... ${\displaystyle \omega ^{2}}$ ${\displaystyle 0}$ ${\displaystyle \omega }$ ${\displaystyle \omega 2}$ ${\displaystyle \omega 3}$
• La secuencia canónica para es: , , , ... ${\displaystyle \psi (\omega ^{\omega })}$ ${\displaystyle \psi (1)}$ ${\displaystyle \psi (\omega )}$ ${\displaystyle \psi (\omega ^{2})}$ ${\displaystyle \psi (\omega ^{3})}$
• La secuencia canónica para es: , , , ... ${\displaystyle \psi (\Omega )^{\omega }}$ ${\displaystyle 1}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega )^{2}}$ ${\displaystyle \psi (\Omega )^{3}}$
• La secuencia canónica para es: , , ... ${\displaystyle \psi (\Omega +1)}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega )^{\psi (\Omega )}}$ ${\displaystyle \psi (\Omega )^{\psi (\Omega )^{\psi (\Omega )}}}$
• La secuencia canónica para es: , , , ... ${\displaystyle \psi (\Omega +\omega )}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega +1)}$ ${\displaystyle \psi (\Omega +2)}$ ${\displaystyle \psi (\Omega +3)}$
• La secuencia canónica para es: , , , ... ${\displaystyle \psi (\Omega \omega )}$ ${\displaystyle \psi (0)}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega 2)}$ ${\displaystyle \psi (\Omega 3)}$
• La secuencia canónica para es: , , , ... ${\displaystyle \psi (\Omega ^{\omega })}$ ${\displaystyle \psi (1)}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega ^{2})}$ ${\displaystyle \psi (\Omega ^{3})}$
• La secuencia canónica para es: , , ... (esta se deriva de la secuencia fundamental para ). ${\displaystyle \psi (\Omega ^{\psi (0)})}$ ${\displaystyle \psi (\Omega ^{\omega })}$ ${\displaystyle \psi (\Omega ^{\omega ^{\omega }})}$ ${\displaystyle \psi (\Omega ^{\omega ^{\omega ^{\omega }}})}$ ${\displaystyle \psi (0)}$
• La secuencia canónica para es: , , ... (esto se deriva de la secuencia fundamental para , que se dio anteriormente). ${\displaystyle \psi (\Omega ^{\psi (\Omega )})}$ ${\displaystyle \psi (\Omega ^{\psi (0)})}$ ${\displaystyle \psi (\Omega ^{\psi (\psi (0))})}$ ${\displaystyle \psi (\Omega ^{\psi (\psi (\psi (0)))})}$ ${\displaystyle \psi (\Omega )}$

Aunque el ordinal Bachmann-Howard en sí no tiene notación canónica, también es útil definir una secuencia canónica para él: esta es , , ... ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi (\Omega ^{\Omega })}$ ${\displaystyle \psi (\Omega ^{\Omega ^{\Omega }})}$

Un proceso de terminación

Comience con cualquier ordinal menor o igual al ordinal de Bachmann-Howard y repita el siguiente proceso siempre que no sea cero:

• si el ordinal es sucesor, restar uno (es decir, reemplazarlo por su predecesor),
• si es un límite, reemplácelo por algún elemento de la secuencia canónica definida para él.

Entonces es cierto que este proceso siempre termina (ya que cualquier secuencia decreciente de ordinales es finita); sin embargo, como (pero incluso más que para) el juego de la hidra :

1. Puede tardar mucho tiempo en terminarse,
2. La prueba de la terminación puede estar fuera del alcance de ciertos sistemas débiles de aritmética.

Para dar una idea de cómo es el proceso, aquí se muestran algunos pasos: comenzando desde (el ordinal Veblen pequeño), podríamos bajar a , de allí a , luego luego luego luego luego luego luego y así sucesivamente. Parece como si las expresiones se fueran haciendo cada vez más complicadas mientras que, de hecho, los ordinales siempre disminuyen. ${\displaystyle \psi (\Omega ^{\Omega ^{\omega }})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{3}})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}\psi (0)})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{\omega }})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{3}})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{2}3})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+\omega )})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+1)})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (0)})})}$ ${\displaystyle \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \omega ^{\omega ^{\omega }}})})}$

En cuanto a la primera afirmación, se podría introducir, para cualquier ordinal menor o igual al ordinal de Bachmann-Howard , la función entera que cuenta el número de pasos del proceso antes de la terminación si uno siempre selecciona el 'ésimo elemento de la secuencia canónica (esta función satisface la identidad ). Entonces puede ser una función de crecimiento muy rápido: ya es esencialmente , la función es comparable con la función de Ackermann , y es comparable con la función de Goodstein . Si en cambio hacemos una función que satisface la identidad , de modo que el índice de la función aumenta si se aplica, entonces creamos una función de crecimiento mucho más rápido: ya es comparable a la función de Goodstein, y es comparable a la función TREE . ${\displaystyle \alpha }$ ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ ${\displaystyle f_{\alpha }(n)}$ ${\displaystyle n}$ ${\displaystyle f_{\alpha }(n)=f_{\alpha [n]}(n)+1}$ ${\displaystyle f_{\alpha }}$ ${\displaystyle f_{\omega ^{\omega }}(n)}$ ${\displaystyle n^{n}}$ ${\displaystyle f_{\psi (\Omega ^{\omega })}(n)}$ ${\displaystyle A(n,n)}$ ${\displaystyle f_{\psi (\varepsilon _{\Omega +1})}(n)}$ ${\displaystyle g_{\alpha }(n)=g_{\alpha [n]}(n+1)+1}$ ${\displaystyle g_{\psi (0)}(n)}$ ${\displaystyle g_{\psi (\Omega ^{\Omega ^{\omega }\omega })}(n)}$

En cuanto a la segunda afirmación, el análisis ordinal nos da una versión precisa : por ejemplo, la teoría de conjuntos de Kripke-Platek puede demostrar ^[4] que el proceso termina para cualquier número dado menor que el ordinal de Bachmann-Howard, pero no puede hacerlo de manera uniforme, es decir, no puede demostrar la terminación a partir del ordinal de Bachmann-Howard. Algunas teorías, como la aritmética de Peano, están limitadas por ordinales mucho más pequeños ( en el caso de la aritmética de Peano). ${\displaystyle \alpha }$ ${\displaystyle \varepsilon _{0}}$

Variaciones sobre el ejemplo

Realizando la funciónmenospoderoso

Es instructivo (aunque no precisamente útil) hacerlo menos poderoso. ${\displaystyle \psi }$

Si alteramos la definición de anterior para omitir la exponenciación del repertorio a partir del cual se construye, entonces obtenemos (ya que este es el ordinal más pequeño que no se puede construir a partir de , y usando solo adición y multiplicación), entonces y de manera similar , hasta que llegamos a un punto fijo que entonces es nuestro . Entonces tenemos y así sucesivamente hasta . Dado que la multiplicación de 's está permitida, todavía podemos formar y y así sucesivamente, pero nuestra construcción termina allí ya que no hay forma de llegar a o más allá de : por lo que el rango de este sistema debilitado de notación es (el valor de es el mismo en nuestro sistema más débil que en nuestro sistema original, excepto que ahora no podemos ir más allá de él). Esto ni siquiera llega tan lejos como el ordinal de Feferman-Schütte. ${\displaystyle \psi }$ ${\displaystyle C(\alpha )}$ ${\displaystyle \psi (0)=\omega ^{\omega }}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \psi (1)=\omega ^{\omega ^{2}}}$ ${\displaystyle \psi (\omega )=\omega ^{\omega ^{\omega }}}$ ${\displaystyle \psi (\psi (0))=\omega ^{\omega ^{\omega ^{\omega }}}}$ ${\displaystyle \psi (\Omega )=\varepsilon _{0}}$ ${\displaystyle \psi (\Omega +1)={\varepsilon _{0}}^{\omega }}$ ${\displaystyle \psi (\Omega 2)=\varepsilon _{1}}$ ${\displaystyle \Omega }$ ${\displaystyle \psi (\Omega ^{2})=\varphi _{2}(0)}$ ${\displaystyle \psi (\Omega ^{3})=\varphi _{3}(0)}$ ${\displaystyle \Omega ^{\omega }}$ ${\displaystyle \psi (\Omega ^{\omega })=\phi _{\omega }(0)}$ ${\displaystyle \psi (\Omega ^{\omega })}$

Si modificamos la definición de todavía algo más para permitir solo la adición como primitiva para la construcción, obtenemos y y así sucesivamente hasta y todavía . Esta vez, y así sucesivamente hasta y de manera similar . Pero esta vez no podemos ir más allá: dado que solo podemos agregar , el rango de nuestro sistema es . ${\displaystyle \psi }$ ${\displaystyle \psi (0)=\omega ^{2}}$ ${\displaystyle \psi (1)=\omega ^{3}}$ ${\displaystyle \psi (\psi (0))=\omega ^{\omega ^{2}}}$ ${\displaystyle \psi (\Omega )=\varepsilon _{0}}$ ${\displaystyle \psi (\Omega +1)=\varepsilon _{0}\omega }$ ${\displaystyle \psi (\Omega 2)=\varepsilon _{1}}$ ${\displaystyle \psi (\Omega 3)=\varepsilon _{2}}$ ${\displaystyle \Omega }$ ${\displaystyle \psi (\Omega \omega )=\varepsilon _{\omega }=\varphi _{1}(\omega )}$

Si modificamos aún más la definición, para no permitir nada excepto psi, obtenemos , , y así sucesivamente hasta , , y , en cuyo punto no podemos ir más allá ya que no podemos hacer nada con los . Por lo tanto, el rango de este sistema es solo . ${\displaystyle \psi (0)=1}$ ${\displaystyle \psi (\psi (0))=2}$ ${\displaystyle \psi (\omega )=\omega +1}$ ${\displaystyle \psi (\psi (\omega ))=\omega +2}$ ${\displaystyle \psi (\Omega )=\omega 2}$ ${\displaystyle \Omega }$ ${\displaystyle \omega 2}$

En ambos casos, encontramos que la limitación de la función debilitada no proviene tanto de las operaciones permitidas sobre los ordinales contables como de los ordinales incontables que nos permitimos denotar. ${\displaystyle \psi }$

Más allá del ordinal de Bachmann-Howard

Sabemos que es el ordinal de Bachmann-Howard. La razón por la que no es mayor, con nuestras definiciones, es que no hay notación para (no pertenece a ningún , siempre es el límite superior mínimo de este). Se podría intentar añadir la función (o las funciones de Veblen de tantas variables) a los primitivos permitidos más allá de la suma, la multiplicación y la exponenciación, pero eso no nos lleva muy lejos. Para crear notaciones más sistemáticas para ordinales contables, necesitamos notaciones más sistemáticas para ordinales incontables: no podemos usar la función en sí misma porque solo produce ordinales contables (por ejemplo, es, , ciertamente no ), por lo que la idea es imitar su definición de la siguiente manera: ${\displaystyle \psi (\varepsilon _{\Omega +1})}$ ${\displaystyle \psi (\varepsilon _{\Omega +1}+1)}$ ${\displaystyle \varepsilon _{\Omega +1}}$ ${\displaystyle C(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \varepsilon }$ ${\displaystyle \psi }$ ${\displaystyle \psi (\Omega +1)}$ ${\displaystyle \varepsilon _{\varphi _{2}(0)+1}}$ ${\displaystyle \varepsilon _{\Omega +1}}$

Sea el ordinal más pequeño que no puede expresarse a partir de todos los ordinales contables y utilizando sumas, productos, exponenciales y la función misma (hasta ordinales previamente construidos menores que ). ${\displaystyle \psi _{1}(\alpha )}$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi _{1}}$ ${\displaystyle \alpha }$

Aquí, se garantiza que un nuevo ordinal será mayor que todos los ordinales que se construirán usando : nuevamente, dejando que y funcionen. ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi _{1}}$ ${\displaystyle \Omega =\omega _{1}}$ ${\displaystyle \Omega _{2}=\omega _{2}}$

Por ejemplo, , y de manera más general para todos los ordinales contables e incluso más allá ( y ): esto se cumple hasta el primer punto fijo de la función más allá de , que es el límite de , y así sucesivamente. Más allá de esto, tenemos y esto sigue siendo cierto hasta que : exactamente como fue el caso para , tenemos y . ${\displaystyle \psi _{1}(0)=\Omega }$ ${\displaystyle \psi _{1}(\alpha )=\varepsilon _{\Omega +\alpha }}$ ${\displaystyle \psi _{1}(\Omega )=\psi _{1}(\psi _{1}(0))=\varepsilon _{\Omega 2}}$ ${\displaystyle \psi _{1}(\psi _{1}(1))=\varepsilon _{\varepsilon _{\Omega +1}}}$ ${\displaystyle \zeta _{\Omega +1}}$ ${\displaystyle \xi \mapsto \varepsilon _{\xi }}$ ${\displaystyle \Omega }$ ${\displaystyle \psi _{1}(0)}$ ${\displaystyle \psi _{1}(\psi _{1}(0))}$ ${\displaystyle \psi _{1}(\alpha )=\zeta _{\Omega +1}}$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi (\Omega )}$ ${\displaystyle \psi _{1}(\Omega _{2})=\zeta _{\Omega +1}}$ ${\displaystyle \psi _{1}(\Omega _{2}+1)=\varepsilon _{\zeta _{\Omega +1}+1}}$

La función nos da un sistema de notaciones ( ¡asumiendo que de alguna manera podemos escribir todos los ordinales contables!) para los ordinales incontables por debajo de , que es el límite de , y así sucesivamente. ${\displaystyle \psi _{1}}$ ${\displaystyle \psi _{1}(\varepsilon _{\Omega _{2}+1})}$ ${\displaystyle \psi _{1}(\Omega _{2})}$ ${\displaystyle \psi _{1}({\Omega _{2}}^{\Omega _{2}})}$

Ahora podemos reinyectar estas notaciones en la función original, modificadas de la siguiente manera: ${\displaystyle \psi }$

${\displaystyle \psi (\alpha )}$es el ordinal más pequeño que no se puede expresar a partir de , , , y usando sumas, productos, exponenciales, la función y la función misma (hasta ordinales construidos previamente menores que ). ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi _{1}}$ ${\displaystyle \psi }$ ${\displaystyle \alpha }$

Esta función modificada coincide con la anterior hasta (e incluyendo) — que es el ordinal de Bachmann–Howard. Pero ahora podemos ir más allá de esto, y es (el siguiente número después del ordinal de Bachmann–Howard). Hemos hecho que nuestro sistema sea doblemente impredicativo: para crear notaciones para ordinales contables usamos notaciones para ciertos ordinales entre y que están definidos usando ciertos ordinales más allá de . ${\displaystyle \psi }$ ${\displaystyle \psi (\psi _{1}(1))}$ ${\displaystyle \psi (\psi _{1}(1)+1)}$ ${\displaystyle \varepsilon _{\psi (\psi _{1}(1))+1}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \Omega }$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \Omega _{2}}$

Una variación de este esquema, que hace poca diferencia cuando se utilizan sólo dos (o un número finito) de funciones colapsantes, pero se vuelve importante para un número infinito de ellas, es definir

${\displaystyle \psi (\alpha )}$es el ordinal más pequeño que no se puede expresar a partir de , , , y utilizando sumas, productos, exponenciales y la función y (a ordinales construidos previamente menores que ). ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi _{1}}$ ${\displaystyle \psi }$ ${\displaystyle \alpha }$

es decir, permite el uso de solo para argumentos menores que él mismo. Con esta definición, debemos escribir en lugar de (aunque sigue siendo también igual a , por supuesto, pero ahora es constante hasta ). Este cambio no es esencial porque, intuitivamente hablando, la función colapsa los ordinales nombrables más allá de debajo de este último, por lo que importa poco si se invoca directamente en los ordinales más allá o en su imagen por . Pero hace posible definir y por inducción simultánea (en lugar de "hacia abajo"), y esto es importante si vamos a usar infinitas funciones colapsantes. ${\displaystyle \psi _{1}}$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\Omega _{2})}$ ${\displaystyle \psi (\psi _{1}(\Omega _{2}))}$ ${\displaystyle \psi (\psi _{1}(\Omega _{2}))=\psi (\zeta _{\Omega +1})}$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi _{1}}$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi }$ ${\displaystyle \Omega _{2}}$ ${\displaystyle \psi _{1}}$ ${\displaystyle \psi }$ ${\displaystyle \psi _{1}}$

De hecho, no hay razón para detenerse en dos niveles: usando nuevos cardinales de esta manera, , obtenemos un sistema esencialmente equivalente al introducido por Buchholz, ^[3] la diferencia no esencial es que dado que Buchholz usa ordinales desde el principio, no necesita permitir la multiplicación o la exponenciación; además, Buchholz no introduce los números o en el sistema ya que también serán producidos por las funciones: esto hace que todo el esquema sea mucho más elegante y más conciso de definir, aunque más difícil de entender. Este sistema también es sensiblemente equivalente a los "diagramas ordinales" anteriores (y mucho más difíciles de entender) de Takeuti ^[5] y las funciones de Feferman: su rango es el mismo ( , que podría llamarse el ordinal de Takeuti-Feferman–Buchholz, y que describe la fuerza de -comprensión más la inducción de barras ). ${\displaystyle \omega +1}$ ${\displaystyle \Omega _{1},\Omega _{2},\ldots ,\Omega _{\omega }}$ ${\displaystyle \omega +1}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \psi }$ ${\displaystyle \theta }$ ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$ ${\displaystyle \Pi _{1}^{1}}$

Una variante "normal"

La mayoría de las definiciones de funciones colapsantes ordinales que se encuentran en la literatura reciente difieren de las que hemos dado en un aspecto técnico pero importante que las hace técnicamente más convenientes aunque intuitivamente menos transparentes. A continuación, explicamos esto.

La siguiente definición (por inducción sobre ) es completamente equivalente a la de la función anterior: ${\displaystyle \alpha }$ ${\displaystyle \psi }$

Sea el conjunto de ordinales generados a partir de , , , y todos los ordinales menores que aplicando recursivamente las siguientes funciones: suma, multiplicación y exponenciación de ordinales, y la función . Entonces se define como el ordinal más pequeño tal que . ${\displaystyle C(\alpha ,\beta )}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \beta }$ ${\displaystyle \psi \upharpoonright _{\alpha }}$ ${\displaystyle \psi (\alpha )}$ ${\displaystyle \rho }$ ${\displaystyle C(\alpha ,\rho )\cap \Omega =\rho }$

(Esto es equivalente, porque si es el ordinal más pequeño que no está en , que es como definimos originalmente a , entonces también es el ordinal más pequeño que no está en , y además las propiedades que describimos de implican que ningún ordinal entre inclusivo y exclusivo pertenece a .) ${\displaystyle \sigma }$ ${\displaystyle C(\alpha ,0)}$ ${\displaystyle \psi (\alpha )}$ ${\displaystyle C(\alpha ,0)=C(\alpha ,\sigma )}$ ${\displaystyle \psi }$ ${\displaystyle \sigma }$ ${\displaystyle \Omega }$ ${\displaystyle C(\alpha ,\sigma )}$

Ahora podemos hacer un cambio en la definición que la hace sutilmente diferente:

Sea el conjunto de ordinales generados a partir de , , , y todos los ordinales menores que aplicando recursivamente las siguientes funciones: suma, multiplicación y exponenciación de ordinales, y la función . Entonces se define como el ordinal más pequeño tal que y . ${\displaystyle {\tilde {C}}(\alpha ,\beta )}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle \omega }$ ${\displaystyle \Omega }$ ${\displaystyle \beta }$ ${\displaystyle {\tilde {\psi }}\upharpoonright _{\alpha }}$ ${\displaystyle {\tilde {\psi }}(\alpha )}$ ${\displaystyle \rho }$ ${\displaystyle {\tilde {C}}(\alpha ,\rho )\cap \Omega =\rho }$ ${\displaystyle \alpha \in {\tilde {C}}(\alpha ,\rho )}$

Los primeros valores de coinciden con los de : es decir, para todos donde , tenemos porque la cláusula adicional siempre se cumple. Pero en este punto las funciones empiezan a diferir: mientras que la función se "atasca" en para todos , la función cumple porque la nueva condición impone . Por otro lado, todavía tenemos (porque para todos entonces la condición adicional no entra en juego). Nótese en particular que , a diferencia de , no es monótona ni es continua. ${\displaystyle {\tilde {\psi }}}$ ${\displaystyle \psi }$ ${\displaystyle \alpha <\zeta _{0}}$ ${\displaystyle \zeta _{0}=\varphi _{2}(0)}$ ${\displaystyle {\tilde {\psi }}(\alpha )=\psi (\alpha )}$ ${\displaystyle \alpha \in {\tilde {C}}(\alpha ,\rho )}$ ${\displaystyle \psi }$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \zeta _{0}\leq \alpha \leq \Omega }$ ${\displaystyle {\tilde {\psi }}}$ ${\displaystyle {\tilde {\psi }}(\zeta _{0})=\varepsilon _{\zeta _{0}+1}}$ ${\displaystyle \alpha \in {\tilde {C}}(\alpha ,\rho )}$ ${\displaystyle {\tilde {\psi }}(\zeta _{0})>\zeta _{0}}$ ${\displaystyle {\tilde {\psi }}(\Omega )=\zeta _{0}}$ ${\displaystyle \Omega \in C(\alpha ,\rho )}$ ${\displaystyle \rho }$ ${\displaystyle {\tilde {\psi }}}$ ${\displaystyle \psi }$

A pesar de estos cambios, la función también define un sistema de notaciones ordinales hasta el ordinal de Bachmann-Howard: las notaciones y las condiciones de canonicidad son ligeramente diferentes (por ejemplo, para todos los menores que el valor común ). ${\displaystyle {\tilde {\psi }}}$ ${\displaystyle \psi (\Omega +1+\alpha )={\tilde {\psi }}({\tilde {\psi }}(\Omega )+\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \psi (\Omega 2)={\tilde {\psi }}(\Omega +1)}$

Otros OCF similares

De Araiψ

La función ψ de Arai es una función colapsante ordinal introducida por Toshiyasu Arai (esposo de Noriko H. Arai ) en su artículo: Un análisis ordinal simplificado de la reflexión de primer orden . es una función colapsante tal que , donde representa el primer ordinal incontable (puede reemplazarse por el ordinal de Church-Kleene a costa de una dificultad técnica adicional). A lo largo de este artículo, representa la teoría de conjuntos de Kripke-Platek para un universo -reflector, es el cardinal menos -indescriptible (puede reemplazarse por el ordinal menos -reflector a costa de una dificultad técnica adicional), es un número natural fijo , y . ${\displaystyle \psi _{\Omega }(\alpha )}$ ${\displaystyle \psi _{\Omega }(\alpha )<\Omega }$ ${\displaystyle \Omega }$ ${\displaystyle {\mathsf {KP\Pi _{N}}}}$ ${\displaystyle {\mathsf {\Pi _{N}}}}$ ${\displaystyle \mathbb {K} _{N}}$ ${\displaystyle {\mathsf {\Pi }}_{N-2}^{1}}$ ${\displaystyle {\mathsf {\Pi }}_{N}}$ ${\displaystyle N}$ ${\displaystyle \geq 3}$ ${\displaystyle \Omega _{0}=0}$

Supóngase que para una oración ( ) . Entonces, existe un finito tal que para , . También se puede demostrar que demuestra que cada segmento inicial está bien fundado , y por lo tanto, es el ordinal de prueba teórica de . Se pueden hacer entonces las siguientes conversiones: ${\displaystyle {\mathsf {KP\Pi _{N}}}\vdash \theta }$ ${\displaystyle {\mathsf {\Sigma _{1}}}}$ ${\displaystyle \Omega }$ ${\displaystyle {\mathsf {\theta }}}$ ${\displaystyle n}$ ${\displaystyle \alpha =\psi _{\Omega }(\omega _{n}(\mathbb {K} _{N}+1))}$ ${\displaystyle L_{\alpha }\models \theta }$ ${\displaystyle {\mathsf {KP\Pi _{N}}}}$ ${\displaystyle \{\alpha \in OT:\alpha <\psi _{\Omega }(\omega _{n}(\mathbb {K} _{N}+1))\};n=1,2,\ldots }$ ${\displaystyle \psi _{\Omega }(\varepsilon _{\mathbb {K} _{N}+1})}$ ${\displaystyle {\mathsf {KP\Pi _{N}}}}$

• ${\displaystyle \psi _{\Omega }(\varepsilon _{\Omega +1})=|{\mathsf {KP\omega }}|={\mathsf {BHO}}}$, donde es el ordinal menos recursivamente regular o el cardinal menos incontable, es la teoría de conjuntos de Kripke-Platek con infinito y es el ordinal de Bachmann-Howard . ${\displaystyle \Omega }$ ${\displaystyle {\mathsf {KP\omega }}}$ ${\displaystyle {\mathsf {BHO}}}$
• ${\displaystyle \psi _{\Omega }(\Omega _{\omega })=|{\mathsf {\Pi _{1}^{1}-CA_{0}}}|={\mathsf {BO}}}$, donde es el límite mínimo de ordinales admisibles o el límite mínimo de cardinales infinitos y es el ordinal de Buchholz . ${\displaystyle \Omega _{\omega }}$ ${\displaystyle {\mathsf {BO}}}$
• ${\displaystyle \psi _{\Omega }(\varepsilon _{\Omega _{\omega }+1})=|{\mathsf {KPl}}|={\mathsf {TFBO}}}$, donde es el límite mínimo de ordinales admisibles o el límite mínimo de cardinales infinitos, es KPi sin el esquema de colección y es el ordinal de Takeuti–Feferman–Buchholz . ${\displaystyle \Omega _{\omega }}$ ${\displaystyle {\mathsf {KPl}}}$ ${\displaystyle {\mathsf {TFBO}}}$
• ${\displaystyle \psi _{\Omega }(\varepsilon _{I+1})=|{\mathsf {KPi}}|}$, donde es el ordinal menos recursivamente inaccesible o el cardinal menos débilmente inaccesible y es la teoría de conjuntos de Kripke-Platek con un universo recursivamente inaccesible. ${\displaystyle I}$ ${\displaystyle {\mathsf {KPi}}}$

De Bachmannψ

El primer ORF verdadero, el de Bachmann , fue inventado por Heinz Bachmann y es un tanto engorroso, ya que depende de secuencias fundamentales para todos los ordinales límite; además, la definición original es complicada. Michael Rathjen ha sugerido una "reformulación" del sistema, que funciona de la siguiente manera: ${\displaystyle \psi }$

• Sea un ordinal incontable tal como : ${\displaystyle \Omega }$ ${\displaystyle \omega _{1}}$
• Luego define como el cierre de bajo adición, y para . ${\displaystyle C^{\Omega }(\alpha ,\beta )}$ ${\displaystyle \beta \cup \{0,\Omega \}}$ ${\displaystyle (\xi \rightarrow \omega ^{\xi })}$ ${\displaystyle (\xi \rightarrow \psi _{\Omega }(\xi ))}$ ${\displaystyle \xi <\alpha }$
• ${\displaystyle \psi _{\Omega }(\alpha )}$es el ordinal contable más pequeño ρ tal que ${\displaystyle C^{\Omega }(\alpha ,\rho )\cap \Omega =\rho }$

${\displaystyle \psi _{\Omega }(\varepsilon _{\Omega +1})}$es el ordinal de Bachmann-Howard, el ordinal de prueba teórica de la teoría de conjuntos de Kripke-Platek con el axioma de infinito (KP).

De Buchholzψ

La de Buchholz  es una jerarquía de funciones de un solo argumento , que  en ocasiones se abrevia como . Esta función es probablemente la más conocida de todas las funciones de función de argumento único. La definición es la siguiente: ${\displaystyle \psi }$ ${\displaystyle \psi _{\nu }:{\mathsf {On}}\rightarrow {\mathsf {On}}}$ ${\displaystyle \psi _{\nu }(\alpha )}$ ${\displaystyle \psi _{\nu }\alpha }$

• Definir y para . ${\displaystyle \Omega _{0}=1}$ ${\displaystyle \Omega _{\nu }=\aleph _{\nu }}$ ${\displaystyle \nu >0}$
• Sea el conjunto de términos distintos en la forma normal de Cantor de (con cada término de la forma para , véase el teorema de la forma normal de Cantor ) ${\displaystyle P(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \omega ^{\xi }}$ ${\displaystyle \xi \in {\mathsf {On}}}$
• ${\displaystyle C_{\nu }^{0}(\alpha )=\Omega _{\nu }}$
• ${\displaystyle C_{\nu }^{n+1}(\alpha )=C_{\nu }^{n}(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^{n}(\alpha )\}\cup \{\psi _{\nu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\land \xi \in C_{u}(\xi )\land u\leq \omega \}}$
• ${\displaystyle C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )}$
• ${\displaystyle \psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})}$

El límite de este sistema es , el ordinal Takeuti–Feferman–Buchholz . ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$

Buchholz ampliadoψ

Esta función de límite ordinario es una extensión sofisticada de la de Buchholz  realizada por el matemático Denis Maksudov. El límite de este sistema, a veces llamado ordinal de Buchholz extendido, es mucho mayor, igual a donde denota el primer punto fijo omega. La función se define de la siguiente manera: ${\displaystyle \psi }$ ${\displaystyle \psi _{0}(\Omega _{\Omega _{\Omega _{\cdots }}})}$ ${\displaystyle \Omega _{\Omega _{\Omega _{...}}}}$

• Definir y para . ${\displaystyle \Omega _{0}=1}$ ${\displaystyle \Omega _{\nu }=\aleph _{\nu }}$ ${\displaystyle \nu >0}$
• ${\displaystyle C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}}$
• ${\displaystyle C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )\mid \mu ,\beta ,\gamma ,\eta \in C_{\nu }^{n}(\alpha )\land \eta <\alpha \}}$
• ${\displaystyle C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )}$
• ${\displaystyle \psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})}$

De Madoreψ

Esta función de función de operaciones ordinarias (OCF) era la misma que la función ψ utilizada anteriormente en este artículo; es una versión más simple y eficiente de la función ψ de Buchholz definida por David Madore. Su uso en este artículo condujo a un uso generalizado de la función.

• ${\displaystyle C_{0}(\alpha )=\{0,1,\omega ,\Omega \}}$
• ${\displaystyle C_{n+1}(\alpha )=\{\gamma +\delta ,\gamma \delta ,\gamma ^{\delta },\psi (\eta )\mid \gamma ,\delta ,\eta \in C_{n}(\alpha );\eta <\alpha \}}$
• ${\displaystyle C(\alpha )=\bigcup \limits _{n<\omega }C_{n}(\alpha )}$
• ${\displaystyle \psi (\alpha )=\min(\{\beta \in \Omega \mid \beta \notin C(\alpha )\})}$

Esta función fue utilizada por Chris Bird, quien también inventó el próximo OCF.

θ de pájaro

Chris Bird ideó la siguiente abreviatura para la función Veblen extendida : ${\displaystyle \varphi }$

• ${\displaystyle \theta (\Omega ^{n-1}a_{n-1}+\cdots +\Omega ^{2}a_{2}+\Omega a_{1}+a_{0},b)=\varphi (a_{n-1},\ldots ,a_{2},a_{1},a_{0},b)}$
• ${\displaystyle \theta (\alpha ,0)}$se abrevia ${\displaystyle \theta (\alpha )}$

Esta función solo está definida para argumentos menores que , y sus salidas están limitadas por el ordinal de Veblen pequeño. ${\displaystyle \Omega ^{\omega }}$

De cazadoresψ

La ψ de Jäger  es una jerarquía de funciones ordinales de un solo argumento ψ _κ  indexadas por cardinales regulares incontables κ  más pequeños que el cardinal de Mahlo menos débil M ₀  introducida por el matemático alemán Gerhard Jäger en 1984. Fue desarrollada sobre la base del enfoque de Buchholz.

• Si para algún α < κ , . ${\displaystyle \kappa =I_{\alpha }(0)}$ ${\displaystyle \kappa ^{-}=0}$
• Si para algún α , β <  κ , . ${\displaystyle \kappa =I_{\alpha }(\beta +1)}$ ${\displaystyle \kappa ^{-}=I_{\alpha }(\beta )}$
• ${\displaystyle C_{\kappa }^{0}(\alpha )=\{\kappa ^{-}\}\cup \kappa ^{-}}$
• Para cada n finito , es el conjunto más pequeño que satisface lo siguiente: ${\displaystyle C_{\kappa }^{n+1}(\alpha )\subset M_{0}}$
  • La suma de cualquier número finito de ordinales en pertenece a . ${\displaystyle C_{\kappa }^{n}(\alpha )\subset M_{0}}$ ${\displaystyle C_{\kappa }^{n+1}(\alpha )\subset M_{0}}$
  • Para cualquier , . ${\displaystyle \beta ,\gamma \in C_{\kappa }^{n}(\alpha )}$ ${\displaystyle \varphi _{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )}$
  • Para cualquier , . ${\displaystyle \beta ,\gamma \in C_{\kappa }^{n}(\alpha )}$ ${\displaystyle I_{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )}$
  • Para cualquier ordinal γ y cardinal regular incontable , . ${\displaystyle \pi \in C_{\kappa }^{n}(\alpha )}$ ${\displaystyle \gamma <\pi <\kappa \Rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )}$
  • Para cualquier cardenal regular incontable , . ${\displaystyle \gamma \in \alpha \cap C_{\kappa }^{n}(\alpha )}$ ${\displaystyle \pi \in C_{\kappa }^{n}(\alpha )}$ ${\displaystyle \gamma \in C_{\pi }(\gamma )\Rightarrow \psi _{\pi }(\gamma )\in C_{\kappa }^{n+1}(\alpha )}$
• ${\displaystyle C_{\kappa }(\alpha )=\bigcup \limits _{n<\omega }C_{\kappa }^{n}(\alpha )}$
• ${\displaystyle \psi _{\kappa }(\alpha )=\min(\{\xi \in \kappa \mid \xi \notin C_{\kappa }(\alpha )\})}$

Jäger simplificadoψ

Esta es una simplificación sofisticada de la ψ de Jäger creada por Denis Maksudov. Un ordinal es α -débilmente inaccesible si es incontable, regular y es un límite de cardinales γ -débilmente inaccesibles para γ < α . Sea I ( α , 0) el primer cardenal α-débilmente inaccesible, I ( α , β + 1) el primer cardenal α -débilmente inaccesible después de I ( α , β ) e I ( α , β ) = para el límite β . Restringimos ρ y π a ordinales regulares incontables de la forma I ( α , 0) o I ( α , β + 1). Entonces, ${\displaystyle sup(\{I(\alpha ,\gamma )\mid \gamma <\beta \})}$

• ${\displaystyle C_{0}(\alpha ,\beta )=\beta \cup \{0\}}$
• ${\displaystyle C_{n+1}(\alpha ,\beta )=\{\gamma +\delta \mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{I(\gamma ,\delta )\mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{\psi _{\pi }(\gamma )\mid \pi ,\gamma ,\in C_{n}(\alpha ,\beta )\land \gamma <\alpha \}}$
• ${\displaystyle C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )}$
• ${\displaystyle \psi _{\pi }(\alpha )=\min(\{\beta <\pi \mid C(\alpha ,\beta )\cap \pi \subseteq \beta \})}$

De RathjenO

La función Ψ de Rathjen  se basa en el cardinal menos débilmente compacto para crear ordinales contables grandes. Para un cardinal débilmente compacto K, las funciones , , y  se definen en recursión mutua de la siguiente manera: ${\displaystyle M^{\alpha }}$ ${\displaystyle C(\alpha ,\pi )}$ ${\displaystyle \Xi (\alpha )}$ ${\displaystyle \Psi _{\pi }^{\xi }(\alpha )}$

• M ⁰ = , donde Lim denota la clase de ordinales límite. ${\displaystyle K\cap {\mathsf {Lim}}}$
• Para α > 0, M ^α es el conjunto estacionario en ${\displaystyle \{\pi <K\mid C(\alpha ,\pi )\cap K=\pi \land \forall \xi \in C(\alpha ,\pi )\cap \alpha ,M^{\xi }{\mathsf {}}}$ ${\displaystyle \pi \land \alpha \in C(\alpha ,\pi )\}}$
• ${\displaystyle C(\alpha ,\beta )}$es el cierre de bajo adición, , dado ξ < K, dado ξ < α, y dado . ${\displaystyle \beta \cup \{0,K\}}$ ${\displaystyle (\xi ,\eta )\rightarrow \varphi (\xi ,\eta )}$ ${\displaystyle \xi \rightarrow \Omega _{\xi }}$ ${\displaystyle \xi \rightarrow \Xi (\xi )}$ ${\displaystyle (\xi ,\pi ,\delta )\rightarrow \Psi _{\pi }^{\xi }(\delta )}$ ${\displaystyle \xi \leq \delta <\alpha }$
• ${\displaystyle \Xi (\alpha )=\min(M^{\alpha }\cup \{K\})}$.
• Para , . ${\displaystyle \xi \leq \alpha }$ ${\displaystyle \Psi _{\pi }^{\xi }(\alpha )=\min(\{\rho \in M^{\xi }\cap \pi :C(\alpha ,\rho )\cap \pi =\rho \land \pi ,\alpha \in C(\alpha ,\rho )\}\cup \{\pi \})}$

Cardenales grandes colapsando

Como se señala en la introducción, el uso y la definición de funciones de colapso ordinales están fuertemente conectados con la teoría del análisis ordinal , por lo que el colapso de este o aquel cardinal grande debe mencionarse simultáneamente con la teoría para la cual proporciona un análisis de teoría de prueba.

• Gerhard Jäger y Wolfram Pohlers ^[6] describieron el colapso de un cardinal inaccesible para describir la fortaleza ordinal-teórica de la teoría de conjuntos de Kripke-Platek aumentada por la inaccesibilidad recursiva de la clase de ordinales ( KPi ), ​​que también es equivalente en teoría de pruebas ^[1] a la -comprensión más la inducción de barras . En términos generales, este colapso se puede obtener agregando la función misma a la lista de construcciones a las que se aplica el sistema colapsante. ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle \alpha \mapsto \Omega _{\alpha }}$ ${\displaystyle C(\cdot )}$
• Michael Rathjen ^[7] luego describió el colapso de un cardinal de Mahlo para describir la fortaleza ordinal-teórica de la teoría de conjuntos de Kripke-Platek aumentada por la Mahloness recursiva de la clase de ordinales ( KPM ).
• Rathjen ^[8] describió posteriormente el colapso de un cardinal débilmente compacto para describir la fortaleza teórica ordinal de la teoría de conjuntos de Kripke-Platek aumentada por ciertos principios de reflexión (concentrándose en el caso de la -reflexión). En términos muy generales, esto se lleva a cabo introduciendo el primer cardinal que es -hiper-Mahlo y agregando la función misma al sistema que colapsa. ${\displaystyle \Pi _{3}}$ ${\displaystyle \Xi (\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha \mapsto \Xi (\alpha )}$
• En un artículo de 2015, Toshyasu Arai creó funciones de colapso ordinal para un vector de ordinales , que colapsan cardinales indescriptibles para . Estas se utilizan para realizar análisis ordinales de la teoría de conjuntos de Kripke-Platek aumentada por principios de reflexión. ^[9] ${\displaystyle \psi _{\pi }^{\vec {\xi }}}$ ${\displaystyle \xi }$ ${\displaystyle \Pi _{n}^{1}}$ ${\displaystyle n>0}$ ${\displaystyle \Pi _{n+2}}$
• Rathjen ha investigado el colapso de cardinales aún más grandes, con el objetivo final de lograr un análisis ordinal de -comprensión (que es teóricamente equivalente a la ampliación de Kripke-Platek por -separación). ^[10] ${\displaystyle \Pi _{2}^{1}}$ ${\displaystyle \Sigma _{1}}$

Notas

1. Rathjen, 1995 (Bull. Lógica simbólica)
2. Kahle, 2002 (Síntesis)
3. Buchholz, 1986 (Lógica aplicada pura, ann.)
4. Rathjen, 2005 (diapositivas de Fischbachau)
5. Takeuti, 1967 (Matemáticas anuales).
6. Jäger & Pohlers, 1983 (Bayer. Akad. Wiss. Math.-Natur. Kl. Sitzungsber.)
7. Rathjen, 1991 (Arquitectura, Matemáticas, Lógica)
8. Rathjen, 1994 (Lógica aplicada puramente ann.)
9. T. Arai, Un análisis simplificado de la reflexión de primer orden (2015).
10. Rathjen, 2005 (Arquitectura, Matemáticas, Lógica)

Referencias

• Arai, Toshiyasu (septiembre de 2020). «Un análisis ordinal simplificado de la reflexión de primer orden». The Journal of Symbolic Logic . 85 (3): 1163–1185. arXiv : 1907.07611 . doi :10.1017/jsl.2020.23. S2CID  118940547.
• Takeuti, Gaisi (1967). "Pruebas de consistencia de subsistemas de análisis clásico". Anales de Matemáticas . 86 (2): 299–348. doi :10.2307/1970691. JSTOR  1970691.
• Jäger, Gerhard; Pohlers, Wolfram (1983). "Eine beweistheoretische Untersuchung von ( -CA)+(BI) und verwandter Systeme". Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte . 1982 : 1–28. ${\displaystyle \Delta _{2}^{1}}$
• Buchholz, Wilfried (1986). "Un nuevo sistema de funciones ordinales basadas en la teoría de la demostración". Anales de lógica pura y aplicada . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 .
• Rathjen, Michael (1991). "Análisis teórico de pruebas de KPM". Archivo de lógica matemática . 30 (5–6): 377–403. doi :10.1007/BF01621475. S2CID  9376863.
• Rathjen, Michael (1994). "Teoría de la prueba de la reflexión" (PDF) . Anales de lógica pura y aplicada . 68 (2): 181–224. doi :10.1016/0168-0072(94)90074-4.
• Rathjen, Michael (1995). "Avances recientes en análisis ordinal: Π 2 1 {\displaystyle \Pi _{2}^{1}} -CA y sistemas relacionados". Boletín de lógica simbólica . 1 (4): 468–485. doi :10.2307/421132. JSTOR  421132. S2CID  10648711.
• Kahle, Reinhard (2002). "Teoría de la prueba matemática a la luz del análisis ordinal". Síntesis . 133 : 237–255. doi :10.1023/A:1020892011851. S2CID  45695465.
• Rathjen, Michael (2005). "Un análisis ordinal de la estabilidad". Archivo de Lógica Matemática . 44 : 1–62. CiteSeerX  10.1.1.15.9786 . doi :10.1007/s00153-004-0226-2. S2CID  2686302.
• Rathjen, Michael (agosto de 2005). "Proof Theory: Part III, Kripke–Platek Set Theory" (PDF) . Archivado desde el original (PDF) el 2007-06-12 . Consultado el 2008-04-17 .(diapositivas de una charla dada en Fischbachau)