Orden total

Orden cuyos elementos son todos comparables.

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 : ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle a,b}$ ${\displaystyle c}$ ${\displaystyle X}$

1. ${\displaystyle a\leq a}$( reflexivo ).
2. Si y entonces ( transitivo ). ${\displaystyle a\leq b}$ ${\displaystyle b\leq c}$ ${\displaystyle a\leq c}$
3. Si y entonces ( antisimétrico ). ${\displaystyle a\leq b}$ ${\displaystyle b\leq a}$ ${\displaystyle a=b}$
4. ${\displaystyle a\leq b}$o ( fuertemente conectado , antes llamado total). ${\displaystyle b\leq a}$

La reflexividad (1.) ya se deriva de la conexión (4.), pero muchos autores la exigen explícitamente para indicar el parentesco con órdenes parciales. ^[1] Los pedidos totales a veces también se denominan pedidos simples , ^[2] conectados , ^[3] o 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 loset ^{[6] [7] .} El término cadena a veces se define como sinónimo de conjunto totalmente ordenado , ^[5] pero se refiere generalmente a algún tipo de subconjuntos totalmente ordenados de un conjunto parcialmente ordenado dado.

Una extensión de un orden parcial dado a un orden total se llama 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 : ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle <}$ ${\displaystyle X}$ ${\displaystyle a,b}$ ${\displaystyle c}$ ${\displaystyle X}$

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

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

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) hay una relación asociada , llamada orden total estricta asociada , que se puede definir de dos formas equivalentes: ${\displaystyle \leq }$ ${\displaystyle <}$ ${\displaystyle \leq }$

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

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

Ejemplos

• Cualquier subconjunto de un conjunto X totalmente ordenado está totalmente ordenado por la restricción del orden en X .
• El orden único en el conjunto vacío, ∅ , es un orden total.
• Cualquier conjunto de números cardinales o números ordinales (más claramente, son de buen orden ).
• 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 estableciendo x ₁ ≤ x ₂ si y sólo si f ( x ₁ ) ≤ f ( x ₂ ) .
• El orden lexicográfico sobre 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 habituales "menor o igual que" (≤) o "mayor o igual que" (≥) está totalmente ordenado. De ahí que cada subconjunto de los números reales esté totalmente ordenado, como los números naturales , los enteros y los números racionales . Se puede demostrar que cada uno de estos es el "ejemplo inicial" único (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 tenga la propiedad, hay un isomorfismo de orden de A a un subconjunto de B ): ^{[10] [ cita necesaria ]}
  • Los números naturales forman un conjunto inicial no vacío, totalmente ordenado y 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 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. Todo 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.
• Las letras del alfabeto ordenadas según el orden estándar del diccionario , por ejemplo, A < B < C , etc., son un orden total estricto.

Cadenas

El término cadena a veces se define 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 por 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 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 X parcialmente ordenado tiene un límite superior en X , entonces X contiene al menos un elemento máximo. ^[12] El lema de Zorn se usa comúnmente siendo X un conjunto de subconjuntos; en este caso, el límite superior se obtiene demostrando que la unión de los elementos de una cadena en X es en X . Esta es la forma que se utiliza generalmente para demostrar que un espacio vectorial tiene bases de Hamel y que un anillo tiene ideales máximos .

En algunos contextos, las cadenas que se consideran son de orden isomorfas 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, una orden está fundada 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, sólo se consideran cadenas que son conjuntos finitos . En este caso se habla de una cadena finita , muchas veces 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. ^[15] 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 utilizar para algunos subconjuntos de estructuras totalmente ordenados 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 paseo en un gráfico .

Otros conceptos

Teoría de la red

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

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$para todos a , b .

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

Pedidos totales finitos

Un simple argumento de conteo verificará que cualquier conjunto finito totalmente ordenado no vacío (y, por tanto, cualquier subconjunto no vacío del mismo) tiene un elemento mínimo. Por tanto, todo orden total finito es de hecho un orden de pozo . Ya sea mediante prueba directa o observando que todo orden de pozo es de orden isomorfo a un ordinal , se puede demostrar que todo 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 órdenes totales finitas u órdenes de pozos con tipo de orden ω 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 orden

Para cualquier conjunto X totalmente ordenado podemos definir los intervalos abiertos

