2.3 Relational Closures, Warshall's Algorithm & Equivalence Partitions

Back to Discrete Mathematics Notes

📚Module 02: Binary Relations & ClosuresTopic 2.3: Relational Closures, Warshall's Algorithm & Equivalence⏱️5 min read

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

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Transit Road Network & Currency Denominations

Imagine managing an urban road infrastructure and banking system:

1. The Reflexive Closure: A road map connects different buildings. If building codes require that every facility must have an internal circular driveway so vehicles can turn around on-site, adding self-loops to every building produces the reflexive closure.
2. The Symmetric Closure: If city planners convert all one-way streets into two-way avenues by adding reverse lanes wherever missing, the resulting network is the symmetric closure.
3. The Transitive Closure: If you can drive from Suburb $A$ to Downtown $B$, and from Downtown $B$ to Airport $C$, adding direct express highways for every multi-hop journey creates the transitive closure—direct reachability between all connected hubs!
4. Warshall's Algorithm: The automated traffic routing engine that calculates all-pairs reachability systematically by testing whether routing through hub 1, hub 2, ..., hub $n$ opens up new shortcut paths.
5. Equivalence Partitions: A cashier sorting cash into cash-drawer slots: all $10 bills in slot 1, all $20 bills in slot 2, all $50 bills in slot 3. Every bill belongs to exactly one slot, no bill belongs to two slots, and together the slots contain all the money. That is an equivalence partition!

💻 Bridging to Computer Science: Reachability, Floyd-Warshall & Disjoint-Set Union (DSU)

In software engineering, transitive closure solves all-pairs reachability in compilers and network packet routing. In graph theory, Warshall's algorithm is the Boolean predecessor to the Floyd-Warshall all-pairs shortest path algorithm ($O(V^3)$). Concurrently, equivalence relations power Disjoint-Set Union (Union-Find) in Kruskal's algorithm, DFA state minimization in compiler lexical scanners, and object identity in object-oriented runtime engines.

📑Table of Contents

• 🛠️ The Three Fundamental Relational Closures
• ⚡ Warshall's Algorithm: Dynamic Programming for Transitive Closure
  • Algorithmic Implementation & Efficiency
• ⚖️ Equivalence Relations & Quotient Partitions
  • Extremal Equivalence Relations
  • Union & Intersection Invariants of Equivalence Relations
• 🧩 Equivalence Classes & The Fundamental Partition Theorem
• 🔢 Counting Equivalence Relations: Bell Numbers & Bell's Triangle
  • Construction of Bell's Triangle
• 🌍 Real-World Engineering Context
• 📝 Step-by-Step Worked Examples
  • Example 1: Calculating Reflexive, Symmetric and Transitive Closures
  • Example 2: Execution Trace of Warshall's Algorithm
  • Example 3: Deriving Equivalence Classes and Quotient Sets
• 🎯 Exam & Interview Pitfall Check

---

🛠️ The Three Fundamental Relational Closures

When a relation lacks a desired algebraic property, we can construct its closure by adding the minimum number of missing ordered pairs.

📖Definition 2.9: The Concept of Closuredefinition

Let $R$ be a binary relation on set $A$, and let $P$ be a property (such as reflexivity, symmetry, or transitivity). The closure of $R$ with respect to property $P$ is the relation $R^*$ such that:

1. $R^*$ possesses property $P$.
2. $R \subseteq R^*$ (it contains the original relation).
3. If $S$ is any other relation containing $R$ that satisfies property $P$, then $R^* \subseteq S$ ($R^*$ is the unique minimal superset).

Fundamental Invariant: A relation $R$ already satisfies property $P$ if and only if $\text{Closure}_P(R) = R$.

📖Definition 2.10: Reflexive, Symmetric & Transitive Closuresdefinition

Let $R$ be a binary relation on set $A$:

1. Reflexive Closure ($r(R)$): Add all missing diagonal self-loops: $$r(R) = R \cup \Delta_A = R \cup \{(x, x) \mid x \in A\}$$
2. Symmetric Closure ($s(R)$): Add all missing reverse pairs: $$s(R) = R \cup R^{-1} = R \cup \{(b, a) \mid (a, b) \in R\}$$
3. Transitive Closure ($t(R)$ or $R^+$): Add all multi-hop reachable shortcut pairs: $$t(R) = R^+ = \bigcup_{k=1}^n R^k = R \cup R^2 \cup R^3 \cup \dots \cup R^n$$ The reflexive-transitive closure (denoted $R^*$) also adds diagonal self-loops: $$R^* = R^+ \cup \Delta_A = \bigcup_{k=0}^n R^k$$

---

⚡ Warshall's Algorithm: Dynamic Programming for Transitive Closure

Computing transitive closure by explicitly multiplying relation powers $R \cup R^2 \cup \dots \cup R^n$ requires $n$ Boolean matrix multiplications, consuming $O(n^4)$ time. Warshall's Algorithm solves all-pairs reachability using dynamic programming in $O(n^3)$ time.

Architecture Flow

Warshall's Algorithm Multi-Stage Matrix Evolution

Systematic reachability expansion through intermediate candidate vertices k = 1 to n

📋W⁽⁰⁾

Adjacency Matrix

Direct 1-hop edge connectivity M_R from the initial input relation.

→

Allow Hub k = 1

🔄W⁽¹⁾

Paths via Vertex 1

Updates reachability using vertex 1 as an intermediate bridge hop.

→

Allow Hub k = 2

⚡W⁽ᵏ⁾

Iterative Hub Expansion

W[i, j] = 1 if a path exists using intermediate vertices from {1, ..., k}.

→

Final Iteration k = n

🎯W⁽ⁿ⁾

Transitive Closure Matrix

Complete all-pairs reachability matrix representing full transitive closure R⁺.

📐Formula 2.5: Warshall's Dynamic Programming Recurrenceformula

Let vertices be indexed $\{1, 2, \dots, n\}$. Let $W^{(k)}[i, j]$ denote whether there is a directed path from vertex $i$ to vertex $j$ whose intermediate vertices all belong to the prefix set $\{1, 2, \dots, k\}$:

$$W^{(k)}[i, j] = W^{(k-1)}[i, j] \lor \Big( W^{(k-1)}[i, k] \land W^{(k-1)}[k, j] \Big)$$

Operational Meaning:

• A path exists from $i$ to $j$ using intermediate vertices up to $k$ if:
  1. A path already existed without vertex $k$ ($W^{(k-1)}[i, j] = 1$).
  2. OR there is a path from $i$ to $k$ AND a path from $k$ to $j$ using vertices from $\{1, \dots, k-1\}$.

Algorithmic Implementation & Efficiency

// Warshall's Algorithm in JavaScript / Node.js
function warshall(adjMatrix, n) {
  // Clone initial adjacency matrix W(0)
  const W = adjMatrix.map(row => [...row]);

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (W[i][k] === 1) { // Optimization: only inspect row i if path i -> k exists
        for (let j = 0; j < n; j++) {
          W[i][j] = W[i][j] || (W[i][k] && W[k][j]);
        }
      }
    }
  }
  return W; // W(n) represents the transitive closure
}

• Time Complexity: $O(n^3)$ operations. With bitwise 64-bit parallel word operations (W[i] |= W[k]), runtime improves by a factor of $64$.
• Space Complexity: $O(n^2)$ using in-place matrix updates.

---

⚖️ Equivalence Relations & Quotient Partitions

An equivalence relation formalizes the intuitive notion of elements being identical under a specific evaluation metric.

📖Definition 2.11: Equivalence Relationdefinition

A relation $R$ on set $A$ is an equivalence relation if and only if it satisfies three foundational axioms simultaneously:

1. Reflexive: $\forall x \in A, \; (x, x) \in R$
2. Symmetric: $\forall x, y \in A, \; (x, y) \in R \implies (y, x) \in R$
3. Transitive: $\forall x, y, z \in A, \; \Big( (x, y) \in R \land (y, z) \in R \Big) \implies (x, z) \in R$

Extremal Equivalence Relations

• Smallest Equivalence Relation: The diagonal identity relation $\Delta_A = \{(x, x) \mid x \in A\}$. It contains $n$ elements. Each element forms its own isolated singleton equivalence class.
• Largest Equivalence Relation: The universal relation $A \times A$. It contains $n^2$ elements. All elements merge into a single massive equivalence class.

