Recordatorio de clases de equivalencia

Contenido

Recordatorio de clases de equivalencia#

Introducción#

En este capítulo vamos a ver un repaso sobre clases de equivalencia. Empezaremos recordando lo que es una relación, pasaremos a definir qué es una relación de equivalencia y terminaremos viendo las clases de equivalencia y particiones.

Relaciones de equivalencia#

Los conceptos de producto cartesiano de conjuntos y de pareja ordenada permiten tratar en forma precisa el concepto de relación.

Definición 27 (Relación)

Sea \(A\) un conjunto. Una relación en \(A\) es un subconjunto \(\sim\) de \(A\times A\). A los elementos de este conjunto se les denota como las parejas \((a,b) \in \sim\) con \(a,b \in A\).
Si \(a\in A\) se relaciona con \(b\in A\), lo denotamos como \((a,b)\in \sim\). Para simplificar la notación, usaremos el símbolo \(\sim\) y así usualmente escribiremos \(a\sim b\) para denotar que \(a\) se relaciona con \(b\).

Ejemplo 70

Tomemos al conjunto \(A = \{ 2,3,4,5,6,8,9,10,12 \}\). Podemos pensar que un elemento \(a \in A\) está relacionado con otro \(b \in A\) si \(a|b\) y \(a<b\).

Es decir, \(2\) está relacionado con \(4\) ya que \(2|4\) y \(2<4\). Entonces tendríamos que la pareja ordenada \((2,4) \in R\), o diríamos que \(2\sim 4\).
Por lo tanto los elementos de la relación son,

\[R = \{ (2,4), (2,6), (2,8), (2,10), (2,12), (3,6), (3,9), (3,12), (4,8), (4,12), (5,10), (6,12) \}.\]

Definición 28 (Relación de equivalencia)

Una relación \(\sim\) en un conjunto \(A\) es de equivalencia si cumple lo siguiente:

Es reflexiva, es decir, para cualquier \(a \in A\) se tiene que \(a \sim a\).
Es simétrica, es decir, para cualesquiera \(a,b \in A\) se tiene que si \(a\sim b\), entonces \(b\sim a\).
Es transitiva, es decir, para cualesquiera \(a,b,c \in A\) se tiene que si \(a\sim b \) y \(b\sim c\), entonces \(a\sim c\).

Veamos algunos ejemplos de relaciones de equivalencia.

Ejemplo 71

Consideremos el conjunto \(\mathbb{Z}^+\). Vamos a dar la siguiente relación \(\sim\) en \(\mathbb{Z}^+\).

Sean \(a,b \in \mathbb{Z}^+\), diremos que \(a \sim b\) si \(\varphi(a) = \varphi(b)\), donde \(\varphi(n)\) es la función de Euler que vimos en la Definición 21.

Observemos algunos ejemplos.

\(7 \sim 9\), ya que \(\varphi(7) = 6 = \varphi(9)\).
\(5\sim 8\), ya que \(\varphi(5) = 4 = \varphi(8)\).

Veamos que la relación es reflexiva, simétrica y transitiva.

Reflexiva.

Sea \(a\in \mathbb{Z}^+\), esta propiedad se cumple directamente de la definición de la función de Euler. Ya que la función de Euler evaluada en el mismo valor da el mismo resultado, es decir, \(\varphi(a) = \varphi(a)\) y por lo tanto \(a\sim a\).

Simétrica.

Sean \(a,b\in \mathbb{Z}^+\). Supongamos que \(a\sim b\), es decir, \(\varphi(a) = \varphi(b)\). Lo anterior quiere decir que \(a\) tienen la misma cantidad de números menores que \(a\) y primos relativos a \(a\) que \(b\). Entonces \(b\) tiene la misma cantidad de números menores que \(b\) y primos relativos a \(b\), es decir que \(\varphi(b) = \varphi(a)\). Por lo tanto, \(b \sim a\).

Transitiva.

Sean \(a,b,c\in \mathbb{Z}^+\). Supongamos que \(a\sim b\) y que \(b\sim c\). Entonces tenemos que,

\[\varphi(a) = \varphi(b) \quad \text{ y } \quad \varphi(b) = \varphi(c).\]

De lo anterior tenemos que \(\varphi(a) = \varphi(c)\). Por lo tanto si \(a\sim b\) y \(b\sim c\), entonces \(a\sim c\).

Ejemplo 72

Consideremos la familia \(A\) de triángulos del plano. Vamos a dar una relación \(\sim\) en \(A\).
Sean \(\bigtriangleup ABC,\bigtriangleup DEF \in A\), diremos que \(\bigtriangleup ABC \sim \bigtriangleup DEF\) si \(\bigtriangleup ABC\) y \(\bigtriangleup DEF\) son triángulos semejantes, es decir, si los ángulos correspondientes son iguales.

Veamos que la relación es reflexiva, simétrica y transitiva.

Reflexiva.

Esta propiedad se sigue directamente de la definición de semejanza de triángulos, ya que si tomamos un triángulo cualquiera \(\bigtriangleup ABC \in A\) tiene los ángulos correspondientes iguales con él mismo. Entonces se cumple que \(\bigtriangleup ABC \sim \bigtriangleup ABC\).

Simétrica.

