Day 14 — Relations, Equivalence Relations & Partial Orders

Updated

July 30, 2025

Day 14 — Relations, Equivalence Relations & Partial Orders

Day 38 — Relations

Stage IV · concept day
Goal: Define binary relations; represent them as digraphs and matrices; check reflexive, symmetric, transitive, antisymmetric properties; understand reflexive/symmetric/transitive closures (paths for transitive); compose relations.

Why this matters

“Depends on,” “reaches,” “⊆,” “≡ mod \(n\),” “≤,” edges in graphs—all are relations. Properties classify them into equivalence relations (Day 39) and partial orders (Day 40). Transitive closure is “path exists”—the mathematical name for reachability in a digraph.

Theory

Binary relations

A binary relation on a set \(A\) is \(R \subseteq A\times A\).
(More generally from \(A\) to \(B\): \(R\subseteq A\times B\).)
Write \(a\,R\,b\) or \((a,b)\in R\).

Representations

Digraph: vertices \(A\); directed edge \(a\to b\) iff \(a\,R\,b\). Loops mean \(a\,R\,a\).

Boolean matrix: order \(A=\{a_1,\ldots,a_n\}\); \(M_{ij}=1\) iff \(a_i\,R\,a_j\).

Core properties (on \(A\))

Property Definition
Reflexive \(\forall a\in A,\; a\,R\,a\)
Symmetric \(\forall a,b,\; a\,R\,b \Rightarrow b\,R\,a\)
Antisymmetric \(\forall a,b,\; (a\,R\,b \wedge b\,R\,a) \Rightarrow a=b\)
Transitive \(\forall a,b,c,\; (a\,R\,b \wedge b\,R\,c) \Rightarrow a\,R\,c\)
Irreflexive \(\forall a,\; \neg(a\,R\,a)\)
Asymmetric \(a\,R\,b \Rightarrow \neg(b\,R\,a)\) (implies irreflexive)

Note: Antisymmetric is not “not symmetric.” Equality is both symmetric and antisymmetric. \(<\) is antisymmetric? If \(a<b\) and \(b<a\) then false, so implication to \(a=b\) holds vacuously—actually strict orders are asymmetric. \(\le\) is antisymmetric and reflexive.

Closures (idea)

Given \(R\), the \(P\)-closure is the smallest relation containing \(R\) with property \(P\) (when it exists).

  • Reflexive closure: \(R \cup \Delta_A\) where \(\Delta_A=\{(a,a):a\in A\}\).
  • Symmetric closure: \(R \cup R^{-1}\) where \(R^{-1}=\{(b,a):(a,b)\in R\}\).
  • Transitive closure: \(R^+\) (or \(R^*\) reflexive-transitive) — edges for paths of positive length;
    \[R^+ = \bigcup_{k\ge 1} R^k,\]
    where \(R^1=R\), \(R^{k+1}=R^k \circ R\) (composition).
    On finite digraphs: \((a,b)\) in transitive closure iff path from \(a\) to \(b\).

Composition of relations

For \(R\subseteq A\times B\), \(S\subseteq B\times C\),
\[S \circ R = \{ (a,c) : \exists b\in B\, (a\,R\,b \wedge b\,S\,c) \}.\]
(Order conventions vary: some write \(R\circ S\) for apply \(R\) first—fix left/right. We use “\(S\circ R\) means \(R\) first then \(S\)” like functions.)

Composition is associative; identity relation \(\Delta_A\) acts as unit for relations on \(A\).

Matrix view of composition

Boolean matrix product: \((MS)_{ik} = \bigvee_j (M_{ij} \wedge S_{jk})\). Transitive closure via repeated product / Warshall awareness.

Examples of relations

  • \(=\) on any \(A\): reflexive, symmetric, transitive (equivalence).
  • \(\le\) on \(\mathbb{R}\): reflexive, antisymmetric, transitive (partial/total order).
  • \(<\) on \(\mathbb{R}\): irreflexive, transitive, asymmetric.
  • “divides” on \(\mathbb{Z}^+\): partial order.
  • “is a parent of”: neither symmetric nor transitive typically.
  • empty relation: transitive, symmetric; reflexive only if \(A=\emptyset\).
  • full relation \(A\times A\): reflexive, symmetric, transitive.

Checking properties algorithmically (finite)

  • Reflexive: all diagonal matrix entries \(1\).
  • Symmetric: matrix equals its transpose.
  • Transitive: harder—check \(M\vee (M*M) = M\) boolean, or use closure and compare.

Worked examples

Example 1 — List pairs

\(A=\{1,2,3\}\), \(R=\{(1,1),(1,2),(2,2),(3,3)\}\).
Reflexive? Missing \((2?\) has \(2,2)\), has all diagonal—yes if only those… has \(1,1;2,2;3,3\) yes. Symmetric? \((1,2)\) without \((2,1)\)—no. Transitive? \((1,2)\) and … no further.

Example 2 — Divisibility

On \(\{1,2,3,4,6\}\), \(a\mid b\). Reflexive yes; transitive yes; antisymmetric yes (on positives).

Example 3 — Mod \(n\)

\(a \equiv b \pmod{n}\): equivalence (Day 39).

Example 4 — Symmetric closure

\(R=\{(1,2)\}\) on \(\{1,2\}\): add \((2,1)\).

Example 5 — Reflexive closure

Same \(R\): add \((1,1),(2,2)\).

Example 6 — Transitive closure / path

\(R=\{(a,b),(b,c)\}\): closure adds \((a,c)\).

Example 7 — Composition

\(R=\{(1,2)\}\), \(S=\{(2,3)\}\): \(S\circ R = \{(1,3)\}\).

Example 8 — Not transitive

“friend” on social graph often not transitive; transitive closure is “connected in friendship undirected” if symmetrized.

Example 9 — Matrix

\(A=\{1,2\}\), \(R=\{(1,1),(1,2)\}\): \(M = \begin{pmatrix}1&1\\0&0\end{pmatrix}\).

Example 10 — Antisymmetric vs asymmetric

\(\le\) antisymmetric not asymmetric (\(a\le a\)). \(<\) asymmetric.

Example 11 — Reachability

