Relation Partitions Set iff Equivalence

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Then $S$ can be partitioned into subsets by $\mathcal R$ if and only if $\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 that the equivalence classes of $\mathcal R$ form a partition.

$\Box$


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

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

$\blacksquare$


Sources