Equivalence Classes and Partitions

Suppose you sort a box of fractions by numerical value. Then 1/21/2, 2/42/4, and 50/10050/100 all land in the same pile. What exactly is a "pile"? Why does this sorting process always produce piles that are disjoint and exhaustive? They never overlap and never leave a fraction homeless. This article answers that question in full generality. It shows that the informal act of "grouping objects by a shared property" is mathematically identical to the notion of an Equivalence Relation. The identification is not an analogy — it is a genuine mathematical equivalence, in the strongest sense. Equivalence relations on a set AA and partitions of AA determine each other exactly, via mutually inverse constructions. This correspondence matters because it converts a relational description of "sameness" into a structural description. A relational description is a set of ordered pairs satisfying three axioms. A structural description is a way of chopping AA into non-overlapping pieces. The structural picture is often easier to reason about, and it is the one that generalizes. The pieces themselves — equivalence classes — become the elements of a new set, the quotient set. On this quotient set, one can define new operations and functions "up to equivalence." Every construction of a quotient object in mathematics rests on this single theorem. This includes modular arithmetic, quotient groups, quotient topological spaces, and the rational numbers built from pairs of integers. The big picture is this: an equivalence relation is the analytic description of a partition. It is a rule for testing when two elements belong together. A partition, meanwhile, is the synthetic description of an equivalence relation. It is an explicit list of the groups. The Fundamental Theorem of Equivalence Relations makes this precise. It does so by exhibiting a bijection between the set of equivalence relations on AA and the set of partitions of AA. This article delivers a complete, rigorous statement and proof of that theorem. It gives careful attention to the definitions of equivalence class and partition. It offers worked examples on both finite and infinite sets. It includes a counterexample showing why each hypothesis (reflexivity, symmetry, transitivity) is indispensable. Finally, it looks at where this correspondence shows up across mathematics. This sets the stage for the notion of a Quotient Set and the delicate question of well-definedness for functions on quotients.

Key takeaways
  • An equivalence relation ∼\sim on AA splits AA into equivalence classes [a]={x∈A:x∼a}[a] = \{x \in A : x \sim a\}.
  • A partition of AA is a collection of nonempty, pairwise disjoint subsets whose union is all of AA.
  • The Fundamental Theorem: equivalence relations on AA and partitions of AA correspond bijectively, each induced from the other.
  • Two elements are related iff they lie in the same block of the induced partition — this is the technical heart of the proof.
  • Dropping reflexivity, symmetry, or transitivity each independently destroys the "disjoint, exhaustive blocks" structure.
  • Key idea: an equivalence relation is, in disguise, nothing more than a rule for grouping a set into disjoint, exhaustive families.

Where this lives today

The equivalence-class/partition correspondence is the quiet engine behind an enormous share of mathematical construction. In abstract algebra, cosets of a subgroup partition a group, and the corresponding equivalence relation (x∼yx \sim y iff xy−1∈Hxy^{-1} \in H) is exactly the machinery behind quotient groups and Lagrange's theorem; the same pattern gives quotient rings from ideals. In number theory, congruence classes modulo nn (Example 1) partition Z\mathbb{Z} and underlie modular arithmetic, RSA cryptography, and check-digit schemes. In the construction of number systems, both Q\mathbb{Q} (Example 2) and R\mathbb{R} (via Cauchy sequences modulo the "eventually close" relation) are built as quotient sets. In topology, quotient spaces (gluing constructions such as building a torus from a square) are defined by first specifying a partition or an equivalence relation on points and topologizing the quotient set. In computer science, union-find (disjoint-set) data structures maintain a partition of a finite set in real time, implicitly tracking an equivalence relation under merge operations, and are central to Kruskal's minimum spanning tree algorithm and to compiler register-allocation and type-inference (unification) algorithms. In linear algebra, cosets of a subspace partition a vector space and are the underlying data of a quotient vector space V/WV/W. In statistics and combinatorics, partitions of a finite set are counted by Bell numbers, and equivalence relations refine or coarsen one another exactly as their partitions refine or coarsen, giving a lattice structure exploited in cluster analysis. Across all of these, the theorem proved here is the silent justification that the two languages — "relation" and "grouping" — may be used interchangeably.

