Editing Transitive closure (section)

== Existence and description ==
For any relation ''R'', the transitive closure of ''R'' always exists. To see this, note that the [[intersection (set theory)|intersection]] of any [[indexed family|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
:<math>R^{+}=\bigcup_{i = 1}^{\infty} R^i.</math>
where <math>R^i</math> is the ''i''-th power of ''R'', defined inductively by
:<math>R^1 = R</math>
and, for <math>i>0</math>,
:<math>R^{i+1} = R \circ R^i</math>
where <math>\circ</math> denotes [[composition of relations]].

To show that the above definition of ''R''<sup>+</sup> 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.

* <math>R \subseteq R^{+}</math>: <math> R^+</math> contains all of the <math> R^i</math>, so in particular <math> R^+</math> contains <math> R</math>.
* <math> R^{+}</math> is transitive: If <math>(s_1, s_2), (s_2, s_3)\in R^+</math>, then <math>(s_1, s_2)\in R^j</math> and <math>(s_2, s_3)\in R^k</math> for some <math>j,k</math> by definition of <math>R^+</math>. Since composition is associative, <math>R^{j+k} = R^j \circ R^k</math>; hence <math>(s_1, s_3)\in R^{j+k} \subseteq R^+</math> by definition of <math>\circ</math> and <math>R^+</math>.
* <math>R^{+}</math> is minimal, that is, if <math>T</math> is any transitive relation containing <math>R</math>, then <math>R^{+} \subseteq T</math>: Given any such <math>T</math>, [[mathematical induction|induction]] on <math>i</math> can be used to show <math>R^i\subseteq T</math> for all <math>i</math> as follows: ''Base:'' <math>R^1 = R \subseteq T</math> by assumption. ''Step:'' If <math>R^i\subseteq T</math> holds, and <math>(s_1, s_3)\in R^{i+1} = R \circ R^i</math>, then <math>(s_1, s_2) \in R</math> and <math>(s_2, s_3)\in R^i</math> for some <math>s_2</math>, by definition of <math>\circ</math>. Hence, <math>(s_1, s_2), (s_2, s_3)\in T</math> by assumption and by induction hypothesis. Hence <math>(s_1, s_3)\in T</math> by transitivity of <math>T</math>; this completes the induction. Finally, <math>R^i\subseteq T</math> for all <math>i</math> implies <math>R^{+} \subseteq T</math> by definition of <math>R^{+}</math>.