Operaciones básicas entre conjuntos

Intuitivamente un álgebra es una estructura en donde ciertos objetos de un conjunto base se combinan por medio de distintas operaciones para formar elementos del mismo conjunto base. Tome, por ejemplo, la estructura de los números náturales. El conjunto base es en este caso el conjunto de los números naturales, y hay varias operaciones, como por ejemplo la suma. Si operamos mediante la suma al $2$ y al $3$, obtendremos el número $2 + 3 = 5$. Estudiar un álgebra significa estudiar las propiedades de las operaciones. Por ejemplo, para el caso anterior, sabemos que una propiedad fundamental de la suma es la conmutatividad: para todos $x, y$, $x + y = y + x$.

Lo importante del álgebra es que le da estructura a un conjunto. Una cosa es representarse a los naturales como simples elementos aislados entre sí, y otra cosa muy distinta es pensar en ellos como estructura compleja, en donde ellos se combinan entre sí. En el primer caso, el $0$ y el $5$ son esencialmente lo mismo. En el segundo caso el $0$ es más interesante que el $5$, ya que posee una característica especial: para todo $x$, $x + 0 = x$ (esto lo expresamos diciendo que $0$ es neutro con respecto a la suma).

En general, una operación $n$-aria $O$ es una regla que le asigna a $n$ elementos $a_{1}, \ldots, a_{n}$ cierto elemento, que llamamos $O(a_{1}, \ldots, a_{n})$. Los siguientes son algunos ejemplos de operaciones $n$-arias:

1. Sea $S(x) = x + 1$, para $x$ un número natural. $S$ es una operación unaria ($n = 1$).

2. Sea $E(x, y) = x + y$, para $x, y$ números enteros. $E$ es una operación binaria ($n = 2$), y por ejemplo, $S(2, 5) = 7$.

En esta sección presentamos un álgebra para los conjuntos, esto es, decribimos ciertas operaciones entre conjuntos y estudiamos sus propiedades.

Definición 8 (Unión)   Si $A$ y $B$ son conjuntos, definimos el conjunto $A \cup B = \{ x : x \in A$ o $x \in B \}$. Es decir, para todo $x$, $x \in A \cup B \leftrightarrow (x \in A \vee x \in B)$.

Definición 9 (Intersección)   Si $A$ y $B$ son conjuntos, definimos el conjunto $A \cap B = \{ x : x \in A$ y $x \in B \}$. Es decir, para todo $x$, $x \in A \cup B \leftrightarrow (x \in A \wedge x \in B)$.

Diremos que $A$ y $B$ son disyuntos si no comparten elementos (es decir, si $A \cap B = \varnothing$).

Ejemplo 10   Sea $A = \{ 0, 2, 3, 5 \}$, $B = \{ 2, 5, 3, 9 \}$ y $C = \{ 0, 1 \}$. Tenemos:

1. $A \cup B = \{ 0, 2, 3, 5, 9 \}$, y $B \cup C = \{ 0, 1, 2, 3, 5, 9 \}$.
2. $A \cap B = \{ 2, 5 \}$ y $A \cap C = \{ 0 \}$.
3. $B$ y $C$ son conjuntos disyuntos.

Para antes de seguir leyendo:

1. Si $A$ posee cuatro elementos y $B$ posee cinco elementos, ¿cuántos elementos como máximo posee $A \cup B$? ¿Y como mínimo?
2. Si $A$ posee $n_{ A }$ elementos y $B$ posee $n_{ B }$ elementos, ¿cuántos elementos como máximo posee $A \cap B$? ¿Y como mínimo?
3. ¿Existe un conjunto disyunto de sí mismo?
4. Si $A$ y $B$ son disyuntos y $B$ y $C$ son disyuntos, ¿puede concluirse que $A$ y $C$ son disyuntos?

Las siguientes propiedades básicas de la unión y la intersección son evidentes y descansan en las propiedades lógicas de $\vee$ y de $\wedge$:

Lema 11   Para cualquier par de conjuntos $A$ y $B$ valen las siguientes propiedades:

1. Idempotencia: $A \cup A = A$ ; $A \cap A = A$.

2. Conmutatividad: $A \cup B = B \cup A$ ; $A \cup B = B \cup A$.

3. Asociatividad: $(A \cup B) \cup C = A \cup (B \cup C)$ ; $(A \cap B) \cap C = A \cap (B \cap C)$.

4. $A \cup \varnothing = A$ ; $A \cap \varnothing = \varnothing$.

