Ordre total

En matemàtiques, un ordre lineal, ordre total, ordre simple o també ordenació és una relació binària (que en aquest article denotarem mitjançant per l'infix ≤) en un conjunt X. Aquesta relació és transitiva, antisimètrica i total. Un conjunt amb un ordre total s'anomena conjunt totalment ordenat, o cadena.

Si X és totalment ordenat per ≤, llavors les següents afirmacions són certes per a, b i c de X qualssevol:

• Si a ≤ b i b ≤ a, llavors a = b (antisimetria).
• Si a ≤ b i b ≤ c, llavors a ≤ c (transitivitat).
• Es té que a ≤ b o bé b ≤ a (totalitat).

L'antisimetria elimina els casos incerts en què a precedeix b i alhora b precedeix a.^[1] Una relació amb la propietat de «totalitat» vol dir que tot parell d'elements del conjunt de la relació són comparables per la relació. Això també vol dir que el conjunt es pot simbolitzar com una línia d'elements.^[2] La totalitat també implica la reflexivitat, és a dir, a ≤ a. Per tant, un ordre total és també un ordre parcial. L'ordre parcial té una forma més feble de la tercera condició (només requereix reflexivitat, no totalitat). Una extensió d'un ordre parcial donat a un ordre total s'anomena extensió lineal de l'ordre parcial.

Per tot ordre total ≤ existeix una relació asimètrica (per tant, no reflexiva) <, anomenada ordre total estricte, que hom pot definir de dues formes equivalents:

• a < b si i només si a ≤ b i a ≠ b
• a < b si i només si no es compleix b ≤ a (és a dir, < és la inversa del complement de ≤)

Propietats:

• La relació és transitiva: a < b i b < c impliquen a < c.
• La relació compleix la llei de tricotomia: o bé a < b, o bé b < a, o bé a = b, i només una d'aquestes expressions és certa.
• La relació és un preordre total, on l'equivalència associada és la igualtat.

També podem treballar en el sentit invers, i començar per escollir < com una relació binària transitiva que compleix la llei de tricotomia; aleshores podem definir un ordre total ≤ de les següents formes equivalents:

• a ≤ b si i només si a < b o a = b
• a ≤ b si i només si no és complex b < a

Els complements d'aquests ordres, ≥ i >, completen la tupla {<, >, ≤, ≥}.

Podem explicar la forma en la qual està ordenat un conjunt mitjançant qualsevol d'aquestes quatre relacions; la notació ens diu si estem parlant d'ordre estricte o no-estricte.

• Les lletres de l'alfabet ordenades per l'ordre alfabètic habitual, és a dir, A < B < C, etc.

• Qualsevol subconjunt d'un conjunt totalment ordenat, amb la restricció de l'ordre definit conjunt total.

• Qualsevol conjunt de nombres cardinals o nombres ordinals (de fet, són conjunts ben ordenats, propietat més forta que el fet de ser ordenats).

• Si X és un conjunt qualsevol i f una funció injectiva de X a un conjunt totalment ordenat, llavors f indueix un ordre total a X: x₁ < x₂ si i només si f(x₁) < f(x₂).

• També és un ordre total l'ordre lexicogràfic sobre el producte cartesià d'un conjunt de conjunts totalment ordenats indexats per un ordinal. Per exemple, qualsevol conjunt de paraules ordenades alfabèticament és un conjunt totalment ordenat, vist com un subconjunt d'un producte cartesià d'una quantitat numerable de còpies d'un conjunt format per l'addició de l'espai a l'alfabet (i definint l'espai com a més petit que qualsevol lletra).

• El conjunt de nombres reals ordenat amb les relacions habituals més petit (<) i més gran (>) és totalment ordenat; per tant, també ho són els subconjunts de nombres naturals, nombres enters i nombres racionals. Es pot demostrar que cadascun d'aquests conjunts és l'únic (llevat d'isomorfisme) exemple menor de conjunt totalment ordenat amb una certa propietat (un ordre total A és el menor amb una certa propietat si, sempre que B té aquesta propietat, existeix un isomorfisme d'ordres des d'A cap a un subconjunt de B):
  • Els nombres naturals és el conjunt totalment ordenat més petit sense fita superior.
  • Els enters són el conjunt totalment ordenat més petit sense fites superior ni inferior.
  • Els nombres racionals són el conjunt totalment ordenat més petit que és dens en els nombres reals. Aquí, el terme «dens» significa que per a i b reals qualssevol tals que a < b, existeix un q racional tal que a < q < b.
  • Els nombres reals és el conjunt totalment ordenat més petit que és connex en la topologia de l'ordre (vegeu més endavant).

• Els cossos ordenats posseeixen un ordre total per definició. Contenen els nombres racionals i els nombres reals.

Mentre que, de vegades, cadena és només un sinònim per a un conjunt totalment ordenat, també es pot referir a un subconjunt totalment ordenat d'un conjunt parcialment ordenat. Aquesta última definició juga un rol crucial en el lema de Zorn.

Per exemple, considerem el conjunt de tots els subconjunts dels enters parcialment ordenats per la inclusió. Llavors el conjunt {I_n : n és un nombre natural}, on I_n és el conjunt de nombres naturals menors que n, és una cadena d'aquesta ordenació, ja que és totalment ordenada sota la inclusió: si n≤k, llavors I_n és un subconjunt de I_k.

Podem definir un conjunt totalment ordenat com un tipus particular de reticle, per exemple on tinguem:

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$ per a i b qualssevol.

Llavors escrivim a ≤ b si i només si ${\displaystyle a=a\wedge b}$. D'aquí es desprèn que qualsevol conjunt totalment ordenat és un reticle distributiu.

Un senzill argument de comptatge mostra que qualsevol conjunt totalment ordenat finit no buit (i per tant qualsevol subconjunt no buit d'aquest) té un element mínim. Així, qualsevol ordre total finit és, de fet, un bon ordre. Ja sigui per inspecció directa, o bé observant per tot bon ordre és un isomorfisme d'ordre a un ordinal, es pot comprovar que tot ordre total finit té un isomorfisme d'ordre a un segment inicial dels nombres naturals, ordenat per <. En altres paraules, un ordre total sobre un conjunt de k elements indueix una bijecció amb els k primers nombres naturals. Per tant, és usual que s'indexin els ordres totals finits o els bons ordres amb tipus d'ordre ω mitjançant nombres naturals, de manera que es respecti l'ordre (independentment de si es comença a indexar per zero o per u).

Els conjunts totalment ordenats configuren una subcategoria completa de la categoria dels conjunts parcialment ordenats, on els morfismes són les aplicacions amb respecte als ordres, és a dir, aplicacions f tals que si a ≤ b llavors f(a) ≤ f(b).

Una funció bijectiva entre dos conjunts totalment ordenats que respecti els dos ordres és un isomorfisme en aquesta categoria.

Per a qualsevol conjunt totalment ordenat X podem definir els intervals oberts (a, b) = {x : a < x i x < b}, (−∞, b) = {x : x < b}, (a, ∞) = {x : a < x} i (−∞, ∞) = X. Podem usar aquests intervals oberts per definir una topologia en qualsevol conjunt ordenat, la topologia de l'ordre.

Quan s'utilitza més d'un ordre en un conjunt, hom parla de la topologia de l'ordre induïda per un cert ordre. Per exemple, si ℕ és el conjunt de nombres naturals, < és la relació «més petit» i > és la relació «més gran», podem referir-nos a la topologia de l'ordre a ℕ induïda per < i a la topologia de l'ordre a ℕ induïda per > (en aquest cas són idèntiques, però en general no tenen per què ser-ho).

Es pot demostrar que la topologia de l'ordre induïda per un ordre total és normal per herència.

Diem que un conjunt totalment ordenat és complet si tot subconjunt no buit que té una fita superior, té un suprem. Per exemple, el conjunt dels nombres reals ℝ és complet, però el conjunt dels nombres racionals ℚ no ho és.

Existeixen diversos resultats que relacionen les propietats de la topologia de l'ordre amb la completesa de X:

• Si la topologia de l'ordre de X és connexa, llavors X és complet.
• X és connex per la topologia de l'ordre si i només si és completa i no existeix cap forat a X (aquí entenem per «forat» dos punts a i b de X amb a < b tals que no hi ha cap c que compleixi a < c < b).
• X és complet si i només si tot conjunt afitat que sigui tancat per la topologia de l'ordre és compacte.

Un conjunt totalment ordenat (amb la seva topologia d'ordre) que a més sigui un reticle complet és compacte. Alguns exemples són els intervals tancats dels reals, com ara l'interval unitat [0,1], i la recta real estesa. Existeixen homeomorfismes preservadors de l'ordre entre aquests exemples.

Per a dos ordres totals disjunts ${\displaystyle (A_{1},\leq _{1})}$ i ${\displaystyle (A_{2},\leq _{2})}$, existeix un ordre natural ${\displaystyle \leq _{+}}$ en el conjunt ${\displaystyle A_{1}\cup A_{2}}$, que s'anomena suma dels dos ordres, i es denota per ${\displaystyle A_{1}+A_{2}}$:

Per ${\displaystyle x,y\in A_{1}\cup A_{2}}$, es té que ${\displaystyle x\leq _{+}y}$ si i només si es compleix alguna de les següents condicions:

1. ${\displaystyle x,y\in A_{1}}$ i ${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$ i ${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$ i ${\displaystyle y\in A_{2}}$

Intuïtivament, això significa que els elements del segon conjunt s'incorporen per sobre dels elements del primer conjunt.

Més generalment, si ${\displaystyle (I,\leq )}$ és un conjunt d'índexs totalment ordenat, i per cada ${\displaystyle i\in I}$ l'estructura ${\displaystyle (A_{i},\leq _{i})}$ és un ordre lineal, on els conjunts ${\displaystyle A_{i}}$ són disjunts dos a dos, llavors l'ordre total natural a ${\displaystyle \bigcup _{i}A_{i}}$ es defineix com:

Per ${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$, es té que ${\displaystyle x\leq y}$ si:

1. O bé existeix algun ${\displaystyle i\in I}$ amb ${\displaystyle x\leq _{i}y}$
2. o bé existeixen ${\displaystyle i<j}$ a ${\displaystyle I}$ amb ${\displaystyle x\in A_{i}}$ i ${\displaystyle y\in A_{j}}$.

Tres possibles ordenacions sobre el producte cartesià de dos conjunts totalment ordenats són (en ordre creixent de precedència, és a dir, conjunts decreixents de parells):

• Ordre lexicogràfic: (a,b) ≤ (c,d) si i només si a < c o bé (a = c i b ≤ d). Aquest és un ordre total.
• (a,b) ≤ (c,d) si i només si a ≤ c i b ≤ d (l'ordre producte). Aquest és un ordre parcial.
• (a,b) ≤ (c,d) si i només si (a < c i b < d) o bé (a = c i b = d) (la clausura reflexiva del producte directe dels corresponents ordres totals estrictes). Aquest també és un ordre parcial.

Tots tres es poden definir de forma similar pel producte cartesià de més de dos conjunts.

Quan s'apliquen a l'espai vectorial ℝⁿ, cadascun d'aquests el transforma en un espai vectorial ordenat.

Vegeu també exemples de conjunts parcialment ordenats.

Una funció real de n variables reals definida en un subconjunt de ℝⁿ defineix un preordre total sobre aquest subconjunt.

Una relació binària que sigui antisimètrica, transitiva i reflexiva (però no necessàriament total) és un ordre parcial.

Un grup amb un ordre total compatible és un grup totalment ordenat.

• Grätzer, George. Lattice theory : first concepts and distributive lattices. San Francisco: W.H. Freeman, 1971. ISBN 0-7167-0442-0. 
• Young, John G. Hocking, Gail S.. Topology. Facsim. ed.. Nova York: Dover Publications, 1988. ISBN 0-486-65676-4.