:::quiz[If ∼\sim is an equivalence relation on AA and a,b∈Aa, b \in A with [a]∩[b]≠∅[a] \cap [b] \ne \varnothing, what can you conclude?]

  • a=ba = b
  • [a][a] and [b][b] are disjoint after all
  • [a]=[b][a] = [b] ✓
  • Nothing; overlapping classes are possible

:::quiz[For the relation x∼y  ⟺  5∣(x−y)x \sim y \iff 5 \mid (x-y) on Z\mathbb{Z}, what is [12][12]?]

  • {12}\{12\}
  • {5k+2:k∈Z}\{5k+2 : k \in \mathbb{Z}\} ✓
  • {5k:k∈Z}\{5k : k \in \mathbb{Z}\}
  • {12,24,36,…}\{12, 24, 36, \ldots\}

Ask the tutor: How do I check that a function defined on equivalence classes is "well-defined," and why does that check matter so much?

DefinitionEquivalence classes and partitions

Let AA be a set and let ∼\sim be an Equivalence Relation on AA, meaning ∼ ⊆A×A\sim \, \subseteq A \times A is reflexive, symmetric, and transitive.

Equivalence class. For a∈Aa \in A, the equivalence class of aa under ∼\sim is

[a]∼  =  { x∈A:x∼a }.[a]_\sim \;=\; \{\, x \in A : x \sim a \,\}.

When ∼\sim is clear from context we write [a][a]. The element aa is called a representative of the class [a][a].

Quotient set. The set of all equivalence classes is denoted

A/ ⁣∼  =  { [a]∼:a∈A }A/\!\sim \;=\; \{\, [a]_\sim : a \in A \,\}

and is called the quotient of AA by ∼\sim (this set becomes the central object in the theory of Quotient Sets).

Partition. A partition of a set AA is a collection P\mathcal{P} of subsets of AA such that: 1. (Nonempty blocks) ∅∉P\varnothing \notin \mathcal{P}; 2. (Pairwise disjoint) for all P,Q∈PP, Q \in \mathcal{P}, if P≠QP \neq Q then P∩Q=∅P \cap Q = \varnothing; 3. (Covers AA) ⋃P∈PP=A\bigcup_{P \in \mathcal{P}} P = A. Elements of P\mathcal{P} are called the blocks (or cells, or parts) of the partition.

Intuition

Think of AA as a room full of people and ∼\sim as the relation "has the same birth-month as." This relation is reflexive (everyone shares a birth-month with themselves), symmetric (if you share a birth-month with me, I share one with you), and transitive (if you and I share, and I and a third person share, then you and that third person share too). The equivalence class [a][a] is simply the crowd of people born in the same month as aa. Twelve possible birth-months give (at most) twelve nonempty crowds; every person belongs to exactly one crowd; the crowds never overlap. That collection of crowds is precisely a partition of the room. The subtlety — and the entire content of the theorem below — is that this process is reversible. If instead someone hands you twelve labeled boxes (already-formed groups) covering the room with no overlaps, you can manufacture a relation: declare x∼yx \sim y exactly when xx and yy sit in the same box. This manufactured relation is automatically reflexive, symmetric, and transitive, and running the "equivalence class" construction on it hands back the exact same twelve boxes you started with. The two processes — relation-to-partition and partition-to-relation — are mutually inverse. That inverse pairing, not just the existence of classes, is the actual theorem.

Figure
A set AA partitioned into three equivalence classes, with the induced relation shown as complete graphs inside each block
A / ~ has three blocks [a] [b] [c]
TheoremFundamental Theorem of Equivalence Relations and Partitions

Let AA be a set. Let Eq(A)\mathrm{Eq}(A) denote the set of all equivalence relations on AA, and let Part(A)\mathrm{Part}(A) denote the set of all partitions of AA.

(I) From relations to partitions. If ∼ ∈Eq(A)\sim \, \in \mathrm{Eq}(A), then the collection of equivalence classes

Φ(∼)  :=  A/ ⁣∼  =  { [a]∼:a∈A }\Phi(\sim) \;:=\; A/\!\sim \;=\; \{\, [a]_\sim : a \in A \,\}