Supongamos que tenemos que \(\bigtriangleup ABC \sim \bigtriangleup DEF\). Es decir, que el triángulo \(\bigtriangleup ABC\) es semejante con el triángulo \(\bigtriangleup DEF\). Esto quiere decir que los ángulos correspondientes del triángulo \(\bigtriangleup ABC\) son iguales a los ángulos del triángulo \(\bigtriangleup DEF\). Luego, podemos decir que los ángulos correspondientes del triángulo \(\bigtriangleup DEF\) son iguales a los ángulos del triángulo \(\bigtriangleup ABC\). Entonces se cumple que \(\bigtriangleup DEF \sim \bigtriangleup ABC\).

Transitiva.

Supongamos que tenemos que \(\bigtriangleup ABC \sim \bigtriangleup DEF\) y \(\bigtriangleup DEF \sim \bigtriangleup XYZ\). Es decir, que el triángulo \(\bigtriangleup ABC\) es semejante al triángulo \(\bigtriangleup DEF\) y que el triángulo \(\bigtriangleup DEF\) es semejante al triángulo \(\bigtriangleup XYZ\). Entonces los ángulos correspondientes de los triángulos \(\bigtriangleup ABC\) y \(\bigtriangleup DEF\) son iguales, y los ángulos correspondientes de los triángulos \(\bigtriangleup DEF\) y \(\bigtriangleup XYZ\) también son iguales. De lo anterior se sigue que, los ángulos correspondientes de los triángulos \(\bigtriangleup ABC\) y \(\bigtriangleup XYZ\) son iguales. Por lo tanto, si \(\bigtriangleup ABC \sim \bigtriangleup DEF\) y \(\bigtriangleup DEF \sim \bigtriangleup XYZ\), se cumple que \(\bigtriangleup ABC \sim \bigtriangleup XYZ\).

Ejemplo 73

Consideremos el conjunto A de las rectas en un plano cartesiano, sin tomar en cuenta a las rectas verticales. Estas tienen ecuación \(l_i = mx + b\) con \(m\) la pendiente y \(b\) la ordenada al origen. Vamos a dar una relación \(\sim\) en \(A\).
Sean \(l_1, l_2 \in A\), diremos que \(l_1 \sim l_2\) si las rectas \(l_1\) y \(l_2\) son paralelas, es decir que tienen la misma pendiente.

Veamos que la relación es reflexiva, simétrica y transitiva.

Reflexiva.

Esta propiedad se sigue directamente de la ecuación de la recta. Supongamos que tenemos \(l_1 = mx + b\) entonces una recta siempre es paralela a ella misma por tener la misma pendiente que sí misma y por lo tanto \(l_1 \sim l_1\).

Simétrica.

Supongamos que \(l_1 \sim l_2\), es decir que \(l_1 = mx + b_1\) y \(l_2 = mx + b_2\) tienen la misma pendiente. Entonces también se cumple que \(l_2\) tiene la misma pendiente que \(l_1\), es decir que \(l_2 \sim l_1\).

Transitiva.

Supongamos que \(l_1 \sim l_2\) y \(l_2 \sim l_3\). Entonces tenemos que \(l_1 = m_1x + b_1, l_2 = m_2x + b_2\) y \(l_3 =m_3x + b_3\). Luego como \(l_1 \sim l_2\) tenemos que \(m_1 = m_2\) y también como \(l_2 \sim l_3\) tenemos que \(m_2 = m_3\). Por lo tanto, se cumple que \(m_1 = m_3\), es decir que \(l_1\) y \(l_3\) tiene la misma pendiente y así se cumple que \(l_1 \sim l_3\).

Veamos las siguientes dos relaciones que se cumplen en los números enteros.

Ejemplo 74

Sea \(n\) un entero positivo. Sean \(a,b \in \mathbb{Z}\), diremos que \(a \overset{n}{\sim_1} b\), si al dividirse entre \(n\) dejan el mismo residuo.

Observemos algunos ejemplos.

Si \(n = 7\).
Si tomamos \(9\) y \(23\). Por el algoritmo de la división, tenemos que \(9 = 7 \cdot 1 + 2\) y \(23 = 7 \cdot 3 + 2\), entonces \(9 \overset{7}{\sim_1} 23\).
Tomando \(13\) y \(48\). Por el algoritmo de la división, tenemos que \(13 = 7\cdot 1 + 6\) y \(48 = 7\cdot 6 + 6\), entonces \(13\overset{7}{\sim_1} 48\).

Ahora, demostremos que \(\overset{n}{\sim_1}\) es una relación de equivalencia. Fijemos \(n\).

Reflexiva.

Para cualquier número entero \(a\), por el algoritmo de la división, al dividirse entre un entero \(n\) deja un residuo \(r\) tal que \(0 \le r < n\), es decir que \(a = nq + r\). Esto significa que \(a\) se relaciona con sí mismo en términos de residuos al dividirse entre \(n\). Por lo tanto, se cumple que \(a \overset{n}{\sim_1} a\).

Simétrica.

Si tenemos que \(a \overset{n}{\sim_1} b\). Por el algoritmo de la división tenemos que \(a = nq_1 + r\) y \(b = nq_2 + r\), entonces \(b\) deja el mismo residuo que \(a\) al ser dividido entre \(n\). Por lo tanto \(b \overset{n}{\sim_1} a\).

Transitiva.

Supongamos que \(a \overset{n}{\sim_1} b\) y \(b \overset{n}{\sim_1} c\). Luego, por el algoritmo de la división tenemos que

\[a = q_1n + r_1, \quad b = q_2n + r_2 \quad \text{y} \quad c = q_3n + r_3,\]

