15. Relaciones de orden total

15.1 Introducción

En un orden parcial no todos los elementos tienen que ser comparables. En cambio, en un orden total, cualquier par de elementos del conjunto puede compararse.

Esta idea aparece cuando ordenamos números, fechas, prioridades, puntajes, versiones o elementos de una lista según un criterio único.

15.2 Definición

Una relación R sobre un conjunto A es una relación de orden total si cumple las propiedades de orden parcial y, además, todo par de elementos es comparable.

• Reflexiva: todo elemento está relacionado consigo mismo.
• Antisimétrica: no hay ida y vuelta entre elementos distintos.
• Transitiva: las comparaciones encadenadas se conservan.
• Total o completa: para todo a y b, se cumple a R b o b R a.

15.3 Ejemplo con números

La relación ≤ sobre números es un orden total. Dados dos números cualesquiera, siempre podemos compararlos.

Para cualquier par de números a y b, al menos una de estas afirmaciones es verdadera: a ≤ b o b ≤ a.

15.4 Ejemplo con fechas

Las fechas también pueden ordenarse totalmente si usamos la relación “ocurre antes o en el mismo momento que”.

Esto permite ordenar eventos, logs, tareas, publicaciones y versiones temporales.

15.5 Comparabilidad total

La diferencia principal con el orden parcial es la comparabilidad. En un orden total no puede haber elementos incomparables.

15.6 Orden total en programación

Cuando usamos un criterio de ordenamiento que puede comparar cualquier par de elementos, estamos trabajando con una idea de orden total.

const puntajes = [42, 15, 99, 73, 15];

puntajes.sort((a, b) => a - b);

console.log(puntajes);

El comparador numérico permite decidir el orden relativo de cualquier par de puntajes.

15.7 Orden lexicográfico

El orden alfabético o lexicográfico también puede verse como un orden total sobre cadenas, siempre que el criterio de comparación esté bien definido.

const nombres = ["Marta", "Ana", "Luis", "Carlos"];

nombres.sort((a, b) => a.localeCompare(b));

console.log(nombres);

Cualquier par de nombres puede compararse alfabéticamente.

15.8 Verificar orden total con pares

Si representamos una relación como pares ordenados, debemos verificar que sea orden parcial y que todos los elementos sean comparables.

function contienePar(relacion, a, b) {
  return relacion.some(([x, y]) => x === a && y === b);
}

function todosComparables(conjunto, relacion) {
  for (const a of conjunto) {
    for (const b of conjunto) {
      if (!contienePar(relacion, a, b) && !contienePar(relacion, b, a)) {
        return false;
      }
    }
  }

  return true;
}

La función revisa todos los pares posibles. Si encuentra dos elementos sin comparación en ningún sentido, la relación no es total.

15.9 Ejemplo completo

Representemos el orden ≤ sobre el conjunto {1, 2, 3}.

const A = [1, 2, 3];

const menorOIgual = [
  [1, 1],
  [1, 2],
  [1, 3],
  [2, 2],
  [2, 3],
  [3, 3]
];

function contienePar(relacion, a, b) {
  return relacion.some(([x, y]) => x === a && y === b);
}

function todosComparables(conjunto, relacion) {
  return conjunto.every(a =>
    conjunto.every(b =>
      contienePar(relacion, a, b) || contienePar(relacion, b, a)
    )
  );
}

console.log(todosComparables(A, menorOIgual));

Todos los elementos pueden compararse con todos los demás, por eso la relación cumple la condición de totalidad.

15.10 Orden parcial que no es total

La inclusión entre conjuntos es un ejemplo clásico de orden parcial que no siempre es total.

Como existe al menos un par de elementos incomparables, la relación no es de orden total.

15.11 Usos en informática

15.12 Errores comunes

• Confundir orden parcial con orden total.
• Creer que cualquier relación transitiva es un orden total.
• Olvidar que todos los pares de elementos deben ser comparables.
• Usar un criterio de comparación que no resuelve empates o casos ambiguos.
• Suponer que una jerarquía siempre es total, aunque tenga ramas incomparables.

15.13 Qué debes recordar de este tema

• Un orden total es un orden parcial donde todos los elementos son comparables.
• Debe ser reflexivo, antisimétrico, transitivo y total.
• No puede haber pares de elementos incomparables.
• Los números con ≤, las fechas y el orden alfabético son ejemplos habituales.
• En programación, los ordenamientos de listas suelen apoyarse en criterios de orden total.

15.14 Conclusión

Las relaciones de orden total permiten organizar todos los elementos de un conjunto en una secuencia comparable. Son fundamentales para ordenar datos, construir rankings, analizar prioridades y procesar listas.

En el próximo tema estudiaremos diagramas de Hasse, una forma visual de representar órdenes parciales eliminando información redundante.