Equivalence relations and partitions

Theorem

Equivalence relations and partitions

T-137Home MU-101Threads logic · structure

Statement

Let \( X \) be a set. An equivalence relation on \( X \) is a relation that is reflexive, symmetric and transitive; a partition of \( X \) is a set of non-empty, pairwise disjoint subsets whose union is the whole of \( X \). Written out, \( {\sim} \subseteq X \times X \) is an equivalence relation when it is reflexive (\( x \sim x \) for all \( x \in X \)), symmetric (\( x \sim y \Longrightarrow y \sim x \)) and transitive (\( x \sim y \) and \( y \sim z \Longrightarrow x \sim z \)), and \( \mathcal{P} \) is a partition when \( \varnothing \notin \mathcal{P} \), distinct members of \( \mathcal{P} \) are disjoint, and \( \bigcup \mathcal{P} = X \). Write \( [x] = \{\, y \in X : y \sim x \,\} \) for the class of \( x \) and \( X/{\sim} = \{\, [x] : x \in X \,\} \). Then: (i) \( X/{\sim} \) is a partition of \( X \); (ii) every partition \( \mathcal{P} \) arises this way, from the relation \( x \sim_{\mathcal{P}} y \iff \) some block of \( \mathcal{P} \) contains both \( x \) and \( y \), which is an equivalence relation; and (iii) the two constructions are mutually inverse, so \( \sim \, \mapsto X/{\sim} \) is a bijection from the set of equivalence relations on \( X \) onto the set of partitions of \( X \). All three axioms and the non-emptiness of blocks are needed.

Why it matters

Almost every construction in mathematics that produces a new object out of an old one is a quotient, and every quotient is this theorem in disguise. The integers modulo \( n \), the rationals as ordered pairs of integers, the reals as Cauchy sequences, quotient groups by a normal subgroup, quotient vector spaces, \( L^p \) spaces of functions identified almost everywhere, homotopy classes of loops, orbit spaces of group actions, the vertices of a graph collapsed by connectivity — each is built by declaring which elements are to be treated as the same and then working with the classes. The theorem says that “declaring elements the same” is a coherent operation exactly when the declaration is reflexive, symmetric and transitive, and that the result is always a clean partition with no overlaps and no leftovers.

It also fixes the vocabulary in both directions. Given a relation, it tells you the classes exist and are disjoint, so “pick a representative” makes sense. Given a partition — a filing system, a set of buckets, a classification — it tells you that “in the same bucket” is automatically an equivalence relation, so classification schemes and equivalence relations are the same data written two ways. The practical consequence is the well-definedness discipline that dominates algebra: to define a function on \( X/{\sim} \) you define it on \( X \) and check that equivalent inputs give equal outputs.

Hypotheses

Reflexivity: \( x \sim x \) for every \( x \in X \).Without it a class can be empty and the classes need not cover \( X \). On \( X = \{1,2,3\} \) the relation \( R = \{(1,1),(1,2),(2,1),(2,2)\} \) is symmetric and transitive but \( 3 \not\sim 3 \); then \( [3] = \varnothing \), so \( \{[1],[2],[3]\} \) contains the empty set and \( 3 \) belongs to no non-empty class. The empty relation on any non-empty \( X \) is the extreme case: symmetric and transitive vacuously, yet every class is empty.

Symmetry: \( x \sim y \Longrightarrow y \sim x \).Without it classes overlap without coinciding. Take \( {\le} \) on \( X = \{1,2,3\} \), which is reflexive and transitive. Then \( [1] = \{1\} \), \( [2] = \{1,2\} \), \( [3] = \{1,2,3\} \): these three sets are neither equal nor disjoint, so they are not a partition. Reflexive and transitive relations are preorders, and their quotient needs the extra step of collapsing \( x \le y \le x \).

Transitivity: \( x \sim y \) and \( y \sim z \Longrightarrow x \sim z \).Without it the “classes” overlap. On \( \mathbb{Z} \) put \( a \sim b \iff \lvert a - b \rvert \le 1 \), which is reflexive and symmetric. Then \( [0] = \{-1,0,1\} \) and \( [1] = \{0,1,2\} \) meet in \( \{0,1\} \) but differ, so no partition results. This is the failure mode of every “agrees to within a tolerance” relation.

Every block of a partition is non-empty.If \( \varnothing \) were allowed as a block, \( \mathcal{P} \) and \( \mathcal{P} \cup \{\varnothing\} \) would induce the identical relation \( \sim_{\mathcal{P}} \), so \( \mathcal{P} \mapsto {\sim_{\mathcal{P}}} \) would not be injective; equivalently, no equivalence relation would have \( \mathcal{P} \cup \{\varnothing\} \) as its set of classes, so the correspondence in (iii) would be an injection that is not onto.

\( X \) is a set, not a proper class.For “\( G \) is isomorphic to \( H \)” on all groups, each class is a proper class, so \( X/{\sim} \) cannot be formed in \( \mathsf{ZF} \) by comprehension. The standard repair is Scott's trick: replace \( [x] \) by the sub-collection of its members of least von Neumann rank, which is a set, and prove the modified classes still partition the domain. The bijection (iii) is a theorem about sets and needs this rewriting before it can even be stated for class-sized domains.

