Skip to main content

Equivalence Relations and Partitions

What This Concept Is​

An equivalence relation on a set $A$ is a relation $\sim \ \subseteq A \times A$ that is simultaneously reflexive, symmetric, and transitive:

  • Reflexive: $\forall a \in A,\ a \sim a$.
  • Symmetric: $\forall a, b \in A,\ a \sim b \rightarrow b \sim a$.
  • Transitive: $\forall a, b, c \in A,\ (a \sim b \land b \sim c) \rightarrow a \sim c$.

Given an equivalence relation, the equivalence class of an element $a \in A$ is

$$[a] \ =\ {x \in A \ :\ x \sim a}.$$

The set of all equivalence classes, written $A / !\sim$, is the quotient set.

It partitions $A$: every element of $A$ lies in exactly one class, and different classes are disjoint. These two facts are not optional; both follow from the three axioms, and the rest of the concept page is about why.

A partition of $A$ is a collection $\mathcal{P} = {B_i}$ of nonempty disjoint subsets whose union is $A$.

The two ideas -- equivalence relations and partitions -- are two views of the same structure:

  • Given $\sim$ on $A$, the equivalence classes form a partition.
  • Given a partition $\mathcal{P}$ of $A$, define $a \sim b$ iff $a$ and $b$ are in the same block. The result is an equivalence relation.

This is the Fundamental Theorem of Equivalence Relations: equivalence relations on $A$ are in one-to-one correspondence with partitions of $A$. Same object, two names.

The relation view is convenient for proofs about closure under operations ("if $\sim$ is preserved by $+$, then $+$ descends to the quotient"). The partition view is convenient for counting ($|A| = \sum |B_i|$ when $A$ is finite) and for implementing quotient structures in code (store a representative per class and a mapping from element to representative -- this is how union-find data structures work).

Why It Matters Here​

Equivalence is the mathematical move that says "treat these as the same for this purpose" without claiming identity. It is the mechanism behind every abstraction in computer science.

Integers modulo $n$, isomorphism of data structures, bisimulation of state machines, structural equality of terms, alpha-equivalence of programs, unification in type inference -- all are quotients by equivalence relations. In each case we throw away distinctions that do not matter for the task and keep the ones that do. The relation axioms are the minimal guarantees that this throwing-away is self-consistent.

Pedagogically, this concept bridges Cluster 1 (where you learned to read nested quantifiers and prove implications) and Cluster 3 (where you learned sets and functions). To prove "$\sim$ is an equivalence relation" you write three small universally quantified implications. To use the resulting quotient you work with classes and partitions -- which are sets of sets, so set language had better be automatic by now.

Downstream, every module where we talk about "up to [something]" is invoking an equivalence relation: "up to isomorphism," "up to reordering," "up to refactoring," "up to renaming." If equivalence is fuzzy here, every "up to" claim later reads as vague prose rather than as a precise mathematical statement.

There is also a pragmatic reason this concept deserves careful attention. Nearly every buggy equals() method in Java or __eq__ in Python can be traced back to one of three failures -- not reflexive, not symmetric, or not transitive. Hash tables, sets, and caches then silently produce wrong answers. Knowing the three axioms as user-visible invariants of a language's equality turns a vague "equality bug" into a specific diagnosis.

Concrete Example​

Running example: congruence modulo 3. Define $\sim$ on $\mathbb{Z}$ by $a \sim b \iff 3 \mid (a - b)$.

Claim. $\sim$ is an equivalence relation.

Proof.

Reflexive. For any $a \in \mathbb{Z}$, $a - a = 0 = 3 \cdot 0$, so $3 \mid 0$ and $a \sim a$.

Symmetric. Suppose $a \sim b$. Then $a - b = 3k$ for some $k \in \mathbb{Z}$, so $b - a = -3k = 3(-k)$, so $3 \mid (b - a)$ and $b \sim a$.

Transitive. Suppose $a \sim b$ and $b \sim c$. Then $a - b = 3j$ and $b - c = 3k$ for integers $j, k$. Adding: $a - c = 3j + 3k = 3(j + k)$, so $3 \mid (a - c)$ and $a \sim c$. $\blacksquare$

Classes. $[0] = {\ldots, -6, -3, 0, 3, 6, \ldots}$, $[1] = {\ldots, -5, -2, 1, 4, 7, \ldots}$, $[2] = {\ldots, -4, -1, 2, 5, 8, \ldots}$. Every integer is in exactly one class; the three classes are pairwise disjoint and their union is $\mathbb{Z}$. The quotient set $\mathbb{Z} / !\sim$ has three elements and is usually written $\mathbb{Z} / 3\mathbb{Z}$ or $\mathbb{Z}_3$.