donde \(0 \le r_1,r_2,r_3 < n\). Entonces como \(a \overset{n}{\sim_1} b\) y \(b \overset{n}{\sim_1} c\), sucede que \(r_1 = r_2\) y también \(r_2 = r_3\). De lo anterior tenemos que \(r_1 = r_3\), entonces \(a\) y \(c\) dejan el mismo residuo al dividirse entre \(n\). Por lo tanto, si \(a \overset{n}{\sim_1} b\) y \(b \overset{n}{\sim_1} c\), entonces concluimos que \(a \overset{n}{\sim_1} c\). \(\square\)

Ejemplo 75

Sea \(n\) un entero positivo. Sean \(a,b \in \mathbb{Z}\), diremos que \(a \overset{n}{\sim_2} b\) si \(n|a-b\).

Veamos algunos ejemplos.

Si \(n = 5\).
Si tomamos \(20\) y \(5\), como \(5|(20 - 5) = 15\) entonces \(20 \overset{5}{\sim_2} 5\).
Tomando \(8\) y \(3\), como \(5|(8-3) = 5\) entonces \(8 \overset{5}{\sim_2} 3\).

Ahora, demostremos que \(\overset{n}{\sim_2}\) es una relación de equivalencia. Sea \(n > 0\).

Reflexiva.

Para cualquier entero \(a\) se tiene que \(a - a = 0\), entonces para cualquier entero \(n\) se cumple que \(n|(a-a)\). Por lo tanto \(a \overset{n}{\sim_2} a\).

Simétrica.

Si tenemos que \(a \overset{n}{\sim_2} b\), entonces \(n|(a - b)\). Esto quiere decir que existe un entero \(k\) tal que \(a - b = kn\). Luego, tenemos que \(b - a = -kn\) y como \(-k\) es un entero tendremos que \(n|(b - a)\). Por lo tanto se cumple que \(b \overset{n}{\sim_2} a\).

Transitiva.

Supongamos que \(a \overset{n}{\sim_2} b\) y \(b \overset{n}{\sim_2} c\), entonces tenemos que \(n|(a - b)\) y \(n| (b - c)\). Por el inciso \(4\) de la Proposición 2, \(n|(a - b) + (b - c) = (a - c)\). Por lo tanto, si \(a \overset{n}{\sim_2} b\) y \(b \overset{n}{\sim_2} c\), entonces se cumple que \(a \overset{n}{\sim_2} c\). \(\square\)

Vamos a demostrar que el Ejemplo 74 y el Ejemplo 75 son equivalentes.

Proposición 24

Sea \(n\) un entero positivo. Si \(a,b\in \mathbb{Z}\), entonces \(a \overset{n}{\sim_1} b\) si y sólo si \(a \overset{n}{\sim_2} b\).

Demostración. Para esta demostración tenemos que probar las dos implicaciones. Sea \(n >0\).

Primero demostremos que si los enteros \(a,b\) dejan el mismo residuo al dividirse entre \(n\), entonces \(n\) divide a \(a - b\).

Por hipótesis tenemos que \(a \overset{n}{\sim_1} b\), es decir que \(a\) y \(b\) dejan el mismo residuo al dividirse entre \(n\). Entonces por el algoritmo de la división, tenemos que existe \(0 \le r < n\) tal que

\[\begin{align*} a = q_1n + r, \\ & \\ b = q_2n + r. \end{align*}\]

Si restamos las ecuaciones obtenemos que

\[a - b = q_1n - q_2 n + r - r = (q_1 - q_2)n.\]

Como \(q_1 - q_2\) es un entero concluimos que \(n|(a - b)\), es decir que \(a \overset{n}{\sim_2} b\).

Ahora, demostremos que para los enteros \(a\) y \(b\) sucede que si \(n|(a-b)\) entonces \(a\) y \(b\) dejan el mismo residuo al dividirse entre \(n\).

Por hipótesis tenemos que \(a \overset{n}{\sim_2} b\), es decir que \(n|(a-b)\). Entonces existe un entero \(k\) tal que \(a - b = kn\).
Por otro lado si dividimos a \(a\) y \(b\) entre \(n\), por el algoritmo de la división, tendremos que

\[\begin{align*} a = q_1n + r_1, \\ & \\ b = q_2n + r_2. \end{align*}\]

Luego, restando ambas ecuaciones tenemos

\[a - b = (q_1n + r_1) - (q_2n + r_2) = (q_1 - q_2)n + r_1 - r_2.\]

Entonces tenemos que

\[kn = (q_1 - q_2)n + r_1 - r_2.\]

Como \(kn\) es múltiplo de \(n\), la única forma en que esta igualdad sea cierta es si \(r_1 - r_2\) también sea múltiplo de \(n\). Pero dado que \(0 \le r_1,r_2 < n\), entonces la única posibilidad es que \(r_1 = r_2\). Esto quiere decir que \(a\) y \(b\) dejan el mismo residuo al ser divididos entre \(n\), es decir que \(a \overset{n}{\sim_1} b\). \(\square\)

Particiones#

Definición 29 (Partición)

Sea \(A\) un conjunto. Una partición de \(A\) es una colección de conjuntos \(\{A_i\}_{i\in I}\) tal que:

Ningún \(A_i\) es vacío.
\(A_i \cap A_j = \emptyset\) si \(i\neq j\).
\(A=\bigcup_{i\in I} A_i\).