Proof

Fix a set \( X \). Write \( \operatorname{Eq}(X) \) for the collection of equivalence relations on \( X \) and \( \operatorname{Part}(X) \) for the collection of partitions of \( X \). Define \( \Phi(\sim) = X/{\sim} \) and \( \Psi(\mathcal{P}) = {\sim_{\mathcal{P}}} \). Steps 1–5 prove (i), Step 6 proves (ii), Steps 7–9 prove (iii).

\[ [x] = \{\, y \in X : y \sim x \,\} \subseteq X, \qquad x \in [x] \quad \text{for every } x \in X . \]

The class is a legitimate subset by separation applied to the predicate \( y \sim x \). Membership \( x \in [x] \) is exactly reflexivity, so no class is empty and \( \bigcup_{x \in X} [x] = X \): the classes already cover \( X \). A

\[ y \sim x \;\Longrightarrow\; [y] \subseteq [x] . \]

Let \( z \in [y] \), i.e. \( z \sim y \). With \( y \sim x \), transitivity gives \( z \sim x \), i.e. \( z \in [x] \). Only transitivity is used here. A

\[ y \sim x \;\Longrightarrow\; [y] = [x] . \]

Symmetry turns \( y \sim x \) into \( x \sim y \); Step 2 applied to each of the two gives \( [y] \subseteq [x] \) and \( [x] \subseteq [y] \), and mutual inclusion is equality. This is the step where symmetry earns its place: without it only one inclusion survives. B

\[ [x] \cap [y] \neq \varnothing \;\Longrightarrow\; [x] = [y] . \]

Pick \( z \in [x] \cap [y] \). Then \( z \sim x \) and \( z \sim y \), so Step 3 gives \( [z] = [x] \) and \( [z] = [y] \), hence \( [x] = [y] \). Contrapositively, two distinct classes are disjoint — there is no partial overlap. B

\[ X/{\sim} \in \operatorname{Part}(X): \quad \varnothing \notin X/{\sim}, \qquad B \neq B' \in X/{\sim} \Longrightarrow B \cap B' = \varnothing, \qquad \bigcup_{B \in X/{\sim}} B = X . \]

Non-emptiness and covering are Step 1; pairwise disjointness is Step 4. The three bullet points are exactly the definition of a partition, so (i) is proved. A

Let \( \mathcal{P} \) be a partition. Each \( x \in X \) lies in exactly one block, so \( B \colon X \to \mathcal{P} \), \( B(x) = \) the block containing \( x \), is a function, and \[ x \sim_{\mathcal{P}} y \iff B(x) = B(y) . \]

Existence of a block containing \( x \) is the covering condition; uniqueness is pairwise disjointness — two blocks containing \( x \) would meet, hence coincide. So \( B \) is total and single-valued. If \( x, y \) share a block \( C \) then \( C = B(x) \) and \( C = B(y) \) by that uniqueness, giving the displayed equivalence. Since \( \sim_{\mathcal{P}} \) is the pullback along \( B \) of equality on \( \mathcal{P} \), and equality is reflexive, symmetric and transitive, so is \( \sim_{\mathcal{P}} \). This proves (ii). B

\[ \Psi\bigl(\Phi(\sim)\bigr) = {\sim} \qquad \text{for every } {\sim} \in \operatorname{Eq}(X) . \]

Unwinding, \( (x,y) \in \Psi(\Phi(\sim)) \) means some class contains both \( x \) and \( y \). If \( x \sim y \) then \( [x] \) is such a class, by Step 1 and Step 3. Conversely if \( x, y \in [z] \) then \( x \sim z \) and \( y \sim z \), so symmetry and transitivity give \( x \sim y \). The two relations have the same pairs, hence are equal as subsets of \( X \times X \). B

\[ \Phi\bigl(\Psi(\mathcal{P})\bigr) = \mathcal{P} \qquad \text{for every } \mathcal{P} \in \operatorname{Part}(X) . \]

Write \( \sim \) for \( \sim_{\mathcal{P}} \). By Step 6, \( [x] = \{\, y : B(y) = B(x) \,\} = B(x) \), so every \( \sim \)-class is a block: \( \Phi(\Psi(\mathcal{P})) \subseteq \mathcal{P} \). Conversely let \( C \in \mathcal{P} \); since blocks are non-empty, choose \( x \in C \) — a single choice from one non-empty set, so no form of the axiom of choice is used — and then \( C = B(x) = [x] \), giving \( \mathcal{P} \subseteq \Phi(\Psi(\mathcal{P})) \). This is the one place where the non-emptiness of blocks is indispensable. C

\[ \Phi \colon \operatorname{Eq}(X) \to \operatorname{Part}(X) \quad \text{is a bijection, with } \Phi^{-1} = \Psi . \]

Steps 5 and 6 say \( \Phi \) and \( \Psi \) land in the stated codomains; Steps 7 and 8 say \( \Psi \circ \Phi = \mathrm{id} \) and \( \Phi \circ \Psi = \mathrm{id} \). A map with a two-sided inverse is a bijection, and the inverse is unique. \( \blacksquare \) A

