---
tag: 64395G4VWB
kind: proof
name: Proof of De Morgan's laws for sets
msc: ["03E20"]
proves: 0VK0W4D5Y5
uses: [0SJ3RX9TXA, 0TB16T2C97, 0B1FSS1VZW, 07KVB4JSC7, 0HBRW4E6G1, 09PKJKA6J0]
sources:
  - url: https://en.wikipedia.org/wiki/De_Morgan's_laws
    locator: Proof for set theory
---

## Proof

We show that each side has the same elements as the other. Two [[sets|0SJ3RX9TXA]] with the same elements are equal, by the [[axiom of extensionality|0TB16T2C97]].

1. Let $U$ be a set, let $A, B \subseteq U$, and write $X^c = U \setminus X$ for the [[complement|0B1FSS1VZW]] of $X \subseteq U$.
2. Let $x$ be an object. By the definitions of complement and [[union|07KVB4JSC7]], $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|09PKJKA6J0]], $\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|0HBRW4E6G1]], 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$.

## Idea

Complement means "not", union means "or" and intersection means "and". Written for one element, each set law becomes one of De Morgan's laws of logic.