Las relaciones describen cómo se vinculan los elementos de un conjunto. Algunas agrupan elementos indistinguibles bajo cierto criterio; otras los organizan mediante precedencia, inclusión o divisibilidad.
En programación no solo importan los valores individuales, sino también sus vínculos: dos usuarios pueden ser iguales por un identificador, una tarea puede depender de otra, un conjunto puede estar contenido en otro y un archivo puede ser una versión posterior de otro.
La matemática discreta modela estos vínculos mediante relaciones. Dos familias especialmente importantes son las relaciones de equivalencia, que clasifican, y las relaciones de orden, que organizan o establecen precedencia.
Dados dos conjuntos A y B, su producto cartesiano A × B es el conjunto de todos los pares ordenados (a, b) con a en A y b en B.
El orden del par importa: (1, x) no es el mismo objeto que (x, 1). Las relaciones se construyen como subconjuntos de productos cartesianos.
Una relación R de A en B es un subconjunto de A × B. Si A = B, decimos que R es una relación sobre A. Escribimos aRb cuando el par (a, b) pertenece a R.
La misma pareja de conjuntos puede admitir muchas relaciones distintas. Las propiedades de R dependen de la regla que define cuáles pares pertenecen a ella.
En conjuntos finitos, una relación puede mostrarse como lista de pares, como matriz o como grafo dirigido. Cada formato resalta una característica diferente.
La matriz permite verificar propiedades mediante patrones de filas y columnas. El grafo dirigido ayuda a visualizar recorridos, ciclos y dependencias.
Para una relación R de A en B, el dominio de R contiene los elementos de A que se relacionan con al menos un elemento de B. La imagen contiene los elementos de B relacionados con al menos un elemento de A.
Una función es un caso particular de relación: cada elemento del dominio debe relacionarse con exactamente un elemento del codominio.
Una relación R sobre A es reflexiva si cada elemento se relaciona consigo mismo:
En la matriz de una relación reflexiva, todos los elementos de la diagonal principal son 1. En un grafo dirigido, cada vértice tiene un lazo hacia sí mismo.
Una relación R sobre A es simétrica si al relacionarse a con b, también se relaciona b con a.
En la matriz, una relación simétrica se refleja respecto de la diagonal principal. En un grafo, toda flecha entre vértices distintos tiene su flecha inversa.
Una relación R es antisimétrica si aRb y bRa solo pueden ocurrir cuando a y b son el mismo elemento.
Antisimétrica no significa «no simétrica». La igualdad es simultáneamente simétrica y antisimétrica; fuera de la diagonal no tiene pares relacionados.
Una relación R es transitiva si una cadena de dos relaciones permite concluir una relación directa:
La transitividad permite deducir consecuencias de dependencias y precedencias. Una relación «ser amigo de» suele ser simétrica, pero no es necesariamente transitiva.
| Relación | Reflexiva | Simétrica | Antisimétrica | Transitiva |
|---|---|---|---|---|
| = | Sí | Sí | Sí | Sí |
| ≤ | Sí | No | Sí | Sí |
| < | No | No | Sí (vacía de pares opuestos) | Sí |
| «misma edad» | Sí | Sí | No en general | Sí |
| «ser amigo de» | No en general | Sí en un modelo mutuo | No | No en general |
Las propiedades deben evaluarse respecto de un conjunto y una definición concretos. Una relación informal puede requerir aclaraciones antes de decidir si las cumple.
Una relación de equivalencia sobre A es reflexiva, simétrica y transitiva. Modela la idea de que dos elementos son indistinguibles según un criterio elegido.
La equivalencia no requiere que los elementos sean idénticos. Dos enteros distintos pueden ser equivalentes módulo 5 si pertenecen a la misma clase de residuos.
La clase de equivalencia de a es el conjunto de todos los elementos relacionados con a. Se escribe [a].
Si a y b son equivalentes, entonces [a] = [b]. Si no lo son, sus clases no tienen elementos en común. Por ello, las clases de equivalencia dividen el conjunto original en grupos disjuntos.
Una partición de un conjunto A es una colección de subconjuntos no vacíos, disjuntos dos a dos, cuya unión es A. Las clases de cualquier relación de equivalencia forman una partición.
También funciona al revés: toda partición define una relación de equivalencia, declarando equivalentes a dos elementos cuando pertenecen al mismo bloque de la partición.
En programación, agrupar registros por una clave construye clases de equivalencia. Por ejemplo, los productos con la misma categoría pertenecen a un mismo grupo respecto de la relación «tener igual categoría».
function agruparPorCategoria(productos) {
const grupos = new Map();
for (const producto of productos) {
const grupo = grupos.get(producto.categoria) ?? [];
grupo.push(producto.nombre);
grupos.set(producto.categoria, grupo);
}
return grupos;
}
const productos = [
{ nombre: "teclado", categoria: "periféricos" },
{ nombre: "mouse", categoria: "periféricos" },
{ nombre: "monitor", categoria: "pantallas" }
];
console.log(agruparPorCategoria(productos));Cada producto queda en exactamente un grupo siempre que cada registro tenga una categoría definida. Esa condición corresponde a que las clases formen una partición.
Una relación de orden parcial sobre A es reflexiva, antisimétrica y transitiva. Se suele denotar con ≤, aunque no tiene por qué ser el orden numérico habitual.
La palabra «parcial» indica que puede haber elementos que no se puedan comparar. No todos los órdenes parciales forman una sola cadena.
En los enteros positivos, definimos a ≤d b cuando a divide a b. Esta relación es un orden parcial.
La reflexividad proviene de que a divide a. La antisimetría y transitividad se derivan de las propiedades de la divisibilidad.
Un orden parcial es total o lineal si cualquier par de elementos puede compararse: para todos a y b, se cumple aRb o bRa.
Ordenar una lista de números usa un orden total. En cambio, ordenar tareas con dependencias necesita tratar elementos incomparables y puede producir varias secuencias válidas.
Un orden estricto, como <, es irreflexivo y transitivo: ningún elemento es menor que sí mismo y las cadenas se preservan. A menudo se obtiene desde un orden no estricto eliminando la igualdad.
Conviene no mezclar las propiedades de los órdenes estrictos con las de los no estrictos. Un orden parcial no estricto es reflexivo; su versión estricta correspondiente es irreflexiva.
Un diagrama de Hasse representa un orden parcial sin dibujar lazos reflexivos ni flechas que se deducen por transitividad. Los elementos mayores se colocan visualmente por encima de los menores.
Esta representación hace visibles los elementos incomparables y las relaciones de cobertura. El próximo tema estudiará estructuras de orden parcial con propiedades adicionales llamadas retículos.
Para una relación definida por una función booleana relacion(a, b), podemos recorrer todas las parejas o ternas del conjunto finito y comprobar sus propiedades.
function esEquivalencia(elementos, relacion) {
for (const a of elementos) {
if (!relacion(a, a)) return false; // reflexividad
for (const b of elementos) {
if (relacion(a, b) && !relacion(b, a)) return false; // simetría
for (const c of elementos) {
if (relacion(a, b) && relacion(b, c) && !relacion(a, c)) {
return false; // transitividad
}
}
}
}
return true;
}
const mismoResiduoMod3 = (a, b) => ((a - b) % 3) === 0;
console.log(esEquivalencia([0, 1, 2, 3, 4, 5], mismoResiduoMod3)); // trueEl algoritmo revisa O(n³) ternas por la condición de transitividad. Para conjuntos pequeños es claro y útil; en estructuras grandes se aprovechan propiedades específicas de la relación en lugar de probar todos los casos.
function esOrdenParcial(elementos, relacion) {
for (const a of elementos) {
if (!relacion(a, a)) return false;
for (const b of elementos) {
if (relacion(a, b) && relacion(b, a) && a !== b) return false;
for (const c of elementos) {
if (relacion(a, b) && relacion(b, c) && !relacion(a, c)) {
return false;
}
}
}
}
return true;
}
const divide = (a, b) => b % a === 0;
console.log(esOrdenParcial([1, 2, 3, 6], divide)); // truePara evitar ambigüedades, los elementos del ejemplo son números primitivos. Si se usan objetos, se debe definir con claridad qué significa que dos elementos sean iguales, por ejemplo mediante un identificador.
Modelar explícitamente una relación obliga a precisar su significado. Esto previene errores como tratar una dependencia como si fuera simétrica o suponer que una clasificación permite comparar todos los elementos.
Las relaciones de equivalencia permiten agrupar; las de orden permiten organizar. En el próximo tema estudiaremos retículos, órdenes parciales en los que ciertos pares poseen operaciones naturales de encuentro y unión.