Ejemplo 76

Si \(A = \{ a \}\) entonces hay una y solo una partición de \(A\), es decir, \(\{ A \}\) la familia con un solo conjunto.

Solución.

Primero notemos que el único subconjunto no vacío de \(A\) es \(\{ a \}\). No puede haber más de un subconjunto no vacío ya que \(A\) sólo tiene un elemento.

Ahora veamos que cumple con la definición de partición.

Como \(\{ a \}\) es el único subconjunto y es no vacío, se cumple que ningún \(A_i\) es vacío.
Además, como sólo hay un subconjunto por vacuidad se cumple que \(A_i \cap A_j = \emptyset\) si \(i \neq j\).
Por último la unión de \(\{ a \}\) es \(A\), por lo tanto se cumple que \(A=\bigcup_{i\in I} A_i\).

Observación 13

Para cualquier conjunto \(A \neq \emptyset\) siempre existen al menos dos particiones que son:

La partición \(\{ A \}\) cuya colección consta de un solo conjunto.
La partición \( \{ \{a \}_{a \in A} \}\) cuya colección consta de todos los subconjuntos de \(A\) que tienen un solo elemento.

Veamos un ejemplo de la Observación 13.

Ejemplo 77

Si tomamos el conjunto \(A = \{ 0,1,2,3,4,5,6 \}\), entonces tendríamos las dos particiones siguientes.

La partición que consta de un solo conjunto.

Entonces tendríamos que \(A_1 = \{0,1,2,3,4,5,6 \} \subseteq A\). Como ya demostramos en el Ejemplo 76, sí cumple con ser una partición.

La partición cuya colección consta de todos los subconjuntos de \(A\) que tienen un solo elemento.

Entonces tendríamos la familia \(A_1 = \{ 0 \}, A_2 = \{ 1 \}, A_3 = \{ 2 \}, A_4 = \{ 3 \}, A_5 = \{ 4 \}, A_6 = \{ 5 \}, A_7 = \{ 6 \}\).

Notemos lo siguiente. Cada uno de los \(A_i\) son no vacíos ya que todos tienen al menos un elemento. Si tomamos \(i\neq j\) sucede que \(A_i \cap A_j = \emptyset\) pues tienen elementos distintos. Finalmente, se cumple que \(A=\bigcup_{i\in I} A_i\). Por lo tanto, se cumplen las condiciones de ser una partición.

En capítulos anteriores hemos visto colecciones que son particiones, por ejemplo:

Ejemplo 78

La partición de los números naturales en pares e impares:

\[\begin{align*} A_1 &= \{0,2,4,6,8,10, \ldots \}, \\ & \\ A_2 &= \{1,3,5,7,9,11, \ldots \}. \end{align*}\]

Ejemplo 79

La partición de los enteros positivos en números primos, números compuestos y el \(1\):

\[\begin{align*} A_1 &= \{2,3,5,7,11,13,17, \ldots \}, \\ & \\ A_2 &= \{4,6,8,9,10,12,14, \ldots \}, \\ & \\ A_3 &= \{1 \}. \end{align*}\]

Otra partición del conjunto que trabajamos en el Ejemplo 77 es la siguiente.

Ejemplo 80

Si tomamos el conjunto \(A = \{0,1,2,3,4,5,6 \}\), tendríamos la siguiente partición.

\[\begin{align*} A_1 &= \{0,1,4,5 \}, \\ & \\ A_2 &= \{2,3 \}, \\ & \\ A_3 &= \{6 \}. \end{align*}\]

Clases de equivalencia y particiones inducidas#

Definición 30 (Clase de equivalencia)

Si \(\sim\) es una relación de equivalencia en \(A\), al conjunto de elementos de \(A\) relacionados con \(a \in A\) le llamamos la clase de equivalencia de \(a\) y lo denotamos por \([a]\). En otras palabras

\[[a] = \{ b \in A \mid a \sim b \}.\]

Como vimos en el Ejemplo 74, la relación \(\overset{n}{\sim_1}\) es una relación de equivalencia. Veamos con el siguiente ejemplo las clases de equivalencia que nos genera esta relación.

Ejemplo 81

Recordemos que la relación \(\overset{n}{\sim_1}\) decía que dos números enteros \(a\) y \(b\) se relacionan \(a \overset{n}{\sim_1} b\) si dejan el mismo residuo al dividirse entre \(n\).

Entonces si tomamos el conjunto \(A = \{1,2,3,4, \ldots, 19,20 \}\) y \(n = 4\) tendríamos lo siguiente:

\[\begin{align*} 1 &= 4\cdot 0 + 1, & 2 &= 4\cdot 0 + 2, & 3 &= 4\cdot 0 + 3, & 4 &= 4\cdot 1 + 0, \\ & \\ 5 &= 4\cdot 1 + 1, & 6 &= 4\cdot 1 + 2, & 7 &= 4\cdot 1 + 3, & 8 &= 4\cdot 2 + 0, \\ & \\ 9 &= 4\cdot 2 + 1, & 10 &= 4\cdot 2 + 2, & 11 &= 4\cdot 2 + 3, & 12 &= 4\cdot 3 + 0, \\ & \\ 13 &= 4\cdot 3 + 1, & 14 &= 4\cdot 3 + 2, & 15 &= 4\cdot 3 + 3, & 16 &= 4\cdot 4 + 0, \\ & \\ 17 &= 4\cdot 4 + 1, & 18 &= 4\cdot 4 + 2, & 19 &= 4\cdot 4 + 3, & 20 &= 4\cdot 5 + 0. \\ \end{align*}\]

