Track / Stage 5 / 297 of 400 #897 of 1964

Problem 897

AIME late

Combinatorics Difficulty 5.7 Prove it

Example 1 (De Morgan's Laws) For any two sets $A, B$ , we have
$\begin{array}{l} (A \cup B)^{\prime}=A^{\prime} \cap B^{\prime} \\ (A \cap B)^{\prime}=A^{\prime} \cup B^{\prime} . \end{array}$

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Proof of (1). $A \cup B$ is the set of elements that are in $A$ or in $B$ , so $(A \cup B)^{\prime}$ consists of elements that are neither in $A$ nor in $B$ . This is precisely $A^{\prime} \cap B^{\prime}$ .

If we consider a Venn diagram, then $(A \cup B)^{\prime}$ and $A^{\prime} \cap B^{\prime}$ are both the shaded regions in Figure 1.7.1 (for convenience, the universal set $I$ is represented by a rectangle).
Similarly, (2) can be proven. The shaded region in Figure 1.7.2 represents both the left side and the right side of (2).

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.