Reflexive-Transitive Closure of a Relation

The reflexive transitive closure of a Relation $\leadsto\;\subseteq R\times R$, denoted $\leadsto^{*}$, is the smallest Reflexive and Transitive relation that contains $\leadsto$.

Explicitly, the reflexive transitive closure of $\leadsto$ contains (potentially empty) chains of elements

• $x_{0}\leadsto x_{1}\leadsto x_{2}\leadsto\cdots\leadsto x_{n}$

We can construct this by taking the Colimit of the following Omega Chain:

• $\bigcup_{n:\mathbb{N}}\leadsto^{n}$

Properties

• The reflexive transitive closure induces an Idempotent Monad on the Poset of relations $R\subseteq A\times A$

  • $R\subseteq R^{*}$

  • $(R^{*})^{*}=R^{*}$