is a partition of AA.

(II) From partitions to relations. If P∈Part(A)\mathcal{P} \in \mathrm{Part}(A), define a relation on AA by

x Ψ(P) yiff∃P∈P (x∈P and y∈P).x \,\Psi(\mathcal{P})\, y \quad \text{iff} \quad \exists P \in \mathcal{P} \ (x \in P \text{ and } y \in P).

Then Ψ(P)\Psi(\mathcal{P}) is an equivalence relation on AA.

(III) Mutual inversion. The maps

Φ:Eq(A)→Part(A),Ψ:Part(A)→Eq(A)\Phi : \mathrm{Eq}(A) \to \mathrm{Part}(A), \qquad \Psi : \mathrm{Part}(A) \to \mathrm{Eq}(A)

are mutually inverse bijections: Ψ(Φ(∼))=∼\Psi(\Phi(\sim)) = \sim for every ∼ ∈Eq(A)\sim \, \in \mathrm{Eq}(A), and Φ(Ψ(P))=P\Phi(\Psi(\mathcal{P})) = \mathcal{P} for every P∈Part(A)\mathcal{P} \in \mathrm{Part}(A). Consequently there is a canonical bijective correspondence between equivalence relations on AA and partitions of AA.

Proof

We prove each part in turn. Throughout, AA is a fixed set.

Part (I): A/ ⁣∼A/\!\sim is a partition of AA. Let ∼\sim be an equivalence relation on AA; write RR for ∼\sim when convenient. We must check the three partition axioms for P:=A/ ⁣∼\mathcal{P} := A/\!\sim. Nonempty blocks. Let [a]∈A/ ⁣∼[a] \in A/\!\sim for some a∈Aa \in A. By reflexivity of ∼\sim, a∼aa \sim a, so a∈[a]a \in [a]. Hence [a]≠∅[a] \neq \varnothing. This establishes axiom 1. Covers AA. Let x∈Ax \in A. By reflexivity, x∼xx \sim x, so x∈[x]x \in [x], and [x]∈A/ ⁣∼[x] \in A/\!\sim. Hence x∈⋃a∈A[a]x \in \bigcup_{a \in A} [a]. Since xx was arbitrary, A⊆⋃[a]A \subseteq \bigcup [a]. Conversely every [a][a] is a subset of AA by definition, so ⋃[a]⊆A\bigcup [a] \subseteq A. Hence ⋃a∈A[a]=A\bigcup_{a\in A}[a] = A, establishing axiom 3. Pairwise disjoint. This is the substantive step. We first prove a lemma. > Lemma. For all a,b∈Aa, b \in A: a∼ba \sim b if and only if [a]=[b][a] = [b]. Proof of Lemma. (⇐\Leftarrow) Suppose [a]=[b][a] = [b]. By reflexivity a∼aa \sim a, so a∈[a]=[b]a \in [a] = [b], i.e. a∈[b]a \in [b], which by definition of [b][b] means a∼ba \sim b. (⇒\Rightarrow) Suppose a∼ba \sim b. We show [a]⊆[b][a] \subseteq [b] and [b]⊆[a][b] \subseteq [a].

  • Let x∈[a]x \in [a], so x∼ax \sim a. Since a∼ba \sim b, transitivity gives x∼bx \sim b, i.e. x∈[b]x \in [b]. Hence [a]⊆[b][a] \subseteq [b].
  • Since ∼\sim is symmetric and a∼ba \sim b, we get b∼ab \sim a. Let y∈[b]y \in [b], so y∼by \sim b. Since b∼ab \sim a, transitivity gives y∼ay \sim a, i.e. y∈[a]y \in [a]. Hence [b]⊆[a][b] \subseteq [a].

