Saltar al contenido principal

# 7.1: Particiones y Relaciones de Equivalencia en Conjuntos

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

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.

1. 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{.}$$ 1 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{.}$$

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

This page titled 7.1: Particiones y Relaciones de Equivalencia en Conjuntos is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jessica K. Sklar via source content that was edited to the style and standards of the LibreTexts platform.