7.1: Particiones y Relaciones de Equivalencia en Conjuntos

Definición: Partición y Celdas

\(S\)Déjese ser un conjunto. Entonces una colección de subconjuntos\(P=\{S_i\}_{i\in I}\) (donde\(I\) hay algún conjunto de índices) es una partición de\(S\) si cada uno\(S_i \neq \emptyset\) y cada elemento de\(S\) está exactamente en uno\(S_i\text{.}\) En otras palabras,\(P=\{S_i\}_{i\in I}\) es una partición de\(S\) si y solo si:

1. cada\(S_i\neq \emptyset\text{;}\)

2. los\(S_i\) son mutuamente disjuntos (es decir,\(S_i\cap S_j = \emptyset\) para\(i\neq j \in I\)); y

3. \(S=\bigcup_{i\in I}S_i\text{.}\)

Los\(S_i\) se llaman las celdas de la partición.

Ejemplo\(\PageIndex{1}\)

1. El conjunto\(\{1,2,3\}\) tiene\(5\) particiones: a saber,

\ begin {ecuación*}\ {\ {1,2,3\}\},\ {\ {1,2\},\ {3\}\},\ {\ {1,3\},\ {2\}\},\ {\ {2,3\},\ {1\}\}\ texto {y}\ {\ {1\},\ {2\},\ {3\}\}. \ end {ecuación*}

La primera partición que hemos mencionado tiene una celda, las tres siguientes tienen dos celdas, y la última tiene tres celdas.

2. La siguiente es una partición\(2\) -celled de\(\mathbb{Z}\text{:}\)

\ begin {ecuación*}\ {\ {x\ in\ mathbb {Z}\,:\ x\ text {es par}\},\ {x\ in\ mathbb {Z}\,:\, x\ text {es impar}\}\}. \ end {ecuación*}

El número de particiones de un conjunto finito de\(n\) elementos se agranda muy rápidamente a medida que\(n\) llega al infinito. En efecto, ¡hay\(52\) particiones de un conjunto que contiene solo\(5\) elementos! (El número total de particiones de un conjunto\(n\) -elemento es el número Bell, No\(B_n\text{.}\) hay una forma trivial de computación\(B_n\text{,}\) en general, aunque el\(B_n\) do satisfaga la relación de recurrencia relativamente simple

\ begin {ecuación*} B_ {n+1} =\ suma_ {k=0} ^n\ binom {n} {k} B_k,\ end {ecuación*}

para cada uno\(n\geq 1\text{.}\)) Pero nuestro objetivo aquí no es contar el número de particiones de un conjunto dado, sino usar particiones particulares de un grupo\(G\) para ayudarnos a estudiar la estructura de ese grupo. Pasamos ahora a nuestra siguiente definición.

Definición: Relación

\(S\)Déjese ser un conjunto. Entonces una relación on\(S\) es un subconjunto\(R\) de\(S\times S\text{.}\) ¹ Más generalmente, si\(S\) and \(T\) are sets, a relation between \(S\) and \(T\) is a subset of \(S \times T\text{.}\) We will not, however, in our class consider the cases in which \(S\) and \(T\) are different sets. Si\(R\) es una relación sobre\(S\) y\(x,y\in S\text{,}\) luego decimos que\(x\) está relacionado a\(y\text{,}\) y escribir\(x R y\text{,}\) si es\((x,y)\in R\text{;}\) contrario, decimos que no\(x\) está relacionado con\(y\text{,}\) y escribimos\(x \not R y\text{.}\)

Observación

Si hay una notación convencional utilizada para denotar una relación particular en un conjunto, usualmente usaremos esa notación, en lugar de\(R\text{,}\) denotar la relación.

Ya estamos familiarizados con algunas relaciones en\(\mathbb{R}\text{.}\) Común tales relaciones\(\geq\text{;}\) son\(=\text{,}\)\(\neq\text{,}\)\(\lt\text{,}\)\(\leq\text{,}\)\(>\text{,}\) y contienen exactamente los elementos que esperaríamos que contengan.

Ejemplo\(\PageIndex{2}\)

