Relation Induced by Partition is Equivalence

Theorem

Let $\mathbb S$ be a partition of a set $S$.

Let $\mathcal R$ be the relation induced by $\mathbb S$.

Then:

• $\mathcal R$ is unique;
• $\mathcal R$ is an equivalence relation on $S$.

Hence $\mathbb S$ is the quotient set of $S$ by $\mathcal R$, that is:

$\mathbb S = S / \mathcal R$

Proof

Let $\mathbb S$ be a partition of a $S$.

From Relation Induced by Partition, we define the relation $\mathcal R$ on $S$ by:

$\mathcal R = \left\{{\left({x, y}\right): \left({\exists T \in \mathbb S: x \in T \land y \in T}\right)}\right\}$

Test for Equivalence

We are to show that $\mathcal R$ is an equivalence relation.

Checking in turn each of the critera for equivalence:

Reflexive

$\mathcal R$ is reflexive:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \left({x \in T \iff x \in T}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rule of Idempotence
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\iff\)	\(\displaystyle \left({x, x}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$

$\Box$

Symmetric

$\mathcal R$ is symmetric:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle x \in T \land y \in T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle y \in T \land x \in T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rule of Commutation
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \left({y, x}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$

$\Box$

Transitive

$\mathcal R$ is transitive:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x \in T \land y \in T\)	\(\iff\)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle y \in T \land z \in T\)	\(\iff\)	\(\displaystyle \left({y, z}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x \in T \land y \in T}\right) \land \left({y \in T \land z \in T}\right)\)	\(\iff\)	\(\displaystyle \left({x, z}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$

$\Box$

So $\mathcal R$ is reflexive, symmetric and transitive, therefore $\mathcal R$ is an equivalence relation.

Test for Uniqueness

Now by definition of a partition, we have that:

$\mathbb S$ partitions $S \implies \forall x \in S: \exists T \in \mathbb S: x \in T$

Also:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x, y \in T\)	\(\implies\)	\(\displaystyle \left({x, y}\right) \in \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of $\mathcal R$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle x \in T_1, y \in T_2, T_1 \ne T_2\)	\(\implies\)	\(\displaystyle \left({x, y}\right) \notin \mathcal R\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by definition of a partition

Thus $\mathbb S$ is the family of $\mathcal R$-classes constructed above, and no other relation can be constructed in this way.

$\blacksquare$

Also see

• Fundamental Theorem on Equivalence Relations for the converse.

Sources

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 3$
• W.E. Deskins: Abstract Algebra (1964): $\S 1.2$
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 2.4$: Example $37$
• J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $2.4$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): $\S 10$: Theorem $10.2$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.3$: Theorem $5$ Part $\text {II}$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 17 \alpha$