Reflexive and Transitive Relation is Idempotent

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Let $\mathcal R$ be both reflexive and transitive.

Then $\mathcal R$ is idempotent, in the sense that:

$\mathcal R \circ \mathcal R = \mathcal R$

where $\circ$ denotes composition of relations.


Proof

Let $\mathcal R$ be both reflexive and transitive.

By definition of transitive relation:

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


Let $\left({x, y}\right) \in \mathcal R$.

By definition of reflexive relation:

$\left({y, y}\right) \in \mathcal R$

By definition of composition of relations:

$\left({x, y}\right) \in \mathcal R \circ \mathcal R$

Hence:

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


Thus by definition of set equality:

$\mathcal R \circ \mathcal R = \mathcal R$

$\blacksquare$


Sources