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 Relación no reflexiva Conjunto preordenado Relación de dependencia Conjunto parcialmente ordenado Relación de equivalencia Orden total Acotado Orden total acotadoClasiBinaEs 004.svg
Acerca de esta imagen
  • si a pertenece a X, entonces aa (reflexiva).
  • Si ab y bc, entonces ac (transitividad).
  • Si ab y ba, entonces a = b (antisimetría).
  • ab o ba (totalidad o completitud).

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:

  • a < b ssi ab y ab.
  • a < b ssi no ba ( 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:

  • ab ssi a < b o a = b.
  • ab ssi 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.

Other Languages