1.3 Set Operations, Venn Diagrams, Algebraic Laws & Cardinality Theorems

Back to Discrete Mathematics Notes

📚Module 01: Set Theory & CardinalityTopic 1.3: Set Operations, Venn Diagrams, Laws & Cardinality Theorems⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Multi-Platform Streaming Subscriber Base

Imagine an international streaming service managing digital subscriptions across platforms:

1. The Universal Set ($U$): The global database containing every registered internet user on Earth.
2. Set Union ($A \cup B$): If iOS_Users is set $A$ and Android_Users is set $B$, the union $A \cup B$ represents all customers who access streaming on a mobile phone (either iOS, Android, or both).
3. Set Intersection ($A \cap B$): The intersection represents power users who log in on both an iOS tablet and an Android smartphone simultaneously.
4. Set Difference ($A - B$): The relative complement represents pure iOS loyalists—users who access via iOS and never touch Android.
5. Symmetric Difference ($A \oplus B$): Represents single-platform users—customers who use either iOS or Android, but strictly not both!
6. Set Complement ($A^c$): Every person in the global directory who does not use an iOS device (desktop users, console users, and non-users).

💻 Bridging to Computer Science: Relational Query Calculus & Compiler Data-Flow

In software architecture, set operations form the algebraic core of SQL database query execution plans (UNION, INTERSECT, EXCEPT), search engine inverted indexes (AND, OR, NOT filters), and compiler data-flow optimizations (such as Liveness Analysis Gen-Kill equations: $\text{OUT}[B] = \text{Gen}[B] \cup (\text{IN}[B] - \text{Kill}[B])$).

📑Table of Contents

