Transitive closure of a finite relation

Question

If $R$ is a relation on $A$, we know that the relation $$T=R\cup R\circ R\cup R\circ R\circ R\cup\cdots$$ is know as the transitive closure of a relation and it is the smallest transitive relation containing $R$. It is almost trivial to prove that it is the smallest transitive relation containing $R$. But further it says that if $\vert A\vert =n$, then the transitive closure of $R$ is $$T=R\cup R\circ R\cup R\circ R\circ R\cup\cdots\cup (R\circ R\circ \cdots \circ R)$$ where the last composition is $n-1$ times. Now, I am finding it difficult to prove that this relation is transitive.

Please help

Answer 1

It suffices to prove that $R^{(n)}$ is contained in $\bigcup_{0 \leqslant i \leqslant n-1}R^{(i)}$.

Proof. Suppose that $x \mathrel{R^{(n)}} y$. Then there is a chain $x= x_0 \mathrel{R} x_1 \mathrel{R} x_2\ \dotsm \ \mathrel{R} x_n = y$. Since $|A| = n$, two of the $x_i$'s are equal and hence the chain can be shortened.

Answer 2

Given any relation $R$ on $A$, the transitive closure may as well be described as the set $T$ consisting of all pairs $(a,b)\in A\times A$ such that there exists a finite sequence of elements $$ a=a_0, a_1, a_2, \dots, a_{k-1}, a_k = b \in A $$ with $$ (a_0,a_1), (a_1,a_2), (a_2,a_3), \dots, (a_{k-1}, a_k) \in R. $$ Note that when such a sequence exists for a given pair $(a,b)$, it follows that there also exists such a sequence without repetitions, since you can just remove the subsequence between the repeating elements.

Hence, you may describe the transitive closure $T$ as the set of all pairs $(a,b)$ such that there exists a non-repeating sequence in $A$ with the above property.

Now if $|A|=n$, the maximal length of a non-repeating sequence in $A$ is $n$ and hence for the transitive closure it is enough to include only up to $(n-1)$-fold compositions of elements in $R$.