Equivalence relations, classes and partitions of a set

Very often, in mathematics as in data work, we want to treat as "equal" things that are not identical: two email addresses that differ only in capitalisation, two fractions such as 1/2 and 2/4, two files with the same content but different names. Equivalence relations are the tool that makes this "equal from a certain point of view" rigorous, and their natural outcome is a partition of the set into groups.

Definition

A relation ~ on a set A is an equivalence relation if it is:

• reflexive: a ~ a for every a;
• symmetric: if a ~ b then b ~ a;
• transitive: if a ~ b and b ~ c then a ~ c.

The three properties capture exactly what we expect from a notion of "sameness": everything is equal to itself, equality has no direction, and it propagates along chains.

Examples

• Same remainder when divided by n: a ~ b if a and b leave the same remainder when divided by n. This is congruence modulo n, the basis of modular arithmetic.
• Same length: on strings, s ~ t if they have the same number of characters.
• Same content: on files, f ~ g if their contents are identical byte for byte.
• Case-insensitive equality: on strings, s ~ t if they match after converting both to lower case.
• Equivalent fractions: a/b ~ c/d if a · d = b · c.

An instructive counterexample: "differ by at most 1", on the integers, is reflexive and symmetric but not transitive (1 ~ 2 and 2 ~ 3, but 1 and 3 differ by 2). The same problem arises with threshold-based "similarity" between strings: small differences accumulated along a chain lead to two very different elements. That is why a similarity relation should not be treated as an equivalence without thinking.

Equivalence classes

Given an equivalence relation, the equivalence class of an element a is the set of all elements equivalent to a:

[a] = {x ∈ A | x ~ a}

With congruence modulo 3 on the integers there are three classes:

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

Any element of a class can serve as its representative: [1] = [4] = [−2]. The set of classes is called the quotient set and written A/~. For congruence modulo n, the quotient is written ℤ/nℤ or ℤₙ, and it has n elements.

The fundamental theorem: equivalences and partitions

A partition of A is a family of non-empty subsets of A, pairwise disjoint, whose union is A. Every element lies in exactly one block.

The central result is that equivalence relations and partitions are the same thing seen from two sides:

1. The classes of an equivalence relation form a partition. Each a lies in its own class [a] by reflexivity; two classes are either identical or disjoint, thanks to symmetry and transitivity.
2. Conversely, every partition defines an equivalence: a ~ b if and only if a and b lie in the same block.

This explains why grouping is such a natural operation. A GROUP BY in SQL partitions rows by the value of one or more columns; implicitly it uses the equivalence relation "they have the same values in those columns".

Computing classes in practice

When the equivalence is given by a key function, such as "convert to lower case" or "compute the hash", the classes are obtained by grouping by key:

from collections import defaultdict

def classes(elements, key):
    groups = defaultdict(list)
    for e in elements:
        groups[key(e)].append(e)
    return list(groups.values())

classes(["Mario@ditta", "mario@ditta", "anna@studio"], str.lower)
# [['Mario@ditta', 'mario@ditta'], ['anna@studio']]

Often, though, you only know some equivalent pairs, and the rest follows by transitivity: "record 1 is the same customer as record 7, and 7 the same as 12". To find the classes in this case you use the union-find (or disjoint-set) structure: each element starts on its own, each known pair merges the two groups, and at the end each group is a class. With path compression and union by rank, the operations take practically constant time. In deduplicating customer records and aggregating indicators collected from different sources, it is one of the tools I reach for most gladly.

In short

• An equivalence relation is reflexive, symmetric and transitive.
• The class [a] collects the elements equivalent to a; the set of classes is the quotient.
• Equivalences and partitions correspond exactly: every equivalence groups, every grouping is an equivalence.
• Threshold-based similarity relations are usually not transitive.
• With a key function, group by key; with scattered pairs, use union-find.