Archivo de la etiqueta: relaciones de equivalencia

Teoría de los Conjuntos I: Relaciones de equivalencias

Introducción

En esta entrada hablaremos acerca de un tipo de relaciones a las que llamaremos relaciones de equivalencia. Trataremos ejemplos que son relaciones de equivalencia así como ejemplos que no lo son.

Sobre el concepto

Definición: Sea $R$ una relación en $A$. Decimos que $R$ es una relación de equivalencia si se satisfacen las siguientes condiciones:

  1. Para cualquier $a\in A$, $(a,a)\in R$ (reflexiva),
  2. Si $(a,b)\in R$, entonces $(b,a)\in R$ (simetría),
  3. Si $(a,b)\in R$ y $(b,c)\in R$, entonces $(a,c)\in R$ (transitiva).

Una forma de recordar las propiedades que caracterizan a la definición de relación de equivalencia es pensar en lo siguiente:

  1. Cualquier persona es amiga de si misma (reflexividad),
  2. Si Juan es amigo de Pedro, entonces Pedro es amigo de Juan (simetría),
  3. Si Ana es amiga de Luis y Luis es amigo de Adrián, entonces Ana es amiga de Adrián (transitividad).

Algunos ejemplos

Ejemplo:

Sea $A=\set{a,b}$. $R=\set{(a,a), (b,b), (a,b), (b,a)}$ es relación de equivalencia. En efecto, podemos verificar que $R$ es una relación en $A$ y se verifican las propiedades:

  1. Reflexivilidad:
    Sea $x\in A$, entonces $x=a$ o $x=b$. Luego, como $(a,a)\in R$ y $(b,b)\in R$ se cumple que $R$ es una relación reflexiva.
  2. Simetría:
    Dado que nuestra relación es un conjunto pequeño podemos evaluar que pasa con cada uno de sus elementos:
    -Si $(a,a)\in R$, entonces $(a,a)\in R$ es verdadero,
    -Si $(b,b)\in R$, entonces $(b,b)\in R$ es verdadero,
    -Si $(a,b)\in R$, entonces $(b,a)\in R$ es verdadero,
    -Si $(b,a)\in R$, entonces $(a,b)\in R$ es verdadero.
    Por lo tanto, $R$ es simetrica.
  3. Transitividad:
    Dado que si $(a,b)\in R$ y $(b,a)\in R$ entonces $(a,a)\in R$ se cumple. Del mismo modo se cumple que si $(b,a)\in R$ y $(a,b)\in R$, entonces $(b,b)\in R$.
    Por lo tanto, $R$ es transitiva.

$\square$

Ejemplo:

Sea $X=\emptyset$, la relación vacía es relación de equivalencia. En efecto, podemos verificar las propiedades:

  1. Reflexividad:
    Sea $x\in X$, entonces $(x,x)\in \emptyset$ es verdadero, pues $x\in X=\emptyset$ es falso y la reflexividad se verifica por vacuidad.
  2. Simetría:
    Sea $(x,y)\in \emptyset$, entonces $(y,x)\in \emptyset$ por vacuidad.
  3. Transitividad:
    Sean $(x,y)\in \emptyset$ y $(y,z)\in\emptyset$, entonces $(x,y)\in \emptyset$ por vacuidad.

Por lo tanto, $\emptyset$ es relación de equivalencia en $X=\emptyset$.

$\square$

Relaciones casi de equivalencia

La definición de relación de equivalencia nos pide verificar tres propiedades: reflexividad, simetría y transitividad. Si alguna relación verifica alguna de ellas pero no todas, entonces no será de equivalencia. Veamos los siguientes ejemplos:

Ejemplo: (Simétrica y transitiva pero no reflexiva)

Sea $X$ un conjunto no vacío, la relación vacía en $X$ no es relación de equivalencia. En efecto, podemos verificar que $\emptyset$ es simétrica y transitiva por un argumento por vacuidad, pero $\emptyset$ no es una relación reflexiva.

