De Morgan's Laws for the Intersections and Unions of Sets

Recall from The Relative Complement and Complement of a Set page that if $A$ and $B$ are sets then the relative complement of $A$ with respect to $B$ is $B \setminus A = \{ x : x \in B \: \mathrm{and} \: x \not \in A \}$ and the complement of $A$ with some universal set $U$ in mind is $A^c = \{ x : x \not \in A \}$.

We will now look at some very important theorems regarding the complements of sets that were discovered by Augustus De Morgan and are famously known as De Morgan's laws.

Theorem 1 (De Morgan's Laws): If $A$ and $B$ are sets then: a) $(A \cup B)^c = A^c \cap B^c$. b) $(A \cap B)^c = A^c \cup B^c$.

• Proof of a): Let $x \in (A \cup B)^c$. Then $x \not \in A \cup B$. So $x \not \in A$ and $x \not \in B$, i.e., $x \in A^c \cap B^c$ so $(A \cup B)^c \subseteq A^c \cap B^c$. Now let $x \in A^c \cap B^c$. Then $x \in A^c$ and $x \in B^c$. So $x \not \in A$ and $x \not \in B$, i.e., $x \not \in A \cap B$ so $x \in (A \cap B)^c$ and hence $A^c \cap B^c \subseteq (A \cup B)^c$. Since $(A \cup B)^c \subseteq A^c \cap B^c$ and $(A \cup B)^c \supseteq A^c \cap B^c$ we conclude that $(A \cup B)^c = A^c \cap B^c$. $\blacksquare$

• Proof of b): Let $x \in (A \cap B)^c$. Then $x \not \in A \cap B$, so $x \not \in A$ and $x \not \in B$. Therefore $x \in A^c$ or $x \in B^c$, i.e., $x \in A^c \cup B^c$ so $(A \cap B)^c \subseteq A^c \cup B^c$. Now let $x \in A^c \cup B^c$. Then $x \in A^c$ or $x \in B^c$ so $x \not \in A$ and $x \not \in B$, i.e., $x \not \in A \cap B$ so $x \in (A \cap B)^c$. Therefore $A^c \cup B^c \subseteq (A \cap B)^c$. Since $(A \cap B)^c \subseteq A^c \cup B^c$ and $(A \cap B)^c \supseteq A^c \cup B^c$ we conclude that $(A \cap B)^c = A^c \cup B^c$. $\blacksquare$

De Morgan's Laws can also be generalized as we see in the following theorem.

Theorem 2 (Generalized De Morgan's Laws): If $\{ A_i \}_{i \in I}$ is a collection of sets where $I$ is some indexing set then: a) $\displaystyle{\left ( \bigcup_{i \in I} A_i \right )^c = \bigcap_{i \in I} A_i^c}$. b) $\displaystyle{\left ( \bigcap_{i \in I} A_i \right )^c = \bigcup_{i \in I} A_i^c}$.