5. $A \subseteq A \cup B$ ; $A \cap B \subseteq A$.

6. $B \subseteq A$ si y sólo si $A \cup B = A$ ; $B \subseteq A$ si y sólo si $A \cap B = B$.

Demostración. [Prueba]

Mostremos, por ejemplo, la primera parte de la última propiedad (las otras pruebas son semejantes y se dejan al lector).

`` $\rightarrow$'': Sea $B \subseteq A$. Hay que mostrar $A \cup B = A$. Utilicemos el principio de la doble inclusión: ``$\subseteq$'': Si $x \in A \cup B$, entonces como todo elemento de $B$ es elemento de $A$, necesariamente $x \in A$.

``$\supseteq$'': Si $x \in A$, entonces $x \in A \cup B$ por propiedad 5.

`` $\leftarrow$'': Supongamos $A \cup B = A$. Debemos probar $B \subseteq A$. Sea $x \in B$. Entonces $x \in A \cup B$, pero por hipótesis este conjunto es $A$, luego $x \in A$ y terminamos. $\qedsymbol$

$\cup$ es una operación binaria. Por esto, una expresión de la forma $A \cup B \cup C$ en principio es ambigüa y debe traducirse a $(A \cup B) \cup C$ ó $A \cup (B \cup C)$. Pero en virtud del lema anterior ambas expresiones denotan el mismo conjunto, y por lo tanto definimos $A \cup B \cup C$ como $(A \cup B) \cup C$ (o $A \cup (B \cup C)$!). Por supuesto la observación anterior también vale si cambiamos $\cup$ por $\cap$.

Si uno se encuentra con una expresión de la forma $A \cup B \cup C$, puede transformarla en $(A \cup B) \cup C$ o en $A \cup (B \cup C)$, según le convenga. A continuación un ejemplo:

Ejemplo 12   Muestre que $(W \cup X \cup Y) \cup Z = (W \cup X) \cup (Y \cup Z)$.

Demostración. [Solución]

$(W \cup X \cup Y) \cup Z = ((W \cup X) \cup Y) \cup Z = (W \cup X) \cup (Y \cup Z)$, la última igualdad valiendo por asociatividad. $\qedsymbol$

Ahora avanzamos un poco más, y comenzamos a relacionar la unión con la intersección mediante las llamadas leyes de la distribución:

Lema 13 (Distribución)   Para $A$, $B$ y $C$ conjuntos:

1. $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$.

2. $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$.

Demostración. [Prueba] (1): Lo mostramos utilizando doble inclusión: ``$\subseteq$'': Sea $x \in (A \cup B) \cap C$. Entonces $x \in A \cup B$ y $x \in C$. Por lo primero, $x \in A$ o $x \in B$. Si $x \in A$, entonces $x \in A \cap C$. Si $x \in B$, entonces $x \in B \cap C$. Luego $x \in A \cap C$ o $x \in B \cap C$, es decir, $x \in (A \cap C) \cup (B \cap C)$.

``$\supseteq$'': Sea $x \in (A \cap C) \cup (B \cap C)$. Entonces $x \in A \cap C$ o $x \in A \cap C$. En el primer caso, como $x \in A$, entonces $x \in A \cup B$, luego $x \in (A \cup B) \cap C$. En el segundo caso, como $x \in B$, entonces $x \in A \cup B$, luego $x \in (A \cup B) \cap C$. En cualquier caso, $x \in (A \cup B) \cap C$.
(2): La prueba es similar a (1) y se deja para el lector. $\qedsymbol$

Figura: Unión e intersección

Así como podemos restar números, podemos restar conjuntos, de una manera natural:

Definición 14 (diferencia)   Para $A$ y $B$ conjuntos, definimos su diferencia como el conjunto $A \smallsetminus B = \{ x \in A : x \not\in B\}$. Por lo tanto, para todo $x$, $x \in A \smallsetminus B \leftrightarrow (x \in A\wedge x \not\in B)$. $A \smallsetminus B$ se denomina ``$A$ menos $B$''.

Algunos ejemplos:

1. $\{ 1, a, 2, b, 3, c, 4, d \} \smallsetminus \{ 1, b, c, 4 \} = \{a, 2, 3, d\}$.

2. Si $A = \{ 0, 4, 7, 10 \}$ y $B = \{ 3, 4, 8, 10, 12 \}$, entonces $A \smallsetminus B = \{ 0, 7 \}$.

3. Si $A$ y $B$ son disyuntos, entonces $A \smallsetminus B = A$. (¿Por qué?).

