Orden total - Total order

Relaciones binarias

	Simétrico	Antisimétrico	Connex	Bien fundado	Tiene uniones	Tiene cumple
Relación de equivalencia	✓	✗	✗	✗	✗	✗
Preorder (Quasiorder)	✗	✗	✗	✗	✗	✗
Orden parcial	✗	✓	✗	✗	✗	✗
Reserva total	✗	✗	✓	✗	✗	✗
Orden total	✗	✓	✓	✗	✗	✗
Pedido previo	✗	✗	✓	✓	✗	✗
Bien casi ordenado	✗	✗	✗	✓	✗	✗
Bien ordenado	✗	✓	✓	✓	✗	✗
Enrejado	✗	✓	✗	✗	✓	✓
Unión-semirrejilla	✗	✓	✗	✗	✓	✗
Encuentro-semilattice	✗	✓	✗	✗	✗	✓

Un " ✓ " indica que la propiedad de la columna es necesaria en la definición de la fila.
Por ejemplo, la definición de una relación de equivalencia requiere que sea simétrica.
Todas las definiciones requieren tácitamente transitividad y reflexividad .

En matemáticas , un orden total , de orden sencillo , orden lineal , de orden connex , o de orden completo es una relación binaria en algunos conjunto , que es antisimétrica , transitiva , y una relación connex . Un conjunto emparejado con un orden total se llama cadena , un conjunto totalmente ordenado , un conjunto simplemente ordenado , un conjunto ordenado linealmente o un conjunto perdido . ${\ Displaystyle X}$

Formalmente, una relación binaria es un orden total en un conjunto si las siguientes declaraciones son válidas para todos y en : ${\ Displaystyle \ leq}$ ${\ Displaystyle X}$ ${\ Displaystyle a, b}$ ${\ Displaystyle c}$ ${\ Displaystyle X}$

Antisimetría: Si y luego ; ${\ Displaystyle a \ leq b}$ ${\ Displaystyle b \ leq a}$ ${\ Displaystyle a = b}$
Transitividad: Si y luego ; ${\ Displaystyle a \ leq b}$ ${\ Displaystyle b \ leq c}$ ${\ Displaystyle a \ leq c}$
Connexity: ${\ Displaystyle a \ leq b}$ o . ${\ Displaystyle b \ leq a}$

La antisimetría elimina los casos inciertos cuando ambos preceden y preceden . Una relación que tiene la propiedad connex significa que cualquier par de elementos en el conjunto de la relación son comparables bajo la relación. Esto también significa que el conjunto se puede diagramar como una línea de elementos, dándole el nombre de lineal . La propiedad de conexión también implica reflexividad , es decir, a ≤ a . Por lo tanto, un orden total también es un (caso especial de a) orden parcial , ya que, para un orden parcial, la propiedad de conexión se reemplaza por la propiedad de reflexividad más débil. Una extensión de un orden parcial dado a un orden total se llama extensión lineal de ese orden parcial. ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle b}$ ${\ Displaystyle a}$

Orden total estricto

Para cada orden total (no estricto) ≤ existe una relación semiconnex transitiva asimétrica (por lo tanto irreflexiva ) asociada <, denominada orden total estricto o orden semiconnex estricto , que se puede definir de dos formas equivalentes:

un < b si un ≤ b y un ≠ b
a < b si no b ≤ a (es decir, <es la inversa del complemento de ≤)

Propiedades:

La relación es transitiva: un < b y b < c implica un < c .
La relación es tricotómica : exactamente uno de un < b , b < una y un = b es cierto.
La relación es un orden estrictamente débil , donde la equivalencia asociada es igualdad.

Podemos trabajar al revés y comenzar eligiendo <como una relación binaria tricotómica transitiva; entonces un orden total ≤ puede definirse de dos formas equivalentes:

a ≤ b si a < b o a = b
a ≤ b si no b < a

Dos órdenes más asociados son los complementos ≥ y>, completando el cuádruple {<,>, ≤, ≥}.

Podemos definir o explicar la forma en que un conjunto está totalmente ordenado por cualquiera de estas cuatro relaciones; la notación implica si estamos hablando del orden total no estricto o estricto.

Ejemplos

