Orden total


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 antisimétrica, transitiva, y total; esto es, si se denota una tal relación por ≤, lo siguiente vale para cualesquiera a, b, y c en X:

  • Si ab y ba, entonces a = b (antisimetría).
  • Si ab y bc, entonces ac (transitividad).
  • 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.

Contenido

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.

Ejemplos

  • 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, ab o ba).
  • Todo conjunto de números cardinales o números ordinales (más aún, éstos 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 bien 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).

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

Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Orden total — En matemáticas, un orden total u orden lineal en un conjunto X es una relación binaria que es reflexiva, antisimétrica, transitiva, y total. Esto significa que, si denotamos la relación por =, vale para todo a …   Enciclopedia Universal

  • Orden (desambiguación) — Orden puede adqurir varios significados en diferentes disciplinas. Puede referirse a: Contenido 1 Teoría de sistemas 2 Criterios de ordenación 3 Significados en diferentes ciencias 3.1 …   Wikipedia Español

  • Orden bien fundamentado — Saltar a navegación, búsqueda En matemáticas, una relación binaria, R, es bien fundamentada (o bienfundamentada) en una clase X si y sólo si todo subconjunto no vacío de X tiene un elemento R mínimo; esto es, para todo subconjunto no vacío S de X …   Wikipedia Español

  • Orden (filosofía) — El orden primigenio es lo que se opone al caos. Es importante no confundir orden caos con orden desorden. El desorden encuentra su sentido frente a un orden previo establecido en el que tiene su punto de referencia. El concepto de orden caos es… …   Wikipedia Español

  • Orden jónico — El orden jónico es el segundo, en sentido cronológico, de los órdenes arquitectónicos clásicos que tuvo su origen hacia el siglo VI a. C. en la costa oeste de Asia Menor y en las islas Cícladas, archipiélago situado al sureste de Grecia …   Wikipedia Español

  • Orden corintio — Esquema del orden corintio de las columnas del Panteón de Roma. El orden corintio es el más elegante y ornamentado de los órdenes arquitectónicos clásicos. Se atribuye su creación al escultor griego Calímaco en el siglo IV a. C. En lo… …   Wikipedia Español

  • Orden — (Del lat. ordo, inis.) ► sustantivo masculino 1 Colocación cuidadosa de un conjunto de cosas, asignando a cada una un lugar o posición determinada: ■ quiero que todo esté en orden. ANTÓNIMO desorden 2 Disposición regular de un conjunto de cosas o …   Enciclopedia Universal

  • Orden monomial — En Álgebra, un orden monomial es una ordenación del conjunto de monomios de un anillo, que se utiliza para poder establecer un algoritmo de división en polinomios de varias variables. Contenido 1 Definición 1.1 Orden monomial global 1.2 Orden… …   Wikipedia Español

  • Orden lexicográfico — El orden lexicográfico es una relación de orden que se utiliza para ordenar producto cartesiano de conjuntos ordenados. Es conocido principalmente por su aplicación a cadenas de caracteres, por ejemplo en diccionarios o en la guía telefónica.… …   Wikipedia Español

  • Orden de la Amistad de los Pueblos — Otorgada por …   Wikipedia Español