Orden total

En matemáticas, a total o orden lineal es un orden parcial en el que los dos elementos son comparables. Es decir, un orden total es una relación binaria ≤ ≤ {displaystyle leq } on some set X{displaystyle X}, que satisface lo siguiente para todos a,b{displaystyle a,b} y c{displaystyle c} dentro X{displaystyle X}:

1. a≤ ≤ a{displaystyle aleq a} (reflexivo).
2. Si a≤ ≤ b{displaystyle aleq b} y b≤ ≤ c{displaystyle bleq c} entonces a≤ ≤ c{displaystyle aleq c} (transitivo).
3. Si a≤ ≤ b{displaystyle aleq b} y b≤ ≤ a{displaystyle bleq a} entonces a=b{displaystyle a=b} (antisimétrico).
4. a≤ ≤ b{displaystyle aleq b} o b≤ ≤ a{displaystyle bleq a} (fuertemente conectado, anteriormente llamado total).

Los pedidos totales a veces también se denominan simples, connex o pedidos completos.

Un conjunto equipado con un pedido total es un conjunto totalmente ordenado; también se utilizan los términos conjunto ordenado simple, conjunto ordenado linealmente y perdido. El término cadena a veces se define como sinónimo de conjunto totalmente ordenado, pero generalmente se refiere a algún tipo de subconjunto totalmente ordenado de un conjunto dado parcialmente ordenado.

Una extensión de una orden parcial dada a una orden total se denomina extensión lineal de esa orden parcial.

Pedidos totales estrictos y no estrictos

A estricto orden total en un set X{displaystyle X} es un estricto orden parcial X{displaystyle X} en los que los dos elementos distintos son comparables. Es decir, un orden total es una relación binaria <math alttext="{displaystyle .{displaystyle]<img alt=" on some set X{displaystyle X}, que satisface lo siguiente para todos a,b{displaystyle a,b} y c{displaystyle c} dentro X{displaystyle X}:

1. No <math alttext="{displaystyle aa.a{displaystyle a wona}<img alt="{displaystyle a (irreflexivo).
2. Si <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a entonces no <math alttext="{displaystyle bb.a{displaystyle b madea}<img alt="{displaystyle b (asímétrica).
3. Si <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a y <math alttext="{displaystyle bb.c{displaystyle b)<img alt="b entonces <math alttext="{displaystyle aa.c{displaystyle aludec}<img alt="a (transitivo).
4. Si aل ل b{displaystyle aneq b}, entonces <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a o <math alttext="{displaystyle bb.a{displaystyle b madea}<img alt="b (conectado).

La asimetría se deriva de la transitividad y la irreflexividad; además, la irreflexividad se deriva de la asimetría.

Para cada orden total (no restringido) ≤ ≤ {displaystyle leq } hay una relación asociada <math alttext="{displaystyle .{displaystyle]<img alt=", llamado el estricto orden total asociado con ≤ ≤ {displaystyle leq } que se puede definir de dos maneras equivalentes:

• <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a si a≤ ≤ b{displaystyle aleq b} y aل ل b{displaystyle aneq b} (Reflexiva reducción).
• <math alttext="{displaystyle aa.b{displaystyle a meantb}<img alt="a si no b≤ ≤ a{displaystyle bleq a} (es decir, <math alttext="{displaystyle .{displaystyle]<img alt=" es el complemento del contrario de ≤ ≤ {displaystyle leq }).

Por el contrario, el cierre reflexivo de un estricto orden total <math alttext="{displaystyle .{displaystyle]<img alt=" es un orden total (no restringido).

Ejemplos

• Cualquier subconjunto de un conjunto totalmente ordenado X está totalmente ordenado para la restricción de la orden X.
• El pedido único en el set vacío, ∅, es un orden total.
• Cualquier conjunto de números cardinales o números ordinal (más fuertemente, estos son bien ordenados).
• Si X es cualquier conjunto y f una función inyectable desde X a un conjunto totalmente ordenado entonces f induce un pedido total en X por configuración x₁ ≤ x₂ si f()x₁≤ f()x₂).
• El orden lexicográfico sobre el producto cartesiano de una familia de conjuntos totalmente ordenados, indexado por un conjunto bien ordenado, es en sí mismo un orden total.
• El conjunto de números reales ordenados por las "menos o iguales" usuales (≤) o "más grandes o iguales a" (≥) relaciones se ordena totalmente. Por lo tanto cada subconjunto de los números reales se ordena totalmente, como los números naturales, números enteros y números racionales. Cada uno de estos se puede demostrar que es el único (hasta un orden isomorfismo) " Ejemplo inicial" de un conjunto totalmente ordenado con una determinada propiedad (aquí, un orden total A es inicial para una propiedad, si, cuando B tiene la propiedad, hay una orden de isomorfismo A a un subconjunto B):
  • Los números naturales forman un conjunto inicial no vacío totalmente ordenado sin límite superior.
  • Los enteros forman un conjunto inicial no vacío totalmente ordenado con ni un límite superior ni inferior.
  • Los números racionales forman un conjunto totalmente ordenado inicial que es denso en los números reales. Además, la reducción reflexiva es una orden densa sobre los números racionales.
  • Los números reales forman un conjunto inicial sin límites totalmente ordenado que está conectado en la topología del orden (definido abajo).
• 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 Dedekind-complete campo ordenado es isomorfo a los números reales.
• Las letras del alfabeto ordenadas por el orden del diccionario estándar, por ejemplo, A. B. C etc., es un orden total estricto.

Cadenas

El término cadena a veces se define como sinónimo de un conjunto totalmente ordenado, pero generalmente se usa para referirse a un subconjunto de un conjunto parcialmente ordenado que está totalmente ordenado por el orden inducido. Por lo general, el conjunto parcialmente ordenado es un conjunto de subconjuntos de un conjunto dado que está ordenado por inclusión, y el término se usa para enunciar propiedades del conjunto de las cadenas. Este alto número de niveles anidados de conjuntos explica la utilidad del término.

Un ejemplo común del uso de cadena para referirse a subconjuntos totalmente ordenados es el lema de Zorn, que afirma que, si cada cadena en un conjunto parcialmente ordenado X tiene un límite superior en X, entonces X contiene al menos un elemento máximo. El lema de Zorn se usa comúnmente con X siendo un conjunto de subconjuntos; en este caso, la cota superior se obtiene demostrando que la unión de los elementos de una cadena en X está en X. Esta es la forma que generalmente se usa para probar que un espacio vectorial tiene bases de Hamel y que un anillo tiene ideales maximales.

En algunos contextos, las cadenas que se consideran son isomorfas de orden a los números naturales con su orden habitual o su orden opuesto. En este caso, una cadena se puede identificar con una secuencia monótona, y se denomina cadena ascendente o cadena descendente, dependiendo de si la secuencia es creciente o decreciente.

Un conjunto parcialmente ordenado tiene la condición de cadena descendente si cada cadena descendente eventualmente se estabiliza. Por ejemplo, una orden está bien fundada si tiene la condición de cadena descendente. De manera similar, la condición de cadena ascendente significa que cada cadena ascendente finalmente se estabiliza. Por ejemplo, un anillo noetheriano es un anillo cuyos ideales satisfacen la condición de cadena ascendente.

En otros contextos, solo se consideran las cadenas que son conjuntos finitos. En este caso, se habla de una cadena finita, a menudo abreviada como cadena. En este caso, la longitud de una cadena es el número de desigualdades (o inclusiones de conjuntos) entre elementos consecutivos de la cadena; es decir, el número menos uno de los elementos de la cadena. Así, un conjunto singleton es una cadena de longitud cero y un par ordenado es una cadena de longitud uno. La dimensión de un espacio a menudo se define o caracteriza como la longitud máxima de cadenas de subespacios. Por ejemplo, la dimensión de un espacio vectorial es la longitud máxima de cadenas de subespacios lineales, y la dimensión de Krull de un anillo conmutativo es la longitud máxima de cadenas de ideales primos.

"Cadena" también se puede usar para algunos subconjuntos totalmente ordenados de estructuras que no son conjuntos parcialmente ordenados. Un ejemplo lo dan las cadenas regulares de polinomios. Otro ejemplo es el uso de "cadena" como sinónimo de un paseo en un gráfico.

Otros conceptos

Teoría de la red

Uno puede definir un conjunto totalmente ordenado como un tipo particular de retículo, a saber, uno en el que tenemos

{}aAlternativa Alternativa b,a∧ ∧ b}={}a,b}{displaystyle {avee b,awedge b}={a,b} para todos a, b.

Entonces escribimos a ≤ b si a=a∧ ∧ b{displaystyle a=awedge b}. Por lo tanto un conjunto totalmente ordenado es una celosía distributiva.

Pedidos totales finitos

Un simple argumento de conteo verificará que cualquier conjunto totalmente ordenado finito 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 bueno. Ya sea por demostración directa o por la observación de que todo orden de pozo es isomorfo a un ordinal, se puede demostrar que todo orden total finito es isomorfo a un segmento inicial de los números naturales ordenados por <. En otras palabras, un orden total en un conjunto con elementos k induce una biyección con los primeros k números naturales. Por lo tanto, es común indexar pedidos totales finitos o bien pedidos con tipo de pedido ω por números naturales de una manera que respeta 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).

