Relations

A relation R from A to B is a set of ordered pairs (a, b) with a ∈ A and b ∈ B, that is, a subset of A × B. We write a R b when (a, b) ∈ R. A relation on A is one from A to A.

"Is less than" on {1, 2, 3} is the set {(1, 2), (1, 3), (2, 3)}. A function is a special relation: each a appears in exactly one pair.

A relation on a small set can be drawn as a matrix (row a, column b, a 1 where a R b) or as a directed graph (an arrow a → b for each pair).

Four properties

Symmetric and antisymmetric are not opposites: "=" is both, and some relations are neither.

def properties(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 = [1, 2, 3, 4]
divides = {(a, b) for a in A for b in A if b % a == 0}
same_parity = {(a, b) for a in A for b in A if a % 2 == b % 2}

print("divides:", properties(divides, A))
print("same parity:", properties(same_parity, A))

# The equivalence classes of "same remainder mod 3"
classes = {}
for x in range(9):
    classes.setdefault(x % 3, []).append(x)
print("mod 3 classes:", list(classes.values()))

Each property is a "for all" statement, so the program checks it with all(...) over every element or pair.

Equivalence relations

A relation that is reflexive, symmetric and transitive is an equivalence relation: it says two things are "the same" in some way. Examples: "has the same birthday as", "has the same remainder when divided by 3".

An equivalence relation splits the set into equivalence classes: groups of elements related to each other. The classes do not overlap and cover the whole set (a partition). For "same remainder mod 3" on {0, ..., 8}, the classes are {0, 3, 6}, {1, 4, 7} and {2, 5, 8}.

Partial orders

A relation that is reflexive, antisymmetric and transitive is a partial order: it ranks elements, but not every pair needs to be comparable. Examples: ≤ on numbers, ⊆ on sets, and "divides" on positive integers (2 | 6, but 2 and 3 are not comparable). A partial order where every pair is comparable, like ≤, is a total order.

A Hasse diagram draws a partial order with the smaller element lower, leaving out the arrows that reflexivity and transitivity would add.

Closures

The transitive closure of R adds the fewest pairs needed to make it transitive: if there are flights Dhaka → Chattogram and Chattogram → Cox's Bazar, the closure adds Dhaka → Cox's Bazar ("reachable by some route"). Warshall's algorithm computes it, like the Floyd-Warshall algorithm in the Algorithms course.

Mark lesson complete