Operaciones con conjuntos

Introducción

El objetivo de esta sección es definir las operaciones básicas y mostrar algunas de sus propiedades. Para lo segundo enfatizaremos la estrecha relación que hay entre lógica y conjuntos. Esta relación será de tal forma que las equivalencias lógicas se traducirán a igualdades de conjuntos y las implicaciones lógicas a contenciones.

Operaciones

Empezamos definiendo todas las operaciones que usaremos en esta parte.

Definición

Sean \(A\) y \(B\) dos conjuntos. Definimos las siguientes operaciones:

• intersección, \(A\cap B=\{x\mid x\in A\,\land\, x\in B\}\),
• unión, \(A\cup B=\{x\mid x\in A\,\lor\, x\in B\}\),
• diferencia, \(A\setminus B=\{x\in A\mid x\notin B\}\),
• potencia, \(PA=\{C\mid C\subseteq A\}\).

De la definición es clara la relación que hay, por ejemplo, entre intersección y conjunción. Lo mismo sucede con la unión y la deferencia. En cambio la potencia de un conjunto es una operación de naturaleza completamente diferente. Aún así la incluimos en esta lista para ver cómo se comporta respecto a las otras operaciones.

Uniones e intersecciones

Si consideramos dos proposiciones \(P=(x\in A)\) y \(Q=(x\in B)\) y recordamos que la conjunción es conmutativa, entonces tenemos que \(P\land Q\equiv Q\land P\), lo que se traduce a \((x\in A)\land (x\in B)\equiv(x\in B)\land(x\in A)\). Este último es el argumento que nos permite mostrar que la intersección es conmutativa.

Proposición

Si \(A\) y \(B\) son conjuntos, entonces \(A\cap B=B\cap A\).

Demostración

Haremos doble contención. Además, escribimos las dos contenciones como una sucesión de “si y sólo si” de la siguiente manera,

\[\begin{align*} x\in A\cap B &\iff x\in A \land x\in B && \text{def de intersección}\\ &\iff x\in B \land x\in A && \land\text{ es conmutativo}\\ &\iff x\in B\cap A && \text{def de intersección.} \end{align*}\]

Un ejercicio es enunciar y demostrar la proposición análoga con unión. En la proposición anterior se puede observar que la intersección es conmutativa porque la conjunción lo es. Al demostrar la proposición análoga con unión se observará el mismo comportamiento: la unión es conmutativa porque la disyunción también lo es. Así, si traducimos cualquier equivalencia lógica a operaciones entre conjuntos, obtendremos una igualdad válida. Un ejemplo de esto es una de las leyes distributivas:

\[\begin{equation} \label{eq:dist} P\land(Q\lor R)\equiv (P\land Q)\lor(P\land R). \end{equation}\]

Esta ley se traduce a el siguiente resultado. Además, es común escribir conjunciones del español en lugar de conectivos lógicos.

Proposición

Si \(A\), \(B\) y \(C\) son conjuntos, entonces \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\).

Demostración

Haremos doble contención escrita con una serie de “si y sólo si”.

\[\begin{align*} x\in A\cap(B\cup C) &\iff x\in A \text{ y } x\in B\cup C && \text{def de }\cap\\ &\iff x\in A \text{ y } (x\in B \text{ o } x\in C) && \text{def de }\cup\\ &\iff (x\in A \text{ y } x\in B) \text{ o } (x\in A \text{ y } x\in C) && \text{por \eqref{eq:dist}}\\ &\iff x\in A\cap B \text{ o } x\in A\cap C && \text{def de }\cap\\ &\iff x\in(A\cap B)\cup(A\cap C) && \text{def de }\cup. \end{align*}\]

Otros ejercicios similares se obtienen al considerar otras tautologías. Por ejemplo, si notamos que \(P\land Q\to P\) es una tautología, o de manera equivalente, \(P\land Q\models P\), entonces podemos obtener la siguiente proposición con conjuntos

Proposición

Si \(A\) y \(B\) son conjuntos, entonces \(A\cap B\subseteq A\).

Análogamente, de la tautología \(P\to P\lor Q\), o bien, de \(P\models P\lor Q\), se obtiene la siguiente proposición.

Proposición

Si \(A\) y \(B\) son conjuntos, entonces \(A\subseteq A\cup B\).

Diferencias

La negación no es tan fácil como la conjunción o la disyunción. Por ejemplo, si consideramos el conjunto de números pares \(P=\{x\mid x\in\mathbb{N}\land\exists k\in\mathbb{N}\;(x=2k)\}\) y ponemos una negación, \(\neg(x\in\mathbb{N}\land\exists k\in\mathbb{N}\;(x=2k)\), entonces obtenemos una colección demasiado grande. Además de los números impares, también incluye a los árboles, las personas, etc. Así, la negación debe restringirse a un contexto. Es en este sentido que se define la diferencia de conjuntos.

Cuando nos restringimos a un contexto podemos tener igualdades de conjuntos a partir de equivalencias que incluyen a la negación. Por ejemplo, si consideramos una de las leyes de De Morgan,

\[\begin{equation} \label{eq:dem} \neg(P\land Q)\equiv \neg P\lor\neg Q, \end{equation}\]

entonces obtenemos la siguiente igualdad.

Proposición

Si \(A\), \(B\) y \(C\) son conjuntos, entonces \(A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)\).

