Orde 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 :
- (reflexiva).
- Se e entón (transitiva).
- Se e entón (antisimétrica).
- ou (fortemente conectado, antes chamado 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 | editar a fonte]
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 :
- Non (irreflexiva).
- Se entón non (asimétrica).
- Se e entón (transitiva).
- 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 | editar a fonte]
- 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 x1 ≤ x2 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 | editar a fonte]
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 | editar a fonte]
Teoría de retículas[editar | editar a fonte]
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 a ≤ b se e só se . Polo tanto, un conxunto totalmente ordenado é unha retícula distributiva.
Orde total finita[editar | editar a fonte]
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 ben-orde tipo de orde ω cos números naturais de xeito que respecte a ordenación (a comezaz por cero ou por un).
Teoría de categorías[editar | editar a fonte]
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 a ≤ b 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 | editar a fonte]
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 | editar a fonte]
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 | editar a fonte]
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:
- e
- e
- 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:
- Ou hai algún con
- ou hai algúns en con ,
Decidibilidade[editar | editar a fonte]
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 | editar a fonte]
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 b ≤ d). Esta é unha orde total.
- (a, b) ≤ ( c, d ) se e só se a ≤ c e b ≤ d (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 | editar a fonte]
Relacións binarias transitivas | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
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 |
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.
Notas[editar | editar a fonte]
- ↑ 1,0 1,1 Birkhoff 1967, p. 2.
- ↑ 2,0 2,1 Schmidt & Ströhlein 1993, p. 32.
- ↑ Fuchs 1963, p. 2.
- ↑ 4,0 4,1 4,2 Davey & Priestley 1990, p. 3.
- ↑ 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.
- ↑ Ganapathy, Jayanthi (1992). Maximal Elements and Upper Bounds in Posets. Pi Mu Epsilon Journal 9. pp. 462–464. ISSN 0031-952X. JSTOR 24340068.
- ↑ This definition resembles that of an initial object of a category, but is weaker.
- ↑ Halmos 1968.
- ↑ 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
- ↑ 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
- ↑ Davey and Priestly 1990, Def.2.24, p. 37
- ↑ 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 | editar a fonte]
Bibliografía[editar | editar a fonte]
- Birkhoff, Garrett (1967). Lattice Theory. Colloquium Publications 25. Providence: Am. Math. Soc.
- Davey, Brian A.; Priestley, Hilary Ann (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753.
- Fuchs, L (1963). Partially Ordered Algebraic Systems. Pergamon Press.
- George Grätzer (1971). Lattice theory: first concepts and distributive lattices. W. H. Freeman and Co. ISBN 0-7167-0442-0
- Halmos, Paul R. (1968). Naive Set Theory. Princeton: Nostrand.
- John G. Hocking and Gail S. Young (1961). Topology. Corrected reprint, Dover, 1988. ISBN 0-486-65676-4
- Rosenstein, Joseph G. (1982). Linear orderings. New York: Academic Press.
- Schmidt, Gunther; Ströhlein, Thomas (1993). Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin: Springer-Verlag. ISBN 978-3-642-77970-1.
Outros artigos[editar | editar a fonte]
Ligazóns externas[editar | editar a fonte]
- Totally ordered set. SpringerEOM. Total_order&oldid=35332.