Combining, [a]=[b][a] = [b]. ■\blacksquare (Lemma) Now suppose [a]≠[b][a] \neq [b] for some a,b∈Aa, b \in A; we must show [a]∩[b]=∅[a] \cap [b] = \varnothing. We argue by contradiction: suppose z∈[a]∩[b]z \in [a] \cap [b]. Then z∼az \sim a and z∼bz \sim b. By symmetry, a∼za \sim z. Combining a∼za \sim z and z∼bz \sim b by transitivity gives a∼ba \sim b. By the Lemma (the ⇒\Rightarrow direction just proved), a∼ba \sim b implies [a]=[b][a] = [b], contradicting our assumption [a]≠[b][a] \neq [b]. Hence no such zz exists, so [a]∩[b]=∅[a] \cap [b] = \varnothing. This establishes axiom 2. All three axioms hold, so A/ ⁣∼A/\!\sim is a partition of AA. This proves (I).

Part (II): Ψ(P)\Psi(\mathcal{P}) is an equivalence relation. Let P\mathcal{P} be a partition of AA and define xRyx \mathrel{R} y to mean "∃P∈P\exists P \in \mathcal{P} with x,y∈Px, y \in P," where R:=Ψ(P)R := \Psi(\mathcal{P}). We check the three axioms of an equivalence relation. Reflexivity. Let x∈Ax \in A. Since P\mathcal{P} covers AA (axiom 3 of a partition), there exists P∈PP \in \mathcal{P} with x∈Px \in P. Then certainly x∈Px \in P and x∈Px \in P, so xRxx \mathrel{R} x. Symmetry. Suppose xRyx \mathrel{R} y. Then there is P∈PP \in \mathcal{P} with x∈Px \in P and y∈Py \in P. The same witness PP shows y∈Py \in P and x∈Px \in P, so yRxy \mathrel{R} x. Transitivity. Suppose xRyx \mathrel{R} y and yRzy \mathrel{R} z. Then there exist P,Q∈PP, Q \in \mathcal{P} with x,y∈Px, y \in P and y,z∈Qy, z \in Q. In particular y∈P∩Qy \in P \cap Q, so P∩Q≠∅P \cap Q \neq \varnothing. By the pairwise-disjointness axiom of a partition (axiom 2, contrapositive form: nonempty intersection forces equality), P=QP = Q. Hence x∈P=Qx \in P = Q and z∈Q=Pz \in Q = P, so x,z∈Px, z \in P, giving xRzx \mathrel{R} z. All three axioms hold, so Ψ(P)\Psi(\mathcal{P}) is an equivalence relation on AA. This proves (II).

Part (III): Φ\Phi and Ψ\Psi are mutually inverse. Claim 1: Ψ(Φ(∼))=∼\Psi(\Phi(\sim)) = \sim for every equivalence relation ∼\sim on AA. Let ∼\sim be an equivalence relation, let P=Φ(∼)=A/ ⁣∼\mathcal{P} = \Phi(\sim) = A/\!\sim, and let R=Ψ(P)R = \Psi(\mathcal{P}). We must show RR, as a set of ordered pairs, equals ∼\sim. We show both inclusions. Suppose xRyx \mathrel{R} y. By definition of Ψ\Psi, there is a block [a]∈P[a] \in \mathcal{P} with x,y∈[a]x, y \in [a]. Then x∼ax \sim a and y∼ay \sim a. By symmetry, a∼ya \sim y; by transitivity applied to x∼ax \sim a and a∼ya \sim y, we get x∼yx \sim y. Hence R⊆∼R \subseteq \sim. Conversely, suppose x∼yx \sim y. Consider the block [x]∈P[x] \in \mathcal{P}. By reflexivity, x∼xx \sim x, so x∈[x]x \in [x]. Since x∼yx \sim y, by definition y∈[x]y \in [x] as well. So x,y∈[x]∈Px, y \in [x] \in \mathcal{P}, which by definition of Ψ\Psi gives xRyx \mathrel{R} y. Hence ∼ ⊆R\sim \, \subseteq R. Combining the two inclusions, R=∼R = \sim, i.e. Ψ(Φ(∼))=∼\Psi(\Phi(\sim)) = \sim. Claim 2: Φ(Ψ(P))=P\Phi(\Psi(\mathcal{P})) = \mathcal{P} for every partition P\mathcal{P} of AA. Let P\mathcal{P} be a partition, let R=Ψ(P)R = \Psi(\mathcal{P}), and let P′=Φ(R)=A/R\mathcal{P}' = \Phi(R) = A/R. We show P′=P\mathcal{P}' = \mathcal{P} as collections of sets, by showing every block of P′\mathcal{P}' is a block of P\mathcal{P} and vice versa. First, take any RR-class [a]R∈P′[a]_R \in \mathcal{P}', where a∈Aa \in A. Since P\mathcal{P} covers AA, there is a (unique, by disjointness — see below) block Pa∈PP_a \in \mathcal{P} with a∈Paa \in P_a. We claim [a]R=Pa[a]_R = P_a.

  • If x∈[a]Rx \in [a]_R, then xRax \mathrel{R} a, so by definition of R=Ψ(P)R = \Psi(\mathcal{P}) there is a block Q∈PQ \in \mathcal{P} with x,a∈Qx, a \in Q. Since a∈Qa \in Q and a∈Paa \in P_a, we have a∈Q∩Paa \in Q \cap P_a, so Q∩Pa≠∅Q \cap P_a \neq \varnothing; by pairwise disjointness of P\mathcal{P}, Q=PaQ = P_a. Hence x∈Pax \in P_a. This shows [a]R⊆Pa[a]_R \subseteq P_a.
  • If x∈Pax \in P_a, then x,a∈Pa∈Px, a \in P_a \in \mathcal{P}, so by definition of RR, xRax \mathrel{R} a, i.e. x∈[a]Rx \in [a]_R. This shows Pa⊆[a]RP_a \subseteq [a]_R.

