Equivalence Relations

Suppose you want to say two fractions like 12\tfrac{1}{2} and 24\tfrac{2}{4} are "the same number." This holds even though they are different symbols built from different pairs of integers. What formal property must a relation have to justify this? It must justify collapsing distinct objects into a single notion of sameness. This question — how to make precise the everyday act of sorting objects into categories of "essentially equal" — is answered by the concept of an equivalence relation. Equivalence relations are the mathematical backbone of the idea of classification. Whenever we say two things are "congruent," "isomorphic," "parallel," "the same modulo nn," or "interchangeable for the purposes at hand," we are implicitly invoking a relation with three specific properties. Those properties are reflexivity, symmetry, and transitivity. Recognizing this pattern lets us treat wildly different-looking constructions as instances of one clean, reusable structure. These include clock arithmetic, similar triangles, rational numbers as pairs of integers, and logical equivalence of formulas. The payoff of isolating this structure is enormous. Once a relation is shown to be an equivalence relation, we automatically know something important. We know it partitions its underlying set into disjoint classes. We may then treat each class as a single new object. This is precisely the mechanism behind constructing Z\mathbb{Z} from N\mathbb{N}, Q\mathbb{Q} from Z\mathbb{Z}, and countless quotient constructions throughout mathematics. This article gives the precise definition and builds intuition with pictures. It proves the fundamental theorem connecting equivalence relations to partitions. It works through two nontrivial examples. It also shows exactly what fails when one of the three defining properties is dropped. It closes by connecting the idea to its many uses across mathematics and beyond. It lightly foreshadows the theory of Equivalence Classes and Partitions built directly on top of it.

Key takeaways
  • An equivalence relation on a set AA is a relation that is reflexive, symmetric, and transitive on AA.
  • It formalizes the intuitive notion of "sameness" or "interchangeability" among elements of a set.
  • Canonical examples: equality itself, congruence mod nn, similarity of triangles, "same parity," "same remainder."
  • The central theorem: equivalence relations on AA correspond exactly to partitions of AA into nonempty disjoint blocks.
  • Dropping any one of the three properties (reflexive, symmetric, transitive) can destroy the partition structure.
  • Key idea: an equivalence relation is precisely the relational shadow of "grouping a set into categories."

Where this lives today

Equivalence relations are one of the most reused ideas in all of mathematics, precisely because "define a new kind of object by declaring certain old objects equivalent" is such a universal move.

Number systems. The integers are formally constructed as equivalence classes of pairs of natural numbers under (a,b)∼(c,d)  ⟺  a+d=b+c(a,b) \sim (c,d) \iff a + d = b + c (representing "a−ba - b"); the rationals are equivalence classes of pairs of integers under (a,b)∼(c,d)  ⟺  ad=bc(a,b) \sim (c,d) \iff ad = bc (representing "a/ba/b," which is exactly why 12=24\tfrac12 = \tfrac24). The real numbers can be built as equivalence classes of Cauchy sequences of rationals that differ by a sequence tending to 00.

Modular arithmetic and cryptography. Congruence modulo nn, worked out above, underlies clock arithmetic, check-digit schemes, and — critically — the RSA cryptosystem and other public-key algorithms, all of which compute inside the equivalence classes Z/nZ\mathbb{Z}/n\mathbb{Z}.

Abstract algebra. Quotient groups, quotient rings, and quotient vector spaces are all built by declaring elements equivalent when they differ by an element of a subgroup, ideal, or subspace; this is the equivalence-relation-to-partition machinery in disguise.

Geometry. Similarity and congruence of triangles are equivalence relations; classifying shapes "up to similarity" or "up to congruence" is literally passing to equivalence classes.

Logic. Logical equivalence of propositional formulas (P≡QP \equiv Q iff they have the same truth table) is an equivalence relation on the set of formulas, and it underlies simplification and normal-form algorithms in automated theorem proving and digital circuit design.

Computer science. Type equivalence in programming language semantics, state minimization in finite automata (Myhill–Nerode equivalence), and union-find / disjoint-set data structures are all direct algorithmic implementations of equivalence relations and their classes.

Statistics and measurement theory. Classifying data into bins, or declaring two measurements "the same" up to a tolerance in a carefully transitive way, requires exactly this structure to avoid the pathology illustrated in the counterexample above.

