Relation Partitions Set iff Equivalence
Jump to navigation
Jump to search
Theorem
Let $\RR$ be a relation on a set $S$.
Then $S$ can be partitioned into subsets by $\RR$ if and only if $\RR$ is an equivalence relation on $S$.
The partition of $S$ defined by $\RR$ is the quotient set $S / \RR$.
Proof
Let $\RR$ be an equivalence relation on $S$.
From the Fundamental Theorem on Equivalence Relations, we have that the equivalence classes of $\RR$ form a partition.
$\Box$
Let $S$ be partitioned into subsets by a relation $\RR$.
From Relation Induced by Partition is Equivalence, $\RR$ is an equivalence relation.
$\blacksquare$
Sources
- 1951: Nathan Jacobson: Lectures in Abstract Algebra: Volume $\text { I }$: Basic Concepts ... (previous) ... (next): Introduction $\S 3$: Equivalence relations
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 7$: Relations
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Relations: Theorem $5$
- 1964: W.E. Deskins: Abstract Algebra ... (previous) ... (next): $\S 1.2$: Theorem $1.11$
- 1978: John S. Rose: A Course on Group Theory ... (previous) ... (next): $0$: Some Conventions and some Basic Facts
- 2002: Thomas Jech: Set Theory (3rd ed.) ... (previous) ... (next): Chapter $1$: Power Set