Orden total

En matemáticas, un orden total, orden lineal, orden simple, o simplemente orden en un conjunto X es una relación binaria sobre X que es: reflexiva, transitiva, antisimétrica, y total; esto es, si se denota una tal relación por ≤, lo siguiente vale para cualesquiera a, b, y c en X:

• Si a pertenece a X, entonces a ≤ a (reflexiva).
• Si a ≤ b y b ≤ c, entonces a ≤ c (transitividad).
• Si a ≤ b y b ≤ a, entonces a = b (antisimetría).
• a ≤ b o b ≤ a (totalidad o completitud).

La propiedad de totalidad de esta relación es equivalente a decir que todo par de elementos es comparable bajo la relación.

Un conjunto dotado de un orden total se denomina conjunto totalmente ordenado, linealmente ordenado, simplemente ordenado, o cadena.

Nótese que la condición de totalidad implica reflexividad, esto es, a ≤ a para todo a ∈ X; por lo tanto, un orden total es también un orden parcial, esto es, una relación binaria reflexiva, antisimétrica, y transitiva. Un orden total, entonces, puede también definirse como un orden parcial que sea "total", i.e. que cumpla con la condición de totalidad.

Como alternativa, se puede definir un conjunto totalmente ordenado como un tipo particular de retículo, en el que se tiene {a ∨ b, a ∧ b} = {a, b} para cualesquiera a, b. Se escribe entonces a ≤ b si y solo si a = a ∧ b. Se deduce que un conjunto totalmente ordenado es un retículo distributivo.

Los conjuntos totalmente ordenados forman una subcategoría completa de la categoría de conjuntos parcialmente ordenados, siendo los morfismos funciones que respetan el orden, es decir, funciones f tales que si a ≤ b entonces f(a) ≤ f(b). Una función biyectiva entre dos conjuntos totalmente ordenados que respete los dos órdenes es un isomorfismo en esta categoría.

Para cada orden total (no estricto) ≤ hay asociada una relación asimétrica (y por tanto irreflexiva) <, llamada orden total estricto, que puede definirse de dos maneras equivalentes:

• a < b sii a ≤ b y a ≠ b.
• a < b sii no b ≤ a (i.e., < es la inversa del complemento de ≤).

El orden total estricto tiene las siguientes propiedades, para cualesquiera a, b, y c en X:

• Es transitivo: a < b y b < c implica a < c.
• Es tricotómico: exactamente una de a < b, b < a, y a = b es válida.
• Es un preorden total.

Se puede trabajar a la inversa tomando < como una relación binaria transitiva y tricotómica; en ese caso, un orden total no estricto ≤ se puede definir de dos maneras equivalentes:

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

Otros dos órdenes asociados son los complementos ≥ y >, completando así el conjunto {<, >, ≤, ≥}. Se puede definir o explicar el orden total de un conjunto usando cualquiera de las cuatro relaciones; la notación dejará en claro si se habla de un orden estricto o no.

• Las letras del alfabeto con el orden alfabético usual: A < B < C < X.
• Cualquier subconjunto de un conjunto totalmente ordenado, restringiendo a él, el orden del conjunto completo.
• Todo conjunto parcialmente ordenado X donde cualesquiera dos elementos se pueden comparar (i.e. para todo par de elementos a y b en X, a ≤ b o b ≤ a).
• Todo conjunto de números cardinales o números ordinales (más aún, estos son bien ordenados).
• Si X es un conjunto y f una función inyectiva de X a un conjunto totalmente ordenado, f induce un orden total en X tomando x < y si y solo si f(x) < f(y).
• El orden lexicográfico en el producto cartesiano de cualquier colección de conjuntos totalmente ordenados es en sí mismo un orden total. Por ejemplo, cualquier conjunto de palabras con el orden alfabético usual está totalmente ordenado, visto como un subconjunto del producto cartesiano de un conjunto finito de símbolos, el alfabeto con un espacio vacío (que se define menor que cualquier letra), un número contable de veces.
• Los naturales, enteros, racionales y los reales, con el orden usual de las relaciones < o >, son conjuntos totalmente ordenados. Cada uno de ellos es un caso único (módulo isomorfismo) y mínimo de conjunto totalmente ordenado con alguna propiedad (un conjunto totalmente ordenado A es el mínimo con cierta propiedad si, para todo conjunto B con la propiedad, hay un isomorfismo de orden entre A y un subconjunto de B):
  • Los naturales forman el mínimo conjunto totalmente ordenado sin cota superior.
  • Los enteros forman el mínimo conjunto totalmente ordenado sin cota superior ni inferior.
  • Los racionales forman el mínimo conjunto totalmente ordenado sin cota superior ni inferior que además es denso, es decir, que para cualesquiera a y b con a < b, existe un c tal que a < c < b.
  • Los reales son el mínimo conjunto totalmente ordenado no acotado y conexo (véase más adelante la definición de la topología).

Para todo conjunto totalmente ordenado X, se pueden definir los intervalos abiertos (a, b) := {x ∈ X | a < x y x < b}, (−∞, b) = {x ∈ X | x < b}, (a, ∞) = {x ∈ X | a < x} y (−∞, ∞) = X. Con estos se puede definir una topología en cualquier conjunto ordenado, la topología del orden.

Nótese que la definición formal de un conjunto ordenado como una pareja formada por un conjunto y un orden garantiza que la topología del orden sea única en cada conjunto ordenado. Sin embargo, en la práctica la distinción entre un conjunto con un orden definido en él y la pareja de conjunto y orden se obvia casi siempre. Para evitar entonces confusión cuando se usa más de un orden sobre un conjunto se habla de la topología del orden inducida por un orden particular. Por ejemplo, si N es el conjunto de los naturales, y < y > son las relaciones usuales de menor y mayor, se puede hablar de la topología del orden en N inducida por < y aquella inducida por > (en este caso resultan ser la misma, pero en general no será así).

La topología del orden sobre un orden total es completamente normal.

Un conjunto X totalmente ordenado se dice completo si todo subconjunto no vacío con cota superior tiene supremo en el conjunto X. Por ejemplo, el conjunto de los reales es completo, pero el de los racionales no.

Un conjunto X es conexo bajo la topología del orden si y solo si es completo y no tiene saltos (un salto es un par de puntos a y b en X con a < b, tales que no hay un c en X que satisfaga a < c < b).

X es completo si y solo si todo subconjunto acotado que sea cerrado en la topología del orden es compacto.

Aunque, según la definición, una cadena es exactamente lo mismo que un conjunto totalmente ordenado, el término se usa en general para referirse a subconjuntos totalmente ordenados de un conjunto parcialmente ordenado; los reales, por ejemplo, seguirían siendo un conjunto totalmente ordenado. Sin embargo, si se considera el conjunto de partes de los naturales parcialmente ordenado por inclusión, un subconjunto totalmente ordenado de este sería llamado cadena.

La preferencia por el uso de "cadena" para referirse a los subconjuntos mencionados probablemente viene de la importancia que estos tienen en el lema de Zorn.

Un simple argumento de conteo basta para demostrar que todo conjunto finito totalmente ordenado (así como cualquier subconjunto) tiene un elemento mínimo, y por lo tanto está bien ordenado. Sea por prueba directa, o porque todo buen orden es isomorfo a un ordinal, se puede demostrar que todo orden total finito es isomorfo a un segmento inicial de los naturales con el orden usual. En otras palabras, un orden total en un conjunto con k elementos induce una biyección con los primeros k naturales; por esto es común listar los órdenes totales finitos con números naturales y ordenarlos según el orden de los naturales.

• Teoría del orden