nLab transitive closure

(Reflexive)-transitive closures

(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 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. Thus prerelations have transitive closures but not necessarily reflexive-transitive closures.

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. The result is a transitive set, the smallest transitive set that contains XX as a subset.

Analogously, the reflexive-transitive closure of XX may be defined as the transitive closure of the successor X{X}X \cup \{X\} of XX, or equivalently the transitive closure of {X}\{X\} itself. Either way, this is the same as X *{X}X^* \cup \{X\}. This is the smallest transitive set that contains XX as a member. (It is not, however, normally a reflexive set; that is, it does not belong to itself.)

Last revised on November 21, 2017 at 19:08:58. See the history of this page for a list of all contributions to it.