# (Reflexive)-transitive closures

## Of a relation

The transitive closure of a binary relation $\sim$ on a set $S$ is the smallest transitive relation that contains $\sim$.

Often one wants the reflexive-transitive closure ${\sim }^{*}$ of $\sim$, which is the smallest transitive relation that contains $\sim$ and is also reflexive.

These can be defined explicitly as follows: $x{\sim }^{*}y$ if and only if, for some natural number $n$, there exists a sequence $\left({r}_{0},\dots ,{r}_{n}\right)$ such that

$x={r}_{0}\sim \cdots \sim {r}_{n}=y.$x = r_0 \sim \cdots \sim r_n = y .

If you accept $0$ as a natural number, then this defines the reflexive-transitive closure; if not, then this defines the transitive closure.

For the transitive closure, it's also possible to rephrase the above slightly (using only ${r}_{1}$ through ${r}_{n-1}$) to avoid any reference to equality.

## Of a material set

In material set theory, the transitive closure of a pure set $X$ is the transitive set ${X}^{*}$ whose members are the elements of the downset of $X$ under the transitive closure (in the previous sense) of $\in$. That is, it consists of the members of $X$, their members, their members, and so on.

Analogously, the reflexive-transitive closure of $X$ may be defined as the transitive closure of the successor ${X}^{+}=X\cup \left\{X\right\}$ of $X$, which is the same as ${X}^{*}\cup \left\{X\right\}$.

Revised on September 3, 2012 21:04:50 by Toby Bartels (98.23.143.147)