Relations, equivalence and partial orders

A function pairs each input with exactly one output. Many relationships in computing are less restrictive: a student takes several courses, a web page links to many pages, a task must finish before several others start. A relation captures any such relationship. This lesson defines relations, studies their key properties, and focuses on two especially important kinds: equivalence relations, which group objects that are alike, and partial orders, which arrange objects by precedence. It ends with closures and Warshall's algorithm, which computes reachability.

Relations

A binary relation \(R\) from a set \(A\) to a set \(B\) is any subset of \(A \times B\). We write \(a\, R\, b\) or \((a, b) \in R\) when \(a\) is related to \(b\). A relation on \(A\) is a relation from \(A\) to itself. Every function is a relation, but a relation can relate one element to many others, or to none.

Relations on a finite set can be represented in three common ways, and each is useful in programming. A set of pairs is the direct definition. A directed graph draws each element as a dot and each pair \((a, b)\) as an arrow from \(a\) to \(b\). A Boolean matrix \(M\) has \(M[i][j] = 1\) exactly when element \(i\) is related to element \(j\).

A = [1, 2, 3, 4]
divides = {(a, b) for a in A for b in A if b % a == 0}
print("pairs:", sorted(divides))
print("matrix (row a, column b):")
for a in A:
    print("   ", [1 if (a, b) in divides else 0 for b in A])

pairs: [(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)]
matrix (row a, column b):
    [1, 1, 1, 1]
    [0, 1, 0, 1]
    [0, 0, 1, 0]
    [0, 0, 0, 1]

Relational databases are named after this idea. A table with columns student and course is a relation from Students to Courses, and a table with more columns is an \(n\)-ary relation, a subset of an \(n\)-fold Cartesian product. The operations of relational algebra, which SQL implements, are set operations on relations. You will use them in CMPUT-291.

Properties of relations

Four properties of a relation \(R\) on a set \(A\) appear again and again.

Antisymmetric is not the opposite of symmetric. A relation can be both (equality is both symmetric and antisymmetric) or neither. Antisymmetry says that the only way two elements can be related in both directions is if they are the same element. In the graph picture, a reflexive relation has a loop at every vertex, a symmetric relation has every arrow paired with a reverse arrow, and an antisymmetric relation has no pair of distinct vertices with arrows both ways.

def props(R, A):
    return {
        "reflexive": all((a, a) in R for a in A),
        "symmetric": all((b, a) in R for (a, b) in R),
        "antisymmetric": all(a == b for (a, b) in R if (b, a) in R),
        "transitive": all((a, d) in R for (a, b) in R for (c, d) in R if b == c),
    }

A = range(1, 7)
relations = {
    "divides": {(a, b) for a in A for b in A if b % a == 0},
    "less than": {(a, b) for a in A for b in A if a < b},
    "same parity": {(a, b) for a in A for b in A if a % 2 == b % 2},
    "differ by 1": {(a, b) for a in A for b in A if abs(a - b) == 1},
}
for name, R in relations.items():
    p = props(R, A)
    print(f"{name:12s}", "  ".join(f"{k[:5]}={'Y' if v else 'n'}" for k, v in p.items()))

divides      refle=Y  symme=n  antis=Y  trans=Y
less than    refle=n  symme=n  antis=Y  trans=Y
same parity  refle=Y  symme=Y  antis=n  trans=Y
differ by 1  refle=n  symme=Y  antis=n  trans=n

Equivalence relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. It expresses a notion of sameness: two objects are related if they are alike in some respect. Equality is the strictest equivalence relation. Other examples: having the same remainder when divided by \(n\); having the same file extension; being reachable from each other along roads; being anagrams of each other.

The equivalence class of an element \(a\), written \([a]\), is the set of all elements related to \(a\): \([a] = \{x \in A \mid x\, R\, a\}\). The central theorem is that the equivalence classes of an equivalence relation partition the set: every element belongs to exactly one class, and two classes are either identical or disjoint. Conversely, every partition defines an equivalence relation, namely being in the same part. Equivalence relations and partitions are two descriptions of the same thing.

words = ["listen", "silent", "enlist", "google", "banana", "tinsel", "elgoog", "nabana"]
classes = {}
for w in words:
    key = "".join(sorted(w))            # anagrams share the same sorted letters
    classes.setdefault(key, []).append(w)
for key, members in classes.items():
    print(f"[{members[0]}] = {members}")
print("classes are disjoint and cover all words:",
      sum(len(m) for m in classes.values()) == len(words))

[listen] = ['listen', 'silent', 'enlist', 'tinsel']
[google] = ['google', 'elgoog']
[banana] = ['banana', 'nabana']
classes are disjoint and cover all words: True

