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 $\leq$ nalgún conxunto $X$ , que satisfaga o seguinte para todos os $a,b$ e $c$ en $X$ :

$a\leq a$ (reflexiva).
Se $a\leq b$ e $b\leq c$ entón $a\leq c$ (transitiva).
Se $a\leq b$ e $b\leq a$ entón $a=b$ (antisimétrica).
$a\leq b$ ou $b\leq a$ (fortemente conexa, 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.

Relacións binarias transitivas

	Simétrica	Antisimétrica	Conexa	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	Conexa	Ben fundada	Ten joins	Ten meets	Reflexiva	Irreflexiva	Asimétrica
Definicións, para todo $a,b$ e $S\neq \varnothing :$	${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$	${\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}$	${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}$	${\begin{aligned}\min S\\{\text{existe}}\end{aligned}}$	${\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}$	${\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}$	$aRa$	${\text{non }}aRa$	${\begin{aligned}aRb\Rightarrow \\{\text{non }}bRa\end{aligned}}$

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 $R$ sexa transitiva: para todo $a,b,c,$ se $aRb$ e $bRc$ entón $aRc.$
Algunha definición dalgún termo pode requerir propiedades adicionais non recollidas na táboa.

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

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

Non $a<a$ (irreflexiva).
Se $a<b$ entón non $b<a$ (asimétrica).
Se $a<b$ e $b<c$ entón $a<c$ (transitiva).
Se $a\neq b$ , entón $a<b$ ou $b<a$ (conexa).

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

$a<b$ se $a\leq b$ e $a\neq b$ (redución reflexiva).
$a<b$ se non $b\leq a$ (é dicir, $<$ é o complemento da inversa de $\leq$ ).

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

Exemplos

Calquera subconxunto dun conxunto $X$ totalmente ordenado está totalmente ordenado para a restrición da orde en $X$ .
A única orde no conxunto baleiro, $\emptyset$ , é 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 $x 1 \leq x 2$ se e só se $f (x 1) \leq f (x 2)$ .
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

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

Teoría de retículas

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

\{a\vee b,a\wedge b\}=\{a,b\}

para todos os a, b.

Escribimos entón a ≤ b se e só se $a=a\wedge b$ . Polo tanto, un conxunto totalmente ordenado é unha retícula distributiva.

Orde total finita

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 $\omega$ cos números naturais de xeito que respecte a ordenación (pode comezar por cero ou por un).

Teoría de categorías

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

Para calquera conxunto $X$ totalmente ordenado podemos definir os intervalos abertos

$(a, b) = {x | a < x e x < b}$ ,
$(-\infty, b) = {x | x < b}$ ,
$(a, \infty) = {x | a < x}$ ,
$(-\infty, \infty) = 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.

Completude

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

Para dúas ordes totais disxuntas calquera $(A_{1},\leq _{1})$ e $(A_{2},\leq _{2})$ , hai unha orde natural $\leq _{+}$ no conxunto $A_{1}\cup A_{2}$ , que se chama suma das dúas ordes ou ás veces só $A_{1}+A_{2}$ :

Para

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

,

x\leq _{+}y

cúmprese se e só se cumpre un dos seguintes:

$x,y\in A_{1}$ e $x\leq _{1}y$
$x,y\in A_{2}$ e $x\leq _{2}y$
$x\in A_{1}$ e $y\in A_{2}$

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

De xeito máis xeral, se $(I,\leq )$ é un conxunto de índices totalmente ordenado, e para cada $i\in I$ a estrutura $(A_{i},\leq _{i})$ é unha orde linear, onde os conxuntos $A_{i}$ son disxuntas por parellas, entón a orde total natural $\bigcup _{i}A_{i}$ está definida por

Para

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

,

x\leq y

cúmprese se:

Ou hai algún $i\in I$ con $x\leq _{i}y$
ou hai algúns $i<j$ en $I$ con $x\in A_{i}$ , $y\in A_{j}$

Decidibilidade

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

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 Rⁿ, cada un delas convérteno nun espazo vectorial ordenado.

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

Estruturas relacionadas

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

Un grupo cunha orde total compatíbel é un grupo totalmente ordenado.

Notas

↑ ^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

Bibliografía

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

Ligazóns externas

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

[FOOTNOTEBirkhoff19672-1] 1,0 ^1,1 Birkhoff 1967, p. 2.

[FOOTNOTESchmidtStröhlein199332-2] 2,0 ^2,1 Schmidt & Ströhlein 1993, p. 32.

[FOOTNOTEFuchs19632-3] Fuchs 1963, p. 2.

[FOOTNOTEDaveyPriestley19903-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.

[FOOTNOTEHalmos1968-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]