Buen orden

Clase de ordenamiento matemático

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

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 (siguiente elemento), es decir, el elemento menor del subconjunto de todos los elementos mayores que s . Puede haber elementos, además del elemento menor, que no tengan predecesor (consulte la sección Números naturales a continuación para ver 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 orden de pozo no estricto , entonces < es un orden de pozo estricto. Una relación es un ordenamiento estricto y estricto si y sólo si es un orden total estricto y bien fundamentado . A menudo se ignora la distinción entre órdenes de pozo estrictos y no estrictos, ya que son fácilmente interconvertibles.

Todo conjunto bien ordenado es isomorfo de orden único a un número ordinal único , llamado tipo de orden del conjunto bien ordenado. El teorema del buen orden , que equivale 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 la 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 mediante la relación menor que habitual se denomina comúnmente principio de buen ordenamiento (para números naturales).

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 encontrar el número ordinal de un determinado objeto, o para encontrar el objeto con un determinado número ordinal, corresponde a asignar números ordinales uno a uno a los objetos. El tamaño (número de elementos, número cardinal ) de un conjunto finito es igual al tipo de orden. ^{[ cita necesaria ]} El conteo en el sentido cotidiano generalmente comienza desde uno, por lo que asigna a cada objeto el tamaño del segmento inicial con ese objeto como último elemento. Tenga en cuenta que estos números son uno más que los números ordinales formales según el orden isomórfico, porque son iguales al número de objetos anteriores (lo que corresponde a contar desde cero). Por lo tanto, para n finito , la expresión " n -ésimo elemento" de un conjunto bien ordenado requiere contexto para saber si cuenta desde cero o uno. En una notación " β -ésimo elemento" donde β también puede ser un ordinal infinito, normalmente contará desde cero.

Para 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 § Números naturales, a continuación, para ver un ejemplo). Para un conjunto contablemente infinito , el conjunto de posibles tipos de órdenes es incontable.

Ejemplos y contraejemplos

Números naturales

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

Otro buen orden de los números naturales se obtiene al definir que todos los números pares son menores que todos los números 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 de orden ω + ω . Cada elemento tiene un sucesor (no existe un elemento más grande). Dos elementos carecen de predecesor: 0 y 1.

Enteros

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 enteros negativos no contiene un elemento mínimo.

La siguiente relación binaria R es un ejemplo de buen ordenamiento 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 orden de pozo 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 ω .

reales

El ordenamiento estándar ≤ de cualquier intervalo real no es un buen ordenamiento, ya que, por ejemplo, el intervalo abierto 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 orden 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 tanto, un buen orden de los reales. No obstante, es posible demostrar que los axiomas ZFC+GCH por sí solos no son suficientes para probar la existencia de un orden bien definible (mediante una fórmula) de los reales. ^[1] Sin embargo, es consistente con ZFC que existe un buen ordenamiento definible de los reales; por ejemplo, es consistente con ZFC que V=L , y de ZFC+V=L se deduce que una fórmula particular ordena bien los reales, o incluso cualquier conjunto. ${\displaystyle (0,1)\subseteq [0,1]}$

Un subconjunto incontable de números reales con el orden estándar ≤ no puede ser un buen orden: supongamos que X es un subconjunto de bien ordenados por ≤ . Para cada x en X , sea s ( x ) el sucesor de x en ≤ ordenando en X (a menos que x sea el último elemento de X ). Sean cuyos elementos sean 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 asignarse a cero más adelante). Y es bien sabido que hay una inyección desde a los números naturales (que podrían elegirse para evitar llegar al cero). Por tanto, hay una inyección de X a los números naturales, lo que significa que X es contable. Por otro lado, un subconjunto contablemente infinito de los reales puede o no ser un buen orden con el estándar ≤ . Por ejemplo, ${\displaystyle \mathbb {R} }$ ${\displaystyle A=\{(x,s(x))\,|\,x\in X\}}$ ${\displaystyle \mathbb {Q} .}$ ${\displaystyle \mathbb {Q} }$

• Los números naturales tienen un buen orden según el orden estándar ≤ .
• El conjunto no tiene ningún elemento mínimo y, por lo tanto, no es un buen orden según el orden 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 números tiene tipo de orden ω ² . El conjunto anterior es el conjunto de puntos límite dentro del conjunto. Dentro del conjunto de números reales, ya sea con topología ordinaria o con topología de orden, 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 números tiene tipo de orden ω + 1 . Con la topología de orden de este conjunto, 1 es un punto límite del conjunto. Con la topología ordinaria (o equivalentemente, la topología de orden ^{[ aclaración necesaria ]} ) de los números reales no lo es. ${\displaystyle \{-2^{-n}\,|\,0\leq n<\omega \}\cup \{1\}}$

Formulaciones equivalentes

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

1. El conjunto está bien ordenado. Es decir, todo subconjunto no vacío tiene un elemento mínimo.
2. La inducción transfinita funciona para todo el conjunto ordenado.
3. Cada 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 ).
4. Todo subordenamiento es isomorfo a un segmento inicial.

Topología de orden

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 : estos son los elementos mínimos y con un predecesor.
• puntos límite : este tipo no ocurre en conjuntos finitos y puede ocurrir o no 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 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 sí acotados en todo el conjunto; 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 completo; si el subconjunto está vacío, este supremo es el mínimo de todo el conjunto.
• Subconjuntos que no están acotados en todo el conjunto.

Un subconjunto es cofinal en todo el conjunto si y sólo si es ilimitado en todo el conjunto o tiene un máximo que también es máximo de todo el conjunto.

Un conjunto bien ordenado como espacio topológico es un primer espacio contable 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 menor tipo de orden incontable .

Ver también

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

Referencias

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

• Folland, Gerald B. (1999). Análisis real: técnicas modernas y sus aplicaciones. Matemática pura y aplicada (2ª ed.). Wiley . págs. 4–6, 9. ISBN 978-0-471-31716-6.