De lo anterior tenemos las siguientes clases.

La clase \([1]\) que son los números que al dividirse entre \(4\) dejan residuo \(1\).

\[[1] = \{1,5,9,13,17 \}.\]

La clase \([2]\) que son los números que al dividirse entre \(4\) dejan residuo \(2\).

\[[2] = \{2,6,10,14,18 \}.\]

La clase \([3]\) que son los números que al dividirse entre \(4\) dejan residuo \(3\).

\[[3] = \{3,7,11,15,19 \}.\]

La clase \([0]\) que son los números que al dividirse entre \(4\) dejan residuo \(0\).

\[[0] = \{4,8,12,16,20 \}.\]

Veamos algunos resultados sobre las clases de equivalencia.

Teorema 25

Las clases de equivalencia de una relación de equivalencia \(\sim\) en \(A\) forman una partición de \(A\).

Demostración. Para esta demostración vamos a probar las \(3\) propiedades de la Definición 29.

Primero demostremos que \(A = \bigcup \{ [a] \mid a \in A \}\).

Empecemos viendo que, \(\bigcup \{ [a] \mid a \in A \} \subseteq A\). Notemos que por definición, \([a] = \{ b \in A \mid a \sim b \}\), por lo que cada \([a] \subseteq A\).
Entonces tenemos que

\[\bigcup \{ [a] \mid a \in A \} \subseteq A.\]

Ahora, veamos que \(A \subseteq \bigcup \{ [a] \mid a \in A \}\).

Como \(a \in A\), tenemos que \(a \in [a]\) ya que cada elemento de \(A\) pertenece a su propia clase de equivalencia pues \(\sim\) es reflexiva. Entonces tenemos que

\[a \in \bigcup \{ [a] \mid a \in A \}.\]

Y así

\[A \subseteq \bigcup \{ [a] \mid a \in A \}.\]

Por lo tanto, concluimos que \(A = \bigcup \{ [a] \mid a \in A \}\).

Demostremos que si \(a,b \in A\) y \([a] \neq [b]\) entonces \([a] \cap [b] = \emptyset\).

Procedamos por contrapuesta y supongamos que \(c \in [a] \cap [b]\), debemos demostrar que \([a] = [b]\).

Tenemos que \(c \in [a]\) y \(c \in [b]\) así que, por definición \(c \sim a\) y \(c \sim b\), como la relación es de equivalencia sabemos que se cumple la simetría, por lo cual \(a \sim c\) y \(c \sim b\). Luego, por la transitividad tenemos que \(a \sim b\), y por lo tanto \(b \in [a]\).

Sea \(d \in [b]\), entonces \(b \sim d\). Ya que \(a \sim b\) y \(b \sim d\) tenemos que \(a \sim d\) y esto quiere decir que \(d \in [a]\). Lo anterior prueba que \([b] \subseteq [a]\).

Ahora, sea \(e \in [a]\), entonces \(a \sim e\). Como \(b \sim a\) y \(a \sim e\) tenemos que \(b \sim e\), es decir que \(e \in [b]\). Esto prueba que \([a] \subseteq [b]\).

Por lo tanto \([a] = [b]\).

Por último probemos que ninguna clase de equivalencia en \(A\) es vacía, es decir que \([a] \neq \emptyset\) para cualquier \(a \in A\).

Esto es claro, ya que por la definición \([a] = \{ b \in A \mid a \sim b \}\), y por reflexividad \(a\sim a\). \(\square\)

Teorema 26

A partir de una partición de \(A\) podemos construir la relación \(a\sim b\) si están en el mismo conjunto de la partición, y esta es una relación de equivalencia.

Demostración. Supongamos que tenemos una partición \(P = \{ P_i \}_{i\in I}\) de \(A\). Demostremos que \(\sim\) es una relación de equivalencia.
Notemos que la regla de la relación es que \(a \sim b\) si \(a,b \in P_i\) para algún \(i\in I\).

Veamos que la relación \(\sim\) es reflexiva.

Como \(P\) es una partición de \(A\), tenemos que dada \(a \in A\), existe un conjunto \(P_i\) en \(P\) tal que \(a \in P_i\), ya que cada elemento del conjunto \(A\) pertenece a uno de los conjuntos de la partición \(P\). Por lo tanto, \(a \sim a\) y así la relación \(\sim\) es reflexiva.

Ahora veamos que la relación \(\sim\) es simétrica.

Si tenemos que \(a\sim b\), existe \(i\in I\) tal que \(a,b \in P_i\). Por lo tanto \(b,a \in P_i\). Así, \(b\sim a\).

Por último veamos que la relación \(\sim\) es transitiva.

Supongamos que \(a\sim b\) y \(b \sim c\). Es decir, existe \(i\in I\) tal que \(a,b\in P_i\) y \(j\in I\) tal que \(b,c\in P_j\). De lo anterior podemos notar que \(b \in P_i \cap P_j\) lo cual implica que \(i = j\) debido a la Definición 29. Entonces \(a,c \in P_i = P_j\), por lo que \(a \sim c\).
Por lo tanto, si \(a \sim b\) y \(b \sim c\) entonces se cumple que \(a \sim c\). Así, la relación \(\sim\) es transitiva.

