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

1. ${\displaystyle a\leq a}$ (reflexiva).
2. Se ${\displaystyle a\leq b}$ e ${\displaystyle b\leq c}$ entón ${\displaystyle a\leq c}$ (transitiva).
3. Se ${\displaystyle a\leq b}$ e ${\displaystyle b\leq a}$ entón ${\displaystyle a=b}$ (antisimétrica).
4. ${\displaystyle a\leq b}$ ou ${\displaystyle 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 v c e
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 ${\displaystyle a,b}$ e ${\displaystyle S\neq \varnothing :}$ ${\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}aRb{\text{ e }}&bRa\\\Rightarrow a={}&b\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ ou }}&bRa\end{aligned}}}$ ${\displaystyle {\begin{aligned}\min S\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\vee b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle {\begin{aligned}a\wedge b\\{\text{existe}}\end{aligned}}}$ ${\displaystyle aRa}$ ${\displaystyle {\text{non }}aRa}$ ${\displaystyle {\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 ${\displaystyle R}$ sexa transitiva: para todo ${\displaystyle a,b,c,}$ se ${\displaystyle aRb}$ e ${\displaystyle bRc}$ entón ${\displaystyle 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.

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.