Web links: transitive closure ≈ can reach by following links.

Example 12 — \(R\circ R\)

\((a,c)\in R^2\) iff some mid \(b\) with two-step path.

Example 13 — Equality as \(\Delta\)

Smallest reflexive relation on \(A\).

Example 14 — Failure of symmetry + antisymmetry

If both, then \(a\,R\,b\) implies \(a=b\): relation \(\subseteq \Delta_A\).

Exercises

  1. For \(A=\{1,2,3\}\) list a relation that is reflexive only among the four properties—or state which hold for \(R=\Delta_A\).
  2. Check properties of \(<\) on \(\mathbb{Z}\).
  3. Check properties of \(\mid\) on \(\mathbb{Z}^+\).
  4. Give a relation that is symmetric but not transitive.
  5. Give transitive but not symmetric.
  6. Compute symmetric and reflexive closures of \(\{(1,2),(2,3)\}\) on \(\{1,2,3\}\).
  7. Compute transitive closure of that same \(R\).
  8. Compose \(R=\{(a,b),(b,b)\}\), \(S=\{(b,c)\}\) on \(\{a,b,c\}\).
  9. Prove composition is associative (element chase with witnesses).
  10. Prove \(R\) transitive iff \(R\circ R \subseteq R\).
  11. Prove \(R\) reflexive iff \(\Delta_A \subseteq R\).
  12. Matrix for “\(\le\)” on \(\{1,2,3\}\).
  13. Is the empty relation on \(\{1,2\}\) transitive? Reflexive?
  14. Prove: if \(R\) and \(S\) symmetric, \(R\cap S\) symmetric. What about \(R\cup S\)? \(R\circ S\)?
  15. Find \(R\) with \(R\circ R = R\) (transitive and … idempotent under composition).
  16. Digraph: draw transitive closure of a 4-edge example.
  17. CS: model “package depends on” — which properties expected?
  18. Antisymmetric: show \(\subseteq\) on \(\mathcal{P}(X)\) is antisymmetric.
  19. Can a relation be both symmetric and asymmetric? Only empty on nonempty? Discuss.
  20. Warshall awareness: one sentence what it computes.
  21. Prove \(R^+\) is transitive.
  22. Number of binary relations on a set of \(n\) elements: \(2^{n^2}\).
  23. Number of reflexive relations on \(n\) elements.
  24. If \(M\) is adjacency matrix, what does \(M^2\) count over integers vs boolean?
  25. Give relation for “shares a class with” and discuss transitivity.

CS connection

  • DAGs / dependency graphs: transitive closure = all transitive deps.
  • RBAC: user–role–permission as composition of relations.
  • SQL joins implement composition-like patterns.
  • Union-find maintains equivalence closure (Day 39).
  • Type subtyping as preorder (reflexive transitive).
  • Adjacency matrices and reachability algorithms.

Common pitfalls

Pitfall What to do instead
Antisymmetric = not symmetric Different definitions
Forgetting loops for reflexive Check diagonal
Transitive closure = one step All path lengths
Composition order confusion Fix a convention and stick to it
Assuming friend-of-friend is friend Not without closure
Infinite \(A\) and “smallest” closure Still defined as intersection of all super-relations with \(P\)

Checkpoint

  • Define relation; digraph; matrix
  • Test four main properties on examples
  • Form reflexive/symmetric/transitive closures
  • Compose two small relations
  • State \(R\) transitive iff \(R\circ R\subseteq R\)
  • Exercises done or logged

Two takeaways:

  1. …
  2. …

Deep dive — closures as operators

Let \(\mathrm{Ref}, \mathrm{Sym}, \mathrm{Trans}\) denote closure operators on relations on a fixed finite \(A\). Then:

  • \(\mathrm{Ref}(R)=R\cup\Delta\)
  • \(\mathrm{Sym}(R)=R\cup R^{-1}\)
  • \(\mathrm{Trans}(R)=R^+\) path relation

Order of applying closures matters for intermediate results; the equivalence closure is the smallest equivalence containing \(R\) (reflexive-symmetric-transitive closure), computed e.g. by undirected connectivity if you first symmetrize.

Warshall / Floyd awareness

Warshall’s algorithm computes transitive closure in \(O(n^3)\) boolean operations on an \(n\)-vertex digraph—dynamic programming over intermediate vertices. Same skeleton as Floyd–Warshall for shortest paths with different “semiring.”

Preorders

Reflexive + transitive (not necessarily antisymmetric) = preorder.
Example: reachability with loops; “\(a\) maps to \(b\) under rewriting.”
Antisymmetrizing a preorder yields a partial order on equivalence classes.

More worked examples

Example 15 — Divisibility matrix
On \(\{1,2,3,4\}\), write \(0/1\) matrix for \(\mid\).

Example 16 — Composition count
\((a,c)\in R\circ R\) iff path length 2.

Example 17 — Smallest transitive containing a cycle
\(R=\{(1,2),(2,3),(3,1)\}\) ⇒ \(R^+\) is full \(A\times A\) on \(\{1,2,3\}\).

Example 18 — Antisymmetric failure
\(R=\{(1,2),(2,1)\}\) not antisymmetric on \(\{1,2\}\).

Additional exercises

  1. Prove \(R\) symmetric iff \(R=R^{-1}\).
  2. Compute equivalence closure of \(\{(1,2),(2,3)\}\) on \(\{1,2,3,4\}\).
  3. Show intersection of transitive relations is transitive; union need not be.
  4. Number of reflexive symmetric relations on \(n\) elements (undirected graphs with loops forced).
  5. CS: model “imports” relation; what does transitive closure mean for build systems?

Extended practice workshop

Property checklist on standard relations

For each, mark R/S/T/A (antisym):

  1. \(=\) on any \(A\).
  2. \(\neq\) on a set with \(\ge 2\) elements.
  3. \(\le\) on \(\mathbb{R}\).
  4. \(<\) on \(\mathbb{R}\).
  5. \(\mid\) on \(\mathbb{Z}^+\).
  6. “is parent of” on people (assume no cycles).
  7. Empty relation on \(\{1,2,3\}\).
  8. Full relation \(A\times A\).