Con esto probamos que la relación \(\sim\) es una relación de equivalencia. \(\square\)

Código ejemplo de particiones#

El siguiente código crea una partición. La idea detrás del código es tomar un texto y generar el conjunto de palabras que hay en el texto. Después, bajo cierta relación crear las clases de equivalencia y esto nos dará una partición del conjunto de palabras.
Si damos la relación “letra”, podemos crear las clases de las palabras que comienzan con la misma letra. Por otro lado si damos la relación “número”, podemos crear las clases de las palabras que tienen el mismo número de letras.

def particion_palabras(texto, criterio):
    texto = texto.lower()
    palabras = list(set(texto.split()))
    print(f"El conjunto de palabras es:")
    for p in range(0,len(palabras),7):
        print(palabras[p:p+7], "\n")
    grupos = {} 

    for palabra in palabras:
        if criterio == "letra":
            clave = palabra[0]  
        elif criterio == "numero":
            clave = len(palabra)  
        else:
            print("Criterio no válido. Debe ser 'letra' o 'numero'.")
            return

        if clave not in grupos:
            grupos[clave] = []
        grupos[clave].append(palabra)
    
    claves_ordenadas = sorted(grupos.keys())

    for clave in claves_ordenadas:
        print(f"Palabras que {'empiezan con' if criterio == 'letra' else 'tienen'} '{clave}'{'letras' if criterio == 'numero' else ''}:")
        print(grupos[clave],'\n')

Usaremos el siguiente texto para usarlo en la función: “La teoría de números estudia las propiedades de los números enteros y sus relaciones. Explora conceptos como divisibilidad, números primos, congruencias y más. Sus aplicaciones se extienden desde la criptografía hasta la física.”

texto = "La teoría de números estudia las propiedades de los números enteros y sus relaciones. Explora conceptos como divisibilidad, números primos, congruencias y más. Sus aplicaciones se extienden desde la criptografía hasta la física."

Primero usaremos la función para hacer las clases de las palabras que empiezan con la misma letra.

particion_palabras(texto, 'letra')

El conjunto de palabras es:
['teoría', 'criptografía', 'de', 'divisibilidad,', 'números', 'extienden', 'los'] 

['primos,', 'aplicaciones', 'propiedades', 'física.', 'desde', 'sus', 'y'] 

['hasta', 'relaciones.', 'explora', 'más.', 'conceptos', 'las', 'como'] 

['enteros', 'congruencias', 'se', 'la', 'estudia'] 

Palabras que empiezan con 'a':
['aplicaciones'] 

Palabras que empiezan con 'c':
['criptografía', 'conceptos', 'como', 'congruencias'] 

Palabras que empiezan con 'd':
['de', 'divisibilidad,', 'desde'] 

Palabras que empiezan con 'e':
['extienden', 'explora', 'enteros', 'estudia'] 

Palabras que empiezan con 'f':
['física.'] 

Palabras que empiezan con 'h':
['hasta'] 

Palabras que empiezan con 'l':
['los', 'las', 'la'] 

Palabras que empiezan con 'm':
['más.'] 

Palabras que empiezan con 'n':
['números'] 

Palabras que empiezan con 'p':
['primos,', 'propiedades'] 

Palabras que empiezan con 'r':
['relaciones.'] 

Palabras que empiezan con 's':
['sus', 'se'] 

Palabras que empiezan con 't':
['teoría'] 

Palabras que empiezan con 'y':
['y'] 

Ahora vamos usar el código para hacer las clases de las palabras que tienen el mismo número de letras.

particion_palabras(texto,'numero')

El conjunto de palabras es:
['teoría', 'criptografía', 'de', 'divisibilidad,', 'números', 'extienden', 'los'] 

['primos,', 'aplicaciones', 'propiedades', 'física.', 'desde', 'sus', 'y'] 

['hasta', 'relaciones.', 'explora', 'más.', 'conceptos', 'las', 'como'] 

['enteros', 'congruencias', 'se', 'la', 'estudia'] 

Palabras que tienen '1'letras:
['y'] 

Palabras que tienen '2'letras:
['de', 'se', 'la'] 

Palabras que tienen '3'letras:
['los', 'sus', 'las'] 

Palabras que tienen '4'letras:
['más.', 'como'] 

Palabras que tienen '5'letras:
['desde', 'hasta'] 

Palabras que tienen '6'letras:
['teoría'] 

Palabras que tienen '7'letras:
['números', 'primos,', 'física.', 'explora', 'enteros', 'estudia'] 

Palabras que tienen '9'letras:
['extienden', 'conceptos'] 

Palabras que tienen '11'letras:
['propiedades', 'relaciones.'] 

Palabras que tienen '12'letras:
['criptografía', 'aplicaciones', 'congruencias'] 

Palabras que tienen '14'letras:
['divisibilidad,'] 

Explicación del código#

En este capítulo trabajamos con variables que tienen como valor asignado un texto. Python reconoce que la variable es de tipo str, es decir, una cadena de texto. Este texto tiene que ir con comillas de apertura y de cerradura. Podemos usar dos tipos de comillas para encerrar el texto y Python lo reconozca como tipo str.

texto = "El valor de esta variable es un texto"

texto_1 = 'Estas comillas son equivalentes a las de arriba'

Una propiedad sobre las cadenas de texto o los objetos tipo str, es que podemos modificarlos. Por ejemplo, podemos convertir todas la letras en minúsculas con el siguiente método.

