Pedido total

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

$a\leq a$ ( reflexivo ).
Si y entonces ( transitivo ). ${\estilo de visualización a\leq b}$ ${\estilo de visualización b\leq c}$ $a\leq c$
Si y entonces ( antisimétrico ). ${\estilo de visualización a\leq b}$ $b\leq a$ ${\estilo de visualización a=b}$
${\estilo de visualización a\leq b}$ o ( fuertemente conectado , antes llamado total). $b\leq a$

La reflexividad (1.) ya se desprende de la conexidad (4.), pero muchos autores la exigen explícitamente, no obstante, para indicar el parentesco con órdenes parciales. ^[1] Los órdenes totales a veces también se denominan simples , ^[2] conexos , ^[3] u órdenes completos . ^[4]

Un conjunto dotado de un orden total es un conjunto totalmente ordenado ; ^[5] también se utilizan los términos conjunto simplemente ordenado , ^[2] conjunto ordenado linealmente , ^[3]^[5] y conjunto de elementos ^[6]^{[7] . El término}cadena se define a veces como sinónimo de conjunto totalmente ordenado , ^[5] pero se refiere en general a algún tipo de 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.

Órdenes totales estrictas y no estrictas

Un orden total estricto en un conjunto es un orden parcial estricto en el que dos elementos distintos son comparables. Es decir, un orden total estricto es una relación binaria en algún conjunto que satisface lo siguiente para todos y en : ${\estilo de visualización X}$ ${\estilo de visualización X}$ ${\estilo de visualización <}$ ${\estilo de visualización X}$ ${\estilo de visualización a,b}$ ${\estilo de visualización c}$ ${\estilo de visualización X}$

No ( irreflexivo ). ${\estilo de visualización a<a}$
Si entonces no ( asimétrico ). ${\estilo de visualización a<b}$ $b<a$
Si y entonces ( transitivo ). ${\estilo de visualización a<b}$ ${\estilo de visualización b<c}$ $a<c$
Si , entonces o ( conectado ). ${\estilo de visualización a\neq b}$ ${\estilo de visualización a<b}$ $b<a$

La asimetría se desprende de la transitividad y la irreflexividad; ^[8] además, la irreflexividad se desprende de la asimetría. ^[9]

A los efectos de delimitación, un orden total como el definido anteriormente se denomina a veces orden no estricto . Para cada orden total (no estricto) existe una relación asociada , denominada orden total estricto asociado a , que puede definirse de dos maneras equivalentes: ${\estilo de visualización \leq}$ ${\estilo de visualización <}$ ${\estilo de visualización \leq}$

${\estilo de visualización a<b}$ si y ( reducción reflexiva ). ${\estilo de visualización a\leq b}$ ${\estilo de visualización a\neq b}$
${\estilo de visualización a<b}$ si no (es decir, es el complemento del inverso de ). $b\leq a$ ${\estilo de visualización <}$ ${\estilo de visualización \leq}$

Por el contrario, el cierre reflexivo de un orden total estricto es un orden total (no estricto). ${\estilo de visualización <}$

Ejemplos

Cualquier subconjunto de un conjunto totalmente ordenado $X$ está totalmente ordenado por la restricción del orden en $X.$
El orden único en el conjunto vacío, $\emptyset$ , es un orden total.
Cualquier conjunto de números cardinales o números ordinales (más fuertemente, estos son buenos órdenes ).
Si $X$ es cualquier conjunto y $f$ una función inyectiva de $X$ a un conjunto totalmente ordenado, entonces $f$ induce un ordenamiento total en $X$ al establecer $x 1 \leq x 2$ si y solo si $f (x 1) \leq f (x 2)$ .
El orden lexicográfico del 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 relaciones habituales "menor o igual que" (≤) o "mayor o igual que" (≥) está totalmente ordenado. Por lo tanto, cada subconjunto de los números reales está totalmente ordenado, como los números naturales , los enteros y los racionales . Se puede demostrar que cada uno de ellos es el único "ejemplo inicial" (hasta un isomorfismo de orden ) de un conjunto totalmente ordenado con una determinada propiedad (aquí, un orden total A es inicial para una propiedad si, siempre que B tiene la propiedad, hay un isomorfismo de orden de A a un subconjunto de B ): ^[10]^{[ cita requerida ]}
- Los números naturales forman un conjunto inicial totalmente ordenado, no vacío y sin límite superior .
- Los números enteros forman un conjunto inicial totalmente ordenado y no vacío, 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 totalmente ordenado que está conexo en la topología de orden (definida a continuación).
Los cuerpos ordenados están totalmente ordenados por definición. Incluyen los números racionales y los números reales. Cada cuerpo ordenado contiene un subcuerpo ordenado que es isomorfo a los números racionales. Cualquier 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., es un orden total estricto.

