Equivalence and order: classes, partitions, and what you can compare
Reflexive + symmetric + transitive = an equivalence relation, and every equivalence partitions a set into disjoint classes — the math behind hash buckets and dedup. Orders rank instead; partial orders allow incomparable pairs, which is how 1.2 vs 1.10 sorts wrong.
A deploy script picked the “latest” release by sorting the version tags and taking the last one. It had worked for months. Then version 1.10.0 shipped — and the script confidently rolled production back to 1.9.0, because as strings, “1.10.0” sorts before “1.2.3”: string comparison reads character by character, and the character “1” is less than “2”. Nobody had asked the quiet question underneath all sorting: what order are we using, and is it the order we mean? This lesson is about the two most useful species of relation built from last lesson’s properties. Equivalence relations answer “which things count as the same?” — they are why hash buckets work and why deduplicating emails needs lowercasing first. Orders answer “what comes before what?” — and they hide a surprise: some perfectly good orders cannot compare every pair.
After this lesson you can define an equivalence relation from its three properties, explain why every equivalence partitions its set into disjoint classes, write a canonical-representative dedup, define a partial order and distinguish it from a total order, and identify incomparable pairs in a concrete relation.
An equivalence relation has all three properties: reflexive, symmetric, transitive. Together they formalize “counts as the same for my purposes”: everything is the same as itself; if a is the same as b then b is the same as a; if a ~ b and b ~ c then a ~ c. The canonical example is same remainder mod 3 on integers — 7 and 4 both leave remainder 1, so they are equivalent. Other everyday equivalences: same string length, is-an-anagram-of (“listen” ~ “silent”), same email after lowercasing and trimming.
Every equivalence relation partitions its set into disjoint equivalence classes. Each element lands in exactly one class, and two elements are related exactly when they share a class. Remainder mod 3 cuts the integers into three classes: {0, 3, 6, 9, …}, {1, 4, 7, 10, …}, {2, 5, 8, 11, …}. No number is in two classes, none is left out — guaranteed by the three properties. Symmetry + transitivity make classes swallow whole groups; reflexivity ensures nobody escapes.
// "Same person" on emails = same value after normalization.
const canon = (e) => e.trim().toLowerCase();
const emails = ["Ana@Example.com ", "ana@example.com", "BOB@x.dev"];
const classes = new Map();
for (const e of emails) {
const rep = canon(e);
(classes.get(rep) ?? classes.set(rep, []).get(rep)).push(e);
}
classes.size; // 2 — two real people, three spellings
[...classes.keys()]; // ["ana@example.com", "bob@x.dev"]A partial order is reflexive, transitive and antisymmetric — mutual relation forces equality, so arrows rank instead of group. Numbers under ≤ are the familiar case. The word partial is the surprise: a total order compares every pair (pick any two numbers, one is ≤ the other), while a partial order legally leaves some pairs incomparable. Under ⊆, {1, 2} and {2, 3} are not equal and neither contains the other — they are incomparable, and nothing is broken. The order is simply partial.
Sorting by the wrong total order is the version bug. Both lexicographic order and semver order are total orders on version strings, but they disagree: as strings “1.10.0” < “1.2.3” because “1” < “2” character-by-character, while semver compares components numerically. The deploy script sorted by the wrong total order and rolled back production. Sorting always commits to a relation — the bug class is committing to the wrong one.
const tags = ["1.9.0", "1.10.0", "1.2.3"];
tags.sort(); // → ["1.10.0", "1.2.3", "1.9.0"] ← wrong
const byVersion = (a, b) => {
const pa = a.split(".").map(Number);
const pb = b.split(".").map(Number);
return (pa[0] - pb[0]) || (pa[1] - pb[1]) || (pa[2] - pb[2]);
};
tags.sort(byVersion); // → ["1.2.3", "1.9.0", "1.10.0"] ← correctClassify each relation as equivalence, partial order, total order, or none.
- “Same length” on strings — reflexive (“ab” has same length as “ab”), symmetric, transitive (same length chains). Equivalence. Cuts strings into classes by length: 0, 1, 2, …
- ⊆ on sets — reflexive, transitive, antisymmetric (A ⊆ B and B ⊆ A forces A = B). But {1,2} and {2,3} are incomparable → partial order, not total.
- ≤ on integers — reflexive, transitive, antisymmetric, and every pair compares. Total order.
- “Is a prefix of” on strings — reflexive, transitive, but not symmetric (“ab” is a prefix of “abc”, not vice versa). Not an equivalence. Antisymmetric? Prefix-of A implies prefix-of B and vice versa only when they are equal → partial order.
- “Shares at least one character” — symmetric, but not transitive: “ab” shares with “bc”, “bc” shares with “cd”, “ab” and “cd” share nothing. None of the above.
▸Why this works
Why do hash buckets count as equivalence classes? A hash table files x and y into the same bucket when hash(x) === hash(y) — and “same hash” is reflexive, symmetric and transitive, so the buckets partition the universe into classes of a genuine equivalence. The subtlety: this equivalence is coarser than equality — equal values always share a bucket, but collisions let unequal values share one too. That is why a lookup has two stages: hash to find the class, then a true equality check inside the class. The partition does the fast narrowing; equality does the final word.
Name the three properties that make a relation an equivalence relation (one word each, comma-separated).
Remainder mod 3 cuts the integers into how many classes? Type the number.
Are {1,2} and {2,3} comparable under ⊆? Answer yes or no.
Is 'is a prefix of' symmetric? Answer yes or no.
A deploy script sorts version tags with default JS sort(). Which sorts LAST: '1.9.0' or '1.10.0'? Type exactly as written.
Which relation on strings is an equivalence relation?
Keep all three pair-by-pair properties — reflexive, symmetric, transitive — and you have an equivalence relation, the precise form of “counts as the same”: same remainder mod 3, same string length, anagram, same email after normalization. Every equivalence partitions its set into disjoint classes with each element in exactly one; groupBy partitions by key, hash buckets are classes of “same hash”, dedup keeps one canonical representative per class. Swap symmetry for antisymmetry — mutual relation forces equality — and you get orders, which rank instead of group. A total order compares every pair (numbers under ≤); a partial order legally leaves some pairs incomparable: ⊆ on sets, “must run before” on tasks where incomparable means parallelizable, and a cycle violates antisymmetry so badly that no valid execution sequence exists. The version-sort bug distilled the discipline: both lexicographic and semver order are total, but only one matches the meaning, and “1.10.0” losing to “1.9.0” is what sorting by the wrong relation looks like. Before comparing, name your order; before grouping, name your equivalence.
Practice
Start at the top. Tasks go easiest → hardest: recall a fact, apply it to a case, then a senior-level stretch. Open one, attempt it, then reveal.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.