función de colapso ordinal

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 recursivos grandes y numerables , cuyo principio consiste en dar nombres a ciertos ordinales mucho mayores que el que se está definiendo, incluso cardinales grandes (aunque pueden reemplazarse por ordinales recursivamente grandes a costa de una mayor dificultad técnica), 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 las funciones de colapso ordinal varían y se vuelven más complejos a medida que se definen ordinales mayores, pero la idea típica es que cuando el sistema de notación se queda sin opciones y no puede nombrar un ordinal determinado, se recurre a un ordinal mucho mayor para dar nombre a ese punto crítico. A continuación se detallará un ejemplo de cómo funciona esto, para una función de colapso ordinal que define el ordinal de Bachmann-Howard (es decir, 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 teórica ordinal de ciertos sistemas formales , típicamente ^{[ 1 ]}^{[ 2 ]} subsistemas de aritmética de segundo orden (como los que se ven en matemáticas inversas ), extensiones de la teoría de conjuntos de Kripke-Platek , sistemas de estilo Bishop de matemáticas constructivas o sistemas de estilo Martin-Löf de teoría de tipos intuicionista .

Las funciones de colapso ordinal se suelen denotar utilizando alguna variación de la letra griega $\psi$ ( psi ) o $\theta$ ( theta ).

Un ejemplo que conduce al ordinal Bachmann-Howard

La elección de la función de colapso ordinal que se muestra a continuación imita en gran medida el sistema introducido por Buchholz, ^{[ 3 ]} pero se limita al colapso de un cardinal para mayor claridad en la exposición. Se describirá con más detalle la relación entre este ejemplo y el sistema de Buchholz cuando se vaya más allá del ordinal de Bachmann-Howard .

Definición

Dejar $\Omega$ representar el primer ordinal incontable $\omega _{1}$ , o, de hecho, cualquier ordinal que sea un $\varepsilon$ -número y garantizado que será 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 $\omega _{1}$ porque permite el uso conveniente de la palabra contable en las definiciones).

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

Asumir

\psi (\beta )

se ha definido para todos

\beta <\alpha

y deseamos definir

\psi (\alpha )

.

Dejar

C(\alpha )

sea el conjunto de ordinales generados a partir de

0

,

1

,

\omega

y

\Omega

aplicando recursivamente las siguientes funciones: suma ordinal, multiplicación y exponenciación y la función

\psi {\upharpoonright _{\alpha }}

, es decir, la restricción de

\psi

a ordinales

\beta <\alpha

. (Formalmente, definimos

C(\alpha )_{0}=\{0,1,\omega ,\Omega \}

y de forma inductiva

C(\alpha )_{n+1}=C(\alpha )_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\cdot \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 \}

para todos los números naturales

n

y dejamos

C(\alpha )

ser la unión de los

C(\alpha )_{n}

a pesar de

n

.)

Entonces

\psi (\alpha )

se define como el ordinal más pequeño que no pertenece a

C(\alpha )

.

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

\psi (\alpha )

es el ordinal más pequeño que no se puede expresar desde

0

,

1

,

\omega

y

\Omega

utilizando sumas, productos, exponenciales y el

\psi

función en sí misma (a ordinales construidos previamente menores que

\alpha

).

Aquí se intenta explicar la motivación para la definición de $\psi$ En términos intuitivos: dado que las operaciones habituales de suma, 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 aún no tiene nombre, y cuando nos quedamos sin nombres, en lugar de inventarlos de forma ad hoc o utilizando esquemas diagonales , los buscamos en los ordinales mucho más allá de los que estamos construyendo (más allá de $\Omega$ , es decir); así que damos nombres a los ordinales incontables y, puesto que al final la lista de nombres es necesariamente contable, $\psi$ los "colapsarán" a ordinales contables.

Cálculo de los valores de ψ

Para aclarar cómo funciona $\psi$ es capaz de producir notaciones para ciertos ordinales, ahora calculamos sus primeros valores.

Inicio predictivo

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

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

\psi (\alpha )=\varepsilon _{\alpha }=\varphi _{1}(\alpha )

a pesar de

\alpha \leq \zeta _{0}

, dónde

\zeta _{0}=\varphi _{2}(0)

es el punto fijo más pequeño de

\alpha \mapsto \varepsilon _{\alpha }

.

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

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

\psi (\alpha )=\zeta _{0}

a pesar de

\zeta _{0}\leq \alpha \leq \Omega

.

Primeros valores impredicativos

De nuevo, $\psi (\Omega )=\zeta _{0}$ Sin embargo, cuando hablamos de informática $\psi (\Omega +1)$ , algo ha cambiado: desde $\Omega$ se agregó ("artificialmente") a todos los $C(\alpha )$ , se nos permite tomar el valor $\psi (\Omega )=\zeta _{0}$ en el proceso. Así que $C(\Omega +1)$ contiene todos los ordinales que se pueden construir a partir de $0$ , $1$ , $\omega$ , $\Omega$ , el $\varphi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ función hasta $\zeta _{0}$ y esta vez también $\zeta _{0}$ en sí mismo, usando suma, multiplicación y exponenciación. El ordinal más pequeño que no está en $C(\Omega +1)$ es $\varepsilon _{\zeta _{0}+1}$ (el más pequeño) $\varepsilon$ -número después $\zeta _{0}$ ).

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

Valores de ψ hasta el ordinal de Feferman-Schütte

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

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

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

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

