Reflexive Closure of Transitive Relation is Transitive

From ProofWiki
Jump to navigation Jump to search


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.


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.


Also see