Bien ordenado

En matemáticas , un bien orden (o bien ordenamiento o relación de bien orden ) en un conjunto $S$ es un ordenamiento total en $S$ con la propiedad de que todo subconjunto no vacío de $S$ tiene un elemento mínimo en este ordenamiento. El conjunto $S$ junto con el ordenamiento se denomina entonces conjunto bien ordenado (o woset ). ^[¹^] En algunos artículos académicos y libros de texto, estos términos se escriben como bienordenado , bien ordenado y bien ordenamiento o bien orden , bien ordenado y bien ordenamiento .

Todo conjunto ordenado no vacío tiene un elemento mínimo. Cada elemento $s$ de un conjunto ordenado, excepto un posible elemento máximo , tiene un sucesor único (elemento siguiente), a saber, el elemento mínimo del subconjunto de todos los elementos mayores que $s$ . Puede haber elementos, además del elemento mínimo, que no tengan predecesor (véase el apartado Números naturales más adelante para un ejemplo). Un conjunto ordenado $S$ contiene, para cada subconjunto T $con$ una cota superior , una cota superior mínima , a saber, el elemento mínimo del subconjunto de todas las cotas superiores de $T$ en $S.$

Si ≤ es un ordenamiento no estricto , entonces < es un ordenamiento estricto. Una relación es un ordenamiento estricto si y solo si es un orden total estricto bien fundado . La distinción entre órdenes estrictos y no estrictos suele pasarse por alto, ya que son fácilmente interconvertibles.

Todo conjunto bien ordenado es isomorfo de orden único a un único número ordinal , denominado tipo de orden del conjunto bien ordenado. El teorema del buen ordenamiento , equivalente al axioma de elección , establece que todo conjunto puede ser bien ordenado. Si un conjunto es bien ordenado (o incluso si simplemente admite una relación bien fundada ), la técnica de demostración de inducción transfinita puede utilizarse para probar que una afirmación dada es verdadera para todos los elementos del conjunto.

La observación de que los números naturales están bien ordenados según la relación usual de "menor que" se conoce comúnmente como el principio de buen ordenamiento (para los números naturales).

Ejemplos y contraejemplos

Números naturales

El orden estándar ≤ de los números naturales es un buen orden:

{\begin{matrix}0&1&2&3&4&5&6&7&8&9&10&\dots \end{matrix}}

Este ordenamiento de pozos tiene la propiedad adicional de que cada número natural distinto de cero tiene un predecesor único. Su tipo de orden es $ω$ , el primer ordinal infinito.

Otro buen ordenamiento de los números naturales viene dado por la definición de que todos los números pares son menores que todos los números impares, y el ordenamiento habitual se aplica dentro de los pares y los impares:

{\begin{matrix}0&2&4&6&8&\dots &1&3&5&7&9&\dots \end{matrix}}

Este es un conjunto bien ordenado de tipo orden $ω + ω$ . Cada elemento tiene un sucesor (no hay un elemento mayor). Dos elementos carecen de predecesor: 0 y 1.

Números enteros

A diferencia del orden estándar ≤ de los números naturales , el orden estándar ≤ de los enteros no es un buen orden, ya que, por ejemplo, el conjunto de enteros negativos no contiene un elemento mínimo.

La siguiente relación binaria $R$ es un ejemplo de buen ordenamiento de los enteros: $x R y$ si y solo si se cumple una de las siguientes condiciones:

$x = 0$
$x$ es positivo e $y$ es negativo.
$x$ e $y$ son ambos positivos, y $x \leq y$
$x$ e $y$ son ambos negativos, y $| x | \leq | y |$

Esta relación $R$ puede visualizarse de la siguiente manera:

{\begin{matrix}0&1&2&3&4&\dots &-1&-2&-3&\dots \end{matrix}}

$R$ es isomorfo al número ordinal $ω + ω$ .

Otra relación para ordenar correctamente los números enteros es la siguiente definición: $x\leq _{z}y$ si y solo si