:::quiz[Which property, if dropped from the definition, allows an element cc to appear to belong to two different, non-identical "would-be classes" [a][a] and [b][b] with [a]∩[b]≠∅[a]\cap[b]\neq\varnothing but [a]≠[b][a]\neq[b]?]

  • Reflexivity
  • Symmetry
  • Transitivity ✓
  • None; this can never happen for any relation

Ask the tutor: Can you show me step by step how to prove that "same remainder when divided by nn" is an equivalence relation for a general modulus nn, and then list all of its equivalence classes?

DefinitionEquivalence Relation

Let AA be a set and let R⊆A×AR \subseteq A \times A be a relation on AA. We say RR is an equivalence relation on AA if RR satisfies all three of the following properties. 1. Reflexive: for every a∈Aa \in A, a R aa\,R\,a. 2. Symmetric: for all a,b∈Aa, b \in A, if a R ba\,R\,b then b R ab\,R\,a. 3. Transitive: for all a,b,c∈Aa, b, c \in A, if a R ba\,R\,b and b R cb\,R\,c then a R ca\,R\,c. When RR is an equivalence relation, it is customary to write a∼ba \sim b instead of a R ba\,R\,b, and to read a∼ba \sim b as "aa is equivalent to bb."

Intuition

Think of a large room full of people, and imagine drawing a relation a∼ba \sim b meaning "aa and bb were born in the same calendar month." This relation is reflexive (everyone shares a birth month with themselves), symmetric (if aa shares a month with bb, then bb shares that month with aa), and transitive (if aa and bb share a month, and bb and cc share a month, then all three share that month). The effect of these three properties together is that the room splits cleanly into twelve non-overlapping groups — the twelve birth months — with every person in exactly one group. This splitting is not a coincidence; it is forced by the three axioms, and it is the entire content of the theorem proved below. The key geometric picture is this: an equivalence relation is a relation whose "graph," when restricted to any subset of mutually related elements, is a complete graph with all loops present — every element in a class points to itself and to every other class member, and to nothing outside the class. Symmetry means arrows are two-directional; transitivity is what prevents "leakage" between what should be separate clusters; reflexivity guarantees no element is left out, isolated, or ambiguous.

Figure
A relation on a 7-point set: three clusters, each internally complete with loops, no arrows between clusters
a b c d e f class [a]=[b]=[c] class [d]=[e] class [f]

The picture shows exactly the structural signature guaranteed by an equivalence relation: the set of seven elements {a,b,c,d,e,f,…}\{a,b,c,d,e,f, \ldots\} (loops at every vertex are implicit by reflexivity but omitted for clarity) breaks into three disjoint clusters. Every pair within a cluster is joined by an edge (symmetric, and transitively closed so no edge is missing), and no edge crosses between clusters. This is the general shape of every equivalence relation on every set, no matter how large or abstract.

TheoremEquivalence Relations Correspond to Partitions

Let AA be a nonempty set.

(a) If ∼\sim is an equivalence relation on AA, then the collection of equivalence classes

[a]:={ x∈A:x∼a },a∈A,[a] := \{\, x \in A : x \sim a \,\}, \qquad a \in A,

forms a partition of AA: that is, each [a][a] is nonempty, the classes are pairwise either equal or disjoint, and ⋃a∈A[a]=A\bigcup_{a \in A} [a] = A.

(b) Conversely, if P={Bi}i∈I\mathcal{P} = \{ B_i \}_{i \in I} is a partition of AA (a collection of nonempty, pairwise disjoint subsets of AA whose union is AA), then the relation

a∼Pb  ⟺  ∃i∈I, a∈Bi and b∈Bia \sim_{\mathcal P} b \iff \exists i \in I,\ a \in B_i \text{ and } b \in B_i

is an equivalence relation on AA, and its equivalence classes are exactly the blocks BiB_i.

(c) These two constructions are mutually inverse: starting from ∼\sim, forming the partition into classes, and then forming the induced relation from that partition, recovers ∼\sim exactly; and likewise starting from a partition, forming its induced relation, and then taking equivalence classes recovers the original partition.

Proof

We prove each part in turn. The technique throughout is direct set-theoretic verification from the definitions, using the reflexive, symmetric, and transitive hypotheses exactly where needed and no more.

