7.3: Particiones

Los teoremas 7.42 y 7.43 implican que si\(\sim\) es una relación de equivalencia en un conjunto\(A\), entonces se\(\sim\)\(A\) rompe en “trozos” disjuntos por pares, donde cada pedazo es algo\([a]\) para\(a\in A\). Como probablemente ya habrás notado, las relaciones de equivalencia están íntimamente relacionadas con el siguiente concepto.

Definición 7.51. Se dice que una colección\(\Omega\) de subconjuntos de un conjunto\(A\) es una partición de\(A\) si los elementos de\(\Omega\) satisfacen:

1. Cada uno no\(X\in \Omega\) está vacío,
2. Para todos\(X,Y\in\Omega\)\(X\neq Y\),\(X\cap Y=\emptyset\) cuándo y
3. \(\displaystyle \bigcup_{X\in\Omega}X=A\).

Es decir, los elementos de\(\Omega\) son conjuntos no vacíos disjuntos por pares y su unión es todo de\(A\). Cada uno\(X\in \Omega\) se llama un bloque de la partición.

Ejemplo 7.52. Considere la relación de equivalencia\(\sim\) en el conjunto\(P\) descrito en el Ejemplo 7.45. Recordemos que las clases de equivalencia corresponden a colecciones de individuos con el mismo apellido. Dado que cada clase de equivalencia no está vacía y cada residente del pueblo pertenece exactamente a una clase de equivalencia, la colección de clases de equivalencia forma una partición de\(P\). Es decir,\(P/\mathord\sim\) es una partición de\(P\), donde los bloques de la partición corresponden a conjuntos de residentes con el mismo apellido.

Ejemplo 7.53. Cada uno de los siguientes es un ejemplo de una partición del conjunto dado entre paréntesis.

1. Demócrata, Republicano, Independiente, Partido Verde, Libertario, etc. (conjunto de votantes registrados)
2. Estudiante de primer año, segundo año, junior, senior (conjunto de estudiantes de secundaria)
3. Equivalos, cuotas (conjunto de enteros)
4. Racionales, irracionales (conjunto de números reales)

Ejemplo 7.54. Dejar\(A=\{a,b,c,d,e,f\}\) y\(\Omega=\{\{a\}, \{b,c,d\}, \{e,f\}\}\). Dado que los elementos de\(\Omega\) son subconjuntos no vacíos disjuntos por parejas de\(A\) tal manera que su unión es todo de\(A\),\(\Omega\) es una partición de\(A\) que consta de tres bloques.

Problema 7.55. Considera el conjunto\(A\) del Ejemplo 7.54.

1. Encuentra una partición de\(A\) que consta de cuatro bloques.
2. Encuentra una colección de subconjuntos\(A\) que no formen una partición. Vea cuántas formas puede evitar que su colección sea una partición.

Problema 7.56. Para cada una de las siguientes, encuentra una partición de\(\mathbb{Z}\) con las propiedades dadas.

1. Una partición de\(\mathbb{Z}\) eso consiste en finitamente muchos bloques, donde cada uno de los bloques es infinito.
2. Una partición de\(\mathbb{Z}\) eso consiste en infinitamente muchos bloques, donde cada uno de los bloques es finito.
3. Una partición de\(\mathbb{Z}\) eso consiste en infinitamente muchos bloques, donde cada uno de los bloques es infinito.

Problema 7.57. Para cada relación en Problema 7.34, determinar si la colección correspondiente de los conjuntos de familiares forma una partición del conjunto dado.

Problema 7.58. ¿Podemos particionar el conjunto vacío? Si es así, describa una partición. Si no, explica por qué.

El siguiente teorema explica la mitad de la estrecha conexión entre particiones y relaciones de equivalencia. El teorema 7.73 arroja la otra mitad.

Problema 7.59. Si\(\sim\) es una relación de equivalencia en un conjunto no vacío\(A\), entonces\(A/\mathord\sim\) forma una partición de\(A\).

Problema 7.60. En el teorema anterior, ¿por qué requeríamos\(A\) estar no vacíos?

Problema 7.61. Considerar la relación de equivalencia\[\sim\ =\{(1,1),(1,2),(2,1), (2,2),(3,3),(4,4),(4,5),(5,4),(5,5),(6,6),(5,6),(6,5),(4,6),(6,4)\}\] en el conjunto\(A=\{1,2,3,4,5,6\}\). Encuentra la partición determinada por\(Rel(\sim)\).