Dado que si $x\in X$ arbitrario, entonces $(x,x)\in \emptyset$ es falso, pues la relación vacía no tiene elementos, concluimos que $\emptyset$ no es reflexiva.

$\square$

Ejemplo: (Reflexiva, simétrica pero no transitiva)

Sea $X=\set{a,b,c}$ y sea $R=\set{(a,a), (b,b), (c,c), (a,b), (b,a), (a,c), (c,a)}$. Tenemos que $R$ no es relación de equivalencia, pues aunque es reflexiva y simétrica no es transitiva.

$R$ no es una relación transitiva pues $(c,a)\in R$ y $(a,b)\in R$, pero $(c,b)\notin R$.

$\square$

Ejemplo: (Reflexiva, transitiva pero no simétrica)

Sea $X=\set{a,b,c}$ y sea $R=\set{(a,a), (b,b), (c,c), (a,b)}$. Tenemos que $R$ no es relación de equivalencia, pues aunque es reflexiva y transitiva no es simétrica.

$R$ no es una relación transitiva pues $(c,a)\in R$ y $(a,b)\in R$, pero $(c,b)\notin R$.

$\square$

Resultados

Teorema: Sean $R_1$ y $R_2$ relaciones de equivalencia en $A$. Demuestra que $R_1\cap R_2$ es relación de equivalencia.

Demostración:

Supongamos que $R_1$ y $R_2$ son relaciones de equivalencia en $A$. Veamos que $R_1\cap R_2$ es una relación de equivalencia en $A$, para ello debemos verificar que $R_1\cap R_2$ es reflexiva, simétrica y transitiva.

Afirmación 1: $R_1\cap R_2$ es reflexiva.

Sea $a\in A$, veamos que $(a,a)\in R_1\cap R_2$.
Como $a\in A$ y $R_1$ es relación de equivalencia en $A$, entonces en particular es reflexiva, de modo que $(a,a)\in R_1$.

Luego, como $a\in A$ y $R_2$ es reflexiva por ser relación de equivalencia se cumple que $(a,a)\in R_2$. Por lo tanto, $(a,a)\in R_1$ y $(a,a)\in R_2$, esto es $(a,a)\in R_1\cap R_2$.

Por lo tanto, $R_1\cap R_2$ es reflexiva.

Afirmación 2: $R_1\cap R_2$ es simétrica.

Sea $(a,b)\in R_1\cap R_2$, veamos que $(b,a)\in R_1\cap R_2$.

Como $(a,b)\in R_1\cap R_2$, entonces $(a,b)\in R_1$ y $(a,b)\in R_2$. Luego, $(b,a)\in R_1$ y $(b,a)\in R_2$ por ser $R_1$ y $R_2$ relaciones simétricas respectivamente. Por lo tanto, $(b,a)\in R_1\cap R_2$.

Por lo tanto, $R_1\cap R_2$ es simétrica.

Afirmación 3: $R_1\cap R_2$ es transitiva.

Sean $(a,b), (b,c)\in R_1\cap R_2$, veamos que $(a,c)\in R_1\cap R_2$.

Como $(a,b)\in R_1\cap R_2$, entonces $(a,b)\in R_1$ y $(a,b)\in R_2$. Luego, como $(b,c)\in R_1\cap R_2$ entonces $(b,c)\in R_1$ y $(b,c)\in R_2$.

Así, $(a,b)\in R_1$ y $(b,c)\in R_1$ y por la transitividad de $R_1$ se sigue que $(a,c)\in R_1$.

De forma similar, como $(a,b)\in R_2$ y $(b,c)\in R_2$ se sigue que $(a,c)\in R_2$ por transitividad de $R_2$.

De los argumentos anteriores se tiene que $(a,c)\in R_1\cap R_2$.

Por lo tanto, $R_1\cap R_2$ es transitiva.

Por lo tanto, $R_1\cap R_2$ es relación de equivalencia en $A$.