Part (a). Let ∼\sim be an equivalence relation on AA, and for a∈Aa \in A let [a]={x∈A:x∼a}[a] = \{x \in A : x \sim a\}. Each [a][a] is nonempty. By reflexivity, a∼aa \sim a, so a∈[a]a \in [a]. Hence [a]≠∅[a] \neq \varnothing. The union of all classes is AA. Since each [a]⊆A[a] \subseteq A by definition, ⋃a∈A[a]⊆A\bigcup_{a \in A} [a] \subseteq A. Conversely, for any a∈Aa \in A we showed a∈[a]⊆⋃a′∈A[a′]a \in [a] \subseteq \bigcup_{a' \in A}[a'], so A⊆⋃a∈A[a]A \subseteq \bigcup_{a\in A}[a]. Hence the union equals AA. Any two classes are equal or disjoint. Let a,b∈Aa, b \in A and suppose [a]∩[b]≠∅[a] \cap [b] \neq \varnothing; we show [a]=[b][a] = [b]. Choose c∈[a]∩[b]c \in [a] \cap [b], so c∼ac \sim a and c∼bc \sim b. By symmetry, a∼ca \sim c. By transitivity applied to a∼ca \sim c and c∼bc \sim b, we get a∼ba \sim b. Now let x∈[a]x \in [a] be arbitrary, so x∼ax \sim a. Since a∼ba \sim b, transitivity gives x∼bx \sim b, i.e. x∈[b]x \in [b]. This shows [a]⊆[b][a] \subseteq [b]. By the symmetric argument (swapping the roles of aa and bb, using b∼ab \sim a, which follows from a∼ba\sim b by symmetry), [b]⊆[a][b] \subseteq [a]. Hence [a]=[b][a] = [b]. We have shown: for all a,b∈Aa,b \in A, either [a]∩[b]=∅[a] \cap [b] = \varnothing or [a]=[b][a] = [b]. Combined with nonemptiness and the union condition, {[a]:a∈A}\{[a] : a \in A\} is a partition of AA.

Part (b). Let P={Bi}i∈I\mathcal P = \{B_i\}_{i \in I} be a partition of AA: the BiB_i are nonempty, pairwise disjoint, and ⋃iBi=A\bigcup_i B_i = A. Define a∼Pba \sim_{\mathcal P} b to mean aa and bb lie in a common block. Reflexive. Let a∈Aa \in A. Since ⋃iBi=A\bigcup_i B_i = A, there is some ii with a∈Bia \in B_i. Then trivially aa and aa lie in the common block BiB_i, so a∼Paa \sim_{\mathcal P} a. Symmetric. If a∼Pba \sim_{\mathcal P} b, there is ii with a,b∈Bia, b \in B_i. The statement "a,b∈Bia,b \in B_i" is symmetric in a,ba,b, so also b,a∈Bib, a \in B_i, giving b∼Pab \sim_{\mathcal P} a. Transitive. Suppose a∼Pba \sim_{\mathcal P} b and b∼Pcb \sim_{\mathcal P} c. Then there exist i,j∈Ii, j \in I with a,b∈Bia, b \in B_i and b,c∈Bjb, c \in B_j. In particular b∈Bi∩Bjb \in B_i \cap B_j, so Bi∩Bj≠∅B_i \cap B_j \neq \varnothing. Since the blocks of a partition are pairwise disjoint, distinct blocks cannot share an element; hence Bi=BjB_i = B_j. Therefore a∈Bi=Bja \in B_i = B_j and c∈Bjc \in B_j, so a,c∈Bja, c \in B_j, giving a∼Pca \sim_{\mathcal P} c. Thus ∼P\sim_{\mathcal P} is an equivalence relation. Finally we check its equivalence classes are exactly the blocks BiB_i. Fix i∈Ii \in I and a∈Bia \in B_i; we claim [a]∼P=Bi[a]_{\sim_{\mathcal P}} = B_i. If x∈Bix \in B_i, then a,x∈Bia, x \in B_i, so x∼Pax \sim_{\mathcal P} a, i.e. x∈[a]x \in [a]; this shows Bi⊆[a]B_i \subseteq [a]. Conversely if x∈[a]x \in [a], then x∼Pax \sim_{\mathcal P} a, so there is some block BjB_j containing both xx and aa; since a∈Bi∩Bja \in B_i \cap B_j and blocks are pairwise disjoint (or equal when they share a point, which for a partition of distinct labeled blocks means Bj=BiB_j = B_i), we get Bj=BiB_j = B_i, so x∈Bix \in B_i. This shows [a]⊆Bi[a] \subseteq B_i. Hence [a]=Bi[a] = B_i for every a∈Bia \in B_i, so every block is an equivalence class, and (since every element lies in some block) every equivalence class arises this way.

