Binary Relations, Equivalence Classes & Warshall's Transitive Closure

Explanation

Binary relations formalize associations between entities, serving as the mathematical underpinning of relational databases (Codd's relational model). Equivalence relations partition data spaces into non-overlapping clusters. The transitive closure of a relation represents the existence of directed paths of arbitrary length between nodes in a network.

Key points

• Properties on a set A: Reflexive (∀a, (a,a) ∈ R); Symmetric (∀a,b, (a,b) ∈ R => (b,a) ∈ R); Antisymmetric (∀a,b, if (a,b) ∈ R and (b,a) ∈ R then a = b); Transitive (∀a,b,c, if (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R).
• Equivalence Relation: A relation that is simultaneously Reflexive, Symmetric, and Transitive. Partitions set A into disjoint Equivalence Classes [a] = {x ∈ A | (a, x) ∈ R}.
• Closures: Reflexive closure R ∪ Δ; Symmetric closure R ∪ R⁻¹; Transitive closure R* (reachability in graphs).
• Warshall's Algorithm: Computes transitive closure of a relation represented as an n×n zero-one matrix in O(n³) operations using dynamic programming.

Example

Code examples

// Warshall's Algorithm in C++ to Compute Transitive Closure Matrix
#include <iostream>
#include <vector>
using namespace std;

void warshall(vector<vector<int>>& W, int n) {
    for (int k = 0; k < n; k++) {          // Intermediate vertex k
        for (int i = 0; i < n; i++) {      // Source vertex i
            for (int j = 0; j < n; j++) {  // Destination vertex j
                W[i][j] = W[i][j] || (W[i][k] && W[k][j]);
            }
        }
    }
}

int main() {
    int n = 4;
    vector<vector<int>> adj = {
        {0, 1, 0, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0},
        {1, 0, 1, 0}
    };
    warshall(adj, n);
    // adj now contains the reachability / transitive closure matrix!
    return 0;
}

Exam questions

• [8 Marks] Define an equivalence relation. Prove that the relation R on ℤ defined by (a, b) ∈ R iff (a - b) is divisible by 5 is an equivalence relation. Determine its equivalence classes.
• [7 Marks] Apply Warshall's algorithm to find the transitive closure of the relation R = {(1,2), (2,3), (3,4), (4,1)} on A = {1, 2, 3, 4}.
• [7 Marks] Determine whether the relation R on positive integers defined by (a, b) ∈ R iff a divides b is a partial order relation. Justify.