$\square$

Proposición: Demuestra que si $R$ es una relación sobre un conjunto $X$, cumple con las siguientes propiedades:

  1. $(x,x)\in R$ para todo $x\in X$,
  2. Si $(x,y)\in R$ y $(y,z)\in R$, entonces $(z,x)\in R$.

Entonces $R$ es relación de equivalencia.

Demostración:

Supongamos que $R$ es una relación tal que $(x,x)\in R$ para todo $x\in X$ y si $(x,y)\in R$ y $(y,z)\in R$, entonces $(z,x)\in R$. Veamos que $R$ es relación de equivalencia.

Tenemos que $R$ es reflexiva pues por hipótesis $(x,x)\in R$ para todo $x\in X$. Luego, si $(x,y)\in R$, veamos que $(y,x)\in R$ para probar que $R$ es simétrica. Dado que $(x,y)\in R$ entonces $x,y\in X$ y por reflexividad $(y,y)\in R$. Así, por hipótesis tenemos que $(y,x)\in R$.

Ahora veamos que $R$ es transitiva. Supongamos que $(x,y)\in R$ y $(y,z)\in R$ y mostremos que $(x,z)\in R$. Como $(x,y)\in R$ y $(y,z)\in R$, entonces $(z,x)\in R$ y por simetría de $R$ se tiene que $(x,z)\in R$.

$\square$

Tarea moral

La siguiente lista de ejercicios te será útil para verificar por tu cuenta que ciertas relaciones son de equivalencia:

  1. Demuestra que $Id_A$ es una relación de equivalencia para $A$ un conjunto cualquiera.
  2. Sea $X=\set{a,b,c}$ y sea $R=\set{(a,a), (b,b), (c,c), (a,b), (b,a), (a,c), (c,a)}$. Demuestra que $R$ es reflexiva y simétrica.
  3. Sea $X=\set{a,b,c}$ y sea $R=\set{(a,a), (b,b), (c,c), (a,b)}$. Demuestra que $R$ es reflexiva y simétrica.
  4. Construye $R$ una relación tal que $R$ sea reflexiva pero no sea ni simétrica ni transitiva.

Más adelante

En la siguiente sección seguiremos tratando a las relaciones de equivalencia, esta vez hablaremos acerca de sus elementos y como podemos estudiarlos según estén relacionados con otros elementos. Definiremos a un nuevo conjunto llamado clase de equivalencia en el que se encontraran aquellos elementos que estén relacionados con un mismo elemento.

Enlaces

Puedes consultar más contenido de relaciones de equivalencia en el siguiente enlace:

Álgebra Superior I: Relaciones de equivalencia y clases de equivalencia

Álgebra Superior I: Relaciones de equivalencia y clases de equivalencia

Introducción

Siguiendo la revisión de algunas relaciones de un conjunto en sí mismo, ahora vamos a hablar de un tipo especial de relaciones, que se llamarán de equivalencia. Este es un concepto que aparece frecuentemente en las matemáticas y es un tipo de relación que permite «agrupar» distintos elementos de un conjunto según alguna propiedad que tengan.

Relación de equivalencia

La relación que veremos en esta entrada es la de equivalencia. Para entender propiedades de este tipo de relaciones, consideremos al conjunto de todas las personas $X$ y la relación $\sim$ como:$$\sim = \{(x,y) \in X^2:x\text{ tiene el mismo cumpleaños que }y\}.$$ Y como es costumbre, escribiremos $x \sim y$ si $(x,y) \in \sim$. Esta relación será de equivalencia, y antes de definirla, vamos a hacer algunas observaciones de ella.

