Equivalence of Definitions of Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

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


The following definitions of the concept of Equivalence Relation are equivalent:

Definition 1

Let $\mathcal R$ be:

$(1): \quad$ reflexive
$(2): \quad$ symmetric
$(3): \quad$ transitive

Then $\mathcal R$ is an equivalence relation on $S$.

Definition 2

$\mathcal R$ is an equivalence relation if and only if:

$\Delta_S \cup \mathcal R^{-1} \cup \mathcal R \circ \mathcal R \subseteq \mathcal R$

where:

$\Delta_S$ denotes the diagonal relation on $S$
$\mathcal R^{-1}$ denotes the inverse relation
$\circ$ denotes composition of relations


Proof

Definition 1 implies Definition 2

Let $\mathcal R$ be an equivalence relation by definition 1.

By definition, $\mathcal R$ is reflexive, symmetric and transitive.


From Relation Contains Diagonal Relation iff Reflexive:

$\Delta_S \subseteq \mathcal R$


From Relation equals Inverse iff Symmetric:

$\mathcal R^{-1} = \mathcal R$

and so by definition of set equality:

$\mathcal R^{-1} \subseteq \mathcal R$


From Relation contains Composite with Self iff Transitive:

$\mathcal R \circ \mathcal R \subseteq \mathcal R$


From Union is Smallest Superset:

$\Delta_S \cup \mathcal R^{-1} \cup \mathcal R \circ \mathcal R \subseteq \mathcal R$

Thus $\mathcal R$ is an equivalence relation by definition 2.

$\Box$


Definition 2 implies Definition 1

Let $\mathcal R$ be an equivalence relation by definition 2.

That is:

$\Delta_S \cup \mathcal R^{-1} \cup \mathcal R \circ \mathcal R \subseteq \mathcal R$

By Union is Smallest Superset:

$(1): \quad \Delta_S \subseteq \mathcal R$
$(2): \quad \mathcal R^{-1} \subseteq \mathcal R$
$(3): \quad \mathcal R \circ \mathcal R \subseteq \mathcal R$


From Relation Contains Diagonal Relation iff Reflexive, $(1)$ gives directly that $\mathcal R$ is reflexive.


From Inverse Relation Equal iff Subset, $(2)$ gives that $\mathcal R^{-1} = \mathcal R$.

So from Relation equals Inverse iff Symmetric $\mathcal R$ is symmetric.


From Relation contains Composite with Self iff Transitive, $(3)$ gives that $\mathcal R$ is transitive.


So $\mathcal R$ has been shown to be reflexive, symmetric and transitive.

Thus $\mathcal R$ is an equivalence relation by definition 1.

$\blacksquare$


Sources