Resulta que podemos revertir la situación, también. Es decir, dada una partición, podemos formar una relación de equivalencia tal que las clases de equivalencia correspondan a los bloques de la partición. Antes de probarlo, necesitamos una definición.

Definición 7.62. Dejar\(A\) ser un conjunto y\(\Omega\) cualquier colección de subconjuntos de\(A\) (no necesariamente una partición). Definir la relación\(R_{\Omega}\) en\(A\) vía\(aR_{\Omega}b\) si existe\(X\in \Omega\) que contenga ambos\(a\) y\(b\). Esta relación se llama la relación sobre\(A\) asociada a\(\Omega\).

En otras palabras, dos elementos están relacionados exactamente cuando están en el mismo subconjunto.

Problema 7.63. Dejar\(A=\{a,b,c,d,e,f\}\) y dejar\(\Omega=\{\{a,c\},\{b,c\},\{d,f\}\}\). Enumere los pares ordenados\(R_{\Omega}\) y dibuje el dígrafo correspondiente.

Problema 7.64. Dejar\(A\) y\(\Omega\) ser como en el Ejemplo 7.54. Enumere los pares ordenados\(R_{\Omega}\) y dibuje el dígrafo correspondiente.

Problema 7.65. Considerar Problema 7.24. Encuentra la relación sobre\(A\) asociado\(Rel(\sim)\) y compara con lo que has obtenido\(R\) en Problema 7.24.

Problema 7.66. Dar un ejemplo de un conjunto\(A\) y una colección\(\Omega\) de\(\mathcal{P}(A)\) tal manera que la relación no\(R_{\Omega}\) sea reflexiva.

Problema 7.67. Dejar\(A=\{1,2,3,4,5,6\}\) y\(\Omega=\{\{1,3,4\},\{2,4\},\{3,4\},\{6\}\}\).

1. ¿Es\(\Omega\) una partición de\(A\)?
2. Encuentra\(R_{\Omega}\) listando pares ordenados o dibujando un dígrafo.
3. ¿Es\(R_{\Omega}\) una relación de equivalencia?
4. Encontrar\(Rel(R_\Omega)\) (es decir, la colección de subconjuntos de\(A\) determinado por\(R_{\Omega}\)). ¿Cómo están\(\Omega\) y\(Rel(R_\Omega)\) relacionados?

Teorema 7.68. Si\(\Omega\) es una colección de subconjuntos de un conjunto no vacío\(A\) (no necesariamente una partición) tal que\[\bigcup_{X\in\Omega}X=A,\] entonces\(R_{\Omega}\) es reflexivo.

Problema 7.69. ¿Es necesario exigir\(A\) estar no vacío en el Teorema 7.68?

Teorema 7.70. Si\(\Omega\) es una colección de subconjuntos de un conjunto\(A\) (no necesariamente una partición), entonces\(R_{\Omega}\) es simétrica.

Teorema 7.71. Si\(\Omega\) es una colección de subconjuntos de un conjunto\(A\) (no necesariamente una partición) tal que los elementos de\(\Omega\) son disjuntos por pares, entonces\(R_{\Omega}\) es transitivo.

Problema 7.72. ¿Por qué no requerimos\(A\) ser no vacíos en los Teoremas 7.70 y 7.71?

Recordemos que Teorema 7.59 dice que las clases de equivalencia para una relación en un conjunto no vacío\(A\) determina una partición de\(A\). El siguiente teorema nos dice que cada partición de un conjunto produce una relación de equivalencia donde las clases de equivalencia corresponden a los bloques de la partición. Este resultado es consecuencia de los Teoremas 7.68, 7.70 y 7.71.

Teorema 7.73. Si\(\Omega\) es una partición de un conjunto\(A\), entonces\(R_{\Omega}\) es una relación de equivalencia.

En conjunto, los Teoremas 7.59 y 7.73 nos dicen que las relaciones de equivalencia y las particiones son dos formas distintas de ver lo mismo.

Corolario 7.74. Si\(R\) es una relación sobre un conjunto no vacío\(A\) tal que la colección del conjunto de parientes con respecto a\(R\) es una partición de\(A\), entonces\(R\) es una relación de equivalencia.

Problema 7.75. Vamos\(A=\{\circ, \triangle, \blacktriangle, \square, \blacksquare, \bigstar \}\). Conformar una partición\(\Omega\)\(A\) y luego dibujar el dígrafo correspondiente a\(R_{\Omega}\).