equivalence-relation

Parent: order-theory

The other great classification of a binary relation ~ (the order family's twin).

Equivalence relation

A relation ~ on a set that is

• reflexive — a ~ a;
• symmetric — a ~ b ⟹ b ~ a;
• transitive — a ~ b and b ~ c ⟹ a ~ c.

What it gives you: classes and quotients

~ partitions the set into disjoint equivalence classes [a] = { x : x ~ a }; the set of classes is the quotient S/~. Conversely every partition is an equivalence relation — the two are the same data.

The clean contrast with order

Symmetry vs antisymmetry is the whole difference:

• a≤b and b≤a ⟹ same class (equivalence) vs ⟹ equal (partial order).
• A preorder splits canonically into an equivalence (its symmetric core a~b ⟺ a≤b≤a) plus a partial order on the quotient. So "preorder = equivalence + order" — the two relation-families are the two halves of a preorder.

Where they show up

Equality, congruence mod n, "same cardinality", isomorphism, Myhill–Nerode indistinguishability (the ≡ whose classes are DFA states), bisimulation (modal logic). Whenever you "quotient out a distinction that doesn't matter," an equivalence relation is doing the work.