Una relación de equivalencia permite agrupar elementos que pueden considerarse iguales bajo un criterio. Es la base para clasificar datos, formar grupos y construir particiones.
En muchos problemas no necesitamos que dos elementos sean idénticos en todos los sentidos. A veces alcanza con que sean equivalentes según una regla concreta.
Por ejemplo, dos usuarios pueden pertenecer al mismo grupo, dos números pueden tener el mismo resto al dividir por 3, dos archivos pueden tener la misma extensión o dos productos pueden estar en la misma categoría.
Una relación R sobre un conjunto A es una relación de equivalencia si cumple tres propiedades:
Una relación de equivalencia agrupa elementos que comparten una característica. Dentro de cada grupo, todos los elementos son equivalentes entre sí según la regla definida.
La equivalencia no significa que los elementos sean iguales, sino que coinciden en el criterio que estamos usando.
En el conjunto de números enteros, podemos definir que dos números están relacionados si tienen el mismo resto al dividir por 3.
Por ejemplo, 1, 4 y 7 son equivalentes porque todos dejan resto 1 al dividir por 3.
| Propiedad | Aplicación al resto módulo 3 |
|---|---|
| Reflexiva | Todo número tiene el mismo resto que sí mismo. |
| Simétrica | Si a tiene el mismo resto que b, entonces b tiene el mismo resto que a. |
| Transitiva | Si a tiene el mismo resto que b y b el mismo resto que c, entonces a tiene el mismo resto que c. |
Podemos definir una relación entre archivos: dos archivos están relacionados si tienen la misma extensión.
Esta relación es de equivalencia porque cada archivo tiene la misma extensión que sí mismo, la coincidencia de extensión es recíproca y si dos coincidencias se encadenan, la tercera también coincide.
Podemos verificar una relación de equivalencia combinando las pruebas de reflexividad, simetría y transitividad.
function contienePar(relacion, a, b) {
return relacion.some(([x, y]) => x === a && y === b);
}
function esReflexiva(conjunto, relacion) {
return conjunto.every(a => contienePar(relacion, a, a));
}
function esSimetrica(relacion) {
return relacion.every(([a, b]) => contienePar(relacion, b, a));
}
function esTransitiva(relacion) {
for (const [a, b] of relacion) {
for (const [c, d] of relacion) {
if (b === c && !contienePar(relacion, a, d)) {
return false;
}
}
}
return true;
}
function esEquivalencia(conjunto, relacion) {
return esReflexiva(conjunto, relacion)
&& esSimetrica(relacion)
&& esTransitiva(relacion);
}Para un conjunto pequeño, podemos construir todos los pares que cumplen un criterio de equivalencia. En este ejemplo, relacionamos números que tienen el mismo resto al dividir por 3.
const numeros = [0, 1, 2, 3, 4, 5, 6, 7, 8];
const mismaClaseModulo3 = numeros.flatMap(a =>
numeros
.filter(b => a % 3 === b % 3)
.map(b => [a, b])
);
console.log(mismaClaseModulo3);La relación generada agrupa los números según su resto: resto 0, resto 1 y resto 2.
Ahora podemos usar las funciones anteriores para comprobar que la relación generada es una relación de equivalencia.
const numeros = [0, 1, 2, 3, 4, 5];
const relacion = numeros.flatMap(a =>
numeros
.filter(b => a % 3 === b % 3)
.map(b => [a, b])
);
function contienePar(relacion, a, b) {
return relacion.some(([x, y]) => x === a && y === b);
}
function esReflexiva(conjunto, relacion) {
return conjunto.every(a => contienePar(relacion, a, a));
}
function esSimetrica(relacion) {
return relacion.every(([a, b]) => contienePar(relacion, b, a));
}
function esTransitiva(relacion) {
for (const [a, b] of relacion) {
for (const [c, d] of relacion) {
if (b === c && !contienePar(relacion, a, d)) return false;
}
}
return true;
}
console.log(esReflexiva(numeros, relacion));
console.log(esSimetrica(relacion));
console.log(esTransitiva(relacion));No toda relación que parece agrupar elementos es una relación de equivalencia. Si falla una sola de las tres propiedades, ya no es equivalencia.
| Relación | Propiedad que puede fallar | Motivo |
|---|---|---|
| Ser menor que | Reflexiva y simétrica | Ningún número es menor que sí mismo y la relación no va en ambos sentidos. |
| Ser amigo de | Transitiva | Si Ana es amiga de Luis y Luis de Marta, Ana no necesariamente es amiga de Marta. |
| Depender de | Simétrica | Si A depende de B, no implica que B dependa de A. |
Una relación de equivalencia divide un conjunto en grupos llamados clases de equivalencia. Todos los elementos de una misma clase son equivalentes entre sí.
Este concepto será el tema central del próximo capítulo.
Las relaciones de equivalencia permiten definir cuándo dos elementos deben considerarse del mismo tipo, grupo o categoría según una regla concreta. Esta idea es clave para clasificar información y organizar datos discretos.
En el próximo tema estudiaremos clases de equivalencia y particiones, que muestran cómo una relación de equivalencia divide un conjunto en grupos bien definidos.