Observa que este tipo de relación nos permite «agrupar» a las personas según su cumpleaños, pues al haber $365$ días en el año, cada persona $x$ tendrá su cumpleaños en alguno de esos días. Nota que podríamos hablar de «el subconjunto» de $X$ formado de las personas las cuales cumplen años el $14$ de febrero, y esto lo haríamos con ayuda de la relación $\sim$, pues considerando alguna persona $x$ que cumpla años ese día, podríamos considerar a todas las personas $y$ tales que $x \sim y$. Y todas las personas que estén relacionadas con $x$, serán las que tienen su cumpleaños ese día. Retomaremos esta idea de las «agrupaciones» más adelante, lo importante ahora es que veas que este tipo de relaciones (aún no hemos dicho qué significa que sea de equivalencia o porqué esta es una relación de equivalencia) nos permiten «agrupar» elementos de un conjunto según los elementos que se relacionan entre sí.

Ahora, veamos algunas propiedades que tiene esta relación que la hará de equivalencia:

  • $\sim$ es reflexiva. Nota que toda persona $x$ cumple el mismo día años que la persona $x$. Esto es porque estamos hablando de la misma persona.
  • $\sim$ es simétrica. Considera dos personas $x,y$ relacionadas ($x \sim y$). Entonces es cierto que $x$ tiene el mismo cumpleaños que $y$. Pero también es cierto que $y$ tiene el mismo cumpleaños que $x$, de esta manera $y \sim x$.
  • $\sim$ es transitiva. Ahora supón que $x \sim y$ y que $y \sim z$. Entonces es cierto que $x$ y $y$ comparten cumpleaños, pero como $y \sim z$ entonces $z$ tiene el mismo cumpleaños que $y$ y esto solo puede significar que $x$ tiene el mismo cumpleaños que $z$, pues no puede suceder que $y$ tenga dos cumpleaños distintos.

Estas son las propiedades que decimos que cumple una relación de equivalencia.

Definición. Sea $X$ un conjuntos y $\sim$ una relación de $X$ en sí mismo. Diremos que $\sim$ es una relación de equivalencia si $\sim$ es reflexiva, simétrica y transitiva.

Este es un concepto que se aparecerá muchas veces en distintas áreas de las matemáticas, veamos a continuación algunos ejemplos de relaciones de equivalencia, no importa que ahora no sepas muy bien qué son estos conceptos, lo importante es que veas que aparecen en distintas áreas de las matemáticas:

  1. En $\mathbb{R}$, la relación $x \sim y \Leftrightarrow |x|=|y|$ es de equivalencia.
  2. Si $X=\{a,b,c\}$ y $\sim=\{(a,a),(b,b),(a,b),(b,a),(c,c)\}$, entonces $\sim$ es una relación de equivalencia.
  3. En el espacio de matrices reales $M_{2\times 2}(\mathbb{R})$, la siguiente es una relación de equivalencia: $A \sim B \Leftrightarrow \exists \lambda \in \mathbb{R}, \lambda \neq 0(A = \lambda B)$
  4. En espacios topológicos, la relación $X \sim Y \Leftrightarrow X \text{ es homeomorfo a } Y$ es una relación de equivalencia.
  5. La congruencia entre triángulos, es una relación de equivalencia.
  6. Diremos que un número entero $x$ es congruente con $y$ módulo $n$ si el residuo de dividir $x$ entre $n$ es el mismo que el residuo de dividir $y$ entre $n$ y lo escribiremos como $x \equiv_n y$. $\equiv_n$ es una relación de equivalencia.

Algunos ejemplos de relaciones que no son de equivalencia:

  1. La relación «ser menor o igual» en números enteros $\leq$ no es de equivalencia.
  2. La relación «ser padre/madre de» no es una relación de equivalencia.
  3. Si $X=\{a,b,c\}$ y $\sim=\{(a,a),(a,b),(b,a),(c,c)\}$, entonces $\sim$ no es de equivalencia.

Clases de equivalencia

