Set Identities

Complete List of Set Identities

Identity Laws

$A \cup \emptyset = A$ $A \cap U = A$

Domination Laws

$A \cup U = U$ $A \cap \emptyset = \emptyset$

Idempotent Laws

$A \cup A = A$ $A \cap A = A$

Complementation Law

$\overline{\overline{A}} = A$

Commutative Laws

$A \cup B = B \cup A$ $A \cap B = B \cap A$

Associative Laws

$(A \cup B) \cup C = A \cup (B \cup C)$ $(A \cap B) \cap C = A \cap (B \cap C)$

Distributive Laws

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

De Morgan's Laws

$\overline{A \cup B} = \overline{A} \cap \overline{B}$ $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Absorption Laws

$A \cup (A \cap B) = A$ $A \cap (A \cup B) = A$

Complement Laws

$A \cup \overline{A} = U$ $A \cap \overline{A} = \emptyset$ $\overline{U} = \emptyset$ $\overline{\emptyset} = U$

Additional Useful Identities

Set Difference

$A - B = A \cap \overline{B}$ $A - (A - B) = A \cap B$ $A - (B \cup C) = (A - B) \cap (A - C)$ $A - (B \cap C) = (A - B) \cup (A - C)$

Symmetric Difference

$A \oplus B = (A \cup B) - (A \cap B)$ $A \oplus B = (A - B) \cup (B - A)$ $A \oplus B = (A \cap \overline{B}) \cup (\overline{A} \cap B)$ $A \oplus A = \emptyset$ $A \oplus \emptyset = A$ $A \oplus B = B \oplus A$ $(A \oplus B) \oplus C = A \oplus (B \oplus C)$

Subset Properties

$A \subseteq B \iff A \cap B = A$ $A \subseteq B \iff A \cup B = B$ $A \subseteq B \iff A - B = \emptyset$ $A \subseteq B \iff \overline{B} \subseteq \overline{A}$

Proving Set Identities

Method 1: Membership Table

Similar to truth tables, use 1 for membership and 0 for non-membership.

Example: Prove $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

$A$	$B$	$C$	$B \cup C$	$A \cap (B \cup C)$	$A \cap B$	$A \cap C$	$(A \cap B) \cup (A \cap C)$
0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0
0	1	0	1	0	0	0	0
0	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0
1	0	1	1	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	1	1	1	1	1

Columns 5 and 8 are identical ✓

Method 2: Element Argument

Show both sets contain exactly the same elements.

Example: Prove $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Proof: $x \in \overline{A \cap B}$ $\iff x \notin (A \cap B)$ $\iff \neg(x \in A \land x \in B)$ $\iff x \notin A \lor x \notin B \text{ (De Morgan's for logic)}$ $\iff x \in \overline{A} \lor x \in \overline{B}$ $\iff x \in \overline{A} \cup \overline{B}$ $\square$

Method 3: Chain of Identities

Transform one side to the other using known identities.

Example: Prove $A \cup (A \cap B) = A$

Proof: $A \cup (A \cap B)$ $= (A \cap U) \cup (A \cap B) \text{ (identity law)}$ $= A \cap (U \cup B) \text{ (distributive law)}$ $= A \cap U \text{ (domination law)}$ $= A \text{ (identity law)}$ $\square$

Duality Principle

Every set identity has a dual obtained by:

• Swapping $\cup$ and $\cap$
• Swapping $\emptyset$ and $U$

If an identity is true, its dual is also true.

Examples of Duals

Identity	Dual
$A \cup \emptyset = A$	$A \cap U = A$
$A \cup U = U$	$A \cap \emptyset = \emptyset$
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$	$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
$\overline{A \cup B} = \overline{A} \cap \overline{B}$	$\overline{A \cap B} = \overline{A} \cup \overline{B}$

Common Proof Patterns

Showing $A \subseteq B$

Let $x \in A$ be arbitrary. Show $x \in B$.

Showing $A = B$

1. Show $A \subseteq B$
2. Show $B \subseteq A$

Showing $A = \emptyset$

Assume $x \in A$ and derive a contradiction.

Showing $A \neq B$

Find an element in one set but not the other.