|x|<|y|\qquad {\text{o}}\qquad |x|=|y|{\text{ y }}x\leq y.

Este orden de pozos se puede visualizar de la siguiente manera:

{\begin{matrix}0&-1&1&-2&2&-3&3&-4&4&\dots \end{matrix}}

Este tiene el tipo de orden $ω$ .

Números racionales

El orden estándar ≤ de los números racionales no es un buen orden, y a diferencia de los enteros, esto sigue siendo cierto para los números racionales no negativos, ya que, por ejemplo, el conjunto $\{1/n\,|\,n=1,2,3,\dots \}$ no tiene elemento mínimo. Sin embargo, dado que el conjunto de números racionales ℚ es numerable , existe un buen ordenamiento de ℚ que es isomorfo en orden al ordenamiento estándar de los números naturales y, por lo tanto, tiene el tipo de orden $ω$ .

Existen muchos subconjuntos de ℚ que están bien ordenados bajo el orden estándar ≤ (el conjunto de los números naturales es un ejemplo trivial). Otros ejemplos incluyen:

El conjunto de números $\{-2^{-n}\,|\,0\leq n<\omega \}$ es un subconjunto acotado de ℚ con tipo de orden $ω$ bajo el ordenamiento estándar:

{\begin{matrix}-1&-1/2&-1/4&-1/8&-1/16&\dots \end{matrix}}

El conjunto de números $\{-2^{-n}-2^{-mn}\,|\,0\leq m,n<\omega \}$ tiene tipo de orden $ω 2$ :

{\begin{matrix}-1-1&-1-1/2&-1-1/4&\dots \\-1=-1/2-1/2&-1/2-1/4&-1/2-1/8&\dots \\-1/2=-1/4-1/4&-1/4-1/8&-1/4-1/16&\dots \\\dots &\dots &\dots &\dots \end{matrix}}

El conjunto anterior es el conjunto de puntos límite dentro del conjunto. Dentro del conjunto de los números reales, ya sea con la topología ordinaria o la topología de orden, el 0 también es un punto límite del conjunto. También es un punto límite del conjunto de puntos límite.

El conjunto de números $\{-2^{-n}\,|\,0\leq n<\omega \}\cup \{1\}$ tiene tipo de orden $ω + 1$ :

{\begin{matrix}-1&-1/2&-1/4&-1/8&-1/16&\dots &1\end{matrix}}

Con la topología de orden de este conjunto, 1 es un punto límite del conjunto, a pesar de estar separado del único punto límite 0 bajo la topología ordinaria de los números reales.

De hecho, para cada ordinal numerable $α$ , existe un subconjunto de ℚ con tipo de orden $α$ bajo el ordenamiento estándar. Este es un caso especial del teorema que establece que todo ordenamiento lineal numerable $A$ puede incrustarse preservando el orden en $(ℚ, \leq)$ , lo cual puede probarse enumerando los elementos de $A$ como una secuencia . $a_{1},a_{2},a_{3},\ldots$ y asignando secuencialmente un número $x_{n}\in \mathbb {Q}$ a cada uno $a_{n}$ de tal manera que el orden entre los elementos finitos $a_{1},a_{2},\ldots ,a_{n}$ Se conserva.^{[ 2 ]}

Reales

El orden estándar ≤ de cualquier intervalo real no es un buen orden, ya que, por ejemplo, el intervalo abierto ⁠ $(0,1)\subseteq [0,1]$ ⁠ no contiene un elemento mínimo. De hecho, aunque el teorema del buen ordenamiento (equivalente al axioma de elección ) implica que hay un buen ordenamiento de los reales, los axiomas ZFC no son suficientes para probar la existencia de un buen ordenamiento definible (por una fórmula) de los reales, incluso si se asume que la hipótesis del continuo generalizado es verdadera.^{[ 3 ]} Sin embargo, es consistente con ZFC que exista un buen ordenamiento definible de los reales; por ejemplo, es consistente con ZFC que V=L , y se sigue de ZFC+V=L que una fórmula particular ordena bien los reales, o de hecho cualquier conjunto.