Volvamos al ejemplo de la relación $\sim$ «tener el mismo cumpleaños». Ahora veremos porqué desde el principio hemos dicho que las relaciones de equivalencias nos ayudan a «agrupar» elementos de un conjunto de acuerdo a los elementos que se relacionan con él. Considera de nuevo el ejemplo de las personas que cumplen años el $14$ de febrero. La relación $\sim$ nos ayuda a encontrar a todas las personas que cumplen años ese día. Pues solo tendríamos que considerar una persona que cumpla años ese día y enseguida encontrar todas las personas que se relacionan con esta persona. Claramente este grupo, será distinto al grupo de personas que cumple años el $17$ de Junio, y a su vez estos do serán distintos al grupo de personas que cumplen el $10$ de Enero. En total podríamos «partir» el conjunto de personas $X$ en $365$ grupos de acuerdo al día en que cumplen años.

Si partimos de una persona $x$, entonces podemos considerar el conjunto $$[x]_{\sim}=\{y \in X: x \sim y\}.$$ Este conjunto representa a todas las personas que tienen el mismo cumpleaños que $x$, y recordando lo que dijimos en el párrafo anterior, si $x$ cumple el $14$ de febrero, entonces $[x]_{\sim}$ es el conjunto de personas que cumplen años ese día. Pues con esto en mente, hemos llegado al siguiente concepto: clase de equivalencia.

Definición. Sea $\sim$ una relación de equivalencia en $X$ y $x \in X$. La clase de equivalencia de $x$ es: $$[x]_{\sim}=\{y \in X: x \sim y\}.$$

Algunas veces cuando estemos hablando de una relación de equivalencia $\sim$ y no haya ambigüedad en qué relación de equivalencia estemos hablando, es común únicamente escribir $[x]$ para la clase de equivalencia del elemento $x$ en lugar de escribir $[x]_\sim$.

Veamos a continuación algunas propiedades que tienen estas clases de equivalencia que nos permiten asegurar que «parten» un conjunto agrupando sus elementos en distintos subconjuntos.

Proposición. Sea $\sim$ una relación de equivalencia en $X$ y $x,y \in X$. Son equivalentes:

  1. $x \sim y$
  2. $[x]=[y]$
  3. $[x] \cap [y] \neq \emptyset$

Demostración.

$(1) \Rightarrow (2)$ Para demostrar la igualdad entre conjuntos, demostraremos que cada clase equivalencia está contenida en la otra.

$\subset )$ Sea $w \in [x]$. Por definición del conjunto, $w \sim x$ y por hipótesis, $x \sim y$. Ahora, como $\sim$ es de equivalencia, entonces $w \sim y$. De esta forma, $w \in [y]$.

$\supset )$ De manera análoga a la contención anterior, si $w \in [y]$ entonces $w \sim y \land w \sim x$ de manera que $w \in [x]$.

$(2) \Rightarrow (3)$. Notemos que si $[x]=[y]$ entonces $[x] \cap [y]=[x]$ y $x \in [x]$, de esta manera, la intersección no es vacía.

$(3) \Rightarrow (1)$. Como $[x] \cap [y] \neq \emptyset$ entonces existe un elemento $w \in [x] \cap [y]$. De esta forma $x \sim w \land y \sim w$. Como $\sim$ es una relación de equivalencia, entonces $x \sim y$.

$\square$

Corolario. Sea $\sim$ una relación de equivalencia en $X$ y $x,y \in X$. Entonces $[x]=[y] \lor [x] \cap [y] = \emptyset.$

Demostración. Sean $x,y$ dos elementos de $X$. Entonces tenemos dos casos para $x,y$.

Caso 1) $x \sim y$. En este caso, por la proposición anterior, $[x]=[y]$.

Caso 2) $x \not \sim y$. Notemos que en este caso $[x]\cap [y]= \emptyset$, pues si no fuera cierto, la intersección no sería vacía y por la proposición anterior, esto significaría que $x \sim y$, contradiciendo la hipótesis de este caso.

$\square$

Particiones