4. Pregunta: ¿Es cierto que $(A \cup B) \smallsetminus B = A$ (para cualquier par de conjuntos $A$ y $B$ )?

Dado un conjunto $A$, el conjunto de todos sus elementos es $A$ mismo: $\{ x : x \in A \} = A$. Pero el conjunto de todos sus subconjuntos resulta ser muy distinto, como se verá más adelante.

Definición 15 (Conjunto partes)   Dado $A$ un conjunto, definimos el conjunto $\mathcal{P}(A) = \{S : S \subseteq A \}$. Esto es, para todo $S$, $S \in \mathcal{P}(A) \leftrightarrow S \subseteq A$. $\mathcal{P}(A)$ suele llamarse tambien el conjunto potencias de $A$.

Ejemplo 16 (Algunos ejemplos del conjunto potencias)  

1. $\varnothing \in \mathcal{P}(A)$, para cualquier A.

2. $\mathcal{P}(\varnothing) = \{ \varnothing \}$: para ver esto, basta preguntarse qué conjunto $S$ es candidato a ser subconjunto de $\varnothing$: Si $S$ posee al menos un elemento $a$, entonces $a \not\in \varnothing$, y por ende $S \not\subseteq \varnothing$. Por otro lado, $\varnothing$ es subconjunto de cualquier conjunto, en particular de él mismo.

3. Sea $A_{1} = \{ 1 \}$. $A_{1}$ tiene $1$ elemento. $\mathcal{P}(A_{1}) = \{ \varnothing, \{1\} \}$. $\mathcal{P}(A_{1})$ tiene $2$ elementos.

4. Sea $A_{2} = \{ 1, 2 \}$. $A_{2}$ tiene $2$ elementos. $\mathcal{P}(A_{2}) = \{ \varnothing, \{1\}, \{2\}, \{1, 2\} \}$. $\mathcal{P}(A_{2})$ tiene $4$ elementos.

5. Sea $A_{3} = \{ 1, 2, 3 \}$. $A_{3}$ tiene $3$ elementos. $\mathcal{P}(A_{3}) = \{ \varnothing, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\},$ $\{1, 3\}, \{1, 2, 3\} \}$. $\mathcal{P}(A_{3})$ tiene $8$ elementos.

Figura: Distintas representaciones del conjunto $\mathcal{P}(\{1, 2, 3 \})$. La primera consiste en un diagrama de Venn. En la segunda se construye el retículo en donde se pintan líneas siempre que haya contenencia (sin pintar, por supuesto, todas las líneas posibles). En la tercera se asocia a cada conjunto $A \in \mathcal{P}(\{1, 2, 3 \})$ una sucesión ordenada de ceros y unos, en donde se coloca un $1$ en la posición $i$ si y sólo si $i \in A$ (así por ejemplo, a $\varnothing$ se le asocia la sucesión $000$).

Ahora tomamos un conjunto $\mathcal{U}$ y trabajamos en $\mathcal{P}(\mathcal{U})$; esto significa que todos los conjuntos que consideremos serán subconjuntos de $\mathcal{U}$. Llamaremos a $\mathcal{U}$ nuestro universo de discurso, o simplemente el universo . Esto nos permite definir el complemento de un conjunto $A$:

Definición 17 (complemento)   Para un conjunto $A \subseteq \mathcal{U}$, definimos su complemento $A^{c} = \mathcal{U} \smallsetminus A$. Note que $A^{c} \subseteq \mathcal{U}$.

Algunos autores suelen notar $A^{c}$ por $A'$, $\bar{A}$ o incluso $\sim \! A$. Note que para cualquier $A \subseteq \mathcal{U}$, $\mathcal{U}$ se puede escribir como la unión disyunta de $A$ y su complemento, esto es, (1) $A \cup A^{c} = \mathcal{U}$ y (2) $A \cap A^{c} = \varnothing$. Para mostrar (1) utilizamos doble inclusión: Si $x \in A \cup A^{c}$, dado que tanto $A$ como $A^{c}$ son subconjuntos de $\mathcal{U}$, entonces $x \in \mathcal{U}$. Ahora, sea $x \in \mathcal{U}$. Hay dos casos: si $x \in A$, entonces $x \in A \cup A^{c}$. Si por el contrario $x \not\in A$, entonces (por definición de complemento) $x \in A^{c}$, luego $x \in A \cup A^{c}$. Mostremos ahora (2) por contradicción: si $A \cap A^{c} \neq \varnothing$, entonces existe $x \in A \cap A^{c}$. Pero entonces $x \in A$ y $x \not\in A$, lo cual es una contradicción. Se concluye $A \cap A^{c} = \varnothing$.

