For any relation
R, the transitive closure of
R always exists. To see this, note that the
intersection of any
family of transitive relations is again transitive. Furthermore,
there exists at least one transitive relation containing
R, namely the trivial one:
X ×
X. The transitive closure of
R is then given by the intersection of all transitive relations containing
R. For finite sets, we can construct the transitive closure step by step, starting from
R and adding transitive edges. This gives the intuition for a general construction. For any set
X, we can prove that transitive closure is given by the following expression :R^{+}=\bigcup_{i = 1}^{\infty} R^i. where R^i is the
i-th power of
R, defined inductively by :R^1 = R and, for i>0, :R^{i+1} = R \circ R^i where \circ denotes
composition of relations. To show that the above definition of
R+ is the least transitive relation containing
R, we show that it contains
R, that it is transitive, and that it is the smallest set with both of those characteristics. • R \subseteq R^{+}: R^+ contains all of the R^i, so in particular R^+ contains R. • R^{+} is transitive: If (s_1, s_2), (s_2, s_3)\in R^+, then (s_1, s_2)\in R^j and (s_2, s_3)\in R^k for some j,k by definition of R^+. Since composition is associative, R^{j+k} = R^j \circ R^k; hence (s_1, s_3)\in R^{j+k} \subseteq R^+ by definition of \circ and R^+. • R^{+} is minimal, that is, if T is any transitive relation containing R, then R^{+} \subseteq T: Given any such T,
induction on i can be used to show R^i\subseteq T for all i as follows:
Base: R^1 = R \subseteq T by assumption.
Step: If R^i\subseteq T holds, and (s_1, s_3)\in R^{i+1} = R \circ R^i, then (s_1, s_2) \in R and (s_2, s_3)\in R^i for some s_2, by definition of \circ. Hence, (s_1, s_2), (s_2, s_3)\in T by assumption and by induction hypothesis. Hence (s_1, s_3)\in T by transitivity of T; this completes the induction. Finally, R^i\subseteq T for all i implies R^{+} \subseteq T by definition of R^{+}. == Properties ==