1. \(\lt\)es una relación sobre la\(\mathbb{R}\) que contiene, por ejemplo,\((3,4)\) pero no\((3,3)\) o\((4,3)\text{;}\)\(\leq\) es una relación sobre la\(\mathbb{R}\) que contiene\((3,4)\) y\((3,3)\) pero no\((4,3)\text{.}\)
2. Dada cualquier\(n\in \mathbb{Z}^+\text{,}\) congruencia, el módulo\(n\text{,}\) denotado\(\equiv_n\text{,}\) es una relación sobre\(\mathbb{Z}\text{,}\) donde\(\equiv_n\) se define como\(\{(x,y) \in \mathbb{Z} \times \mathbb{Z} \,:\, n \text{ divides } x-y\}\text{.}\)
3. Podemos definir una relación\(R\) sobre\(C^1\) (el conjunto de todas las funciones diferenciables de\(\mathbb{R}\) a\(\mathbb{R}\) cuyas derivadas son continuas) declarando que\((f,g)\in C^1 \times C^1\) está en\(R\) si y solo si\(f'=g'\text{.}\)

Definición: Relación de equivalencia

Dejar\(R\) ser una relación en un set\(S\text{.}\) Entonces\(R\) se dice que es:

• reflexivo sobre\(S\) si\(xR x\) por cada\(x\in S\text{;}\)
• simétrico en\(S\) si siempre\(x,y\in S\) con\(xR y\) nosotros también tenemos\(yR x\text{;}\) y
• transitivo en\(S\) si siempre\(x,y,z\in S\) con\(xR y\) y también\(yR z\) tenemos\(xR z\text{.}\)

Una relación reflexiva, simétrica y transitiva se denomina relación de equivalencia.

Si sabemos, o planeamos probar, que una relación es una relación de equivalencia, por convención podemos denotar la relación por\(\sim\text{,}\) más que por\(R\text{.}\)

Observación

Se puede pensar en una relación de equivalencia en un conjunto\(S\) como una “versión débil” de la igualdad en\(S\text{.}\) Indeed,\(=\) es una relación de equivalencia en cualquier conjunto\(S\text{,}\) pero también tiene una propiedad muy especial que la mayoría de las relaciones de equivalencia no tienen: es decir, ningún elemento de \(S\)está relacionado con cualquier otro elemento\(S\) de\(=\text{.}\)

Ejemplo\(\PageIndex{3}\)

1. \(\lt\)no es una relación de equivalencia sobre\(\mathbb{R}\) porque no es reflexiva: por ejemplo, tampoco\(3\not\lt 3\text{.}\)\(\leq\) es una relación de equivalencia sobre\(\mathbb{R}\text{,}\) ya que aunque sea reflexiva, no es simétrica: en efecto,\(3\leq 4\) pero\(4\not\leq 3\text{.}\)
2. Dado cualquiera\(n\in \mathbb{Z}^+\text{,}\)\(\equiv_n\) es una relación de equivalencia en\(\mathbb{Z}\text{.}\) La prueba de esto se deja como un ejercicio para el lector.
3. La relación\(R\) sobre\(C^1\) discutida anteriormente (\(fR g\)iff\(f'=g'\)) es una relación de equivalencia sobre\(C^1\text{.}\)
4. \(\simeq\)es una relación de equivalencia en cualquier conjunto de grupos. Esto se desprende del Teorema\(3.3.1\).
5. Definir relación\(R\) sobre\(\mathbb{Z}\) por\(xR y\) si y solo si\(xy \geq 0\text{.}\) Es\(R\) una relación de equivalencia en\(\mathbb{Z}\text{?}\) Bueno, para cada\(x\in \mathbb{Z}\text{,}\)\(x^2\geq 0\text{,}\) así\(R\) es reflexivo. Además, si\(x,y\in \mathbb{Z}\) con\(xy \geq 0\text{,}\) entonces\(yx \geq 0\text{;}\) así\(R\) es simétrico. Pero no\(R\) es transitivo: en efecto,\(3,0,-4\in \mathbb{Z}\) con\(3(0)=0 \geq 0\) y\(0(-4)=0\geq 0\text{,}\) así\(3\mathbb{R} 0\) y\(0 R -4\text{;}\) pero\(3(-4)=-12 \not \geq 0\text{.}\) Así\(R\) no es transitivo, y por lo tanto no es una relación de equivalencia.

