Maths WorkshopMaths problems with full solutions
Exercise 1177Logic, sets and proofs › Sets and mapsL1Added 3 Nov 2026

Equivalence classes and partitions

#equivalence class#partition#quotient

Statement

Show that the equivalence classes of an equivalence relation on AA form a partition of AA.

Hint

Show that classes are nonempty, disjoint, and cover AA.

Show solutionHide solution

Solution

Definition. The equivalence class of x∈Ax\in A is [x]={y∈A:y∼x}[x]=\{y\in A:y\sim x\}.

Nonempty. x∈[x]x\in[x] (reflexive).

Cover. Every xx belongs to its own class.

Disjoint. If [x]∩[y]≠∅[x]\cap[y]\neq\emptyset, take zz in both. Then z∼xz\sim x and z∼yz\sim y, so by symmetry and transitivity x∼yx\sim y. Then for any w∈[x]w\in[x], w∼x∼yw\sim x\sim y, so w∈[y]w\in[y]: [x]⊆[y][x]\subseteq[y]. Symmetrically, [y]⊆[x][y]\subseteq[x]. So [x]=[y][x]=[y].

Conclusion. The classes form a partition of AA; the set of classes is A/∼A/\sim (the quotient).