D: Particiones y Relaciones de Equivalencia
- Page ID
- 118501
Una partición de un conjunto\(X\) es una colección\(\mathcal{P}\) de subconjuntos disjuntos por pares, no vacíos de\(X\) cuya unión es\(X\). Los elementos de\(\mathcal{P}\) se llaman los bloques de la partición.
Por ejemplo, si\(X=[9]= \{1,2,3,4,5,6,7,8,9\}\) entonces\[\mathcal{P}=\{ \{1,2\},\{3\},\{5,8,9\}, \{4,6,7\} \}\] es una partición de\(X\). Tenga en cuenta que esta partición tiene cuatro bloques\(\{1,2\}\)\(\{3\}\),,\(\{5,8,9\}\), y\(\{4,6,7\}\).
Observación: En la definición de partición utilizamos el término colección. Este es solo otro nombre para set. Simplemente es más natural decir colección de conjuntos que decir conjunto de conjuntos. Entonces, de hecho, una partición de\(X\) es un conjunto cuyos elementos son ellos mismos conjuntos a los que elegimos llamar bloques, satisfaciendo tres propiedades:
- Cada bloque es un subconjunto no vacío de\(X\).
- No hay dos bloques diferentes que tengan un elemento en común.
- Cada elemento de\(X\) yace en al menos un bloque.
Problema D.1 Encuentra todas las particiones del conjunto\([4]\). Listarlos de acuerdo a los números de bloques en cada partición. El número de bloques puede ser cualquier número entero de 1 a 4.
Problema D.2 Encuentra una partición\(\mathcal{P}_k\) del conjunto\(\mathbb{Z}\) que tenga exactamente\(k\) bloques para cada uno de los siguientes valores de\(k\): 1,2,3,4,5,10.
Una relación (binaria) en un conjunto\(X\) es un subconjunto\(\rho\) del producto cartesiano\(X \times X\). Si\((a,b) \in R\) escribimos\(a \rho b\) y decimos que\(a\) está relacionado\(b\) con respecto a la relación\(R\).
Ya que solo nos ocuparemos de las relaciones binarias, dejaremos fuera el modificador binario. Ejemplos de relaciones son\(<\) y\(\le\) en el set\(\mathbb{R}\),\(=\) en cualquier set, y\(\cong\) en la clase de todos los grupos. En lugar de usar\(\rho\) para una relación genérica, usamos el símbolo\(\sim\).
Una relación\(\sim\) en un conjunto\(X\) es una relación de equivalencia sobre\(X\) si las siguientes propiedades se mantienen para todos\(x,y,z \in X\).
- \(x \sim x\).
- Si\(x \sim y\) entonces\(y \sim x\).
- Si\(x \sim y\) y\(y \sim z\) entonces\(x \sim z\).
Las propiedades en la definición anterior se denominan reflexividad, simetría, transitividad, respectivamente.
La relación de equivalencia más común es la igualdad. La igualdad es una relación de equivalencia en cualquier conjunto.
Si\(\sim\) es una relación de equivalencia en el conjunto\(X\), y\(a \in X\) definimos el conjunto\[[a] = \{ x \in X \ | \ x \sim a \}.\]\([a]\) se llama la clase de equivalencia de\(a\) relativo a la relación de equivalencia \(\sim\).
Si\(\sim\) hay alguna relación de equivalencia en el conjunto\(X\) entonces la colección de todas las clases de equivalencia es una partición de\(X\). Por el contrario, dada cualquier partición\(\mathcal{P}\) del conjunto\(X\), se puede definir una relación\(\sim\) de equivalencia\(X\) por la regla\[a \sim b \Longleftrightarrow a,b \in B \mbox{ for some block $B \in \mathcal{P}$}\] en cuyo caso las clases de equivalencia de\(\sim\) son precisamente los bloques del partición\(\mathcal{P}\).