Aritmética ordinal

En el campo matemático de la teoría de conjuntos , la aritmética ordinal incluye operaciones binarias sobre números ordinales, como la suma, la multiplicación y la potenciación. Cada una puede definirse de dos maneras diferentes: construyendo un conjunto explícito bien ordenado que represente el resultado de la operación o utilizando la recursión transfinita . Además de estas operaciones estándar para ordinales, también existen las operaciones aritméticas "naturales" , que generalmente se describen utilizando la forma normal de Cantor para ordinales, y las operaciones de nimber .

Los números ordinales son como los números naturales {0, 1, 2, ...} pero se extienden hasta el infinito ω y más allá ω +1, ω +2, ..., ω + ω , ω + ω +1, ... . Las operaciones aritméticas estándar y las operaciones aritméticas naturales sobre los ordinales finitos son las mismas que las operaciones correspondientes sobre los números naturales, pero las operaciones aritméticas sobre los ordinales infinitos son más complicadas.

La suma de dos conjuntos bien ordenados S y T es el ordinal que representa la variante del orden lexicográfico con la posición menos significativa primero, en la unión de los productos cartesianos S × {0} y T × {1} . De esta manera, cada elemento de S es menor que cada elemento de T , las comparaciones dentro de S mantienen el orden que ya tienen, y lo mismo ocurre con las comparaciones dentro de T.

La definición de suma ordinal α + β también puede darse mediante recursión transfinita sobre β . Cuando el sumando derecho β = 0 , la suma da α + 0 = α para cualquier α . Para β > 0 , el valor de α + β es el ordinal más pequeño estrictamente mayor que la suma de α y δ para todo δ < β . Escribiendo los casos de ordinales sucesores y límite por separado:

• α + 0 = α
• α + S ( β ) = S ( α + β ) , donde S denota lafunción sucesora .
• α + β =${\displaystyle \bigcup _{\delta <\beta }}$( α + δ ) cuando β es un ordinal límite .

La suma ordinal de los números naturales es igual que la suma estándar. El primer ordinal transfinito es ω , el conjunto de todos los números naturales, seguido de ω + 1 , ω + 2 , etc. El ordinal ω + ω se obtiene mediante dos copias de los números naturales ordenadas de la forma habitual y la segunda copia completamente a la derecha de la primera. Escribiendo 0 ′ < 1 ′ < 2 ′ < ... para la segunda copia, ω + ω se ve así:

0 < 1 < 2 < 3 < ... < 0 ′ < 1 ′ < 2 ′ < ...

Esto es diferente de ω porque en ω solo 0 no tiene un predecesor directo, mientras que en ω + ω los dos elementos 0 y 0 ′ no tienen predecesores directos.

El producto cartesiano , S × T , de dos conjuntos bien ordenados S y T puede ordenarse mediante una variante del orden lexicográfico que coloca primero la posición menos significativa. En efecto, cada elemento de T se reemplaza por una copia disjunta de S. El tipo de orden del producto cartesiano es el ordinal que resulta de multiplicar los tipos de orden de S y T.

La definición de multiplicación ordinal también puede darse mediante recursión transfinita sobre β . Cuando el factor derecho β = 0 , la multiplicación da α · 0 = 0 para cualquier α . Para β > 0 , el valor de α · β es el ordinal más pequeño mayor o igual que ( α · δ ) + α para todo δ < β . Escribiendo los casos de ordinales sucesores y límite por separado:

• α · 0 = 0 .
• α · S ( β ) = ( α · β ) + α , para un ordinal sucesor S ( β ) .
• α · β =${\displaystyle \bigcup _{\delta <\beta }}$( α · δ ) , cuando β es un ordinal límite.

Como ejemplo, aquí está la relación de orden para ω · 2 :

0 ₀ < 1 ₀ < 2 ₀ < 3 ₀ < ... < 0 ₁ < 1 ₁ < 2 ₁ < 3 ₁ < ... ,

que tiene el mismo tipo de orden que ω + ω . En cambio, 2 · ω se ve así:

0 ₀ < 1 ₀ < 0 ₁ < 1 ₁ < 0 ₂ < 1 ₂ < 0 ₃ < 1 ₃ < ...

y después de cambiarle el nombre, se ve igual que ω . Por lo tanto, ω · 2 = ω + ω ≠ ω = 2 · ω , lo que demuestra que la multiplicación de ordinales no es en general conmutativa, cf. imágenes.

Al igual que ocurre con la suma, la multiplicación ordinal de los números naturales es igual que la multiplicación estándar.