Un subconjunto no numerable de los números reales con el orden estándar ≤ no puede ser un buen orden: Supongamos que $X$ es un subconjunto de ⁠ $\mathbb {R}$ ⁠ bien ordenado por ≤ . Para cada $x$ en $X$ , sea $s (x)$ el sucesor de $x$ en el orden ≤ en $X$ (a menos que $x$ sea el elemento más grande de $X$ ). Todos los intervalos de la forma $(x, s (x))$ son no vacíos y disjuntos. Dado que cada intervalo abierto de este tipo contiene un número racional, y ℚ es numerable, solo puede haber una cantidad numerable de tales intervalos. Y dado que $(x, s (x))$ está definido para todo $x \in X$ excepto posiblemente para un elemento más grande, $X$ debe ser numerable.

Formulaciones equivalentes

Si un conjunto es totalmente ordenado , entonces las siguientes expresiones son equivalentes entre sí:

El conjunto está bien ordenado. Es decir, cada subconjunto no vacío tiene un elemento mínimo.
La inducción transfinita funciona para todo el conjunto ordenado.
Toda secuencia estrictamente decreciente de elementos del conjunto debe terminar después de un número finito de pasos (suponiendo el axioma de elección dependiente ).
Cada subordenamiento es isomorfo a un segmento inicial (véase la sección « segmentos iniciales» más abajo).

Segmentos iniciales

Un segmento inicial , determinado por un elemento $x$ de un poset $X$ , es un subconjunto de forma $\{y\in X\mid y<x\}$ . ^{[ 4 ]} Por convención, $X$ En sí mismo también se cuenta como un segmento inicial (impropio).

Para un conjunto bien ordenado $X$ , un subconjunto $S\subset X$ es un segmento inicial (ya sea $X$ o un segmento inicial por algún elemento) si y solo si contiene

\{y\in X\mid y<x\}

para cada $x$ en $S$ . ^{[ 5 ]}^{[ 6 ]} En otras palabras, un segmento inicial es lo mismo que un conjunto inferior en la teoría del orden y esta caracterización a veces también se toma como una definición de un segmento inicial. ^{[ 7 ]}

Los segmentos iniciales se utilizan a menudo en el estudio de conjuntos bien ordenados y conjuntos bien fundados . Por ejemplo, un número ordinal es un conjunto bien ordenado. $\alpha$ cuyos elementos son todos segmentos iniciales determinados por sí mismos; es decir, para cada elemento $x$ en $\alpha$ , tenemos:

x=\{y\in \alpha \mid y<x\}.

^{[ 8 ]}

Véase también el apartado § Números ordinales más abajo. Los segmentos iniciales también se utilizan en el enunciado del teorema de recursión transfinita .

Las propiedades de los segmentos iniciales incluyen:

Un conjunto bien ordenado nunca es isomorfo a un segmento inicial propio de sí mismo. ^{[ 9 ]} Además, dados dos conjuntos bien ordenados $X,Y$ , cualquiera $X$ es isomorfo a un segmento inicial de $Y$ o $Y$ es isomorfo a un segmento inicial de $X$ .
Un morfismo entre conjuntos bien ordenados envía segmentos iniciales a segmentos iniciales, donde un morfismo es una aplicación inyectiva que preserva el orden y cuya imagen es un segmento inicial. ^{[ 10 ]}
Los segmentos iniciales dan un orden. $\trianglelefteq$ en la clase $\operatorname {Well}$ conjuntos bien ordenados; a saber, $A\trianglelefteq B$ si y solo si $A\subset B$ es un subconjunto con el orden restringido de $B$ y $A$ es un segmento inicial de $B$ . ^{[ 11 ]} La unión de una cadena de conjuntos bien ordenados es entonces bien ordenada, donde una cadena es con respecto a $\trianglelefteq$ . ^{[ 11 ]} Para los ordinales, este ordenamiento dado por los segmentos iniciales coincide con la inclusión de conjuntos. ^{[ 12 ]}
Un conjunto con una relación binaria está bien fundado si y solo si está cubierto por segmentos iniciales bien fundados. ^{[ 13 ]}