Cadenas

El término cadena se define a veces como sinónimo de un conjunto totalmente ordenado, pero generalmente se utiliza para referirse a un subconjunto de un conjunto parcialmente ordenado que está totalmente ordenado para el orden inducido. ^[1]^[11] Normalmente, el conjunto parcialmente ordenado es un conjunto de subconjuntos de un conjunto dado que está ordenado por inclusión, y el término se utiliza para indicar propiedades del conjunto de las cadenas. Este elevado 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 maximal. ^[12] El lema de Zorn se usa comúnmente con $X$ siendo un conjunto de subconjuntos; en este caso, el límite superior se obtiene probando 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 maximalistas .

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

Un conjunto parcialmente ordenado tiene la condición de cadena descendente si cada cadena descendente eventualmente se estabiliza. ^[14] 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 cada cadena ascendente eventualmente 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 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. ^[15] Por lo tanto, 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 puede usarse para algunos subconjuntos totalmente ordenados de estructuras que no son conjuntos parcialmente ordenados. Un ejemplo lo constituyen las cadenas regulares de polinomios. Otro ejemplo es el uso de "cadena" como sinónimo de un paseo en un grafo .

Otros conceptos

Teoría de celosía

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

\{a\vee b,a\cuña b\}=\{a,b\}

para todos a , b .

Entonces escribimos a ≤ b si y solo si . Por lo tanto, un conjunto totalmente ordenado es una red distributiva . $a=a\cuña b$

Pedidos totales finitos

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. Por lo tanto, cada orden total finito es de hecho un buen orden . Ya sea por prueba directa o por observar que cada buen orden es orden isomorfo a un ordinal uno puede mostrar que cada orden total finito es 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 órdenes totales finitos o buenos órdenes con tipo de orden ω por 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 ).

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

Topología de órdenes

Para cualquier conjunto totalmente ordenado $X$ podemos definir los intervalos abiertos

$(a, b) = {x | a < x y x < b}$ ,
$(-\infty, b) = {x | x < b}$ ,
$(a, \infty) = {x | a < x}$ , y
$(-\infty, \infty) = X$ .

Podemos utilizar estos intervalos abiertos para definir una topología en cualquier conjunto ordenado, la topología de orden .

Cuando se utiliza más de un orden en un conjunto, se habla de la topología de orden inducida por un orden particular. Por ejemplo, si N son los números naturales, < es menor que y > es mayor que, podríamos referirnos a la topología de orden en N inducida por < y a la topología de orden en N inducida por > (en este caso, resultan ser idénticas, 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

Un conjunto totalmente ordenado se dice que es 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 es completo pero el conjunto de números racionales Q no lo es. En otras palabras, los diversos conceptos de completitud (que no debe confundirse con ser "total") no se trasladan a las restricciones . Por ejemplo, sobre los números reales una propiedad de la relación ≤ es que cada 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 completitud de X:

Si la topología de orden en X está conectada, X está completo.
X está conexo bajo la topología de orden si y solo si es completo y no hay ningún espacio en X (un espacio son dos puntos a y b en X con a < b tales que ningún c satisface a < c < b ).
X es completo si y sólo 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 red 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 extendido por afinidad (recta de números reales extendida). Existen homeomorfismos que preservan el orden entre estos ejemplos.

Sumas de pedidos

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

Para , se cumple si y sólo si se cumple una de las siguientes condiciones:

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

x\leq _{+}y

$x,y\en A_{1}$ y $estilo de visualización x\leq _{1}y}$
$x,y\en A_{2}$ y $estilo de visualización x\leq _{2}y}$
$x\en A_{1}$ y $y\in A_{2}$

