Conjunto bien ordenado

En matemáticas , un conjunto ordenado ( E , ≤) está bien ordenado y la relación ≤ es un buen orden si se cumple la siguiente condición:

Cualquier porción que no esté vacía de E tiene un elemento más pequeño .

Si ( E , ≤) es bien ordenó entonces ≤ es necesariamente un orden total , es decir, cualquiera de los dos elementos de x y y de E siempre son comparables. De hecho, el conjunto { x , y } tiene un elemento más pequeño, por lo que tenemos x ≤ y o y ≤ x .

Si además se verifica el axioma de elección dependiente , esta propiedad (estar bien ordenada) es equivalente, para un orden total presupuestado, a la condición de cadena descendente "no hay secuencia infinita estrictamente decreciente". Según el teorema de Zermelo , el axioma de elección en toda su fuerza es equivalente al hecho de que cualquier conjunto puede estar bien ordenado.

Ejemplos y contraejemplos

Cualquier parte de un conjunto bien ordenado está en sí misma bien ordenada (para el orden inducido).
El conjunto vacío está bien ordenado por su única relación : (Ø, Ø) (es el ordinal más pequeño ).
De manera más general, cualquier conjunto finito totalmente ordenado está bien ordenado. Dicho conjunto ordenado se caracteriza (en isomorfismo cercano ) por el número n de elementos del conjunto, lo que justifica la notación n para la coincidencia del tipo de orden .
Si define un buen orden basado en y una cadena de , la restricción es un buen orden. ${\ Displaystyle \ leq}$ ${\ Displaystyle (E, \ leq)}$ $VS$ ${\ Displaystyle (E, \ leq)}$ ${\ Displaystyle (C, \ leq)}$
El conjunto (ℕ, ≤) de enteros naturales , siempre con su orden habitual, está bien ordenado; a menudo se indica ω en este contexto.
Si es una familia de conjuntos bien ordenados y si está dotada de un buen orden, entonces: (miI,≤I)I∈I{\ Displaystyle (E_ {i}, \ leq _ {i}) _ {i \ in I}} ${\ Displaystyle (E_ {i}, \ leq _ {i}) _ {i \ in I}}$ I{\ Displaystyle I} $I$
- si es finito, en el
producto , el orden lexicográfico es un buen orden. Para cuatro ejemplos de productos de un par de buenos pedidos, consulte n × p , 2 × N , N × 2 y N × N (isomorfo a los ordinales de los productos pn , ω2, 2ω (= ω) y ω 2, respectivamente ) ;I{\ Displaystyle I} $I$ ∏I∈ImiI={(XI)I∈I∣∀I∈I, XI∈miI}{\ Displaystyle \ prod _ {i \ in I} E_ {i} = \ {(x_ {i}) _ {i \ in I} \ mid \ forall i \ in I, \ x_ {i} \ in E_ { I} \}} ${\ Displaystyle \ prod _ {i \ in I} E_ {i} = \ {(x_ {i}) _ {i \ in I} \ mid \ forall i \ in I, \ x_ {i} \ in E_ { I} \}}$
la unión disjunta está bien ordenada por: si o ( y ). Este orden correcto se llama suma ordinal de la familia. Tenga en cuenta eso . Se anota la suma ordinal de un par de buenos pedidos . Para ver tres ejemplos, consulte ω + ω (= ω2) y 3 + ω, ω + 3 (⊂ ω2) . ${\ Displaystyle \ bigsqcup _ {i \ in I} E_ {i} = \ {(i, x) \ mid i \ in I, \ x \ in E_ {i} \}}$ ${\ Displaystyle (i, x) \ leq (j, y)}$ $yo <j$ $i = j$ ${\ Displaystyle x \ leq _ {i} y}$ ${\ Displaystyle \ sum _ {i \ in I} E = I \ times E}$ $(A, B)$ $A + B$

Demostración