Hence [a]R=Pa∈P[a]_R = P_a \in \mathcal{P}, so every block of P′\mathcal{P}' is a block of P\mathcal{P}; that is, P′⊆P\mathcal{P}' \subseteq \mathcal{P}. Conversely, let P∈PP \in \mathcal{P}. Since PP is nonempty (axiom 1 of a partition), pick a∈Pa \in P. By the argument just given (with this PP in place of PaP_a, valid since a∈Pa \in P), [a]R=P[a]_R = P. Hence P=[a]R∈P′P = [a]_R \in \mathcal{P}', so P⊆P′\mathcal{P} \subseteq \mathcal{P}'. Combining, P′=P\mathcal{P}' = \mathcal{P}, i.e. Φ(Ψ(P))=P\Phi(\Psi(\mathcal{P})) = \mathcal{P}.

Conclusion. By Claims 1 and 2, Ψ∘Φ=idEq(A)\Psi \circ \Phi = \mathrm{id}_{\mathrm{Eq}(A)} and Φ∘Ψ=idPart(A)\Phi \circ \Psi = \mathrm{id}_{\mathrm{Part}(A)}. A function with a two-sided inverse is a bijection, so Φ:Eq(A)→Part(A)\Phi : \mathrm{Eq}(A) \to \mathrm{Part}(A) is a bijection with inverse Ψ\Psi. ■\blacksquare

∎

The proof technique throughout is direct element-chasing from the axioms — reflexivity, symmetry, and transitivity are each invoked at a specific, identifiable point (reflexivity for covering and for membership a∈[a]a \in [a]; symmetry and transitivity together for disjointness), and the two-sided inverse verification is done by mutual set-inclusion, the standard technique for proving set equality.

Worked examples

Example 1: Congruence mod nn, with n=5n = 5 and A=ZA = \mathbb{Z}. Define x∼yx \sim y iff 5∣(x−y)5 \mid (x - y). This is a standard equivalence relation (reflexive since 5∣05 \mid 0; symmetric since 5∣(x−y)⇒5∣(y−x)5\mid(x-y) \Rightarrow 5 \mid (y-x); transitive since 5∣(x−y)5\mid(x-y) and 5∣(y−z)5\mid(y-z) imply 5∣(x−z)5 \mid (x-z), as the sum of two multiples of 55 is a multiple of 55). Let us compute [17][17]. We need all integers xx with 5∣(x−17)5 \mid (x - 17), i.e. x≡17≡2(mod5)x \equiv 17 \equiv 2 \pmod 5. So

