De Morgan's formulas set theory

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.

For sets, $S=T$ means $x\in S$ and $x\in T$ are equivalent statements. So think about what those statements mean. In (3), they're different ways of saying $x$ is in $X$ but none of the $A\in\Gamma$; we can think of this instead as "for each such $A$, it's in $X$ but not that $A$". Similarly (4) gives two ways to say $x$ is in $X$ but not all if the $A\in\Gamma$, i.e. there is an $A$ such that $x\notin A$.

The notion of a family of subsets is abstract and you have to work with quantifiers here. So if you can't 'wrap your head around' something, try writing things out in English and 'scaling down' to something more concrete.

Statement 1: $\Gamma$ is a family of subsets of $X$.

Concretization 2: Let $A$ and $B$ be two subsets of $X$.

Concretization 3: Let $\Gamma$ contain only $A$ and $B$.

For this less abstract scale down we write out,

$\tag 1 \displaystyle { X \, \setminus \bigcup_{\gamma \in \Gamma} \; \gamma= X \, \setminus (A \cup B)}$

and we're left looking at

$\tag 2 \displaystyle{X \, \setminus (A \cup B) = \bigcap_{\gamma \in \Gamma} \; X \, \setminus \gamma = (X \setminus A) \, \bigcap \, (X \setminus B)} $

Statement 4: The lhs of $\text{(2)}$ is obtained by removing from $X$ all the elements that are in $A$ or $B$.

Statement 5: (a bit long-winded):
The rhs of $\text{(2)}$ is obtained by by gathering all elements $X$ that belong to each of two sets.
The first set $X \setminus A$ is obtained by removing from $X$ all the elements that are in $A$.
The second set $X \setminus B$ is obtained by removing from $X$ all the elements that are in $B$.
Intersection 'means' $\text{AND}$.
Any element belonging to this intersection can't belong to $A$ nor can it belong to $B$.

Statement 6: So statements 4 and 5 describe the same thing by logic: if $p$ and $q$ are statements then

$\tag 3 \lnot (p \lor q) \equiv \lnot p \land \lnot q$