La definición de exponenciación mediante tipos de orden se explica más fácilmente utilizando la definición de Von Neumann de un ordinal como el conjunto de todos los ordinales más pequeños . Luego, para construir un conjunto de tipo de orden α ^β, consideremos el conjunto de todas las funciones f  : β → α tales que f ( x ) = 0 para todos los elementos x ∈ β excepto un número finito (esencialmente, consideramos las funciones con soporte finito ). Este conjunto está ordenado lexicográficamente con la posición menos significativa primero: es decir, escribimos f < g si y solo si f ( x ) < g ( x ) para el valor x = max{ y | f ( y ) ≠ g ( y )} . Este es un buen orden y su tipo de orden es un número ordinal, α ^β .

La definición de exponenciación ordinal también puede darse mediante recursión transfinita sobre el exponente β . Cuando el exponente β = 0 , la exponenciación da α₀ ⁼ 1 para cualquier α , incluyendo α = 0. Para β > 0 , el valor de αβ es el ^ordinal más pequeño mayor o igual que αδ ^· α para todo δ < β . Escribiendo los casos de ordinales sucesores y límite por separado:

• α ⁰ = 1 .
• α ^{S ( β )} = ( α ^β ) · α , para un ordinal sucesor S ( β ) .
• α ^β =${\displaystyle \bigcup _{0<\delta <\beta }}$( α ^δ ) , cuando β es un ordinal límite.

Ambas definiciones se simplifican considerablemente si el exponente β es un número finito: α ^β es entonces simplemente el producto de β copias de α ; por ejemplo, ω ³ = ω · ω · ω , y los elementos de ω ³ pueden considerarse como ternas de números naturales, ordenados lexicográficamente con el menos significativo en primer lugar. Esto concuerda con la exponenciación ordinaria de los números naturales.

Pero para exponentes infinitos, la definición puede no ser obvia. Por ejemplo, α ^ω puede identificarse con un conjunto de secuencias finitas de elementos de α , debidamente ordenadas. La ecuación 2 ^ω = ω expresa el hecho de que las secuencias finitas de ceros y unos pueden identificarse con números naturales, utilizando el sistema numérico binario . El ordinal ω ^ω puede verse como el tipo de orden de secuencias finitas de números naturales; cada elemento de ω ^ω (es decir, cada ordinal menor que ω ^ω ) puede escribirse de forma única en la forma ω ^{n ₁} ⋅ c ₁ + ω ^{n ₂} ⋅ c ₂ + ⋯ + ω ^{n _k} ⋅ c _k , donde k , n ₁ , ..., n _k son números naturales, c ₁ , ..., c _k son números naturales distintos de cero, y n ₁ > ... > n _k .

Lo mismo es cierto en general: cada elemento de α ^β (es decir, cada ordinal menor que α ^β ) puede escribirse de forma única en la forma α ^{b ₁} ⋅ a ₁ + α ^{b ₂} ⋅ a ₂ + ⋯ + α ^{b _k} ⋅ a _k donde k es un número natural, b ₁ , ..., b _k son ordinales menores que β con b ₁ > ... > b _k , y a ₁ , ..., a _k son ordinales no nulos menores que α . Esta expresión corresponde a la función f  : β → α que envía b _i a a _i para i = 1, ..., k y envía todos los demás elementos de β a 0 .

Aunque se utiliza la misma notación de exponentes para la exponenciación ordinal y la exponenciación cardinal , ambas operaciones son bastante diferentes y no deben confundirse. La exponenciación cardinal A ^B se define como el número cardinal del conjunto de todas las funciones B → A , mientras que la exponenciación ordinal α ^β solo contiene las funciones β → α con soporte finito, generalmente un conjunto de cardinalidad mucho menor. Para evitar confusiones entre la exponenciación ordinal y la cardinal, se pueden usar símbolos para los ordinales (p. ej., ω ) en la primera y símbolos para los cardinales (p. ej., ℵ ₀ ) en la segunda.

Existen operaciones ordinales que continúan la secuencia iniciada por la suma, la multiplicación y la exponenciación, incluyendo versiones ordinales de la tetración y otras hiperoperaciones . Véase también función de Veblen .