Producto cartesiano (finito): que la razón por la inducción de la cardinalidad de : I{\ Displaystyle I} $I$
- inicialización: si , es decir , se reduce a un singleton (rigurosamente, el que contiene la secuencia vacía :) , por lo tanto bien ordenado; ${\ Displaystyle | I | = 0}$ ${\ Displaystyle I = \ varnothing}$ $\ prod_ {i \ in I} E_i$ ${\ Displaystyle \ {() \}}$
- herencia: se supone que la propiedad es genéricamente verdadera para cualquier conjunto de índices de $n$ cardinal ; suponemos . Sea $A$ una parte no vacía de . $I$ está bien ordenada, admite un elemento más pequeño $i$ $0$ ; establecemos , entonces y (donde denota la proyección canónica en el componente $i$ $0$ ). Entonces definimos $A$ $'$ por , que es legítimo ya que $A$ $i$ $0$ es una parte no vacía (por no vacío de $A$ ) del conjunto ordenado $E$ $i$ $0$ y, por lo tanto, admite un mínimo. $A$ $'$ no está vacío entonces (siempre porque $A$ tampoco lo está); ahora forma parte del conjunto $E$ $'$ , que está bien ordenado (para el orden lexicográfico inducido) por hipótesis de inducción ya que , y en consecuencia, $A$ $'$ tiene un elemento menor . Observando , obtenemos con un mínimo de $A$ : de hecho, si , entonces ; hay una alternativa: o , y luego , o , y tenemos entonces , por tanto, por minimidad de en $A$ $'$ , que, según la definición recursiva del orden lexicográfico , devuelve bien . ${\ Displaystyle | I | = n + 1}$ $\ prod_ {i \ in I} E_i$ ${\ Displaystyle I '= I \ setminus \ {i_ {0} \}}$ ${\ Displaystyle E '= \ prod _ {i \ in I'} E_ {i}}$ ${\ Displaystyle A_ {i_ {0}} = \ pi _ {i_ {0}} (A)}$ ${\ Displaystyle \ pi _ {i_ {0}}}$ ${\ Displaystyle A '= \ {(x_ {i}) _ {i \ in I'} \ in E '\ mid (x_ {i}) _ {i \ in I} \ in A \ \ \ mathrm {y } \ x_ {i_ {0}} = \ operatorname {min} (A_ {i_ {0}}) \}}$ ${\ Displaystyle | I '| = n}$ ${\ Displaystyle (m_ {i}) _ {i \ in I '}}$
  ${\ displaystyle m_ {i_ {0}} = \ operatorname {min} (A_ {i_ {0}})}$ ${\ Displaystyle (m_ {i}) _ {i \ in I}}$ ${\ Displaystyle (x_ {i}) _ {i \ in I} \ in A}$ ${\ Displaystyle m_ {i_ {0}} \ leq x_ {i_ {0}}}$ ${\ Displaystyle m_ {i_ {0}} <x_ {i_ {0}}}$ ${\ Displaystyle (m_ {i}) _ {i \ in I} \ leq _ {\ mathrm {lex} _ {I}} (x_ {i}) _ {i \ in I}}$ ${\ Displaystyle m_ {i_ {0}} = x_ {i_ {0}}}$ ${\ Displaystyle (x_ {i}) _ {i \ in I '} \ in A'}$ ${\ Displaystyle (m_ {i}) _ {i \ in I '} \ leq _ {\ mathrm {lex} _ {I'}} (x_ {i}) _ {i \ in I '}}$ ${\ Displaystyle (m_ {i}) _ {i \ in I '}}$ ${\ Displaystyle (m_ {i}) _ {i \ in I} \ leq _ {\ mathrm {lex} _ {I}} (x_ {i}) _ {i \ in I}}$

Suma disjunta: sea $A$ una parte no vacía de . Posamos ; $I$ $A$ es un no vacío parte de $I$ desde $A$ es no vacío, por lo tanto, $que$ ser bien ordenada, $I$ $A$ admite un mínimo $i$ $0$ . Luego definimos $E '$ por ; $E '$ es una parte no vacía de $E$ $i$ $0$ por construcción, pero esta última está bien ordenada, por lo que $E'$ tiene un elemento más pequeño $x$ $0$ . Luego verificamos que $($ $i$ $0$ $,$ $x$ $0$ $)$ es el mínimo de $A$ para el orden de la suma ordinal: si , entonces y por lo tanto ; si , tenemos , si no, y luego de dónde , lo que resulta entonces . ${\ Displaystyle \ bigsqcup _ {i \ in I} E_ {i}}$ ${\ Displaystyle I_ {A} = \ {i \ in I \ mid \ existe x \ in E_ {i}, (i, x) \ in A \}}$ ${\ Displaystyle E '= \ {x \ in E_ {i_ {0}} \ mid (i_ {0}, x) \ in A \}}$
${\ Displaystyle (i, x) \ in A}$ ${\ Displaystyle i \ in I_ {A}}$ ${\ Displaystyle i_ {0} \ leq i}$ ${\ Displaystyle i_ {0} <i}$ ${\ Displaystyle (i_ {0}, x_ {0}) \ leq (i, x)}$ ${\ Displaystyle i_ {0} = i}$ ${\ Displaystyle (i_ {0}, x) \ in A}$ ${\ Displaystyle x \ in E_ {i_ {0}}}$ ${\ Displaystyle x_ {0} \ leq _ {i_ {0}} x}$ ${\ Displaystyle (i_ {0}, x_ {0}) \ leq (i, x)}$

El conjunto de enteros relativos o el intervalo real ] 0, 1 [(con sus respectivos órdenes habituales) no están bien ordenados ya que ellos mismos no tienen un elemento más pequeño. Los intervalos reales [0, 1 [y [0, 1] tampoco están bien ordenados ya que su parte no está vacía] 0, 1 [.
El conjunto de sucesiones infinitas de 0 y 1, que se pueden escribir y proporcionar con el orden lexicográfico asociado (inducido por 0 <1 y el orden habitual en , por lo tanto dos buenos órdenes), entonces no está bien ordenado, ya que es un parte no vacía que no admite mínimo (efectivamente, 1…> 01…> 001…> 0001…>…); esto constituye un contraejemplo de la propiedad sobre el producto cartesiano mencionado anteriormente en el caso donde es infinito. ${\ Displaystyle \ prod _ {i \ in \ mathbb {N}} \ {0.1 \}}$ ${\ mathbb N}$ ${\ Displaystyle \ {0 ^ {i} 1 ^ {\ omega} \ mid i \ in \ mathbb {N} \}}$ $I$

Predecesores y sucesores

Sea ( E , ≤) un conjunto no vacío bien ordenado.

Tiene un elemento más pequeño, pero puede (como en el caso E = ω, el conjunto de números naturales para el orden habitual) no tener uno más grande; pero nada impide agregarle uno: este es el comienzo de una construcción ingenua de ordinales transfinitos .
Sea α un elemento de E : si α no es el elemento más grande de E , existe, entre los elementos de E estrictamente mayores que α, un elemento menor β, llamado sucesor de α y frecuentemente señalado como α + 1 , del cual α es el predecesor .
Un elemento de E tiene como máximo un predecesor; el elemento más pequeño obviamente no tiene uno y este es el único caso para E = ω, pero en general, en un conjunto E bien ordenado , muchos elementos no tienen un predecesor; además, es una propiedad característica de los ordinales transfinitos> ω. Un miembro de E que tiene un predecesor de dicho primer tipo (o sucesora ) y la segunda especie (o límite ), si no es así, y si no es el elemento más pequeño de E . Esta distinción suele ser útil para el razonamiento por inducción transfinita .

Segmento inicial

Un segmento inicial de un conjunto ordenado ( E , ≤) es un subconjunto S de E tal que cualquier límite inferior de un elemento de S está en S. El conjunto E en sí mismo es un segmento inicial de ( E , ≤), y todos los se dice que otros están limpios .

Para x ∈ E , el conjunto S x : = { y ∈ E | y < x } es siempre un segmento inicial propio de E , y el mapa x ↦ S x aumenta de ( E , ≤) a ( P ( E ) , ⊂).

Si ( E , ≤) es un orden bueno, tal inicial propio segmento S es igual a S x , donde x es el elemento más pequeño de la complementaria de S . El mapa x ↦ S x es entonces biyectivo de E en el conjunto de sus segmentos iniciales propios.

Un conjunto bien ordenado nunca es isomorfo a uno de sus segmentos iniciales adecuados.

Comparación de buenos órdenes y ordinales

Los buenos órdenes pueden compararse por el morfismo; un morfismo de orden es una aplicación cada vez mayor. Un isomorfismo de buen orden es, por tanto, un mapa uno a uno creciente, siendo lo contrario también creciente (porque un buen orden es total). Por ejemplo, el mapa x ↦ S x del párrafo anterior define un isomorfismo entre un conjunto bien ordenado y el conjunto de sus segmentos iniciales propios.

Si dos buenos órdenes son isomorfos, el isomorfismo entre ellos es único.

Los isomorfismos de orden permiten clasificar los buenos órdenes, gracias a una propiedad fundamental (demostrada por Georg Cantor ):

Teorema.— Dados dos buenos órdenes, uno es isomorfo a un segmento inicial del otro.

Por ejemplo, mostramos que cualquier conjunto infinito bien ordenado tiene un segmento inicial isomorfo a ω (el orden habitual en ℕ), por el teorema de definición por inducción en ℕ.

El teorema se deduce fácilmente del teorema de definición por inducción en buen orden . Más directamente: let y dos buenos pedidos, en los que se anotan los segmentos iniciales adecuados respectivamente y ; entonces, el conjunto de pares tal que es isomorfo a es la gráfica de un isomorfismo entre dos segmentos iniciales, y , que no pueden ser ambos propios. ${\ Displaystyle (E, \ leq)}$ ${\ Displaystyle (F, \ leq)}$ ${\ Displaystyle S_ {e}}$ $T_ {f}$ ${\ Displaystyle (e, f) \ in E \ times F}$ ${\ Displaystyle S_ {e}}$ $T_ {f}$ $S \ subconjunto E$ ${\ Displaystyle T \ subconjunto F}$

Esta propiedad expresa esencialmente que, salvo el isomorfismo, la comparación por segmento inicial ordena completamente los órdenes correctos. Se puede especificar restringiéndose a todos los buenos órdenes que se pueden definir en un conjunto E dado ; entonces, el conjunto de clases isomorfas ( clase de equivalencia para la relación de isomorfismo) de estos buenos órdenes está totalmente ordenado por la relación "ser isomorfo a un segmento inicial", e incluso bien ordenado como deducimos de la caracterización de los segmentos iniciales de los buenos órdenes (es una construcción del ordinal Hartogs asociado con el conjunto E ).

Llamamos ordinal a un buen orden visto hasta el isomorfismo. En la teoría de conjuntos , la definición de clases isomórficas como una clase de equivalencias choca con las paradojas habituales, ya que estas clases no pueden ser conjuntos. Una solución es poder definir de manera uniforme un representante por clase: se trata de la construcción de ordinales debida a von Neumann (consiste en definir un ordinal como el conjunto de sus propios segmentos iniciales).

Esta construcción se hace en la teoría de conjuntos de Zermelo-Fraenkel , requiere imperativamente el esquema de axiomas de reemplazo . La teoría de conjuntos de Zermelo (sin este esquema de axiomas) no nos permite mostrar la existencia del ordinal de von Neumann ω + ω (ni los que están más allá), mientras que un buen orden de tipo ω + ω se define fácilmente por suma en esta teoría.

Teorema (ZF) .— Cualquier conjunto bien ordenado es isomorfo a uno y sólo a un ordinal de von Neumann .

Buen orden terminado

En un conjunto finito bien ordenado, cualquier parte no vacía también tiene un elemento más grande, es decir, el orden opuesto también es un buen orden. Esta propiedad es característica de los pedidos bien terminados. En teoría de conjuntos, puede proporcionar una definición:

números naturales, que luego son ordinales finitos (en este sentido);
conjuntos finitos, es decir en biyección con un entero natural, que son entonces los conjuntos a los que se puede dotar de un buen orden finito.

Notas y referencias

Paul Halmos , Introducción a la teoría de conjuntos [ detalle de las ediciones ], pag. 82 de la edición en inglés, vista previa en Google Books .
(en) Kenneth Kunen , Teoría de conjuntos: una introducción a las pruebas de independencia , Elsevier,2014( leer en línea ) , pág. 14-15, Lema 6.1.
Kunen , 2014 , p. 15, Lema 6.2.
Moschovakis , 2006 , p. 99, Teorema 7.31.
Kunen , 2014 , p. 15, Teorema 6.3.
Kunen , 2014 , p. 17, Teorema 7.4.

Ver también

Bibliografía

(en) Yiannis Moschovakis , Notes on Set Theory [ detalle de las ediciones ]

Artículo relacionado

Relación bien fundada