Bien ordenado
Relaciones binarias transitivas | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Y indica que la propiedad de la columna es requerida por la definición del término de la fila (a la izquierda). Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica. ✗ indica que la propiedad puede, o no puede retener. Todas las definiciones requieren tácitamente la relación homogénea R{displaystyle R. ser transitivo: para todos a,b,c,{displaystyle a,b,c,} si aRb{displaystyle ARb! y bRc{displaystyle bRc} entonces aRc,{displaystyle ARc,} y hay propiedades adicionales que una relación homogénea puede satisfacer. |
En matemáticas, un buen orden (o buen orden o relación de buen orden) en un conjunto S es un orden total en S con la propiedad de que todo subconjunto no vacío de S tiene un elemento mínimo en este orden. El conjunto S junto con la relación de buen orden 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 buen orden, 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), a saber, el elemento menor del subconjunto de todos los elementos mayores que s. Puede haber elementos además del elemento menor que no tienen predecesor (ver § 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 una ordenación de pozos no estricta, entonces < es un orden bien estricto. Una relación es un orden bien estricto si y sólo si es un orden total estricto bien fundado. La distinción entre órdenes de pozo estrictas y no estrictas a menudo se ignora, ya que son fácilmente interconvertibles.
Todo conjunto bien ordenado tiene un orden único isomorfo a un número ordinal único, denominado tipo de orden del conjunto bien ordenado. El teorema del 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 demostración de la inducción transfinita para demostrar que un enunciado dado es verdadero para todos los elementos del conjunto.
La observación de que los números naturales están bien ordenados por la relación habitual menor que se denomina comúnmente principio de buena ordenación (para números naturales).
Números ordinales
Todo conjunto bien ordenado tiene un orden único isomorfo a un número ordinal único, denominado 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 objeto particular, o para encontrar 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. Contar 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 isomorfo, porque estos son iguales al número de objetos anteriores (que corresponde a contar desde cero). Así, para n finito, la expresión "n-ésimo elemento" de un conjunto bien ordenado requiere contexto para saber si cuenta desde cero o desde 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 (ver § Números naturales, a continuación, para ver un ejemplo). Para un conjunto infinito numerable, el conjunto de posibles tipos de órdenes es incontable.
Ejemplos y contraejemplos
Números naturales
La ordenación estándar ≤ de los números naturales es una buena ordenación 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 al definir que todos los números pares son menores que todos los números impares, y la ordenación habitual se aplica dentro de los pares y las probabilidades:
- 0 2 4 6 8... 1 3 5 7 9...
Este es un conjunto bien ordenado de tipo de orden ω + ω. Cada elemento tiene un sucesor (no hay elemento más grande). Dos elementos carecen de un predecesor: 0 y 1.
Enteros
A diferencia de la ordenación estándar ≤ de los números naturales, la ordenación estándar ≤ de los enteros no es una buena ordenación, ya que, por ejemplo, el conjunto de enteros negativos no contiene un elemento mínimo.
La siguiente relación R es un ejemplo de buena ordenación de los números enteros: x R y si y solo si se cumple una de las siguientes condiciones:
- x = 0
- x es positivo, y Sí. es negativo
- x y Sí. son positivos, y x ≤ Sí.
- x y Sí. son ambos negativos, y SilencioxØ ≤ latitudSí.Silencio
Esta relación R se puede visualizar de la siguiente manera:
- 0 1 2 3 4 – 1 −2 −3...
R es isomorfo al número ordinal ω + ω.
Otra relación para ordenar bien los números enteros es la siguiente definición: x ≤z y si y solo si (|x | < |y| o (|x| = |y| y x ≤ y)). Este orden de pozo se puede visualizar de la siguiente manera:
- 0 - 1 - 2 −3 3 −4 4...
Este tiene el tipo de orden ω.
Reales
La ordenación estándar ≤ de cualquier intervalo real no es una buena ordenación, ya que, por ejemplo, el intervalo abierto (0, 1) ⊆ [0,1] no contiene un elemento mínimo. A partir de los axiomas de 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) implican el axioma de elección y, por lo 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. 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 sigue que una fórmula particular ordena bien los reales, o de hecho cualquier colocar.
Un subconjunto incontable de los números reales con el orden estándar ≤ no puede ser un buen orden: supongamos que X es un subconjunto de R bien ordenado por ≤. Para cada x en X, sea s(x) el sucesor de x en ≤ ordenar en X (a menos que x sea el último elemento de X). Sea A = { (x, s(x)) | x ∈ X } cuyos elementos son intervalos no vacíos y disjuntos. Cada uno de estos intervalos contiene al menos un número racional, por lo que existe una función inyectiva de A a Q. Hay una inyección de X a A (excepto posiblemente por un último elemento de X que podría asignarse a cero más tarde). Y es bien sabido que hay una inyección de Q 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 otro lado, un subconjunto numerable infinito de los reales puede o no estar bien ordenado con el estándar "≤". Por ejemplo,
- Los números naturales son un buen orden bajo el orden estándar ≤.
- El set {1/n: n =1,2,3,...} no tiene menos elemento y por lo tanto no es un buen orden bajo el orden estándar ≤.
Ejemplos de órdenes de pozo:
- El conjunto de números { - 2−n SPECIAL ≤ n ► tiene el tipo de orden ω.
- El conjunto de números { - 2−n − 2−m−n SPECIAL ≤ m,n ► tiene el tipo de orden2. El conjunto anterior es el conjunto de puntos límite dentro del conjunto. Dentro del conjunto de números reales, ya sea con la topología ordinaria o la topología del pedido, 0 es también 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 SPECIAL ≤ n ► ω { 1 } tiene el tipo de orden 1. Con la topología del pedido de este conjunto, 1 es un punto límite del conjunto. Con la topología ordinaria (o equivalente, la topología del orden) de los números reales no lo es.
Formulaciones equivalentes
Si un conjunto está totalmente ordenado, entonces los siguientes son equivalentes entre sí:
- El set está bien ordenado. Es decir, cada subconjunto no vacío tiene un elemento menos.
- La inducción transfinita funciona para todo el conjunto ordenado.
- Cada secuencia estrictamente decreciente de elementos del conjunto debe terminar después de sólo finitamente muchos pasos (asumiendo el axioma de elección dependiente).
- Cada subordinación es isomorfa 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.
Con respecto a esta topología puede haber dos tipos de elementos:
- puntos aislados — estos son los mínimos y los elementos con un predecesor.
- puntos límite — este tipo no ocurre en conjuntos finitos, y puede o no ocurrir en un conjunto infinito; los conjuntos infinitos sin punto límite son los conjuntos del tipo de orden ω, por ejemplo N.
Por subconjuntos podemos distinguir:
- Subconjuntos con un máximo (es decir, subconjuntos que están obligados por sí mismos); esto 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.
- Los subconjuntos que están desbordados por sí mismos pero atados en todo el conjunto; no tienen un máximo, sino un supremum fuera del subconjunto; si el subconjunto no es vacío este supremum es un punto límite del subconjunto y por lo tanto también del conjunto entero; si el subconjunto está vacío este supremum es el mínimo de todo el conjunto.
- Subconjuntos sin límites en todo el conjunto.
Un subconjunto es cofinal en el conjunto completo si y solo si es ilimitado 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 primer espacio numerable si y solo si tiene un tipo de orden menor o igual a ω1 (omega-uno), es decir, si y solo si el conjunto es contable o tiene el tipo de orden incontable más pequeño.
Contenido relacionado
Tomas Fincke
Hipatia
Fractales