Reflexive Closure of Transitive Relation is Transitive

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a set.

Let $\mathcal R$ be a transitive relation.

Let $\mathcal R^=$ be the reflexive closure of $\mathcal R$.


Then $\mathcal R^=$ is also transitive.


Proof

Let $a, b, c \in S$.

Suppose that $a \mathrel{\mathcal R^=} b$ and $b \mathrel{\mathcal R^=} c$.

If $a = b$, then since $b \mathrel{\mathcal R^=} c$, also $a \mathrel{\mathcal R^=} c$.

If $b = c$, then since $a \mathrel{\mathcal R^=} b$, also $a \mathrel{\mathcal R^=} c$.


The only case that remains is that $a \ne b$ and $b \ne c$.

Then by the definition of $\mathcal R^=$, $a \mathrel{\mathcal R} b$ and $b \mathrel{\mathcal R} c$.


Since $\mathcal R$ is transitive, it follows that:

$a \mathrel{\mathcal R} c$

and hence also $a \mathrel{\mathcal R^=} c$.


Thus $\mathcal R^=$ is transitive.

$\blacksquare$


Also see


Sources