Relations, equivalence relations and partitions

Many of the most useful ideas in mathematics are ways of saying that two things are related: one number divides another, two integers leave the same remainder, two triangles are similar, one set is a subset of another. A relation is the general form of all of these. This lesson defines relations as sets of ordered pairs, studies the properties a relation can have, and proves the central theorem of the topic: equivalence relations on a set and partitions of that set are the same thing seen from two sides. That theorem is how mathematicians build new objects, such as the integers modulo \(n\) in number theory and the rational numbers from pairs of integers, by deciding which things to treat as equal.

Relations as sets of pairs

A relation \(R\) on a set \(A\) is a subset of \(A \times A\). If \((a, b) \in R\) we write \(a \, R \, b\) and say \(a\) is related to \(b\). The definition is deliberately bare: any set of pairs is a relation, whether or not it follows a pattern. The relation \(<\) on \(\mathbb{Z}\) is the set \(\{(a, b) : a < b\}\), and divisibility on the positive integers is \(\{(a, b) : a \mid b\}\). On the finite set \(A = \{1, 2, 3\}\), the set \(R = \{(1, 1), (1, 2), (3, 2)\}\) is a relation with no particular meaning at all.

A function \(f : A \to A\) is a special kind of relation, one in which each \(a\) is related to exactly one \(b\). Relations in general allow an element to be related to many elements or to none. More generally a relation from \(A\) to \(B\) is a subset of \(A \times B\), but this lesson concentrates on relations on a single set.

Finite relations can be drawn as directed graphs: a dot for each element and an arrow from \(a\) to \(b\) when \(a \, R \, b\), with a loop at \(a\) when \(a \, R \, a\). They can also be written as a table of zeros and ones, with a 1 in row \(a\) and column \(b\) when \(a \, R \, b\). Both pictures make the properties below easy to see.

Properties of relations

A relation \(R\) on \(A\) is reflexive if \(a \, R \, a\) for every \(a \in A\); symmetric if \(a \, R \, b\) implies \(b \, R \, a\); antisymmetric if \(a \, R \, b\) and \(b \, R \, a\) together imply \(a = b\); and transitive if \(a \, R \, b\) and \(b \, R \, c\) together imply \(a \, R \, c\). In the arrow picture: reflexive means a loop at every dot; symmetric means every arrow has a return arrow; antisymmetric means no pair of distinct dots has arrows both ways; transitive means every two-step path has a one-step shortcut.

Each 'no' in the table has a witness. Divisibility is not symmetric because \(2 \mid 4\) but \(4 \nmid 2\). Congruence mod \(n\) is not antisymmetric because \(0 \equiv n\) but \(0 \ne n\). The relation \(|a - b| \le 1\) is not transitive because \(0\) is within 1 of \(0.8\) and \(0.8\) is within 1 of \(1.6\), but \(0\) is not within 1 of \(1.6\). That last relation, 'close to', is a reminder that a sensible-sounding notion of similarity can fail transitivity, which is why the definition of an equivalence relation insists on it.

Watch the quantifiers. Symmetry is a conditional statement about all pairs, so a relation can be symmetric because it has no pairs at all; the empty relation on \(A\) is symmetric, antisymmetric and transitive, though not reflexive unless \(A\) is empty. Symmetry and antisymmetry are not opposites: the equality relation has both properties, and \(\{(1, 2), (2, 1), (1, 3)\}\) on \(\{1, 2, 3\}\) has neither.

Equivalence relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. Equivalence relations capture the idea of 'the same in some respect': same remainder, same birthday, same shape, same cardinality. They are often written \(a \sim b\).

The most important example is congruence modulo a positive integer \(n\): \(a \equiv b \pmod{n}\) means \(n \mid (a - b)\). Theorem: congruence modulo \(n\) is an equivalence relation on \(\mathbb{Z}\).