Topología de orden

Todo conjunto bien ordenado puede convertirse en un espacio topológico dotándolo de la topología de orden .

Con respecto a esta topología, puede haber dos tipos de elementos:

puntos aislados : estos son el mínimo y los elementos con un predecesor.
puntos límite : este tipo no aparece en conjuntos finitos y puede o no aparecer en un conjunto infinito; los conjuntos infinitos sin punto límite son los conjuntos de tipo de orden $ω$ , por ejemplo, los números naturales . $\mathbb {N} .$ ⁠

Para subconjuntos podemos distinguir:

Subconjuntos con un máximo (es decir, subconjuntos que están acotados por sí mismos); este puede ser un punto aislado o un punto límite de todo el conjunto; en este último caso, puede o no ser también un punto límite del subconjunto.
Subconjuntos que no están acotados por sí mismos pero sí por el conjunto completo; no tienen máximo, pero sí un supremo fuera del subconjunto; si el subconjunto no está vacío, este supremo es un punto límite del subconjunto y, por lo tanto, también del conjunto completo; si el subconjunto está vacío, este supremo es el mínimo del conjunto completo.
Subconjuntos que no están acotados en todo el conjunto.

Un subconjunto es cofinal en el conjunto completo si y solo si no está acotado en el conjunto completo o tiene un máximo que también es el máximo del conjunto completo.

Un conjunto bien ordenado como espacio topológico es un espacio numerable de primer orden si y solo si tiene un tipo de orden menor o igual a ω ₁ ( omega-uno ), es decir, si y solo si el conjunto es numerable o tiene el tipo de orden no numerable más pequeño .

Números ordinales

Todo conjunto bien ordenado es isomorfo de orden único a un número ordinal único , llamado tipo de orden del conjunto bien ordenado. La posición de cada elemento dentro del conjunto ordenado también viene dada por un número ordinal. En el caso de un conjunto finito, la operación básica de contar , para hallar el número ordinal de un objeto en particular, o para hallar el objeto con un número ordinal particular, corresponde a asignar números ordinales uno por uno a los objetos. El tamaño (número de elementos, número cardinal ) de un conjunto finito es igual al tipo de orden. ^{[ 14 ]} El conteo en el sentido cotidiano normalmente comienza desde uno, por lo que asigna a cada objeto el tamaño del segmento inicial con ese objeto como último elemento. Nótese que estos números son uno más que los números ordinales formales según el orden isomorfo, porque son iguales al número de objetos anteriores (lo que corresponde a contar desde cero). Así, para $un n$ finito , la expresión " elemento $n$ " de un conjunto bien ordenado requiere contexto para saber si se cuenta desde cero o desde uno. En una expresión " elemento $β ", donde$ $β$ también puede ser un ordinal infinito, normalmente se contará desde cero.

Para un conjunto infinito, el tipo de orden determina la cardinalidad , pero no a la inversa: los conjuntos de una cardinalidad infinita particular pueden tener órdenes bien definidos de muchos tipos diferentes (véase el apartado « Números naturales» , más adelante, para un ejemplo). Para un conjunto infinito numerable , el conjunto de posibles tipos de orden es incontable.

Véase también

Árbol (teoría de conjuntos) , generalización
Número ordinal
Conjunto bien fundamentado
Bueno, orden parcial
Pedido previo de pozo
Conjunto dirigido

Referencias