Definición: Clase de equivalencia de x por debajo de ~

Dada una relación de equivalencia\(\sim\) en un conjunto\(S\text{,}\) para cada uno\(x\in S\) definimos la clase de equivalencia de\(x\) under\(\sim\) to be

\ begin {ecuación*} [x] =\ {y\ en S\,:\, y\ sim x\}. \ end {ecuación*}

Estos conjuntos clases de\([x]\) (\(x\in S\)) are called the equivalencia de\(S\) menores\(\sim\).

Observación

Tenga en cuenta que, por reflexividad de\(\sim\text{,}\)\(x\in [x]\) para cada\(x\in S\text{.}\)

Tenemos ahora el siguiente Lema Muy Importante:

Lema\(\PageIndex{1}\)

Dejar\(\sim\) ser una relación de equivalencia en conjunto\(S\text{.}\) Entonces para\(x,y\in S\text{,}\) los siguientes son equivalentes:

1. \(y\in [x]\text{;}\)
2. \([x]=[y]\text{;}\)
3. \(x\in [y]\text{.}\)

Prueba

Para probar que las declaraciones primera y segunda son equivalentes: Vamos\(x,y∈S\). Si\(y∈[x]\), entonces\(y\sim x\), así para cada\(z∈[y]\) (es decir, para cada\(z\) en\(S\) con\(z\sim y\)), tenemos, por transitividad\(z\sim x\), así\(z∈[x]\). Por otra parte, por la simetría de que\(\sim\) tenemos\(x\sim y\); así para cada\(z∈[x]\), tenemos, nuevamente por transitividad, eso\(z∈[y]\). Así,\([x]=[y]\). Por el contrario, si\([x]=[y]\), entonces desde\(y∈[y]=[x]\).

La prueba de que las declaraciones segunda y tercera son equivalentes es casi idéntica.

Definición: Representante

En muchos casos hay muchos elementos distintos\(x,y\in S\) con\([x]=[y]\text{;}\) por lo tanto, generalmente hay muchas formas diferentes en las que podríamos denotar una clase de equivalencia particular de\(S\) bajo\(\sim\text{.}\) Element\(y\in S\) se llama un representante de clase\(X\) si\(y\in X\text{.}\)

Para probar que las declaraciones primera y segunda son equivalentes: Let\(x, y\in S\text{.}\) Si\(y\in [x]\text{,}\) entonces\(y \sim x\text{,}\) así para cada\(z\in [y]\) (es decir, para cada\(z\) en\(S\) con\(z\sim y\)), tenemos, por transitividad,\(z\sim x\text{,}\) entonces\(z\in [x]\text{.}\) Por otra parte, por la simetría de\(\sim\) tenemos \(x\sim y\text{;}\)así por cada que\(z\in [x]\text{,}\) tenemos, de nuevo por la transitividad, que\(z\in [y]\text{.}\) Así, Por\([x]=[y]\text{.}\) el contrario, si\([x]=[y]\text{,}\) entonces desde\(y\in [y]=[x]\text{.}\)

La prueba de que las declaraciones segunda y tercera son equivalentes es casi idéntica.

Ejemplo\(\PageIndex{4}\)

1. Consideremos la relación de equivalencia\(\equiv_2\) en\(\mathbb{Z}\text{.}\) Bajo esta relación,\([0]=\{0,\pm 2, \pm 4, \ldots\}\) y\([1]=\{\ldots, -3, -1, 1, 3, \ldots\}\text{;}\) de hecho, si dejamos\(E\) ser el conjunto de todos los enteros pares y\(O\) el conjunto de todos los enteros impares, entonces para\(x\in \mathbb{Z}\text{,}\)\([x]=E\) si\(x\) es par y\(O\) si\(x\) es impar. Por lo tanto, el conjunto de todas las clases de equivalencia de\(\mathbb{Z}\) under\(\equiv_2\) es el conjunto de 2 elementos\(\{E,O\}\text{:}\) cada entero par es un representante de\(E\text{,}\) mientras que cada entero impar es un representante de\(O\text{.}\)