Todo número ordinal α puede escribirse de forma única como ω ^{β ₁} ⋅ c ₁ + ω ^{β ₂} ⋅ c ₂ + ⋯ + ω ^{β _k} ⋅ c _k , donde k es un número natural, c ₁ , c ₂ , ..., c _k son números naturales distintos de cero, y β ₁ > β ₂ > ... > β _k ≥ 0 son números ordinales. El caso degenerado α = 0 ocurre cuando k = 0 , lo que requiere que no haya β s ni c s. Esta descomposición de α se llama la forma normal de Cantor de α , y puede considerarse el sistema de numeración posicional de base ω . El exponente más alto β ₁ se llama grado de α , y satisface β ₁ ≤ α . La igualdad β ₁ = α se cumple si y solo si α = ω ^α . En ese caso, la forma normal de Cantor no logra expresar el ordinal en términos de otros más pequeños; esto puede ocurrir como se explica a continuación.

Para comparar dos ordinales escritos en forma normal de Cantor, primero se compara β₁, luego c₁, luego β₂ _, luego c₂ , y _{así sucesivamente} . En la primera aparición de la desigualdad, el ordinal con el componente mayor es el mayor. Si son iguales hasta _que uno termina antes que el otro, entonces el que termina primero es el menor.

La forma normal de Cantor nos permite expresar de forma única —y ordenar— los ordinales α que se construyen a partir de los números naturales mediante un número finito de operaciones aritméticas de suma, multiplicación y exponenciación en base ω : en otras palabras, suponiendo que β ₁ < α en la forma normal de Cantor, también podemos expresar los exponentes β _i en la forma normal de Cantor, y haciendo la misma suposición para β _i que para α y así sucesivamente recursivamente, obtenemos un sistema de notación para estos ordinales (por ejemplo,

ω ^{ω ω 7 ⋅6+ ω +42 ⋅1729+ ω 9 +88} ⋅3 + ω ^{ω ω} ⋅5 + 65537

denota un ordinal).

Ernst Jacobsthal demostró que los ordinales satisfacen una forma del teorema de factorización única : todo ordinal distinto de cero puede escribirse como producto de un número finito de ordinales primos. Esta factorización en ordinales primos no es única en general, pero existe una factorización "mínima" en primos que es única salvo por un cambio en el orden de los factores primos finitos ( Sierpiński 1958 ) .

Un ordinal primo es un ordinal mayor que 1 que no puede escribirse como producto de dos ordinales menores. Algunos de los primeros primos son 2 , 3 , 5 , ..., ω , ω + 1 , ω² + 1 , ^ω³ + 1 ^, ..., ω² + ^ω² , ω² + ω² ⁺ 1 , ω² + ω² ^{+ 1} + 1 , ... Hay tres tipos de ordinales primos:

• Los números primos finitos 2 , 3 , 5 , ...
• Los ordinales de la forma ω ^{ω α} para cualquier ordinal α . Estos son los ordinales primos que son límites, y son los números delta , los ordinales transfinitos que son cerrados bajo la multiplicación.
• Los ordinales de la forma ω ^α + 1 para cualquier ordinal α > 0. Estos son los primos sucesores infinitos, y son los sucesores de los números gamma , los ordinales aditivamente indescomponibles.

La factorización en números primos no es única: por ejemplo, 2 ⋅ 3 = 3 ⋅ 2 , 2 ⋅ ω = ω , ( ω + 1) ⋅ ω = ω ⋅ ω y ω ⋅ ω ^ω = ω ^ω . Sin embargo, existe una única factorización en números primos que satisface las siguientes condiciones adicionales:

• Todo número primo límite debe aparecer antes que cualquier número primo sucesor.
• Si dos números primos consecutivos de la factorización prima son ambos límites o ambos finitos, el segundo debe ser menor o igual que el primero.

Esta factorización prima se puede leer fácilmente utilizando la forma normal de Cantor de la siguiente manera:

• Primero escribe el ordinal como un producto α ⋅ β , donde α es la potencia más pequeña de ω en la forma normal de Cantor y β es un sucesor.
• Si α = ω ^γ, entonces escribir γ en forma normal de Cantor da una expansión de α como producto de primos límite.
• Ahora veamos la forma normal de Cantor de β . Si β = ω ^λ ⋅ m + ω ^μ ⋅ n + términos más pequeños, entonces β = ( ω ^μ ⋅ n + términos más pequeños) ⋅ ( ω ^{λ − μ} + 1) ⋅ m es un producto de un ordinal más pequeño y un número primo y un número natural m . Repitiendo esto y factorizando los números naturales en primos se obtiene la factorización prima de β .

Así pues, la factorización de la forma normal de Cantor ordinal

ω ^{α ₁} ⋅ n ₁ + ⋯ + ω ^{α _k} ⋅ n _k (con α ₁ > ... > α _k )

en un producto mínimo de números primos y naturales infinitos es

