Set Operations

Basic Operations

Union

The union of $A$ and $B$ contains elements in either set: $A \cup B = \{x \mid x \in A \lor x \in B\}$

Example: $\{1, 2, 3\} \cup \{3, 4, 5\} = \{1, 2, 3, 4, 5\}$

Intersection

The intersection of $A$ and $B$ contains elements in both sets: $A \cap B = \{x \mid x \in A \land x \in B\}$

Example: $\{1, 2, 3\} \cap \{3, 4, 5\} = \{3\}$

Difference (Relative Complement)

The difference $A - B$ contains elements in $A$ but not in $B$: $A - B = A \setminus B = \{x \mid x \in A \land x \notin B\}$

Example: $\{1, 2, 3\} - \{3, 4, 5\} = \{1, 2\}$

Complement

The complement of $A$ contains all elements not in $A$ (relative to universal set $U$): $\overline{A} = A^c = U - A = \{x \in U \mid x \notin A\}$

Symmetric Difference

The symmetric difference contains elements in exactly one set: $A \oplus B = A \triangle B = (A - B) \cup (B - A)$ $= (A \cup B) - (A \cap B)$

Example: $\{1, 2, 3\} \oplus \{3, 4, 5\} = \{1, 2, 4, 5\}$

Venn Diagrams

Venn diagrams visualize set operations with overlapping circles.

Two Sets

Region	Description
$A \cap B$	Intersection (overlap)
$A - B$	Only in A
$B - A$	Only in B
$A \cup B$	All shaded areas
$\overline{A \cup B}$	Outside both circles

Generalized Operations

Union of Multiple Sets

$\bigcup_{i=1}^{n} A_i = A_1 \cup A_2 \cup \cdots \cup A_n$

Intersection of Multiple Sets

$\bigcap_{i=1}^{n} A_i = A_1 \cap A_2 \cap \cdots \cap A_n$

Properties of Set Operations

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 \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Identity Laws

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

Complement Laws

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

Idempotent Laws

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

Domination Laws

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

Absorption Laws

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

De Morgan's Laws

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

Generalized De Morgan's Laws

$\overline{\bigcup_{i=1}^{n} A_i} = \bigcap_{i=1}^{n} \overline{A_i}$ $\overline{\bigcap_{i=1}^{n} A_i} = \bigcup_{i=1}^{n} \overline{A_i}$

Disjoint Sets

Two sets are disjoint if they have no common elements: $A \cap B = \emptyset$

A collection of sets is pairwise disjoint if every pair is disjoint: $A_i \cap A_j = \emptyset \text{ for all } i \neq j$

Cardinality and Set Operations

Inclusion-Exclusion (Two Sets)

$|A \cup B| = |A| + |B| - |A \cap B|$

Inclusion-Exclusion (Three Sets)

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

Complement

$|\overline{A}| = |U| - |A|$

Difference

$|A - B| = |A| - |A \cap B|$

Proving Set Equality

Method 1: Element Argument

Show $A \subseteq B$ and $B \subseteq A$:

1. Take arbitrary $x \in A$, show $x \in B$
2. Take arbitrary $x \in B$, show $x \in A$

Method 2: Set Identities

Transform one side to the other using known identities.

Example

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

Proof: $x \in A - (B \cup C)$ $\iff x \in A \land x \notin (B \cup C)$ $\iff x \in A \land (x \notin B \land x \notin C)$ $\iff (x \in A \land x \notin B) \land (x \in A \land x \notin C)$ $\iff x \in (A - B) \land x \in (A - C)$ $\iff x \in (A - B) \cap (A - C)$ $\square$