Relation Partitions a Set iff Equivalence

Theorem

Let $\mathcal R$ be a relation on a set $S$.

Then $S$ can be partitioned into subsets by $\mathcal R$ iff $\mathcal R$ is an equivalence relation on $S$.

The partition of $S$ defined by $\mathcal R$ is the quotient set $S / \mathcal R$.

Proof

• Let $\mathcal R$ be an equivalence relation on $S$.

From the Fundamental Theorem on Equivalence Relations, we have shown that the equivalence classes of $\mathcal R$ form a partition.

• Let $S$ be partitioned into subsets by a relation $\mathcal R$.

From Relation Induced by Partition is Equivalence, $\mathcal R$ must be an equivalence.

$\blacksquare$

Sources

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 3$
• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 7$: Relations
• W.E. Deskins: Abstract Algebra (1964): $\S 1.2$: Theorem $1.11$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.3$: Theorem $5$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Theorem $5$, Exercise $\text{E}$
• A.N. Kolmogorov and S.V. Fomin‎: Introductory Real Analysis (1968): $\S 1.4$: Theorem $4$
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 6$: Theorem $6.4$