Set Operations

Union

• $A \cup B \equiv \{x \ | \ x\in A \lor x \in B\}$
• The set where $x$ is in $A$ or $B$ for any arbitrary $x$
• $|A \cup B| = |A| + |B| - |A \cap B|$

Intersection

• $A \cap B \equiv \{x \ | \ x \in A \land x \in B\}$
• The set where $x$ is in both $A$ and $B$ for any arbitrary $x$

Complement

• $\bar{A} \equiv \{x \in U \ | \ x \notin A\}$
• The set where $x$ is not in $A$ for any arbitrary $x$

Difference

• $A - B \equiv \{x \ | \ x \in A \land x \notin B\} \equiv A \cap \bar{B}$
• The set where $x$ is strictly only in $A$, and not $B$, for any arbitrary $x$

Symmetric Difference

• $A \oplus B \equiv (A - B) \cup (B - A) \equiv (A \cup B) - (A \cap B)$
• The set where $x$ is either in $A$ or $B$, but not both (xor)
  • $\{x \ | \ x \in A \oplus x \in B\}$

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

• $\bar{(\bar{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)$

DeMorgan’s Laws

• Still applies!

Generalized Unions and Intersections

Generalized Union

• Denoted as:

• $x \in \bigcup\limits_{i=1}^n A_{i}$ if $\exists i | x \in A_i$

Generalized Intersection

• Denoted as:

• $x \in \bigcap\limits_{i=1}^n A_{i}$ if $\forall i | x \in A_i$

References

• Course slides §8.2: Set Operations
• Course slides §9.1: Set Identities
• Course slides §9.2: Generalized Union and Intersection