Part (c). Direction 1: relation →\to partition →\to relation. Start with equivalence relation ∼\sim on AA, form the partition P∼={[a]:a∈A}\mathcal{P}_\sim = \{[a] : a \in A\} from part (a), and form the induced relation ∼P∼\sim_{\mathcal{P}_\sim} from part (b). We must show ∼P∼\sim_{\mathcal{P}_\sim} equals ∼\sim as relations on AA. Suppose a∼P∼ba \sim_{\mathcal{P}_\sim} b. Then a,ba, b lie in a common block of P∼\mathcal{P}_\sim, i.e. there is c∈Ac \in A with a,b∈[c]a, b \in [c]. So a∼ca \sim c and b∼cb \sim c. By symmetry c∼bc \sim b, and by transitivity applied to a∼ca \sim c and c∼bc \sim b, we get a∼ba \sim b. Conversely suppose a∼ba \sim b. Then a∈[a]a \in [a] (by reflexivity) and b∈[a]b \in [a] (by definition of [a][a], since b∼ab \sim a follows from a∼ba \sim b by symmetry — actually directly, b∈[a]b \in [a] means b∼ab \sim a, which holds by symmetry from a∼ba\sim b). So a,ba, b both lie in block [a][a], hence a∼P∼ba \sim_{\mathcal{P}_\sim} b. This proves ∼P∼ = ∼\sim_{\mathcal{P}_\sim}\ =\ \sim. Direction 2: partition →\to relation →\to partition. Start with partition P={Bi}i∈I\mathcal P = \{B_i\}_{i\in I}, form ∼P\sim_{\mathcal P} from part (b), and form its equivalence classes. Part (b) already showed directly that the equivalence classes of ∼P\sim_{\mathcal P} are exactly the blocks BiB_i. Hence the resulting partition is P\mathcal P itself. This establishes the claimed mutual inverse correspondence, completing the proof. ■\blacksquare

∎

Worked examples

Example 1: Congruence modulo nn, with n=5n = 5. Let A=ZA = \mathbb{Z} and define a∼ba \sim b to mean 5∣(a−b)5 \mid (a - b), i.e. aa and bb leave the same remainder upon division by 55. We verify the three properties directly, and then identify the classes for a specific asymmetric set of integers. Reflexive: For any a∈Za \in \mathbb{Z}, a−a=0=5⋅0a - a = 0 = 5\cdot 0, so 5∣(a−a)5 \mid (a-a). Hence a∼aa \sim a. Symmetric: Suppose a∼ba \sim b, so a−b=5ka - b = 5k for some k∈Zk \in \mathbb{Z}. Then b−a=5(−k)b - a = 5(-k), and −k∈Z-k \in \mathbb{Z}, so 5∣(b−a)5 \mid (b-a), i.e. b∼ab \sim a. Transitive: Suppose a∼ba \sim b and b∼cb \sim c, so a−b=5ka - b = 5k and b−c=5mb - c = 5m for integers k,mk, m. Adding, a−c=(a−b)+(b−c)=5(k+m)a - c = (a-b) + (b-c) = 5(k+m), and k+m∈Zk + m \in \mathbb{Z}, so 5∣(a−c)5 \mid (a - c), i.e. a∼ca \sim c. So ∼\sim is an equivalence relation on Z\mathbb{Z}. Now let's find the class of a specific, non-obvious integer, say a=−17a = -17. We have −17=5⋅(−4)+3-17 = 5\cdot(-4) + 3 (check: 5×(−4)=−205 \times (-4) = -20, and −20+3=−17-20 + 3 = -17 ✓, with remainder 33 satisfying 0≤3<50 \le 3 < 5). So −17-17 leaves remainder 33 upon division by 55, and

