27. Relaciones de orden

27.1 Introducción

Muchas estructuras necesitan comparar elementos: números, permisos, tareas, versiones, prioridades o subconjuntos. Las relaciones de orden permiten formalizar esas comparaciones.

No todos los órdenes se comportan igual. Algunos permiten comparar cualquier par de elementos; otros solo permiten comparar ciertos pares. Por eso distinguimos entre orden parcial y orden total.

27.2 Qué es una relación de orden

Una relación de orden sobre un conjunto A es una relación que permite comparar elementos de A respetando ciertas propiedades.

La forma más común que estudiaremos es el orden parcial, definido por tres propiedades: reflexividad, antisimetría y transitividad.

27.3 Reflexividad en un orden

La reflexividad indica que todo elemento está relacionado consigo mismo.

Por ejemplo, todo número es menor o igual que sí mismo: a ≤ a.

27.4 Antisimetría en un orden

La antisimetría evita ciclos de comparación entre elementos distintos.

Por ejemplo, si a ≤ b y b ≤ a, entonces necesariamente a = b.

27.5 Transitividad en un orden

La transitividad permite encadenar comparaciones.

Si una tarea A debe ejecutarse antes que B, y B antes que C, entonces A debe ejecutarse antes que C.

27.6 Ejemplo: menor o igual

La relación ≤ sobre los números es una relación de orden.

27.7 Ejemplo: inclusión de conjuntos

La relación ⊆ entre subconjuntos también es una relación de orden.

Todo conjunto está contenido en sí mismo, la inclusión mutua implica igualdad y la inclusión puede encadenarse.

27.8 Orden parcial

Un orden parcial permite comparar algunos pares de elementos, pero no necesariamente todos.

Con la relación de inclusión, {1} y {2} no son comparables: ninguno está contenido en el otro.

27.9 Orden total

Un orden total es un orden donde cualquier par de elementos puede compararse.

La relación ≤ sobre números es un orden total porque dados dos números siempre podemos compararlos.

27.10 Comparación entre orden parcial y total

27.11 Relación estricta y no estricta

Algunas relaciones de orden se escriben en forma no estricta, como ≤, y otras en forma estricta, como <.

En este tema usamos principalmente órdenes no estrictos.

27.12 Órdenes en programación

En programación, las relaciones de orden aparecen al comparar prioridades, versiones, fechas, dependencias y niveles de acceso.

Este tipo de orden permite ordenar tareas, resolver colas de prioridad o validar jerarquías.

27.13 Verificar un orden parcial en JavaScript

Podemos representar una relación con pares y verificar sus propiedades.

function clave(a, b) {
  return `${a}:${b}`;
}

function crearRelacion(pares) {
  return new Set(pares.map(([a, b]) => clave(a, b)));
}

function esReflexiva(elementos, relacion) {
  return elementos.every(a => relacion.has(clave(a, a)));
}

function esAntisimetrica(pares, relacion) {
  return pares.every(([a, b]) =>
    a === b || !relacion.has(clave(b, a))
  );
}

function esTransitiva(pares, relacion) {
  return pares.every(([a, b]) =>
    pares.every(([c, d]) => {
      if (b !== c) return true;
      return relacion.has(clave(a, d));
    })
  );
}

Estas funciones reutilizan las propiedades estudiadas en el tema anterior.

27.14 Comprobar la relación ≤ en un conjunto finito

function clave(a, b) {
  return `${a}:${b}`;
}

function crearRelacion(pares) {
  return new Set(pares.map(([a, b]) => clave(a, b)));
}

function esReflexiva(elementos, relacion) {
  return elementos.every(a => relacion.has(clave(a, a)));
}

function esAntisimetrica(pares, relacion) {
  return pares.every(([a, b]) =>
    a === b || !relacion.has(clave(b, a))
  );
}

function esTransitiva(pares, relacion) {
  return pares.every(([a, b]) =>
    pares.every(([c, d]) => {
      if (b !== c) return true;
      return relacion.has(clave(a, d));
    })
  );
}

const elementos = [1, 2, 3];
const paresMenorIgual = [];

for (const a of elementos) {
  for (const b of elementos) {
    if (a <= b) {
      paresMenorIgual.push([a, b]);
    }
  }
}

const relacion = crearRelacion(paresMenorIgual);

console.log(esReflexiva(elementos, relacion));
console.log(esAntisimetrica(paresMenorIgual, relacion));
console.log(esTransitiva(paresMenorIgual, relacion));

Las tres salidas son verdaderas, por lo tanto la relación es un orden parcial. Además, en este caso es total.

27.15 Aplicaciones prácticas

27.16 Errores frecuentes

• Creer que todo orden debe comparar cualquier par de elementos.
• Confundir orden parcial con orden total.
• Olvidar verificar la antisimetría.
• Confundir una relación simétrica con una relación de orden.
• Usar una relación estricta como si fuera reflexiva.

27.17 Qué debes recordar de este tema

• Una relación de orden parcial es reflexiva, antisimétrica y transitiva.
• La relación ≤ es un ejemplo clásico de orden.
• La inclusión ⊆ también define un orden parcial.
• Un orden parcial no exige que todos los pares sean comparables.
• Un orden total sí permite comparar cualquier par de elementos.
• En JavaScript, las propiedades pueden verificarse recorriendo pares de la relación.

27.18 Conclusión

Las relaciones de orden permiten modelar comparaciones, jerarquías y dependencias. Su estructura se apoya en reflexividad, antisimetría y transitividad.

En el próximo tema estudiaremos conjuntos parcialmente ordenados.