[17]={…,−8,−3,2,7,12,17,22,27,…}={5k+2:k∈Z}.[17] = \{\ldots, -8, -3, 2, 7, 12, 17, 22, 27, \ldots\} = \{5k + 2 : k \in \mathbb{Z}\}.

Note [17]=[2]=[−3]=[12][17] = [2] = [-3] = [12] — infinitely many representatives give the same class, exactly as the Lemma in the proof predicts, since 17∼217 \sim 2. The full quotient set is

Z/ ⁣∼  =  { [0],[1],[2],[3],[4] },\mathbb{Z}/\!\sim \;=\; \{\, [0], [1], [2], [3], [4] \,\},

a partition of Z\mathbb{Z} into exactly 55 infinite blocks — the residue classes mod 55. Applying Ψ\Psi to this partition (declare x∼′yx \sim' y iff x,yx, y lie in a common block) recovers precisely the original congruence relation, illustrating Claim 2 of Part (III) concretely: Φ(Ψ(P))=P\Phi(\Psi(\mathcal P)) = \mathcal P here reads as "sorting integers by residue mod 5, then re-deriving the 'same residue' relation from the sorting, gives back congruence mod 5."

Example 2: A relation on ordered pairs, building the rationals. Let A=Z×(Z∖{0})A = \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}), and define

(a,b)∼(c,d)iffad=bc.(a,b) \sim (c,d) \quad \text{iff} \quad ad = bc.

This is the relation whose quotient set is used to construct Q\mathbb{Q} from Z\mathbb{Z}. Let's verify it is an equivalence relation and compute a specific class. Reflexive: (a,b)∼(a,b)(a,b) \sim (a,b) iff ab=baab = ba, true in Z\mathbb{Z}. Symmetric: if ad=bcad = bc then cb=dacb = da (just commutativity and reading the equation backwards), so (c,d)∼(a,b)(c,d) \sim (a,b). Transitive: suppose (a,b)∼(c,d)(a,b) \sim (c,d) and (c,d)∼(e,f)(c,d) \sim (e,f), i.e. ad=bcad = bc and cf=decf = de. We want af=beaf = be. Multiply the first equation by ff: adf=bcfadf = bcf. Substitute cf=decf = de: adf=b(de)=bdeadf = b(de) = bde. Since d≠0d \neq 0 (as dd is a second coordinate, hence nonzero by definition of AA), we may cancel dd from adf=bdeadf = bde to get af=beaf = be, as desired. (Cancellation is valid because Z\mathbb{Z} is an integral domain.) Hence (a,b)∼(e,f)(a,b) \sim (e,f). Now compute [(6,4)][(6, 4)]: this is the set of all (c,d)∈A(c,d) \in A with 6d=4c6d = 4c, i.e. 3d=2c3d = 2c, i.e. c/d=3/2c/d = 3/2 in lowest terms. So

[(6,4)]={(3,2),(6,4),(−3,−2),(9,6),(−9,−6),(12,8),…}={(3k,2k):k∈Z,k≠0}.[(6,4)] = \{(3,2), (6,4), (-3,-2), (9,6), (-9,-6), (12, 8), \ldots\} = \{(3k, 2k) : k \in \mathbb{Z}, k \neq 0\}.

This infinite set of pairs is exactly the equivalence class that we call the rational number 3/23/2. The quotient set A/ ⁣∼A/\!\sim is, by definition in the standard construction, the set Q\mathbb{Q} of rational numbers — each fraction is literally an equivalence class of pairs. The theorem guarantees that this quotient set, viewed as a collection of classes, genuinely partitions AA: every pair (a,b)(a,b) lands in exactly one such class, with no pair belonging to two different "fractions" and no pair left over. This is the first hint of the general theme of Quotient Sets: interesting new objects (rationals, cosets, quotient groups) are frequently defined as equivalence classes of more primitive data.

CounterexampleWhy transitivity cannot be dropped

The theorem requires ∼\sim to be reflexive, symmetric, and transitive. We show that dropping transitivity alone already destroys the disjointness of the "classes," so that Φ(∼)\Phi(\sim) need not be a partition at all. Let A={1,2,3}A = \{1, 2, 3\} and define RR by:

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