Closure computations

  1. \(R=\{(1,2),(2,1),(2,3)\}\) on \(\{1,2,3\}\): Ref, Sym, Trans closures (separately).
  2. Equivalence closure of \(R\) (combine).
  3. Path interpretation of Trans\((R)\).

Composition

  1. \(R=\{(a,b),(b,c),(c,c)\}\), compute \(R\circ R\) and \(R\circ R\circ R\).
  2. Prove \(R\) transitive iff \(R\circ R\subseteq R\) (both directions).
  3. Identity \(\Delta\) satisfies \(R\circ\Delta=R=\Delta\circ R\).

Matrix

  1. Write boolean matrix for \(\le\) on \(\{1,2,3\}\).
  2. Boolean square of that matrix—interpret.

CS scenarios

  1. Package depends-on: expected properties?
  2. Git “parent commit”: transitive closure = ancestor.
  3. RBAC user→role→permission as composition.
  4. Reachability in a call graph.

Property decision tree

Need ignore differences? → aim for equivalence (add SYM)
Need ranking/dependency? → aim for partial order (add ANTI, keep REF+TRANS)
Need reachability? → take TRANS closure of edge relation

Quick theorems to recite

  1. \(R\) reflexive iff \(\Delta\subseteq R\).
  2. \(R\) symmetric iff \(R=R^{-1}\).
  3. \(R\) transitive iff \(R\circ R\subseteq R\).
  4. Transitive closure ↔︎ paths of length \(\ge 1\).
  5. Composition is associative; \(\Delta\) is unit.
  6. Number of relations on \(n\) elements: \(2^{n^2}\).

Checkpoint recap (relations day)

  • Test four properties on a 4-pair relation
  • Form Ref/Sym/Trans closures
  • Compose two relations
  • Draw a digraph and its transitive closure
  • Matrix for a small relation

Synthesis

A binary relation is “just” a set of pairs, but the named properties (REF, SYM, TRANS, ANTI) carve out the structures CS uses constantly: equivalence (clustering), partial order (dependencies), and reachability (transitive closure of edges). Composition is relational join; closures are the “least structure containing \(R\).”

Property checklist (run every example)

Property Test Closure idea
Reflexive \(\Delta\subseteq R\) Add all \((a,a)\)
Symmetric \((a,b)\in R\Rightarrow(b,a)\in R\) Add reverse edges
Transitive paths of length \(2\) imply edge Add all path pairs
Antisymmetric \((a,b)\) and \((b,a)\) ⇒ \(a=b\) Not a “closure” target usually

More worked examples

Example — Composition as path length 2.
If \(R\) is edges, \((a,c)\in R\circ R\) iff \(\exists b\,(aRb\wedge bRc)\). Transitivity says \(R\circ R\subseteq R\).

Example — Reflexive-transitive closure.
Reachability with self: \(R^*=\bigcup_{n\ge 0} R^n\) with \(R^0=\Delta\). In graphs: paths of any length including \(0\).

Example — “Depends on” for packages.
Typically not symmetric; should be acyclic for install order; transitive closure = full dependency set. Antisymmetry fails if mutual depends (cycle of equals)—real systems forbid or collapse.

Example — Matrix boolean square.
If \(M\) is the adjacency matrix (boolean), \(M\vee M^2\vee\cdots\) builds reachability (Warshall/Floyd–Warshall family). Hand-compute \(2\times 2\) or \(3\times 3\) examples.

Example — Counting.
On an \(n\)-element set there are \(2^{n^2}\) relations; \(2^{n(n-1)/2}\) undirected simple graphs if you force SYM and irreflexive—different counting conventions.

Extra exercises (synthesis)

  1. For \(R=\{(1,2),(2,3)\}\) on \(\{1,2,3\}\), compute Ref, Sym, Trans closures separately and the equivalence closure.
  2. Prove: \(R\) symmetric iff \(R=R^{-1}\).
  3. Prove: \(R\) transitive iff \(R\circ R\subseteq R\).
  4. Show composition is associative: \((T\circ S)\circ R = T\circ(S\circ R)\).
  5. RBAC: users \(U\), roles \(S\), permissions \(P\); relations \(R_1\subseteq U\times S\), \(R_2\subseteq S\times P\); interpret \(R_2\circ R_1\).
  6. Draw digraph of \(<\) on \(\{1,2,3,4\}\) and mark transitive edges not in the Hasse (cover) relation.

Map forward

  • Equivalence = REF + SYM + TRANS → partitions (Day 39).
  • Partial order = REF + ANTI + TRANS → Hasse, topo sort (Day 40).
  • Functions = special relations: left-total and right-unique (Days 41–42).

Property tests are boolean; closures are constructive. Always compute on a \(3\)–\(4\) element set before claiming intuition.

Tomorrow

Day 39 — Equivalence relations. Partitions ↔︎ equivalences; classes; \(\mathbb{Z}/n\mathbb{Z}\); well-defined operations awareness; refining partitions.

Day 39 — Equivalence relations

Stage IV · concept day
Goal: Connect equivalence relations to partitions; compute equivalence classes; work with \(\mathbb{Z}/n\mathbb{Z}\); know well-definedness of operations on classes at awareness level; refine partitions.

Why this matters

“Same hash bucket,” “same connected component,” “equal modulo \(n\),” “same type after erasure”—all identify elements that are interchangeable for a purpose. Equivalence relations are the math of ignoring irrelevant differences. Quotient sets \(\mathbb{Z}/n\mathbb{Z}\) undergird modular arithmetic in crypto and hashing.

Theory

Equivalence relation

A relation \(\sim\) on \(A\) is an equivalence relation when it is reflexive, symmetric, and transitive.

Equivalence class

For \(a\in A\),
\[[a] = \{ x\in A : x \sim a \}.\]
Any \(c\in [a]\) is a representative.
\(a\sim b \Leftrightarrow [a]=[b]\).
\(a\nsim b \Leftrightarrow [a]\cap[b]=\emptyset\).

Partition

A partition of \(A\) is a family \(\mathcal{F}\) of nonempty subsets of \(A\) such that:

  1. \(\bigcup_{B\in\mathcal{F}} B = A\),
  2. if \(B,C\in\mathcal{F}\) and \(B\neq C\) then \(B\cap C=\emptyset\).

