Pedido total

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

1. ${\displaystyle a\leq a}$( reflexivo ).
2. Si${\displaystyle a\leq b}$y${\displaystyle b\leq c}$entonces${\displaystyle a\leq c}$( transitivo ).
3. Si${\displaystyle a\leq b}$y${\displaystyle b\leq a}$entonces${\displaystyle a=b}$( antisimétrico ).
4. ${\displaystyle a\leq b}$o${\displaystyle b\leq a}$( fuertemente conectada , anteriormente llamada totalidad).

Los requisitos 1 a 3 simplemente conforman la definición de un orden parcial. La reflexividad (1) ya se deduce de la fuerte conexión (4), pero muchos autores la requieren explícitamente para indicar el parentesco con los órdenes parciales. ^{[ 1 ]} Los órdenes totales también se denominan a veces órdenes simples , ^{[ 2 ]} connexos , ^{[ 3 ]} u órdenes completos . ^{[ 4 ]}

Un conjunto equipado con un orden total es un conjunto totalmente ordenado ; ^{[ 5 ]} también se utilizan los términos conjunto simplemente ordenado , ^{[ 2 ]} conjunto linealmente ordenado , ^{[ 3 ] [ 5 ]} toset ^{[ 6 ]} y loset ^{[ 7 ] [ 8 ]} . El término cadena a veces se define como sinónimo de conjunto totalmente ordenado , ^{[ 5 ]} pero generalmente se refiere a un subconjunto totalmente ordenado de un conjunto parcialmente ordenado dado.

Una extensión de un orden parcial dado a un orden total se denomina extensión lineal de ese orden parcial.

Para fines de delimitación, un orden total como se define anteriormente a veces se denomina orden no estricto . Para cada orden total (no estricto)${\displaystyle \leq }$existe una relación asociada${\displaystyle <}$, llamado el orden total estricto asociado con${\displaystyle \leq }$que se puede definir de dos maneras equivalentes:

• ${\displaystyle a<b}$si${\displaystyle a\leq b}$y${\displaystyle a\neq b}$( reducción reflexiva ).
• ${\displaystyle a<b}$si no${\displaystyle b\leq a}$(es decir,${\displaystyle <}$es el complemento del recíproco de${\displaystyle \leq }$).

Por el contrario, el cierre reflexivo de un orden total estricto${\displaystyle <}$es un pedido total (no estricto).

Por lo tanto, un orden total estricto en un conjunto${\displaystyle X}$es una orden parcial estricta en${\displaystyle X}$en la que cualesquiera dos elementos distintos son comparables. Es decir, un orden total estricto es una relación binaria.${\displaystyle <}$en algún set${\displaystyle X}$, que satisface lo siguiente para todos${\displaystyle a,b}$y${\displaystyle c}$en${\displaystyle X}$:

1. No${\displaystyle a<a}$( irreflexivo ).
2. Si${\displaystyle a<b}$entonces no${\displaystyle b<a}$( asimétrico ).
3. Si${\displaystyle a<b}$y${\displaystyle b<c}$entonces${\displaystyle a<c}$( transitivo ).
4. Si${\displaystyle a\neq b}$, entonces${\displaystyle a<b}$o${\displaystyle b<a}$( conectado ).

La asimetría se deriva de la transitividad y la irreflexividad; ^{[ a ]} ​​además, la irreflexividad se deriva de la asimetría. ^{[ b ]}

• Cualquier subconjunto de un conjunto totalmente ordenado X es totalmente ordenado para la restricción del orden en X.
• El orden único en el conjunto vacío, ∅ , es un orden total.
• Cualquier conjunto de números ordinales (más concretamente, son buenos órdenes ).
• Si X es cualquier conjunto y funa función inyectiva de X a un conjunto totalmente ordenado entonces f induce un orden total en X al establecer x ₁ ≤ x ₂ si y solo si f ( x ₁ ) ≤ f ( x ₂ ) .
• El orden lexicográfico en el 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 usuales "menor o igual que" (≤) o "mayor o igual que" (≥) es totalmente ordenado. Por lo tanto, cada subconjunto de los números reales es totalmente ordenado, como los números naturales , los enteros y los racionales . Se puede demostrar que cada uno de estos es el único "ejemplo inicial" (salvo un isomorfismo de orden ) de un conjunto totalmente ordenado con una propiedad determinada (en este caso, un orden total A es inicial para una propiedad si, siempre que B tenga dicha propiedad, existe un isomorfismo de orden de A a un subconjunto de B ): ^{[ 9 ]}
  • Los números naturales forman un conjunto inicial no vacío totalmente ordenado sin límite superior .
  • Los números enteros forman un conjunto inicial no vacío totalmente ordenado sin límite superior ni inferior .
  • Los números racionales forman un conjunto inicial totalmente ordenado que es denso en los números reales. Además, la reducción reflexiva < es un orden denso en los números racionales.
  • Los números reales forman un conjunto inicial ilimitado y totalmente ordenado que está conectado según la topología de orden (definida a continuación).