Check reflexivity: (1,1),(2,2),(3,3)∈R(1,1), (2,2), (3,3) \in R. ✓. Check symmetry: (1,2)(1,2) and (2,1)(2,1) both present; (2,3)(2,3) and (3,2)(3,2) both present. ✓. Check transitivity: we need, for instance, that 1R21 \mathrel{R} 2 and 2R32 \mathrel{R} 3 force 1R31 \mathrel{R} 3. But (1,3)∉R(1,3) \notin R. So RR is not transitive — this is the only axiom that fails. Now compute the "classes" using the same formula [a]={x∈A:xRa}[a] = \{x \in A : x R a\}:

[1]={1,2},[2]={1,2,3},[3]={2,3}.[1] = \{1, 2\}, \qquad [2] = \{1, 2, 3\}, \qquad [3] = \{2, 3\}.

These are not the blocks of a partition: [1]∩[3]={2}≠∅[1] \cap [3] = \{2\} \neq \varnothing, yet [1]≠[3][1] \neq [3]. Axiom 2 (pairwise disjointness) fails outright, even though every "class" is nonempty and their union is all of AA (axioms 1 and 3 survive). The proof of Part (I) breaks exactly where expected: the disjointness argument used transitivity essentially — given z∈[a]∩[b]z \in [a]\cap[b], we derived a∼ba \sim b via a∼z∼ba \sim z \sim b using transitivity, and it is precisely that step that is unavailable here. Without it, classes can genuinely overlap without being equal, and Φ(∼)\Phi(\sim) fails to be a partition. This shows transitivity is not a decorative hypothesis: it is exactly what forces "overlapping classes" to collapse into "identical classes."

Scope, edge cases & common traps

SituationWhat happens
A=∅A = \varnothingThe unique relation ∅⊆∅×∅\varnothing \subseteq \varnothing \times \varnothing is (vacuously) an equivalence relation, and the unique partition of ∅\varnothing is P=∅\mathcal{P} = \varnothing (the empty collection of blocks). The correspondence holds trivially.
∼\sim is equality (==)Every class is a singleton [a]={a}[a] = \{a\}; the induced partition is the finest possible one, "all singletons."
∼\sim relates everything to everything (A×AA \times A)There is exactly one class, [a]=A[a] = A for every aa; the induced partition is the coarsest one, {A}\{A\} itself (assuming A≠∅A \neq \varnothing).
AA infiniteClasses may be infinite (Example 1) or the quotient set may be infinite (Example 2); the theorem makes no finiteness assumption anywhere in its proof.
Confusing "block of a partition" with "equivalence class"These are literally the same objects under the correspondence, but only once P=Φ(∼)\mathcal P = \Phi(\sim) or ∼=Ψ(P)\sim = \Psi(\mathcal P) — an arbitrary collection of disjoint sets that fails to cover AA, or a random equivalence-like relation missing an axiom, breaks the identification (see the counterexample).

The mathematician behind it

Origins · 1 minRichard Dedekind and how this was discovered
RD
Richard Dedekind
1831–1916 · Foundations of arithmetic and set theory, late 19th-century Germany

Richard Dedekind, working alongside Georg Cantor in the formative decades of set theory, was among the first to treat equivalence and quotient constructions with full rigor — most famously in his construction of the real numbers via Dedekind cuts, and in his systematic use of "sameness up to a relation" to build new number systems out of old ones. The general theorem connecting equivalence relations to partitions, though folklore by the early 20th century and formalized repeatedly in the development of abstract algebra (compare cosets and quotient groups) and mathematical logic, crystallizes the technique Dedekind pioneered: define new mathematical objects not by exhibiting them directly, but as equivalence classes of more concrete data subject to a relation capturing exactly the intended notion of "essentially the same."

History
- 1872 — Dedekind publishes his construction of the real numbers via cuts of rationals, an early rigorous quotient-style construction.
- 1888 — Dedekind's Was sind und was sollen die Zahlen? develops set-theoretic foundations including systematic use of equivalence and mapping.
- 1895–1897 — Cantor's foundational papers on set theory formalize the language of sets, relations, and mappings in which the modern statement of the theorem is phrased.
- 1930s — The Bourbaki school and contemporaries standardize the modern axiomatic definitions of equivalence relation and partition used in this article.
- 1958 — Halmos's Naive Set Theory fixes the now-standard undergraduate exposition of equivalence classes and the partition correspondence.
What exactly is the difference between an equivalence class and a partition?

