Particiones

Definición 124 (Partición)   Sea $X$ un conjunto. $P$ es una partición de $X$ si y sólo si:

1. $\varnothing \not\in P$.
2. $\bigcup P = A$.
3. Los conjuntos de $P$ son disyuntos 2 a 2, es decir, si $S_{1}, S_{2} \in P$ y $S_{1} \not= S_{2}$, entonces $S_{1} \cap S_{2} = \varnothing$.

Observe que si $P$ es una partición de $X$, entonces todo elemento de $X$ está en uno y sólo un elemento $S \in P$, de modo que $P$ parte a $X$ en conjuntos disyuntos. Por ejemplo, el conjunto de barriles propuesto al comienzo de la sección es una partición del conjunto de mangos. Otro ejemplo de una partición es de la división política de un país: El país (visto como un conjunto de personas) se parte en estados o departamentos no vacíos disyuntos entre sí.

Ejemplo 125   Sea $X = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$. Entonces $P = \{ \{ 1, 9 \}, \{ 2, 8 \}, \{ 3, 4, 5, 6, 7 \} \}$ es una partición de $X$ en tres conjuntos: elementos externos ($1, 9$), elementos semi-externos ($2, 8$) y elementos internos ( $3, 4, 5, 6, 7$). Note que $Q = \{ \{ 1, 2, 9 \}, \{ 2, 8 \}, \{ 3, 4, 5, 6, 7 \} \}$ no es partición de $X$ (¿por qué?).

Como lo habíamos insinuado, resulta que toda relación de equivalencia determina de manera natural una partición:

Teorema 126 (Relación de equivalencia $\leadsto$ partición)   Sea $X$ un conjunto no vacío, y $\sim$ una relación de equivalencia sobre $X$. Entonces $X/\sim$ es una partición de $X$.

Demostración. [Prueba]

Sea $P = X/\sim$. Veamos que $P$ es una partición de $X$. Como existe $a \in X$, $[a] \in P$, luego $P \not= \varnothing$. Además:

1. $\varnothing \not\in P$: Esto se tiene pues si $a \in X$, entonces $a \in [a]$.

2. $\bigcup P = X$: Si $a \in \bigcup P$, existe $[b] \in P$ tal que $a \in [b]$, y esto implica $a \in X$. Para la otra inclusión, si $a \in X$, entonces $a \in [a] \in P$, e.d., $a \in \bigcup P$.

3. Los elementos de $P$ son disyuntos 2 a 2: Si $[a], [b] \in P$ y $[a] \not= [b]$, por el lema 123, $[a]$ y $[b]$ son disyuntos.

$\qedsymbol$

Figura 5.1: Si $\sim$ es una relación de equivalencia sobre $X$ conjunto no vacío, $X/\sim$ es una partición de $X$.

La figura 5.1 ilustra el teorema anterior: en ella, $X$ es un conjunto de $7$ elementos, mientras que la partición $X/\sim = \{ [a], [b], [c]\}$ tiene tan sólo $3$ elementos.

La moraleja es: toda relación de equivalencia sobre $X$ ``genera'' una partición sobre $X$. Como veremos a continuación, el fenómeno inverso ocurre también: toda partición genera de manera natural una relación de equivalencia:

Teorema 127 (Partición $\leadsto$ relación de equivalencia)   Dada $P$ una partición de $X$, defina en $X$ la relación $R_{P}$ así:

$$aR_{P}b$$    si y sólo si existe $S &isin#in;P$ tal que $$a, b \in S$$

Entonces $R_{S}$ es una relación de equivalencia.

Demostración. [Prueba]

Sea $\sim \; = R_{P}$. Verifiquemos que $\sim$ es reflexiva, simétrica y transitiva:

1. Reflexividad: Sea $a \in X$. Como $\bigcup P = X$, existe $S \in P$ tal que $a \in S$. Entonces $a, a \in S$, luego $a \sim a$.

2. Simetría: Si $a \sim b$, existe $S \in P$ tal que $a, b \in S$, que es lo mismo que decir $b, a \in S$, y esto prueba que $b \sim a$.

