Relación de orden

Una relación de orden es una relación binaria en un conjunto que es reflexiva, antisimétrica y transitiva.

Motivación

El orden es un concepto habitual con el que trabajamos también en la vida cotidiana. Muchas cosas podemos ordenarlas de algún modo: las palabras por orden alfabético, los alumnos del colegio por estatura, los productos por precio. Todo esto lo describe la relación de orden, que solemos designar con el símbolo ≤. Los símbolos relacionados son: <, >, ≥. Su significado es evidente.

¿Qué esperaríamos de una relación así? Ya por el símbolo está claro que en la relación de orden habrá elementos que son iguales; nos interesa, pues, definir las propiedades de la relación «menor o igual». Una relación así debería ser reflexiva. Debe cumplirse que a ≤ a.

¿Qué más? Desde luego no se cumplirá la simetría: si tenemos un orden por precio y el coche es más barato que el pan, seguro que el pan no será al mismo tiempo más barato que el coche. ¿Qué esperaríamos en general si ocurriera que a ≤ b y, al mismo tiempo, b ≤ a? ¿Tendría sentido alguna vez? Sí, si se cumpliera a = b. El único caso en que no importa el orden de los elementos puestos en la relación es cuando esos elementos son iguales; el orden es, por tanto, antisimétrico.

Por último, si sabemos que el coche es más caro que el pan y que el avión es todavía más caro que el coche, esperamos que el avión sea, sin duda, más caro que el pan. Eso lo describe la transitividad.

Orden parcial

Lo que acabamos de definir es en realidad solo un orden parcial, no es total. ¿Por qué no es total? Intentemos definir un orden entre conjuntos. ¿De qué manera podríamos comparar dos conjuntos?

Diremos que el conjunto A es menor o igual que el conjunto B si A ⊆ B, es decir, si A es un subconjunto de B. Tiene sentido, porque si tenemos A = {1, 2} y B = {1, 2, 3}, de A podríamos decir que es menor: B contiene los mismos elementos que A y además contiene el número tres. Así, por ejemplo, se cumplirá:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

El problema surge cuando queremos comparar estos conjuntos: A = {a, b} y B = {a, c}. ¿Cuál de ellos es menor o mayor? El problema es que, aunque ambos conjuntos contienen el elemento a, el segundo elemento es siempre distinto. Ninguno de los conjuntos es subconjunto del otro, así que no se cumple ni A ≤ B ni B ≤ A. Estos conjuntos son, con nuestro orden, no comparables.

Por eso llamamos conjunto totalmente ordenado o también cadena a un conjunto en el que dos elementos cualesquiera son comparables. Conjuntos así son, por ejemplo, los conjuntos numéricos con el orden clásico. Para dos números reales cualesquiera a, b eres capaz de decidir si a ≤ b o b ≤ a.

Ejemplos de la vida cotidiana

Un ejemplo en el que conviene no comparar podría ser el orden según lo bien que se juega: la relación < significaría «jugar peor». Quizá deberíamos definirlo más bien al revés, > como «jugar mejor», para ser más amables :-). Tiene sentido comparar entre sí a dos tenistas, por ejemplo, «Lucía» < «Sofía» en el sentido de que Sofía juega mejor que Lucía. O a dos ajedrecistas: «Hugo» < «Pablo» en el sentido de que Pablo juega mejor que Hugo.

El problema es que difícilmente podemos comparar a una tenista con un ajedrecista. ¿Juega mejor Sofía o Pablo? ¿Juega peor nuestra querida Lucía o Hugo? Mejor no investigarlo…

Si en el último ejemplo nos limitamos, por ejemplo, solo a las tenistas, podemos decir que tenemos un conjunto totalmente ordenado, porque somos capaces de comparar el juego de todas las tenistas.

Elemento minimal y maximal, elemento mínimo y máximo

Si tenemos un conjunto ordenado M, llamamos minimal al elemento min ∈ M si no existe ningún x ∈ M tal que x < min. Es decir, no somos capaces de encontrar un elemento que sea menor que el elemento min.

Llamamos maximal al elemento max ∈ M si no existe ningún x ∈ M tal que x > max. Es decir, no somos capaces de encontrar un elemento que sea mayor.

Los dos conceptos anteriores se diferencian de los conceptos de mínimo y máximo.

Llamamos mínimo al elemento a ∈ M si para todos los x ∈ M se cumple que a ≤ x. Es decir, el elemento mínimo a es menor o igual que todos los demás elementos del conjunto M.