• Los cuerpos ordenados son, por definición, totalmente ordenados. Incluyen los números racionales y los números reales. Todo cuerpo ordenado contiene un subcuerpo ordenado isomorfo a los números racionales. Todo cuerpo ordenado Dedekind-completo es isomorfo a los números reales.
• Las letras del alfabeto ordenadas según el orden estándar del diccionario , por ejemplo, A < B < C , etc., constituyen un orden total estricto.

El término cadena se define a veces como sinónimo de conjunto totalmente ordenado, pero generalmente se usa para referirse a un subconjunto de un conjunto parcialmente ordenado que está totalmente ordenado para el orden inducido. ^{[ 1 ] [ 10 ]} Típicamente, 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 cadenas. Este alto número de niveles anidados de conjuntos explica la utilidad del término.

Un ejemplo común del uso de cadenas para referirse a subconjuntos totalmente ordenados es el lema de Zorn, que afirma que, si toda cadena en un conjunto parcialmente ordenado X tiene una cota superior en X , entonces X contiene al menos un elemento maximal. ^{[ 11 ]} El lema de Zorn se usa comúnmente con X como 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 se usa generalmente para demostrar que un espacio vectorial tiene bases de Hamel y que un anillo tiene ideales maximales .

En algunos contextos, las cadenas consideradas son isomorfas en orden a los números naturales con su orden usual o su orden opuesto . En este caso, una cadena puede identificarse con una sucesión monótona y se denomina cadena ascendente o descendente , dependiendo de si la sucesión es creciente o decreciente. ^{[ 12 ]}

Un conjunto parcialmente ordenado tiene la condición de cadena descendente si toda cadena descendente se estabiliza finalmente. ^{[ 13 ]} Por ejemplo, un orden está bien fundado si tiene la condición de cadena descendente. De manera similar, la condición de cadena ascendente significa que toda cadena ascendente se estabiliza finalmente. Por ejemplo, un anillo noetheriano es un anillo cuyos ideales satisfacen la condición de cadena ascendente.

En otros contextos, solo se consideran 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 elementos en la cadena. ^{[ 14 ]} Así, un conjunto unitario 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 .

El término «cadena» también puede utilizarse para referirse a subconjuntos totalmente ordenados de estructuras que no son conjuntos parcialmente ordenados. Un ejemplo son las cadenas regulares de polinomios. Otro ejemplo es el uso de «cadena» como sinónimo de recorrido en un grafo .

Existen varias maneras de tomar dos conjuntos totalmente ordenados y extenderlos a un orden en el producto cartesiano , aunque el orden resultante puede ser solo parcial . Aquí se presentan tres de estos posibles órdenes, enumerados de manera que cada orden sea más fuerte que el anterior:

• Orden lexicográfico : ( a , b ) ≤ ( c , d ) si y solo si a < c o ( a = c y b ≤ d ). Este es un orden total.
• ( a , b ) ≤ ( c , d ) si y solo si a ≤ c y b ≤ d (el orden del producto ). Este es un orden parcial.
• ( a , b ) ≤ ( c , d ) si y solo si ( a < c y b < d ) o ( a = c y b = d ) (el cierre reflexivo del producto directo de los órdenes totales estrictos correspondientes). Este es también un orden parcial.

Cada uno de estos órdenes extiende al siguiente en el sentido de que si tenemos x ≤ y en el orden del producto, esta relación también se cumple en el orden lexicográfico, y así sucesivamente. Los tres pueden definirse de manera similar para el producto cartesiano de más de dos conjuntos.

Aplicadas al espacio vectorial R ⁿ , cada una de ellas lo convierte en un espacio vectorial ordenado .

Véanse también ejemplos de conjuntos parcialmente ordenados .

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

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 existen unas pocas estructuras no triviales que son (interdefinibles como) reductos 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 el uso de la separación de pares de puntos para distinguir, en un círculo, los dos intervalos determinados por un par de puntos. ^{[ 16 ]}

Referencias

• Birkhoff, Garrett (1967). Teoría de retículos . Publicaciones del coloquio. Vol.  25. Providence: Am. Math. Soc.
• Davey, Brian A.; Priestley, Hilary Ann (1990). Introducción a las redes y el orden . Libros de texto matemáticos de Cambridge. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753 . 
• Fuchs, L (1963). Sistemas algebraicos parcialmente ordenados . Pergamon Press.
• George Grätzer (1971). Teoría de retículos: primeros conceptos y retículos distributivos. WH Freeman and Co. ISBN 0-7167-0442-0
• Halmos, Paul R. (1968). Teoría ingenua de conjuntos . Princeton: Nostrand.
• John G. Hocking y Gail S. Young (1961). Topología. Reimpresión corregida, Dover, 1988. ISBN 0-486-65676-4
• Rosenstein, Joseph G. (1982). Ordenamientos lineales . Nueva York: Academic Press.
• Schmidt, Gunther ; Ströhlein, Thomas (1993). Relaciones y grafos: Matemáticas discretas para informáticos . Berlín: Springer-Verlag. ISBN 978-3-642-77970-1.

• "Conjunto totalmente ordenado" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]