An equivalence class is a single subset of AA — the set of all elements related to some fixed aa. A partition is the entire collection of such subsets, one for each "type" of element, arranged so they are disjoint and cover AA. So [a][a] is one block; A/ ⁣∼={[a]:a∈A}A/\!\sim = \{[a] : a \in A\} is the whole partition. Every equivalence relation produces one partition (all its classes together), and conversely every partition can be read off as the class structure of some equivalence relation, by the Fundamental Theorem proved above.

Why do we need all three axioms — reflexivity, symmetry, transitivity — and not just one or two?

Each axiom does distinct work in the proof. Reflexivity guarantees every aa lies in its own class [a][a], which forces classes to be nonempty and to cover AA. Symmetry and transitivity together are exactly what force the Lemma a∼b  ⟺  [a]=[b]a \sim b \iff [a] = [b], which in turn forces classes that overlap at all to be identical, giving disjointness. The counterexample above shows a reflexive, symmetric relation lacking transitivity whose "classes" genuinely overlap without being equal — so transitivity cannot be dropped, and by symmetric reasoning neither can the other two.

Can two different equivalence relations induce the same partition?

No. Part (III) of the theorem shows Φ\Phi is a bijection, so it is in particular injective: distinct equivalence relations always induce distinct partitions. If you ever find Φ(∼1)=Φ(∼2)\Phi(\sim_1) = \Phi(\sim_2) as partitions, then in fact ∼1\sim_1 and ∼2\sim_2 must be the identical relation, since Ψ(Φ(∼1))=∼1\Psi(\Phi(\sim_1)) = \sim_1 and Ψ(Φ(∼2))=∼2\Psi(\Phi(\sim_2)) = \sim_2 by Claim 1, and applying Ψ\Psi to equal partitions gives equal outputs.

Is the empty set ever an equivalence class?

No, never — an equivalence class [a][a] always contains at least aa itself, by reflexivity (a∼aa \sim a). This is exactly axiom 1 of a partition ("nonempty blocks"), and it is why the proof of Part (I) explicitly invokes reflexivity to rule out empty classes. If you ever compute a "class" and get ∅\varnothing, either the relation is not reflexive or an arithmetic error occurred.

How does this theorem relate to the idea of a quotient set used elsewhere in mathematics, like quotient groups?

The quotient set A/ ⁣∼A/\!\sim constructed here is the general set-theoretic template. Quotient groups G/HG/H, quotient rings R/IR/I, and quotient vector spaces V/WV/W are all special cases: one first defines an equivalence relation encoding "differ by an element of HH (or II, or WW)," confirms it is an equivalence relation, and then the Fundamental Theorem guarantees the classes genuinely partition the ambient set — a prerequisite for the group/ring/vector-space operations to even be sensibly defined on the classes. The deeper question of whether operations defined on representatives are actually well-defined on classes is the subject of Quotient Sets and Well-Definedness.

Does this correspondence require AA to be finite?

No. Nothing in the statement or the proof assumes finiteness; AA can be any set, including infinite ones, as both worked examples (integers under congruence, and pairs of integers modulo cross-multiplication) demonstrate. Finiteness is irrelevant to the logical structure of the argument, which is purely about membership, reflexivity, symmetry, and transitivity — properties that make sense for sets of any cardinality, a theme that continues into the study of Cardinality.

If I only check that classes are pairwise disjoint and cover AA, have I verified ∼\sim is an equivalence relation?

Not directly — pairwise disjointness and covering are properties of the partition you get out, not axioms you check on ∼\sim itself. To confirm ∼\sim is an equivalence relation you must verify reflexivity, symmetry, and transitivity directly from its definition, as in both worked examples. The payoff of the theorem is that once you've done that, the disjoint-covering structure of A/ ⁣∼A/\!\sim follows automatically — you never need to separately re-verify it by brute-force set comparison.

Before this

Where this leads