Tenemos $\psi (\Omega ^{\Omega }+\Omega ^{\alpha })=\varphi _{\Gamma _{0}+\alpha }(0)$ a pesar de $\alpha \leq \Gamma _{1}$ dónde $\Gamma _{1}$ es el siguiente punto fijo de $\alpha \mapsto \varphi _{\alpha }(0)$ . Entonces, si $\alpha \mapsto \Gamma _{\alpha }$ enumera los puntos fijos en cuestión (que también pueden ser señalados) $\varphi (1,0,\alpha )$ utilizando las funciones Veblen multivaluadas) tenemos $\psi (\Omega ^{\Omega }(1+\alpha ))=\Gamma _{\alpha }$ hasta el primer punto fijo $\varphi (1,1,0)$ del $\alpha \mapsto \Gamma _{\alpha }$ sí mismo, que será $\psi (\Omega ^{\Omega +1})$ (y el primer punto fijo $\varphi (2,0,0)$ del $\alpha \mapsto \varphi (1,\alpha ,0)$ las funciones serán $\psi (\Omega ^{\Omega \cdot 2})$ ). De esta manera:

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

Notaciones ordinales hasta el ordinal de Bachmann-Howard

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

Una nota sobre las representaciones básicas

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

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

Algunas propiedades de ψ

La función $\psi$ es no decreciente y continua (esto es más o menos obvio a partir de su definición).
Si $\psi (\alpha )=\psi (\beta )$ con $\beta <\alpha$ entonces necesariamente $C(\alpha )=C(\beta )$ . De hecho, ningún ordinal $\beta '$ con $\beta \leq \beta '<\alpha$ puede pertenecer a $C(\alpha )$ (de lo contrario su imagen por $\psi$ , que es $\psi (\alpha )$ pertenecería a $C(\alpha )$ — imposible); así que $C(\beta )$ está cerrado por todo lo que está bajo el cual $C(\alpha )$ es el cierre, por lo tanto son iguales.
Cualquier valor $\gamma =\psi (\alpha )$ tomado por $\psi$ es un $\varepsilon$ -número (es decir, un punto fijo de $\beta \mapsto \omega ^{\beta }$ ). De hecho, si no fuera así, entonces al escribirlo en forma normal de Cantor , podría expresarse usando sumas, productos y exponenciación de elementos menores que él, por lo tanto en $C(\alpha )$ , así que estaría en $C(\alpha )$ , una contradicción.
Lema: Supongamos $\delta$ es un $\varepsilon$ -número y $\alpha$ un ordinal tal que $\psi (\beta )<\delta$ a pesar de $\beta <\alpha$ : entonces el $\Omega$ -piezas (definidas anteriormente ) de cualquier elemento de $C(\alpha )$ son menos que $\delta$ En efecto, dejemos $C'$ sea el conjunto de ordinales todos aquellos $\Omega$ -las piezas son menos que $\delta$ . Entonces $C'$ es cerrado bajo la suma, la multiplicación y la exponenciación (porque $\delta$ es un $\varepsilon$ -número, por lo que los ordinales menores que él son cerrados bajo la suma, la multiplicación y la potenciación). Y $C'$ también contiene todos $\psi (\beta )$ para $\beta <\alpha$ por supuesto, y contiene $0$ , $1$ , $\omega$ , $\Omega$ . Entonces $C'\supseteq C(\alpha )$ , que debía ser mostrado.
Bajo la hipótesis del lema anterior, $\psi (\alpha )\leq \delta$ (de hecho, el lema muestra que $\delta \not \in C(\alpha )$ ).
Cualquier $\varepsilon$ -número menor que algún elemento en el rango de $\psi$ está en sí mismo dentro del rango de $\psi$ (eso es, $\psi$ no omite $\varepsilon$ -número). En efecto: si $\delta$ es un $\varepsilon$ -número no mayor que el rango de $\psi$ , dejar $\alpha$ sea el límite superior más pequeño de la $\beta$ de tal manera que $\psi (\beta )<\delta$ : entonces por lo anterior tenemos $\psi (\alpha )\leq \delta$ , pero $\psi (\alpha )<\delta$ contradiría el hecho de que $\alpha$ es el límite superior más pequeño , por lo tanto $\psi (\alpha )=\delta$ .
Cuando sea $\psi (\alpha )=\delta$ , el conjunto $C(\alpha )$ consta exactamente de esos ordinales $\gamma$ (menos que $\varepsilon _{\Omega +1}$ ) todos aquellos $\Omega$ -las piezas son menos que $\delta$ . De hecho, sabemos que todos los ordinales menores que $\delta$ , por lo tanto todos los ordinales (menores que $\varepsilon _{\Omega +1}$ ) cuyo $\Omega$ -las piezas son menos que $\delta$ , están en $C(\alpha )$ . Por el contrario, si asumimos $\psi (\beta )<\delta$ a pesar de $\beta <\alpha$ (en otras palabras si $\alpha$ es lo menos posible con $\psi (\alpha )=\delta$ ), el lema proporciona la propiedad deseada. Por otro lado, si $\psi (\alpha )=\psi (\beta )$ para algunos $\beta <\alpha$ , entonces ya lo hemos comentado $C(\alpha )=C(\beta )$ y podemos reemplazar $\alpha$ por lo menos posible con $\psi (\alpha )=\delta$ .

La notación ordinal

Utilizando los hechos anteriores, podemos definir una notación ordinal (canónica) para cada $\gamma$ menos que el ordinal de Bachmann-Howard. Hacemos esto por inducción sobre $\gamma$ .

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

Queda por tratar el caso donde $\gamma =\delta$ es un $\varepsilon$ -número: hemos argumentado que, en este caso, podemos escribir $\delta =\psi (\alpha )$ para algún (posiblemente incontable) ordinal $\alpha <\varepsilon _{\Omega +1}$ : dejar $\alpha$ ser el mayor ordinal posible de este tipo (que existe desde $\psi$ es continuo). Usamos la base iterada $\Omega$ representación de $\alpha$ : queda por demostrar que cada parte de esta representación es menor que $\delta$ (por lo que ya hemos definido una notación para ello). Si este no es el caso, entonces, por las propiedades que hemos mostrado, $C(\alpha )$ no contiene $\alpha$ ; pero entonces $C(\alpha +1)=C(\alpha )$ (se cierran bajo las mismas operaciones, ya que el valor de $\psi$ en $\alpha$ nunca se puede tomar), así que $\psi (\alpha +1)=\psi (\alpha )=\delta$ , contradiciendo la máxima de $\alpha$ .