↑ Manolios P, Vroon D. Algoritmos para aritmética ordinal . Conferencia internacional sobre deducción automatizada . Consultado el 16 de enero de 2025 .
↑ Smith, Trey; Ozer, Aksel (2025). "Órdenes lineales y la línea real". arXiv : 2508.15644 [ math.NT ].
↑ Feferman, S. (1964). "Algunas aplicaciones de las nociones de forzamiento y conjuntos genéricos" . Fundamenta Mathematicae . 56 (3): 325– 345. doi : 10.4064/fm-56-3-325-345 .
↑ Halmos 1960 , § 14
↑松坂 (Matsuzaka), 和夫 (Kazuo) (1968).集合・位相入門(en japonés). Cap. 3., § 2., (B) Lema 1.: 岩波書店.{{cite book}}: CS1 mantenimiento: ubicación ( enlace )
↑ Tao 2009 , Conjuntos bien ordenados, Ejercicio 5.
↑ Tao 2009 , Conjuntos bien ordenados, Definición 2.
↑ Halmos 1960 , § 19
↑ Halmos 1960 , § 18
↑ Tao 2009 , Conjuntos bien ordenados, Ejercicio 7.
1 2 Halmos 1960 , § 17
↑ Halmos 1960 , § 20.
↑ Taylor 1999 , Proposición 2.6,6,
↑ Bonnet, Rémi; Finkel, Alain; Haddad, Serge; Rosa-Velardo, Fernando (2013). "Teoría ordinal para la expresividad de sistemas de transición bien estructurados". Information and Computation . 224 : 1–22 . doi : 10.1016/j.ic.2012.11.003 . MR 3016456 .

Folland, Gerald B. (1999). Análisis real: técnicas modernas y sus aplicaciones . Matemáticas puras y aplicadas (2.ª ed.). Wiley . pp. 4–6 , 9. ISBN 978-0-471-31716-6.

Tao, T (28 de enero de 2009). "245B, Notas 7: Conjuntos bien ordenados, ordinales y lema de Zorn (opcional)" . Novedades .
Halmos, Paul (1960). Teoría de conjuntos ingenua . Princeton, Nueva Jersey: D. Van Nostrand Company.Reimpreso por Springer-Verlag, Nueva York, 1974. ISBN 0-387-90092-6(Edición de Springer-Verlag).
Taylor, Paul (13 de mayo de 1999). Fundamentos prácticos de las matemáticas . Cambridge University Press. ISBN 978-0-521-63107-5.

Lecturas adicionales

Paul Taylor, Hacia un tratamiento unificado de la inducción, I: el teorema general de recursión (1996).
Observación 2.5. en https://ncatlab.org/nlab/show/Zorn's+lemma

[woset-1] Manolios P, Vroon D. Algoritmos para aritmética ordinal . Conferencia internacional sobre deducción automatizada . Consultado el 16 de enero de 2025 .

[2] Smith, Trey; Ozer, Aksel (2025). "Órdenes lineales y la línea real". arXiv : 2508.15644 [ math.NT ].

[3] Feferman, S. (1964). "Algunas aplicaciones de las nociones de forzamiento y conjuntos genéricos" . Fundamenta Mathematicae . 56 (3): 325– 345. doi : 10.4064/fm-56-3-325-345 .

[Halmos_14-4] Halmos 1960 , § 14

[5] 松坂 (Matsuzaka), 和夫 (Kazuo) (1968).集合・位相入門(en japonés). Cap. 3., § 2., (B) Lema 1.: 岩波書店.{{cite book}}: CS1 mantenimiento: ubicación ( enlace )

[6] Tao 2009 , Conjuntos bien ordenados, Ejercicio 5.

[7] Tao 2009 , Conjuntos bien ordenados, Definición 2.

[Halmos_19-8] Halmos 1960 , § 19

[Halmos_18-9] Halmos 1960 , § 18

[10] Tao 2009 , Conjuntos bien ordenados, Ejercicio 7.

[Halmos-11] 1 2 Halmos 1960 , § 17

[12] Halmos 1960 , § 20.

[13] Taylor 1999 , Proposición 2.6,6,

[14] Bonnet, Rémi; Finkel, Alain; Haddad, Serge; Rosa-Velardo, Fernando (2013). "Teoría ordinal para la expresividad de sistemas de transición bien estructurados". Information and Computation . 224 : 1–22 . doi : 10.1016/j.ic.2012.11.003 . MR 3016456 .

[

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]