Result

\[ \operatorname{Eq}(X) \;\xrightarrow[\ \ \Psi\ \ ]{\ \ \Phi\ \ }\; \operatorname{Part}(X), \qquad \Phi(\sim) = \bigl\{\, [x] : x \in X \,\bigr\}, \qquad \Psi(\mathcal{P}) = \bigl\{\, (x,y) : \exists\, B \in \mathcal{P},\ x,y \in B \,\bigr\}, \qquad \Psi \circ \Phi = \mathrm{id}, \quad \Phi \circ \Psi = \mathrm{id} \]

Reading. An equivalence relation and a partition are two notations for one thing. Reflexivity makes the classes non-empty and covering, transitivity plus symmetry makes them disjoint, and nothing else is needed; conversely “lies in the same block” is automatically an equivalence relation.

Scope. Any set \( X \), including \( X = \varnothing \) (one equivalence relation, the empty one; one partition, \( \varnothing \) itself — the empty family of blocks). It says nothing about relations lacking one of the three axioms, nothing about how many classes there are, and nothing about the sizes of the classes, which may all differ.

Corollaries & converses

Three equivalent tests. For an equivalence relation, \( x \sim y \iff [x] = [y] \iff [x] \cap [y] \neq \varnothing \). The last is the useful one in practice: exhibit a single common element and the classes coincide.
Quotient map. \( q \colon X \to X/{\sim} \), \( q(x) = [x] \), is surjective and its fibres are exactly the classes: \( q^{-1}([x]) = [x] \). Conversely, every surjection \( g \colon X \to Z \) has fibres forming a partition, so partitions of \( X \) are surjections out of \( X \) up to a bijection of the target.
Universal property. If \( f \colon X \to Y \) satisfies \( x \sim y \Longrightarrow f(x) = f(y) \), there is a unique \( \bar{f} \colon X/{\sim} \to Y \) with \( f = \bar{f} \circ q \), namely \( \bar{f}([x]) = f(x) \). This is the formal content of “check it is well defined on representatives”.
Kernel of a function. For any \( f \colon X \to Y \), the relation \( x \sim_f y \iff f(x) = f(y) \) is an equivalence relation, and \( \bar{f} \colon X/{\sim_f} \to f(X) \) is a bijection. Every equivalence relation is of this form, with \( f = q \).
Counting. If \( X \) is finite then \( \lvert X \rvert = \sum_{B \in \mathcal{P}} \lvert B \rvert \), and the number of equivalence relations on an \( n \)-element set is the Bell number \( \mathrm{B}_n \): \( 1, 1, 2, 5, 15, 52, 203, 877 \) for \( n = 0, 1, \dots, 7 \), with \( \mathrm{B}_n = \sum_{k=0}^{n} S(n,k) \) where \( S(n,k) \) counts the partitions into exactly \( k \) blocks.
Closure under intersection. An arbitrary non-empty intersection of equivalence relations on \( X \) is again one, so every relation \( R \subseteq X \times X \) is contained in a smallest equivalence relation \( \langle R \rangle \), the intersection of all those containing \( R \). Unions are not closed (Problem 2).
Refinement order. \( {\sim_1} \subseteq {\sim_2} \) as sets of pairs exactly when every \( \sim_1 \)-class is contained in a \( \sim_2 \)-class. Under this order \( \operatorname{Part}(X) \) is a complete lattice, with least element the discrete partition \( \{\{x\} : x \in X\} \) and greatest element \( \{X\} \) when \( X \neq \varnothing \).
Converse of the axioms fails one at a time. Each of reflexivity, symmetry and transitivity is independent of the other two: the empty relation on a non-empty set is symmetric and transitive only, \( {\le} \) is reflexive and transitive only, and \( \lvert a-b \rvert \le 1 \) is reflexive and symmetric only.

Fails without

Reflexivity dropped: on \( X = \{1,2,3\} \) the relation \( \{(1,1),(1,2),(2,1),(2,2)\} \) is symmetric and transitive, but \( [3] = \varnothing \). The classes do not cover \( X \), so \( X/{\sim} \) is not a partition and no quotient of \( X \) is produced. The popular “proof” that symmetry and transitivity imply reflexivity — \( x \sim y \Longrightarrow y \sim x \Longrightarrow x \sim x \) — silently assumes that some \( y \) with \( x \sim y \) exists, which is false at \( x = 3 \).
Symmetry dropped: \( {\le} \) on \( \{1,2,3\} \) is reflexive and transitive, yet \( [1] = \{1\} \subsetneq [2] = \{1,2\} \subsetneq [3] = \{1,2,3\} \). The classes are nested, not disjoint, and the map \( x \mapsto [x] \) is injective rather than a collapse: the “quotient” loses no information at all.
Transitivity dropped: on \( \mathbb{Z} \) with \( a \sim b \iff \lvert a - b \rvert \le 1 \), the classes \( [0] = \{-1,0,1\} \) and \( [1] = \{0,1,2\} \) overlap in two elements and differ. Every measurement-tolerance relation (“the masses agree to within \( 0.30\ \mathrm{g} \)”) has this defect: chains of small differences accumulate into large ones, as Example 2 shows numerically.
Empty blocks admitted: if \( \varnothing \) counts as a block, then \( \mathcal{P} = \{\{1\},\{2\}\} \) and \( \mathcal{P}' = \{\{1\},\{2\},\varnothing\} \) induce the same relation on \( \{1,2\} \), so \( \Psi \) is no longer injective and Step 8 breaks: \( \Phi(\Psi(\mathcal{P}')) = \mathcal{P} \neq \mathcal{P}' \).
Domain a proper class: for isomorphism of groups the classes are proper classes and \( X/{\sim} \) does not exist as a set. Category theory handles this with skeleta or Grothendieck universes rather than by forming the quotient.