3. Transitividad: Suponga $a \sim b$ y $b \sim c$, y sean $S, T \in P$ tales que $a, b \in S$, $b, c \in T$. Como $P$ es una partición y $S \cap T \not= \varnothing$, $S = T$, de modo que $a, c \in S$, y esto prueba que $a \sim c$.

$\qedsymbol$

Los teoremas anteriores nos permiten pensar en particiones como relaciones de equivalencia y viceversa. Además las traducciones dadas son mutuamente inversas:

Teorema 128   Para $X$ un conjunto, $P$ una partición de $X$ y $\sim$ relación de equivalencia sobre $X$:

(a)

$X / R_{P} = P$.

(b)

$R_{X / \sim} = \sim$.

Demostración. [Prueba]Demostramos (a) y (b) por doble inclusión:

(a)

``$\subseteq$'': Sea $[ a ]_{ R_{P} } = [ a ] \in X / R_{ P }$, y sea $S \in P$ tal que $a \in S$. Veamos que $[a] = S$ pore doble inclusión: si $b \in [a]$, entonces $a R_{P} b$, luego $a, b \in T$ para algún $T \in S$. Entonces $S \cap T \neq \varnothing$, luego $S = T$, y así $b \in S$. Para la otra inclusión, si $b \in S$, entonces $a, b \in S \in P$, luego $a R_{P} b$, es decir, $b \in [a]$.

``$\supseteq$'': Sea $S \in P$. Tome $a \in S$ (¿por qué existe?); es fácil verificar (se deja al lector) que $S = [a]_{R_{P}}$, luego $S \in X / R_{P}$.

(b)

Mostramos que para todo $x, y \in X$, $(x, y) \in R_{X / \sim }$ si y sólo si $(x, y) \in \sim$:

$$\begin{array}{lll} (x, y) \in R_{X / \sim} & \leftrightarrow & \e... ... \exists a \in X : x, y \sim a \\ & \leftrightarrow & x \sim y \\ \end{array}$$

El lector debe ser capaz de justificar claramente cada una de las anteriores equivalencias.

$\qedsymbol$

Finalmente introducimos la noción de conjunto de representantes de una partición:

Definición 129 (Conjunto de representantes)   Sea $P$ una partición de $X$. Diremos que $C$ es un conjunto de representantes de $P$ si y sólo si $C \subseteq X$ y para todo $S \in P$, $S \cap C = \{ a\}$ para algún $a \in X$.

Como su nombre lo indica, un conjunto de representantes está formado por exactamente un elemento (representante) de cada elemento de la partición. La anterior definición puede darse también pensando en relaciones de equivalencia: $C$ es un conjunto de representantes para la relación de equivalencia $R$ (sobre $X$) si y sólo si $C$ es un conjunto de representantes de $X/R$. Veamos algunos ejemplos.

Ejemplo 130 (Conjuntos de representantes)  

1. $A$ es un conjunto de representantes para la relación $Id_{A}$.

2. Para la relación $\equiv_{2}$ sobre $\mathbb{Z}$, los siguientes son conjuntos de representantes: $\{ 0, 1 \}$, $\{0, 3\}$, $\{-10, 5\}$, $\{100, -3\}$, $\{7, 6\}$, $\{21, -2\}$, etc.

3. Para la relación $R_{f}$ un conjunto de representantes es el siguiente: dado $y \in Im(f)$, escoja un $x_{y} \in X$ tal que $f(x_{y}) = y$. El conjunto $C = \{ x_{y} : y \in Im(f) \} \subseteq X$ es un conjunto de representantes para $R_{f}$: para $[a] \in X/R_{f}$, si $b \in [a]\cap C$, entonces $f(b) = f(a)$ y $b = x_{y}$ para un $y \in Im(f)$. Pero entonces $f(a) = f(x_{y}) = y$, luego $b = x_{f(a)}$. Además es claro que $x_{f(a)} \in [a]\cap C$, de modo que $[a] \cap C = \{ x_{f(a)} \}$.

El lector podrá notar que si $C$ es un conjunto de representantes de $P$, entonces $C$ y $P$ ``poseen el mismo tamaño''.