Editing Transitive relation (section)

==Transitive extensions and transitive closure==
{{main|Transitive closure}}

Let {{mvar|R}} be a binary relation on set {{mvar|X}}. The ''transitive extension'' of {{mvar|R}}, denoted {{math|''R''<sub>1</sub>}}, is the smallest binary relation on {{mvar|X}} such that {{math|''R''<sub>1</sub>}} contains {{mvar|R}}, and if {{math|(''a'', ''b'') ∈ ''R''}} and {{math|(''b'', ''c'') ∈ ''R''}} then {{math|(''a'', ''c'') ∈ ''R''<sub>1</sub>}}.<ref>{{harvnb|Liu|1985|loc=p. 111}}</ref> For example, suppose {{mvar|X}} is a set of towns, some of which are connected by roads. Let {{mvar|R}} be the relation on towns where {{math|(''A'', ''B'') ∈ ''R''}} if there is a road directly linking town {{mvar|A}} and town {{mvar|B}}. This relation need not be transitive. The transitive extension of this relation can be defined by {{math|(''A'', ''C'') ∈ ''R''<sub>1</sub>}} if you can travel between towns {{mvar|A}} and {{mvar|C}} by using at most two roads.

If a relation is transitive then its transitive extension is itself, that is, if {{mvar|R}} is a transitive relation then {{math|1=''R''<sub>1</sub> = ''R''}}.

The transitive extension of {{math|''R''<sub>1</sub>}} would be denoted by {{math|''R''<sub>2</sub>}}, and continuing in this way, in general, the transitive extension of {{math|''R''<sub>''i''</sub>}} would be {{math|''R''<sub>''i'' + 1</sub>}}. The ''transitive closure'' of {{mvar|R}}, denoted by {{math|''R''*}} or {{math|''R''<sup>∞</sup>}} is the set union of {{mvar|R}}, {{math|''R''<sub>1</sub>}}, {{math|''R''<sub>2</sub>}}, ... .<ref name=Liu112>{{harvnb|Liu|1985|loc=p. 112}}</ref>

The transitive closure of a relation is a transitive relation.<ref name=Liu112 />

The relation "is the birth parent of" on a set of people is not a transitive relation. However, in biology the need often arises to consider birth parenthood over an arbitrary number of generations: the relation "is a birth ancestor of" ''is'' a transitive relation and it is the transitive closure of the relation "is the birth parent of".

For the example of towns and roads above, {{math|(''A'', ''C'') ∈ ''R''*}} provided you can travel between towns {{mvar|A}} and {{mvar|C}} using any number of roads.