[−17]={x∈Z:x≡3(mod5)}={…,−17,−12,−7,−2,3,8,13,18,…}.[-17] = \{ x \in \mathbb{Z} : x \equiv 3 \pmod 5\} = \{\ldots, -17, -12, -7, -2, 3, 8, 13, 18, \ldots\}.

Let's double check two elements are related: take x=18x = 18 and y=−12y = -12. Then x−y=30=5⋅6x - y = 30 = 5 \cdot 6, so indeed 5∣(18−(−12))5 \mid (18 - (-12)) and 18∼−1218 \sim -12, confirming both lie in the class [−17][-17]. There are exactly 55 classes total, indexed by remainder r∈{0,1,2,3,4}r \in \{0,1,2,3,4\}:

[0]=5Z,[1],[2],[3] (containing −17),[4],[0] = 5\mathbb{Z}, \quad [1], \quad [2], \quad [3] \ (\text{containing } -17), \quad [4],

and by the theorem these five sets partition Z\mathbb{Z}: they are pairwise disjoint (an integer has a unique remainder mod 5 by the division algorithm) and their union is all of Z\mathbb{Z} (every integer has some remainder mod 5).

Example 2: "Same image under a fixed non-injective function." Let A={−3,−2,−1,0,1,2,3}A = \{-3,-2,-1,0,1,2,3\} and let f:A→Zf : A \to \mathbb{Z} be f(x)=x2f(x) = x^2. Define a relation on AA by

a∼b  ⟺  f(a)=f(b).a \sim b \iff f(a) = f(b).

This is an instance of a general pattern: for any function f:A→Bf: A \to B, the relation "a∼b  ⟺  f(a)=f(b)a \sim b \iff f(a) = f(b)" is always an equivalence relation. Let's verify this in general and then compute the classes for this specific asymmetric domain. Reflexive: For any a∈Aa \in A, f(a)=f(a)f(a) = f(a) trivially (equality of a value with itself), so a∼aa \sim a. Symmetric: If a∼ba \sim b, then f(a)=f(b)f(a) = f(b). Equality of real numbers (or elements of BB) is symmetric, so f(b)=f(a)f(b) = f(a), giving b∼ab \sim a. Transitive: If a∼ba \sim b and b∼cb \sim c, then f(a)=f(b)f(a) = f(b) and f(b)=f(c)f(b) = f(c). By transitivity of equality, f(a)=f(c)f(a) = f(c), so a∼ca \sim c. So ∼\sim is an equivalence relation on AA for our specific f(x)=x2f(x) = x^2 and A={−3,…,3}A = \{-3,\dots,3\}. Compute the images: f(−3)=9f(-3) = 9, f(−2)=4f(-2) = 4, f(−1)=1f(-1) = 1, f(0)=0f(0) = 0, f(1)=1f(1) = 1, f(2)=4f(2) = 4, f(3)=9f(3) = 9. Grouping elements with equal image gives the classes

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

Check disjointness and coverage: these four sets are pairwise disjoint (a quick scan confirms no repeats among {0},{−1,1},{−2,2},{−3,3}\{0\}, \{-1,1\}, \{-2,2\}, \{-3,3\}) and their union is {−3,−2,−1,0,1,2,3}=A\{-3,-2,-1,0,1,2,3\} = A, exactly as the theorem guarantees. Note the classes have different sizes (1,2,2,21, 2, 2, 2) — nothing in the definition of equivalence relation requires classes of equal size; this asymmetry is completely typical.

CounterexampleWhy transitivity cannot be dropped

Consider A={p,q,r}A = \{p, q, r\}, the set of three people, and define the relation

R={(p,p),(q,q),(r,r),(p,q),(q,p),(q,r),(r,q)}.R = \{(p,p), (q,q), (r,r), (p,q), (q,p), (q,r), (r,q)\}.