Una aplicación biyectiva entre dos conjuntos totalmente ordenados que respeta los dos órdenes es un isomorfismo en esta categoría.

Topología de orden

Para cualquier conjunto totalmente ordenado X podemos definir los intervalos abiertos (a, b) = { x: a < x y x < b}, (−∞, b) = {x: x < b}, (a, ∞) = {x: a < 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 orden 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.

Integridad

Se dice que un conjunto totalmente ordenado es completo si todo subconjunto no vacío que tiene una cota superior tiene una cota superior mínima. Por ejemplo, el conjunto de números reales R está completo pero el conjunto de números racionales Q no lo está. En otras palabras, los diversos conceptos de integridad (que no debe confundirse con ser "total") no se transfieren a las restricciones. Por ejemplo, sobre los números reales, una propiedad de la relación ≤ es que todo subconjunto no vacío S de R con un límite superior en R tiene un límite superior mínimo (también llamado supremo) en R. Sin embargo, para los números racionales este supremo no es necesariamente racional, por lo que la misma propiedad no se cumple en la restricción de la relación ≤ a los números racionales.

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

• Si el pedido de topología en X está conectado, X está completo.
• X está conectado bajo la topología del pedido si y sólo si está completo y no brecha dentro X (una brecha es dos puntos a y b dentro X con a. b tal que no c satisfizo a. c. b.)
• X está completo si y sólo si cada conjunto atado que está cerrado en la topología del orden es compacto.

Un conjunto totalmente ordenado (con su topología de orden) que es un retículo completo es compacto. Ejemplos son los intervalos cerrados de números reales, p. el intervalo unitario [0,1] y el sistema de números reales afinemente extendido (recta de números reales extendida). Hay homeomorfismos que preservan el orden entre estos ejemplos.

Sumas de pedidos

Para cualquier orden total de dos personas ()A1,≤ ≤ 1){displaystyle (A_{1},leq _{1})} y ()A2,≤ ≤ 2){displaystyle (A_{2},leq _{2}}, hay un orden natural ≤ ≤ +{displaystyle leq _{+} en el set A1∪ ∪ A2{displaystyle A_{1}cup A_{2}, que se llama la suma de las dos órdenes o a veces simplemente A1+A2{displaystyle A_{1}+A_{2}:

Para x,Sí.▪ ▪ A1∪ ∪ A2{displaystyle x,yin A_{1}cup A_{2}, x≤ ≤ +Sí.{displaystyle xleq _{+}y} sostiene si y sólo si uno de los siguientes sostiene:

1. x,Sí.▪ ▪ A1{displaystyle x,yin A_{1} y x≤ ≤ 1Sí.{displaystyle xleq _{1}y}
2. x,Sí.▪ ▪ A2{displaystyle x,yin A_{2} y x≤ ≤ 2Sí.{displaystyle xleq _{2}y}
3. x▪ ▪ A1{displaystyle xin A_{1} y Sí.▪ ▪ A2{displaystyle yin A_{2}

Intuitivamente, esto significa que los elementos del segundo conjunto se agregan encima de los elementos del primer conjunto.

Más generalmente, si ()I,≤ ≤ ){displaystyle (I,leq)} es un conjunto de índice totalmente ordenado, y para cada i▪ ▪ I{displaystyle iin I} la estructura ()Ai,≤ ≤ i){displaystyle (A_{i},leq _{i})} es un orden lineal, donde los sets Ai{displaystyle A_{i} son dos veces disjoint, entonces el orden total natural en ⋃ ⋃ iAi{displaystyle bigcup ¿Qué? se define por

Para x,Sí.▪ ▪ ⋃ ⋃ i▪ ▪ IAi{displaystyle x,yin bigcup _{iin Yo..., x≤ ≤ Sí.{displaystyle xleq y} sostiene si:

1. O hay algunos i▪ ▪ I{displaystyle iin I} con x≤ ≤ iSí.{displaystyle xleq _{i}y}
2. o hay algunos <math alttext="{displaystyle ii.j{displaystyle i donej}<img alt="i dentro I{displaystyle Yo... con x▪ ▪ Ai{displaystyle xin A_{i}, Sí.▪ ▪ Aj{displaystyle yin A_{j}

Decidibilidad

La teoría de primer orden de los pedidos totales es decidible, es decir, existe un algoritmo para decidir qué enunciados de primer orden se cumplen para todos los pedidos totales. Usando la interpretabilidad en S2S, la teoría monádica de segundo orden de órdenes totales contables también es decidible.

Órdenes sobre el producto cartesiano de conjuntos totalmente ordenados

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

• Orden Lexicográfico: (a,b≤c,dSi y sólo si a. c oa = c y b ≤ d). Es un orden total.
• ()a,b≤c,dSi y sólo si a ≤ c y b ≤ d (el pedido del producto). Es una orden parcial.
• ()a,b≤c,dSi y sólo sia. c y b. d) o (a = c y b = d) (el cierre reflexivo del producto directo de las órdenes totales correspondientes). Esto también es un orden parcial.

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

Aplicados al espacio vectorial Rⁿ, cada uno de estos lo convierte en un espacio vectorial ordenado.

Vea 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 pedido anticipado total correspondiente en ese subconjunto.

Estructuras relacionadas

Relaciones binarias transitivas v t e
Simétrico Antisymmetric Conectado Bien fundada Has joineds Has meets Reflexivo Irreflexivo Asimétrica Total, Semiconnex Anti- reflexivo Equivalencia relación Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorden (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Orden parcial ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preordenado ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Orden total ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Bien ordenado ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Bien ordenado ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Orden parcial estricta ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden débil estricto ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Orden total estricta ✗ Y Y ✗ ✗ ✗ ✗ Y Y Simétrico Antisymmetric Conectado Bien fundada Has joineds Has meets Reflexivo Irreflexivo Asimétrica Definiciones, para todos a,b{displaystyle a,b} y Sل ل ∅ ∅ :{displaystyle Sneq varnothing:} aRb⇒ ⇒ bRa{displaystyle {begin{aligned}ducaRb\\\\\\\\\\\\\\\\\\\}}}}} aRbybRa⇒ ⇒ a=b{displaystyle {begin{aligned}aRb{text{ and } {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\fn}}}}}}}} aل ل b⇒ ⇒ aRbobRa{displaystyle {begin{aligned}aneq {} {fn}} {fn} {fn}} {fn}} {fn}}}} {fn}}}}}} {fn}}}} minSexiste{displaystyle {begin{aligned}min} S\{text{exists}end{aligned}} aAlternativa Alternativa bexiste{displaystyle {begin{aligned}avee b{text{exists}end{aligned}}} a∧ ∧ bexiste{displaystyle {begin{aligned}awedge b\{text{exists}end{aligned}}} aRa{displaystyle aRa} noaRa{displaystyle {text{not }a Ra. aRb⇒ ⇒ nobRa{displaystyle {begin{aligned}aRb Rightarrow Raend{aligned}}
Y indica que la propiedad de la columna es siempre verdad el término de la fila (a la izquierda), mientras que ✗ indica que la propiedad no está garantizada en general (puede, o no, mantener). Por ejemplo, que cada relación de equivalencia es simétrica, pero no necesariamente antisimétrica, se indica por Y en la columna "Simétrica" y ✗ en la columna "Antisimétrica", respectivamente. 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.} La definición de un término puede requerir propiedades adicionales que no se enumeran en esta tabla.

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.