Section 14.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.
Theorem 14.3.1.
A relation \(R\) on a set \(X\) is transitive if and only if \(R^n \subseteq R\) for all positive integers \(n\text{.}\)
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
to be the set of all elements that are in at least one of the \(A_n\text{.}\)
Definition 14.3.2.
The transitive closure of a relation \(R\) on a set \(X\) is the relation
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.
Theorem 14.3.3.
Given a relation \(R\) on a set \(X\text{,}\) the relation \(R^n\) is precisely the set of all pairs \((x,y)\) such that there is an \(n\)-walk in \(R\) beginning at \(x\) and ending at \(y\text{.}\)
Example 14.3.4.
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.
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
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
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{.}\)
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