transitive closure

(Reflexive)-transitive closures

Of a relation

The transitive closure of a binary relation \sim on a set SS 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 *y x \sim^* y if and only if, for some natural number nn, there exists a sequence (r 0,,r n)(r_0, \ldots, r_n) such that

x=r 0r n=y. x = r_0 \sim \cdots \sim r_n = y .

If you accept 00 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 1r_1 through r n1r_{n-1}) to avoid any reference to equality.

Of a material set

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

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

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