Transitive closure in set theory is an operation on binary relations . The transitive closure of a binary relation R on a set X is the smallest transitive relation on a set X, including R.
For example, if X is a multitude of people (both living and dead), and R is the relation “is the parent”, then the transitive closure of R is the relation “is the ancestor”. If X is a set of airports, and xRy is equivalent to “there is a flight from x to y” and the transitive closure of R is P, then xPy is equivalent to “you can fly from x to y by plane” (although sometimes you have to fly with transfers)
Example
Let the set A be the following set of parts and constructions:
A = {Bolt, Nut, Engine, Car, Wheel, Axle}
some of the parts and structures may be used in the assembly of other structures. The interconnection of parts is described by the relation R (“directly used in”) and consists of the following tuples:
| Design | Where is used |
|---|---|
| Bolt | Engine |
| Bolt | Wheel |
| Nut | Engine |
| Nut | Wheel |
| Engine | Car |
| Wheel | Car |
| Axis | Wheel |
Table 1. The ratio of R.
A transitive closure consists of tuples (added tuples are marked in bold):
| Design | Where is used |
|---|---|
| Bolt | Engine |
| Bolt | Wheel |
| Nut | Engine |
| Nut | Wheel |
| Engine | Car |
| Wheel | Car |
| Axis | Wheel |
| Bolt | Car |
| Nut | Car |
| Axis | Car |
Table 2. Transitive closure of the relation R.
The obvious meaning of the R closure is to describe the inclusion of parts into each other not only directly, but through their use in intermediate parts, for example, a bolt is used in a car, since it is used in the engine, and the engine is used in the car.