Maths WorkshopMaths problems with full solutions
Exercise 1165Logic, sets and proofs › RelationsL1Added 3 Nov 2026

Equivalence classes form a partition

#partition#equivalence classes#proof

Statement

Show that the set of equivalence classes of any equivalence relation on AA forms a partition of AA.

Hint

Show classes are nonempty, disjoint, and cover AA.

Show solutionHide solution

Solution

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

Cover. Every aa is in [a][a].

Disjoint. Suppose [a]∩[b]≠∅[a]\cap[b]\neq\emptyset, say c∈[a]∩[b]c\in[a]\cap[b]. Then c∼ac\sim a and c∼bc\sim b. By symmetry, a∼ca\sim c; by transitivity a∼ba\sim b. For any x∈[a]x\in[a]: x∼a∼bx\sim a\sim b, so x∈[b]x\in[b]: [a]⊆[b][a]\subseteq[b]. Symmetrically [b]⊆[a][b]\subseteq[a]. Equal.

Conclusion. The classes are disjoint, nonempty, cover AA: a partition.