Orde total

relación binaria que é reflexiva, transitiva, antisimétrica e total

En matemáticas, unha orde total ou orde linear é unha orde parcial na que dous elementos calquera son comparables. É dicir, unha orde total é unha relación binaria nalgún conxunto , que satisfaga o seguinte para todos os e en :

  1. (reflexiva).
  2. Se e entón (transitiva).
  3. Se e entón (antisimétrica).
  4. ou (fortemente conectada, antes chamada total).

A orde total ás veces tamén se chama simple,[1] connex,[2] ou orde completa.[3]

Un conxunto equipado cunha orde total é un conxunto totalmente ordenado; [4] tamén se usan os termos conxunto ordenado simple, [1] conxunto ordenado lineaemente, [2] [4] e loset [5][6]. O termo cadea defínese ás veces como un sinónimo de conxunto totalmente ordenado, [4] mais refírese xeralmente a subconxuntos totalmente ordenados dun conxunto parcialmente ordenado.

A extensión dunha orde parcial dada a unha orde total chámase extensión linear desa orde parcial.

Orde total estrita e non estrita

editar

Unha orde total estrita nun conxunto   é unha orde parcial estrita   no que calquera dous elementos distintos son comparables. É dicir, unha orde total estrita é unha relación binaria   nalgún conxunto  , que satisfaga o seguinte para todos os   e   en  :

  1. Non   (irreflexiva).
  2. Se   entón non   (asimétrica).
  3. Se   e   entón   (transitiva).
  4. Se  , entón   ou   (conectada).

Por cada orde total (non estrita)   existe unha relación asociada  , chamada orde total estrita asociada a   que se pode definir de dúas formas equivalentes:

  •   se   e   (redución reflexiva).
  •   se non   (é dicir,   é o complemento da inversa de   ).

No outro sentido, o pechamento reflexivo dunha orde total estrita   é unha orde total (non estrita).

Exemplos

editar
  • Calquera subconxunto dun conxunto X totalmente ordenado está totalmente ordenado para a restrición da orde en X.
  • A única orde no conxunto baleiro, , é unha orde total.
  • Calquera conxunto de números cardinais ou números ordinais (de feito son ben-ordes).
  • Se X é calquera conxunto e f unha función inxectiva de X a un conxunto totalmente ordenado, entón f induce unha orde total en X establecendo x1x2 se e só se f(x1) ≤ f(x2) .
  • A orde lexicográfica sobre o produto cartesiano dunha familia de conxuntos totalmente ordenados, indexados por un conxunto ben-ordenado, é en si mesma unha orde total.
  • O conxunto de números reais ordenados polas relacións habituais "menor ou igual a" (≤) ou "maior ou igual a" (≥) está totalmente ordenado. Polo tanto, cada subconxunto dos números reais está totalmente ordenado, como os números naturais, os enteiros e os números racionais. Pódese demostrar que cada un destes é o "exemplo inicial" único (ata un isomorfismo de orde) dun conxunto totalmente ordenado cunha determinada propiedade (aquí, unha orde total A é inicial para unha propiedade, se, sempre que B ten a propiedade, hai un isomorfismo de orde de A a un subconxunto de B): [7] 
    • Os nú[ cita necesaria ]meros naturais forman un conxunto inicial totalmente ordenado non baleiro sen elemento maiorante.
    • Os enteiros forman un conxunto inicial totalmente ordenado non baleiro sen elemento maiorante nin minorante.
    • Os números racionais forman un conxunto inicial totalmente ordenado que é denso nos números reais. Ademais, a redución reflexiva < é unha orde densa sobre os números racionais.
    • Os números reais forman un conxunto inicial totalmente ordenado ilimitado que está conectado na topoloxía de orde (definida a continuación).
  • Os corpos ordenados están totalmente ordenados por definición. Inclúen os números racionais e os números reais. Cada corpo ordenado contén un subcampo ordenado isomorfo aos números racionais. Calquera corpo ordenado completo de Dedekind é isomorfo aos números reais.
  • As letras do alfabeto ordenadas pola orde estándar do dicionario, por exemplo, A < B < C etc., é unha orde total estrita.

Cadeas

editar

O termo cadea ás veces defínese como sinónimo dun conxunto totalmente ordenado, mais xeralmente úsase para referirse a un subconxunto dun conxunto parcialmente ordenado que está totalmente ordenado para a orde inducida. [8] [9] Normalmente, o conxunto parcialmente ordenado é un conxunto de subconxuntos dun conxunto dado que se ordena por inclusión, e o termo úsase para indicar as propiedades do conxunto das cadeas. Este elevado número de niveis aniñados de conxuntos explica a utilidade do termo.

Un exemplo común do uso de cadea para referirse a subconxuntos totalmente ordenados é o lema de Zorn que afirma que, se cada cadea dun conxunto parcialmente ordenado X ten un elemento maiorante en X, entón X contén polo menos un elemento maximal.[10]