Nota : En realidad, hemos definido notaciones canónicas no solo para ordinales por debajo del ordinal de Bachmann-Howard sino también para ciertos ordinales no numerables, a saber, aquellos cuyos $\Omega$ -las piezas son menores que el ordinal Bachmann-Howard (es decir: escríbalas en base iterada) $\Omega$ representación y utilice la representación canónica para cada pieza). Esta notación canónica se utiliza para los argumentos de la $\psi$ función (que puede ser incontable).

Ejemplos

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

Para ordinales menores que $\varepsilon _{1}=\psi (1)$ , la notación coincide con la base iterada $\varepsilon _{0}$ notación (las piezas están escritas en forma normal de Cantor iterada): por ejemplo, $\omega ^{\omega ^{\varepsilon _{0}+\omega }}$ será escrito ${\varepsilon _{0}}^{\omega ^{\omega }}$ , o, más precisamente, $\psi (0)^{\omega ^{\omega }}$ . Para ordinales menores que $\varepsilon _{2}=\psi (2)$ , de manera similar escribimos en base iterada $\varepsilon _{1}$ y luego escribir las piezas en base iterada $\varepsilon _{0}$ (y escribe las partes de eso en forma normal de Cantor iterada): así que $\omega ^{\omega ^{\varepsilon _{1}+\varepsilon _{0}+1}}$ está escrito ${\varepsilon _{1}}^{\varepsilon _{0}\omega }$ , o, más precisamente, $\psi (1)^{\psi (0)\,\omega }$ . Por lo tanto, hasta $\zeta _{0}=\psi (\Omega )$ Siempre utilizamos el mayor posible $\varepsilon$ -base numérica que proporciona una representación no trivial.

Más allá de esto, es posible que necesitemos expresar ordinales más allá de $\Omega$ : esto siempre se hace de forma iterativa $\Omega$ -base, y las piezas mismas deben expresarse utilizando el mayor posible $\varepsilon$ -base numérica que proporciona una representación no trivial.

Tenga en cuenta que mientras $\psi (\varepsilon _{\Omega +1})$ es igual al ordinal de Bachmann-Howard, esto 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).

Condiciones para la canonicidad

Las notaciones así definidas tienen la propiedad de que siempre que se aniden $\psi$ funciones, los argumentos del "interno" $\psi$ Las funciones son siempre menores que las de la "externa" (esto es consecuencia del hecho de que la $\Omega$ -piezas de $\alpha$ , dónde $\alpha$ es el mayor posible tal que $\psi (\alpha )=\delta$ para algunos $\varepsilon$ -número $\delta$ , todos son menores que $\delta$ , como hemos mostrado anteriormente). Por ejemplo, $\psi (\psi (\Omega )+1)$ no aparece como una notación: es una expresión bien definida (y es igual a $\psi (\Omega )=\zeta _{0}$ desde $\psi$ es constante entre $\zeta _{0}$ y $\Omega$ ), pero no es una notación producida por el algoritmo inductivo que hemos descrito.

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 $\varepsilon _{0}$ o una base iterada $\delta$ representación cuyas piezas son todas canónicas, para algunos $\delta =\psi (\alpha )$ dónde $\alpha$ está escrito en base iterada $\Omega$ representación cuyas piezas son todas canónicas y menos que $\delta$ . El orden se comprueba mediante verificación lexicográfica en todos los niveles (teniendo en cuenta que $\Omega$ es mayor que cualquier expresión obtenida por $\psi$ y para valores canónicos el mayor $\psi$ siempre supera a las sumas, productos y exponenciales menores o incluso arbitrarias del menor).

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

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

Secuencias estándar para notaciones ordinales

Para constatar que hemos definido notaciones para ordinales inferiores al ordinal de Bachmann-Howard (que son todos de cofinalidad numerable ), podríamos definir secuencias estándar que convergen a cualquiera de ellos (siempre que sea un ordinal límite, por supuesto). De hecho, también definiremos secuencias canónicas para ciertos ordinales no numerables, a saber, los ordinales no numerables de cofinalidad numerable (si queremos definir una secuencia que converja a ellos...) que son representables (es decir, todos aquellos cuyos $\Omega$ -las piezas son menos que el ordinal Bachmann-Howard).

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