Las letras del alfabeto ordenadas por el orden estándar del diccionario , por ejemplo, $A < B < C,$ etc.
Cualquier subconjunto de un conjunto totalmente ordenado $X$ está totalmente ordenó para la restricción de la orden en $X$ .
El pedido único en el conjunto vacío, $\emptyset$ , es un pedido total.
Cualquier conjunto de números cardinales o ordinales (más fuertemente, estos son órdenes de pozo ).
Si $X$ es cualquier conjunto $yf$ una función inyectiva de $X$ a un conjunto totalmente ordenado entonces $f$ induce un orden total en $X$ estableciendo $x 1 < x 2$ si y solo si $f (x 1) < f (x 2)$ .
El orden lexicográfico del producto cartesiano de una familia de conjuntos totalmente ordenados, indexados por un conjunto bien ordenado , es en sí mismo un orden total.
El conjunto de números reales ordenados por las relaciones habituales "menor que" ( < ) o "mayor que" ( > ) está totalmente ordenado y, por tanto, también lo son los subconjuntos de números naturales , enteros y números racionales . Se puede demostrar que cada uno de estos es el ejemplo más pequeño único (hasta el isomorfismo de orden ) de un conjunto totalmente ordenado con una determinada propiedad (un orden total A es el más pequeño con una determinada propiedad si siempre que B tiene la propiedad, hay un orden isomorfismo de A a un subconjunto de B
):
- Los números naturales comprenden el conjunto totalmente ordenado no vacío más pequeño sin límite superior .
- Los números enteros comprenden el conjunto totalmente ordenado no vacío más pequeño sin un límite superior ni inferior .
- Los números racionales comprenden el conjunto más pequeño totalmente ordenado que es denso en los números reales. La definición de densidad usada aquí dice que para cada $a$ y $b$ en los números reales tales que $a < b$ , hay una $q$ en los números racionales tal que $a < q < b$ .
- Los números reales comprenden el conjunto totalmente ordenado ilimitado más pequeño que está conectado en la topología de orden (definida a continuación).
Los campos ordenados están totalmente ordenados por definición. Incluyen los números racionales y los números reales. Cada campo ordenado contiene un subcampo ordenado que es isomorfo a los números racionales. Cualquier campo ordenado completo de Dedekind es isomorfo a los números reales.

Cadenas

El término cadena es sinónimo de un conjunto totalmente ordenado, en particular, el término se usa a menudo para referirse a un subconjunto totalmente ordenado de algún conjunto parcialmente ordenado , por ejemplo, en el lema de Zorn .
Una cadena ascendente es un conjunto totalmente ordenado que tiene un elemento mínimo (único), mientras que una cadena descendente es un conjunto totalmente ordenado que tiene un elemento máximo (único).
Dado un conjunto S con un orden parcial ≤, una cadena descendente infinita es un infinito , disminuyendo estrictamente secuencia de elementos x ₁ > x ₂ > ... . Como ejemplo, en el conjunto de números enteros , la cadena -1, -2, -3, ... es una cadena descendente infinita, pero no existe una cadena descendente infinita en los números naturales , ya que toda cadena de números naturales tiene una elemento mínimo. Si un conjunto parcialmente ordenado no posee ninguna cadena descendente infinita, se dice que satisface la condición de cadena descendente . Suponiendo el axioma de elección , la condición de cadena descendente en un conjunto parcialmente ordenado equivale a requerir que el orden estricto correspondiente esté bien fundado . Una condición más fuerte, que no haya cadenas descendentes infinitas ni antichains infinitos , define los cuasi-ordenamientos bien . Un conjunto totalmente ordenado sin infinitas cadenas descendentes se llama bien ordenado .
Consulte también Condición de cadena ascendente para conocer esta noción.

La altura de un poset denota la cardinalidad de su cadena más grande en este sentido.

Por ejemplo, considere el conjunto de todos los subconjuntos de números enteros, parcialmente ordenados por inclusión . Entonces el conjunto { I _n : n es un número natural}, donde I _n es el conjunto de números naturales por debajo de n , es una cadena en este orden, ya que está totalmente ordenado bajo inclusión: Si n ≤ k , entonces I _n es un subconjunto de I _k .

Otros conceptos

Teoría de celosía

Se puede definir un conjunto totalmente ordenado como un tipo particular de celosía , es decir, uno en el que tenemos

