Transitive closure

Y indicates that the column's property is always true for the row's term (at the very left), while ✗ indicates that the property is not guaranteed
in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric,
is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require the homogeneous relation${\displaystyle R}$ be transitive: for all ${\displaystyle a,b,c,}$ if ${\displaystyle aRb}$ and ${\displaystyle bRc}$ then ${\displaystyle aRc.}$
A term's definition may require additional properties that are not listed in this table.

In mathematics, the transitive closureR of a homogeneous binary relationR on a setX is the smallest relation on X that contains R and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets R is the unique minimal transitive superset of R.

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

More formally, the transitive closure of a binary relation R on a set X is the smallest (w.r.t. ⊆) transitive relation R on X such that R ⊆ R; see Lidl & Pilz (1998, p. 337). We have R = R if, and only if, R itself is transitive.

Conversely, transitive reduction reduces a minimal relation S from a given relation R such that they have the same closure, that is, S = R; however, many different S with this property may exist.

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