Part 6 · 1 chapters · ~8 min

Relations and Orders

Relations as sets of pairs, properties (reflexive, symmetric, transitive, antisymmetric), equivalence relations and classes, partial and total orders, Hasse diagrams, lattices, comparators that sort correctly, closures (transitive closure for reachability), and Lamport's happened-before relation.

Relations in code

code

// a correct comparator: a total order on (amount desc, then id asc)
payouts.sort((a, b) => (b.amountKobo - a.amountKobo) || a.id.localeCompare(b.id));
// a broken one: not transitive, so the result is unspecified
payouts.sort(() => Math.random() - 0.5);          // also a biased shuffle: use Fisher-Yates

// equivalence classes: group customers whose normalised emails match
const key = (e: string) => e.trim().toLowerCase();
const classes = Map.groupBy(customers, c => key(c.email));     // ES2024

// transitive closure: everything reachable (who can see this document via nested groups?)
SELECT … WITH RECURSIVE members(g) AS (SELECT $1 UNION SELECT child FROM group_edges JOIN members ON parent = g) SELECT * FROM members;

RELATIONS AND ORDERS

how things relate, and when they can be sorted

swipe the figure sideways, or tap expand for full screen

1/4

equivalence

An equivalence relation groups things into classes: "same currency", "same customer after case-insensitive email match". Deduplication is finding classes.

partitions into classesdeduplication