Blocks of the partition are pairwise disjoint and cover \(A\).

Fundamental theorem (correspondence)

  1. If \(\sim\) is an equivalence on \(A\), the distinct classes \(\{[a]: a\in A\}\) form a partition of \(A\).
  2. If \(\mathcal{F}\) partitions \(A\), define \(a\sim b\) iff \(a\) and \(b\) lie in the same block; then \(\sim\) is an equivalence whose classes are exactly the blocks.

Proof sketch. (1) Reflexivity ⇒ \(a\in[a]\), so cover; if classes intersect, shared element forces equal classes by symmetry+transitivity. (2) Same-block is easily REF/SYM/TRANS. \(\square\)

Quotient set

\[A/\sim \;=\; \{ [a] : a\in A \}\]
the set of equivalence classes.

Modular arithmetic \(\mathbb{Z}/n\mathbb{Z}\)

On \(\mathbb{Z}\), \(a \equiv b \pmod{n}\) iff \(n\mid (a-b)\).
This is an equivalence. Classes: \([0],[1],\ldots,[n-1]\) (for \(n>0\)).
\(\mathbb{Z}/n\mathbb{Z} = \{[0],\ldots,[n-1]\}\).

Well-defined operations (awareness)

Define \([a]+[b]=[a+b]\), \([a]\cdot[b]=[ab]\).
Well-defined means: if \([a]=[a']\) and \([b]=[b']\), then \([a+b]=[a'+b']\).
True for \(\equiv\pmod{n}\)—must be checked once.
Ill-defined example: on \(\mathbb{Q}\) as pairs \((p,q)\) with \(q\neq 0\), addition via wrong formula on unreduced fractions without care—classic need for well-definedness.

Kernel of a function

For \(f: A\to B\), define \(a \sim b\) iff \(f(a)=f(b)\). Equivalence; classes are fibers \(f^{-1}(\{y\})\).
Partitions induced by “same output.”

Refining partitions

Partition \(\mathcal{F}\) refines \(\mathcal{G}\) if every block of \(\mathcal{F}\) is contained in some block of \(\mathcal{G}\) (finer equivalence = more classes, smaller blocks).
Equality is finest with all singletons; coarsest is one block \(A\).

Counting (finite)

Stirling numbers of the second kind \(S(n,k)\) count partitions of an \(n\)-set into \(k\) nonempty unlabeled blocks; Bell number \(B_n=\sum_k S(n,k)\) total partitions—awareness for later combinatorics.

Worked examples

Example 1 — Mod 3 classes

\([0]=\{\ldots,-3,0,3,6,\ldots\}\), \([1]\), \([2]\).

Example 2 — Same absolute value

On \(\mathbb{R}\), \(x\sim y\) iff \(|x|=|y|\): classes \(\{0\}\), and \(\{a,-a\}\) for \(a>0\).

Example 3 — Not equivalence

\(\le\) on \(\mathbb{Z}\): not symmetric.

Example 4 — Partition to relation

Blocks \(\{1,2\},\{3\}\) on \(\{1,2,3\}\): \(1\sim 2\), \(3\sim 3\), etc.

Example 5 — Strings same length

Equivalence on \(\Sigma^*\); classes by length \(n\).

Example 6 — Well-defined +

If \(a\equiv a'\pmod n\), \(b\equiv b'\), then \(a+b\equiv a'+b'\).

Example 7 — Kernel

\(f:\mathbb{Z}\to\mathbb{Z}/2\mathbb{Z}\), \(f(n)=[n]\). Kernel relation is \(\equiv\pmod 2\).

Example 8 — Connected components

On vertices, \(u\sim v\) iff path in undirected graph: equivalence; classes = components.

Example 9 — Refinement

Mod \(6\) classes refine? Compare mod \(2\): mod \(6\) is finer than mod \(2\) (\([0]_6\) and \([2]_6\) and \([4]_6\) all even).

Example 10 — Singletons

\(=\) is equivalence; \(A/= \cong A\).

Example 11 — Full relation

One class \(A\) if \(|A|\ge 1\) and \(R=A\times A\).

Example 12 — Rational equality

\((p,q)\sim(r,s)\) iff \(ps=qr\) on \(\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})\): constructs \(\mathbb{Q}\).

Example 13 — Hash buckets

\(x\sim y\) if \(\mathrm{hash}(x)=\mathrm{hash}(y)\): equivalence (coarse); collisions = same class.

Example 14 — Prove classes equal or disjoint

If \(z\in[a]\cap[b]\), then \(a\sim z\sim b\) so \(a\sim b\) and \([a]=[b]\).

Exercises

  1. Prove \(\equiv\pmod{n}\) is an equivalence.
  2. List all classes of \(\equiv\pmod{4}\) with representatives \(0,1,2,3\).
  3. Verify the three properties for “same length” on strings.
  4. Why is \(<\) not an equivalence?
  5. Partition \(\{1,2,3,4\}\) into even/odd—write the relation as a set of pairs.
  6. Prove: \(a\sim b \Leftrightarrow [a]=[b]\) for an equivalence \(\sim\).
  7. Prove distinct classes are disjoint.
  8. Show \(+\) on \(\mathbb{Z}/n\mathbb{Z}\) is well-defined.
  9. Show a bad definition is ill-defined: \([a]*[b]=[a]\) “projection product”—is it well-defined? (Yes actually.) Try \([a]\star[b]=[\max(a,b)]\) on \(\mathbb{Z}/n\)—ill-defined?
  10. Kernel of \(f(x)=x^2\) on \(\mathbb{R}\): describe classes.
  11. How many equivalence relations on a \(2\)-element set? On a \(3\)-element set?
  12. Connected components: prove path-equivalence is transitive.
  13. Does refinement of partitions correspond to implication of relations (\(a\sim_F b \Rightarrow a\sim_G b\))? Explain.
  14. Construct \(\mathbb{Z}/2\mathbb{Z}\) addition table.
  15. True/false: every partition comes from exactly one equivalence.
  16. Strings: \(u\sim v\) if \(u\) is anagram of \(v\)—equivalence?
  17. CS: session IDs mapping to users—what are classes?
  18. Prove reflexivity of kernel relation of any \(f\).
  19. Give two different equivalences on \(\{1,2,3,4\}\), one refining the other.
  20. Explain well-definedness failure: define \(f:\mathbb{Q}\to\mathbb{Z}\) by \(f(p/q)=p\)—why ill-defined?
  21. Bell number \(B_3=5\)—list all partitions of \(\{1,2,3\}\).
  22. Equivalence vs partial order: can a relation be both (nontrivial)?
  23. On \(\mathbb{Z}\), \(a\sim b\) iff \(a-b\) even: same as mod \(2\).
  24. Prove \([a]=[b]\) or \([a]\cap[b]=\emptyset\) fully.
  25. Modular: solve \([x]+[3]=[1]\) in \(\mathbb{Z}/5\mathbb{Z}\).