Proof. Reflexive: \(a - a = 0 = n \cdot 0\), so \(n \mid (a - a)\). Symmetric: if \(a - b = nk\) then \(b - a = n(-k)\), so \(n \mid (b - a)\). Transitive: if \(a - b = nk\) and \(b - c = nm\) then \(a - c = (a - b) + (b - c) = n(k + m)\), so \(n \mid (a - c)\). \(\blacksquare\)

Equivalence classes

If \(\sim\) is an equivalence relation on \(A\) and \(a \in A\), the equivalence class of \(a\) is \([a] = \{x \in A : x \sim a\}\), the set of everything equivalent to \(a\). Under congruence mod 3 there are three classes: \([0] = \{\ldots, -3, 0, 3, 6, \ldots\}\), \([1] = \{\ldots, -2, 1, 4, 7, \ldots\}\) and \([2] = \{\ldots, -1, 2, 5, 8, \ldots\}\). Each integer lies in exactly one, determined by its remainder on division by 3, which is the division algorithm from lesson 8. Note that \([1] = [4] = [-2]\): a class has many names, and any member can serve as its representative.

Lemma. Let \(\sim\) be an equivalence relation on \(A\) and let \(a, b \in A\). Then \(a \sim b\) if and only if \([a] = [b]\). Moreover, any two equivalence classes are either equal or disjoint.

Proof. Suppose \(a \sim b\). If \(x \in [a]\) then \(x \sim a\), and with \(a \sim b\) transitivity gives \(x \sim b\), so \(x \in [b]\). This shows \([a] \subseteq [b]\). By symmetry \(b \sim a\), and the same argument gives \([b] \subseteq [a]\). So \([a] = [b]\). Conversely if \([a] = [b]\), then \(a \in [a]\) by reflexivity, so \(a \in [b]\), which means \(a \sim b\). For the second claim, suppose \([a]\) and \([b]\) are not disjoint, and pick \(x\) in both. Then \(x \sim a\) and \(x \sim b\), so \(a \sim x\) by symmetry and \(a \sim b\) by transitivity. By the first part \([a] = [b]\). \(\blacksquare\)

The proof uses all three properties, each for a specific reason: reflexivity makes every element belong to its own class, so no class is empty and nothing is left out; symmetry and transitivity make overlapping classes coincide.

Partitions

A partition of a set \(A\) is a collection of non-empty subsets of \(A\), called blocks or parts, such that every element of \(A\) lies in exactly one block. The blocks are pairwise disjoint and their union is \(A\). The even and odd integers form a partition of \(\mathbb{Z}\) into two blocks. The singletons \(\{a\}\) form a partition of any set into the finest possible pieces; the single block \(\{A\}\) is the coarsest.

Theorem (the fundamental theorem on equivalence relations). (a) If \(\sim\) is an equivalence relation on \(A\), the set of equivalence classes is a partition of \(A\). (b) Conversely, if \(\mathcal{P}\) is a partition of \(A\), the relation 'in the same block', defined by \(a \sim b\) when \(a\) and \(b\) lie in a common block of \(\mathcal{P}\), is an equivalence relation whose classes are exactly the blocks of \(\mathcal{P}\).

Proof. (a) Each class \([a]\) is non-empty because it contains \(a\). Each \(a \in A\) lies in at least one class, namely \([a]\), and by the lemma any two classes are equal or disjoint, so \(a\) lies in only one. (b) Every \(a\) lies in some block, so \(a \sim a\). If \(a\) and \(b\) share a block, so do \(b\) and \(a\). If \(a, b\) share block \(P\) and \(b, c\) share block \(Q\), then \(b \in P \cap Q\), so \(P = Q\) because distinct blocks are disjoint; hence \(a, c\) share a block. Finally the class of \(a\) is the set of elements sharing \(a\)'s block, which is that block. \(\blacksquare\)