Common errors

“Symmetry and transitivity give reflexivity, so only two axioms are needed.” The argument needs a partner \( y \) with \( x \sim y \) for the chosen \( x \), and an element related to nothing has none. Reflexivity is exactly the assertion that no element is isolated.
“Define \( f \) on classes by picking a representative.” Legal only after checking that the value does not depend on the choice. On \( \mathbb{Z} \times \mathbb{Z}_{\neq 0} \) with \( (a,b) \sim (c,d) \iff ad = bc \), the rule \( f([a,b]) = a + b \) is not legitimate: \( (1,2) \sim (2,4) \) but \( 1 + 2 = 3 \neq 6 = 2 + 4 \).
Confusing levels: \( x \in X \), \( [x] \subseteq X \), \( [x] \in X/{\sim} \), \( X/{\sim} \subseteq \mathcal{P}(X) \). Writing \( [x] \in X \) or \( x \in X/{\sim} \) is a type error that quickly produces nonsense in proofs about quotients.
“All classes have the same size.” True for cosets of a subgroup, false in general: congruence modulo \( 3 \) on \( \{1,\dots,10\} \) has classes of sizes \( 4, 3, 3 \).
“The union of two equivalence relations is an equivalence relation.” It is reflexive and symmetric but rarely transitive; the correct object is the equivalence relation generated by the union, obtained by taking transitive closure.
“Having a common factor greater than \( 1 \) partitions the integers.” On \( \{2,3,\dots\} \) this relation is reflexive and symmetric, but \( 2 \sim 6 \) and \( 6 \sim 3 \) while \( 2 \not\sim 3 \). Sharing some feature is not transitive unless the feature is the value of a function.
Confusing a partition with a labelling of its blocks. Two partitions are equal as sets of blocks; relabelling the blocks (renaming buckets) changes nothing. Conversely, two surjections with the same fibres are the same partition but need not be the same function.

Discussion

The prototype is Gauss's congruence notation \( a \equiv b \pmod{n} \), introduced in the Disquisitiones Arithmeticae of 1801, which made “same remainder” into an object one could calculate with. The general axioms were isolated much later, as nineteenth-century algebra accumulated constructions — cosets, ideals, ordered pairs of integers standing for fractions, Cauchy sequences standing for reals — that all had the same shape: an auxiliary set, a rule saying which of its elements represent the same thing, and a proof that the rule respects the operations. The theorem above is the abstraction of that shape, and the reason the modern definition of “quotient” needs no further hypotheses.

The two directions of the bijection get used very differently. Passing from a relation to a partition is how one builds: define \( \mathbb{Q} \) as \( (\mathbb{Z} \times \mathbb{Z}_{\neq 0})/{\sim} \), define \( \mathbb{Z}/n\mathbb{Z} \), define homotopy classes. Passing from a partition to a relation is how one classifies: a filing system, a taxonomy, a set of buckets in a hash table, the connected components of a graph. The theorem guarantees that a classification scheme with no overlaps and no omissions can always be described by a two-place test, and conversely, which is why database keys, type systems and equality testing in programming languages all bottom out in the same three axioms.

Counting partitions is a subject in itself. The number of partitions of an \( n \)-set into exactly \( k \) non-empty blocks is the Stirling number of the second kind \( S(n,k) \), satisfying \( S(n,k) = k\,S(n-1,k) + S(n-1,k-1) \) with \( S(n,n) = S(n,1) = 1 \), and summing them over \( k \) gives the Bell number \( \mathrm{B}_n \), which also satisfies \( \mathrm{B}_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \mathrm{B}_k \). Algorithmically, the disjoint-set (“union—find”) data structure maintains a partition under merging of blocks and queries of the form “are these two elements equivalent?”; with union by rank and path compression, a sequence of \( m \) operations on \( n \) elements runs in \( O(m\,\alpha(n)) \) time, where \( \alpha \) is the inverse Ackermann function — effectively constant per operation. It is the standard engine behind connected-component labelling and Kruskal's minimum-spanning-tree algorithm.

