De Morgan’s formulas set theory

elementary-set-theory

De Morgan Formulas

I can't seem to wrap my head around these two formulas. I don't know whether it's that I don't understand the union and intersection of elements of gamma being put into set A. Or either that I don't understand how the distributive property works in these kind of problems. If anyone could please help it would be greatly appreciated, thanks.

Best Answer

Elements of $\Gamma$ aren’t being put into sets $A$: the sets $A$ in the expressions are elements of $\Gamma$: $\Gamma$ is simply a collection of sets.

It may help to work through the reasoning showing that one of these identities is true, illustrating it with a small example. Let’s take the first one,

$$X\setminus\bigcup_{A\in\Gamma}A=\bigcap_{A\in\Gamma}(X\setminus A)\;.\tag{1}$$

The lefthand side is the set of all members of $X$ that are not in any of the sets in the collection $\Gamma$.

  • For instance, if $\Gamma=\{A_1,A_2,A_3\}$, the lefthand side is $X\setminus(A_1\cup A_2\cup A_3)$, the set of all members of $X$ that are not in any of the sets $A_1,A_2$, and $A_3$.

Suppose that $x$ is such a member of $X$, i.e., that $x\in X\setminus\bigcup_{A\in\Gamma}A$; then $x$ is not in any of the members of $\Gamma$, so if $A\in\Gamma$, we know that $x\notin A$. But $x\in X$, so $x\in X\setminus A$. That’s true for every $A\in\Gamma$, so $x$ is in all of the sets $X\setminus A$ and is therefore in their intersection: $$x\in\bigcap_{A\in\Gamma}(X\setminus A)\;.$$

  • In terms of the small example above, $x\in X$, but $x\notin A_1$, $x\notin A_2$, and $x\notin A_3$, so $x\in X\setminus A_1$, $x\in X\setminus A_2$, and $x\in X\setminus A_3$. But then $x$ must be in the intersection of these three sets: $x\in\bigcap_{i=1}^3(X\setminus A_i)=\bigcap_{A\in\Gamma}(X\setminus A)$.

This shows that in general

$$X\setminus\bigcup_{A\in\Gamma}A\subseteq\bigcap_{A\in\Gamma}(X\setminus A)\;.$$

Now suppose that $x\in\bigcap_{A\in\Gamma}(X\setminus A)$. This just says that for every set $A$ in the collection $\Gamma$, $x\in X\setminus A$: that is, $x$ is in $X$ but not in $A$. This clearly implies that $x\in X$. It also implies that $x$ is not in the union of all of the sets $A$ in the collection $\Gamma$, since it’s not in any of those sets. That is, $x\in X$, but $x\notin\bigcup_{A\in\Gamma}A$, so $x\in X\setminus\bigcup_{A\in\Gamma}A$.

  • Again in terms of the small example, $x$ is in each of the sets $X\setminus A_1$, $X\setminus A_2$, and $X\setminus A_3$, so $x\in X$, but $x\notin A_1$, $x\notin A_2$, and $x\notin A_3$. Thus, $x\in X$, but $x\notin A_1\cup A_2\cup A_3=\bigcup_{A\in\Gamma}A$, so $x\in X\setminus\bigcup_{A\in\Gamma}A$.

This shows that in general

$$\bigcap_{A\in\Gamma}(X\setminus A)\subseteq X\setminus\bigcup_{A\in\Gamma}A\;,$$

which completes the proof of $(1)$.

You might find it helpful to draw a Venn diagram for the small example that I used.

Related Question