Intuitivamente, esto significa que los elementos del segundo conjunto se agregan encima de 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 $(yo,\leq)$ $i\en I$ $(A_{i},\leq _{i})$ $Estilo de visualización A_{i}}$ $\bigcup _ {i}A_ {i}$

Para , se cumple si:

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

x\leq y

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

Decidibilidad

La teoría de primer orden de los órdenes totales es decidible , es decir, existe un algoritmo para decidir qué enunciados de primer orden son válidos para todos los órdenes totales. Al utilizar la interpretabilidad en S2S , la teoría monádica de segundo orden de los órdenes totales contables también es decidible. ^[16]

Órdenes sobre el producto cartesiano de conjuntos totalmente ordenados

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

Orden lexicográfico : ( a , b ) ≤ ( c , d ) si y sólo 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 sólo si ( a < c y b < d ) o ( a = c y b = d ) (la clausura reflexiva 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.

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

Véase 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 .

Sólo 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 . ^[17]

Véase también

Anillo artiniano : anillo que satisface la condición de cadena descendente en ideales.
Línea Countryman
Teoría del orden – Rama de las matemáticas
Permutación – Versión matemática de un cambio de orden
Orden de prefijo : generalización de la noción de prefijo de una cadena y de la noción de árbol : un orden parcial total descendente
Problema de Suslin : la proposición, independiente de ZFC, de que un orden total denso completo no vacío e ilimitado que satisface la condición de cadena contable es isomorfo a los números reales.
Buen orden – Clase de ordenamientos matemáticos

Notas

^ desde Halmos 1968, Cap.14.
^ desde Birkhoff 1967, pág. 2.
^ de Schmidt y Ströhlein 1993, pág. 32.
^ Fuchs 1963, pág. 2.
^ abc Davey y Priestley 1990, pág. 3.
^ Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1 de agosto de 1990). "Ordenación de caracteres y cadenas". ACM SIGAda Ada Letters (7): 84. doi : 10.1145/101120.101136 . S2CID : 38115497.
^ Ganapathy, Jayanthi (1992). "Elementos máximos y límites superiores en conjuntos parciales". Pi Mu Epsilon Journal . 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.
^ Supongamos por contradicción que también . Luego por transitividad, lo que contradice la irreflexividad. $a<b$ $b<a$ $a<a$
^ Si , no por asimetría. $a<a$ $a<a$
^ Esta definición se asemeja a la de un objeto inicial de una categoría , pero es más débil.
^ Roland Fraïssé (diciembre de 2000). Teoría de las relaciones. Estudios de lógica y fundamentos de las matemáticas. Vol. 145 (1.ª ed.). Elsevier. ISBN 978-0-444-50542-2.Aquí: p. 35
^ Brian A. Davey y Hilary Ann Priestley (1990). Introducción a los retículos y el orden . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. Número de LCCN : 89009753.Aquí: p. 100
^ Yiannis N. Moschovakis (2006) Notas sobre la teoría de conjuntos , Textos de pregrado en matemáticas (Birkhäuser) ISBN 0-387-28723-X , pág. 116
^ es decir, más allá de algún índice, todos los demás miembros de la secuencia son iguales
^ Davey y Priestly 1990, Def.2.24, pág. 37
^ Weyer, Mark (2002). "Decidibilidad de S1S y S2S". Autómatas, lógicas y juegos infinitos . Apuntes de clase en informática. Vol. 2500. Springer. págs. 207–230. doi :10.1007/3-540-36387-4_12. ISBN. 978-3-540-00388-5.
^ Macpherson, H. Dugald (2011), "Un estudio de estructuras homogéneas", Discrete Mathematics , 311 (15): 1599–1634, doi : 10.1016/j.disc.2011.01.024

Referencias

Birkhoff, Garrett (1967). Teoría de retículos . Colloquium Publications. Vol. 25. Providence: Am. Math. Soc.
Davey, Brian A.; Priestley, Hilary Ann (1990). Introducción a los retículos y el orden . Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. Número de 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 de conjuntos ingenua . 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 gráficos: matemáticas discretas para científicos informáticos. Berlín: Springer-Verlag. ISBN 978-3-642-77970-1.

Enlaces externos

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