Bien ordenado - Well-order

En matemáticas , un buen orden (o una relación bien ordenada o bien ordenada ) 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 conjunto bien ordenado relación se llama entonces un conjunto bien ordenada . En algunos artículos académicos y libros de texto, estos términos se escriben bien ordenados , bien ordenados y bien ordenados o bien ordenados. bien ordenado , bien ordenado y bien ordenado .

Cada 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 (elemento siguiente), es decir, el elemento menor del subconjunto de todos los elementos mayores que s . Puede haber elementos además del elemento mínimo que no tienen predecesor (consulte el § Números naturales a continuación para ver un ejemplo). Un conjunto bien ordenada S contiene para cada subconjunto T con un límite superior de un extremo superior a saber, el elemento mínimo, del subconjunto de todos los límites superiores de T en S .

Si ≤ es un ordenamiento no estricto , entonces <es un ordenamiento estricto. Una relación es un estricto bien ordenamiento si y solo si es un estricto orden total bien fundado . La distinción entre órdenes de pozo estrictos y no estrictos a menudo se ignora, ya que son fácilmente interconvertibles.

Cada conjunto bien ordenado tiene un orden único isomorfo a un número ordinal único , llamado 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 ), la técnica de prueba de inducción transfinita puede usarse 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 buen orden (para los números naturales).

Números ordinales

Cada conjunto bien ordenado tiene un orden único isomorfo 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 , encontrar el número ordinal de un objeto particular, o 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. 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 isomorfo, porque son iguales al número de objetos anteriores (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 esto 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 la Sección #Números naturales para ver un ejemplo sencillo. Para un conjunto infinito contable , el conjunto de posibles tipos de orden es incluso 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 da 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 las probabilidades:

0 2 4 6 8 ... 1 3 5 7 9 ...

Este es un conjunto bien ordenado del tipo de orden ω + ω. Cada elemento tiene un sucesor (no hay ningún elemento más grande). Dos elementos carecen de 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 ordenación correcta, ya que, por ejemplo, el conjunto de enteros negativos no contiene un elemento mínimo.

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

  1. x = 0
  2. x es positivo e y es negativo
  3. x y 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:

0 1 2 3 4 ... −1 −2 −3 ...

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

Otra relación para ordenar bien los 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 1 −2 2 −3 3 −4 4 ...

Tiene el tipo de orden ω.

Reales

La ordenación estándar ≤ de cualquier intervalo real no es una ordenación bien, ya que, por ejemplo, el intervalo abierto (0, 1) ⊆ [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 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 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 definible (mediante una fórmula) de los reales. Sin embargo, es consistente con ZFC que existe un buen orden 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 orden correcto: suponga que X es un subconjunto de R bien ordenado por ≤. Para cada x en X , sea s ( x ) el sucesor de x en ≤ ordenando 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 tales intervalo contiene al menos un número racional, así que no es 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 mapearse a cero más adelante). Y es bien sabido que hay una inyección de Q a los números naturales (que podrían 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 numerablemente infinito de los reales puede o no ser un buen orden con el estándar "≤". Por ejemplo,

  • Los números naturales están bien ordenados bajo el orden estándar ≤.
  • El conjunto {1 / n: n = 1,2,3, ...} no tiene ningún elemento mínimo y, por lo tanto, no es un buen orden según el orden estándar ≤.

Ejemplos de órdenes de pozo:

  • El conjunto de números {- 2 - n | 0 ≤ n <ω} tiene el tipo de orden ω.
  • El conjunto de números {- 2 - n - 2 - m - n | 0 ≤ m , n <ω} tiene el tipo de orden ω 2 . 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 con la topología de orden, 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 ≤ n <ω} ∪ {1} tiene el 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) de los números reales no lo es.

Formulaciones equivalentes

Si un conjunto está totalmente ordenado , 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. Cada secuencia estrictamente decreciente de elementos del conjunto debe terminar después de un número finito de pasos (asumiendo el axioma de elección dependiente ).
  4. Cada suborden es isomorfo a un segmento inicial.

Topología de pedidos

Cada conjunto bien ordenado se puede convertir 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 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 N .

Para subconjuntos podemos distinguir:

  • Subconjuntos con un máximo (es decir, subconjuntos que están delimitados por sí mismos); este puede ser un punto aislado o un punto límite de todo el conjunto; en el último caso, puede ser o no también un punto límite del subconjunto.
  • Subconjuntos que no están delimitados por sí mismos pero están delimitados en el conjunto completo; no tienen un 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 delimitados en todo el conjunto.

Un subconjunto es cofinal en todo el conjunto si y solo si no está acotado en todo el conjunto o tiene un máximo que también es el 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 ω 1 ( omega-uno ), es decir, si y solo si el conjunto es contable o tiene el menor tipo de orden incontable .

Ver también

Referencias

  1. ^ 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 .