In universal algebra the theorem is refined rather than replaced. An equivalence relation on the underlying set of an algebraic structure descends to a quotient structure precisely when it is a congruence: compatible with every operation, so that \( x_i \sim y_i \) for all \( i \) implies \( \omega(x_1,\dots,x_k) \sim \omega(y_1,\dots,y_k) \). For groups, congruences correspond exactly to normal subgroups (via \( x \sim y \iff xy^{-1} \in N \)); for rings, to two-sided ideals; for vector spaces, to subspaces. Categorically, \( q \colon X \to X/{\sim} \) is the coequaliser of the two projections \( \pi_1, \pi_2 \colon {\sim} \to X \), and in \( \mathsf{Set} \) every equivalence relation is effective: it is the kernel pair of its own quotient map, which is exactly Step 7. This effectiveness is a genuine property, not a formality: it holds in \( \mathsf{Set} \) and in every variety of algebras, where the effective equivalence relations are exactly the congruences, but it fails in \( \mathsf{Top} \), where a relation carrying a strictly finer topology than the subspace topology on \( \{\, (x,y) : q(x) = q(y) \,\} \) is still an internal equivalence relation while the kernel pair of its coequaliser returns the subspace topology. A category in which every equivalence relation is effective and regular epimorphisms are stable under pullback is called exact; \( \mathsf{Set} \) and every variety are exact, \( \mathsf{Top} \) is not, since quotient maps of spaces are not stable under pullback.

Common misconceptions. The theorem does not say the classes have equal size, does not say there are finitely many, and does not provide a way to choose a representative from each class: a simultaneous choice across infinitely many classes is precisely the axiom of choice, which is why a transversal for \( \mathbb{R}/\mathbb{Q} \) exists but cannot be written down and yields the Vitali non-measurable set. Nor does it say anything about structure: an equivalence relation on a group gives a quotient set for free, but a quotient group only when the relation is a congruence.

Worked examples

Example 1 (congruence modulo 12, and a clock). Show that \( a \sim b \iff 12 \mid (a-b) \) is an equivalence relation on \( \mathbb{Z} \), identify its partition, and use it: a furnace cycle starts at \( 09{:}00 \) and runs for \( 2500 \) hours. What does a \( 12 \)-hour clock face read when it ends?

\[ a - a = 0 = 12 \cdot 0 \;\Longrightarrow\; a \sim a . \]

Reflexivity: \( 12 \) divides \( 0 \), since \( 0 \) is \( 12 \) times the integer \( 0 \). A

\[ a - b = 12k \;\Longrightarrow\; b - a = 12(-k) \;\Longrightarrow\; b \sim a . \]

Symmetry: \( -k \in \mathbb{Z} \) whenever \( k \in \mathbb{Z} \), so the witness for \( b \sim a \) is obtained by negating the witness for \( a \sim b \). A

\[ a - b = 12k,\quad b - c = 12\ell \;\Longrightarrow\; a - c = (a-b) + (b-c) = 12(k+\ell) \;\Longrightarrow\; a \sim c . \]

Transitivity: the difference telescopes and \( \mathbb{Z} \) is closed under addition, so \( k + \ell \) is an integer witness. Symbols first: no numerical value of \( a, b, c \) is used. A

\[ \mathbb{Z} = [0] \cup [1] \cup \dots \cup [11], \qquad [r] = \{\, 12q + r : q \in \mathbb{Z} \,\}, \qquad \lvert \mathbb{Z}/{\sim} \rvert = 12 . \]

Covering: the division algorithm writes any \( a = 12q + r \) with \( 0 \le r \lt 12 \), so \( a - r = 12q \) and \( a \in [r] \). Distinctness: if \( 0 \le r \lt s \le 11 \) then \( 0 \lt s - r \lt 12 \), so \( 12 \nmid (s-r) \) and \( [r] \neq [s] \). By the theorem the twelve classes are pairwise disjoint, so this is a partition into exactly \( 12 \) blocks. B

\[ 2500 = 12 \cdot 208 + 4 \;\Longrightarrow\; 2500 \equiv 4, \qquad 9 + 2500 \equiv 9 + 4 = 13 \equiv 1 \pmod{12} . \]

Addition descends to the quotient because \( a \sim a' \) and \( b \sim b' \) give \( (a+b) - (a'+b') = (a-a') + (b-b') \), a sum of multiples of \( 12 \) — the congruence condition of the Discussion. So the clock reading of the end time depends only on the classes of \( 9 \) and \( 2500 \). B

\[ 2500\ \mathrm{h} = 104 \times 24\ \mathrm{h} + 4\ \mathrm{h} \;\Longrightarrow\; \text{end time} = 09{:}00 + 4\ \mathrm{h} = 13{:}00 \text{ on the } 104\text{th following day.} \]

Independent check in the calendar rather than the quotient: \( 24 \cdot 104 = 2496 \) and \( 2500 - 2496 = 4 \). A \( 12 \)-hour face shows \( 13 - 12 = 1 \), matching Step 5. A