Nalgúns contextos, as cadeas que se consideran son de orde isomórfica aos números naturais coa súa orde habitual ou a súa orde oposta. Neste caso, unha cadea pódese identificar cunha secuencia monótona, e chámase cadea ascendente ou descendente, dependendo de se a secuencia é crecente ou decrecente.

Un conxunto parcialmente ordenado ten a condición de cadea descendente se cada cadea descendente finalmente se estabiliza (acolá de certo índice, todos os membros da secuencia son iguais). Por exemplo, unha orde está ben fundada se ten a condición de cadea descendente. Do mesmo xeito, a condición de cadea ascendente significa que cada cadea ascendente eventualmente se estabiliza. Por exemplo, un anel Noetheriano é un anel cuxos ideais satisfán a condición de cadea ascendente.

Noutros contextos, só se consideran cadeas que son conxuntos finitos. Neste caso, fálase dunha cadea finita, moitas veces acurtada como cadea. Neste caso, a lonxitude dunha cadea é o número de desigualdades (ou inclusións de conxunto) entre elementos consecutivos da cadea; é dicir, o número menos un dos elementos da cadea. [11] Así, un conxunto unitario é unha cadea de lonxitude cero e un par ordenado é unha cadea de lonxitude un. A dimensión dun espazo adoita definirse ou caracterizarse como a lonxitude máxima de cadeas de subespazos. Por exemplo, a dimensión dun espazo vectorial é a lonxitude máxima das cadeas de subespazos lineais, e a dimensión de Krull dun anel conmutativo é a lonxitude máxima das cadeas dos ideais primos.

Outros conceptos

editar

Teoría de retículas

editar

Pódese definir un conxunto totalmente ordenado como un tipo particular de retícula, aquela na que temos

  para todos os a, b.

Escribimos entón ab se e só se   . Polo tanto, un conxunto totalmente ordenado é unha retícula distributiva.

Orde total finita

editar

Unha orde total nun conxunto con k elementos induce unha bixección cos primeiros k números naturais. Polo tanto, é común indexar unha orde total finita ou unha boa orde con tipo de orde   cos números naturais de xeito que respecte a ordenación (pode comezar por cero ou por un).

Teoría de categorías

editar

Os conxuntos totalmente ordenados forman unha subcategoría completa da categoría de conxuntos parcialmente ordenados, sendo os morfismos mapas que respectan as ordes, é dicir, mapas f tal que se ab entón f(a) ≤ f(b).

Un mapa bixectivo entre dous conxuntos totalmente ordenados que respecta as dúas ordes é un isomorfismo nesta categoría.

Topoloxía da orde

editar

Para calquera conxunto X totalmente ordenado podemos definir os intervalos abertos

  • (a, b) = x ,
  • (−∞, b) = x ,
  • (a, ∞) = x ,
  • (−∞, ∞) = X.

Podemos usar estes intervalos abertos para definir unha topoloxía en calquera conxunto ordenado, a topoloxía de orde.

Cando se usa máis dunha orde nun conxunto fálase da topoloxía da orde inducida por unha orde particular. Por exemplo, se N son os números naturais, < é menor e > maior do que poderiamos referirnos á topoloxía de orde en N inducida por < e á topoloxía de orde en N inducida por > (neste caso son idénticas mais poden en xeral non selo).

A topoloxía da orde inducida por unha orde total pode mostrarse que é hereditariamente normal.

Completitude

editar

Un conxunto totalmente ordenado dise que é completo se cada subconxunto non baleiro que teña un elemento maiorante ten un supremo. Por exemplo, o conxunto de números reais R é completo pero o conxunto de números racionais Q non. Noutras palabras, os distintos conceptos de integridade (que non deben confundirse con "total") non se trasladan ás restricións. Por exemplo, sobre os números reais unha propiedade da relación ≤ é que todo subconxunto non baleiro S de R cun elemento maiorante en R ten un supremo en R. Non obstante, para os números racionais este supremo non é necesariamente racional, polo que a mesma propiedade non se aplica á restrición da relación ≤ cos números racionais.

Un conxunto totalmente ordenado (coa súa topoloxía da orde) que é unha retícula completa é compacto. Exemplos son os intervalos pechados de números reais, por exemplo, o intervalo unidade [0,1], e o sistema de números reais estendido. Tamén hai homeomorfismos que conservan a orde entre estes exemplos.

Sumas de ordes

editar

Para dúas ordes totais disxuntas calquera   e  , hai unha orde natural   no conxunto , que se chama suma das dúas ordes ou ás veces só  :

Para  ,   cúmprese se e só se cumpre un dos seguintes:
  1.   e  
  2.   e  
  3.   e  

Intuitivamente, isto significa que os elementos do segundo conxunto superpóñense aos elementos do primeiro conxunto.

De xeito máis xeral, se   é un conxunto de índices totalmente ordenado, e para cada   a estrutura   é unha orde linear, onde os conxuntos   son disxuntas por parellas, entón a orde total natural   está definida por

Para  ,   cúmprese se:
  1. Ou hai algún   con  
  2. ou hai algúns   en   con  ,  

Decidibilidade

editar