Demostración

Haremos doble contención escrita con una serie de “si y sólo si”.

\[\begin{align*} x\in A\setminus(B\cap C) &\iff x\in A \text{ y } x\notin B\cap C && \text{def de }A\setminus -\\ &\iff x\in A \text{ y } \neg(x\in B\text{ y } x\in C) && \text{def de }\notin\\ &\iff x\in A \text{ y } (x\notin B\text{ o } x\notin C) && \text{por \eqref{eq:dem}}\\ &\iff (x\in A \text{ y } x\notin B) \text{ o } (x\in A \text{ y } x\notin C) && \text{por \eqref{eq:dist}}\\ &\iff x\in A\setminus B \text{ o } x\in A\setminus C && \text{def de }A\setminus -\\ &\iff x\in(A\setminus B)\cup(A\setminus C) && \text{def de }\cup. \end{align*}\]

Lo que resta es hacer el ejercicio de enunciar y demostrar las traducciones de equivalencias lógicas a igualdades de conjuntos. En otras palabras, escribir \(\cap\) donde haya \(\land\) y \(\cup\) donde haya \(\lor\).

Potencia de un conjunto

La potencia de un conjunto es una operación que no tiene una equivalencia lógica. Sin embargo, nos da un contexto en el cual tiene sentido hablar de complementos. Además, tiene propiedades interesantes que se pueden relacionar con lógica, órdenes y algunas otras estructuras matemáticas. Recordemos la definición de potencia de un conjunto,

\[PA=\{C\mid C\subseteq A\}.\]

Primero empezamos dando algunos ejemplos de potencias de conjuntos. Por ejemplo, \(P\emptyset=\{\emptyset\}\), \(P\{1\}=\{\emptyset,\{1\}\}\), \(P\{1,2,3\}=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\)

Una pregunta es ¿cuántos elementos tiene la potencia de un conjunto (finito)?

Algo que sí podemos hacer en este momento es ver cómo se comporta la potencia con las operaciones de conjuntos anteriores. Por ejemplo, si consideramos la intersección, entonces ¿podremos mostrar que \(P(A\cap B)=PA\cap PB\)?

Proposición

Si \(A\) y \(B\) son conjuntos, entonces \(P(A\cap B)=PA\cap PB\).

Demostración

De nuevo, haremos doble contención.

\[\begin{align*} C\in P(A\cap B) &\iff C\subseteq A\cap B && \text{def de potencia}\\ &\iff C\subseteq A\land C\subseteq B && \text{proposición anterior}\\ &\iff C\in PA\land C\in PB && \text{def de potencia}\\ &\iff C\in PA\cap PB && \text{def de }\cap. \end{align*}\]

Ahora podemos intentar hacer el ejercicio análogo con la unión. Trataremos de seguir la misma idea para la demostración.

¿Proposición?

Si \(A\) y \(B\) son conjuntos, entonces \(P(A\cup B)=PA\cup PB\).

¿Demostración?

\[\begin{align*} C\in PA \cup PB &\iff (C\in PA) \lor (C\in PB) && \text{def de }\cup\\ &\iff (C\subseteq A) \lor (C\subseteq B) && \text{def de potencia}\\ &\implies C\subseteq A\cup B && \text{proposición anterior}\\ &\iff C\in P(A\cup B) \end{align*}\]

En la demostración se puede observar que hay un paso que no es posible hacer un “si y sólo si”, es decir, sólo se vale la implicación que se deriva de \(A\subseteq A\cup B\) y \(B\subseteq A\cup B\). Sin embargo, la otra implicación no es válida. Así, la proposición correcta debería ser la siguiente.

Proposición

Si \(A\) y \(B\) son conjuntos, entonces \(PA\cup PB\subseteq P(A\cup B)\).

La demostración de arriba funciona como una demostración de la proposición. Además, es posible dar un ejemplo de que la otra contención no es válida. Por ejemplo, si consideramos \(A=\{1\}\) y \(B=\{2\}\), entonces \(P(A\cup B)=\{\emptyset,\{1\},\{2\},\{1,2\}\}\). Sin embargo \(PA\cup PB=\{\emptyset,\{1\},\{2\}\}\). De donde es evidente que no son iguales.

Ahora, ¿cómo se relaciona potencia con diferencias? Esto es, ¿podemos decir a que es igual el conjunto \(P(A\setminus B)\)?

Por último, la potencia nos da un contexto para hablar de complementos. Por ejemplo, si tomamos un conjunto \(X\) y un elemento \(A\in PX\), entonces el complemento de \(A\) será algún \(B\in PX\) tal que \(A\cup B=X\) y \(A\cap B=\emptyset\). Así, el complemento de \(A\) es

\[A^c=X\setminus A.\]

Lo cual significa que hemos restringido el dominio del cual cual tomaremos complemento. En otras palabras, \(X\) es el universo de discurso.

Las propiedades de los complementos son las mismas que las de la diferencia de conjuntos, o bien, las mismas que las de la negación.