Llamamos máximo al elemento b ∈ M si para todos los x ∈ M se cumple que b ≥ x. El elemento máximo b es mayor o igual que todos los demás elementos del conjunto M.

¿Cuál es la diferencia entre el elemento máximo y el elemento maximal? Puede haber varios elementos maximales, porque el conjunto no tiene por qué estar totalmente ordenado. Si volvemos al ejemplo de comparar personas según cómo juegan, podemos decir que Sofía es la mejor tenista y Pablo es el mejor ajedrecista. Pero a estas dos personas ya no somos capaces de compararlas entre sí: no sabemos si juega mejor Sofía o Pablo.

Ambos elementos son, pues, maximales. No somos capaces de encontrar una persona que juegue mejor que Pablo: Pablo juega mejor que todos los demás ajedrecistas y con las tenistas no podemos compararlo. De manera similar para Sofía: ella juega mejor que todas las tenistas y con los ajedrecistas no podemos compararla.

Pero ninguno de ellos es el máximo, en este sentido, el que mejor juega. Porque, para que Pablo fuera el que mejor juega o el máximo, tendría que jugar mejor que todas las personas, incluidas todas las tenistas. Pero ya hemos dicho que con las tenistas no podemos compararlo, por lo que no puede ser la persona que mejor juega; es solo, en la terminología de la teoría del orden, maximal.

Es fácil ver que, si un conjunto tiene elemento máximo, ese elemento es también maximal. Si el elemento a es mayor que todos los demás elementos del conjunto (definición de elemento máximo), seguro que no encontraremos un elemento que sea aún mayor (definición de elemento maximal).

Un ejemplo de conjunto que tiene elemento máximo y mínimo es el intervalo cerrado [0, 1]. Si elegimos el mismo intervalo, pero abierto, no tendría ni máximo ni mínimo: (0, 1).

Si quisiéramos infinitos elementos minimales, podríamos definir el orden R así. Primero definimos unos conjuntos auxiliares M_x. Los conjuntos tendrán esta forma: para todo x del intervalo (0, 1) definimos el conjunto M_x = {y ∣ y = x + n}, donde n es un número entero no negativo. Así obtenemos, por ejemplo, estos conjuntos:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

En cada conjunto M_x definimos el orden clásico, que designamos R_x. Al final basta con unir estos órdenes: R = ∪ R_x. En este orden podemos comparar siempre solo dentro de las cadenas originales. Así podemos averiguar si 0,5 ≤ 2,5, pero ya no podemos averiguar si 0,5 ≤ 2,7, porque estos números no estaban en el mismo conjunto M_x y su relación no está definida.

En esta relación de orden se cumple entonces que cada elemento del intervalo (0, 1) es un elemento minimal.

Diagramas de Hasse

Los conjuntos ordenados podemos representarlos mediante un diagrama de Hasse. Se trata de un grafo en el que los vértices representan los elementos del conjunto y una arista entre los vértices (a, b) nos dice que a < b y que, al mismo tiempo, no existe ningún c tal que a < c < b. Es decir, entre los elementos a y b ya no hay ningún otro elemento. Además, debe cumplirse que en el grafo el vértice a esté más abajo que el vértice b. Ejemplo de diagrama de Hasse:

Este diagrama de Hasse representa el conjunto ordenado {A, B, C, D, E, F}. Se cumple: A < B, B < E, y por supuesto se cumple también A < E, pero entre estos vértices no hay arista, porque existe el vértice B, para el que se cumple A < B < E. Los elementos E y D no son comparables, porque ninguno está por encima o por debajo del otro.

Aunque los diagramas de Hasse suelen dibujarse así, bien alineados, no es estrictamente necesario. El diagrama de Hasse anterior puede tener también este aspecto:

Otro ejemplo puede ser el conjunto: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Son los divisores naturales del número 60. El orden por divisibilidad puede representarse así:

El orden por divisibilidad significa que (a, b) ∈ R si y solo si a divide a b. En el diagrama podemos observar que cada número tiene por encima los números a los que divide. Por ejemplo, por encima del número 6 están los números 12, 30 y 60. Por encima del número 4 están los números 12, 20 y 60. Etcétera. En cambio, el número 3 no tiene por encima el número 10, porque no lo divide; ojo, el número 10 está visualmente por encima del número 3, pero hasta él no llega «de abajo arriba» ninguna línea. Si desde el número 3 nos movemos solo hacia arriba, podemos ir a los números 15 y 6 y desde ellos al número 30. Al número 10 solo podríamos llegar bajando, lo cual no está permitido.