Archivo de la etiqueta: partición

Teoría de los Conjuntos I: Conjunto cociente

Por Gabriela Hernández Aguilar

Introducción

En esta entrada definiremos al conjunto cociente, dicho conjunto tendrá como elementos a las clases de equivalencia de una relación. Además probaremos que toda relación de equivalencia induce una partición y viceversa.

Concepto

Definición: Sea $R$ una relación de equivalencia en $A$, definimos al conjunto cociente por la relación $R$ como el conjunto:

$R\diagup A=\set{[a]_R: a\in A}$.

Ejemplo:

Sea $A=\set{1,2,3,4}$ y $R$ la relación identidad en $A$. Sabemos que $R$ es de equivalencia en $A$. Luego, siguiendo la definición de conjunto cociente tenemos que $R\diagup A=\set{[1]_R, [2]_R, [3]_R, [4]_R}$, donde $[1]_R=\set{1}$, $[2]_R=\set{2}$, $[3]_R=\set{3}$, $[4]_R=\set{4}$.

$\square$

Ejemplo:

Sea $A=\set{1,2,3,4}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (1,4), (4,1)}$ una relación de equivalencia en $A$. Luego, tenemos que

$R\diagup A=\set{[1]_R, [2]_R, [3]_R, [4]_R}$,

donde

  • $[1]_R=\set{1,4}$,
  • $[2]_R=\set{2}$,
  • $[3]_R=\set{3}$,
  • $[4]_R=\set{4,1}$.

Por lo tanto, $R\diagup A=\set{[1]_R, [2]_R, [3]_R}$

$\square$

Cada relación de equivalencia induce una partición

Teorema: Sea $R$ una relación de equivalencia en $A$, entonces el conjunto cociente $A\diagup R$ es una partición de $A$.

Demostración:

Supongamos que $R$ es una relación de equivalencia en $A$. Veamos que $A\diagup R$ es una partición de $A$.

  1. Sea $a\in A$, vimos en la entrada de particiones que $[a]_R\not=\emptyset$.
  2. Sean $[a]_R,[b]_R\in A\diagup R$ tales que $[a]_R\not=[b]_R$ y veamos que $[a]_R\cap [b]_R=\emptyset$. Supongamos que no ocurre que $[a]_R\cap [b]_R=\emptyset$, es decir, $[a]_R\cap [b]_R\not=\emptyset$ lo que es equivalente a que $[a]_R=[b]_R$
  3. Por último, $\bigcup_{a\in A} [a]_R= A$ pues para cada $a\in A$, $a\in [a]_R$.

$\square$

Este último teorema demuestra que toda relación de equivalencia induce una partición.

Las particiones inducen una relación de equivalencia

El teorema anterior nos permitió probar que cada relación de equivalencia induce una partición y de hecho, esta partición será el conjunto cociente, por lo que es válido preguntarnos si el resultado se cumple de regreso, es decir, dada una partición podemos inducir una relación de equivalencia. Veamos el siguiente ejemplo.

Ejemplo:

Sea $A=\set{0,1,2, 3, \cdots}$ y sean $A_1=\set{0,2,4,\cdots}$ y $A_2=\set{1,3, 5,\cdots}$. Resulta que $\mathcal{P}$ es una partición de $A$ pues tanto $A_1$ y $A_2$ son conjuntos no vacíos, además $A_1\cap A_2=\emptyset$ y $A_1\cup A_2=A$.

Queremos ver si existe la manera de relacionar a los elementos de $A$ tal que la relación que resulte sea de equivalencia. Consideremos la siguiente relación definida como sigue:

$R_\mathcal{P}=\set{(a,b)\in A^2: \exists A_i\in \mathcal{P}\ \text{tales que}\ a,b\in A_i}$.

Notemos que la relación $R_\mathcal{P}$ es una relación en $A$ y además relaciona a los elementos si pertenece a un mismo conjunto de la partición.

Veamos que $R_\mathcal{P}$ es una relación de equivalencia, para ello verifiquemos si es una relación reflexiva, simétrica y transitiva.

  1. Sea $a\in A$, si $a$ es un número par (existe $k$ tal que $a= 2k$), entonces $a\in A_1$ y por lo tanto, existe $A_1\in \mathcal{F}$ tal que $a\in A_1$ y así $(a,a)\in R_\mathcal{P}$.
    Si $a$ es un número impar (existe $k$ tal que $a= 2k+1$), entonces $a\in A_2$ y por lo tanto, existe $A_2\in \mathcal{P}$ tal que $a\in A_2$ y así $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a, b\in A_i$. Lo que es equivalente a decir que existe $A_i\in \mathcal{P}$ con $i\in\set{1,2}$ tal que $b,a\in A_i$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a, b\in A_i$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces existe $A_j\in \mathcal{P}$ con $j\in \set{1, 2}$ tal que $b,c\in A_j$. Luego $A_i=A_j$ pues de lo contrario $A_i\not= A_j$ y $b\in A_1$ al mismo tiempo que $b\in A_2$ y así, $b$ es par e impar, lo cuál no puede ocurrir. Por lo tanto, existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a,c\in A_i$ y así, $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia.

$\square$

Podemos demostrar que esto ocurre para cualquier conjunto y cualquier partición. Veamos el siguiente teorema.

Teorema: Toda partición induce una relación de equivalencia.

Demostración:

Sea $A$ un conjunto y $\mathcal{P}=\set{A_i:i\in I}$ una partición de $A$. Defimos a $R_\mathcal{E}$ como el siguiente conjunto:

$R_\mathcal{P}=\set{(a,b)\in A\times A: \exists A_i\in \mathcal{P}\ \text{tal que}\ a,b\in A_i}$.

Notemos que $R_\mathcal{P}$ es una relación en $A$ pues es un subconjunto de $A\times A$. Veamos que $R$ es de equivalencia, es decir, $R$ es reflexiva, simétrica y transitiva.

  1. Sea $a\in A$, dado que $\mathcal{P}$ es una partición de $A$, entonces $A=\bigcup_{i\in I}A_i$. Entonces existe $j\in I$ tal que $a\in A_j$, de donde $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ tal que $a, b\in A_i$. Lo que es equivalente a decir que existe $A_i\in \mathcal{P}$ tal que $b,a\in A_i$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ tal que $a, b\in A_i$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces existe $A_j\in \mathcal{P}$ tal que $b,c\in A_j$. Además $A_i=A_j$ pues de lo contrario, $A_i\not= A_j$ y $b\in A_i$ al mismo tiempo que $b\in A_j$ y así, $b\in A_i\cap A_j=\emptyset$ lo cual es una contradicción. Por lo tanto, existe $A_i\in \mathcal{P}$ tal que $a,c\in A_i$ y así, $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia en $A$.

$\square$

Con este último teorema hemos probado que en efecto, así como cada relación de equivalencia induce una partición, se cumple que cada partición induce una relación de equivalencia.

Tarea moral

La siguiente lista de ejercicios te ayudará a reforzar el contenido de esta entrada:

  • Demuestra que si $A$ es un conjunto y $R$ es una relación de equivalencia en $A$, entonces $A\diagup R$ es un conjunto.
  • Sea $A=\set{1,2,3,4,5,6}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (5,6), (6,5), (4,6), (6,4), (4,5), (5,4)}$ relación de equivalencia en $A$. Determina al conjunto cociente de $A$ respecto de $R$.

Más adelante

En la siguiente sección continuaremos con algunos teoremas del conjunto cociente, dichos teoremas involucraran funciones.

Enlaces

Más sobre relaciones de equivalencia y clases de equivalencia:

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