Transitive closure

Definition

Let $R$ be a binary relation on a set $A$. The transitive closure of $R$ is the relation $R^{+}$ on $A$ such that $a \mathrel{R^{+}} b$ when there are $n \ge 1$ and $x_0, \dots, x_n \in A$ with $$a = x_0 \mathrel{R} x_1 \mathrel{R} x_2 \cdots x_{n-1} \mathrel{R} x_n = b.$$

Remarks

The relation $R^{+}$ is transitive, it contains $R$, and it is a subset of each transitive relation that contains $R$. It is also the intersection of all transitive relations on $A$ that contain $R$. Example: the transitive closure of "is a parent of" is "is an ancestor of".

Explanations

L1 human

The transitive closure adds all the shortcuts. In a graph, $a \mathrel{R^{+}} b$ means that there is a path of one or more arrows from $a$ to $b$.