Buen orden

Relaciones binarias transitivas en a mi
Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Total, Semiconnex Anti- reflexivo Relación de equivalencia Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido anticipado (cuasi pedido) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Orden parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Pedido anticipado total ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Pedido total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Preordenamiento de pozos ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Bien-cuasi-ordenamiento ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Buen orden ✗ Y Y Y ✗ ✗ Y ✗ ✗ Enrejado ✗ Y ✗ ✗ Y Y Y ✗ ✗ Unión de semirrejilla ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Conocer-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Orden parcial estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden débil estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden total estricta ✗ Y Y ✗ ✗ ✗ ✗ Y Y Simétrico Antisimétrico Conectado Bien fundado Tiene uniones Tiene cumple Reflexivo Irreflexivo Asimétrico Definiciones, para todos y${\estilo de visualización a,b}$${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{not }}aRa}$ ${\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}$
Yindica que la propiedad de la columna siempre es verdadera para el término de la fila (a la izquierda), mientras que ✗ indica que la propiedad no está garantizada en general (puede cumplirse o no). Por ejemplo, que toda relación de equivalencia es simétrica, pero no necesariamente antisimétrica, se indica con en la columna "Simétrica" ​​y ✗ en la columna "Antisimétrica", respectivamente.Y Todas las definiciones requieren tácitamente que la relación homogénea sea transitiva : para todo si y entonces La definición de un término puede requerir propiedades adicionales que no están incluidas en esta tabla.${\displaystyle R}$${\displaystyle a,b,c,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

En matemáticas , un buen orden (o buen ordenamiento o relación de buen orden ) en un conjunto S es un ordenamiento total en S con la propiedad de que cada subconjunto no vacío de S tiene un elemento menor en este ordenamiento. El conjunto S junto con el ordenamiento se denomina entonces conjunto bien ordenado . En algunos artículos y libros de texto académicos, estos términos se escriben como bienorden , bienordenado y bienordenando o bien orden , bien ordenado y bien ordenando .

Todo conjunto bien ordenado no vacío tiene un elemento mínimo. Cada elemento s de un conjunto bien ordenado, excepto un posible elemento mayor , tiene un sucesor único (próximo elemento), es decir, 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 § Números naturales a continuación para un ejemplo). Un conjunto bien ordenado S contiene para cada subconjunto T con un límite superior un límite superior mínimo , es decir, el elemento mínimo del subconjunto de todos los límites superiores de T en S .

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

Todo conjunto bien ordenado es isomorfo en orden único a un número ordinal único , llamado tipo de orden del conjunto bien ordenado. El teorema de buen orden , que es equivalente al axioma de elección , establece que todo conjunto puede estar bien ordenado. Si un conjunto está bien ordenado (o incluso si simplemente admite una relación bien fundada ), se puede utilizar la técnica de prueba de inducción transfinita para demostrar 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 por la relación usual menor que se denomina comúnmente principio de buen orden (para números naturales).

Todo conjunto bien ordenado es unívocamente isomorfo en orden a un único número ordinal , llamado tipo de orden del conjunto bien ordenado. La posición de cada elemento dentro del conjunto ordenado también está dada por un número ordinal. En el caso de un conjunto finito, la operación básica de contar , para encontrar el número ordinal de un objeto en particular, o para encontrar el objeto con un número ordinal en 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. ^[1] 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 estos son iguales al número de objetos anteriores (lo que corresponde a contar desde cero). Por lo tanto, para un número finito de n , la expresión " elemento n -ésimo" de un conjunto bien ordenado requiere contexto para saber si se cuenta desde cero o desde uno. En una notación " elemento β -ésimo", donde β también puede ser un ordinal infinito, normalmente se contará desde cero.

En el caso de un conjunto infinito, el tipo de orden determina la cardinalidad , pero no a la inversa: los conjuntos bien ordenados de una cardinalidad particular pueden tener muchos tipos de orden diferentes (consulte el apartado Números naturales, a continuación, para ver un ejemplo). En el caso de un conjunto infinito numerable , el conjunto de tipos de orden posibles es incontable.

El ordenamiento estándar ≤ de los números naturales es un buen ordenamiento y tiene la propiedad adicional de que cada número natural distinto de cero tiene un predecesor único.

Otra buena ordenación de los números naturales se da definiendo que todos los números pares son menores que todos los impares, y el orden habitual se aplica dentro de los pares y los impares:

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

Este es un conjunto bien ordenado de tipo ω + ω . Cada elemento tiene un sucesor (no hay un elemento más grande). Dos elementos carecen de predecesor: 0 y 1.

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

La siguiente relación binaria R es un ejemplo de buen orden de los números enteros: x R y si y sólo si se cumple una de las siguientes condiciones:

1. x = 0
2. x es positivo e y es negativo
3. x e y son ambos positivos y x ≤ y
4. x e y son ambos negativos, y | x | ≤ | y |

