Complement and De Morgan's laws

Once we fix a universal set $U$, every subset $A \subseteq U$ has a natural partner , the set of all elements of $U$ that are not in $A$. This is the complement. It looks innocent, but it is the operation that lets us flip "everyone who plays cricket" into "everyone who does not play cricket" , and the two De Morgan laws tell us how complement interacts with union and intersection.

Definitions

Fix a universal set $U$. For $A \subseteq U$, the complement of $A$ in $U$ is $A' = U - A = \{x \in U : x \notin A\}.$ Other common notations: $A^c$, $\overline{A}$, $\complement_U A$. In a Venn diagram, $A'$ is everything inside the rectangle but outside the circle for $A$.

Properties of complement

Let $A, B \subseteq U$.

1. Double complement: $(A')' = A$.
2. Universal: $\varnothing' = U$, $U' = \varnothing$.
3. Self-disjointness: $A \cap A' = \varnothing$.
4. Cover: $A \cup A' = U$.
5. Reversal of inclusion: if $A \subseteq B$ then $B' \subseteq A'$.
6. Difference via complement: $A - B = A \cap B'$.

All can be checked element by element. For (5): if $A \subseteq B$ and $x \in B'$, then $x \notin B$, hence $x \notin A$ (since $A \subseteq B$), so $x \in A'$.

De Morgan's laws

The two De Morgan laws for sets are: $\boxed{(A \cup B)' = A' \cap B', \qquad (A \cap B)' = A' \cup B'.}$

In words: "not (A or B)" = "(not A) and (not B)", and "not (A and B)" = "(not A) or (not B)". The complement swaps union and intersection.

Proof of $(A \cup B)' = A' \cap B'$

($\subseteq$) Let $x \in (A \cup B)'$. Then $x \in U$ and $x \notin A \cup B$. Hence $x \notin A$ and $x \notin B$ (if either held, then $x$ would be in $A \cup B$). So $x \in A'$ and $x \in B'$, i.e. $x \in A' \cap B'$.

($\supseteq$) Let $x \in A' \cap B'$. Then $x \in A'$ and $x \in B'$, so $x \notin A$ and $x \notin B$. Therefore $x \notin A \cup B$, i.e. $x \in (A \cup B)'$.

Both inclusions give equality. The second law follows by applying the first to $A'$ and $B'$ and using $(A')' = A$. $\qed$

De Morgan generalised

For any family $A_1, A_2, \dots, A_n \subseteq U$: $\left(\bigcup_{i=1}^n A_i\right)' = \bigcap_{i=1}^n A_i', \qquad \left(\bigcap_{i=1}^n A_i\right)' = \bigcup_{i=1}^n A_i'.$

The proof is by induction using the two-set version.

Why De Morgan is fundamental

The laws are not just notation: they are the algebra of "and / or / not". You will see exactly the same shape in:

• Logic: $\neg(p \lor q) \equiv (\neg p) \land (\neg q)$.
• Probability: $P(\overline{A \cup B}) = P(A' \cap B')$; the chance that neither event happens.
• Circuits: a NAND-gate equals an inverter on each input followed by an OR.

Mastering De Morgan now will save you headaches throughout Class XII, JEE and beyond.

Worked examples

Example 1. Take $U = \{1, 2, \dots, 10\}$, $A = \{2, 4, 6, 8, 10\}$, $B = \{1, 2, 3, 4, 5\}$. Find $A'$, $B'$, $(A \cup B)'$ and verify De Morgan.

$A' = \{1, 3, 5, 7, 9\}$, $B' = \{6, 7, 8, 9, 10\}$. $A \cup B = \{1, 2, 3, 4, 5, 6, 8, 10\}$, so $(A \cup B)' = \{7, 9\}$. Also $A' \cap B' = \{7, 9\}$. They agree.

Example 2. Simplify $(A \cap B)' \cap A$.

$(A \cap B)' = A' \cup B'$ (De Morgan). So $(A \cap B)' \cap A = (A' \cup B') \cap A = (A' \cap A) \cup (B' \cap A) = \varnothing \cup (A \cap B') = A - B$.

Example 3. If $A = \{x \in \mathbb{R} : x \ge 0\}$ and $U = \mathbb{R}$, find $A'$.

$A' = \{x \in \mathbb{R} : x < 0\} = (-\infty, 0)$.

Example 4. Prove $A \cup A' = U$ and $A \cap A' = \varnothing$.

Take any $x \in U$. By the law of the excluded middle, either $x \in A$ or $x \notin A$. The first puts $x$ in $A \subseteq A \cup A'$; the second puts $x$ in $A' \subseteq A \cup A'$. Hence $U \subseteq A \cup A'$, and the reverse is obvious. For the intersection: no $x$ can be both in $A$ and not in $A$.

Example 5 (harder). Use De Morgan to simplify $(A' \cap B') \cup (A' \cap B)$.

Factor out $A'$: $(A' \cap B') \cup (A' \cap B) = A' \cap (B' \cup B) = A' \cap U = A'$.

Try it yourself

1. Let $U = \{1, 2, \dots, 10\}$ and $A = \{1, 3, 5, 7, 9\}$. Find $A'$.
2. Verify De Morgan's law $(A \cap B)' = A' \cup B'$ for $A = \{1, 2, 3\}$, $B = \{2, 3, 4\}$, $U = \{1, 2, 3, 4, 5\}$.
3. Simplify $(A')' \cup B'$.
4. Show $A - B = A \cap B'$.
5. Prove $A \subseteq B$ iff $B' \subseteq A'$.
6. Simplify $(A \cup B) \cap A'$.
7. If $A \cap B = \varnothing$, prove $A \subseteq B'$.
8. With $U = \mathbb{R}$, find the complement of $[2, 5)$.
9. Show $(A \cup B \cup C)' = A' \cap B' \cap C'$ by induction on the number of sets.
10. Simplify $(A - B)' = ?$ (express using $\cup, \cap, '$).
11. Show $A \cap (A' \cup B) = A \cap B$.
12. Prove $A \cup B = (A' \cap B')'$.

Pitfalls / Tricks

• The complement depends on $U$. The complement of $\{0\}$ in $\mathbb{N}$ is empty; in $\mathbb{Z}$ it is huge.
• $(A \cup B)' = A' \cup B'$ is WRONG. The correct rule swaps the operation: $(A \cup B)' = A' \cap B'$.
• $A - B = A \cap B'$ is the bridge identity. Use it to convert any difference into intersection-with-complement, then apply algebra.
• Insight. Complement is an involution , applying it twice returns the original. Union and intersection are dual under complement. These two facts together generate every identity you will ever need on sets.