2. Para\(f\in C^1\text{,}\) la clase de equivalencia de\(f\) bajo\(R\) (definido anteriormente) es el conjunto de todas las funciones en\(C^1\) la forma\(g(x)=f(x)+c\text{,}\) donde\(c\in \mathbb{R}\text{.}\)

3. Dejar\(A=\{a,b,c\}\text{,}\) y definir\(\sim\) sobre el conjunto\(P(A)\) de potencia de\(A\) por\(X\sim Y\) si y solo si\(|X|=|Y|\text{.}\) Es sencillo mostrar que\(\sim\) es una relación de equivalencia sobre\(P(A)\text{,}\) la cual\(P(A)\) tiene exactamente 4 clases de equivalencia distintas.

\ begin {equation*} [\ emptyset] =\ {\ emptyset\},\ end {ecuación*}\ begin {ecuación*} [\ {a\}] = [\ {b\}] = [\ {c\}] =\ {\ {a\},\ {b\},\ {c\}\ final {ecuación*}\ comenzar {*} [\ {a, b\}] = [\ {a, c\}] = [\ {b, c\}] =\ {\ {a, b\},\ {a, c\},\ {b, c\}\},\ texto {y}\ final {ecuación*}\ comenzar {ecuación*} [A] =\ {A\}. \ end {ecuación*}

Observación

Observe que el conjunto completo\(\{E,O\}\) de clases de equivalencia distintas de\(\mathbb{Z}\) under\(\equiv_n\) es una partición de\(\mathbb{Z}\text{,}\) y el conjunto completo

\ begin {ecuación*}\ {[\ emptyset], [\ {a\}], [\ {a, b\}], [A]\}\ end {ecuación*}

de distintas clases de equivalencia de\(P(A)\) under \(\sim\) is a partition of \(P(A)\text{.}\) This is not a coincidence! It turns out that equivalence relations and partitions go hand in hand.

Teorema\(\PageIndex{1}\)

\(S\)Déjese ser un conjunto. Entonces:

1. Si\(\sim\) es una relación de equivalencia en\(S\text{,}\) entonces el conjunto de todas las clases de equivalencia de\(S\) bajo\(\sim\) es una partición de\(S\text{;}\) y

2. Si\(P\) es una partición de\(S\text{,}\) entonces la relación en\(S\) definida por\(x\sim y\) si y solo\(x\) está en la misma celda de\(P\) como\(y\) es una relación de equivalencia en\(S\text{.}\)

Observe que en cada caso, las celdas de la partición son las clases de equivalencia del conjunto bajo la relación de equivalencia correspondiente.

Prueba

Para probar la primera afirmación:\(\sim\) Sea una relación de equivalencia sobre\(S\). Claramente, las clases de equivalencia de\(S\) menores\(\sim\) son conjuntos no vacíos cuya unión es\(S\). Así, basta con mostrar\(X∩Y=∅\) por cada par de clases de equivalencia\(X≠Y\) de\(S\) menores\(\sim\). Que\(X,Y\) sean clases de equivalencia de\(S\) menores\(\sim\) que NO sean disjuntas. Entonces existe un elemento\(z∈X∩Y\). Entonces por Lema\(7.1.1\),\([z]=X\) y\([z]=Y\); así\(X=Y\). Así, si\(X≠Y\), entonces\(X∩Y=∅\).

Por último, es sencillo (¡casi tonto!) para demostrar que\(\sim\) es reflexivo, simétrico y transitivo.

Ejemplo\(\PageIndex{5}\)

1. Para\(n\in \mathbb{Z}^+\text{,}\) el conjunto de las clases de equivalencia de\(\mathbb{Z}\) bajo\(\equiv_n\) es la partición\(\{[0],[1],\ldots,[n-1]\}\) de\(\mathbb{Z}\text{.}\) (La partición\(\{E ,O\}\) de\(\mathbb{Z}\) discutida anteriormente es esta partición cuando\(n=2\text{.}\))

Notas

1. Más generalmente, si\(S\) y\(T\) son conjuntos, una relación entre\(S\) y\(T\) es un subconjunto de\(S×T\). No vamos a, sin embargo, en nuestra clase considerar los casos en los que\(S\) y\(T\) son conjuntos diferentes.