Primero, deshazte de la base (iterada) $\delta$ $\delta$ representaciones: definir una secuencia estándar que converge a $\alpha =\delta ^{\beta _{1}}\gamma _{1}+\cdots +\delta ^{\beta _{k}}\gamma _{k}$ $\alpha =\delta ^{\beta _ {1}}\gamma _ {1}+\cdots +\delta ^{\beta _ {k}}\gamma _ {k}$ , dónde $\delta$ $\delta$ es o $\omega$ $\omega$ o $\psi (\cdots )$ $\psi (\cdots)$ (o $\Omega$ $\Omega$ , pero véase más abajo):
- si $k$ entonces es cero $\alpha =0$ y no hay nada que hacer;
- si $\beta _{k}$ es cero y $\gamma _{k}$ es sucesor, entonces $\alpha$ es el sucesor y no hay nada que hacer;
- si $\gamma _{k}$ es límite, tome la secuencia estándar que converge a $\gamma _{k}$ y reemplazar $\gamma _{k}$ en la expresión mediante los elementos de esa secuencia;
- si $\gamma _{k}$ es sucesor y $\beta _{k}$ es límite, reescribe el último término $\delta ^{\beta _{k}}\gamma _{k}$ como $\delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}}$ y reemplazar el exponente $\beta _{k}$ en el último término por los elementos de la secuencia fundamental que convergen hacia ella;
- si $\gamma _{k}$ es sucesor y $\beta _{k}$ También es, reescribe el último término $\delta ^{\beta _{k}}\gamma _{k}$ como $\delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}-1}\delta$ y reemplazar el último $\delta$ en esta expresión por los elementos de la secuencia fundamental que convergen hacia ella.
Si $\delta$ es $\omega$ , entonces tomemos lo obvio $0,1,2,3,\ldots$ como la secuencia fundamental para $\delta$ .
Si $\delta =\psi (0)$ entonces tomar como secuencia fundamental para $\delta$ la secuencia $\omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\ldots$
Si $\delta =\psi (\alpha +1)$ entonces tomar como secuencia fundamental para $\delta$ la secuencia $\psi (\alpha ),\psi (\alpha )^{\psi (\alpha )},\psi (\alpha )^{\psi (\alpha )^{\psi (\alpha )}},\ldots$
Si $\delta =\psi (\alpha )$ dónde $\alpha$ es un ordinal límite de cofinalidad contable , defina la secuencia estándar para $\delta$ que se obtendrá aplicando $\psi$ a la secuencia estándar para $\alpha$ (recuerde que $\psi$ es continuo y creciente, aquí).
Queda por manejar el caso donde $\delta =\psi (\alpha )$ con $\alpha$ un ordinal de cofinalidad incontable (por ejemplo, $\Omega$ por sí mismo). Obviamente no tiene sentido definir una secuencia que converge a $\alpha$ en este caso; sin embargo, lo que podemos definir es una sucesión que converge a algún $\rho <\alpha$ con cofinalidad contable y tal que $\psi$ es constante entre $\rho$ y $\alpha$ . Este $\rho$ será el primer punto fijo de una determinada función (continua y no decreciente) $\xi \mapsto h(\psi (\xi ))$ Para encontrarlo, aplique las mismas reglas (desde la base). $\Omega$ representación de $\alpha$ ) para encontrar la secuencia canónica de $\alpha$ , excepto que siempre que una secuencia converge a $\Omega$ se requiere (algo que no puede existir), reemplace el $\Omega$ en cuestión, en la expresión de $\alpha =h(\Omega )$ , por un $\psi (\xi )$ (dónde $\xi$ es una variable) y realizar una iteración repetida (comenzando desde $0$ , digamos) de la función $\xi \mapsto h(\psi (\xi ))$ : esto da una secuencia $0,h(\psi (0)),h(\psi (h(\psi (0)))),\ldots$ tendiendo a $\rho$ y la secuencia canónica para $\psi (\alpha )=\psi (\rho )$ es $\psi (0)$ , $\psi (h(\psi (0)))$ , $\psi (h(\psi (h(\psi (0)))))$ ... Si dejamos que el $n$ elemento (comenzando en $0$ ) de la secuencia fundamental para $\delta$ ser denotado como $\delta [n]$ , entonces podemos expresar esto más claramente usando recursión. Usando esta notación, podemos ver que $\delta [0]=\psi (0)$ Bastante fácilmente. Podemos definir el resto de la secuencia usando recursión: $\delta [n]=\psi (h(\delta [n-1]))$ (Los ejemplos que aparecen a continuación deberían aclararlo).

Aquí tenéis algunos ejemplos para el último (y más interesante) caso:

La secuencia canónica para $\psi (\Omega )$ es: $\psi (0)$ , $\psi (\psi (0))$ , $\psi (\psi (\psi (0)))$ ... Esto, en efecto, converge a $\rho =\psi (\Omega )=\zeta _{0}$ después de lo cual $\psi$ es constante hasta $\Omega$ .
La secuencia canónica para $\psi (\Omega 2)$ es: $\psi (0)$ , $\psi (\Omega +\psi (0))$ , $\psi (\Omega +\psi (\Omega +\psi (0))),\ldots$ Esto, en efecto, converge al valor de $\psi$ en $\rho =\Omega +\psi (\Omega 2)=\Omega +\zeta _{1}$ después de lo cual $\psi$ es constante hasta $\Omega 2$ .
La secuencia canónica para $\psi (\Omega ^{2})$ es: $\psi (0),\psi (\Omega \psi (0)),\psi (\Omega \psi (\Omega \psi (0))),\ldots$ Esto converge al valor de $\psi$ en $\rho =\Omega \psi (\Omega ^{2})$ .
La secuencia canónica para $\psi (\Omega ^{2}3+\Omega )$ es $\psi (0),\psi (\Omega ^{2}3+\psi (0)),\psi (\Omega ^{2}3+\psi (\Omega ^{2}3+\psi (0))),\ldots$ Esto converge al valor de $\psi$ en $\rho =\Omega ^{2}3+\psi (\Omega ^{2}3+\Omega )$ .
La secuencia canónica para $\psi (\Omega ^{\Omega })$ es: $\psi (0),\psi (\Omega ^{\psi (0)}),\psi (\Omega ^{\psi (\Omega ^{\psi (0)})}),\ldots$ Esto converge al valor de $\psi$ en $\rho =\Omega ^{\psi (\Omega ^{\Omega })}$ .
La secuencia canónica para $\psi (\Omega ^{\Omega }3)$ es: $\psi (0),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)}),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)})}),\ldots$ Esto converge al valor de $\psi$ en $\rho =\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }3)}$ .
La secuencia canónica para $\psi (\Omega ^{\Omega +1})$ es: $\psi (0),\psi (\Omega ^{\Omega }\psi (0)),\psi (\Omega ^{\Omega }\psi (\Omega ^{\Omega }\psi (0))),\ldots$ Esto converge al valor de $\psi$ en $\rho =\Omega ^{\Omega }\psi (\Omega ^{\Omega +1})$ .
La secuencia canónica para $\psi (\Omega ^{\Omega ^{2}+\Omega 3})$ es: $\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$

Aquí hay algunos ejemplos de los otros casos:

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

