La teoría del orden es una rama de la matemática que estudia varias clases de relaciones binarias que capturan la noción intuitiva del orden matemático. Este artículo provee una introducción detallada a este campo e incluye algunas de las definiciones básicas. Para una rápida búsqueda de un término orden teórico, hay también un glosario de teoría del orden. Una lista de asuntos sobre orden recoge los artículos que existen en relación con esta teoría

Trasfondo y motivación

El orden aparece por todas partes, por lo menos si se trata de matemáticas y áreas relacionadas, tales como la informática. El primer orden que uno típicamente encuentra en la educación matemática de la escuela primaria es el orden ≤ de los números naturales. Este concepto intuitivo es fácilmente extendido a otros conjuntos de números, tal como los enteros y reales. De hecho la idea de ser mayor o menor que otro número es una de las intuiciones básicas de los sistemas de numeración en general (que uno generalmente se interesa también en la diferencia real de dos números, que no viene dada por el orden). Otro ejemplo popular de un orden es el orden lexicográfico de las palabras en un diccionario.

Los tipos antedichos de orden tienen una propiedad especial: cada elemento se puede comparar con cualquier otro elemento, es decir es o mayor, o menor, o igual. Sin embargo, esto no siempre es un requisito deseable. Un ejemplo bien conocido es el orden de los subconjuntos de un conjunto. Si un conjunto contiene los elementos de cierto otro conjunto, entonces se puede decir que es mayor o igual. Con todo, hay conjuntos que pueden no ser comparables de este modo, puesto que cada uno puede contener algún elemento que no esté presente en el otro. Por lo tanto, inclusión de subconjuntos es un orden parcial, en comparación con los órdenes totales dados antes.

Alentadas por los amplios usos prácticos de los órdenes, se pueden definir numerosas clases especiales de conjuntos ordenados, algunas de las cuales han llegado a ser campos matemáticos por sí mismos. Además, la teoría del orden no se restringe a las varias clases de relaciones de orden, sino que también considera funciones apropiadas entre ellas. Un ejemplo simple de una propiedad orden teórica viene del análisis donde encontramos con frecuencia a las funciones monótonas.

Introducción a las definiciones básicas

Esta sección tiene como objetivo dar una primera guía al reino de los conjuntos ordenados. Está dirigida al lector que tiene un conocimiento básico teoría de conjuntos y aritmética y que sabe qué es una relación binaria, pero que no está familiarizado, hasta ahora, con consideraciones teóricas sobre orden.

Conjuntos parcialmente ordenados

Como ya se hizo alusión arriba, un orden es una relación binaria especial. Por lo tanto consideremos algún conjunto P y una relación binaria ≤ en P. Entonces ≤ es un orden parcial si es reflexiva, antisimétrica, y transitiva, es decir, para todo a, b y c en P, tenemos que:

a ≤ a (reflexividad) si a ≤ b y b ≤ c entonces a ≤ c (transitividad) si a ≤ b y b ≤ a entonces a = b, (antisimetría).

Un conjunto con un orden parcial se llama conjunto parcialmente ordenado, o, en breve, poset (del inglés partially ordered set). El término conjunto ordenado a veces también se utiliza para los posets, mientras esté claro del contexto que no se quiere significar ninguna otra clase de órdenes. Comprobando esta propiedad, se ve inmediatamente que los bien conocidos órdenes de los naturales, enteros, racionales y reales son todos órdenes en el antedicho sentido. Sin embargo, tienen la propiedad adicional de ser total, es decir, para todo a, b en X a ≤ b o b ≤ a (totalidad) este orden se puede también llamar orden lineal o cadena. mientras que muchos órdenes clásicos son lineales, el orden entre subconjuntos de un conjunto proporciona un ejemplo donde este no es el caso. De hecho, muchas propiedades avanzadas de los posets son interesantes principalmente para un orden no lineal.

Visualizando órdenes

Antes de proceder con más ejemplos y definiciones, será provechoso poder exhibir un orden de una manera gráfica conveniente, para proporcionar un "cuadro" que uno pueda tener en mente (o en papel) cuando se intente acceder a conceptos más abstractos. Para este propósito se han introducidos los, así llamados, diagramas de Hasse. Estos son grafos donde los vértices son los elementos del poset y la relación de orden está indicada por las aristas y la posición relativa de los vértices. Los órdenes se dibujan de abajo hacia arriba: si un elemento x es menor que y entonces existe una trayectoria de x hasta y que se dirige hacia arriba. A menudo es necesario que la conexión entre puntos se intersequen, pero los puntos nunca deben ser situados en conexión directa entre otros dos puntos.

Aún los conjuntos infinitos pueden a veces ser ilustrados por diagramas similares, usando puntos suspensivos (...) después de dibujar un suborden finito que sea lo suficientemente instructivo. Esto funciona bien para los números naturales, pero falla para los reales, donde no existe el inmediato sucesor. Sin embargo, frecuentemente se obtiene una intuición relacionada con diagramas de este tipo.

Todos los órdenes antedichos son muy comunes en matemática, sin embargo hay también ejemplos que uno no considera a menudo como órdenes. Por ejemplo, la relación de identidad "=" en un conjunto es un orden parcial. Dentro de este orden, cualesquiera dos (i.e. distintos) elementos son incomparables. Es también la única relación que es un orden parcial y una relación de equivalencia. El diagrama de Hasse de tal orden discreto es solamente una colección de puntos etiquetados, sin ninguna arista entre ellos.

Otro ejemplo viene dado por la relación de divisibilidad "|". Para dos números naturales n y m, escribimos n|m si n divide a m sin resto. Uno ve fácilmente que esto da realmente un orden parcial. Un ejercicio instructivo es dibujar el diagrama de Hasse para el conjunto de los números naturales que son menores o iguales que, digamos, 13, ordenados por |.