texto = "Este texto ConTiene MAYÚSculas IntenCionaleS"  

texto_minusculas = texto.lower()

El resultado de la variable «texto_minusculas» es el mismo texto pero con todas sus letras en minúsculas “este texto contiene mayúsculas intencionales.”

Otra propiedad interesante es que podemos convertir el texto en una lista. Esta lista contendrá todas las palabras del texto que estén separadas por un espacio. Dicha separacióm la logramos con el siguiente método.

texto = "El valor de esta variable es un texto" 

texto_lista = texto.split()

El resultado de la variable «texto_lista» sería una lista donde sus elementos son las palabras del texto, es decir

\[[\text{"El"},\text{"valor"},\text{"de"},\text{"esta"},\text{"variable"},\text{"es"},\text{"un"},\text{"texto"}].\]

Al igual que las listas, los objetos de tipo str tienen un índice y podemos acceder a cada caracter individual de la cadena de texto. Al igual que las listas estos índices comienzan con \(0\).

texto = "Cadena"

tercer_elemento = texto[2]

El resultado de la variable «tercer_elemento» sería la letra \(\text{"d"}\) el cual sigue siendo un objeto de tipo str.

Ya habíamos visto la función len() para las listas. Esta función también sirve para los objetos tipo str y si lo aplicamos nos dirá la longitud de la cadena de texto tomando también en cuenta los espacios.

texto = "esto es un ejemplo"

texto_elementos = len(texto)

El resultado de la variable «texto_elementos» sería igual a \(18\).

Usamos la función list(). Esta función sirve para convertir objetos iterables en una lista. Con esto logramos por ejemplo, convertir un objeto del tipo conjunto (set) en un objeto del tipo lista (list). La sintaxis sería la siguiente.

list(objeto_iterable)

Utilizamos otra propiedad de las listas. Podemos usar la función sorted() para organizarlas, ya sea en orden alfabético o numérico.

Lista_1 = ["b",'e','a','c','d']

lista_ordenada = sorted(lista_1)

El resultado de la variable «lista_ordenada» sería \([\text{"a"}, \text{"b"}, \text{"c"}, \text{"d"}, \text{"e"}]\).

También presentamos una nueva estructura, los diccionarios. Son una estructura de datos muy útil cuando se quiere guardar información de forma organizada. Un diccionario contiene objetos que constan de dos cosas: una clave y un valor. Una clave es algo único que sirve para identificar a los valores, las claves pueden de tipo cadenas o enteros o cualquier objeto no inmutable. Los valores pueden ser de cualquier tipo.
Para comprender mejor los diccionarios, pensemos como si fueran una agenda donde se guardan los números de las personas, las claves serían los nombres de las personas que son únicos para identificar los números telefónicos de estas.
Los diccionarios, a diferencia de las listas, usan llaves para ser creados.
En el siguiente código mostramos cómo crear un diccionario vacío, cómo sería la sintaxis para los objetos de un diccionario y un ejemplo de un diccionario.

diccionario_vacio = {}

diccionario_sintaxis = {"clave":"valor"}

diccionario_ejemplo = {"Juan":36, "Pedro":"5582938475","sub_dicc":{"clave":"valor"}, 4:["mi","clave","es","un","entero"]}

Si queremos modificar el valor de algún elemento dentro del diccionario debemos usar el siguiente comando.

diccionario["clave"] = "nuevo_valor"

Para agregar valores nuevos a un diccionario debemos usar el siguiente comando.

diccionario["nueva_clave"] = "valor"

Si quisiéramos ver las claves que contiene nuestro diccionario debemos usar el siguiente comando.

diccionario.keys()

Por último utilizamos una expresión condicional dentro de un f-string. Esta forma de expresión condicional nos funciona si queremos imprimir en la consola dependiendo del valor de alguna condición. La sintaxis sería la siguiente.

{valor_1 if condición else valor_2}

Lo que hace esta forma de impresión es que, en caso de que la condición dentro del condicional if sea verdadera, se devuelve el «valor_1». En caso de que sea falsa la condición se devuelve el «valor_2».

Ahora vamos a explicar cómo funciona el código.

def particion_palabras(texto, criterio):
    texto = texto.lower()
    palabras = list(set(texto.split()))
    print(f"El conjunto de palabras es:")
    for p in range(0,len(palabras),7):
        print(palabras[p:p+7], "\n")
    grupos = {} 

    for palabra in palabras:
        if criterio == "letra":
            clave = palabra[0]  
        elif criterio == "numero":
            clave = len(palabra)  
        else:
            print("Criterio no válido. Debe ser 'letra' o 'numero'.")
            return

        if clave not in grupos:
            grupos[clave] = []
        grupos[clave].append(palabra)
    
    claves_ordenadas = sorted(grupos.keys())

    for clave in claves_ordenadas:
        print(f"Palabras que {'empiezan con' if criterio == 'letra' else 'tienen'} '{clave}'{'letras' if criterio == 'numero' else ''}:")
        print(grupos[clave],'\n')

