Day 39 — Equivalence relations

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

26. Prove carefully that \(\equiv\pmod n\) is transitive.
    
27. Show \(f([a])=2a \bmod n\) on \(\mathbb{Z}/n\) is well-defined.
    
28. Is \(g([a])=a\) as integer well-defined on \(\mathbb{Z}/n\)?
    
29. List all equivalence relations on a 3-element set (5 Bell).
    
30. 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

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

Partition drills

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

Well-definedness drills

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

Proof writing

14. Full proof: classes equal or disjoint.
    
15. Full proof: same-block relation is transitive.
    
16. \(\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)

31. Prove fully that \(\equiv\pmod n\) is REF, SYM, TRANS.
    
32. List all equivalence relations on \(\{1,2,3\}\) (equivalently: all partitions).
    
33. Kernel of \(f(n)=n \bmod 2\) on \(\mathbb{Z}\)—describe classes.
    
34. Show addition on \(\mathbb{Z}/n\mathbb{Z}\) is well-defined: if \(a\equiv a'\), \(b\equiv b'\) then \(a+b\equiv a'+b'\).
    
35. Is multiplication well-defined mod \(n\)? Prove.
    
36. 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.