Editing Transitive closure (section)

{{Short description|Smallest transitive relation containing a given binary relation}}
{{stack|{{Binary relations}}}}
{{About|the transitive closure of a binary relation|the transitive closure of a set|Transitive set#Transitive closure}}

In [[mathematics]], the '''transitive closure''' {{math|''R''{{sup|+}}}} of a [[homogeneous binary relation]] {{mvar|R}} on a [[set (mathematics)|set]] {{mvar|X}} is the smallest [[Relation (mathematics)|relation]] on {{mvar|X}} that contains {{mvar|R}} and is [[Transitive relation|transitive]]. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets {{math|''R''{{sup|+}}}} is the unique [[minimal element|minimal]] transitive [[superset]] of {{math|''R''}}.

For example, if {{mvar|X}} is a set of airports and {{mvar|x R y}} means "there is a direct flight from airport {{mvar|x}} to airport {{mvar|y}}" (for {{mvar|x}} and {{mvar|y}} in {{mvar|X}}), then the transitive closure of {{mvar|R}} on {{mvar|X}} is the relation {{math|''R''{{sup|+}}}} such that {{math|''x'' ''R''{{sup|+}} ''y''}} means "it is possible to fly from {{mvar|x}} to {{mvar|y}} in one or more flights".

More formally, the transitive closure of a binary relation {{mvar|R}} on a set {{mvar|X}} is the smallest (w.r.t. ⊆) transitive relation {{math|''R''{{sup|+}}}} on {{mvar|X}} such that {{mvar|R}} ⊆ {{math|''R''{{sup|+}}}}; see {{harvtxt|Lidl|Pilz|1998|p=337}}. We have {{math|''R''{{sup|+}}}} = {{mvar|R}} if, and only if, {{mvar|R}} itself is transitive.

Conversely, [[transitive reduction]] adduces a minimal relation {{mvar|S}} from a given relation {{mvar|R}} such that they have the same closure, that is, {{math|1=''S''{{sup|+}} = ''R''{{sup|+}}}}; however, many different {{mvar|S}} with this property may exist.

Both transitive closure and transitive reduction are also used in the closely related area of [[graph theory]].