Proving disjointness explicitly. A useful lemma: for any equivalence $\sim$, if $[a] \cap [b] \ne \emptyset$, then $[a] = [b]$.

Proof. Let $c \in [a] \cap [b]$. Then $c \sim a$ and $c \sim b$. By symmetry, $a \sim c$; by transitivity, $a \sim b$. For any $x \in [a]$, $x \sim a \sim b$ gives $x \in [b]$; the reverse inclusion is symmetric. So $[a] = [b]$. $\blacksquare$

This shows the classes are either identical or disjoint -- there is no partial overlap. Combined with reflexivity ($a \in [a]$, so no element is unassigned), this gives the partition.

A second worked example: $\alpha$-equivalence on lambda terms. In programming-language theory, two terms are $\alpha$-equivalent if they differ only in the names of bound variables: $\lambda x.,x$ and $\lambda y.,y$ are $\alpha$-equivalent. This is reflexive (a term is $\alpha$-equivalent to itself), symmetric (swap the renaming), and transitive (compose two renamings). The quotient $\text{Terms} / !\sim_\alpha$ is how compilers reason about terms "up to bound-variable naming" without tripping on accidental name capture. Same partition structure as modular arithmetic, different domain.

Common Confusion / Misconception​

  1. Confusing $\sim$ with $=$. Equivalence says "same for this purpose," not "identical." $4 \sim 1$ under congruence mod $3$, but $4 \ne 1$. Writing $[4] = [1]$ is correct (they are the same equivalence class); writing $4 = 1$ is wrong. When you switch between "elements" and "classes" in a proof, keep the notation straight.
  2. Transitivity imagined but not established. Reflexivity and symmetry are often easy to check; transitivity is where most proposed equivalences fail. A classic failure: "have met each other" on a group of people is reflexive and symmetric but not transitive. Always verify the third property explicitly.
  3. Thinking every partition induces a unique relation "close to" $=$. The partition with a single block (everybody related to everybody) is a legal equivalence -- it is the coarsest one, identifying all elements. The partition with every singleton as a block is the finest equivalence -- it is equality. Between these extremes lies every other equivalence. Which one you pick depends on what you are abstracting over.
  4. Requiring classes to be "small." Equivalence classes can be arbitrarily large and even infinite. $[0] \in \mathbb{Z} / 3\mathbb{Z}$ is an infinite set (all multiples of $3$). The quotient set may still be finite: $|\mathbb{Z} / 3\mathbb{Z}| = 3$ even though each class is infinite.
  5. Well-definedness on classes forgotten. When you define an operation on equivalence classes (e.g., addition modulo $3$: $[a] + [b] := [a + b]$), you must prove the rule does not depend on representatives. If $a \sim a'$ and $b \sim b'$, you must show $a + b \sim a' + b'$. Skipping this check produces the most common bug in quotient constructions.
  6. Two different equivalences giving identical classes on some subset. Two equivalences $\sim_1$ and $\sim_2$ can produce the same partition on a subset while disagreeing globally. The equivalence is defined by all its pairs, not by a sample. When you see a rule like "same colour" you still owe the proof that the rule really is reflexive, symmetric, and transitive on the whole domain.

How To Use It​

Operational checklist for working with equivalence relations:

  1. To show $\sim$ is an equivalence: prove reflexive, symmetric, transitive -- three short paragraphs, each following the proof template for a universally quantified implication.
  2. To identify a class: pick a representative $a$ and compute $[a] = {x : x \sim a}$ using the defining rule.
  3. To prove two classes are equal: show one representative is equivalent to the other; $[a] = [b] \iff a \sim b$.
  4. To prove disjointness: show that overlap forces equality (the lemma proved above), so the partition is well-defined.
  5. To define functions on the quotient: pick a rule on representatives and prove well-definedness -- the rule must give the same answer on any two equivalent representatives.
  6. To translate between views: given $\sim$, list its classes; given a partition, define "same block" as the relation. The two views are interchangeable.
  7. To count classes: partition size equals the number of classes; when $A$ is finite, $|A| = \sum_i |B_i|$ over the partition.
  8. To descend an operation: verify the original operation respects $\sim$ on each input coordinate; then define the operation on classes by $[a] \star [b] := [a \star b]$.

