Relations

A binary relation R on a set A is any subset of A × A; we write a R b when (a, b) ∈ R. "Less than", "divides" and "has the same remainder mod 3" are relations on the integers.

A relation on a finite set can be drawn as a 0/1 matrix (entry (a, b) is 1 when a R b) or as a directed graph (an arrow a → b when a R b). On a set of n elements there are n² possible pairs, so 2^(n²) relations.

Properties

Symmetric and antisymmetric are not opposites: the equality relation is both, and some relations are neither.

Counting relations on an n-element set

Each property restricts some entries of the n × n matrix. Counting the free choices gives:

A brute-force check over all 512 relations on {0, 1, 2}:

from itertools import product

n = 3
S = range(n)
pairs = [(a, b) for a in S for b in S]
counts = dict.fromkeys(["reflexive", "symmetric", "antisymmetric", "transitive", "equivalence", "partial order"], 0)

for mask in range(2 ** len(pairs)):
    R = {pairs[i] for i in range(len(pairs)) if mask >> i & 1}
    reflexive = all((a, a) in R for a in S)
    symmetric = all((b, a) in R for a, b in R)
    antisymmetric = all(a == b or (b, a) not in R for a, b in R)
    transitive = all((a, d) in R for a, b in R for c, d in R if b == c)
    counts["reflexive"] += reflexive
    counts["symmetric"] += symmetric
    counts["antisymmetric"] += antisymmetric
    counts["transitive"] += transitive
    counts["equivalence"] += reflexive and symmetric and transitive
    counts["partial order"] += reflexive and antisymmetric and transitive
print(counts)

{'reflexive': 64, 'symmetric': 64, 'antisymmetric': 216, 'transitive': 171, 'equivalence': 5, 'partial order': 19}

Closures

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

• Reflexive closure: add all pairs (a, a).
• Symmetric closure: add (b, a) for every (a, b) ∈ R.
• Transitive closure R⁺: add (a, c) whenever there is a path from a to c in the graph of R. It is computed by Warshall's algorithm in O(n³), the same idea as Floyd–Warshall for shortest paths.

Equivalence relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. It splits the set into disjoint equivalence classes [a] = {x : x R a}: a partition. Conversely, every partition defines an equivalence relation ("in the same block").

Example: congruence mod 3 on the integers has three classes, [0], [1] and [2].

So the number of equivalence relations on an n-element set equals the number of partitions of the set, the Bell number Bₙ: 1, 1, 2, 5, 15, 52, 203, … (for n = 0, 1, 2, …). They satisfy B_n+1 = Σₖ C(n, k) Bₖ. The number of partitions into exactly k non-empty blocks is the Stirling number of the second kind S(n, k).

Practice questions