|
In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains
R.
In more concrete terms the transitive closure of R is the relation R* such that xR*y if xRy, or if xRz for some z with zRy, or
if xRz and zRw and wRy for some z and w in X, and so on for any number of intermediates. If X is the set of humans (alive or
dead) and R is the relation 'parent of', then xR*y means y is a direct descendant of x.
Examples
- If xRy means x is the parent of y, then the transitive closure of R is the relation
"x is an ancestor of y."
- If xRy means "there is a regular direct airplane flight from airport x to airport y", then the
transitive closure of R is the relation "it is possible to fly from x to y in one or more
flights."
See also: Transitivity (mathematics),
Intransitivity
|