\[ \mathbb{Z}/12\mathbb{Z} = \bigl\{ [0], [1], \dots, [11] \bigr\}, \qquad 9\ \mathrm{h} + 2500\ \mathrm{h} \equiv 1\ \mathrm{h} \pmod{12\ \mathrm{h}} \;\Longrightarrow\; \text{the clock reads } 1 \text{ o'clock} \]

Reading. Divisibility by \( 12 \) partitions \( \mathbb{Z} \) into twelve infinite classes, and a clock face is literally the quotient set: the hands display \( [t] \), not \( t \). The \( 2500 \) hours of elapsed time are compressed, with no loss of clock information, into the single residue \( 4 \).

Scope. Any modulus \( n \ge 1 \) gives \( n \) classes by the same three steps; \( n = 0 \) gives the discrete partition of \( \mathbb{Z} \) into singletons, and negative \( n \) gives the same partition as \( \lvert n \rvert \).

Example 2 (a measurement partition, and a tolerance relation that is not one). Eight machined pins have measured masses \( 12.30,\ 12.48,\ 12.55,\ 12.62,\ 12.91,\ 13.05,\ 13.38,\ 13.44 \) grams. Bin them by \( b(m) = \lfloor m/(0.5\ \mathrm{g}) \rfloor \) and show the bins partition the batch; then show that “the masses differ by at most \( 0.30\ \mathrm{g} \)” does not.

\[ b \colon X \to \mathbb{Z}, \qquad b(m) = \left\lfloor \frac{m}{0.5\ \mathrm{g}} \right\rfloor, \qquad m \sim_b m' \iff b(m) = b(m') . \]

The argument of the floor is a dimensionless ratio, so \( b \) is a genuine function into \( \mathbb{Z} \); by the kernel-of-a-function corollary, \( \sim_b \) is an equivalence relation with no further checking. Symbolic form first: the numbers enter only at Step 2. B

\[ \frac{12.30}{0.5} = 24.60,\quad \frac{12.48}{0.5} = 24.96,\quad \frac{12.55}{0.5} = 25.10,\quad \frac{12.62}{0.5} = 25.24, \] \[ \frac{12.91}{0.5} = 25.82,\quad \frac{13.05}{0.5} = 26.10,\quad \frac{13.38}{0.5} = 26.76,\quad \frac{13.44}{0.5} = 26.88 . \]

Each ratio is the mass in grams divided by the bin width \( 0.5\ \mathrm{g} \); the grams cancel, leaving pure numbers to which the floor applies. A

\[ b = 24 \colon \{12.30,\, 12.48\}, \qquad b = 25 \colon \{12.55,\, 12.62,\, 12.91\}, \qquad b = 26 \colon \{13.05,\, 13.38,\, 13.44\} . \]

Taking floors of Step 2. Class \( b = k \) is \( X \cap [\,0.5k,\ 0.5(k+1)\,) \) grams, so the blocks are the traces on \( X \) of half-open intervals of width \( 0.5\ \mathrm{g} \): \( [12.00, 12.50) \), \( [12.50, 13.00) \), \( [13.00, 13.50) \). A

\[ \lvert B_{24} \rvert + \lvert B_{25} \rvert + \lvert B_{26} \rvert = 2 + 3 + 3 = 8 = \lvert X \rvert . \]

The counting corollary: for a partition of a finite set the block sizes sum to the size of the set. The check would fail if any pin had been counted twice or omitted, so it audits both disjointness and covering at once. A

\[ m \approx_\tau m' \iff \lvert m - m' \rvert \le \tau, \qquad \tau = 0.30\ \mathrm{g}: \quad \lvert 12.30 - 12.48 \rvert = 0.18,\quad \lvert 12.48 - 12.62 \rvert = 0.14,\quad \lvert 12.30 - 12.62 \rvert = 0.32 . \]

\( \approx_\tau \) is reflexive (\( \lvert m - m \rvert = 0 \le \tau \)) and symmetric (\( \lvert m - m' \rvert = \lvert m' - m \rvert \)), but the three numbers show \( 12.30 \approx_\tau 12.48 \) and \( 12.48 \approx_\tau 12.62 \) while \( 12.30 \not\approx_\tau 12.62 \), because \( 0.32\ \mathrm{g} \gt 0.30\ \mathrm{g} \). Transitivity fails. B

\[ [12.30]_{\approx_\tau} = \{12.30,\, 12.48,\, 12.55\}, \qquad [12.48]_{\approx_\tau} = \{12.30,\, 12.48,\, 12.55,\, 12.62\}, \qquad [12.30] \cap [12.48] \neq \varnothing,\ \ [12.30] \neq [12.48] . \]

Two classes of \( \approx_\tau \) overlap without being equal, which Step 4 of the Proof forbids for any equivalence relation. So no partition of \( X \) induces \( \approx_\tau \), and the failure is visible without ever mentioning transitivity — the overlap is itself the certificate. \( \lvert 12.30 - 12.55 \rvert = 0.25 \le 0.30 \) and \( \lvert 12.48 - 12.62 \rvert = 0.14 \le 0.30 \) justify the memberships listed. C

\[ X/{\sim_b} = \bigl\{ \{12.30, 12.48\},\ \{12.55, 12.62, 12.91\},\ \{13.05, 13.38, 13.44\} \bigr\}\ \mathrm{g}, \qquad 2 + 3 + 3 = 8; \qquad \approx_{0.30\ \mathrm{g}} \notin \operatorname{Eq}(X) \]

Reading. Binning by a function always partitions, because it is the kernel of that function; binning by mutual closeness never does, because closeness is not transitive. If a classification must be a partition, define it by a function, not by a tolerance.

Scope. Any bin width \( w \gt 0 \) and any finite or infinite set of measurements; the three blocks here depend on the choice of origin as well as \( w \), since lowering the bin edges by \( 0.05\ \mathrm{g} \) — that is, using \( b(m) = \lfloor (m + 0.05\ \mathrm{g})/(0.5\ \mathrm{g}) \rfloor \) — would move \( 12.48\ \mathrm{g} \) into the second block, leaving \( 12.30\ \mathrm{g} \) alone in the first.

Problems

(Routine.) On \( X = \{1,2,\dots,10\} \) define \( a \sim b \iff 3 \mid (a-b) \). List the classes, verify that they form a partition, and check the block sizes against \( \lvert X \rvert \).
Solution
The relation is the restriction to \( X \) of congruence modulo \( 3 \), an equivalence relation by the argument of Example 1 with \( 12 \) replaced by \( 3 \). Sorting \( 1, \dots, 10 \) by remainder on division by \( 3 \):
\[ [1] = \{1,4,7,10\}, \qquad [2] = \{2,5,8\}, \qquad [3] = \{3,6,9\} . \]
Each block is non-empty; no integer appears in two blocks, since the division algorithm gives each \( a \) exactly one remainder \( r \in \{0,1,2\} \); and every element of \( X \) appears, so the union is \( X \). Sizes: \( 4 + 3 + 3 = 10 = \lvert X \rvert \), as the counting corollary requires. Note the blocks have different sizes — \( 10 \) is not a multiple of \( 3 \) — which is the ordinary situation.
Show that the intersection of any non-empty family of equivalence relations on \( X \) is an equivalence relation, and give an explicit example of two equivalence relations whose union is not one.
Solution
Intersection. Let \( \{ {\sim_i} \}_{i \in I} \) be equivalence relations, \( I \neq \varnothing \), and put \( {\sim} = \bigcap_{i \in I} {\sim_i} \), i.e. \( x \sim y \iff \forall i,\ x \sim_i y \). Reflexive: \( x \sim_i x \) for every \( i \), so \( x \sim x \). Symmetric: if \( x \sim y \) then \( x \sim_i y \) for all \( i \), hence \( y \sim_i x \) for all \( i \), hence \( y \sim x \). Transitive: if \( x \sim y \) and \( y \sim z \) then for each \( i \) we have \( x \sim_i y \) and \( y \sim_i z \), so \( x \sim_i z \); as \( i \) was arbitrary, \( x \sim z \). (The hypothesis \( I \neq \varnothing \) is there only to make \( \bigcap_{i \in I} {\sim_i} \) well defined without naming an ambient set: computed inside \( X \times X \), the empty intersection is \( X \times X \), which is again an equivalence relation, so the conclusion survives either way.)
Union. On \( X = \{1,2,3\} \) take \[ R = \{(1,1),(2,2),(3,3),(1,2),(2,1)\}, \qquad S = \{(1,1),(2,2),(3,3),(2,3),(3,2)\}, \] the partitions \( \{\{1,2\},\{3\}\} \) and \( \{\{1\},\{2,3\}\} \). Both are equivalence relations. Their union contains \( (1,2) \) and \( (2,3) \) but not \( (1,3) \), so it is not transitive. Its transitive closure is \( X \times X \), the relation of the partition \( \{X\} \), which is the join of \( R \) and \( S \) in the refinement lattice.
How many equivalence relations are there on a set of \( 4 \) elements? Break the count down by the number of blocks.
Solution
By the theorem the count equals the number of partitions of a \( 4 \)-set, namely \( \mathrm{B}_4 = \sum_{k=1}^{4} S(4,k) \).
\( S(4,4) = 1 \): only \( \{\{1\},\{2\},\{3\},\{4\}\} \).
\( S(4,1) = 1 \): only \( \{\{1,2,3,4\}\} \).
\( S(4,3) = 6 \): a partition into three blocks of a \( 4 \)-set must have sizes \( 2+1+1 \), so it is determined by the \( 2 \)-block, and there are \( \binom{4}{2} = 6 \) choices.
\( S(4,2) = 7 \): sizes are \( 3+1 \) or \( 2+2 \). Type \( 3+1 \) is determined by the singleton: \( 4 \) partitions. Type \( 2+2 \) is determined by the block containing \( 1 \), which may be \( \{1,2\}, \{1,3\}, \{1,4\} \): \( 3 \) partitions. Total \( 4 + 3 = 7 \). (Check against the recurrence \( S(4,2) = 2\,S(3,2) + S(3,1) = 2 \cdot 3 + 1 = 7 \).)
Hence \( \mathrm{B}_4 = 1 + 7 + 6 + 1 = 15 \). For comparison \( \mathrm{B}_3 = 5 \) and \( \mathrm{B}_5 = 52 \); note \( 15 \) is far smaller than the \( 2^{16} = 65536 \) relations on a \( 4 \)-set, so being an equivalence relation is a severe restriction.
Let \( f \colon X \to Y \) be any function and \( x \sim_f x' \iff f(x) = f(x') \). Prove \( \sim_f \) is an equivalence relation, that \( \bar{f}([x]) = f(x) \) is well defined and injective, and that \( \bar{f} \) is a bijection \( X/{\sim_f} \to f(X) \). Illustrate with \( X = \{-3,-2,-1,0,1,2,3\} \) and \( f(x) = x^2 \).
Solution
Equivalence. Reflexive: \( f(x) = f(x) \). Symmetric: \( f(x) = f(x') \Longrightarrow f(x') = f(x) \). Transitive: \( f(x) = f(x') \) and \( f(x') = f(x'') \) give \( f(x) = f(x'') \). All three are inherited from the corresponding properties of equality on \( Y \).
Well defined. Suppose \( [x] = [x'] \). Then \( x \sim_f x' \), i.e. \( f(x) = f(x') \), so the proposed value of \( \bar{f} \) does not depend on the representative. This is the universal property with \( q(x) = [x] \): \( f \) is constant on classes, hence factors as \( f = \bar{f} \circ q \), uniquely because \( q \) is surjective.
Injective. If \( \bar{f}([x]) = \bar{f}([x']) \) then \( f(x) = f(x') \), so \( x \sim_f x' \) and \( [x] = [x'] \) by Step 3 of the Proof.
Onto \( f(X) \). Every element of \( f(X) \) is \( f(x) = \bar{f}([x]) \) for some \( x \). Hence \( \bar{f} \colon X/{\sim_f} \to f(X) \) is a bijection.
Numerical instance. \( f(x) = x^2 \) on \( X \) gives \( f(X) = \{0,1,4,9\} \) and \[ X/{\sim_f} = \bigl\{ \{0\},\ \{-1,1\},\ \{-2,2\},\ \{-3,3\} \bigr\}, \] four blocks of sizes \( 1,2,2,2 \) summing to \( 7 = \lvert X \rvert \). The bijection sends \( \{0\} \mapsto 0 \), \( \{-1,1\} \mapsto 1 \), \( \{-2,2\} \mapsto 4 \), \( \{-3,3\} \mapsto 9 \), and \( \lvert X/{\sim_f} \rvert = 4 = \lvert f(X) \rvert \) as required.
(Harder.) Let \( R \) be an arbitrary relation on \( X \). Prove that a smallest equivalence relation \( \langle R \rangle \) containing \( R \) exists, and that \( (x,y) \in \langle R \rangle \) holds exactly when \( x = y \) or there is a finite chain \( x = z_0, z_1, \dots, z_m = y \) with \( m \ge 1 \) and, for each \( i \), \( (z_{i-1}, z_i) \in R \) or \( (z_i, z_{i-1}) \in R \). Compute \( \langle R \rangle \) for \( X = \{1,\dots,6\} \) and \( R = \{(1,2),(3,4),(4,5)\} \), including \( \lvert \langle R \rangle \rvert \) as a set of ordered pairs.
Solution
Existence. The family \( \mathcal{F} \) of equivalence relations on \( X \) containing \( R \) is non-empty, since \( X \times X \in \mathcal{F} \). By Problem 2 the intersection \( \langle R \rangle = \bigcap \mathcal{F} \) is an equivalence relation; it contains \( R \) because every member does; and it is contained in each member, so it is the smallest.
Chain description. Let \( E \) be the relation described by chains. \( E \) is reflexive by the clause \( x = y \); symmetric, since reversing a chain reverses each step and the step condition is already symmetric in the two orders; and transitive, since concatenating a chain from \( x \) to \( y \) with one from \( y \) to \( z \) is a chain from \( x \) to \( z \) (if either is the trivial chain the conclusion is immediate). Also \( R \subseteq E \), taking \( m = 1 \). Hence \( \langle R \rangle \subseteq E \). Conversely any equivalence relation \( {\sim} \supseteq R \) contains every chain relation: each step gives \( z_{i-1} \sim z_i \) by \( R \subseteq {\sim} \) and symmetry, and transitivity composes the \( m \) steps; the case \( x = y \) is reflexivity. So \( E \subseteq \bigcap \mathcal{F} = \langle R \rangle \), and \( E = \langle R \rangle \).
Computation. The chains from \( R = \{(1,2),(3,4),(4,5)\} \) link \( 1 \) with \( 2 \); and \( 3 \) with \( 4 \), \( 4 \) with \( 5 \), hence \( 3 \) with \( 5 \) through \( 4 \). Element \( 6 \) appears in no pair of \( R \), so its class is \( \{6\} \). The partition is \[ \bigl\{ \{1,2\},\ \{3,4,5\},\ \{6\} \bigr\}, \] with block sizes \( 2 + 3 + 1 = 6 = \lvert X \rvert \). As a set of ordered pairs, \( \langle R \rangle \) is the disjoint union of \( B \times B \) over the blocks, so \[ \lvert \langle R \rangle \rvert = 2^2 + 3^2 + 1^2 = 4 + 9 + 1 = 14 \] pairs, out of the \( 6^2 = 36 \) pairs in \( X \times X \). In general \( \lvert {\sim} \rvert = \sum_{B \in \mathcal{P}} \lvert B \rvert^2 \), which is minimised by the discrete partition (\( \lvert X \rvert \) pairs) and maximised by \( \{X\} \) (\( \lvert X \rvert^2 \) pairs).