Aunque el ordinal Bachmann-Howard $\psi (\varepsilon _{\Omega +1})$ En sí mismo no tiene notación canónica, también es útil definir una secuencia canónica para ello: esto es $\psi (\Omega )$ , $\psi (\Omega ^{\Omega })$ , $\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 mientras no sea cero:

si el ordinal es un sucesor, réstale uno (es decir, reemplázalo por su predecesor),
Si se trata de un límite, sustitúyalo 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 :

Puede tardar mucho tiempo en terminar,
La prueba de terminación puede estar fuera del alcance de ciertos sistemas aritméticos débiles.

Para dar una idea de cómo se siente el proceso, aquí hay algunos pasos del mismo: comenzando desde $\psi (\Omega ^{\Omega ^{\omega }})$ (el pequeño ordinal de Veblen), podríamos bajar hasta $\psi (\Omega ^{\Omega ^{3}})$ , desde allí hasta $\psi (\Omega ^{\Omega ^{2}\psi (0)})$ , entonces $\psi (\Omega ^{\Omega ^{2}\omega ^{\omega }})$ entonces $\psi (\Omega ^{\Omega ^{2}\omega ^{3}})$ entonces $\psi (\Omega ^{\Omega ^{2}\omega ^{2}3})$ entonces $\psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+\omega )})$ entonces $\psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+1)})$ entonces $\psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (0)})})$ entonces $\psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \omega ^{\omega ^{\omega }}})})$ y así sucesivamente. Parece como si las expresiones se volvieran cada vez más complicadas, cuando en realidad los ordinales siempre disminuyen.

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

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

Variaciones sobre el ejemplo

Haciendo que la función sea menos potente

Resulta instructivo (aunque no exactamente útil) hacer $\psi$ menos potente.

Si modificamos la definición de $\psi$ arriba para omitir la exponenciación del repertorio del cual $C(\alpha )$ se construye, luego obtenemos $\psi (0)=\omega ^{\omega }$ (ya que este es el ordinal más pequeño que no se puede construir a partir de $0$ , $1$ y $\omega$ usando solo suma y multiplicación), entonces $\psi (1)=\omega ^{\omega ^{2}}$ y de manera similar $\psi (\omega )=\omega ^{\omega ^{\omega }}$ , $\psi (\psi (0))=\omega ^{\omega ^{\omega ^{\omega }}}$ hasta que lleguemos a un punto fijo que entonces es nuestro $\psi (\Omega )=\varepsilon _{0}$ . Entonces tenemos $\psi (\Omega +1)={\varepsilon _{0}}^{\omega }$ y así sucesivamente hasta $\psi (\Omega 2)=\varepsilon _{1}$ . Dado que la multiplicación de $\Omega$ Está permitido, aún podemos formar $\psi (\Omega ^{2})=\varphi _{2}(0)$ y $\psi (\Omega ^{3})=\varphi _{3}(0)$ y así sucesivamente, pero nuestra construcción termina ahí ya que no hay manera de llegar a o más allá $\Omega ^{\omega }$ : por lo tanto, el alcance de este sistema de notación debilitado es $\psi (\Omega ^{\omega })=\varphi _{\omega }(0)$ (el valor de $\psi (\Omega ^{\omega })$ es lo mismo en nuestro sistema más débil que en nuestro sistema original, excepto que ahora no podemos ir más allá). Esto ni siquiera llega al ordinal de Feferman-Schütte.

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

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

En ambos casos, encontramos que la limitación en el debilitado $\psi$ La función no proviene tanto de las operaciones permitidas en los ordinales contables como de los ordinales incontables que nos permitimos denotar.

Ir más allá del orden Bachmann-Howard

Sabemos que $\psi (\varepsilon _{\Omega +1})$ es el ordinal Bachmann-Howard. La razón por la que $\psi (\varepsilon _{\Omega +1}+1)$ no es más grande, con nuestras definiciones, es que no hay notación para $\varepsilon _{\Omega +1}$ (no pertenece a $C(\alpha )$ para cualquier $\alpha$ , siempre es el límite superior más bajo de él). Se podría intentar añadir el $\varepsilon$ función (o las funciones de Veblen de tantas variables) a las primitivas permitidas 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 no contables: no podemos usar la $\psi$ la función en sí misma porque solo produce ordinales contables (por ejemplo, $\psi (\Omega +1)$ es, $\varepsilon _{\varphi _{2}(0)+1}$ , ciertamente no $\varepsilon _{\Omega +1}$ ), por lo que la idea es imitar su definición de la siguiente manera:

Dejar

\psi _{1}(\alpha )

sea el ordinal más pequeño que no se puede expresar a partir de todos los ordinales contables y

\Omega _{2}

utilizando sumas, productos, exponenciales y el

\psi _{1}

función en sí misma (a ordinales construidos previamente menores que

\alpha

).

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

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

El $\psi _{1}$ Esta función nos proporciona un sistema de notaciones (¡ suponiendo que podamos escribir de alguna manera todos los ordinales contables!) para los ordinales incontables que se muestran a continuación. $\psi _{1}(\varepsilon _{\Omega _{2}+1})$ , que es el límite de $\psi _{1}(\Omega _{2})$ , $\psi _{1}({\Omega _{2}}^{\Omega _{2}})$ y así sucesivamente.

Ahora podemos reinsertar estas anotaciones en el original. $\psi$ función, modificada de la siguiente manera:

\psi (\alpha )

es el ordinal más pequeño que no se puede expresar desde

0

,

1

,

\omega

,

\Omega

y

\Omega _{2}

usando sumas, productos, exponenciales, el

\psi _{1}

la función y la

\psi

función en sí misma (a ordinales construidos previamente menores que

\alpha

).