CS connection

  • Hash tables: keys with same hash (ignore perfect hashing).
  • Union-find: maintains the finest equivalence forced by union ops.
  • α-equivalence of bound variables in compilers.
  • bisimulation / observational equivalence (awareness).
  • Modular arithmetic in PRNG, crypto, checksums.
  • Graph components as classes.

Common pitfalls

Pitfall What to do instead
Forgetting symmetry or transitivity Check all three
Picking non-unique class representation casually Mind well-definedness
Thinking partitions can overlap They cannot
Confusing \(\mathbb{Z}/n\mathbb{Z}\) elements with integers Elements are sets of ints
Ill-defined “functions on classes” Check independence of representatives
\(\le\) as equivalence Not symmetric

Checkpoint

  • Define equivalence; class; partition
  • State and use the correspondence theorem
  • Work \(\mathbb{Z}/n\mathbb{Z}\) classes
  • Explain well-definedness with one example
  • Kernel of \(f\) as equivalence
  • Refinement intuition
  • Exercises done or logged

Two takeaways:

  1. …
  2. …

Deep dive — quotient constructions everywhere

Domain Equivalence Quotient meaning
\(\mathbb{Z}\) \(\equiv\pmod n\) clock arithmetic
fractions \(ps=qr\) rational number
vectors differ by nullspace solution space cosets
strings same histogram anagram class
graph verts path-connected component
programs observational eq semantics quotient

Well-definedness proof pattern