Esta relación R se puede visualizar de la siguiente manera:

${\displaystyle {\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 bien los números enteros es la siguiente definición: si y sólo si${\displaystyle x\leq _{z}y}$

${\displaystyle |x|<|y|\qquad {\text{or}}\qquad |x|=|y|{\text{ and }}x\leq y.}$

Este buen orden se puede visualizar de la siguiente manera:

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

Este tiene el tipo de orden ω .

El ordenamiento estándar ≤ de cualquier intervalo real no es un buen ordenamiento, ya que, por ejemplo, el intervalo abierto ⁠ ⁠${\displaystyle (0,1)\subseteq [0,1]}$ no contiene un elemento mínimo. A partir de los axiomas ZFC de la teoría de conjuntos (incluido el axioma de elección ) se puede demostrar que existe un buen ordenamiento de los reales. También Wacław Sierpiński demostró que ZF + GCH (la hipótesis del continuo generalizado ) implica el axioma de elección y, por lo tanto, un buen ordenamiento de los reales. No obstante, es posible demostrar que los axiomas ZFC+GCH por sí solos no son suficientes para demostrar la existencia de un buen ordenamiento definible (por una fórmula) de los reales. ^[2] 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 incontable de los números reales con el ordenamiento estándar ≤ no puede ser un buen orden: supóngase que X es un subconjunto de ⁠ ⁠${\displaystyle \mathbb {R} }$ bien ordenado por ≤ . Para cada x en X , sea s ( x ) el sucesor de x en ≤ ordenamiento en X (a menos que x sea el último elemento de X ). Sea cuyos elementos son intervalos no vacíos y disjuntos. Cada uno de estos intervalos contiene al menos un número racional, por lo que hay una función inyectiva de A a ⁠ ⁠ Hay una inyección de X a A (excepto posiblemente por un último elemento de X , que podría mapearse a cero más tarde). Y es bien sabido que hay una inyección de ⁠ ⁠ a los números naturales (que podría elegirse para evitar llegar a cero). Por lo tanto, hay una inyección de X a los números naturales, lo que significa que X es contable. Por otra parte, un subconjunto numerablemente infinito de los números reales puede o no ser un buen orden con el estándar ≤ . Por ejemplo,${\displaystyle A=\{(x,s(x))\,|\,x\in X\}}$${\displaystyle \mathbb {Q} .}$${\displaystyle \mathbb {Q} }$

• Los números naturales están bien ordenados según el ordenamiento estándar ≤ .
• El conjunto no tiene ningún elemento mínimo y, por lo tanto, no está bien ordenado según el ordenamiento estándar ≤ .${\displaystyle \{1/n\,|\,n=1,2,3,\dots \}}$

Ejemplos de órdenes de pozo:

• El conjunto de números tiene tipo de orden ω .${\displaystyle \{-2^{-n}\,|\,0\leq n<\omega \}}$
• El conjunto de los números tiene tipo de orden ω ² . 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 con la topología de orden, el 0 es también un punto límite del conjunto. También es un punto límite del conjunto de puntos límite.${\displaystyle \{-2^{-n}-2^{-m-n}\,|\,0\leq m,n<\omega \}}$
• El conjunto de los números tiene tipo de orden ω + 1. 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.${\displaystyle \{-2^{-n}\,|\,0\leq n<\omega \}\cup \{1\}}$

Si un conjunto está totalmente ordenado , entonces los siguientes son equivalentes entre sí:

1. El conjunto está bien ordenado, es decir, cada subconjunto no vacío tiene un elemento mínimo.
2. La inducción transfinita funciona para todo el conjunto ordenado.
3. Toda secuencia estrictamente decreciente de elementos del conjunto debe terminar después de sólo un número finito de pasos (asumiendo el axioma de elección dependiente ).
4. Cada subordenamiento es isomorfo a un segmento inicial.

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

Respecto a esta topología pueden existir dos tipos de elementos:

• puntos aislados : son los mínimos y los elementos con un predecesor.
• puntos límite — este tipo no se da en conjuntos finitos, y puede o no darse en un conjunto infinito; los conjuntos infinitos sin punto límite son los conjuntos de tipo de orden ω , por ejemplo los números naturales ⁠ ⁠${\displaystyle \mathbb {N} .}$

Para los subconjuntos podemos distinguir:

• Subconjuntos con un máximo (es decir, subconjuntos acotados por sí mismos); éste 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 están acotados en el conjunto total; no tienen máximo, sino un supremo fuera del subconjunto; si el subconjunto no está vacío, este supremo es un punto límite del subconjunto y, por tanto, también del conjunto total; si el subconjunto está vacío, este supremo es el mínimo del conjunto total.
• Subconjuntos que no están acotados en el conjunto completo.

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

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

• Árbol (teoría de conjuntos) , generalización
• Número ordinal
• Conjunto bien fundado
• Bueno pedido parcial
• Preordenamiento de pozos
• Conjunto dirigido