Reflexive Circular Relation is Equivalence

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathcal R \subseteq S \times S$ be a reflexive and circular relation in $S$.


Then $\mathcal R$ is an equivalence relation.


Proof

To prove a relation is an equivalence, we need to prove it is reflexive, symmetric and transitive.

So, checking in turn each of the criteria for equivalence:


Reflexive

By hypothesis $\mathcal R$ is reflexive.

$\Box$


Symmetric

By reflexivity:

$\tuple {x, x} \in \mathcal R$


If $\tuple {x, y} \in \mathcal R$ then by the definition of circular relation $\tuple {y, x} \in \mathcal R$.


Hence $\mathcal R$ is symmetric.

$\Box$


Transitive

Let $\tuple {x, y}, \tuple {y, z} \in \mathcal R$.

By definition of circular relation:

$\tuple {z, x} \in \mathcal R$

By $\mathcal R$ being symmetric:

$\tuple {x, z} \in \mathcal R$


Hence $\mathcal R$ is transitive.

$\Box$


Thus is $\mathcal R$ is reflexive, symmetric and transitive, and therefore by definition an equivalence.

$\blacksquare$


Sources