( ω ^{ω β ₁} ⋅ ⋯ ⋅ ω ^{ω β _m} ) ⋅ n _k ⋅ ( ω ^{α _{k −1} −α _k} + 1) ⋅ n _{k −1} ⋅ ⋯ ⋅ ( ω ^{α ₁ − α ₂} + 1) ⋅ n ₁

donde cada n _i debe ser reemplazado por su factorización en una secuencia no creciente de primos finitos y

α _k = ω ^{β ₁} + ⋯ + ω ^{β _m} con β ₁ ≥ ... ≥ β _m .

Como se mencionó anteriormente, la forma normal de Cantor de los ordinales menores que ε ₀ se puede expresar en un alfabeto que contiene solo los símbolos de función para la suma, la multiplicación y la exponenciación, así como símbolos constantes para cada número natural y para ω . Podemos prescindir de los infinitos numerales usando solo el símbolo constante 0 y la operación de sucesor, S (por ejemplo, el número natural 3 puede expresarse como S ( S ( S (0))) . Esto describe una notación ordinal : un sistema para nombrar ordinales sobre un alfabeto finito. Este sistema particular de notación ordinal se llama colección de expresiones ordinales aritméticas , y puede expresar todos los ordinales por debajo de ε ₀ , pero no puede expresar ε ₀ . Hay otras notaciones ordinales capaces de capturar ordinales mucho más allá de ε ₀ , pero debido a que solo hay una cantidad numerable de cadenas de longitud finita sobre cualquier alfabeto finito, para cualquier notación ordinal dada habrá ordinales por debajo de ω ₁ (el primer ordinal no numerable ) que no se pueden expresar. Dichos ordinales se conocen como ordinales numerables grandes .

Las operaciones de suma, multiplicación y potenciación son ejemplos de funciones ordinales recursivas primitivas , y se pueden utilizar funciones ordinales recursivas primitivas más generales para describir ordinales de mayor tamaño.

Las operaciones de suma natural y producto natural sobre ordinales fueron definidas en 1906 por Gerhard Hessenberg , y a veces se denominan suma (o producto) de Hessenberg ( Sierpiński 1958 ) . La suma natural de α y β se suele denotar por α ⊕ β o α # β , y el producto natural por α ⊗ β o α ⨳ β .

La suma natural y el producto se definen de la siguiente manera. Sean α = ω ^{α ₁} + ⋯ + ω ^{α _k} y β = ω ^{β ₁} + ⋯ + ω ^{β _ℓ} estar en forma normal de Cantor (es decir, α ₁ ≥ ... ≥ α _k y β ₁ ≥ ... ≥ β _ℓ ). Sean γ ₁ , ..., γ _{k + ℓ} los exponentes α ₁ , ..., α _k , β ₁ , ..., β _ℓ ordenados en orden no creciente. Entonces α ⊕ β se define como

α ⊕ β = ω ^{γ ₁} + ⋯ + ω ^{γ _{k + ℓ}} .

El producto natural de α y β se define como

α ⊗ β =${\displaystyle \bigoplus _{\begin{aligned}&1\leq i\leq k\\&1\leq j\leq \ell \end{aligned}}}$ω ^{α _i ⊕ β _j} .

Por ejemplo, supongamos α = ω ^{ω ω} + ω y β = ω ^ω + ω ⁵ . Entonces α ⊕ β = ω ^{ω ω} + ω ^ω + ω ⁵ + ω , mientras que α + β = ω ^{ω ω} + ω ^ω + ω ⁵ . Y α ⊗ β = ω ^{ω ω + ω} + ω ^{ω ω +5} + ω ^{ω +1} + ω ⁶ , mientras que α ⋅ β = ω ^{ω ω + ω} + ω ^{ω ω +5} .

La suma natural y el producto son conmutativos y asociativos, y el producto natural se distribuye sobre la suma natural. Las operaciones también son monótonas, en el sentido de que si α < β entonces α ⊕ γ < β ⊕ γ ; si α ≤ β entonces α ⊗ γ ≤ β ⊗ γ ; y si α < β y γ > 0 entonces α ⊗ γ < β ⊗ γ .

Tenemos${\displaystyle \underbrace {\alpha \oplus \cdots \oplus \alpha } _{n}=\alpha \otimes n}$.

Siempre tenemos α + β ≤ α ⊕ β y α ⋅ β ≤ α ⊗ β . Si tanto α < ω ^γ como β < ω ^γ entonces α ⊕ β < ω ^γ . Si tanto α < ω ^{ω γ} como β < ω ^{ω γ} entonces α ⊗ β < ω ^{ω γ} .

La suma y el producto naturales no son continuos. Por ejemplo, si la suma natural fuera continua, entonces lim _{n < ω} (1 ⊕ n ) = 1 ⊕ ω , pero el lado izquierdo es igual a ω y el lado derecho es igual a ω + 1 . De manera similar, si el producto natural fuera continuo, lim _{n < ω} (2 ⊗ n ) = 2 ⊗ ω , pero el lado izquierdo es igual a ω y el lado derecho es igual a ( ω ⁰ + ω ⁰ ) ⊗ ω ¹ = ω ¹ + ω ¹ = ω · 2 .

La suma y el producto naturales son los mismos que la suma y la multiplicación (restringidas a los ordinales) del campo de números surrealistas de John Conway .

Las operaciones naturales aparecen en la teoría de órdenes parciales bien definidas ; dados dos órdenes parciales bien definidas S y T , de tipos ( linealizaciones máximas ) o ( S ) y o ( T ) , el tipo de la unión disjunta es o ( S ) ⊕ o ( T ) , mientras que el tipo del producto directo es o ( S ) ⊗ o ( T ) . ^{[ 2 ]} Se puede tomar esta relación como una definición de las operaciones naturales eligiendo S y T como ordinales α y β ; de modo que α ⊕ β es el tipo de orden máximo de un orden total que extiende la unión disjunta (como un orden parcial) de α y β ; mientras que α ⊗ β es el tipo de orden máximo de un orden total que extiende el producto directo (como un orden parcial) de α y β . ^{[ 3 ]} Una aplicación útil de esto es cuando α y β son ambos subconjuntos de algún orden total mayor; entonces su unión tiene un tipo de orden como máximo α ⊕ β . Si ambos son subconjuntos de algún grupo abeliano ordenado , entonces su suma tiene un tipo de orden como máximo α ⊗ β .

También podemos definir la suma natural α ⊕ β por recursividad transfinita simultánea en α y β , como el ordinal más pequeño estrictamente mayor que la suma natural de α y γ para todo γ < β y de γ y β para todo γ < α . ^{[ 4 ]} De manera similar, podemos definir el producto natural α ⊗ β por recursión transfinita simultánea en α y β , como el ordinal γ más pequeño tal que ( α ⊗ δ ) ⊕ ( ε ⊗ β ) < γ ⊕ ( ε ⊗ δ ) para todo ε < α y δ < β . ^{[ 4 ]} Además, consulte el artículo sobre números surrealistas para conocer la definición de multiplicación natural en ese contexto; Sin embargo, utiliza la sustracción surrealista, que no está definida en términos ordinales.

La suma natural es asociativa y conmutativa. Siempre es mayor o igual que la suma usual, pero puede ser estrictamente mayor. Por ejemplo, la suma natural de ω y 1 es ω + 1 (la suma usual), pero esta también es la suma natural de 1 y ω . El producto natural es asociativo y conmutativo y se distribuye sobre la suma natural. El producto natural siempre es mayor o igual que el producto usual, pero puede ser estrictamente mayor. Por ejemplo, el producto natural de ω y 2 es ω · 2 (el producto usual), pero este también es el producto natural de 2 y ω .  

Bajo la suma natural, los ordinales pueden identificarse con los elementos del monoide conmutativo libre generado por los números gamma ω ^α . Bajo la suma y multiplicación naturales, los ordinales pueden identificarse con los elementos del semianillo conmutativo libre generado por los números delta ω ^{ω α} . Los ordinales no tienen factorización única en primos bajo el producto natural. Si bien el anillo completo de polinomios sí tiene factorización única, el subconjunto de polinomios con coeficientes no negativos no la tiene: por ejemplo, si x es cualquier número delta, entonces

x ⁵ + x ⁴ + x ³ + x ² + x + 1 = ( x + 1) ( x ⁴ + x ² + 1) = ( x ² + x + 1) ( x ³ + 1)

tiene dos expresiones incompatibles como producto natural de polinomios con coeficientes no negativos que no se pueden descomponer más.

Existen operaciones aritméticas con ordinales gracias a la correspondencia biunívoca entre ordinales y números . Tres operaciones comunes con números son la suma de números, la multiplicación de números y el valor mínimo excluido (MEX) . La suma de números es una generalización de la operación OR exclusiva bit a bit aplicada a números naturales. El MEX de un conjunto de ordinales es el ordinal más pequeño que no está presente en dicho conjunto.

• Calculadora ordinal ordCalc en Wayback Machine (archivada el 5 de junio de 2021)