Orde total

En matemàtiques, un orde total, orde llineal, orde simple, o simplement orde en un conjunt X és una relació binaria sobre X que és: reflexiva, transitiva, antisimètrica, i total; açò és, si es denota una tal relació per ≤, lo següent val per a qualssevol a, b, i c en X: Plantilla:Relació binaria 101

• Si a pertany a X, llavors a ≤ a (reflexiva).
• Si a ≤ b i b ≤ c, llavors a ≤ c (transitividad).
• Si a ≤ b i b ≤ a, llavors a = b (antisimetría).
• a ≤ b o b ≤ a (totalitat o completitud).

La propietat de totalitat d'esta relació és equivalent a dir que tot parell d'elements és comparable baixe la relació.

Un conjunt dotat d'un orde total es denomina conjunt totalment ordenat, linealmente ordenat, simplement ordenat, o cadena.

Note's que la condició de totalitat implica reflexividad, açò és, a ≤ a para tot a ∈ X; per lo tant, un orde total és també un orde parcial, açò és, una relació binaria reflexiva, antisimètrica, i transitiva. Un orde total, llavors, pugues també definir-se com un orde parcial que siga "total", i.i. que complixca en la condició de totalitat.

Com a alternativa, es pot definir un conjunt totalment ordenat com un tipo particular de retícul, en el que es té {a ∨ b, a ∧ b} = {a, b} per a qualssevol a, b. S'escriu llavors a ≤ b si i solament si a = a ∧ b. Es deduïx que un conjunt totalment ordenat és un retícul distributivo.

Els conjunts totalment ordenats formen una subcategoría completa de la categoria de conjunts parcialment ordenats, sent els morfismos funciones que respecten l'orde, és dir, funciones f tals que si a ≤ b llavors f(a) ≤ f(b). Una funció biyectiva entre dos conjunts totalment ordenats que respecte els dos órdens és un isomorfisme en esta categoria.

Orde total estricte

Per a cada orde total (no estricte) ≤ hi ha associada una relació asimètrica (i per tant irreflexiva) <, cridada orde total estricte, que pot definir-se de dos maneres equivalents:

• a < b sii a ≤ b i a ≠ b.
• a < b sii no b ≤ a (i.i., < és l'inversa del complement de ≤).

L'orde total estricte té les següents propietats, per a qualssevol a, b, i c en X:

• És transitivo: a < b i b < c implica a < c.
• És tricotómico: exactament una de a < b, b < a, i a = b és vàlida.
• És un preorden total.

Es pot treballar a l'inversa prenent < com una relació binaria transitiva i tricotómica; en eixe cas, un orde total no estricte ≤ es pot definir de dos maneres equivalents:

• a ≤ b sii a < b o a = b.
• a ≤ b sii no b < a.

Atres dos órdens associats són els complements ≥ i >, completant aixina el conjunt {<, >, ≤, ≥}. Es pot definir o explicar l'orde total d'un conjunt usant qualsevol de les quatre relacions; la notació deixarà en clar si es parla d'un orde estricte o no.

Eixemples

• Les lletres de l'alfabet en l'orde alfabètic usual: A < B < C < X.
• Qualsevol subconjunt d'un conjunt totalment ordenat, restringint a ell, l'orde del conjunt complet.
• Tot conjunt parcialment ordenat X a on qualssevol dos elements es poden comparar (i.i. para tot parell d'elements a i b en X, a ≤ b o b ≤ a).
• Tot conjunt de número cardinal o números ordinals (més encara, estos són ben ordenats).
• Si X és un conjunt i f una funció inyectiva de X a un conjunt totalment ordenat, f induïx un orde total en X prenent x < i si i solament si f(x) < f(i).

• l'orde lexicogràfic en el producte cartesiano de qualsevol colecció de conjunts totalment ordenats és en sí mateixa un orde total. Per eixemple, qualsevol conjunt de paraules en l'orde alfabètic usual està totalment ordenat, vist com un subconjunt del producte cartesiano d'un conjunt finito de símbols, l'alfabet en un espai buit (que es definix menor que qualsevol lletra), un número contable de voltes.
• Els naturals, sancers, racionals i els reals, en l'orde usual de les relacions < o >, són conjunts totalment ordenats. Cada u d'ells és un cas únic (mòdul isomorfisme) i mínim de conjunt totalment ordenat en alguna propietat (un conjunt totalment ordenat A és el mínim en certa propietat si, per a tot conjunt B en la propietat, hi ha un isomorfisme d'orde entre A i un subconjunt de B):
  • Els naturals formen el mínim conjunt totalment ordenat sense cota superior.
  • Els sancers formen el mínim conjunt totalment ordenat sense cota superior ni inferior.
  • Els racionals formen el mínim conjunt totalment ordenat sense cota superior ni inferior que ademés és dens, és dir, que para qualssevol a i b en a < b, existix un c tal que a < c < b.
  • Els reals són el mínim conjunt totalment ordenat no acotat i conexo (vore més alvance la definició de la topología).