{\ Displaystyle \ {a \ vee b, a \ wedge b \} = \ {a, b \}}

para todo a , b .

Luego escribimos a ≤ b si y solo si . Por tanto, un conjunto totalmente ordenado es una red distributiva . ${\ Displaystyle a = a \ wedge b}$

Órdenes totales finitas

Un simple argumento de conteo verificará que cualquier conjunto finito totalmente ordenado no vacío (y por lo tanto cualquier subconjunto no vacío del mismo) tiene un elemento mínimo. Así, todo orden total finito es de hecho un orden bien . Ya sea mediante una prueba directa o observando que cada orden de pozo es de orden isomorfo a uno ordinal, se puede demostrar que cada orden total finito es de orden isomorfo a un segmento inicial de los números naturales ordenados por <. En otras palabras, un orden total en un conjunto con k elementos induce una biyección con los primeros k números naturales. Por lo tanto, es común indexar los pedidos totales finitos o los pedidos de pozo con el tipo de orden numbers mediante números naturales de una manera que respete el orden (ya sea comenzando con cero o con uno).

Teoría de categorías

Los conjuntos totalmente ordenados forman una subcategoría completa de la categoría de conjuntos parcialmente ordenados , siendo los morfismos mapas que respetan los órdenes, es decir, mapas f tales que si a ≤ b entonces f ( a ) ≤ f ( b ).

Un mapa biyectivo entre dos conjuntos totalmente ordenados que respeta los dos órdenes es un isomorfismo en esta categoría.

Topología de pedidos

Para cualquier conjunto X totalmente ordenado podemos definir los intervalos abiertos ( a , b ) = { x : a < x y x < b }, (−∞, b ) = { x : x < b }, ( a , ∞) = { x : un < x } y (-∞, ∞) = X . Podemos usar estos intervalos abiertos para definir una topología en cualquier conjunto ordenado, la topología de orden .

Cuando se utiliza más de una orden en un conjunto, se habla de la topología de órdenes inducida por una orden en particular. Por ejemplo, si N son los números naturales, <es menor que y> mayor de lo que podríamos referirnos a la topología de orden en N inducida por <y la topología de orden en N inducida por> (en este caso resultan ser idénticos pero no lo serán en general).

Se puede demostrar que la topología de orden inducida por un orden total es hereditariamente normal .

Lo completo

Se dice que un conjunto totalmente ordenado está completo si cada subconjunto no vacío que tiene un límite superior tiene un límite superior mínimo . Por ejemplo, el conjunto de números reales R está completo pero el conjunto de números racionales Q no lo es.

Hay una serie de resultados que relacionan las propiedades de la topología de orden con la integridad de X:

Si la topología de pedidos en X está conectada, X está completo.
X está conectado bajo la topología del orden si y sólo si es completo y no hay diferencia en X (una brecha es de dos puntos a y b en X con un < b de tal manera que no hay c satisface un < c < b .)
X es completo si y solo si cada conjunto acotado que está cerrado en la topología de orden es compacto.

Un conjunto totalmente ordenado (con su topología de orden) que es una celosía completa es compacto . Algunos ejemplos son los intervalos cerrados de números reales, por ejemplo, el intervalo unitario [0,1], y el sistema de números reales afines extendido (recta numérica real extendida). Hay homeomorfismos que preservan el orden entre estos ejemplos.

Sumas de pedidos

Para cualesquiera dos órdenes totales disjuntos y , existe un orden natural en el conjunto , que se denomina suma de los dos órdenes o, a veces, simplemente : ${\ Displaystyle (A_ {1}, \ leq _ {1})}$ ${\ Displaystyle (A_ {2}, \ leq _ {2})}$ ${\ Displaystyle \ leq _ {+}}$ ${\ Displaystyle A_ {1} \ cup A_ {2}}$ ${\ Displaystyle A_ {1} + A_ {2}}$

Para , se mantiene si y solo si se cumple una de las siguientes:

{\ Displaystyle x, y \ en A_ {1} \ cup A_ {2}}

{\ Displaystyle x \ leq _ {+} y}

${\ Displaystyle x, y \ en A_ {1}}$ y ${\ Displaystyle x \ leq _ {1} y}$
${\ Displaystyle x, y \ en A_ {2}}$ y ${\ Displaystyle x \ leq _ {2} y}$
${\ Displaystyle x \ en A_ {1}}$ y ${\ Displaystyle y \ en A_ {2}}$