Esta función modificada $\psi$ coincide con el anterior hasta (e incluyendo) $\psi (\psi _{1}(1))$ — que es el ordinal Bachmann-Howard. Pero ahora podemos ir más allá de esto, y $\psi (\psi _{1}(1)+1)$ es $\varepsilon _{\psi (\psi _{1}(1))+1}$ (el próximo $\varepsilon$ -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 $\Omega$ y $\Omega _{2}$ que a su vez se definen utilizando ciertos ordinales más allá $\Omega _{2}$ .

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

\psi (\alpha )

es el ordinal más pequeño que no se puede expresar desde

0

,

1

,

\omega

,

\Omega

y

\Omega _{2}

utilizando sumas, productos, exponenciales y el

\psi _{1}

y

\psi

función (a ordinales construidos previamente menores que

\alpha

).

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

De hecho, no hay razón para detenerse en dos niveles: usar $\omega +1$ nuevos cardenales de esta manera, $\Omega _{1},\Omega _{2},\ldots ,\Omega _{\omega }$ , obtenemos un sistema esencialmente equivalente al introducido por Buchholz, ^{[ 3 ]} la diferencia no esencial es que dado que Buchholz utiliza $\omega +1$ ordinales desde el principio, no necesita permitir la multiplicación o la exponenciación; además, Buchholz no introduce los números $1$ o $\omega$ en el sistema, ya que también serán producidos por el $\psi$ 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 sensatamente equivalente a los "diagramas ordinales" anteriores (y mucho más difíciles de comprender) de Takeuti ^{[ 5 ]} y $\theta$ funciones de Feferman: su rango es el mismo ( $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$ , que podría llamarse el ordinal Takeuti-Feferman-Buchholz, y que describe la fuerza de $\Pi _{1}^{1}$ -comprensión más inducción de barra ).

Una variante "normal"

La mayoría de las definiciones de funciones de colapso ordinal que se encuentran en la literatura reciente difieren de las que hemos presentado 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 en $\alpha$ ) es completamente equivalente a la de la función $\psi$ arriba :

Dejar

C(\alpha ,\beta )

sea el conjunto de ordinales generados a partir de

0

,

1

,

\omega

,

\Omega

y todos los ordinales menores que

\beta

aplicando recursivamente las siguientes funciones: suma ordinal, multiplicación y exponenciación, y la función

\psi {\upharpoonright _{\alpha }}

. Entonces

\psi (\alpha )

se define como el ordinal más pequeño

\rho

de tal manera que

C(\alpha ,\rho )\cap \Omega =\rho

.

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

Ahora podemos modificar la definición para que sea sutilmente diferente:

Dejar

{\tilde {C}}(\alpha ,\beta )

sea el conjunto de ordinales generados a partir de

0

,

1

,

\omega

,

\Omega

y todos los ordinales menores que

\beta

aplicando recursivamente las siguientes funciones: suma ordinal, multiplicación y exponenciación, y la función

{\tilde {\psi }}{\upharpoonright _{\alpha }}

. Entonces

{\tilde {\psi }}(\alpha )

se define como el ordinal más pequeño

\rho

de tal manera que

{\tilde {C}}(\alpha ,\rho )\cap \Omega =\rho

y

\alpha \in {\tilde {C}}(\alpha ,\rho )

.

Los primeros valores de ${\tilde {\psi }}$ coinciden con los de $\psi$ : es decir, para todos $\alpha <\zeta _{0}$ dónde $\zeta _{0}=\varphi _{2}(0)$ , tenemos ${\tilde {\psi }}(\alpha )=\psi (\alpha )$ porque la cláusula adicional $\alpha \in {\tilde {C}}(\alpha ,\rho )$ siempre está satisfecho. Pero en este punto las funciones comienzan a diferir: mientras que la función $\psi$ se queda "atascado" en $\zeta _{0}$ a pesar de $\zeta _{0}\leq \alpha \leq \Omega$ , la función ${\tilde {\psi }}$ Satisface ${\tilde {\psi }}(\zeta _{0})=\varepsilon _{\zeta _{0}+1}$ porque la nueva condición $\alpha \in {\tilde {C}}(\alpha ,\rho )$ impone ${\tilde {\psi }}(\zeta _{0})>\zeta _{0}$ Por otro lado, todavía tenemos ${\tilde {\psi }}(\Omega )=\zeta _{0}$ (porque $\Omega \in C(\alpha ,\rho )$ a pesar de $\rho$ por lo que la condición adicional no entra en juego). Nótese en particular que ${\tilde {\psi }}$ , a diferencia de $\psi$ , no es monótono, ni es continuo.

A pesar de estos cambios, el ${\tilde {\psi }}$ 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, $\psi (\Omega +1+\alpha )={\tilde {\psi }}({\tilde {\psi }}(\Omega )+\alpha )$ a pesar de $\alpha$ menos que el valor común $\psi (\Omega 2)={\tilde {\psi }}(\Omega +1)$ ).

Otras funciones de colapso ordinal similares

El ψ de Arai

La función ψ de Arai es una función de colapso 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 . $\psi _{\Omega }(\alpha )$ es una función colapsante tal que $\psi _{\Omega }(\alpha )<\Omega$ , dónde $\Omega$ representa el primer ordinal incontable (puede ser reemplazado por el ordinal Church-Kleene a costa de una dificultad técnica adicional). A lo largo de este artículo, ${\mathsf {KP\Pi _{N}}}$ representa la teoría de conjuntos de Kripke-Platek para un ${\mathsf {\Pi _{N}}}$ -reflejando el universo, $\mathbb {K} _{N}$ es el menos ${\mathsf {\Pi }}_{N-2}^{1}$ -cardinal indescriptible (puede ser reemplazado por el menos ${\mathsf {\Pi }}_{N}$ -reflejando el orden a costa de una dificultad técnica adicional), $N$ es un número natural fijo $\geq 3$ , y $\Omega _{0}=0$ .

