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:

Relación homogénea Relación reflexiva Conjunto preordenado Relación de dependencia Conjunto parcialmente ordenado Relación de equivalencia Orden total Acotado ClasiBinaEs 004.svg
Acerca de esta imagen

La propiedad de totalidad de esta relación se puede también describir como que todo par de elementos son comparables bajo la relación.

Por tanto, un orden total es un orden parcial que cumple la comparabilidad.

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, aa para todo aX; 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 ab si y solo si a = ab. 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 ab 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.

Orden total estricto

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.

Ejemplos

Topología del orden

Para todo conjunto totalmente ordenado X, se pueden definir los intervalos abiertos (a, b) := {xX | a < x y x < b}, (−∞, b) = {xX | x < b}, (a, ∞) = {xX | a < x} y (−∞, ∞) = X. Con éstos 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.

Completitud

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.

Cadenas

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 éste sería llamado cadena.

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

Órdenes totales finitos

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.

Esquema de temas relacionados

Teoría del orden
Bien ordenado
Orden total
Parcialmente ordenado
Preordenado
Relación reflexiva
Relación transitiva
Relación antisimétrica
Relación total
Relación bien fundada
This article is issued from Wikipedia - version of the Tuesday, February 24, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.