Algunas propiedades del complemento:

Lema 18   Para $A$, $B$ subconjuntos de $\mathcal{U}$:

1. $A \smallsetminus B = A \cap B^{c}$.

2. $(A^{c})^{c} = A$ (doble complemento).

3. $A \subseteq B$, si y sólo si $B^{c} \subseteq A^{c}$.

Demostración. [Prueba] (1): Para $x$ arbitrario, $x \in A \smallsetminus B$ si y sólo si ($x \in A$ y $x \not\in B$) si y sólo si $x \in A \cap B_{c}$.

(2): Si $x \in (A^{c})^{c}$, entonces $x \in \mathcal{U} = A \cup A^{c}$ y $x \not\in A^{c}$, luego necesariamente $x \in A$. Ahora, si $x \in A$, entonces $x \in \mathcal{U}$. Pero además $x \not\in A^{c}$ (de lo contrario se tendría $x \not\in A$), y entonces (por definición de complemento), $x \in (A^{c})^{c}$.

(3): `` $\rightarrow$'' : Suponga que $A \subseteq B$. Hay que mostrar que $B^{c} \subseteq A^{c}$. Sea $x \in B^{c}$. Entonces $x \in \mathcal{U}$ y $x \not\in B$. Este último hecho más la hipótesis implican que $x \not\in A$ (o de lo contrario $x$ sería elemento de $B$).

`` $\leftarrow$'' : Suponga que $B^{c} \subseteq A^{c}$. Por la implicación que acabamos de mostrar (donde $B^{c}$ juega el papel de $A$ y $A^{c}$ el de $B$) se tiene que $(A^{c})^{c} \subseteq (B^{c})^{c}$, y esto más (1) garantizan el resultado. $\qedsymbol$

Note que la prueba de (1) no fue descompuesta en dos inclusiones, como de costumbre, sino que consistió en mostrar directamente que pertenecer al primer conjunto equivalía a pertenecer al segundo (luego al ambos conjuntos tener los mismos elementos, deben ser iguales). Quien no haya quedado convencido de esta prueba puede hacer otra utilizando doble inclusión, y después volver a revisar la que hemos presentado. Pese a la elegancia del método directo, el lector se dará cuenta con el tiempo de que muchas pruebas de igualdad de conjuntos deben hacerse utilizando la doble inclusión.

Teorema 19 (Leyes de De Morgan)   Para $A, B \subseteq \mathcal{U}$:

1. $(A \cup B)^{c} = A^{c} \cap B^{c}$ (el complemento de la unión es la intersección de los complementos).

2. $(A \cap B)^{c} = A^{c} \cup B^{c}$ (el complemento de la intersección es la unión de los complementos).

Demostración. [Prueba] La prueba de (1) se deja al lector, y probamos (2): Si $x \in (A \cap B)^{c}$, entonces $x \in \mathcal{U}$ y $x \not\in A \cap B$; pero esto último implica $x \not\in A$ ó $x \not\in B$. Por ende, necesariamente $x \in A^{c}$ ó $x \in B^{c}$, ésto es, $x \in A^{c} \cup B^{c}$.

Si $x \in A^{c} \cup B^{c}$, entonces (i) $x \in A^{c}$, ó (ii) $x \in B^{c}$. En el caso (i), $x \in \mathcal{U}$ y $x \not\in A$, luego $x \not\in A \cap B$. En el caso (ii), $x \in \mathcal{U}$ y $x \not\in B$, luego $x \not\in A \cap B$. Por lo tanto $x \in \mathcal{U}$ y $x \not\in A \cap B$, e.d., $(A \cap B)^{c}$. $\qedsymbol$

Imagine ahora la siguiente situación: se le entregan dos conjuntos $A$ y $B$ y usted debe decidir cómo se relacionan entre sí. Hay varias posibilidades:

1. $A \subseteq B$ pero $B \not\subseteq A$, es decir, $A \subset B$ ($A$ es subconjunto propio de $B$).

2. $B \subseteq A$ pero $A \not\subseteq B$ (es decir, $B \subset A$).

3. $A \subseteq B$ y $B \subseteq A$: en este caso, $A = B$.

4. $A \not\subseteq B$ y $B \not\subseteq A$: en este caso diremos que $A$ y $B$ no son comparables (entre sí).

Figura 2.3: Dados dos conjuntos $A$ y $B$, ocurre una y sólo una de estas cuatro posibilidades.