Suponer ${\mathsf {KP\Pi _{N}}}\vdash \theta$ por un ${\mathsf {\Sigma _{1}}}$ ( $\Omega$ )-oración ${\mathsf {\theta }}$ . Entonces, existe un número finito $n$ de tal manera que para $\alpha =\psi _{\Omega }(\omega _{n}(\mathbb {K} _{N}+1))$ , $L_{\alpha }\models \theta$ También se puede demostrar que ${\mathsf {KP\Pi _{N}}}$ demuestra que cada segmento inicial $\{\alpha \in OT:\alpha <\psi _{\Omega }(\omega _{n}(\mathbb {K} _{N}+1))\};n=1,2,\ldots$ está bien fundamentado y, por lo tanto, $\psi _{\Omega }(\varepsilon _{\mathbb {K} _{N}+1})$ es el ordinal de la teoría de la demostración de ${\mathsf {KP\Pi _{N}}}$ A continuación, se pueden realizar las siguientes conversiones:

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

El ψ de Bachmann

La primera función de colapso ordinal verdadera, la de Bachmann $\psi$ Fue inventado por Heinz Bachmann , resultando algo engorroso ya que depende de secuencias fundamentales para todos los ordinales límite; y la definición original es complicada. Michael Rathjen ha sugerido una "reformulación" del sistema, que se presenta de la siguiente manera:

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

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

ψ de Buchholz

Buchholz $\psi$ es una jerarquía de funciones de un solo argumento $\psi _{\nu }:{\mathsf {On}}\rightarrow {\mathsf {On}}$ , con $\psi _{\nu }(\alpha )$ ocasionalmente abreviado como $\psi _{\nu }\alpha$ Esta función es probablemente la más conocida de todas las funciones de colapso ordinal. Su definición es la siguiente:

Definir $\Omega _{0}=1$ y $\Omega _{\nu }=\aleph _{\nu }$ para $\nu >0$ .
Dejar $P(\alpha )$ sea el conjunto de términos distintos en la forma normal de Cantor de $\alpha$ (con cada término de la forma $\omega ^{\xi }$ para $\xi \in {\mathsf {On}}$ (véase el teorema de la forma normal de Cantor )
$C_{\nu }^{0}(\alpha )=\Omega _{\nu }$
$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 \}$
$C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )$
$\psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})$

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

ψ de Buchholz extendido

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

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

ψ de Madore

Esta función de colapso ordinal era la misma que la función ψ utilizada anteriormente en este artículo; se trata de una versión más simple y eficiente de la función ψ de Buchholz , definida por David Madore. Su uso en este artículo propició su uso generalizado.

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

Esta función fue utilizada por Chris Bird, quien también inventó la siguiente función de colapso ordinal.

θ de Bird

Chris Bird ideó la siguiente notación abreviada para la función Veblen extendida. $\varphi$ :

$\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)$
$\theta (\alpha ,0)$ se abrevia $\theta (\alpha )$

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

ψ de Jäger

La ψ de Jäger es una jerarquía de funciones ordinales de un solo argumento ψ _κ indexadas por cardinales regulares no numerables κ menores que el cardinal débilmente Mahlo menos M _0, introducida por el matemático alemán Gerhard Jäger en 1984. Fue desarrollada a partir del enfoque de Buchholz.

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

ψ de 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 cardinal α-débilmente inaccesible, I ( α , β + 1) el primer cardinal α -débilmente inaccesible después de I ( α , β ) e I ( α , β ) = $sup(\{I(\alpha ,\gamma )\mid \gamma <\beta \})$ para el límite β . Restringimos $π$ a ordinales regulares no numerables de la forma I ( α , 0) o I ( α , β + 1). Entonces,

$C_{0}(\alpha ,\beta )=\beta \cup \{0\}$
$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 \}$
$C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )$
$\psi _{\pi }(\alpha )=\min(\{\beta <\pi \mid C(\alpha ,\beta )\cap \pi \subseteq \beta \})$

Ψ de Rathjen

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

M ⁰ = $K\cap {\mathsf {Lim}}$ , donde Lim denota la clase de ordinales límite.
Para α > 0, M ^α es el conjunto $\{\pi <K\mid C(\alpha ,\pi )\cap K=\pi \land \forall \xi \in C(\alpha ,\pi )\cap \alpha ,M^{\xi }{\mathsf {}}$ está estacionario en $\pi \land \alpha \in C(\alpha ,\pi )\}$
$C(\alpha ,\beta )$ es el cierre de $\beta \cup \{0,K\}$ bajo adición, $(\xi ,\eta )\rightarrow \varphi (\xi ,\eta )$ , $\xi \rightarrow \Omega _{\xi }$ dado ξ < K, $\xi \rightarrow \Xi (\xi )$ dado ξ < α, y $(\xi ,\pi ,\delta )\rightarrow \Psi _{\pi }^{\xi }(\delta )$ dado $\xi \leq \delta <\alpha$ .
$\Xi (\alpha )=\min(M^{\alpha }\cup \{K\})$ .
Para $\xi \leq \alpha$ , $\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ñaló en la introducción, el uso y la definición de las funciones de colapso ordinal están estrechamente relacionados 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 demostración.