Read x R yx\,R\,y as "xx and yy have met and gotten along." Let's check reflexivity and symmetry directly from the list. Reflexive: (p,p),(q,q),(r,r)∈R(p,p), (q,q), (r,r) \in R, so every element is related to itself. ✓. Symmetric: The pairs (p,q)(p,q) and (q,p)(q,p) both appear; the pairs (q,r)(q,r) and (r,q)(r,q) both appear. Every ordered pair in RR has its reverse also in RR. ✓. Transitive? We have p R qp\,R\,q and q R rq\,R\,r. If RR were transitive we would need p R rp\,R\,r. But (p,r)∉R(p,r) \notin R (we can scan the list of six ordered pairs above: it contains no (p,r)(p,r) and no (r,p)(r,p)). So transitivity fails. Because transitivity fails, RR is not an equivalence relation, and correspondingly the "would-be classes" fail to form a partition. If we try to define [p]={x:x R p}={p,q}[p] = \{x : x\,R\,p\} = \{p, q\} and [r]={x:x R r}={q,r}[r] = \{x : x\,R\,r\} = \{q, r\}, these two sets are neither equal nor disjoint — they overlap in exactly {q}\{q\} without being identical, which is precisely the pathology the theorem's proof rules out using transitivity. Concretely, qq "belongs" both to pp's group and to rr's group, while pp and rr themselves are not linked at all — there is no consistent way to sort {p,q,r}\{p,q,r\} into disjoint clusters using RR. This is exactly the scenario transitivity is designed to prevent: without it, "sameness" fails to be a coherent, well-defined notion of grouping.

Scope, edge cases & common traps

SituationWhat to checkCommon pitfall
Relation defined by a formula (e.g. a∼b  ⟺  ∣a−b∣<εa\sim b \iff \lvert a-b\rvert < \varepsilon)Test transitivity carefully — "closeness" relations often fail itAssuming "looks symmetric and reflexive" is enough; forgetting transitivity
Relation on an infinite set (e.g. Z,R\mathbb{Z}, \mathbb{R})Reflexivity, symmetry, transitivity must hold for all elements, not just checked examplesVerifying only a few sample pairs instead of a general argument
Relation defined via a function (a∼b  ⟺  f(a)=f(b)a \sim b \iff f(a)=f(b))Always an equivalence relation, for any function ffConfusing this with ff being injective (not needed at all)
Empty relation on nonempty AAReflexivity fails immediately unless A=∅A = \varnothingThinking "no pairs related" is vacuously fine; it violates reflexivity whenever A≠∅A\neq\varnothing
Equivalence relation on the empty set A=∅A=\varnothingR=∅⊆∅×∅R = \varnothing \subseteq \varnothing\times\varnothing is (vacuously) reflexive, symmetric, transitiveOverlooking that all three conditions are vacuously true, so ∅\varnothing does have (exactly one) equivalence relation on it
"Partial order" vs "equivalence relation"Both need reflexive + transitive; the difference is antisymmetry vs. symmetryConfusing ≤\le (order) with ∼\sim (equivalence) since both are reflexive & transitive

The mathematician behind it

The abstract formulation of equivalence relations, as a triple of axioms isolated for their own sake, crystallized gradually through the development of modern algebra and set theory in the 19th and early 20th centuries — it does not trace to one single inventor the way, say, a named theorem often does. But the figure most associated with codifying the equivalence-class method into a general foundational tool for constructing new mathematical objects (integers from naturals, rationals from integers, real numbers from Cauchy sequences) is Richard Dedekind, whose work on the foundations of number systems made "define a new object as an equivalence class of old ones" a standard, rigorous technique.

Origins · 1 minRichard Dedekind and how this was discovered
RD
Richard Dedekind
1831–1916 · Foundations of arithmetic and abstract algebra, Braunschweig and Göttingen

Richard Dedekind was a German mathematician who studied under Gauss and worked closely with the ideas of Dirichlet and Riemann. He is best known for his rigorous construction of the real numbers via Dedekind cuts, his foundational work on ideals in ring theory, and his insistence — radical for his time — that mathematical objects like numbers should be defined rigorously from more primitive set-theoretic notions rather than taken as intuitively given. His 1888 essay Was sind und was sollen die Zahlen? ("What are numbers and what should they be?") is a landmark in using set-theoretic equivalence and partition ideas to build up the number systems from first principles.

History
- 1831 — Richard Dedekind born in Braunschweig, in the Duchy of Brunswick.
- 1858 — Dedekind develops his construction of the real numbers via cuts, later published in 1872.
- 1871 — Dedekind introduces the modern definition of an ideal in ring theory, an equivalence-class-flavored organizing idea.
- 1888 — Dedekind publishes Was sind und was sollen die Zahlen?, formalizing set-based constructions of number systems.
- 1908–1922 — Zermelo–Fraenkel axiomatization of set theory provides the rigorous backdrop in which "equivalence relation" and "partition" become fully precise, general-purpose tools usable in any set.
Is every reflexive and symmetric relation automatically transitive?

