Relation Induced by Partition is Equivalence

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $\RR$ be the relation induced by $\mathbb S$.


Then:

$(1): \quad \RR$ is unique
$(2): \quad \RR$ is an equivalence relation on $S$.

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

$\mathbb S = S / \RR$


Proof

From the definition of Relation Induced by Partition, we define the relation $\RR$ on $S$ by:

$\RR = \set {\tuple {x, y}: \paren {\exists T \in \mathbb S: x \in T \land y \in T} }$


Test for Equivalence

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

Checking in turn each of the criteria for equivalence:


Reflexive

$\RR$ is reflexive:

\(\ds \) \(\) \(\ds \paren {x \in T \land x \in T}\) Rule of Idempotence
\(\ds \) \(\leadstoandfrom\) \(\ds \tuple {x, x} \in \RR\) Definition of $\RR$

$\Box$


Symmetric

$\RR$ is symmetric:

\(\ds \) \(\) \(\ds \tuple {x, y} \in \RR\)
\(\ds \) \(\leadsto\) \(\ds x \in T \land y \in T\) Definition of $\RR$
\(\ds \) \(\leadsto\) \(\ds y \in T \land x \in T\) Rule of Commutation
\(\ds \) \(\leadsto\) \(\ds \tuple {y, x} \in \RR\) Definition of $\RR$

$\Box$


Transitive

$\RR$ is transitive:

\(\ds x \in T \land y \in T\) \(\leadstoandfrom\) \(\ds \tuple {x, y} \in \RR\) Definition of $\RR$
\(\ds y \in T \land z \in T\) \(\leadstoandfrom\) \(\ds \tuple {y, z} \in \RR\) Definition of $\RR$
\(\ds \paren {x \in T \land y \in T} \land \paren {y \in T \land z \in T}\) \(\leadstoandfrom\) \(\ds \tuple {x, z} \in \RR\) Definition of $\RR$

$\Box$


So $\RR$ is reflexive, symmetric and transitive.

Hence, by definition, $\RR$ is an equivalence relation.

$\Box$


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:

\(\ds x, y \in T\) \(\leadsto\) \(\ds \tuple {x, y} \in \RR\) Definition of $\RR$
\(\ds x \in T_1, y \in T_2, T_1 \ne T_2\) \(\leadsto\) \(\ds \tuple{x, y} \notin \RR\) Definition of Set Partition


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

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Relation_Induced_by_Partition_is_Equivalence&oldid=629650"