Unions and Intersections

Binary Operations

Union

$A \cup B = \{x : x \in A \lor x \in B\}$

Intersection

$A \cap B = \{x : x \in A \land x \in B\}$

Properties

Property	Union	Intersection
Commutative	$A \cup B = B \cup A$	$A \cap B = B \cap A$
Associative	$(A \cup B) \cup C = A \cup (B \cup C)$	$(A \cap B) \cap C = A \cap (B \cap C)$
Identity	$A \cup \emptyset = A$	$A \cap U = A$
Idempotent	$A \cup A = A$	$A \cap A = A$

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)$

Proof of the First

$x \in A \cap (B \cup C) \iff x \in A \land (x \in B \lor x \in C)$ $\iff (x \in A \land x \in B) \lor (x \in A \land x \in C)$ $\iff x \in (A \cap B) \cup (A \cap C)$

Big Unions and Intersections

Notation

For an indexed family of sets $\{A_i\}_{i \in I}$:

$\bigcup_{i \in I} A_i = \{x : \exists i \in I. x \in A_i\}$

$\bigcap_{i \in I} A_i = \{x : \forall i \in I. x \in A_i\}$

Examples

• $\displaystyle\bigcup_{n \in \mathbb{N}} \{0, 1, \ldots, n\} = \mathbb{N}$
• $\displaystyle\bigcap_{n \in \mathbb{N}} \{n, n+1, n+2, \ldots\} = \emptyset$
• $\displaystyle\bigcup_{n \in \mathbb{N}} \{n\} = \mathbb{N}$ (each $\{n\}$ is a singleton)

De Morgan’s Laws for Big Operations

$\left(\bigcup_{i \in I} A_i\right)^c = \bigcap_{i \in I} A_i^c$ $\left(\bigcap_{i \in I} A_i\right)^c = \bigcup_{i \in I} A_i^c$

Verification

$x \in (\bigcup_{i \in I} A_i)^c \iff \neg(\exists i \in I. x \in A_i)$ $\iff \forall i \in I. x \notin A_i$ $\iff \forall i \in I. x \in A_i^c$ $\iff x \in \bigcap_{i \in I} A_i^c$

Distributivity of Big Operations

Big Union over Intersection

$A \cap \left(\bigcup_{i \in I} B_i\right) = \bigcup_{i \in I} (A \cap B_i)$

Big Intersection over Union

$A \cup \left(\bigcap_{i \in I} B_i\right) = \bigcap_{i \in I} (A \cup B_i)$

Empty Index Set

Convention

When $I = \emptyset$:

$\bigcup_{i \in \emptyset} A_i = \emptyset$ $\bigcap_{i \in \emptyset} A_i = U$

Rationale: $\exists i \in \emptyset$ is always false, so the union is empty.

For intersection: $\forall i \in \emptyset$ is vacuously true, so every $x$ satisfies the condition. The intersection is the entire universe $U$.

Set Difference

Definition

$A \setminus B = \{x \in A : x \notin B\}$

Properties

• $A \setminus B = A \cap B^c$
• $A \setminus A = \emptyset$
• $A \setminus \emptyset = A$
• $\emptyset \setminus A = \emptyset$

Symmetric Difference

$A \triangle B = (A \setminus B) \cup (B \setminus A)$

This is the set of elements in exactly one of $A$ or $B$.

---

Summary

• $\cup$ and $\cap$ are commutative, associative, and idempotent
• $\cup$ distributes over $\cap$ and vice versa
• Big unions $\bigcup_{i \in I} A_i$ generalise to indexed families
• De Morgan’s laws apply to complemented big unions/intersections