Proof of De Morgan's laws for sets

Proof

We show that each side has the same elements as the other. Two sets with the same elements are equal, by the axiom of extensionality.

1. Let $U$ be a set, let $A, B \subseteq U$, and write $X^c = U \setminus X$ for the complement of $X \subseteq U$.
2. Let $x$ be an object. By the definitions of complement and union, $x \in (A \cup B)^c$ holds exactly when $x \in U$ and $\neg (x \in A \lor x \in B)$.
3. By the first of De Morgan's laws, $\neg (x \in A \lor x \in B)$ is equivalent to $x \notin A \land x \notin B$.
4. So $x \in (A \cup B)^c$ holds exactly when $x \in U$, $x \notin A$ and $x \notin B$. This says $x \in A^c$ and $x \in B^c$.
5. By the definition of intersection, step 4 says that $x \in (A \cup B)^c$ holds exactly when $x \in A^c \cap B^c$. Hence $(A \cup B)^c = A^c \cap B^c$.
6. By the definitions of complement and intersection, $x \in (A \cap B)^c$ holds exactly when $x \in U$ and $\neg (x \in A \land x \in B)$.
7. By the second of De Morgan's laws, $\neg (x \in A \land x \in B)$ is equivalent to $x \notin A \lor x \notin B$.
8. So $x \in (A \cap B)^c$ holds exactly when $x \in U$, and $x \notin A$ or $x \notin B$. This says $x \in A^c$ or $x \in B^c$.
9. By the definition of union, step 8 says that $x \in (A \cap B)^c$ holds exactly when $x \in A^c \cup B^c$. Hence $(A \cap B)^c = A^c \cup B^c$.