Check Yourself​

  1. Why is "being in the same equivalence class" automatically reflexive, symmetric, and transitive? Sketch the proof from the partition axioms.
  2. What is the equivalence class of $5$ under congruence modulo $4$? How many classes does $\mathbb{Z} / 4\mathbb{Z}$ have, and why exactly that many?
  3. Give a relation that is reflexive and symmetric but not transitive. Explain what structure you get if you take its transitive closure.
  4. When defining a function $f : \mathbb{Z} / n \mathbb{Z} \to X$ by a rule on integers, what must you prove to conclude that $f$ is well-defined on classes?
  5. Describe the coarsest and finest equivalence relations on a set $A$. What do their quotients look like?
  6. If $|A| = 4$, how many different equivalence relations are there on $A$? (Hint: count partitions; the answer is a Bell number.)
  7. Why does the lemma "$[a] \cap [b] \ne \emptyset \Rightarrow [a] = [b]$" require all three properties, not just reflexivity and symmetry?

Mini Drill or Application​

  1. On the set of strings over ${a, b}$, define $s \sim t$ iff $s$ and $t$ have the same length. Prove this is an equivalence relation. Describe the equivalence class of "$ab$" and describe the quotient set.
  2. On $\mathbb{Z}$, define $a \sim b$ iff $a$ and $b$ have the same remainder when divided by $5$. Prove this is an equivalence; list the classes; define addition and multiplication on classes and verify well-definedness of both.
  3. On the set of all functions $\mathbb{Z} \to \mathbb{Z}$, define $f \sim g$ iff $f$ and $g$ agree on every input. Is this an equivalence relation? Is it the same as function equality? Compare with "$f$ and $g$ agree on ${-10, \ldots, 10}$"; is that still an equivalence?
  4. Describe the partition of a committee into "groups that have voted the same way on a fixed ballot" and verify it is induced by an equivalence relation on committee members.
  5. Prove the Fundamental Theorem of Equivalence Relations formally: the map $\sim \ \mapsto \ A / !\sim$ is a bijection between equivalence relations on $A$ and partitions of $A$.

Complete at least items 1 and 2 in full; the others are good for discussion with a study partner.

Bonus drill (well-definedness): on $\mathbb{Z} / 6 \mathbb{Z}$, attempt to define an operation $f([a]) := [a^2]$. Show this is well-defined by proving: if $a \equiv a' \pmod 6$, then $a^2 \equiv (a')^2 \pmod 6$. Now attempt $g([a]) := [\lfloor a/2 \rfloor]$; find two representatives of the same class whose images differ, and conclude $g$ is not well-defined. The contrast is the discipline of quotient constructions in miniature.

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Union-find (disjoint-set) is the canonical data structure for maintaining equivalence classes as they merge; Kruskal's algorithm relies on it. The data structure's invariant is "two elements are in the same set iff they are equivalent under the current relation."
  • Semester 3 (software design). equals() in Java, Eq in Haskell, __eq__ in Python are equivalence relations the language requires you to implement correctly -- reflexive, symmetric, transitive. Violations cause bugs in hash tables and set operations.
  • Semester 5 (concurrency). Bisimulation is an equivalence on states of labelled transition systems capturing "observationally indistinguishable"; it is the semantic foundation for process calculi.
  • Semester 6 (distributed systems). Eventual consistency asks whether all replicas eventually reach the "same" state -- same up to a chosen equivalence (bytewise? logical content? commutative-reordering?). Choosing the equivalence is a design decision.
  • Semester 7 (architecture). "Semantically equivalent refactorings" is an equivalence relation on code: reflexive (code is equivalent to itself), symmetric (refactoring can be undone), transitive (chain of safe refactorings is safe).
  • Semester 9+ (PL theory / verification). $\alpha$-equivalence, $\beta$-equivalence, and observational equivalence on programs are all equivalence relations; quotienting programs by the right equivalence is the mechanism behind program refinement and equational reasoning.
  • Across engineering. Hashing relies on an equivalence: two inputs hash the same iff they belong to the same bucket. A hash function's correctness is "$a = b \Rightarrow h(a) = h(b)$" -- i.e., hashing respects equality as a coarser equivalence.

Read This Only If Stuck​

Closing Note​

Equivalence relations are the formal apparatus for every time you say "these are the same in the way that matters." That move powers modular arithmetic, data-structure identity, program semantics, and architectural refactoring.

If you leave this page knowing how to prove the three properties, write classes in set notation, and check well-definedness of operations on classes, you have the toolkit needed to read every "up to $\sim$" claim in the rest of the curriculum without flinching.

Treat the three-property proof template as a reflex -- by the end of Cluster 4 it should take a minute, not a page. And keep the partition-quotient duality in mind: whenever a design decision asks you to "group these things together," there is an equivalence relation waiting to be named.