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: the relation on integers defined by $|a-b| \le 1$ is reflexive and symmetric but not transitive (0 relates to 1 and 1 to 2, but 0 does not relate to 2). 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 to the module project

Use this concept to state, justify or challenge one claim in the workflow project. Name the mathematical model and the execution assumptions separately; software behavior is not established by an analogy alone.

Read This Only If Stuck

Use the bounded reading guide to locate this lesson's topic in MCS or Rosen. These links open book indexes. Find the named topic in your edition, read one relevant explanation, then reconstruct the argument with the book closed.

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.

A function on classes must ignore representative choice

Suppose q:A→A/~ sends an element to its class and f:A→B is a total map. We want a map h on classes with f=h∘q. Such h exists exactly when f is constant on each class. Necessity: equivalent a,b have q(a)=q(b), so applying h gives f(a)=f(b). Sufficiency: define h([a])=f(a); class constancy makes the value independent of a, and each class has a representative.

For a finite empty carrier, the empty collection of blocks is the partition. The usual partition definition requires each block nonempty, not the collection itself nonempty. No representative is needed when there are no classes.

Transfer attempt: apply this criterion to the two label choices in the workflow project. Choosing the first element in an iteration order does not prove that the original proposed label rule was representative-independent.

Use Practice Solutions and Feedback after your attempt, and Proof and Model Contracts to audit assumptions.