Basic Set Operations

Why This Matters

Set operations are the verbs of set theory—they describe how sets combine, overlap, and relate to one another. When you're working through proofs or solving problems in discrete mathematics, probability, or even computer science, you'll constantly rely on these operations to manipulate and analyze collections of objects. Understanding union, intersection, complement, difference, and their properties isn't just about memorizing symbols; it's about grasping how mathematical structures interact.

You're being tested on your ability to apply these operations correctly, recognize their algebraic properties (like commutativity and associativity), and use fundamental laws like De Morgan's to simplify complex expressions. Don't just memorize that $A \cup B$ means "everything in A or B"—know why union is commutative, how complement relates to difference, and when to apply De Morgan's Laws to break apart a complicated set expression.

---

Combining Sets: Union and Intersection

These two operations form the backbone of set manipulation. Union gathers elements together; intersection finds common ground. Both share key algebraic properties that make them predictable and powerful.

Union

• Notation: $A \cup B$—includes all elements that are in $A$, in $B$, or in both sets
• No duplication occurs; each element appears exactly once in the resulting set, regardless of how many times it appears across the original sets
• Commutative and associative—$A \cup B = B \cup A$ and $(A \cup B) \cup C = A \cup (B \cup C)$, allowing flexible regrouping in proofs

Intersection

• Notation: $A \cap B$—contains only elements that belong to both $A$ and $B$ simultaneously
• Identifies overlap between sets, which is essential for determining shared characteristics or common membership
• Commutative and associative—$A \cap B = B \cap A$ and $(A \cap B) \cap C = A \cap (B \cap C)$, mirroring union's algebraic behavior

---

Removing Elements: Complement and Difference

These operations focus on what's not included. Complement removes everything in a set from the universal set; difference removes one set's elements from another. Understanding their relationship is key to simplifying expressions.

Complement

• Notation: $A'$ or $A^c$—includes all elements in the universal set $U$ that are not in $A$
• Depends on context; the complement only makes sense relative to a defined universal set, so always identify $U$ first
• Equivalent to $U - A$—this connection to set difference helps when rewriting expressions or applying De Morgan's Laws

Difference

• Notation: $A - B$ (or $A \setminus B$)—contains elements that are in $A$ but not in $B$
• Highlights uniqueness; isolates what belongs exclusively to the first set
• Not commutative—$A - B \neq B - A$ in general, so order matters when computing differences

Symmetric Difference

• Notation: $A \triangle B$—includes elements in either $A$ or $B$, but not in both
• Equivalent to $(A - B) \cup (B - A)$—think of it as "union minus the overlap"
• Commutative and associative—unlike regular difference, symmetric difference behaves predictably under reordering

---

Set Relationships: Subsets and Disjoint Sets

Before performing operations, you often need to understand how sets relate structurally. Subset relationships establish hierarchy; disjoint sets have no overlap at all.

Subset and Superset

• Notation: $A \subseteq B$—every element of $A$ is also an element of $B$, making $A$ a subset
• Superset is the inverse—$B \supseteq A$ means $B$ contains all elements of $A$ (and possibly more)
• Proper subsets use $A \subset B$—this indicates $A \subseteq B$ and $A \neq B$, meaning $B$ has at least one element not in $A$

Disjoint Sets

• Definition: $A \cap B = \emptyset$—two sets are disjoint when they share no elements whatsoever
• Critical in probability—disjoint sets represent mutually exclusive events, where $P(A \cup B) = P(A) + P(B)$
• Pairwise vs. mutually disjoint—a collection of sets is mutually disjoint if every pair of sets in the collection is disjoint

---

Building New Structures: Power Sets and Cartesian Products

Some operations don't combine sets element-by-element but instead construct entirely new collections. Power sets enumerate all possible subsets; Cartesian products generate ordered pairs.

Power Set

• Notation: $\mathcal{P}(A)$ or $2^A$—the set of all possible subsets of $A$, including $\emptyset$ and $A$ itself
• Cardinality formula: $|\mathcal{P}(A)| = 2^n$—if $A$ has $n$ elements, its power set has $2^n$ elements
• Fundamental for counting arguments—power sets appear in combinatorics, topology, and anywhere you need to consider "all possible selections"

Cartesian Product

• Notation: $A \times B$—the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$
• Order matters in pairs—$(a, b) \neq (b, a)$ unless $a = b$, so the Cartesian product is not commutative
• Cardinality formula: $|A \times B| = |A| \cdot |B|$—essential for counting problems involving combinations from two sets

---

Fundamental Laws: De Morgan's Rules

These laws connect union, intersection, and complement in a way that's essential for simplifying complex set expressions. De Morgan's Laws let you "distribute" a complement across an operation by swapping union and intersection.

De Morgan's Laws

• First law: $(A \cup B)' = A' \cap B'$—the complement of a union equals the intersection of the complements
• **Second law: $(A \cap B)' = A' \cup B'$—the complement of an intersection equals the union of the complements
• Proof strategy essential—when you need to prove two sets are equal, De Morgan's Laws often provide the key transformation

---

Quick Reference Table

---

Self-Check Questions

1. Which two operations are both commutative and associative, yet produce opposite effects on set size—one expanding and one contracting?

2. If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$, compute $A - B$, $B - A$, and $A \triangle B$. What does this reveal about commutativity?

3. Using De Morgan's Laws, rewrite $(A \cup B \cup C)'$ as an expression involving only intersections and complements.

4. Compare and contrast: How does the power set of a set with 4 elements differ in size from the Cartesian product of that set with itself? What does each operation represent conceptually?

5. If two sets $A$ and $B$ satisfy both $A \subseteq B$ and $A \cap B = \emptyset$, what can you conclude about $A$? Justify your answer using definitions.