The program uses a standard technique: compute a canonical key for each element so that two elements are equivalent exactly when their keys are equal, then group by key. Hash-based grouping, database GROUP BY, and duplicate detection all work this way. Union–find, a data structure you will meet in CMPUT-204, maintains equivalence classes as pairs are added, and is used in Kruskal's minimum spanning tree algorithm.

Partial orders

A relation that is reflexive, antisymmetric and transitive is a partial order. A set with a partial order is called a poset. Partial orders describe precedence or containment: \(\le\) on numbers, \(\subseteq\) on sets, divides on positive integers, and is a prerequisite of on courses (taking the relation to include each course itself). The word partial means that some pairs may be incomparable: neither \(\{1\} \subseteq \{2\}\) nor \(\{2\} \subseteq \{1\}\). If every pair is comparable, the order is a total order, like \(\le\) on the integers.

A Hasse diagram draws a finite poset compactly. Place each element above the elements it is greater than, draw a line from \(a\) up to \(b\) only when \(a\) is below \(b\) with nothing in between, and omit loops and lines implied by transitivity. Reading upward along lines recovers the whole order.

Some elements of a poset are special. A minimal element has nothing below it; a maximal element has nothing above it. A least element is below everything, and a greatest element is above everything. In the divisors of 12, 1 is least and 12 is greatest. In the set \(\{2, 3, 4, 6\}\) under divides, both 2 and 3 are minimal but there is no least element.

Topological sorting

Many scheduling problems ask for a total order that respects a partial order: take courses in an order that respects prerequisites, compile modules so that each comes after the modules it imports, run build steps in a valid sequence. Such a total order is a topological sort. Every finite poset has one, and it can be found by repeatedly removing a minimal element.

prereq = {                 # course: set of courses that must come first
    "CMPUT-174": set(),
    "CMPUT-201": {"CMPUT-174"},
    "CMPUT-272": {"CMPUT-174"},
    "CMPUT-204": {"CMPUT-201", "CMPUT-272"},
    "CMPUT-304": {"CMPUT-204"},
    "CMPUT-474": {"CMPUT-272", "CMPUT-204"},
}
order, remaining = [], {c: set(p) for c, p in prereq.items()}
while remaining:
    minimal = sorted(c for c, p in remaining.items() if not p)   # no unmet prerequisites
    if not minimal:
        raise ValueError("cycle: no valid order")
    c = minimal[0]
    order.append(c)
    del remaining[c]
    for p in remaining.values():
        p.discard(c)
print(" -> ".join(order))

CMPUT-174 -> CMPUT-201 -> CMPUT-272 -> CMPUT-204 -> CMPUT-304 -> CMPUT-474

If the relation contains a cycle, for example A before B and B before A, antisymmetry fails, the relation is not a partial order, and no valid order exists. The program above detects this when no minimal element remains. Build tools and package managers report exactly this situation as a circular dependency.

Closures and Warshall's algorithm

A relation may lack a property we need. The closure of \(R\) with respect to a property is the smallest relation containing \(R\) that has the property. The reflexive closure adds every pair \((a, a)\); the symmetric closure adds every reverse pair \((b, a)\). The transitive closure is the most useful and the hardest: it adds \((a, c)\) whenever there is a path from \(a\) to \(c\) through any number of steps. If \(R\) is is a direct flight to, its transitive closure is can be reached by some sequence of flights.

Warshall's algorithm computes the transitive closure of a relation on \(n\) elements in \(n^3\) steps. It considers each element \(k\) in turn as a possible intermediate stop and adds \((i, j)\) whenever \((i, k)\) and \((k, j)\) are already present.

def warshall(M):
    n = len(M)
    R = [row[:] for row in M]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                R[i][j] = R[i][j] or (R[i][k] and R[k][j])
    return R

names = ["a", "b", "c", "d"]
M = [[0, 1, 0, 0],    # a -> b
     [0, 0, 1, 0],    # b -> c
     [0, 0, 0, 1],    # c -> d
     [0, 0, 0, 0]]
T = warshall(M)
for i, row in enumerate(T):
    print(names[i], "reaches", [names[j] for j in range(4) if row[j]])

a reaches ['b', 'c', 'd']
b reaches ['c', 'd']
c reaches ['d']
d reaches []

Warshall's algorithm, published by Stephen Warshall in 1962, is closely related to the Floyd–Warshall algorithm for shortest paths, which you will study in CMPUT-204. Its correctness proof is an induction on \(k\): after round \(k\), the matrix records every path whose intermediate stops all lie among the first \(k\) elements. That is a loop invariant, the topic of lesson 12.