En la publicación anterior estudiamos las relaciones binarias, sus propiedades fundamentales y las clasificamos en 8 clases. Entre todas ellas, la relación de equivalencia ocupa un lugar especial: es la herramienta matemática que permite agrupar elementos que comparten una característica común, tratándolos como si fueran «iguales» bajo cierto criterio.
En esta publicación profundizaremos en las relaciones de equivalencia, descubriremos cómo generan clases de equivalencia y conjuntos cociente, y demostraremos el poderoso Teorema Fundamental que conecta estas relaciones con las particiones de un conjunto. Además, veremos cómo este concepto aparentemente abstracto tiene aplicaciones directas en áreas como la computación, la inteligencia artificial, la ingeniería y la vida cotidiana.
Recordatorio: relación de equivalencia
En la publicación anterior definimos que una relación \( R \) sobre un conjunto \( A \) es una relación de equivalencia si cumple tres propiedades simultáneamente:
| Propiedad | Definición formal | Significado |
|---|---|---|
| Reflexiva | \( \forall a \in A: (a,a) \in R \) | Todo elemento se relaciona consigo mismo |
| Simétrica | \( (a,b) \in R \implies (b,a) \in R \) | Si \( a \) se relaciona con \( b \), entonces \( b \) se relaciona con \( a \) |
| Transitiva | \( (a,b) \in R \wedge (b,c) \in R \implies (a,c) \in R \) | Si \( a \) se relaciona con \( b \) y \( b \) con \( c \), entonces \( a \) se relaciona con \( c \) |
Intuición. Una relación de equivalencia generaliza la idea de igualdad: agrupa elementos que, bajo cierto criterio, se consideran «lo mismo». La igualdad \( = \) es la relación de equivalencia más básica, pero hay muchas otras.
¿Qué falla si falta alguna propiedad?
Si una relación cumple solo dos de las tres propiedades, no es de equivalencia y no puede agrupar elementos correctamente:
| Propiedades presentes | Clase | Ejemplo |
|---|---|---|
| Reflexiva + Simétrica | Dependencia | «se conocen mutuamente» — si Ana conoce a Bruno y Bruno a Carlos, no implica que Ana conozca a Carlos; sin transitividad, los grupos tienen elementos en común |
| Reflexiva + Transitiva | Preorden | \( \leq \) — sin simetría, hay jerarquía en vez de igualdad |
| Simétrica + Transitiva | — | Sin reflexividad, puede haber elementos que no pertenecen a ningún grupo |
En otras palabras: Una relación de equivalencia no permite que existan grupos con elementos en común (solapamiento), ni que un grupo esté contenido dentro de otro (jerarquía), ni que haya elementos sueltos que no pertenezcan a ningún grupo.
Solo la combinación completa de las tres propiedades garantiza una agrupación perfecta: bloques separados, sin huecos, donde cada elemento pertenece a exactamente un grupo que comparte los mismos criterios.
Ejemplos de relaciones de equivalencia
En los siguientes ejemplos usaremos una matriz de relación para visualizar los pares ordenados. En esta tabla, las filas y columnas representan los elementos del conjunto, y cada celda contiene:
- 1 si el par \( (fila,\ columna) \) pertenece a la relación (verdadero)
- 0 si no pertenece (falso)
Por ejemplo, para el conjunto \( \{a, b\} \) con la relación \( R = \{(a, a),\ (a, b),\ (b, b)\} \):
| a | b | |
|---|---|---|
| a | 1 | 1 |
| b | 0 | 1 |
La celda de la fila \( a \) y columna \( b \) contiene 1 porque \( (a, b) \in R \), mientras que la celda de la fila \( b \) y columna \( a \) contiene 0 porque \( (b, a) \notin R \).
Dicho esto, veamos los ejemplos:
Ejemplo 1: relación explícita sobre un conjunto finito
Sea \( S = \{1, 2, 3\} \) y la relación:
\[ R = \{(1, 1),\ (1, 2),\ (2, 1),\ (2, 2),\ (3, 3)\} \]
Verificamos las tres propiedades:
- Reflexiva: \( (1,1),\ (2,2),\ (3,3) \in R \) ✓
- Simétrica: \( (1,2) \in R \) y \( (2,1) \in R \) ✓; los pares diagonales son su propio espejo ✓
- Transitiva: \( (1,2) \wedge (2,1) \implies (1,1) \in R \) ✓; \( (2,1) \wedge (1,2) \implies (2,2) \in R \) ✓
\( R \) es una relación de equivalencia. ✓
Su matriz de relación:
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 0 | 0 | 1 |
Observa cómo la matriz forma bloques cuadrados de 1s a lo largo de la diagonal. Este patrón visual es característico de las relaciones de equivalencia.
Ejemplo 2: la igualdad
La relación \( = \) sobre cualquier conjunto es una relación de equivalencia:
- \( a = a \) ✓ (reflexiva)
- \( a = b \implies b = a \) ✓ (simétrica)
- \( a = b \wedge b = c \implies a = c \) ✓ (transitiva)
Es la relación de equivalencia más fina posible: cada elemento solo es equivalente a sí mismo.
Ejemplo 3: misma paridad
Sea \( R \) la relación sobre \( \mathbb{Z} \) definida por: \( aRb \) si \( a \) y \( b \) tienen la misma paridad (ambos pares o ambos impares).
- Reflexiva: Todo número tiene la misma paridad que sí mismo ✓
- Simétrica: Si \( a \) tiene la misma paridad que \( b \), entonces \( b \) tiene la misma paridad que \( a \) ✓
- Transitiva: Si \( a \) y \( b \) son ambos pares, y \( b \) y \( c \) son ambos pares, entonces \( a \) y \( c \) son ambos pares ✓ (análogo para impares)
\( R \) es una relación de equivalencia que divide a \( \mathbb{Z} \) en exactamente dos grupos: los números pares y los números impares.
Ejemplo numérico:
- \( 4R6 \) ✓ (ambos pares)
- \( 3R7 \) ✓ (ambos impares)
- \( 4 \not{R} 3 \) ✗ (uno par, otro impar)
Ejemplo 4: la diferencia es un entero
Sea \( R \) la relación sobre \( \mathbb{R} \) definida por \( aRb \) si y solo si \( a – b \in \mathbb{Z} \).
- Reflexiva: \( a – a = 0 \in \mathbb{Z} \) ✓
- Simétrica: Si \( a – b \in \mathbb{Z} \), entonces \( b – a = -(a – b) \in \mathbb{Z} \) ✓
- Transitiva: Si \( a – b \in \mathbb{Z} \) y \( b – c \in \mathbb{Z} \), entonces \( a – c = (a – b) + (b – c) \in \mathbb{Z} \) ✓
¿Qué agrupa esta relación? Los números reales que difieren en un entero: por ejemplo, \( 3.7 R 0.7 R (-2.3) \), ya que todos tienen la misma parte decimal \( 0.7 \).
Ejemplo 5: relaciones geométricas
| Relación | Conjunto | ¿Equivalencia? | Criterio de «igualdad» |
|---|---|---|---|
| Paralelismo (\( \parallel \)) | Rectas del plano | ✓ | Misma dirección |
| Congruencia (\( \cong \)) | Figuras geométricas | ✓ | Misma forma y tamaño |
| Semejanza (\( \sim \)) | Figuras geométricas | ✓ | Misma forma (tamaño puede variar) |
Ejemplo 6: relación que NO es de equivalencia
Sea \( R \) sobre \( \mathbb{R} \) definida por \( xRy \) si \( |x – y| < 1 \).
- Reflexiva: \( |x – x| = 0 < 1 \) ✓
- Simétrica: \( |x – y| = |y – x| \), así que si \( |x – y| < 1 \) entonces \( |y – x| < 1 \) ✓
- Transitiva: Tomemos \( x = 2.8 \), \( y = 1.9 \), \( z = 1.1 \). Entonces \( |2.8 – 1.9| = 0.9 < 1 \) ✓ y \( |1.9 – 1.1| = 0.8 < 1 \) ✓, pero \( |2.8 – 1.1| = 1.7 > 1 \) ✗
No es de equivalencia porque falla la transitividad. Sin ella, las agrupaciones se solapan sin fronteras claras.
Elementos equivalentes y notación
Después de ver varios ejemplos, podemos formalizar qué significa que dos elementos sean «equivalentes».
Dados dos elementos \( a \) y \( b \) de un conjunto \( A \), decimos que \( a \) y \( b \) son equivalentes bajo una relación de equivalencia \( R \) si están relacionados entre sí por dicha relación, es decir, si \( (a, b) \in R \).
Esto se expresa formalmente como:
\[ a \sim b \]
que se lee «\( a \) es equivalente a \( b \)» o «\( a \) está relacionado con \( b \)».
Notación. El símbolo \( \sim \) se usa en lugar de \( R \) cuando trabajamos con relaciones de equivalencia. Así, \( a \sim b \) es otra forma de escribir \( (a, b) \in R \) o \( aRb \). De aquí en adelante usaremos esta notación.
Aplicando esta notación a los ejemplos anteriores:
| Ejemplo | Equivalencia | Significado |
|---|---|---|
| Ej. 1 (conjunto finito) | \( 1 \sim 2 \) | 1 y 2 pertenecen a la misma clase en \( R \) |
| Ej. 2 (igualdad) | \( 7 \sim 7 \) | 7 es igual a sí mismo |
| Ej. 3 (paridad) | \( 4 \sim 6 \) | 4 y 6 son ambos pares |
| Ej. 4 (diferencia entera) | \( 3.7 \sim 0.7 \) | \( 3.7 – 0.7 = 3 \in \mathbb{Z} \) |
| Ej. 5 (paralelismo) | \( L_1 \sim L_2 \) | Las rectas \( L_1 \) y \( L_2 \) son paralelas |
| Ej. 6 (no equivalencia) | \( 2.8 \not\sim 1.1 \) | \( R \) no es de equivalencia — no se puede usar \( \sim \) |
Tomemos el ejemplo 3 (paridad): sabemos que \( 4 \sim 6 \) porque ambos son pares. Pero 4 también se relaciona con 8, con 10, con 2, con 0… En general, todos los números pares son equivalentes entre sí. Esto significa que existe un conjunto completo de números que se relacionan con 4 — el conjunto de todos los pares. Ese conjunto tiene un nombre formal, y es precisamente lo que estudiaremos a continuación.
Clases de equivalencia
Como vimos con el ejemplo de la paridad, una relación de equivalencia agrupa los elementos de un conjunto en subconjuntos — todos los pares por un lado, todos los impares por otro. Cada uno de estos subconjuntos se llama clase de equivalencia. De manera general, para cualquier relación de equivalencia, tenemos la siguiente definición:
Definición
Sea \( \sim \) una relación de equivalencia sobre un conjunto \( A \). La clase de equivalencia de un elemento \( a \in A \) es el conjunto de todos los elementos de \( A \) que están relacionados con \( a \):
\[ [a] = \{x \in A \mid x \sim a\} \]
En palabras simples: La clase \( [a] \) contiene a todos los elementos que son «equivalentes» a \( a \) — incluyendo al propio \( a \).
Cualquier elemento \( b \in [a] \) se llama representante de la clase. Como veremos, cualquier elemento de una clase puede usarse como representante — no hay nada especial en la elección de \( a \).
Ejemplo 1: clases en un conjunto finito
Retomemos \( S = \{1, 2, 3\} \) con \( R = \{(1,1),\ (1,2),\ (2,1),\ (2,2),\ (3,3)\} \).
Para calcular la clase de cada elemento, tomamos un elemento y buscamos con cuáles otros está relacionado en los pares ordenados de \( R \):
- Clase de 1: Buscamos todos los pares donde aparece 1: \( (1,1) \) y \( (1,2) \). Es decir, 1 se relaciona con 1 y con 2. Por tanto: \( [1] = \{1, 2\} \)
- Clase de 2: Pares donde aparece 2: \( (2,1) \) y \( (2,2) \). El 2 se relaciona con 1 y consigo mismo. Por tanto: \( [2] = \{1, 2\} \)
- Clase de 3: Pares donde aparece 3: solo \( (3,3) \). El 3 solo se relaciona consigo mismo. Por tanto: \( [3] = \{3\} \)
Observa que \( [1] = [2] = \{1, 2\} \) — como 1 y 2 son equivalentes, generan la misma clase. Por otro lado, \( [3] = \{3\} \) forma su propia clase.
Las clases distintas son: \( \{1, 2\} \) y \( \{3\} \). Juntas cubren todo \( S \) sin solaparse.
Nota. Intuitivamente, «cubrir» significa que al unir todas las clases se obtiene el conjunto original: \( \{1, 2\} \cup \{3\} = \{1, 2, 3\} = S \). Si deseas profundizar en los conceptos de cubrimientos y particiones de conjuntos, puedes consultar la publicación sobre familia de conjuntos, donde abordamos estos temas en detalle.
Ejemplo 2: clases de la paridad
Retomemos la relación de paridad del ejemplo 3 (sección anterior): \( aRb \) si \( a \) y \( b \) tienen la misma paridad. Calculamos las clases:
\[ [0] = \{\ldots, -4, -2, 0, 2, 4, \ldots\} = \text{pares} \] \[ [1] = \{\ldots, -3, -1, 1, 3, 5, \ldots\} = \text{impares} \]
Todo entero pertenece a exactamente una de estas 2 clases. Por ejemplo:
- \( 8 \in [0] \) porque 8 es par
- \( -7 \in [1] \) porque \( -7 \) es impar
- \( [4] = [0] = [2] = [-6] \) — todos los pares generan la misma clase
Observa que el conjunto \( \mathbb{Z} \) (infinito) queda dividido en solo 2 clases.
Ejemplo 3: clases en un conjunto con 4 elementos
Sea \( A = \{a, b, c, d\} \) y la relación:
\[ R = \{(a,a),\ (b,b),\ (c,c),\ (d,d),\ (a,c),\ (c,a),\ (b,d),\ (d,b)\} \]
Verificamos que \( R \) es de equivalencia (reflexiva ✓, simétrica ✓, transitiva ✓). Las clases son:
\[ [a] = \{a, c\}, \quad [b] = \{b, d\}, \quad [c] = \{c, a\} = [a], \quad [d] = \{d, b\} = [b] \]
Solo hay dos clases distintas: \( \{a, c\} \) y \( \{b, d\} \).
Propiedades fundamentales de las clases de equivalencia
Las clases de equivalencia satisfacen tres propiedades que se deducen directamente de los axiomas de la relación:
Propiedad 1. Todo elemento pertenece a su propia clase.
\[ \forall a \in A: a \in [a] \]
Demostración: Como \( \sim \) es reflexiva, \( a \sim a \), lo que por definición significa que \( a \in [a] \). En particular, ninguna clase de equivalencia puede ser vacía. ∎
Propiedad 2. Dos elementos equivalentes generan la misma clase.
\[ a \sim b \implies [a] = [b] \]
Demostración: Supongamos que \( a \sim b \). Mostraremos que \( [a] \subseteq [b] \) y \( [b] \subseteq [a] \).
Sea \( x \in [a] \), entonces \( x \sim a \). Como tenemos \( a \sim b \) (hipótesis), aplicamos transitividad: \( x \sim a \) y \( a \sim b \) implican \( x \sim b \). Luego \( x \in [b] \), así que \( [a] \subseteq [b] \).
De manera análoga (usando \( b \sim a \) por simetría), se demuestra que \( [b] \subseteq [a] \).
Por tanto, \( [a] = [b] \). ∎
Propiedad 3. Dos clases distintas son completamente disjuntas.
\[ [a] \neq [b] \implies [a] \cap [b] = \emptyset \]
Demostración: Procedemos por reducción al absurdo. Supongamos que \( [a] \cap [b] \neq \emptyset \). Entonces existe \( y \in [a] \cap [b] \), lo que significa \( y \sim a \) y \( y \sim b \). Por simetría, \( a \sim y \). Aplicando transitividad con \( y \sim b \), obtenemos \( a \sim b \). Pero por la Propiedad 2, esto implica \( [a] = [b] \), lo que contradice la hipótesis de que son distintas. ∎
Resumen visual. Las tres propiedades nos dicen que las clases de equivalencia forman un mosaico perfecto sobre \( A \): cada elemento pertenece a exactamente una clase, y las clases no se solapan ni dejan huecos. Este comportamiento tiene un nombre propio: partición.
Conjunto cociente
Definición
Sea \( \sim \) una relación de equivalencia sobre \( A \). La colección de todas las clases de equivalencia distintas se llama conjunto cociente de \( A \) respecto a \( \sim \), y se denota:
\[ A/ \negthinspace \sim \ = \{[a] \mid a \in A\} \]
En palabras simples: El conjunto cociente es un «nuevo conjunto» cuyos elementos no son los elementos originales de \( A \), sino las clases (los «grupos») que la equivalencia forma. Es como pasar de ver individuos a ver familias.
Ejemplo 1
Con \( S = \{1, 2, 3\} \) y la relación del ejemplo anterior:
\[ S/ \negthinspace \sim \ = \{[1], [3]\} = \{\{1, 2\},\ \{3\}\} \]
El conjunto \( S \) tenía 3 elementos; el cociente \( S/ \negthinspace \sim \) tiene 2 elementos (dos clases). Como representantes podemos elegir \( \{1, 3\} \) o \( \{2, 3\} \) — cualquier elección es válida.
¿Qué son los representantes? Un representante es cualquier elemento que elijamos para nombrar una clase. Como \( [1] = [2] = \{1, 2\} \), podemos llamar a esta clase «[1]» o «[2]» — ambos nombres se refieren al mismo conjunto. Para la clase \( \{3\} \), el único representante posible es 3. Así, un posible conjunto de representantes es \( \{1, 3\} \), pero \( \{2, 3\} \) también es válido.
Ejemplo 2
Con \( A = \{a, b, c, d\} \) y la relación del ejemplo anterior:
\[ A/ \negthinspace \sim \ = \{[a], [b]\} = \{\{a, c\},\ \{b, d\}\} \]
Ejemplo 3: el cociente de los enteros por paridad
La relación de paridad sobre \( \mathbb{Z} \) produce el conjunto cociente:
\[ \mathbb{Z}/ \negthinspace \sim \ = \{[0],\ [1]\} = \{\text{pares},\ \text{impares}\} \]
El conjunto \( \mathbb{Z} \) (infinito) queda comprimido en un cociente de solo 2 elementos. Cualquier par puede usarse como representante de la primera clase (\( [0] = [2] = [-4] \)) y cualquier impar como representante de la segunda (\( [1] = [3] = [-7] \)).
Conteo de pares en una relación de equivalencia
Existe una fórmula útil para contar el número total de pares ordenados en una relación de equivalencia. Si \( \sim \) divide un conjunto de \( N \) elementos en clases de tamaños \( k_1, k_2, \ldots, k_m \), entonces:
\[ \text{Número total de pares} = \sum_{i=1}^{m} k_i^2 \]
¿Por qué? Dentro de cada clase de tamaño \( k_i \), todos los elementos están relacionados entre sí (reflexiva y simétricamente), generando una cuadrícula completa de \( k_i \times k_i = k_i^2 \) pares.
Ejemplo. En \( A = \{a, b, c, d\} \) con clases \( \{a, c\} \) y \( \{b, d\} \):
\[ k_1 = 2,\quad k_2 = 2 \implies \text{pares} = 2^2 + 2^2 = 4 + 4 = 8 \]
Verificamos: \( R = \{(a,a), (c,c), (a,c), (c,a), (b,b), (d,d), (b,d), (d,b)\} \) tiene exactamente 8 pares. ✓
Nota. Además, se cumple siempre que \( \sum_{i=1}^{m} k_i = N \) (la suma de los tamaños reconstituye el conjunto completo).
Particiones
Imagina que tienes un grupo de 6 estudiantes y necesitas dividirlos en equipos para un trabajo. Si los separas en tres equipos — \( \{Ana, Luis\} \), \( \{Carlos, María\} \) y \( \{Pedro, Sofía\} \) — has creado una partición: cada estudiante está en exactamente un equipo, ningún equipo está vacío, y entre todos los equipos están todos los estudiantes. Si algún estudiante quedara en dos equipos a la vez, o si alguno quedara fuera, ya no sería una partición.
Nota. Si deseas profundizar en el concepto de partición y otros tipos de familias de conjuntos (cubrimientos, cadenas, anticadenas), puedes consultar la publicación sobre familia de conjuntos, donde abordamos estos temas en detalle.
El concepto de partición está muy relacionado con las relaciones de equivalencia, es por eso que traemos de vuelta este concepto en la siguiente definición formal.
Definición
Sea \( A \) un conjunto no vacío. Una partición de \( A \) es una familia de subconjuntos \( \{A_i\}_{i \in I} \) que cumple tres condiciones:
| Condición | Nombre | Enunciado | Significado |
|---|---|---|---|
| P₁ | No vacuidad | \( A_i \neq \emptyset \) para todo \( i \in I \) | Ningún subconjunto de la familia es vacío |
| P₂ | Disyunción | \( A_i \cap A_j = \emptyset \) para todo \( i \neq j \) | Los subconjuntos son disjuntos dos a dos |
| P₃ | Cobertura | \( \bigcup_{i \in I} A_i = A \) | La unión de todos los subconjuntos reconstituye \( A \) |
En palabras simples: Una partición «corta» al conjunto \( A \) en pedazos que no se solapan y que juntos forman el todo. Cada elemento de \( A \) cae en exactamente uno de los pedazos.
Ejemplo 1: partición de un conjunto finito
Sea \( S = \{1, 2, 3, 4, 5, 6\} \). La familia \( \{A_1, A_2, A_3\} \) con:
\[ A_1 = \{1, 2, 3\}, \quad A_2 = \{4, 5\}, \quad A_3 = \{6\} \]
es una partición de \( S \):
- P₁: \( A_1 \neq \emptyset \), \( A_2 \neq \emptyset \), \( A_3 \neq \emptyset \) ✓
- P₂: \( A_1 \cap A_2 = \emptyset \), \( A_1 \cap A_3 = \emptyset \), \( A_2 \cap A_3 = \emptyset \) ✓
- P₃: \( A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6\} = S \) ✓
Ejemplo 2: todas las particiones de un conjunto pequeño
Sea \( A = \{a, b, c\} \). Las particiones posibles son:
| Partición | Subconjuntos |
|---|---|
| \( P_1 \) | \( \{\{a\}, \{b\}, \{c\}\} \) — cada elemento en su propio bloque |
| \( P_2 \) | \( \{\{a, b\}, \{c\}\} \) |
| \( P_3 \) | \( \{\{a, c\}, \{b\}\} \) |
| \( P_4 \) | \( \{\{b, c\}, \{a\}\} \) |
| \( P_5 \) | \( \{\{a, b, c\}\} \) — todo el conjunto en un solo bloque |
Hay exactamente 5 particiones. Este número corresponde al tercer número de Bell (\( B_3 = 5 \)). (ver este concepto en mi publicación sobre familia de conjuntos)
Nota. Las familias como \( \{\{a, b\}, \{b, c\}\} \) no son particiones porque \( b \) aparece en dos subconjuntos (viola P₂). Tampoco \( \{\{a\}, \{c\}\} \) porque falta \( b \) (viola P₃).
Ejemplo 3: partición del conjunto universal
Sea \( A \) un subconjunto de un universo \( U \). La familia \( \{A, A^c\} \) (donde \( A^c \) es el complemento de \( A \)) es una partición de \( U \), siempre que tanto \( A \) como \( A^c \) sean no vacíos:
- P₁: \( A \neq \emptyset \) y \( A^c \neq \emptyset \) ✓ (asumiendo \( A \neq \emptyset \) y \( A \neq U \))
- P₂: \( A \cap A^c = \emptyset \) ✓ (por definición de complemento)
- P₃: \( A \cup A^c = U \) ✓
Ejemplo 4: partición de un intervalo
Sea el intervalo \( I = [1, 3) \). Lo dividimos en 5 subintervalos de igual longitud \( \frac{3-1}{5} = \frac{2}{5} \):
\[ I_k = \left[1 + \frac{2}{5}(k-1),\ 1 + \frac{2}{5}k\right), \quad k = 1, 2, 3, 4, 5 \]
La familia \( \{I_1, I_2, I_3, I_4, I_5\} \) es una partición de \( I \):
- Cada \( I_k \neq \emptyset \) ✓
- Los subintervalos son disjuntos (no se solapan) ✓
- Su unión es \( [1, 3) = I \) ✓
El Teorema Fundamental
El resultado más importante de esta publicación establece una correspondencia perfecta entre dos conceptos aparentemente distintos:
Enunciado
Sea \( A \) un conjunto no vacío.
(a) Toda relación de equivalencia \( \sim \) sobre \( A \) induce una partición de \( A \), donde los bloques son las clases de equivalencia.
(b) Toda partición \( \{A_i\}_{i \in I} \) de \( A \) induce una relación de equivalencia sobre \( A \), donde dos elementos son equivalentes si y solo si pertenecen al mismo bloque.
En otras palabras: relaciones de equivalencia y particiones son dos caras de la misma moneda. Cada una determina a la otra de forma única.
Demostración de (a): de equivalencia a partición
Sea \( \sim \) una relación de equivalencia sobre \( A \). Debemos verificar que la familia de clases de equivalencia \( A/ \negthinspace \sim \) cumple las tres condiciones de partición:
P₁ (no vacuidad). Para todo \( a \in A \), la clase \( [a] \neq \emptyset \) porque \( a \in [a] \) (por la Propiedad 1 de las clases). ✓
P₃ (cobertura). Todo elemento \( a \in A \) pertenece a su clase \( [a] \), así que:
\[ \bigcup_{a \in A} [a] = A \]
Es decir, si tomamos todas las clases de equivalencia y las unimos (\( [a_1] \cup [a_2] \cup \ldots \)), el resultado es el conjunto \( A \) completo. Ningún elemento queda fuera. ✓
P₂ (disyunción). Si \( [a] \neq [b] \), entonces \( [a] \cap [b] = \emptyset \) (por la Propiedad 3 de las clases). ✓
Por lo tanto, \( A/ \negthinspace \sim \) es una partición de \( A \). ∎
Demostración de (b): de partición a equivalencia
Sea \( \{A_i\}_{i \in I} \) una partición de \( A \). Definimos la relación \( R \) sobre \( A \):
\[ x R y \iff \text{existe } A_i \text{ tal que } x \in A_i \text{ y } y \in A_i \]
Es decir, dos elementos están relacionados si y solo si pertenecen al mismo bloque de la partición. Verificamos los tres axiomas:
Reflexiva. Todo \( a \in A \) pertenece a algún bloque \( A_i \) (por P₃), así que \( a \) y \( a \) están en el mismo bloque. Luego \( aRa \). ✓
Simétrica. Si \( aRb \), entonces \( a \) y \( b \) están en el mismo bloque \( A_i \). Pero entonces \( b \) y \( a \) también están en el mismo bloque, así que \( bRa \). ✓
Transitiva. Si \( aRb \) y \( bRc \), entonces \( a, b \in A_i \) para algún bloque \( A_i \), y \( b, c \in A_j \) para algún bloque \( A_j \). Ahora bien, \( b \) pertenece tanto a \( A_i \) como a \( A_j \), pero como los bloques de una partición son disjuntos (P₂), un elemento no puede estar en dos bloques distintos. Por tanto, \( A_i = A_j \), y como \( a \) y \( c \) están ambos en ese mismo bloque, concluimos que \( aRc \). ✓
Por lo tanto, \( R \) es una relación de equivalencia, y las clases de equivalencia de \( R \) son exactamente los bloques \( A_i \). ∎
Ejemplo: construir una relación desde una partición
Dada la partición \( A_1 = \{1, 2, 3\} \), \( A_2 = \{4, 5\} \), \( A_3 = \{6\} \) de \( S = \{1, 2, 3, 4, 5, 6\} \):
La relación de equivalencia inducida contiene los pares \( (x, y) \) donde \( x \) e \( y \) están en el mismo bloque:
- Del bloque \( \{1, 2, 3\} \): \( (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) \) — 9 pares
- Del bloque \( \{4, 5\} \): \( (4,4), (4,5), (5,4), (5,5) \) — 4 pares
- Del bloque \( \{6\} \): \( (6,6) \) — 1 par
Total: \( 3^2 + 2^2 + 1^2 = 9 + 4 + 1 = 14 \) pares. ✓
Su matriz de relación:
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 1 | 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 1 | 1 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 | 0 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 |
Observa los bloques cuadrados de 1s a lo largo de la diagonal — uno de 3×3, uno de 2×2 y uno de 1×1. Cada bloque corresponde a una clase de equivalencia (y a un bloque de la partición).
Ejemplo: la partición inducida por la paridad
La relación de paridad divide a \( \mathbb{Z} \) en 2 clases: pares e impares. Verificamos que forman una partición:
- P₁ (no vacuidad): Ambas clases tienen infinitos elementos ✓
- P₂ (disyunción): Ningún número es par e impar a la vez ✓
- P₃ (cobertura): Todo entero es par o impar, así que pertenece a alguna clase ✓
Resumen del Teorema Fundamental. Este resultado nos da la libertad de pensar en equivalencias o particiones según convenga. Si necesitamos verificar una relación, comprobamos reflexividad, simetría y transitividad. Si necesitamos construir una, basta con definir una partición y la relación se obtiene automáticamente.
Aplicaciones de las relaciones de equivalencia
Las relaciones de equivalencia y las particiones no son solo conceptos teóricos — están presentes en múltiples disciplinas. Aquí algunas de sus aplicaciones más prácticas y comunes:
1. Computación y programación
- Estructuras de datos (Disjoint Set Union): Se usa para agrupar elementos y determinar rápidamente si dos pertenecen al mismo conjunto. Es clave en algoritmos como el de Kruskal para encontrar el árbol de expansión mínima en una red.
- Bases de datos: La normalización de tablas busca particionar la información para evitar redundancias, asegurando que cada dato esté en la «clase» que le corresponde por su dependencia lógica.
2. Matemáticas y aritmética
- Aritmética modular: La base de la criptografía moderna. Dos números son equivalentes si al dividirlos por un módulo (como 12 en un reloj) dan el mismo residuo. Esto particiona todos los enteros en un grupo finito de clases.
- Números racionales: Un medio (\( \frac{1}{2} \)) y dos cuartos (\( \frac{2}{4} \)) son representaciones diferentes del mismo valor. La relación de equivalencia permite tratarlos como un solo «número» aunque se escriban distinto.
3. Inteligencia artificial y datos
- Clustering (agrupamiento): En aprendizaje no supervisado, el objetivo es crear una partición de un conjunto de datos donde los elementos de un mismo grupo sean «similares» entre sí y diferentes a los de otros grupos.
- Procesamiento de lenguaje natural: Agrupar palabras por su raíz (lematización) o por su función gramatical es, en esencia, definir una relación de equivalencia.
4. Ingeniería y física
- Análisis dimensional: Permite agrupar diferentes magnitudes físicas en clases de equivalencia (como todas las unidades que miden «energía»), facilitando la simplificación de ecuaciones complejas.
- Circuitos lógicos: En el diseño de hardware, se agrupan estados equivalentes en máquinas de estado para reducir el número de componentes necesarios (minimización de autómatas).
5. Vida cotidiana
- Sistemas de clasificación: Desde la taxonomía biológica (especies, géneros) hasta organizar archivos en una computadora; cada vez que clasificas algo sin que un objeto pueda estar en dos categorías a la vez, estás creando una partición.
Ejercicios resueltos
Ejercicio 1: congruencia módulo \( m \)
Sean \( m \) un entero positivo fijo y \( a, b \in \mathbb{Z} \). Decimos que \( a \) es congruente con \( b \) módulo \( m \), escrito:
\[ a \equiv b \pmod{m} \]
si \( m \) divide a la diferencia \( a – b \), es decir, \( m \mid (a – b) \).
Recordatorio. \( a \mid b \) (se lee «\( a \) divide a \( b \)») significa que la división \( \frac{b}{a} \) da un número entero exacto, sin residuo. Por ejemplo: \( 4 \mid 12 \) porque \( \frac{12}{4} = 3 \in \mathbb{Z} \), pero \( 4 \nmid 10 \) porque \( \frac{10}{4} = 2.5 \notin \mathbb{Z} \).
En palabras simples: Dos enteros son congruentes módulo \( m \) cuando dejan el mismo residuo al dividirse cada uno por separado entre \( m \).
¿Qué significa «mismo residuo»? Al dividir cada número entre \( m \), usamos la fórmula \( a = mq + r \) (donde \( 0 \leq r < m \)). Si dos números dan el mismo \( r \), son congruentes. Por ejemplo, con \( m = 4 \):
| Número | División | Cociente (\( q \)) | Residuo (\( r \)) |
|---|---|---|---|
| 11 | \( 11 = 4 \cdot 2 + 3 \) | 2 | 3 |
| 3 | \( 3 = 4 \cdot 0 + 3 \) | 0 | 3 |
Ambos dejan residuo 3, por lo tanto \( 11 \equiv 3 \pmod{4} \). Y su diferencia \( 11 – 3 = 8 \) es divisible por 4 (\( 4 \mid 8 \)) — ambas formas son equivalentes.
a) Demostrar que la congruencia módulo \( m \) es una relación de equivalencia.
Solución:
- Reflexiva: \( a – a = 0 \) y \( m \mid 0 \) (porque \( 0 = 0 \cdot m \)) ✓
- Simétrica: Si \( m \mid (a – b) \), entonces \( a – b = km \) para algún entero \( k \). Luego \( b – a = (-k)m \), así que \( m \mid (b – a) \) ✓
- Transitiva: Si \( m \mid (a – b) \) y \( m \mid (b – c) \), entonces \( a – b = km \) y \( b – c = lm \). Sumando: \( a – c = (k + l)m \), así que \( m \mid (a – c) \) ✓
Por tanto, la congruencia módulo \( m \) es una relación de equivalencia. ∎
b) Determinar las clases de equivalencia y el conjunto cociente para \( m = 4 \).
Solución: Hay exactamente 4 residuos posibles (0, 1, 2, 3), así que hay 4 clases:
\[ [0]_4 = \{\ldots, -8, -4, 0, 4, 8, \ldots\} \] \[ [1]_4 = \{\ldots, -7, -3, 1, 5, 9, \ldots\} \] \[ [2]_4 = \{\ldots, -6, -2, 2, 6, 10, \ldots\} \] \[ [3]_4 = \{\ldots, -5, -1, 3, 7, 11, \ldots\} \]
El conjunto cociente es \( \mathbb{Z}/ \negthinspace \sim \ = \{[0]_4, [1]_4, [2]_4, [3]_4\} \) — el conjunto infinito \( \mathbb{Z} \) queda comprimido en solo 4 clases.
Estas clases forman una partición de \( \mathbb{Z} \):
- P₁: Cada clase tiene infinitos elementos ✓
- P₂: Las clases son disjuntas (ningún entero tiene dos residuos distintos al dividir entre 4) ✓
- P₃: Todo entero tiene un residuo al dividir entre 4, así que pertenece a alguna clase ✓
Generalización. Para cualquier módulo \( m \), la congruencia módulo \( m \) produce exactamente \( m \) clases de equivalencia: \( [0]_m, [1]_m, \ldots, [m-1]_m \). El ejemplo de la paridad (ejemplo 3 de la publicación) es un caso particular con \( m = 2 \).
Ejercicio 2: conjunto cociente módulo 5
La congruencia módulo 5 sobre \( \mathbb{Z} \) (definida por \( a \sim b \) si \( 5 \mid (a – b) \)) es una relación de equivalencia (la demostración es análoga al ejercicio 1).
Determinar las clases de equivalencia y el conjunto cociente.
Solución: Hay exactamente 5 residuos posibles (0, 1, 2, 3, 4), así que hay 5 clases:
\[ [0]_5 = \{\ldots, -10, -5, 0, 5, 10, \ldots\} \] \[ [1]_5 = \{\ldots, -9, -4, 1, 6, 11, \ldots\} \] \[ [2]_5 = \{\ldots, -8, -3, 2, 7, 12, \ldots\} \] \[ [3]_5 = \{\ldots, -7, -2, 3, 8, 13, \ldots\} \] \[ [4]_5 = \{\ldots, -6, -1, 4, 9, 14, \ldots\} \]
El conjunto cociente es \( \mathbb{Z}/ \negthinspace \sim \ = \{[0]_5, [1]_5, [2]_5, [3]_5, [4]_5\} \) — el conjunto infinito \( \mathbb{Z} \) queda comprimido en solo 5 clases.
Conexión con la aritmética modular. El conjunto cociente \( \mathbb{Z}/ \negthinspace \sim \) es la base de la aritmética modular: las operaciones de suma y multiplicación se pueden realizar entre clases, y el resultado es independiente del representante elegido. Por ejemplo, en módulo 5: \( [3]_5 + [4]_5 = [7]_5 = [2]_5 \).
Ejercicio 3: construir una relación de equivalencia a partir de una partición
Dada la partición \( \{\{1, 3, 5\},\ \{2, 4, 6\}\} \) del conjunto \( S = \{1, 2, 3, 4, 5, 6\} \), construir la relación de equivalencia inducida y verificar que es de equivalencia.
Solución: Según el Teorema Fundamental (dirección b), dos elementos están relacionados si pertenecen al mismo bloque. Los bloques son:
- \( B_1 = \{1, 3, 5\} \) — los impares
- \( B_2 = \{2, 4, 6\} \) — los pares
Construimos todos los pares ordenados dentro de cada bloque:
- De \( B_1 \): \( (1,1), (1,3), (1,5), (3,1), (3,3), (3,5), (5,1), (5,3), (5,5) \) — 9 pares
- De \( B_2 \): \( (2,2), (2,4), (2,6), (4,2), (4,4), (4,6), (6,2), (6,4), (6,6) \) — 9 pares
Total: \( 3^2 + 3^2 = 18 \) pares.
Verificamos:
- Reflexiva: \( (1,1), (2,2), (3,3), (4,4), (5,5), (6,6) \in R \) ✓
- Simétrica: Por cada \( (a,b) \) en un bloque, \( (b,a) \) también está (ambos pertenecen al mismo bloque) ✓
- Transitiva: Si \( (a,b) \) y \( (b,c) \) están en \( R \), los tres están en el mismo bloque, así que \( (a,c) \in R \) ✓
Es una relación de equivalencia. El conjunto cociente es \( S/ \negthinspace \sim \ = \{[1],\ [2]\} = \{\{1, 3, 5\},\ \{2, 4, 6\}\} \), que coincide con la partición original. ∎
Resumen del capítulo
Partimos de la relación de equivalencia — una relación reflexiva, simétrica y transitiva — y descubrimos las estructuras que genera. A lo largo de esta publicación:
- Recordamos la definición de relación de equivalencia y analizamos qué ocurre cuando falta alguna propiedad
- Estudiamos 6 ejemplos detallados, incluyendo la paridad, relaciones geométricas y un contraejemplo
- Definimos las clases de equivalencia \( [a] \) y demostramos sus 3 propiedades fundamentales: pertenencia, identidad de clases y disyunción
- Construimos el conjunto cociente \( A/!\sim \) como la colección de todas las clases distintas
- Definimos las particiones y sus 3 condiciones (no vacuidad, disyunción, cobertura)
- Demostramos el Teorema Fundamental: las relaciones de equivalencia y las particiones son dos caras de la misma moneda
- Exploramos las aplicaciones en computación, matemáticas, inteligencia artificial, ingeniería y vida cotidiana
- Resolvimos ejercicios sobre congruencia módulo \( m \) y conjunto cociente
Con estas herramientas, entendemos cómo las relaciones de equivalencia organizan cualquier conjunto en bloques perfectamente disjuntos, y cómo cualquier división en bloques genera una equivalencia.
¿Qué viene próximamente?
Con las relaciones de equivalencia y particiones dominadas, estamos listos para abordar los siguientes temas en las próximas publicaciones:
- Correspondencia matemática — Desarrollaremos en detalle las cuatro condiciones (existencia/unicidad de imagen y origen), con ejemplos completos y diagramas sagitales para cada tipo de correspondencia.
- Funciones — Estudiaremos la función como un tipo especial de correspondencia, con su clasificación completa (inyectiva, sobreyectiva, biyectiva), composición, inversas y sus aplicaciones.
¡Nos vemos en la siguiente publicación!