Definimos una función llamada «particion_palabras» que recibe como primer argumento una variable llamada «texto» la cual debe ser un objeto de tipo str y debe ser definida en una variable aparte de la función. El segundo argumento es «criterio» al cual le podemos asignar dos valores, el de “letra” o el de “palabra”.
Aplicamos el método lower() a la variable «texto» para convertir todas las letras del texto en minúsculas y actualizamos la variable «texto» asignando este cambio a la misma variable.
Luego creamos la variable «palabras» la cual es una lista que se crea aplicando el método split() a la variable «texto». Utilizando la función set(), quitamos las palabras repetidas para generar el conjunto de las palabras. Con la función list() convertimos nuevamente en un objeto del tipo lista.
Creamos un ciclo for para mostrar en la consola cuál es el conjunto de palabras con el que va a trabajar el código. Finalmente, creamos la variable «grupos» la cual es un diccionario vacío.

def particion_palabras(texto, criterio):
    texto = texto.lower()
    palabras = list(set(texto.split()))
    print(f"El conjunto de palabras es:")
    for p in range(0,len(palabras),7):
        print(palabras[p:p+7], "\n")
    grupos = {} 

Iniciamos un ciclo for en el cual vamos a recorrer los elementos de la lista de palabras en la variable «palabras». Luego creamos tres condicionales para revisar que valor toma la variable «criterio».
Cada palabra que es tomado por el ciclo for, es evaluada por los condicionales if, elif y else.
Empezamos con el condicional if. Si la variable «criterio» es igual a «letra» entonces se crea la variable «clave» que toma como valor la primera letra de la palabra.
Si el condicional anterior no se cumple entonces pasa al condicional elif. Si el valor de la variable «criterio» es igual a «numero», se crea la variable «clave» que toma como valor el tamaño de la palabra, es decir cuántas letras tiene la palabra.
En caso de que no se dé bien el valor de la variable «criterio», el código pasa al condicional else que nos imprime en pantalla que el criterio dado no es válido.

    for palabra in palabras:
        if criterio == "letra":
            clave = palabra[0]  
        elif criterio == "numero":
            clave = len(palabra)  
        else:
            print("Criterio no válido. Debe ser 'letra' o 'numero'.")
            return

Una vez que se define el valor de la variable «criterio» el código pasa a un siguiente condicional if, el cual revisa si la «clave» que se tomó de la palabra en el ciclo for ya está en el diccionario vacío «grupos». Si no está, se agrega el objeto al diccionario, se agrega la «clave» y como valor de esa clave una lista vacía.
Si la «clave» ya está en el diccionario, entonces el código salta el condicional if y pasa a la siguiente parte del código que lo que hace es agregar la «palabra» del ciclo for al valor de la clave ya creada en el diccionario. Como los valores de las claves son listas tenemos que usar el método append() para agregar la palabra a la lista.
El ciclo for repite todo el procedimiento para cada palabra en la lista «palabras».

        if clave not in grupos:
            grupos[clave] = []
        grupos[clave].append(palabra)

Una vez que el ciclo for termina de recorrer todas las palabras, pasa a crear la variable «claves_ordenadas». Como sabemos, los diccionarios no tienen un orden, entonces cuando usamos el método grupos.key() nos da una lista desordenada de las claves a la cual le aplicamos el método sorted() para obtener una lista en orden alfabético o numérico, dependiendo del valor de la variable «criterio».
Por último, creamos un ciclo for con el cual recorremos las claves ordenadas de la lista «claves_ordenadas». Lo que hace el código es que por cada clave que toma imprime el resultado, pero depende del valor de la variable criterio. Si el criterio fue «letra» nos imprime “palabras que empiezan con la letra” y la lista de palabras que empiezan con esa letra, para cada clave en la lista. Si el criterio fue «numero» nos imprime “palabras que tienen \(n\) letras” y la lista con las palabras que tienen el mismo número de letras, para cada clave en la lista.

    claves_ordenadas = sorted(grupos.keys())

    for clave in claves_ordenadas:
        print(f"Palabras que {'empiezan con' if criterio == 'letra' else 'tienen'} '{clave}'{'letras' if criterio == 'numero' else ''}:")
        print(grupos[clave],'\n')

Ejercicios de práctica#

Da un ejemplo de relación para la cual se valgan las siguientes propiedades:

Que sea reflexiva y simétrica pero no sea transitiva.
Que sea reflexiva y transitiva pero que no sea simétrica.

Para un conjunto \(A\) la relación diagonal \(D(A)\) es tal que \(a \sim a\) para todo \(a\in A\).
Demuestra de la relación diagonal es una relación de equivalencia.
Para los siguientes incisos, verifica si las relaciones son de equivalencia.

Sean \(a,b \in \mathbb{Z}^+\), diremos que \(a\sim b\) si \((a,b) = 1\).
Sean \(a,b \in \mathbb{Z}^+\), diremos que \(a\sim b\) si \(a\) tiene un factor primo en común con \(b\).

Una relación \(\sim\) en un conjunto \(A\), se dice que es antisimétrica si cumple que, para todo \(a,b\in A\), si \(a\sim b\) y \(b\sim a\), entonces \(a =b\).

Da un ejemplo de una familia \(F\) de conjuntos tal que se pueda establecer entre ellos la siguiente relación: Si \(A, B \in F\) sucede que \(A \sim B\) si \(A \subseteq B\). Demuestra que esta relación es reflexiva, transitiva y antisimétrica. Para demostrar que es antisimétrica debes ver que para cualesquiera dos conjuntos \(A\) y \(B\) en \(F\), si \(A \subseteq B\) y \(B \subseteq A\), entonces \(A = B\).
Demuestra que la partición del Ejemplo 79 induce una relación de equivalencia.