The set of equivalence classes of \(\sim\) on \(A\) is the quotient set \(A / {\sim}\). For congruence mod \(n\) it is written \(\mathbb{Z}_n = \{[0], [1], \ldots, [n - 1]\}\). Arithmetic on classes is defined by \([a] + [b] = [a + b]\) and \([a][b] = [ab]\), and the work is to show this is well defined: the answer must not depend on which representatives are chosen. If \(a \equiv a'\) and \(b \equiv b'\), then \(a + b \equiv a' + b'\) and \(ab \equiv a'b'\), so it is. This is the foundation of modular arithmetic and of much of algebra; MATH-322 builds groups and rings from exactly this construction.

Partial orders

A relation that is reflexive, antisymmetric and transitive is a partial order. Examples are \(\le\) on \(\mathbb{R}\), \(\subseteq\) on the power set of a set, and divisibility on the positive integers. The word 'partial' is there because two elements need not be comparable: neither \(2 \mid 3\) nor \(3 \mid 2\), and neither \(\{1\} \subseteq \{2\}\) nor \(\{2\} \subseteq \{1\}\). A partial order in which every two elements are comparable, such as \(\le\) on \(\mathbb{R}\), is a total or linear order. Finite partial orders are drawn as Hasse diagrams, with \(b\) placed above \(a\) and joined by an edge when \(a\) precedes \(b\) with nothing in between.

Equivalence relations and partial orders are the two great families of relations. One says when things are interchangeable; the other says when one comes before another. The well-ordering principle of lesson 8 is a statement about the total order \(\le\) on \(\mathbb{N}\), and lesson 12 uses the relation 'has the same cardinality as', which behaves like an equivalence relation on sets.

Computing equivalence classes

For a relation on a finite set the properties can be checked mechanically, and equivalence classes can be computed by grouping. The code below tests the four properties for several relations on \(\{0, 1, \ldots, 11\}\) and, for congruence mod 4, prints the partition into classes. It also counts the partitions of small sets; the counts \(1, 2, 5, 15, 52\) are the Bell numbers, and by the theorem they are also the numbers of equivalence relations.

from itertools import product

A = range(12)

def props(rel):
    R = {(a, b) for a, b in product(A, A) if rel(a, b)}
    refl = all((a, a) in R for a in A)
    symm = all((b, a) in R for a, b in R)
    anti = all(a == b for a, b in R if (b, a) in R)
    trans = all((a, d) in R for a, b in R for c, d in R if b == c)
    return refl, symm, anti, trans

tests = {
    "a = b mod 4": lambda a, b: (a - b) % 4 == 0,
    "a <= b":      lambda a, b: a <= b,
    "a divides b": lambda a, b: a != 0 and b % a == 0,
    "|a - b| <= 1": lambda a, b: abs(a - b) <= 1,
}
print("relation       refl  symm  anti  trans")
for name, rel in tests.items():
    print(f"{name:14s}", "  ".join(f"{str(p):5s}" for p in props(rel)))

classes = {}
for a in A:
    classes.setdefault(a % 4, []).append(a)
print("classes mod 4:", list(classes.values()))

def partitions(items):
    if not items:
        yield []
        return
    first, rest = items[0], items[1:]
    for p in partitions(rest):
        for i in range(len(p)):
            yield p[:i] + [[first] + p[i]] + p[i + 1:]
        yield [[first]] + p

print("number of partitions:", [sum(1 for _ in partitions(list(range(n)))) for n in range(1, 6)])

relation       refl  symm  anti  trans
a = b mod 4    True   True   False  True 
a <= b         True   False  True   True 
a divides b    False  False  True   True 
|a - b| <= 1   True   True   False  False
classes mod 4: [[0, 4, 8], [1, 5, 9], [2, 6, 10], [3, 7, 11]]
number of partitions: [1, 2, 5, 15, 52]

The divisibility line deserves a comment: on \(\{0, \ldots, 11\}\) with the convention used here (0 divides nothing), the relation is not reflexive, because \(0 \mid 0\) fails. On the positive integers alone it is a partial order. The domain matters for relations just as it does for functions.