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:

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:

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

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:

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.

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.