No. Reflexivity and symmetry are independent of transitivity, and there are many relations satisfying the first two but not the third. A standard example is "aa and bb differ by less than 11" on R\mathbb{R}: it is reflexive (∣a−a∣=0<1|a-a|=0<1) and symmetric (∣a−b∣=∣b−a∣|a-b|=|b-a|), but not transitive, since 00 is close to 0.90.9 and 0.90.9 is close to 1.81.8, yet 00 and 1.81.8 differ by 1.8≥11.8 \ge 1. The counterexample block above gives a finite analogue with three people. All three properties must be checked independently and explicitly.

Why does an equivalence relation always produce a partition rather than some messier overlapping structure?

This is exactly the content of the central theorem proved above. The key step uses transitivity (together with symmetry) to show that if two equivalence classes share even a single element, they must be entirely equal, not just partially overlapping. Reflexivity guarantees every element lands in some class (namely its own). Together these three properties leave no room for classes to partially overlap, which is precisely why the classes tile the whole set into disjoint, exhaustive blocks — a genuine partition.

Can a set have more than one equivalence relation on it?

Yes, almost always, unless the set is empty or a singleton. Any set AA with ∣A∣≥2|A|\ge 2 admits at least two equivalence relations: the finest one, equality itself (a∼b  ⟺  a=ba\sim b \iff a=b, giving singleton classes), and the coarsest one, the "universal" relation relating every element to every other (a∼ba \sim b always true, giving a single class equal to all of AA). In general, the number of distinct equivalence relations on a finite set of size nn equals the number of partitions of an nn-element set, counted by the Bell numbers.

Is "logical equivalence" of statements really an equivalence relation in this technical sense?

Yes. Define P∼QP \sim Q to mean PP and QQ have identical truth tables (equivalently, P↔QP \leftrightarrow Q is a tautology). Reflexivity holds since any formula trivially has the same truth table as itself. Symmetry holds since "same truth table" is a symmetric condition on the pair. Transitivity holds since if P,QP,Q share a truth table and Q,RQ,R share a truth table, then PP and RR share that same truth table. So logical equivalence is a genuine equivalence relation on the set of propositional formulas, and its equivalence classes correspond exactly to distinct truth-table patterns (Boolean functions).

Does every function f:A→Bf: A \to B give rise to an equivalence relation on AA, even if ff is not injective or surjective?

Yes, always, and injectivity/surjectivity of ff are irrelevant to this fact. Define a∼b  ⟺  f(a)=f(b)a \sim b \iff f(a) = f(b). Reflexivity, symmetry, and transitivity of ∼\sim follow immediately from reflexivity, symmetry, and transitivity of ordinary equality in the codomain BB, as shown in Worked Example 2. If ff happens to be injective, every equivalence class is a singleton, recovering plain equality on AA; if ff collapses many elements together, the classes can be large. This construction — sometimes called the kernel of ff — is one of the most common sources of equivalence relations in practice.

How is an equivalence relation different from a partial order?

Both require reflexivity and transitivity, but they differ in the third axiom: an equivalence relation requires symmetry (if a∼ba\sim b then b∼ab \sim a), while a partial order requires antisymmetry (if a≤ba \le b and b≤ab \le a then a=ba = b). These are essentially opposite conditions when a≠ba \ne b: symmetry insists related distinct elements point both ways, antisymmetry forbids it. This is why equivalence relations produce "clusters of interchangeable elements" while partial orders produce "rankings" or "hierarchies," covered separately under Partial Orders.

Why do we care about equivalence classes at all, rather than just using the relation directly?

Working directly with a relation can be cumbersome because it constantly requires re-checking whether two elements are related. Passing to equivalence classes lets us treat "being equivalent" as literal set-theoretic equality of a new object (the class), which is often far easier to manipulate — this is exactly how Z\mathbb{Z}, Q\mathbb{Q}, and quotient groups are built. The theorem above guarantees this passage is always legitimate: every equivalence relation gives rise to a genuine partition, so grouping elements into classes never loses information or creates ambiguity. This transition is developed fully in Equivalence Classes and Partitions.

Before this

Where this leads