A teoría de ordes totais de primeira orde é decidible, é dicir, hai un algoritmo para decidir que declaracións de primeira orde se cumpren para toda orde total. Usando a interpretabilidade en S2S, a teoría monádica de segunda orde das ordes totais numerables tamén é decidible. [12]

Orde sobre o produto cartesiano de conxuntos totalmente ordenados

editar

En orde crecente de forza, tres das posibles ordes do produto cartesiano de dous conxuntos totalmente ordenados son:

  • Orde lexicográfica: ( a, b ) ≤ ( c, d ) se e só se a < c ou (a = c e bd). Esta é unha orde total.
  • (a, b) ≤ ( c, d ) se e só se ac e bd (orde do produto). Esta é unha orde parcial.
  • (a, b) ≤ ( c, d ) se e só se (a < c e b < d) ou (a = c e b = d) (o pechamento reflexivo do produto directo das correspondentes ordes totais estritas). Esta é tamén unha orde parcial.

As tres poden definirse de xeito similar para o produto cartesiano de máis de dous conxuntos.

Aplicadas ao espazo vectorial Rn, cada un delas convérteno nun espazo vectorial ordenado.

Unha función real de n variables reais definidas nun subconxunto de Rn define unha orde débil estrita e unha preorde total correspondente nese subconxunto.

Estruturas relacionadas

editar

 

Relacións binarias transitivas
Simétrica Antisimétrica Conectada Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica
Relación de equivalencia   Si   Non   Non   Non   Non   Non   Si   Non   Non
Preorde (Cuasiorde)   Non   Non   Non   Non   Non   Non   Si   Non   Non
Orde parcial   Non   Si   Non   Non   Non   Non   Si   Non   Non
Preorde total   Non   Non   Si   Non   Non   Non   Si   Non   Non
Orde total   Non   Si   Si   Non   Non   Non   Si   Non   Non
Pre-Ben ordenada   Non   Non   Si   Si   Non   Non   Si   Non   Non
Cuasi-Ben ordenada   Non   Non   Non   Si   Non   Non   Si   Non   Non
Ben ordenada   Non   Si   Si   Si   Non   Non   Si   Non   Non
Retícula   Non   Si   Non   Non   Si   Si   Si   Non   Non
Semiretícula superior (join)   Non   Si   Non   Non   Si   Non   Si   Non   Non
Semiretícula inferior (meet)   Non   Si   Non   Non   Non   Si   Si   Non   Non
Orde estrita parcial   Non   Si   Non   Non   Non   Non   Non   Si   Si
Orde estrita feble   Non   Si   Non   Non   Non   Non   Non   Si   Si
Orde estrita total   Non   Si   Si   Non   Non   Non   Non   Si   Si
Simétrica Antisimétrica Conectada Ben fundada Ten joins Ten meets Reflexiva Irreflexiva Asimétrica
Definicións, para todo   e                    
  Si indica que a columna da propiedade é sempre verdadeira no termo da fila (na esquerda de todo), mentres que   Non indica que a propiedade non está garantida en xeral (pode cumprirse ou non). Por exemplo, toda relación de equivalencia é simétrica, mais non necesariamente antisimétrica, está indicada por   Si na columna "Simétrica" e   Non na columna "Antisimétrica".

Todas as definicións requiren tacitamente que a relación homoxénea   sexa transitiva: para todo   se   e   entón  
Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.


Unha relación binaria que é antisimétrica, transitiva e reflexiva (mais non necesariamente total) é unha orde parcial.

Un grupo cunha orde total compatible é un grupo totalmente ordenado.

  1. 1,0 1,1 Birkhoff 1967, p. 2.
  2. 2,0 2,1 Schmidt & Ströhlein 1993, p. 32.
  3. Fuchs 1963, p. 2.
  4. 4,0 4,1 4,2 Davey & Priestley 1990, p. 3.
  5. Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1990-08-01). Ordering of characters and strings. ACM SIGAda Ada Letters (en inglés). p. 84. doi:10.1145/101120.101136. 
  6. Ganapathy, Jayanthi (1992). Maximal Elements and Upper Bounds in Posets. Pi Mu Epsilon Journal 9. pp. 462–464. ISSN 0031-952X. JSTOR 24340068. 
  7. This definition resembles that of an initial object of a category, but is weaker.
  8. Halmos 1968.
  9. Roland Fraïssé (Dec 2000). Theory of Relations. Studies in Logic and the Foundations of Mathematics 145 (1st ed.). Elsevier. ISBN 978-0-444-50542-2.  p. 35
  10. Brian A. Davey and Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753.  p. 100
  11. Davey and Priestly 1990, Def.2.24, p. 37
  12. Weyer, Mark (2002). "Decidability of S1S and S2S". Automata, Logics, and Infinite Games. Lecture Notes in Computer Science 2500. Springer. pp. 207–230. ISBN 978-3-540-00388-5. doi:10.1007/3-540-36387-4_12. 

Véxaxe tamén

editar

Bibliografía

editar

Outros artigos

editar

Ligazóns externas

editar
  • Totally ordered set. SpringerEOM. Total_order&oldid=35332.