De manera intuitiva, esto significa que los elementos del segundo conjunto se agregan sobre los elementos del primer conjunto.

De manera más general, si es un conjunto de índices totalmente ordenado, y para cada uno la estructura es un orden lineal, donde los conjuntos son disjuntos por pares, entonces el orden total natural en se define por ${\ Displaystyle (I, \ leq)}$ ${\ Displaystyle i \ in I}$ ${\ Displaystyle (A_ {i}, \ leq _ {i})}$ ${\ Displaystyle A_ {i}}$ ${\ Displaystyle \ bigcup _ {i} A_ {i}}$

Porque , se mantiene si:

{\ Displaystyle x, y \ in \ bigcup _ {i \ in I} A_ {i}}

{\ Displaystyle x \ leq y}

O hay algunos con ${\ Displaystyle i \ in I}$ ${\ Displaystyle x \ leq _ {i} y}$
o hay algunos en con , ${\ Displaystyle i <j}$ ${\ Displaystyle I}$ ${\ Displaystyle x \ in A_ {i}}$ ${\ Displaystyle y \ in A_ {j}}$

Pedidos sobre el producto cartesiano de conjuntos totalmente ordenados

En orden de fuerza creciente, es decir, conjuntos decrecientes de pares, tres de los posibles órdenes en el producto cartesiano de dos conjuntos totalmente ordenados son:

Orden lexicográfico : ( a , b ) ≤ ( c , d ) si y solo si a < c o ( a = c y b ≤ d ). Este es un pedido total.
( Un , b ) ≤ ( c , d ) si y sólo si una ≤ c y b ≤ d (la orden de producto ). Este es un pedido parcial.
( Un , b ) ≤ ( c , d ) si y sólo si ( a < c y b < d ) o ( un = c y b = d ) (el cierre reflexiva del producto directo de los pedidos totales estrictos correspondientes). Este también es un pedido parcial.

Los tres pueden definirse de manera similar para el producto cartesiano de más de dos conjuntos.

Aplicado al espacio vectorial R ⁿ , cada uno de ellos lo convierte en un espacio vectorial ordenado .

Consulte también ejemplos de conjuntos parcialmente ordenados .

Una función real de n variables reales definidas en un subconjunto de R ⁿ define un orden débil estricto y un preorden total correspondiente en ese subconjunto.

Estructuras relacionadas

Una relación binaria que es antisimétrica, transitiva y reflexiva (pero no necesariamente total) es un orden parcial .

Un grupo con un orden total compatible es un grupo totalmente ordenado .

Solo hay unas pocas estructuras no triviales que son (interdefinibles como) reducciones de un orden total. Olvidar la orientación da como resultado una relación de intermediación . Olvidar la ubicación de los extremos da como resultado un orden cíclico . Olvidar ambos datos da como resultado una relación de separación .

Ver también

Anillo artiniano
Teoría del orden
Bien ordenado
El problema de Suslin
Línea compatriota
Orden de prefijo: orden parcial total descendente

Notas

Referencias

Garrett Birkhoff (1967). Teoría de celosía . Publicaciones del coloquio. 25 . Providencia: Am. Matemáticas. Soc.
Brian A. Davey; Hilary Ann Priestley (1990). Introducción a las celosías y el orden . Libros de texto de matemáticas de Cambridge. Prensa de la Universidad de Cambridge. ISBN 0-521-36766-2. LCCN 89009753 .
Fuchs, L (1963). Sistemas algebraicos parcialmente ordenados . Pergamon Press.
George Grätzer (1971). Teoría de la celosía: primeros conceptos y celosías distributivas. WH Freeman and Co. ISBN 0-7167-0442-0
John G. Hocking y Gail S. Young (1961). Topología. Reimpresión corregida, Dover, 1988. ISBN 0-486-65676-4
Schmidt, Gunther ; Ströhlein, Thomas (1993). Relaciones y gráficos: matemáticas discretas para informáticos . Berlín: Springer-Verlag. ISBN 978-3-642-77970-1.

enlaces externos

"Conjunto totalmente ordenado" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]

Languages

In other projects