Union & Intersection Invariants of Equivalence Relations

• Intersection: If $R_1$ and $R_2$ are equivalence relations on $A$, then their intersection $R_1 \cap R_2$ is guaranteed to be an equivalence relation.
  • Proof: Reflexivity, symmetry, and transitivity all distribute strictly across set intersection.
• Union: If $R_1$ and $R_2$ are equivalence relations on $A$, then their union $R_1 \cup R_2$ is NOT necessarily an equivalence relation!
  • While reflexivity and symmetry are preserved under union, transitivity frequently fails.
  • Concrete Counterexample: Let $A = \{1, 2, 3\}$.
    • $R_1 = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ (Equivalence)
    • $R_2 = \{(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)\}$ (Equivalence)
    • $R_1 \cup R_2$ contains $(1, 2)$ and $(2, 3)$. For transitivity, $(1, 3)$ must be present.
    • But $(1, 3) \notin (R_1 \cup R_2)$!
    • Hence, $R_1 \cup R_2$ is not an equivalence relation. The smallest equivalence relation containing $R_1 \cup R_2$ is its transitive closure $(R_1 \cup R_2)^+$.

---

🧩 Equivalence Classes & The Fundamental Partition Theorem

An equivalence relation naturally decomposes its domain set into mutually exclusive, exhaustive subsets called equivalence classes.

📖Definition 2.12: Equivalence Class & Quotient Setdefinition

Let $R$ be an equivalence relation on set $A$. For any element $a \in A$, the equivalence class of $a$, denoted by $[a]$ or $a/R$, is the set of all elements in $A$ related to $a$:

$$[a] = \{x \in A \mid (x, a) \in R\} = \{x \in A \mid a \, R \, x\}$$

Any element $x \in [a]$ is called a representative of the equivalence class.

The set of all distinct equivalence classes is called the quotient set of $A$ by $R$, denoted by $A/R$:

$$A/R = \{[a] \mid a \in A\}$$

Equivalence Relations vs Set Partitions: Bijective Duality

The exact 1-to-1 isomorphism between algebraic relations and geometric set partitions

Relation View

Equivalence Relation R ⊆ A × A

🔗

Dominant Architecture / DomainRelational Calculus & Matrix Algebra

• •Defines pairwise comparisons between elements: (x, y) ∈ R.
• •Must strictly satisfy Reflexivity, Symmetry, and Transitivity.
• •Encodes connectivity across a Boolean adjacency matrix.
• •Guarantees that [a] = [b] if and only if (a, b) ∈ R.

"Every equivalence relation automatically partitions its underlying set into disjoint cells."

Partition View

Set Partition Π = {A₁, A₂, ..., Aₖ}

🧩

Dominant Architecture / DomainCombinatorics & Disjoint Clustering

• •Decomposes set A into non-empty, pairwise disjoint blocks: A_i ∩ A_j = ∅.
• •Exhaustive: The union of all blocks reconstructs the entire set: ⋃ A_i = A.
• •Defines an equivalence relation by declaring (x, y) ∈ R ⇔ x, y reside in the same block.
• •Number of possible partitions of size n is given by the Bell Number B_n.

"Every valid partition of a set uniquely generates an equivalence relation."

📐Theorem 2.1: The Fundamental Theorem of Equivalence Relationstheorem

Let $R$ be an equivalence relation on set $A$. The collection of distinct equivalence classes $A/R$ forms a valid partition of set $A$:

1. Non-Empty Blocks: For every $a \in A$, $[a] \neq \emptyset$ (since $a \in [a]$ by reflexivity).
2. Pairwise Disjointness: For any $a, b \in A$, either $[a] = [b]$ or $[a] \cap [b] = \emptyset$. Two equivalence classes never partially overlap!
3. Exhaustive Union: The union of all equivalence classes reconstructs the original set $A$: $$\bigcup_{a \in A} [a] = A$$

Converse: Given any partition $\Pi = \{A_1, A_2, \dots, A_k\}$ of set $A$, the relation defined by:

$$(x, y) \in R \iff \exists i \text{ such that } x \in A_i \land y \in A_i$$

is guaranteed to be an equivalence relation whose equivalence classes are precisely the blocks $A_i$.

---

🔢 Counting Equivalence Relations: Bell Numbers & Bell's Triangle

Because every equivalence relation corresponds bijectively to a unique partition of the set, the total number of distinct equivalence relations on a set of size $n$ equals the Bell Number ($B_n$).

Construction of Bell's Triangle

Bell numbers are generated row-by-row using Bell's Triangle (also known as the Aitken array):

Row 1 (n=1):  [1]
Row 2 (n=2):  [1]   -->  (1+1) = [2]
Row 3 (n=3):  [2]   -->  (2+1) = 3   -->  (3+2) = [5]
Row 4 (n=4):  [5]   -->  (5+2) = 7   -->  (7+3) = 10  -->  (10+5) = [15]
Row 5 (n=5):  [15]  -->  (15+5) = 20 -->  27  -->  37  -->  [52]
Row 6 (n=6):  [52]  -->  67  -->  87  -->  114  -->  151  -->  [203]

Generation Rules:

1. Row 1 starts with $1$.
2. The first number of each new row is the last number of the previous row.
3. Every subsequent entry is computed by adding the number immediately to the left and the number directly above-left: $$A(n, k) = A(n, k-1) + A(n-1, k-1)$$
4. The last number of row $n$ is the Bell number $B_n$.

📐Formula 2.6: Bell Numbers & Partition Recurrenceformula

The total number of equivalence relations on a set of cardinality $n$ is:

Set Size $\vert A \vert = n$	Bell Number $B_n$ (Total Equivalence Relations)
$n = 0$	$B_0 = 1$ (Empty partition)
$n = 1$	$B_1 = 1$
$n = 2$	$B_2 = 2$
$n = 3$	$B_3 = 5$
$n = 4$	$B_4 = 15$
$n = 5$	$B_5 = 52$
$n = 6$	$B_6 = 203$

Combinatorial Recurrence Formula:

$$B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_k$$

Using Stirling Numbers of the Second Kind $S(n, k)$ (partitions of $n$ elements into exactly $k$ non-empty subsets):

$$B_n = \sum_{k=1}^{n} S(n, k)$$

---

🌍 Real-World Engineering Context

1. Disjoint-Set Union (DSU / Union-Find): In Kruskal's Minimum Spanning Tree algorithm and network cycle detection, connected components are maintained as dynamic equivalence classes. The find(u) operation returns the canonical representative of $u$'s equivalence class $[u]$, while union(u, v) merges two classes in near-linear $O(\alpha(V))$ time.
2. DFA Minimization (Hopcroft's & Moore's Algorithms): In compiler construction, minimizing a Deterministic Finite Automaton (DFA) begins with the language equivalence relation $\equiv_L$. States $p$ and $q$ are equivalent if for all strings $w$, $\hat{\delta}(p, w)$ and $\hat{\delta}(q, w)$ lead to identical acceptance outcomes. Equivalence classes of states merge into single states in the minimal DFA.
3. Database Relational Clustering: In distributed database engines (Snowflake, BigQuery), clustered tables partition records into micro-partitions using hash equivalence relations, allowing the query engine to prune entire partition files during query execution.

---

📝 Step-by-Step Worked Examples

Example 1: Calculating Reflexive, Symmetric and Transitive Closures

Problem Statement:
Let $A = \{1, 2, 3\}$ and relation $R = \{(1, 2), (2, 3), (3, 1)\}$.

1. Determine the reflexive closure $r(R)$.
2. Determine the symmetric closure $s(R)$.
3. Determine the transitive closure $t(R)$.

Step-by-Step Solution:

1. Reflexive Closure $r(R)$: Add all diagonal pairs $\Delta_A = \{(1, 1), (2, 2), (3, 3)\}$: $$r(R) = R \cup \Delta_A = \{(1, 2), (2, 3), (3, 1), (1, 1), (2, 2), (3, 3)\}$$
2. Symmetric Closure $s(R)$: Add all reverse pairs $R^{-1} = \{(2, 1), (3, 2), (1, 3)\}$: $$s(R) = R \cup R^{-1} = \{(1, 2), (2, 3), (3, 1), (2, 1), (3, 2), (1, 3)\}$$
3. Transitive Closure $t(R)$:
   • 1-hop pairs: $R = \{(1, 2), (2, 3), (3, 1)\}$
   • 2-hop pairs ($R^2 = R \circ R$):
     • $(1, 2)$ and $(2, 3) \implies (1, 3)$
     • $(2, 3)$ and $(3, 1) \implies (2, 1)$
     • $(3, 1)$ and $(1, 2) \implies (3, 2)$
     • $\implies R^2 = \{(1, 3), (2, 1), (3, 2)\}$
   • 3-hop pairs ($R^3 = R^2 \circ R$):
     • $(1, 3)$ and $(3, 1) \implies (1, 1)$
     • $(2, 1)$ and $(1, 2) \implies (2, 2)$
     • $(3, 2)$ and $(2, 3) \implies (3, 3)$
     • $\implies R^3 = \{(1, 1), (2, 2), (3, 3)\}$
   • Combining $R \cup R^2 \cup R^3$: $$t(R) = R \cup R^2 \cup R^3 = A \times A$$
   Because the directed graph contains a 3-cycle traversing all vertices, every vertex can reach every other vertex. The transitive closure is the full universal relation $A \times A$!

Key Takeaway:
If a relation forms a directed cycle containing all $n$ vertices, its transitive closure encompasses the entire Cartesian space $A \times A$.

---

Example 2: Execution Trace of Warshall's Algorithm

Problem Statement:
Let $A = \{1, 2, 3, 4\}$, and let the directed adjacency matrix $W^{(0)}$ be:

$$W^{(0)} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$

Trace Warshall's algorithm to compute the transitive closure matrix $W^{(4)}$.

Step-by-Step Solution:

1. Iteration $k = 1$ (Allowing intermediate vertex 1):
   • Column 1 has a $1$ at Row $i$: None (no edges lead into vertex 1).
   • Since Column 1 is all zeros, no paths can route through vertex 1.
   $$W^{(1)} = W^{(0)}$$
2. Iteration $k = 2$ (Allowing intermediate vertex 2):
   • Column 2 has a $1$ at Row 1 ($W^{(1)}[1, 2] = 1$).
   • Row 2 has a $1$ at Column 3 ($W^{(1)}[2, 3] = 1$).
   • Apply update: $W^{(2)}[1, 3] = W^{(1)}[1, 3] \lor (1 \land 1) = 1$.
   $$W^{(2)} = \begin{pmatrix} 0 & 1 & \mathbf{1} & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$
3. Iteration $k = 3$ (Allowing intermediate vertex 3):
   • Column 3 has $1$s at Row 1 and Row 2.
   • Row 3 has a $1$ at Column 4 ($W^{(2)}[3, 4] = 1$).
   • Updates:
     • $W^{(3)}[1, 4] = W^{(2)}[1, 4] \lor (1 \land 1) = 1$
     • $W^{(3)}[2, 4] = W^{(2)}[2, 4] \lor (1 \land 1) = 1$
   $$W^{(3)} = \begin{pmatrix} 0 & 1 & 1 & \mathbf{1} \\ 0 & 0 & 1 & \mathbf{1} \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$
4. Iteration $k = 4$ (Allowing intermediate vertex 4):
   • Row 4 is all zeros (vertex 4 has no outgoing edges).
   • No new entries added:
   $$W^{(4)} = W^{(3)} = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$$

Key Takeaway:
Each step $k$ in Warshall's algorithm expands reachability by linking every vertex with an edge into $k$ to every vertex with an edge out of $k$.

---

Example 3: Deriving Equivalence Classes and Quotient Sets

Problem Statement:
Let $A = \{1, 2, 3, 4, 5, 6, 7, 8\}$. Define a relation $R$ on $A$ by:

$$a \, R \, b \iff a \equiv b \pmod 3$$

1. Prove that $R$ is an equivalence relation.
2. Determine all distinct equivalence classes.
3. Construct the quotient set $A/R$.

Step-by-Step Solution:

1. Verifying Equivalence Axioms:
   • Reflexive: For any $a \in A$, $a - a = 0 = 3 \times 0$. Thus $a \equiv a \pmod 3$. Reflexive: Yes.
   • Symmetric: If $a \equiv b \pmod 3$, then $a - b = 3k$ for some $k \in \mathbb{Z}$. Then $b - a = 3(-k)$. Thus $b \equiv a \pmod 3$. Symmetric: Yes.
   • Transitive: If $a \equiv b \pmod 3$ and $b \equiv c \pmod 3$, then $a - b = 3k_1$ and $b - c = 3k_2$. Adding equations gives $a - c = 3(k_1 + k_2)$. Thus $a \equiv c \pmod 3$. Transitive: Yes.
   • Conclusion: $R$ is an equivalence relation.
2. Determining Equivalence Classes:
   • Class $[1]$: Elements $x \in A$ such that $x \equiv 1 \pmod 3$: $$[1] = \{1, 4, 7\}$$
   • Class $[2]$: Elements $x \in A$ such that $x \equiv 2 \pmod 3$: $$[2] = \{2, 5, 8\}$$
   • Class $[3]$: Elements $x \in A$ such that $x \equiv 0 \pmod 3$: $$[3] = \{3, 6\}$$
3. Constructing Quotient Set $A/R$: Notice:
   • $[1] \cap [2] = \emptyset$, $[2] \cap [3] = \emptyset$, $[1] \cap [3] = \emptyset$ (Pairwise disjoint).
   • $[1] \cup [2] \cup [3] = \{1, 4, 7\} \cup \{2, 5, 8\} \cup \{3, 6\} = A$ (Exhaustive union).
   $$A/R = \big\{ \{1, 4, 7\}, \; \{2, 5, 8\}, \; \{3, 6\} \big\}$$

Key Takeaway:
Modulo congruence $\equiv_m$ partitions the integers into exactly $m$ disjoint equivalence classes corresponding to remainders $\{0, 1, \dots, m-1\}$.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: "Why is the intersection of two equivalence relations always an equivalence relation, but their union is not?"
Key Focus Points:

• Intersection Invariance: If $(a, b) \in R_1 \cap R_2$ and $(b, c) \in R_1 \cap R_2$, then $(a, c) \in R_1$ (since $R_1$ is transitive) and $(a, c) \in R_2$ (since $R_2$ is transitive). Therefore $(a, c) \in R_1 \cap R_2$. Transitivity holds identically.
• Union Breakdown: In $R_1 \cup R_2$, a path can alternate between an edge from $R_1$ and an edge from $R_2$ ($a \xrightarrow{R_1} b \xrightarrow{R_2} c$). The shortcut $(a, c)$ belongs to neither $R_1$ nor $R_2$ alone, breaking transitivity.

Question 2: "How do Bell numbers relate to set partitions and equivalence relations?"
Key Focus Points:

• Bijective Correspondence: By the Fundamental Theorem of Equivalence Relations, there is an exact 1-to-1 bijection between equivalence relations on set $A$ and partitions of set $A$.
• Definition of Bell Numbers: $B_n$ is defined as the number of ways to partition a set of $n$ elements into non-empty disjoint subsets. Therefore, the total number of equivalence relations on an $n$-element set is strictly $B_n$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Is Warshall's algorithm the same as Floyd-Warshall's algorithm?
Answer: They are closely related, but distinct. Warshall's algorithm (1962) computes 0-1 unweighted reachability (transitive closure) using Boolean operations ($\lor, \land$). Floyd's algorithm (1962) generalizes Warshall's algorithm to weighted graphs to compute all-pairs shortest path distances using real arithmetic ($\min, +$).

Trap 2: Can two distinct equivalence classes share an element?
Answer: Never! If two equivalence classes share even a single element $x \in ([a] \cap [b])$, then by symmetry and transitivity, $a \, R \, x \land x \, R \, b \implies a \, R \, b$. This forces $[a] = [b]$! Two equivalence classes are either completely identical or completely disjoint.

---

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic2.2 Relational Properties: Reflexivity, Symmetry, Transitivity & AntisymmetryNext Topic →3.1 Function Mappings: Injective, Surjective & Bijective Classifications