Orden total
En matemáticas , llamamos relación de orden total en un conjunto E a cualquier relación de orden ≤ para la cual dos elementos de E son siempre comparables, es decir,
.
Entonces decimos que E está totalmente ordenado por ≤.
Definición
Una relación binaria ≤ en un conjunto E es un orden total si (para todos los elementos x , y y z de E ):
- si x ≤ y e y ≤ z , entonces x ≤ z ( transitividad );
- si x ≤ y e y ≤ x , entonces x = y ( antisimetría );
- x ≤ x ( reflexividad );
- x ≤ y o y ≤ x ( totalidad ).
Las primeras tres propiedades son las que forman ≤ una relación de orden. El cuarto hace de este pedido un pedido total.
Ejemplos de
- El conjunto de letras de un alfabeto está completamente ordenado por orden alfabético .
- Cualquier campo euclidiano , como el campo ℝ de números reales , está dotado de un orden total natural: x ≤ y si y solo si y - x es un cuadrado .
- Sea f : X → Y una inyección , ≤ un orden en Y , y ≼ el orden inducido en X estableciendo: x 1 ≼ x 2 si y solo si f ( x 1 ) ≤ f ( x 2 ). Si ≤ es total, entonces ≼ también. En particular: la restricción de una porción X de Y de un orden total en Y es un orden total en X . Por ejemplo, cualquier parte de ℝ está totalmente ordenada por la relación de orden habitual.
- Si un orden ≤ en E es total, entonces el orden opuesto ≥ en E es total (los resultados inversos ).
- El orden lexicográfico del producto cartesiano de un conjunto bien ordenado de conjuntos totalmente ordenados es en sí mismo un orden total; por ejemplo, cualquier conjunto de palabras está completamente ordenado alfabéticamente y cualquier orden correcto es un orden total.
- Una cadena de un conjunto parcialmente ordenado ( E , ≤) es una parte de E sobre la cual el orden ≤ es total. Esta noción juega un papel importante en la teoría de conjuntos , según el lema de Zorn .
- Podemos definir un conjunto totalmente ordenado como una red en la que { a ∨ b , a ∧ b } = { a, b } para todo a , b ; entonces podemos establecer a ≤ b si y solo si a = a ∧ b ; probamos que un orden total es también una red distributiva.
- De acuerdo con el teorema de extensión de Szpilrajn , cualquier orden parcial ≤ en un conjunto E es extensible a un orden total en E , llamado extensión lineal de ≤.
Contraejemplos
- En el conjunto de enteros naturales, la relación de orden "es un divisor de" no es un orden total, porque podemos encontrar pares de enteros positivos, ninguno de los cuales es divisor del otro.
- Del mismo modo, en el conjunto de partes de un conjunto que contiene al menos dos elementos de un y b (distintos), la inclusión es sólo una orden parcial: no tenemos ni { un } ⊂ { b }, ni { b } ⊂ { un } .
El caso terminado
- En un conjunto finito completamente ordenado, cualquier parte no vacía tiene un elemento más pequeño . En otras palabras: en un conjunto finito, cualquier orden total es un buen orden .
- Cualquier conjunto totalmente ordenado finito es isomorfo a la orden a un segmento inicial de N .
En teoría de categorías
Los conjuntos totalmente ordenados forman una subcategoría de la categoría de órdenes , cuyos morfismos tienen cada vez más aplicaciones .
Cualquier biyección creciente de un orden total a cualquier orden es un isomorfismo de orden .
Orden estricto total
La biyección canónica entre los órdenes estrictos y los órdenes del mismo conjunto E asocia una relación de orden estricto <(antirreflexivo y transitivo por lo tanto antisimétrico) a una relación de orden ≤ (reflexivo, transitivo y antisimétrico), por:
x < y ⇔ ( x ≤ y y x ≠ y )o :
x ≤ y ⇔ ( x < y o x = y ).Un orden ≤ es total si y solo si su orden estricto asociado <satisface:
∀ x , y ∈ E ( x < y o x = y o y < x ).Llamamos orden estricto total a cualquier orden estricta que verifique esta propiedad, denominada “tricotomía”.