• ( una , segundo ) = { x | a < x y x < b } ,
• (−∞, segundo ) = { x | x < b } ,
• ( una , ∞) = { 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 un orden en un conjunto, se habla de la topología del orden inducida por un orden particular. Por ejemplo, si N son los números naturales, < es menor que y > 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 del 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 los números reales R es completo pero el conjunto de los números racionales Q no lo es. En otras palabras, los diversos conceptos de integridad (que no debe confundirse con ser "total") no se trasladan a restricciones . Por ejemplo, sobre los números reales una propiedad de la relación ≤ es que cada subconjunto S no vacío 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 ≤ con los números racionales.

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

• Si la topología de orden en X está conectada, X está completo.
• X está conectado bajo la topología de orden si y solo si está completo y no hay un espacio en X (un espacio son dos puntos a y b en X con a < b tal 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 afínmente extendido (recta de números reales extendida). Hay homeomorfismos que preservan el orden entre estos ejemplos.

sumas de pedidos

Para dos órdenes totales disjuntos cualesquiera y , hay un orden natural en el conjunto , que se llama 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 cumple si y sólo si se cumple una de las siguientes condiciones: ${\displaystyle x,y\in A_{1}\cup A_{2}}$ ${\displaystyle x\leq _{+}y}$

1. ${\displaystyle x,y\in A_{1}}$y ${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$y ${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$y ${\displaystyle 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 está definido por ${\displaystyle (I,\leq )}$ ${\displaystyle i\in I}$ ${\displaystyle (A_{i},\leq _{i})}$ ${\displaystyle A_{i}}$ ${\displaystyle \bigcup _{i}A_{i}}$

Para , se cumple si: ${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$ ${\displaystyle x\leq y}$

1. O hay algunos con ${\displaystyle i\in I}$ ${\displaystyle x\leq _{i}y}$
2. o hay algunos con , ${\displaystyle i<j}$ ${\displaystyle I}$ ${\displaystyle x\in A_{i}}$ ${\displaystyle 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é afirmaciones de primer orden son válidas para todos los órdenes totales. Utilizando la interpretabilidad en S2S , la teoría monádica de segundo orden de órdenes totales contables también es decidible. ^[dieciséis]

Órdenes sobre el producto cartesiano de conjuntos totalmente ordenados

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

• 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 pedido 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 pedidos totales estrictos correspondientes). Esta también es una orden parcial.

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 convierte en un espacio vectorial ordenado .

Véanse 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 resulta en 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]

Ver también

• Anillo artiniano  : anillo que satisface la condición de cadena descendente de idealesPages displaying wikidata descriptions as a fallback
• linea paisana
• Teoría del orden  - Rama de las matemáticas
• Permutación  : versión matemática de un cambio de orden
• Orden de prefijos  – generalización de la noción de prefijo de una cadena y de la noción de árbol Pages displaying wikidata descriptions as a fallback– un orden parcial total descendente
• El problema de Suslin  : la proposición, independiente de ZFC, de que un orden total denso, completo, ilimitado y no vacío que satisface la condición de cadena contable es isomorfo a los realesPages displaying wikidata descriptions as a fallback
• Bien-orden  - Clase de ordenamiento matemático

Notas

1. Halmos 1968, capítulo 14.
2. Birkhoff 1967, pág. 2.
3. Schmidt y Ströhlein 1993, pág. 32.
4. Fuchs 1963, pág. 2.
5. Davey y Priestley 1990, pág. 3.
6. Strohmeier, Alfred; Genillard, cristiano; Weber, Mats (1 de agosto de 1990). "Ordenamiento de caracteres y cadenas". ACM SIGada Ada Letras (7): 84. doi : 10.1145/101120.101136 . S2CID  38115497.
7. Ganapathy, Jayanthi (1992). "Elementos máximos y límites superiores en posets". Diario Pi Mu Epsilon . 9 (7): 462–464. ISSN  0031-952X. JSTOR  24340068.
8. Supongamos por contradicción que también . Luego por la transitividad, que contradice la irreflexividad. ${\displaystyle a<b}$ ${\displaystyle b<a}$ ${\displaystyle a<a}$
9. Si , no por asimetría. ${\displaystyle a<a}$ ${\displaystyle a<a}$
10. Esta definición se parece 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ág. 35
12. Brian A. Davey y Hilary Ann Priestley (1990). Introducción a las celosías y al orden . Libros de texto de matemáticas de Cambridge. Prensa de la Universidad de Cambridge. ISBN 0-521-36766-2. LCCN  89009753.Aquí: pág. 100
13. Yiannis N. Moschovakis (2006) Notas sobre teoría de conjuntos , Textos de pregrado en matemáticas (Birkhäuser) ISBN 0-387-28723-X , p. 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 conferencias sobre informática. vol. 2500. Saltador. 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", Matemáticas discretas , 311 (15): 1599-1634, doi : 10.1016/j.disc.2011.01.024

Referencias

• Birkhoff, Garrett (1967). Teoría de la celosía . Publicaciones del Coloquio. vol. 25. Providencia: Enm. Matemáticas. Soc.
• Davey, Brian A.; Priestley, Hilary Ann (1990). Introducción a las celosías y al 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 . Prensa de Pérgamo.
• George Grätzer (1971). Teoría de celosías: primeros conceptos y celosías distributivas. WH Freeman y compañía 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, Günther ; 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", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]