Two Descriptions of Grouping a Set
An equivalence relation groups elements that are regarded as equivalent: each element belongs to its own class, equivalent elements share a class, and the classes do not overlap unless they are the same class. A partition describes the same grouping directly, by listing the nonempty blocks. We will prove that these descriptions determine one another, then build both descriptions for several finite sets.
Let \(X\) be a set. Recall that a relation \(\sim\) on \(X\) is an equivalence relation if it is reflexive, symmetric, and transitive: \(x\sim x\) for every \(x\in X\); \(x\sim y\) implies \(y\sim x\); and \(x\sim y\) together with \(y\sim z\) implies \(x\sim z\). For \(x\in X\), its equivalence class is \([x]=\{y\in X:y\sim x\}\).
The requirement that blocks be nonempty is part of the definition. It prevents an empty set from being treated as an extra block: adding an empty set changes no coverage or intersections, but it does not give a group of elements. For a nonempty \(X\), every element lies in exactly one block: coverage gives at least one, and disjointness gives at most one.
Equivalence Classes Form a Partition
Proof. First suppose \(X\ne\varnothing\). Every class is nonempty: if \(x\in X\), reflexivity gives \(x\sim x\), so \(x\in[x]\). Every element \(x\in X\) belongs to \([x]\), so the classes cover \(X\). It remains to show that two classes which intersect are equal. Suppose \([a]\cap[b]\ne\varnothing\), and choose \(z\in[a]\cap[b]\). Then \(z\sim a\) and \(z\sim b\). By symmetry, \(a\sim z\); by transitivity with \(z\sim b\), \(a\sim b\). Now take any \(w\in[a]\). Then \(w\sim a\) and \(a\sim b\), so transitivity gives \(w\sim b\), hence \(w\in[b]\). Thus \([a]\subseteq[b]\). Symmetry gives \(b\sim a\); applying the same reasoning with \(a\) and \(b\) interchanged gives \([b]\subseteq[a]\). Therefore \([a]=[b]\). If \(X=\varnothing\), there are no elements and hence no equivalence classes. The empty family covers the empty set, and has no pair of distinct blocks that could intersect, so it is a partition by definition. \(\square\)
The theorem says more than that each element has a class. It says the classes cannot overlap in a partial way: once two classes share even one element, they contain exactly the same elements. This is the feature that lets us use the classes as blocks in a partition.
Worked Example: Congruence Classes on a Six-Element Set
Let \(X=\{1,2,3,4,5,6\}\), and define \(x\sim y\) when \(3\) divides \(x-y\). This is an equivalence relation: \(x-x=0\) is divisible by \(3\); if \(3\) divides \(x-y\), then it divides \(y-x=-(x-y)\); and if it divides both \(x-y\) and \(y-z\), it divides their sum \(x-z\).
We compute the classes by checking which elements differ by a multiple of \(3\). For \(1\), the differences from \(1,2,3,4,5,6\) are \(0,1,2,3,4,5\); only \(0\) and \(3\) are divisible by \(3\), so \([1]=\{1,4\}\). For \(2\), the differences are \(-1,0,1,2,3,4\), giving \([2]=\{2,5\}\). For \(3\), the differences are \(-2,-1,0,1,2,3\), giving \([3]=\{3,6\}\). The remaining classes repeat: \([4]=\{1,4\}\), \([5]=\{2,5\}\), and \([6]=\{3,6\}\).
Thus the distinct classes form the partition \(\big\{\{1,4\},\{2,5\},\{3,6\}\big\}\). As a direct check, the relation consists of the ordered pairs \((1,1),(1,4),(4,1),(4,4)\), \((2,2),(2,5),(5,2),(5,5)\), and \((3,3),(3,6),(6,3),(6,6)\). These are exactly the pairs within the three displayed blocks.
A Partition Defines an Equivalence Relation
Proof. If \(X=\varnothing\), the relation has no ordered pairs. Reflexivity, symmetry, and transitivity are universal statements about elements of \(X\); each is satisfied because there are no elements that could violate it. There are also no equivalence classes, so the claim about classes and blocks holds because the partition has no blocks. Now suppose \(X\ne\varnothing\). For reflexivity, each \(x\in X\) belongs to a block, so \(x\) and itself belong to the same block and \(x\sim_{\mathcal{P}}x\). For symmetry, if \(x\) and \(y\) belong to the same block, then \(y\) and \(x\) belong to that same block, so \(y\sim_{\mathcal{P}}x\). For transitivity, suppose \(x\sim_{\mathcal{P}}y\) and \(y\sim_{\mathcal{P}}z\). Let \(P,Q\in\mathcal{P}\) be blocks containing \(x,y\) and \(y,z\), respectively. Since \(y\in P\cap Q\), the partition property gives \(P=Q\). Thus \(x\) and \(z\) belong to the same block, so \(x\sim_{\mathcal{P}}z\). This proves that the relation is an equivalence relation.
To identify its classes, fix \(x\in X\), and let \(P_x\) be the unique block containing \(x\). For any \(y\in P_x\), the points \(x,y\) lie in the same block, so \(y\sim_{\mathcal{P}}x\) and \(y\in[x]\). Conversely, if \(y\in[x]\), then some block \(Q\) contains both \(x\) and \(y\). Since \(x\in Q\cap P_x\), the partition property implies \(Q=P_x\), so \(y\in P_x\). Hence \([x]=P_x\). Every block is \(P_x\) for any \(x\) it contains, so the classes are exactly the blocks. \(\square\)
Worked Example: Build a Relation from a Partition
Let \(X=\{a,b,c,d,e\}\) and \(\mathcal{P}=\big\{\{a,b\},\{c\},\{d,e\}\big\}\). The blocks are nonempty, their union is \(X\), and they are pairwise disjoint, so this is a partition.
By Theorem 2, declare two elements related precisely when they lie in the same block. The block \(\{a,b\}\) contributes \((a,a),(a,b),(b,a),(b,b)\); the block \(\{c\}\) contributes \((c,c)\); and the block \(\{d,e\}\) contributes \((d,d),(d,e),(e,d),(e,e)\). There are \(4+1+4=9\) ordered pairs in the relation. No pair connects different blocks.
For example, \(a\sim_{\mathcal{P}}b\), \(b\sim_{\mathcal{P}}a\), and \(d\sim_{\mathcal{P}}e\), while \(a\not\sim_{\mathcal{P}}c\). The equivalence classes are \([a]=[b]=\{a,b\}\), \([c]=\{c\}\), and \([d]=[e]=\{d,e\}\). They recover the three original blocks exactly.
Check: each displayed pair has both entries in one of the three blocks, so it satisfies the definition of the relation. Conversely, any related pair must lie together in one of those blocks, and the list includes every ordered pair from each block. Thus the list neither omits nor adds any related pair.
Worked Example: Grouping Integers by Absolute Value
Let \(X=\{-2,-1,0,1,2\}\), and define \(x\sim y\) if and only if \(|x|=|y|\). Equality of absolute values is reflexive, symmetric, and transitive, so this is an equivalence relation. Compute \(|x|\) for each element: \(|-2|=2\), \(|-1|=1\), \(|0|=0\), \(|1|=1\), and \(|2|=2\). Therefore the classes are \([0]=\{0\}\), \([1]=[-1]=\{-1,1\}\), and \([2]=[-2]=\{-2,2\}\).
The corresponding partition is \(\big\{\{0\},\{-1,1\},\{-2,2\}\big\}\). The relation has \(1^2+2^2+2^2=9\) ordered pairs: \((0,0)\); the four pairs \((-1,-1),(-1,1),(1,-1),(1,1)\); and the four pairs \((-2,-2),(-2,2),(2,-2),(2,2)\).
Check: the three blocks are nonempty, they have no element in common, and their union contains all five elements of \(X\). The pair \((-2,2)\) is included because both absolute values are \(2\); the pair \((-2,1)\) is excluded because \(2\ne1\). This agrees with the rule defining the relation.
Why the Partition Conditions Matter
The two theorems give a conversion in both directions. Starting with an equivalence relation, take its distinct classes; starting with a partition, declare elements equivalent when they belong to the same block. The resulting classes are the original blocks. The distinction between “distinct classes” and the list \([x]\) for every \(x\) matters: different elements can name the same class, as \(a\) and \(b\) do in the second example.
Common pitfall. A family of sets that merely covers \(X\) need not be a partition. For instance, consider \(\{1,2\}\) and \(\{2,3\}\) as proposed blocks of \(X=\{1,2,3\}\). They cover \(X\), but they intersect at \(2\) and are not equal. If we try to define a relation by “belonging to a common proposed block,” then \(1\sim2\) and \(2\sim3\), but \(1\not\sim3\). Transitivity fails, so this is not an equivalence relation. The correction is not to allow partially overlapping blocks: a partition requires intersecting blocks to be equal. Here the valid partition \(\big\{\{1,2,3\}\big\}\) gives the relation in which every pair is related; another valid partition, \(\big\{\{1\},\{2\},\{3\}\big\}\), gives only the three reflexive pairs.
For a finite set, a useful check when writing a partition is to verify three things separately: every element appears in at least one block, no block is empty, and distinct blocks have no common element. Once those checks pass, the “same block” rule automatically gives an equivalence relation, as Theorem 2 proves.
Check Your Understanding
Use the definitions and the two conversion theorems to answer each question.
- For the relation on \(\{1,2,3,4,5,6\}\) defined by divisibility of \(x-y\) by \(3\), list all distinct equivalence classes.
- On \(X=\{p,q,r,s\}\), let \(\mathcal{P}=\big\{\{p,r\},\{q\},\{s\}\big\}\). List every ordered pair in the relation defined by belonging to the same block.
- Explain why the empty family is a partition of the empty set, and describe the equivalence relation it determines.
- Give a family of subsets that covers a three-element set but is not a partition. Show how the “same block” rule fails transitivity.
- Prove directly that if two equivalence classes intersect, they are equal, identifying where symmetry and transitivity are used.