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.
Theorem 13.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 13.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 13.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 13.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{.}\)
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 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.
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