Skip to main content

Section 13.3 Transitive closure

Composition takes the pairs \((x,y)\) and \((y,z)\) and returns \((x,z)\text{,}\) so you can already imagine how this would relate to transitivity. A transitive relation is one that contains all of its self-compositions.

Therefore, the smallest transitive relation containing \(R\) is the union of all of the \(R^n\text{.}\) It is time to break the cardinal rule of this book and talk about infinity. Consider the sequence of sets \((A_n)_{n=0}^\infty\text{.}\) Define the infinite union

\begin{equation*} \bigcup_{n=1}^\infty A_n = A_1 \cup A_2 \cup \cdots \end{equation*}

to be the set of all elements that are in at least one of the \(A_n\text{.}\)

Definition 13.3.2.

The transitive closure of a relation \(R\) on a set \(X\) is the relation

\begin{equation*} R^* = \bigcup_{n=1}^\infty R^n. \end{equation*}

Of course, in practice, we will not need to calculate infinitely many composites. You will be able to tell that there are no new pairs that would arise from a new composition.

The following comment makes it easier to conceptualize \(R^n\text{.}\) Recall a walk of length \(n\) is a sequence \((x_1, x_2, \ldots, x_{n+1})\) where \((x_i,x_{i+1}) \in R\text{.}\) We can call these \(n\)-walks for short.

Consider the set \(X=\{w,x,y,z\}\) and the relation \(R = \{(w,x), (x,y), (y,z), (z,y) \}\text{.}\) Construct \(R^*\text{.}\)

The original relation \(R\) is pictured with \(w\) related to \(x\text{,}\) \(x\) related to \(y\text{,}\) and \(y\) and \(z\) related to each other.
Figure 13.3.5.

The original relation \(R\) is pictured with \(w\) related to \(x\text{,}\) \(x\) related to \(y\text{,}\) and \(y\) and \(z\) related to each other.

We will find \(R^2\) and \(R^3\text{,}\) and the union of these with \(R\) will be the transitive closure.

To find \(R^2\text{,}\) find all of the pairs that are “two steps away” in the original relation. You may immediately name \((w,y)\) and \((x,z)\) as two such pairs, but there are two less obvious pairs: \((y,y)\) and \((z,z)\text{.}\) Recall from the last chapter that any time you have invertible pairs in a transitive relation, that symmetry must produce loops; because \(y\) is related to \(z\) and \(z\) is related to \(y\text{,}\) for the relation to be transitive \(y\) must be related to \(y\text{.}\) (Same for \(z\text{.}\)) Therefore

\begin{equation*} R^2 = \{(w,y), (x,z), (y,y), (z,z)\}. \end{equation*}
The original relation \(R\) is pictured with four new arrows: the arrow from \(w\) to \(y\text{,}\) from \(x\) to \(z\text{,}\) and the loops at \(y\) and \(z\text{.}\) The new arrows are in red.
Figure 13.3.6.

The original relation \(R\) is pictured with four new arrows: the arrow from \(w\) to \(y\text{,}\) from \(x\) to \(z\text{,}\) and the loops at \(y\) and \(z\text{.}\) The new arrows are in red.

The triple composite \(R^3\) consists of all the pairs that are “three steps away,” which at first glance is just \((w,z)\text{.}\) In fact, if we stopped here we would be correct about \(R^*\text{,}\) but we should be careful: because of the loops in \(R^2\) there are more pairs in \(R^3\text{.}\) For example, one iteration of \(R\) may take \(x\) to \(y\text{;}\) another takes \(y\) to \(z\text{;}\) and a third takes \(z\) back to \(y\text{.}\) Therefore the pair \((x,y)\) is in \(R^*\text{,}\) even though it is also in \(R\text{.}\) Check for yourself that

\begin{equation*} R^3 = \{(w,z), (x,y), (y,z), (z,y) \} \end{equation*}

is the set of all pairs that start and end 3-paths in the original relation.

The previous picture is reproduced with one new arrow in blue, the arrow from \(w\) to \(z\text{.}\)
Figure 13.3.7.

The previous picture is reproduced with one new arrow in blue, the arrow from \(w\) to \(z\text{.}\)

Verify on your own that \(R^4\) does not contain any pairs that aren't already in \(R\text{,}\) \(R^2\text{,}\) or \(R^3\text{.}\)

Finally, we take the union of these three sets to make

\begin{equation*} R^*= \{(w,x), (w,y), (w,z), (x,y), (x,z), (y,y), (y,z), (z,y), (z,z)\}. \end{equation*}