Elementos especiales dentro de un orden

En un conjunto parcialmente ordenado hay algunos elementos que desempeñan un papel especial. El ejemplo más básico está dado por el mínimo de un poset. Por ejemplo, 1 es el mínimo de los números naturales y el conjunto vacío es el mínimo bajo el orden de subconjuntos. Formalmente, esto se puede describir por la propiedad:

0 ≤ a, para todo elemento a del conjunto ordenado.

Es frecuente encontrar la notación 0 para el mínimo, incluso cuando no se refiera a números. Sin embargo, en un orden de un conjunto numérico, esta notación puede ser inadecuada o ambigua, puesto que el número 0 no siempre es el mínimo. Un ejemplo es el antedicho orden de divisibilidad |, donde 1 es el mínimo puesto que divide a todo el resto de números. Por otra parte, 0 es un número que se divide por todo el resto de números. ¡Por lo tanto es el máximo del orden! Otros términos frecuentes para estos elementos son fondo y tapa o cero y uno. Pueden no existir los elementos "mínimo" o "máximo", como demuestra el ejemplo de los números reales. Por otra parte, si existen son siempre únicos. En contraste, consideremos la relación de divisibilidad | en el conjunto {2, 3, 4, 5, 6}. Aunque este conjunto no tiene ni tapa ni fondo, los elementos 2, 3, y 5 no tienen ningún elemento debajo, mientras que 4, 5, y 6 no tienen ninguno otro número arriba. Tales elementos se llaman minimales y maximales, respectivamente. Formalmente, un elemento m es minimal si:

a ≤ m implica a = m, para todo elemento a.

Intercambiando ≤ con ≥ obtenemos la definición de maximal. Como el ejemplo demuestra, puede haber muchos elementos minimales o maximales y algún elemento puede ser maximal y minimal (e.g. 5 arriba). Sin embargo, si hay un elemento mínimo, entonces es el único elemento minimal del orden. (Si se sigue estrictamente la definición dada. Lamentablemente hay una tradición matemática "a contrario": considerar los minimales y maximales en el conjunto despojado de su máximo y su mínimo, si los hubiere. Esto debe recordarse. N.T.). Una vez más, en los posets no siempre hay infinitos elementos maximales - el conjunto de todos los subconjuntos finitos en un conjunto infinito dado, ordenado por inclusión de subconjuntos, proporciona uno, entre muchos, contraejemplo. Una herramienta importante para asegurar la existencia de elementos maximales bajo ciertas condiciones es el Lema de Zorn.

Los subconjuntos de un conjunto parcialmente ordenado heredan el orden. Ya aplicamos esto al considerar el subconjunto {2, 3, 4, 5, 6} de los números naturales con el orden de divisibilidad inducido. Hay también elementos de un poset que son especiales con respecto a cierto subconjunto del orden. Esto conduce a la definición de cota superior. Dado un subconjunto S de cierto poset P, una cota superior de S es un elemento b de P que está sobre todo elemento de S. Formalmente, esto significa que s ≤ b, para todo s en S.

Cota inferior se define invirtiendo el orden. Por ejemplo, -5 es una cota inferior de los números naturales como subconjunto de los enteros. Dado un conjunto de conjuntos , una cota superior para éstos conjuntos viene dado por su unión. De hecho, esta cota superior es muy especial: es el más pequeño conjunto que contiene todos los conjuntos dados. Por lo tanto, encontramos la menor cota superior de un conjunto de conjuntos. Este concepto se llama también supremo y para un conjunto S se escribe sup S o VS para su menor cota superior. Inversamente, la mayor cota inferior se la conoce como ínfimo y se denota inf S o ^S. Este concepto desempeña un papel importante en muchos usos de la teoría del orden. Para dos elementos x y y, uno también escribe x v y y x ^ y para sup{x, y} e inf{x, y}, respectivamente.

Usando Wikipedia TeX markup, uno puede también escribir y , así como símbolos grandes y . Observe, sin embargo, que todos esos símbolos pueden no tener símbolo de tamaño correspondiente al de la fuente del texto estándar y, por tanto, se prefiere utilizarlos en líneas adicionales. Muchos de los navegadores de hoy son incapaces de representar ∨ para v y ∧ para ^ en algunas plataformas, y por lo tanto se evita aquí.

Considere otro ejemplo en la relación | para los números naturales. La menor cota superior de dos números es el menor número que es múltiplo de ambos, es decir el mínimo común múltiplo. Mayor cota inferior es, alternativamente, el máximo común divisor.

Dualidad

En las anteriores definiciones, a menudo, observamos que un concepto puede ser definido por invertir simplemente el orden en una definición anterior. Este es el caso para "menor" y "mayor", para "mínimo" y "máximo", para "cota superior " y "cota inferior", etcétera. Esto es una situación general en teoría de orden: Un orden dado se puede invertir con solamente intercambiar su dirección, pictóricamente dar vuelta el diagrama de Hasse de arriba para abajo. Esto da el, así llamado, orden dual, inverso u opuesto.

Cada definición orden teórica tiene su dual: es la noción que se obtiene al aplicar la definición al orden inverso. Dada la simetría de todos los conceptos, esta operación preserva los teoremas del orden parcial. Para un resultado matemático dado, se puede, simplemente, invertir el orden y substituir todo definición por su dual y obtener otro teorema válido. Esto es importante y útil, puesto que uno obtiene dos teoremas al precio de uno. Más detalle y ejemplos se pueden encontrar en el artículo sobre dualidad en teoría de orden.

Construcción nuevos órdenes