To define \(F: A/\sim \to B\) by \(F([a])=\varphi(a)\):

  1. Assume \([a]=[a']\), i.e. \(a\sim a'\).
  2. Show \(\varphi(a)=\varphi(a')\).
  3. Conclude \(F\) does not depend on representative.

If step 2 fails, the definition is illegal.

Lattice of equivalences

Equivalence relations on \(A\) ordered by inclusion (\(R\subseteq S\) means \(R\) finer) form a lattice; meet is intersection; join is the equivalence closure of the union. Awareness for union-find “merging.”

More worked examples

Example 15 — Mod 5 mult table
Compute \([3]\cdot[4]=[12]=[2]\) in \(\mathbb{Z}/5\mathbb{Z}\).

Example 16 — Kernel of abs
\(f:\mathbb{R}\to[0,\infty)\), \(f(x)=|x|\): classes \(\{0\}\) and \(\pm a\).

Example 17 — Not transitive
“differs by at most 1” on \(\mathbb{Z}\): not equivalence.

Example 18 — Partition refinement
\(\{\{1,2\},\{3,4\}\}\) refined by \(\{\{1\},\{2\},\{3,4\}\}\).

Additional exercises

  1. Prove carefully that \(\equiv\pmod n\) is transitive.
  2. Show \(f([a])=2a \bmod n\) on \(\mathbb{Z}/n\) is well-defined.
  3. Is \(g([a])=a\) as integer well-defined on \(\mathbb{Z}/n\)?
  4. List all equivalence relations on a 3-element set (5 Bell).
  5. Prove: if \(f:A\to B\) surjective, then \(A/\ker f \cong B\) (bijection of classes to \(B\)).

Extended practice workshop

Modular arithmetic drills

  1. List \([0],\ldots,[6]\) in \(\mathbb{Z}/7\mathbb{Z}\) with three members each.
  2. Compute \([6]+[5]\) and \([6]\cdot[5]\) in \(\mathbb{Z}/7\mathbb{Z}\).
  3. Find additive inverse of \([3]\) in \(\mathbb{Z}/10\mathbb{Z}\).
  4. Does \([2]\) have a multiplicative inverse in \(\mathbb{Z}/10\mathbb{Z}\)? In \(\mathbb{Z}/7\mathbb{Z}\)?

Kernel drills

  1. \(f(n)=n^2 \bmod 5\) on \(\mathbb{Z}\)—describe fibers.
  2. \(f:\{a,b,c,d\}\to\{0,1\}\) with \(f(a)=f(b)=0\), \(f(c)=f(d)=1\)—write \(\sim\) as pairs.
  3. Prove kernel relation always equivalence.

Partition drills

  1. All partitions of \(\{1,2,3,4\}\) into exactly \(2\) blocks (list).
  2. For each, write the corresponding equivalence as a set of pairs (one example fully).
  3. Which partitions refine \(\{\{1,2\},\{3,4\}\}\)?

Well-definedness drills

  1. \(F([a])=a^2 \bmod n\) on \(\mathbb{Z}/n\)—well-defined? Prove.
  2. \(G([a])=\) leading digit of \(a\)—well-defined on \(\mathbb{Z}/n\)?
  3. Rational \(p/q\mapsto p+q\)—ill-defined; show two reps.

Proof writing

  1. Full proof: classes equal or disjoint.
  2. Full proof: same-block relation is transitive.
  3. \(\exists!\) rewritten without \(!\), applied to “unique residue of \(n\) mod \(m\) in \(\{0,\ldots,m-1\}\).”

Map of Stage IV so far

Sets → ops → products → relations → equivalences → orders → functions.
Equivalences classify; orders rank; functions map.

Quick theorems to recite

  1. Equivalence ⇔ partition (classes are blocks).
  2. \([a]=[b]\) iff \(a\sim b\); else classes disjoint.
  3. \(a\equiv b\pmod n\) iff \(n\mid(a-b)\); \(n\) classes.
  4. Kernel of any \(f\) is an equivalence.
  5. Ops on classes need well-definedness check.
  6. Finer partition = smaller blocks = more classes.

Checkpoint recap (equivalence day)

  • Prove \(\equiv\pmod n\) is an equivalence
  • Compute a class explicitly
  • Convert a partition to a relation
  • Spot an ill-defined “function on classes”
  • Give a kernel example from CS (hash, component, …)

Synthesis

Equivalence relations are principled ways to ignore differences: same residue mod \(n\), same hash bucket, same connected component, same string under case-folding. The fundamental theorem of this day is the bijection between equivalences and partitions—classes are the blocks. Well-definedness is the tax you pay for operating on classes instead of representatives.

Core dictionary

Language Meaning
\(a\sim b\) related
\([a]\) class of \(a\)
\(a\sim b \Leftrightarrow [a]=[b]\) classes equal iff related
Partition blocks pairwise disjoint, cover \(A\)
Kernel of \(f\) \(a\sim b \Leftrightarrow f(a)=f(b)\)

More worked examples

Example — \(\equiv\pmod n\) classes.
For \(n=5\), classes \([0],[1],[2],[3],[4]\) partition \(\mathbb{Z}\). \([7]=[2]\) because \(5\mid(7-2)\).

Example — Kernel of a projection.
\(f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}\), \(f(x,y)=x\). Then \((x,y)\sim(x',y')\) iff \(x=x'\). Classes are vertical lines \(\{x_0\}\times\mathbb{Z}\).

Example — Ill-defined “function.”
Try \(F:\mathbb{Z}/6\mathbb{Z}\to\mathbb{Z}/6\mathbb{Z}\), \(F([a])=[2a+1]\) is well-defined (check). Try \(G([a])=\) “smallest positive representative’s number of divisors”—depends only on representative in \(1..6\), OK; but \(H([a])=a\) as an integer is not a function on classes (many \(a\) per class).

Example — Refinement.
Partition \(\pi_1=\{\{1,2\},\{3,4\}\}\) refined by \(\pi_2=\{\{1\},\{2\},\{3,4\}\}\): every \(\pi_2\)-block sits inside a \(\pi_1\)-block. Finer = more classes = smaller blocks (typically).

Example — Classes equal or disjoint.
If \([a]\cap[b]\neq\emptyset\), take \(c\) in both; then \(a\sim c\sim b\) so \(a\sim b\) and \([a]=[b]\). Critical lemma for partitions.

Extra exercises (synthesis)

  1. Prove fully that \(\equiv\pmod n\) is REF, SYM, TRANS.
  2. List all equivalence relations on \(\{1,2,3\}\) (equivalently: all partitions).
  3. Kernel of \(f(n)=n \bmod 2\) on \(\mathbb{Z}\)—describe classes.
  4. Show addition on \(\mathbb{Z}/n\mathbb{Z}\) is well-defined: if \(a\equiv a'\), \(b\equiv b'\) then \(a+b\equiv a'+b'\).
  5. Is multiplication well-defined mod \(n\)? Prove.
  6. CS: session IDs that collide under a hash—interpret as nontrivial kernel; what breaks if you treat hash as unique ID?

Well-definedness protocol

To define \(F([a])=\textit{expr}(a)\) on \(A/{\sim}\):
assume \(a\sim a'\), prove \(\textit{expr}(a)=\textit{expr}(a')\) (in the codomain).
If proof fails, the “function” is illegal—even if each representative computes something.

Equivalences classify; orders rank (next). Keep both toolboxes separate.

Tomorrow

Day 40 — Partial orders. Posets; Hasse diagrams; comparable elements; chains/antichains; topological order; lattices lite; product order.

Day 40 — Partial orders

Stage IV · concept day
Goal: Define partial orders and posets; draw Hasse diagrams; use comparable vs incomparable; work with chains and antichains; connect to topological order; meet/join lattices lite; product orders.

Why this matters

Dependencies among tasks, package versions, subset inclusion, and integer divisibility are orders that need not compare every pair. Topological sort linearizes a partial order—the algorithm side of DAGs. Lattices appear in type systems and program analysis (awareness).

Theory

Partial order

A relation \(\le\) on \(A\) is a partial order when it is reflexive, antisymmetric, and transitive.
The pair \((A,\le)\) is a poset (partially ordered set).

Strict order \(<\) often defined by \(a < b \Leftrightarrow a\le b \wedge a\neq b\) (irreflexive, transitive).

Total (linear) order

A partial order is total if every pair is comparable: \(\forall a,b,\; a\le b \lor b\le a\).
\((\mathbb{Z},\le)\) total; \((\mathcal{P}(X),\subseteq)\) not total if \(|X|\ge 2\).

Comparability

\(a\) and \(b\) are comparable if \(a\le b\) or \(b\le a\); otherwise incomparable (\(a \parallel b\)).

Hasse diagrams

For finite posets: draw \(a\) below \(b\) with an edge if \(a < b\) and no \(c\) with \(a < c < b\) (cover relation). Omit transitive edges and loops. Read upward as increasing.

Chains and antichains

  • Chain: subset where every two elements are comparable (totally ordered subset).
  • Antichain: subset where no two distinct elements are comparable.

Height ≈ size of largest chain (conventions vary by inclusive).
Width ≈ size of largest antichain (Dilworth’s theorem awareness: width = min number of chains in a chain partition).

Extrema

  • Maximal: no strictly larger element.
  • Maximum: \(\ge\) all elements (unique if exists).
  • Minimal / minimum dual.

Finite nonempty posets have maximal elements; not always a unique maximum.

Topological order

A topological order of a finite poset is a total order \(\preceq\) that extends \(\le\): \(a\le b \Rightarrow a\preceq b\).
Exists iff the strict order is acyclic (always for partial orders).
For a DAG of tasks: edge \(a\to b\) means \(a\) before \(b\); topo sort lists a linear schedule.

Lattices (lite)

A poset is a lattice if every two elements \(a,b\) have a meet \(a\wedge b = \mathrm{glb}\{a,b\}\) and join \(a\vee b = \mathrm{lub}\{a,b\}\).
Bounded lattice has top \(1\) and bottom \(0\).
Examples: \((\mathcal{P}(X),\subseteq)\) with \(\cap,\cup\); \((\mathbb{N},\mid)\) with \(\gcd,\mathrm{lcm}\) (on positives).
Not all posets are lattices (missing joins).

Product order

On \(A\times B\), set \((a,b) \le (a',b')\) iff \(a\le a'\) and \(b\le b'\).
Componentwise. Used for multi-criteria comparison (Pareto: incomparable tradeoffs).

Dual poset

Reverse the order: \(a \le^{\mathrm{op}} b \Leftrightarrow b\le a\).

Worked examples

Example 1 — Divisibility poset

\((\{1,2,3,4,6,12\},\mid)\). Hasse: \(1\) at bottom; \(12\) at top; \(2,3\) above \(1\); etc.

Example 2 — Power set

\(\mathcal{P}(\{1,2\})\) Boolean lattice: \(\emptyset\) bottom, full set top, two middle incomparable singletons.

Example 3 — Incomparable

\(\{1\}\) and \(\{2\}\) under \(\subseteq\).

Example 4 — Chain

\(\emptyset \subset \{1\} \subset \{1,2\}\) chain of size \(3\).

Example 5 — Antichain

All singletons in \(\mathcal{P}([n])\) form an antichain (Sperner capacity awareness).

Example 6 — Maximal vs maximum

In \(\{2,3,4\}\) under divisibility: \(4\) and \(3\) maximal; no maximum.

Example 7 — Topological order

Tasks \(A\le C\), \(B\le C\) (must finish \(A,B\) before \(C\)): orders \(A,B,C\) or \(B,A,C\).

Example 8 — Product order

\((1,3)\) and \((2,2)\) incomparable in \(\mathbb{R}^2\) with product order if using usual \(\le\).

Example 9 — Meet join

In \(\mathcal{P}(X)\), meet \(= \cap\), join \(=\cup\).

Example 10 — Not lattice

A four-element “bowtie” or certain truncated posets missing glb—standard textbook V shape with two tops can lack join if two maxima… actually two maxima lack join if no common upper bound unique—use a poset with two maxima and no top.

Example 11 — Total order Hasse

A path (line) Hasse diagram.

Example 12 — Package versions

Version constraints as order—often not total across products.

Example 13 — Schedule

Critical path ≈ long chain of dependencies.

Example 14 — Dual

Maximal become minimal in dual.

Exercises

  1. Prove \(\subseteq\) is a partial order on \(\mathcal{P}(X)\).
  2. Prove \(\mid\) is a partial order on \(\mathbb{Z}^+\).
  3. Draw Hasse diagram for \((\{1,2,3,4,6,12\},\mid)\).
  4. Find all maximal elements in that poset.
  5. Find a largest chain and a largest antichain in \(\mathcal{P}(\{1,2,3\})\).
  6. Give two topological orders for a poset you draw with \(4\) elements.
  7. Show \((\mathbb{Z},\le)\) is total.
  8. Product order on \(\{0,1\}^2\): draw Hasse.
  9. Prove: in a poset, at most one maximum.
  10. Finite nonempty poset has a maximal element (use finite chain extension / proof).
  11. Is “proper subset” \(\subsetneq\) a partial order? (Reflexive?)
  12. Meet and join of \(\{1,2\}\) and \(\{1,3\}\) in \(\mathcal{P}(\{1,2,3\})\).
  13. \(\gcd\) and \(\mathrm{lcm}\) as meet and join for divisibility—compute for \(12,18\).
  14. CS: list files with include-dependencies as topo sort requirement.
  15. Dilworth awareness: width of Boolean lattice middle level.
  16. Can a partial order have two distinct minima? Yes—example.
  17. Prove antisymmetry of \(\le\) from a Hasse (no—prove from definition on divisibility).
  18. Strict order \(<\) is not reflexive—confirm.
  19. Extend a small partial order to a total order (linear extension) by listing.
  20. Why does a cycle in “must before” prevent topo sort?
  21. Lattice or not: chain of \(3\) elements.
  22. Lattice or not: antichain of \(2\) elements with no extra bounds—add top and bottom?
  23. Prove product of two posets is a poset.
  24. Find incomparable tasks in a real project sketch (3–5 tasks).
  25. Explain Pareto front as antichain in product order of objectives.

CS connection

  • Topological sort of build/package/task DAGs.
  • Subtype lattices and inheritance (not always lattices).
  • Version constraints and dependency resolution.
  • Program analysis abstract domains as lattices (awareness).
  • Git history is not a total order (merges)—poset of commits.
  • Scheduling and critical path = long chain.

Common pitfalls

Pitfall What to do instead
Assuming all pairs comparable Check total vs partial
Maximal = maximum Maximum compares to all
Drawing all transitive edges in Hasse Only covers
Confusing chain with path in unrelated graph Chain = totally ordered subset
Forcing joins that do not exist Not every poset is a lattice
Topo sort on cyclic deps Impossible—fix cycle

Checkpoint

  • Define partial order / poset
  • Draw a Hasse diagram
  • Chain vs antichain examples
  • Maximal vs maximum
  • Topological order connection
  • Meet/join lite on power set or divisibility
  • Product order example
  • Exercises done or logged

Two takeaways:

  1. …
  2. …

Deep dive — linear extensions

A linear extension of a poset is a total order refining it—exactly a topological order of the Hasse DAG. Counting linear extensions is hard in general (#P); for small posets, list them by hand.

Multisets and schedules

If tasks have duration, longest chain ≈ critical path length (in unit durations, chain size). Width ≈ maximum parallel antichain (Dilworth/Mirsky dualities awareness).

Boolean lattice structure

\((\mathcal{P}([n]),\subseteq)\):

  • Rank levels by cardinality.
  • Largest antichain is middle level(s) (Sperner’s theorem awareness).
  • Height \(n+1\) (chain empty to full).
  • Complements give order-reversing involution.

Product order vs lexicographic order

Lex order on \(A\times B\): \((a,b)\le_{lex}(a',b')\) if \(a<a'\) or (\(a=a'\) and \(b\le b'\)).
This is total if \(A,B\) are total—different from product order, which can have incomparabilities. Dictionary order is lex.

More worked examples

Example 15 — Hasse for product
\(\{0,1\}^2\) product order: square with bottom \((0,0)\), top \((1,1)\), two mids incomparable.

Example 16 — Minimal elements of divisors of 30
On divisors of \(30\) under \(\mid\): minimal is \(1\), maximal \(30\).

Example 17 — Topo
Edges \(1\to 2,1\to 3,2\to 4,3\to 4\): linear extensions include \(1,2,3,4\) and \(1,3,2,4\).

Example 18 — Not lattice
Poset with elements \(a,b\) maximal incomparable and no top has no join \(a\vee b\).

Additional exercises

  1. Draw Hasse of \(\mathcal{P}(\{1,2,3\})\).
  2. Prove at most one maximum in a poset.
  3. Count linear extensions of a 3-element V-shaped poset.
  4. Meet/join in divisibility lattice for \(12\) and \(18\).
  5. Explain Pareto front of two-objective optimization as an antichain.

Extended practice workshop

Hasse drawing practice (paper)

  1. Divisors of \(60\) under \(\mid\)—draw Hasse; mark maximal/minimal.
  2. \(\mathcal{P}(\{1,2,3\})\)—draw; identify a maximum chain; middle-level antichain.
  3. Product order on \(\{1,2\}\times\{1,2,3\}\)—draw; find width and height roughly.

Topological orders

  1. Dependency edges: build→test→deploy, lint→test, docs parallel to build. List \(\ge 3\) valid schedules.
  2. Add a cycle docs→build→docs—explain impossibility.

Lattice checks

  1. Is a total order a lattice? (Yes: min/max.)
  2. Antichain of \(3\) elements with no extra bounds—lattice? (No.)
  3. Add top and bottom to that antichain—now a lattice?

Proofs

  1. Prove \(\subseteq\) antisymmetric on \(\mathcal{P}(X)\).
  2. Prove product of posets is a poset.
  3. Prove finite nonempty poset has a minimal element (dual of maximal).
  4. If \(a\le b\) and \(b\le a\) then \(a=b\)—which axiom?

CS write-ups

  1. Package versions: why “latest” may not be a maximum under constraint order.
  2. Git commits with merges as a poset—not a total order.
  3. Critical path = long chain in a task poset.

Glossary card

Term One-line meaning
Poset Set + \(\le\) REF+ANTI+TRANS
Hasse Cover graph drawn upward
Chain Totally ordered subset
Antichain Pairwise incomparable subset
Linear extension Topological total order
Meet/join glb/lub of two elements

Quick theorems to recite

  1. Finite nonempty poset has a maximal element.
  2. At most one maximum (if it exists).
  3. Topological order exists for every finite poset (acyclic strict order).
  4. \((\mathcal{P}(X),\subseteq)\) is a bounded lattice with \(\cap,\cup\).
  5. \((\mathbb{Z}^+,\mid)\) is a lattice with \(\gcd,\mathrm{lcm}\).
  6. Product order is a poset; need not be total even if factors are.

Checkpoint recap (poset day)

  • Draw one Hasse from a relation list
  • Exhibit chain and antichain
  • Distinguish maximal vs maximum
  • Give two topo sorts of a small DAG
  • Compute one meet and one join

Synthesis

Partial orders capture dependency without forcing a unique ranking. Hasse diagrams drop transitive edges so the eye sees covers; topological sorts reinsert a total order compatible with the poset—the algorithm side of finite DAGs. Maximal \(\neq\) maximum: local peaks vs global top.

Vocabulary drill

Term Meaning
Comparable \(a\le b\) or \(b\le a\)
Chain totally ordered subset
Antichain pairwise incomparable
Maximal nothing strictly above
Maximum \(\ge\) every element
Cover \(a\prec b\) \(a<b\) and nothing between
Linear extension total order refining \(\le\)

More worked examples

Example — Divisibility poset.
On \(\{1,2,3,4,6,12\}\) ordered by \(\mid\): Hasse connects \(1\) to primes/prime powers minimal, up to \(12\). Max element \(12\) (also maximum). Chain \(1\mid 2\mid 4\mid 12\); antichain \(\{2,3\}\).

Example — Subset lattice.
\((\mathcal{P}(\{a,b\}),\subseteq)\): bottom \(\emptyset\), top \(\{a,b\}\), middle antichain \(\{\{a\},\{b\}\}\). Meet \(=\cap\), join \(=\cup\).

Example — Topological orders.
Tasks \(A\to B\), \(A\to C\), \(B\to D\), \(C\to D\). Linear extensions include \(A,B,C,D\) and \(A,C,B,D\). Not \(B,A,\ldots\).

Example — Product order.
On \(\mathbb{N}\times\mathbb{N}\), \((a,b)\le(c,d)\) iff \(a\le c\) and \(b\le d\). \((1,4)\) and \((2,3)\) incomparable. Not a total order.

Example — Finite nonempty poset has a maximal element.
Proof idea: start at any \(x_0\); if not maximal climb; finite height/no infinite strict ascent ⇒ stop. (Or take a maximal chain.)

Extra exercises (synthesis)

  1. Draw Hasse for \((\{1,2,3,4,5,6\},\mid)\).
  2. Find all maximal elements of \(\{2,3,4,5,6\}\) under \(\mid\) (no \(1\)).
  3. Prove: a poset has at most one maximum.
  4. Give two different topological sorts of a \(5\)-element poset you invent.
  5. In \((\mathcal{P}(\{1,2,3\}),\subseteq)\), find a chain of size \(4\) and an antichain of size \(3\).
  6. Explain why package install order needs a linear extension of the dependency poset—and what cycles mean.

Orders vs equivalences (keep distinct)

Equivalence Partial order
SYM yes no (ANTI instead)
Picture partition blocks Hasse / DAG
CS cluster, mod \(n\) build order, types

Next: functions as structure-preserving maps between sets—not order maps yet, but the same \(\in\)-based proof style.

Tomorrow

Day 41 — Injections, surjections, bijections. Definitions; pigeon link; finite size comparisons; counting injections; inverse functions iff bijective.