stringtranslate.com

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 :

  1. ( reflexivo ).
  2. Si y entonces ( transitivo ).
  3. Si y entonces ( antisimétrico ).
  4. o ( fuertemente conectado , antes llamado total).

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-perdido [6] [7] . El término cadena se define a veces 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.

Ó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 :

  1. No ( irreflexivo ).
  2. Si entonces no ( asimétrico ).
  3. Si y entonces ( transitivo ).
  4. Si , entonces o ( conectado ).

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:

Por el contrario, el cierre reflexivo de un orden total estricto es un orden total (no estricto).

Ejemplos

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

para todos a , b .

Entonces escribimos ab si y solo si . Por lo tanto, un conjunto totalmente ordenado es una red distributiva .

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 ab 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

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:

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 :

Para , se cumple si y sólo si se cumple una de las siguientes condiciones:
  1. y
  2. y
  3. y

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

Para , se cumple si:
  1. O bien hay alguno con
  2. o hay algunos en con ,

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:

Cada uno de estos órdenes extiende al siguiente en el sentido de que si tenemos xy 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 n , 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 n 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

Notas

  1. ^ desde Halmos 1968, Cap.14.
  2. ^ desde Birkhoff 1967, pág. 2.
  3. ^ de Schmidt y Ströhlein 1993, pág. 32.
  4. ^ Fuchs 1963, pág. 2.
  5. ^ abc Davey y Priestley 1990, pág. 3.
  6. ^ 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.
  7. ^ 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.
  8. ^ Supongamos por contradicción que también . Luego por transitividad, lo que contradice la irreflexividad.
  9. ^ Si , no por asimetría.
  10. ^ Esta definición se asemeja a la de un objeto inicial de una categoría , pero es más débil.
  11. ^ 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
  12. ^ 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
  13. ^ 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 
  14. ^ es decir, más allá de algún índice, todos los demás miembros de la secuencia son iguales
  15. ^ Davey y Priestly 1990, Def.2.24, pág. 37
  16. ^ 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.
  17. ^ 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

Enlaces externos