El siguiente concepto nos permite hablar de «partir» un conjunto en distintos subconjuntos. En términos simples, una partición será una forma de dividir un conjunto en subconjuntos que no comparten elementos en común entre sí. Por ejemplo, considera a los números enteros. Podemos dividir el conjunto en dos particiones: el de los número pares y el de los impares. Denotemos al conjunto de los números pares como $P$ y al de los impares como $I$ entonces:

  • $P \cap I=\emptyset$
  • $P \cup I = \mathbb{Z}$

Entonces podemos observar algunos puntos para definir qué es una partición:

  • Cada uno de los subconjuntos que forman la partición son no vacíos. Nota que tanto $P$ como $I$ tienen al menos un elemento.
  • La intersección entre cada una de los subconjuntos de la partición es vacía. Esto significa que las particiones no comparten elementos, en el ejemplo, es claro que ningún número par es impar y viceversa.
  • La unión de los subconjuntos de la partición forman de nuevo el conjunto. Esto significa que todo elemento del conjunto pertenece a una única partición, en nuestro ejemplo esto significa que cualquier número entero es impar o es par, no ambos al mismo tiempo.

Estas son las tres propiedades que pediremos para definir una partición.

Definición. Sea $X$ un conjunto y $F = \{X_i\}_{i \in \mathcal{F}}$ una colección de subconjuntos, entonces diremos que $F$ es una partición de $X$ si:

  • Para cada $X_i \in F, X_i \neq \emptyset$.
  • Para $X_i,X_j \in F$ dos subconjuntos distintos, $X_i \cap X_j = \emptyset$.
  • $\bigcup F = X$

Resulta que esta definición no es al azar, pues cada relación de equivalencia induce una partición.

Proposición. Sea $\sim$ una relación de equivalencia sobre un conjunto $X$. Entonces las distintas clases de equivalencia forman una partición.

Demostración. Denotemos a $P$ como el conjunto de todas las clases de equivalencia de $X$, es decir $$P = \{[x]: x \in X\}$$. Ahora demostraremos que $P$ es una partición. Para ello, notemos que:

  1. Cada elemento de la partición $P$ es distinta al vacío. Observemos que si $[x] \in P$ entonces existe al menos un elemento en esa clase de equivalencia, de manera explícita, $x \in [x]$.
  2. Si $[x], [y] \in P$ son dos clases distintas, entonces $[x] \cap [y]$ es vacía. Este punto sale directamente del corolario demostrado anteriormente, pues $[x]=[y]$ o $[x] \cap [y]=\emptyset$.
  3. $\bigcup P = X$. De manera clara sucede que $\bigcup P \subset X$, pues cada elemento de $P$ es un subconjunto de $X$, y la unión de subconjuntos de un conjunto siempre está contenida en el conjunto. Para demostrar que $X \subset \bigcup P$, notemos que si $x \in X$, entonces $x \in [x]$ y $[x] \in P$, de esta manera, $x \in \bigcup P$.

De esta manera, $P$ es una partición.

$\square$

Este concepto de relaciones de equivalencia aparece muy seguido en distintas ramas de las matemáticas, será importante conforme avances en tu carrera del área matemática, pues muchas veces será útil ver que algunas relaciones son de equivalencias de manera en que sabremos que son particiones y podremos ver el conjunto en sus distintas partes de acuerdo a la relación.

Tarea moral

  1. Demuestra que la relación «ser igual a» $=$ en $\mathbb{Z}^2$ es una relación de equivalencia.
  2. Demuestre que la relación «ser menor o igual» en números enteros no es una relación de equivalencia.
  3. Demuestra que cualquier orden parcial no es una relación de equivalencia.
  4. Demuestra que si $x \in [y]_{\sim} \Leftrightarrow [x]_{\sim}=[y]_{\sim}$.

Más adelante…

En la siguiente entrada volveremos a hablar de relaciones entre conjuntos que en un inicio, no deben ser el mismo. Y el siguiente tipo de relación será fundamental, pues es el concepto de función entre dos conjuntos. No solo aparecerá aquí, sino que es una base para hablar en otras materias como en cálculo, geometría, entre otras.

Entradas relacionadas