• 🧱 The Fundamental Set Operations
  • 1. Set Union (A ∪ B)
  • 2. Set Intersection (A ∩ B) & Disjoint Sets
  • 3. Set Difference (Relative Complement: A - B and B - A)
  • 4. Symmetric Difference (A ⊕ B)
  • 5. Set Complement (A' or Aᶜ)
• 📐 Venn Diagram Geometry & Inclusion-Exclusion
  • Partitioning 2 Sets into Disjoint Regions
• 📜 The 8 Fundamental Algebraic Laws of Set Theory
• ♾️ Cardinality Theorems on Finite and Infinite Sets
• 🌍 Real-World Engineering Context
• 📝 Step-by-Step Worked Examples
  • Example 1: Algebraic Simplification of Set Expressions
  • Example 2: Principle of Inclusion-Exclusion Application
  • Example 3: Evaluating Statements on Infinite Cardinalities
• 🎯 Exam & Interview Pitfall Check

---

🧱 The Fundamental Set Operations

All operations in set theory occur within the context of a designated Universal Set ($U$), which encapsulates all objects under consideration for a specific mathematical problem.

1. Set Union (A ∪ B)

📖Definition 1.9: Set Uniondefinition

$$A \cup B = \{x \mid x \in A \lor x \in B\}$$$$x \in (A \cup B) \iff x \in A \lor x \in B$$

Shaded: All elements belonging to set A, set B, or both.

• Concrete Example: Let $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$. $$A \cup B = \{1, 2, 3, 4, 5\}$$
• Fundamental Invariants:
  • $A \subseteq (A \cup B)$ and $B \subseteq (A \cup B)$
  • $A \cup \emptyset = A$ and $A \cup U = U$
  • Cardinality bound: $\max(|A|, |B|) \le |A \cup B| \le |A| + |B|$

---

2. Set Intersection (A ∩ B) & Disjoint Sets

📖Definition 1.10: Set Intersection & Disjoint Conditiondefinition

$$A \cap B = \{x \mid x \in A \land x \in B\}$$$$x \in (A \cap B) \iff x \in A \land x \in B$$

If $A \cap B = \emptyset$, sets $A$ and $B$ are disjoint (mutually exclusive).

A ∩ B ≠ ∅: Shaded center lens contains common elements.

A ∩ B = ∅: Zero overlapping elements; separated sets.

• Concrete Example:
  • For $A = \{1, 2, 3\}$ and $B = \{3, 4, 5\}$: $$A \cap B = \{3\}$$
  • For Evens $E = \{2, 4, 6, \dots\}$ and Odds $O = \{1, 3, 5, \dots\}$: $$E \cap O = \emptyset \quad \text{(Disjoint sets)}$$
• Fundamental Invariants:
  • $(A \cap B) \subseteq A$ and $(A \cap B) \subseteq B$
  • $A \cap \emptyset = \emptyset$ and $A \cap U = A$
  • Cardinality bound: $\max(0, |A| + |B| - |U|) \le |A \cap B| \le \min(|A|, |B|)$

---

3. Set Difference (Relative Complement: A - B and B - A)

📖Definition 1.11: Set Difference (Relative Complement)definition

$$A - B = \{x \mid x \in A \land x \notin B\} = A \cap B^c$$$$B - A = \{x \mid x \in B \land x \notin A\} = B \cap A^c$$

A - B: Shaded left crescent contains elements in A excluding B.

B - A: Shaded right crescent contains elements in B excluding A.

• Concrete Example: Let $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$. $$A - B = \{1, 2\} \qquad \text{and} \qquad B - A = \{5, 6\}$$
• Asymmetry Invariant: Notice that $\{1, 2\} \neq \{5, 6\}$. Set difference is strictly non-commutative: $$A - B \neq B - A \quad (\text{unless } A = B)$$
• Cardinality Formula: $$|A - B| = |A| - |A \cap B| \qquad \text{and} \qquad |B - A| = |B| - |A \cap B|$$

---

4. Symmetric Difference (A ⊕ B)

📖Definition 1.12: Symmetric Difference (Boolean XOR)definition

$$A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$$$$A \oplus B = \{x \mid (x \in A \land x \notin B) \lor (x \in B \land x \notin A)\}$$

A ⊕ B: Both crescents shaded; center intersection remains clear.

• Concrete Example: For $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$: $$A \oplus B = \{1, 2\} \cup \{5, 6\} = \{1, 2, 5, 6\}$$ Equivalently: $$(A \cup B) - (A \cap B) = \{1, 2, 3, 4, 5, 6\} - \{3, 4\} = \{1, 2, 5, 6\}$$
• Algebraic Group Invariants:
  • Commutative: $A \oplus B = B \oplus A$
  • Associative: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$
  • Identity Element: $A \oplus \emptyset = A$
  • Self-Inverse: $A \oplus A = \emptyset$
  • Cardinality Formula: $|A \oplus B| = |A| + |B| - 2|A \cap B|$

---

5. Set Complement (A' or Aᶜ)

📖Definition 1.13: Absolute Complementdefinition

$$A^c = A' = \{x \in U \mid x \notin A\} = U - A$$$$A \cup A' = U \qquad \text{and} \qquad A \cap A' = \emptyset$$

A': Universal rectangle U shaded; set A remains unshaded.

• Concrete Example: Let $U = \{1, 2, 3, 4, 5, 6, 7, 8\}$ and $A = \{2, 4, 6, 8\}$. $$A' = \{1, 3, 5, 7\}$$
• Fundamental Invariants:
  • $A \cup A' = U$
  • $A \cap A' = \emptyset$
  • $(A')' = A$ (Involution Law)
  • $U' = \emptyset$ and $\emptyset' = U$
  • Cardinality: $|A'| = |U| - |A|$

---

📐 Venn Diagram Geometry & Inclusion-Exclusion

Venn diagrams represent sets geometrically as closed planar regions inside a bounding universal rectangle $U$.

Partitioning 2 Sets into Disjoint Regions

Two intersecting sets $A$ and $B$ partition the universal space into 4 mutually disjoint regions:

1. Region 1: $A - B = A \cap B^c$ (Exclusively in $A$)
2. Region 2: $B - A = B \cap A^c$ (Exclusively in $B$)
3. Region 3: $A \cap B$ (Simultaneously in both $A$ and $B$)
4. Region 4: $(A \cup B)^c = A^c \cap B^c$ (Outside both $A$ and $B$)

Because these 4 regions are pairwise disjoint, their cardinalities sum directly:

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

📐Formula 1.3: The Principle of Inclusion-Exclusion (PIE)formula

Two-Set Cardinality:

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

Three-Set Cardinality:

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

Symmetric Difference Cardinality:

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

📐Formula 1.4: Extremal Bounds on Union & Intersection Cardinalityformula

For any two finite sets $A$ and $B$ inside universal set $U$:

1. Extremal Bounds on Union Cardinality $|A \cup B|$:

   $$\max(|A|, |B|) \le |A \cup B| \le \min(|U|, |A| + |B|)$$
   • Minimum Value: $\min(|A \cup B|) = \max(|A|, |B|)$. Occurs when one set is completely contained in the other ($A \subseteq B$ or $B \subseteq A$).
   • Maximum Value: $\max(|A \cup B|) = \min(|U|, |A| + |B|)$. Occurs when sets are mutually disjoint ($A \cap B = \emptyset$).

2. Extremal Bounds on Intersection Cardinality $|A \cap B|$:

   $$\max(0, |A| + |B| - |U|) \le |A \cap B| \le \min(|A|, |B|)$$
   • Minimum Value: $\min(|A \cap B|) = \max(0, |A| + |B| - |U|)$. If $|A| + |B| \le |U|$, the sets can be completely disjoint ($|A \cap B| = 0$). If $|A| + |B| > |U|$, the pigeonhole principle forces at least $|A| + |B| - |U|$ elements to overlap.
   • Maximum Value: $\max(|A \cap B|) = \min(|A|, |B|)$. Occurs when the smaller set is entirely subsumed within the larger set.

📐Formula 1.5: Exact Regional Decomposition for 3 Setsformula

For three intersecting sets $A, B, C$ inside universal set $U$:

1. Elements in Exactly One Set: $$N(\text{exactly 1}) = (|A| + |B| + |C|) - 2(|A \cap B| + |B \cap C| + |C \cap A|) + 3|A \cap B \cap C|$$
2. Elements in Exactly Two Sets: $$N(\text{exactly 2}) = (|A \cap B| + |B \cap C| + |C \cap A|) - 3|A \cap B \cap C|$$
3. Elements in At Least Two Sets: $$N(\text{at least 2}) = (|A \cap B| + |B \cap C| + |C \cap A|) - 2|A \cap B \cap C|$$

---

📜 The 8 Fundamental Algebraic Laws of Set Theory

Set operations satisfy an exact isomorphism with Boolean propositional logic connectives ($\cup \leftrightarrow \lor$, $\cap \leftrightarrow \land$, $^c \leftrightarrow \neg$, $U \leftrightarrow \mathbf{T}$, $\emptyset \leftrightarrow \mathbf{F}$).

⚡Law 1.3: The 8 Canonical Algebraic Laws of Set Theorylaw

1. Idempotent Laws: $$A \cup A = A \qquad \text{and} \qquad A \cap A = A$$
2. Commutative Laws: $$A \cup B = B \cup A \qquad \text{and} \qquad A \cap B = B \cap A$$
3. Associative Laws: $$(A \cup B) \cup C = A \cup (B \cup C) \qquad \text{and} \qquad (A \cap B) \cap C = A \cap (B \cap C)$$
4. 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)$$
5. De Morgan's Laws: $$(A \cup B)^c = A^c \cap B^c \qquad \text{and} \qquad (A \cap B)^c = A^c \cup B^c$$
6. Identity Laws: $$A \cup \emptyset = A \qquad \text{and} \qquad A \cap U = A$$ $$A \cup U = U \qquad \text{and} \qquad A \cap \emptyset = \emptyset$$
7. Complement Laws: $$A \cup A^c = U \qquad \text{and} \qquad A \cap A^c = \emptyset$$ $$(A^c)^c = A \quad (\text{Involution Law}), \qquad U^c = \emptyset, \qquad \emptyset^c = U$$
8. Absorption Laws: $$A \cup (A \cap B) = A \qquad \text{and} \qquad A \cap (A \cup B) = A$$

---

♾️ Cardinality Theorems on Finite and Infinite Sets

When sets involve infinite cardinalities ($\aleph_0$ or $\mathfrak{c}$), intuitive arithmetic breaks down. The following 5 theorems govern set behavior under finite unions and intersections.

Architecture Flow

Finite vs Infinite Cardinality Decision Pipeline

Rigorous logical flow for determining set size under finite union and intersection

∪Union Rule

Finite Union of Sets

If all sets are finite, the union is strictly finite. If any single set is infinite, the union is infinite.

→

Branching to Intersections

⚡Inversion

Infinite Union Origin

If a finite union of sets is infinite, AT LEAST ONE participating set MUST be infinite.

→

Contradiction Proof

∩Intersection Rule

Finite Intersection of Infinite

Can be finite OR infinite! E.g., evens ∩ odds = ∅ (finite); evens ∩ multiples of 4 = infinite.

→

Bounded Constraint

🎯Theorem 5

Infinite Intersection Requirement

If a finite intersection is infinite, then ALL participating sets MUST be infinite without exception.

📐Theorem 1.2: Finite Union of Finite Setstheorem

A finite union of finite sets is always finite:

$$|A_1|, |A_2|, \dots, |A_n| < \infty \implies \left|\bigcup_{i=1}^n A_i\right| < \infty$$

Proof: By induction and inclusion-exclusion, $|\bigcup_{i=1}^n A_i| \le \sum_{i=1}^n |A_i|$. The sum of finitely many finite non-negative integers is finite.

📐Theorem 1.3: The Infinite Union Inversetheorem

If a finite union of sets is infinite, then at least one of the participating sets must be infinite:

$$\left|\bigcup_{i=1}^n A_i\right| = \infty \implies \exists k \in \{1, \dots, n\} \text{ such that } |A_k| = \infty$$

Proof by Contrapositive: Assume all sets $A_1, \dots, A_n$ are finite. Then by Theorem 1.2, their union must be finite. This contradicts the premise. Hence, at least one $A_k$ must be infinite.

📐Theorem 1.4: Finite Intersection of Infinite Setstheorem

The finite intersection of infinite sets can be either finite or infinite:

• Case 1: Intersection is Finite (or Empty):
  • Let $A = \{2, 4, 6, 8, \dots\}$ (infinite evens, $|A| = \aleph_0$) and $B = \{1, 3, 5, 7, \dots\}$ (infinite odds, $|B| = \aleph_0$).
  • Their intersection is: $$A \cap B = \emptyset \implies |A \cap B| = 0 < \infty \quad \text{(Finite Empty Set!)}$$
  • Singleton Witness in Real Intervals: Let $A = [0, 1]$ and $B = [1, 2]$ (both uncountable). $$A \cap B = \{1\} \implies |A \cap B| = 1 \quad \text{(Finite Singleton!)}$$
• Case 2: Intersection is Infinite:
  • Let $A = \{2, 4, 6, 8, \dots\}$ and $B = \{4, 8, 12, 16, \dots\}$. $$A \cap B = \{4, 8, 12, 16, \dots\} \implies |A \cap B| = \aleph_0 \quad \text{(Infinite!)}$$
  • Uncountable Witness in Real Intervals: Let $A = [0, 2]$ and $B = [1, 3]$. $$A \cap B = [1, 2] \implies |A \cap B| = \mathfrak{c} \quad \text{(Uncountable!)}$$

📐Theorem 1.5: The Infinite Intersection Necessitytheorem

If a finite intersection of sets is infinite, then every single participating set must be infinite:

$$\left|\bigcap_{i=1}^n A_i\right| = \infty \implies \forall i \in \{1, \dots, n\}, \; |A_i| = \infty$$

Proof: For any set $A_k$ in the collection:

$$\left(\bigcap_{i=1}^n A_i\right) \subseteq A_k \implies \left|\bigcap_{i=1}^n A_i\right| \le |A_k|$$

If even a single set $A_k$ were finite with size $|A_k| = m < \infty$, the cardinality of the intersection would be bounded by $m$, making it finite. Because the intersection is infinite, every participating set $A_i$ must be infinite.

---

🌍 Real-World Engineering Context

1. Search Engine Inverted Indexes: In search engines like Elasticsearch and Google Search, queries evaluate set operations over document posting lists. An AND query computes posting list intersections ($A \cap B$), an OR query computes unions ($A \cup B$), and NOT computes set differences ($A - B$). Fast skip-lists perform these set operations in linear time.
2. Database Query Optimization (Relational Algebra): In database execution plans, UNION computes $A \cup B$ with deduplication, INTERSECT computes $A \cap B$, and EXCEPT (or MINUS) computes $A - B$. Query optimizers use De Morgan's laws and distributivity to push filters down the execution tree before executing expensive disk scans.
3. Network Firewall Rule Evaluation: Network security appliances evaluate packet filters as overlapping sets of IP address blocks (CIDR notation). Evaluating whether a packet matches a whitelist while being excluded from a blacklist relies on $A \cap B^c = A - B$.

---

📝 Step-by-Step Worked Examples

Example 1: Algebraic Simplification of Set Expressions

Problem Statement:
Using the algebraic laws of set theory, simplify the following expression to its irreducible canonical form:

$$E = (A \cup B) \cap (A \cup B^c)$$

Step-by-Step Solution:

1. Apply Distributive Law (in reverse): Notice that $A \cup$ is common to both factors in the intersection: $$(A \cup B) \cap (A \cup B^c) = A \cup (B \cap B^c)$$
2. Apply Complement Law: By the complement law, any set intersected with its own complement is the empty set: $$B \cap B^c = \emptyset$$
3. Substitute into the Expression: $$E = A \cup \emptyset$$
4. Apply Identity Law: By the identity law of union: $$A \cup \emptyset = A$$

Key Takeaway:
Factoring common sub-expressions via the Distributive Law reduces multi-variable set expressions down to elementary components without requiring Venn diagram enumeration.

---

Example 2: Principle of Inclusion-Exclusion Application

Problem Statement:
In a computer engineering cohort of 120 students:

• 65 students are proficient in Python ($P$).
• 50 students are proficient in C++ ($C$).
• 40 students are proficient in Rust ($R$).
• 25 students know both Python and C++.
• 20 students know both Python and Rust.
• 15 students know both C++ and Rust.
• 8 students are proficient in all three languages.

Determine:

1. The number of students proficient in at least one of these three languages.
2. The number of students who know none of these languages.
3. The number of students proficient in exactly one language.

Step-by-Step Solution:

1. Compute $|P \cup C \cup R|$ using 3-Set PIE: $$|P \cup C \cup R| = |P| + |C| + |R| - (|P \cap C| + |P \cap R| + |C \cap R|) + |P \cap C \cap R|$$ $$|P \cup C \cup R| = 65 + 50 + 40 - (25 + 20 + 15) + 8$$ $$|P \cup C \cup R| = 155 - 60 + 8 = 103$$ There are 103 students proficient in at least one language.
2. Students who know none of these languages: $$|U| - |P \cup C \cup R| = 120 - 103 = 17 \text{ students}$$
3. Students proficient in exactly one language:
   • Exactly Python: $65 - (25 - 8) - (20 - 8) - 8 = 65 - 17 - 12 - 8 = 28$.
   • Exactly C++: $50 - (25 - 8) - (15 - 8) - 8 = 50 - 17 - 7 - 8 = 18$.
   • Exactly Rust: $40 - (20 - 8) - (15 - 8) - 8 = 40 - 12 - 7 - 8 = 13$.
   • Total exactly one: $$28 + 18 + 13 = 59 \text{ students}$$

Key Takeaway:
Pairwise intersections count triple overlaps multiple times; the alternating signs of PIE guarantee exact single-count attribution.

---

Example 3: Evaluating Statements on Infinite Cardinalities

Problem Statement:
Evaluate the validity (True or False) of each of the following statements with rigorous mathematical justification:

1. $S_1$: "If the union of three sets $A \cup B \cup C$ is infinite, then all three sets $A, B, C$ must be infinite."
2. $S_2$: "The intersection of any two uncountable sets is always uncountable."
3. $S_3$: "If $A \cap B$ is infinite, then $A \cup B$ must be infinite."

Step-by-Step Solution:

1. Evaluating $S_1$: By Theorem 1.3, if a finite union is infinite, at least one participating set must be infinite. It does not require all three to be infinite. For example, let $A = \mathbb{N}$ (infinite), $B = \{1, 2\}$ (finite), and $C = \{3\}$ (finite). Then $A \cup B \cup C = \mathbb{N}$ is infinite, but $B$ and $C$ are finite. Conclusion: $S_1$ is False.
2. Evaluating $S_2$: Consider the two uncountable intervals $A = [0, 1]$ and $B = [1, 2]$. Both sets are uncountable (cardinality $\mathfrak{c}$). But their intersection is $A \cap B = \{1\}$, which is a finite singleton set ($|\{1\}| = 1$). Even more drastically, $(0, 1) \cap (2, 3) = \emptyset$, which has cardinality $0$. Conclusion: $S_2$ is False.
3. Evaluating $S_3$: Notice that $(A \cap B) \subseteq (A \cup B)$. If $A \cap B$ is infinite, then $|A \cap B| = \infty$. Since $A \cup B$ is a superset of $A \cap B$, its cardinality is bounded below: $|A \cup B| \ge |A \cap B| = \infty$. Conclusion: $S_3$ is True.

Key Takeaway:
Subsets bound intersections from above ($|A \cap B| \le \min(|A|, |B|)$) and unions from below ($|A \cup B| \ge \max(|A|, |B|)$).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is set difference non-commutative, while symmetric difference is commutative?"
Key Focus Points:

• Asymmetry of Filtration: $A - B$ removes $B$'s elements from $A$. If $A = \{1, 2\}$ and $B = \{2, 3\}$, then $A - B = \{1\}$ while $B - A = \{3\}$. Since $\{1\} \neq \{3\}$, $A - B \neq B - A$.
• Symmetry of XOR: $A \oplus B = (A - B) \cup (B - A)$. Because set union is commutative, $(A - B) \cup (B - A) = (B - A) \cup (A - B) = B \oplus A$.

Question 2: "If A and B are infinite sets, can A ∩ B be finite? Can it be empty?"
Key Focus Points:

• Empty Intersection: Let $A = \{2, 4, 6, \dots\}$ (evens) and $B = \{1, 3, 5, \dots\}$ (odds). Both are infinite, but $A \cap B = \emptyset$ (size 0).
• Finite Intersection: Let $A = [0, 1]$ and $B = [1, 2]$. Both intervals are uncountable, but $A \cap B = \{1\}$ (size 1).
• Core Takeaway: Infinite inputs do NOT guarantee infinite intersections.

Common Interview Traps: Architectural Trade-Offs

Trap 1: If an intersection of n sets is infinite, must all n sets be infinite?
Answer: Yes, absolutely. If even a single set $A_k$ were finite with size $m$, then $|\bigcap A_i| \le |A_k| = m < \infty$, so the intersection would be finite. For the intersection to be infinite, every participating set must be infinite.

Trap 2: Does De Morgan's Law invert the union symbol into an intersection symbol?
Answer: Yes. $(A \cup B)^c = A^c \cap B^c$. A common mistake is writing $(A \cup B)^c = A^c \cup B^c$, which is completely invalid. The union flips to intersection, and intersection flips to union.

---

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic1.2 Subsets, Power Sets & Set Membership AlgebraNext Topic →2.1 Binary Relations, Representations & Relational Matrix Algebra