Gerhard Jäger y Wolfram Pohlers ^{[ 6 ]} describieron el colapso de un cardinal inaccesible para describir la fuerza 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 demostra-teóricamente equivalente ^{[ 1 ]} a $\Delta _{2}^{1}$ -comprensión más inducción de barra . En términos generales, este colapso se puede obtener añadiendo la $\alpha \mapsto \Omega _{\alpha }$ la función misma a la lista de construcciones a las que el $C(\cdot )$ Se aplica el sistema de colapso.
Michael Rathjen ^{[ 7 ]} luego describió el colapso de un cardinal de Mahlo para describir la fuerza 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ó más tarde el colapso de un cardinal débilmente compacto para describir la fuerza ordinal-teórica de la teoría de conjuntos de Kripke-Platek aumentada por ciertos principios de reflexión (concentrándose en el caso de $\Pi _{3}$ -reflexión). En términos muy generales, esto procede introduciendo el primer cardinal $\Xi (\alpha )$ que es $\alpha$ -hiper-Mahlo y añadiendo el $\alpha \mapsto \Xi (\alpha )$ la función misma para el sistema colapsado.
En un artículo de 2015, Toshiyasu Arai creó funciones de colapso ordinal. $\psi _{\pi }^{\vec {\xi }}$ para un vector de ordinales $\xi$ , que colapsan $\Pi _{n}^{1}$ - cardenales indescriptibles para $n>0$ Estos se utilizan para llevar a cabo el análisis ordinal de la teoría de conjuntos de Kripke-Platek aumentada por $\Pi _{n+2}$ -principios de reflexión. ^{[ 9 ]}
Rathjen ha investigado el colapso de cardinales aún más grandes, con el objetivo final de lograr un análisis ordinal de $\Pi _{2}^{1}$ -comprensión (que es teóricamente equivalente a la ampliación de Kripke-Platek por $\Sigma _{1}$ -separación). ^{[ 10 ]}

Notas

1 2 Rathjen, 1995 (Bull. Symbolic Logic)
↑ Kahle, 2002 (Síntesis)
1 2 Buchholz, 1986 (Ann. Pure Appl. Logic)
↑ Rathjen, 2005 (diapositivas de Fischbachau)
^ Takeuti, 1967 (Ann. Matemáticas).
↑ Jäger & Pohlers, 1983 (Bayer. Akad. Wiss. Math.-Natur. Kl. Sitzungsber.)
↑ Rathjen, 1991 (Arch. Math. Logic)
↑ Rathjen, 1994 (Ann. Pure Appl. Logic)
↑ T. Arai, Un análisis simplificado de la reflexión de primer orden (2015).
↑ 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 del análisis clásico". Annals of Mathematics . 86 (2): 299– 348. doi : 10.2307/1970691 . JSTOR 1970691 .
Jäger, Gerhard; Pohlers, Wolfram (1983). "Eine beweistheoretische Untersuchung von ( $\Delta _{2}^{1}$ -CA)+(BI) und verwandter Systeme". Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte . 1982 : 1– 28.
Buchholz, Wilfried (1986). "Un nuevo sistema de funciones ordinales de 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 de la teoría de la demostración de KPM". Archive for Mathematical Logic . 30 ( 5– 6): 377– 403. doi : 10.1007/BF01621475 . S2CID 9376863 .
Rathjen, Michael (1994). "Teoría de la demostración de la reflexión" (PDF) . Anales de lógica pura y aplicada . 68 (2): 181– 224. doi : 10.1016/0168-0072(94)90074-4 . Archivado del original (PDF) el 21 de octubre de 2020. Consultado el 10 de mayo de 2008 .
Rathjen, Michael (1995). "Avances recientes en el análisis ordinal: $\Pi _{2}^{1}$ -CA y sistemas relacionados" . The Bulletin of Symbolic Logic . 1 (4): 468– 485. doi : 10.2307/421132 . JSTOR 421132. S2CID 10648711 .
Kahle, Reinhard (2002). "Teoría de la demostración matemática a la luz del análisis ordinal". Synthese . 133 ( 1–2 ): 237–255 . doi : 10.1023/A:1020892011851 . S2CID 45695465 .
Rathjen, Michael (2005). "An ordinal analysis of stability" . Archive for Mathematical Logic . 44 : 1–62 . CiteSeerX 10.1.1.15.9786 . doi : 10.1007/s00153-004-0226-2 . S2CID 2686302. Archivado del original el 20 de diciembre de 2022. Consultado el 10 de mayo de 2008 .
Rathjen, Michael (agosto de 2005). "Teoría de la demostración: Parte III, Teoría de conjuntos de Kripke-Platek" (PDF) . Archivado del original (PDF) el 12 de junio de 2007. Recuperado el 17 de abril de 2008 .(Diapositivas de una charla impartida en Fischbachau)

[Rathjen-survey-1] 1 2 Rathjen, 1995 (Bull. Symbolic Logic)

[Kahle-2] Kahle, 2002 (Síntesis)

[Buchholz-3] 1 2 Buchholz, 1986 (Ann. Pure Appl. Logic)

[Rathjen-slides-part3-4] Rathjen, 2005 (diapositivas de Fischbachau)

[5] Takeuti, 1967 (Ann. Matemáticas).

[6] Jäger & Pohlers, 1983 (Bayer. Akad. Wiss. Math.-Natur. Kl. Sitzungsber.)

[7] Rathjen, 1991 (Arch. Math. Logic)

[8] Rathjen, 1994 (Ann. Pure Appl. Logic)

[9] T. Arai, Un análisis simplificado de la reflexión de primer orden (2015).

[10] Rathjen, 2005 (Arquitectura, Matemáticas, Lógica)

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

Un ejemplo que conduce al ordinal Bachmann-Howard

Definición

Cálculo de los valores de ψ

Inicio predictivo

Primeros valores impredicativos

Valores de ψ hasta el ordinal de Feferman-Schütte

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

Notaciones ordinales hasta el ordinal de Bachmann-Howard

Una nota sobre las representaciones básicas

Algunas propiedades de ψ

La notación ordinal

Ejemplos

Condiciones para la canonicidad

Secuencias estándar para notaciones ordinales

Un proceso de terminación

Variaciones sobre el ejemplo

Haciendo que la función sea menos potente

Ir más allá del orden Bachmann-Howard

Una variante "normal"

Otras funciones de colapso ordinal similares

El ψ de Arai

El ψ de Bachmann

ψ de Buchholz

ψ de Buchholz extendido

ψ de Madore

θ de Bird

ψ de Jäger

ψ de Jäger simplificado

Ψ de Rathjen

Cardenales grandes colapsando

Notas

Referencias

Articulos relacionados