Relations

A relation R from set A to set B is a subset of A × B. If (a, b) ∈ R we write a R b: "a is related to b". A relation on A is a subset of A × A.

Example on A = {1, 2, 3, 4}: R = "divides" = {(a, b) : a | b}.

R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

#Representations

Matrix: M[i][j] = 1 if (i, j) ∈ R.

Digraph: an arrow from a to b for each pair, with a loop at a for each (a, a).

#Properties of a relation on A

"Divides" is reflexive, antisymmetric and transitive, but not symmetric (1 | 2, but 2 ∤ 1).

def properties(A, R):
    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}
less_than = {(a, b) for a in A for b in A if a < b}
for name, R in [("divides", divides), ("same parity", same_parity), ("less than", less_than)]:
    print(f"{name:12}", properties(A, R))

divides      {'reflexive': True, 'symmetric': False, 'antisymmetric': True, 'transitive': True}
same parity  {'reflexive': True, 'symmetric': True, 'antisymmetric': False, 'transitive': True}
less than    {'reflexive': False, 'symmetric': False, 'antisymmetric': True, 'transitive': True}

#Equivalence relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. It splits A into disjoint equivalence classes: [a] = {x : x R a}.

Example: congruence mod 3 on ℤ — a ≡ b (mod 3) when 3 | (a − b). Its classes are:

• [0] = {…, −3, 0, 3, 6, …}
• [1] = {…, −2, 1, 4, 7, …}
• [2] = {…, −1, 2, 5, 8, …}

The classes form a partition of the set: they are non-empty, pairwise disjoint, and together cover everything. Conversely, every partition defines an equivalence relation ("in the same block").

A = range(0, 12)
classes = {}
for x in A:
    classes.setdefault(x % 3, []).append(x)      # same remainder = same class
for r, members in classes.items():
    print(f"[{r}] = {members}")

[0] = [0, 3, 6, 9]
[1] = [1, 4, 7, 10]
[2] = [2, 5, 8, 11]

#Closures

The closure of R with respect to a property is the smallest relation containing R that has the property.

def transitive_closure(A, R):
    R = set(R)
    for k in A:                          # Warshall: allow k as an intermediate vertex
        for i in A:
            for j in A:
                if (i, k) in R and (k, j) in R:
                    R.add((i, j))
    return R

A = [1, 2, 3, 4]
R = {(1, 2), (2, 3), (3, 4)}
print(sorted(transitive_closure(A, R)))

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

(The same triple loop computes shortest paths in Floyd–Warshall.)