Proving that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on A Let $R$ be a relation on set $A$.
How can i prove that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on $A$?
Maybe it has to do with $\bigcup_{n=1}^{\infty }R^n=tc(R)$ ?
 A: An incisive Comment by @PrahladVaidyanathan asks what $R^n$ and $tc(R)$ are.  The first step is to give them a definition, one that allows the desired conclusion(s).
If $R,S$ are relations on a set $A$, their composition $S \circ R \subseteq A\times A$ is the relation:
$$ S\circ R = \{(x,z)\in A\times A : \exists y \in A \text{ s.t. } (x,y) \in R \text{ and } (y,z) \in S \} $$
Composition of relations generalizes function composition and shares the associativity of that more familiar construct.
Then $R^n$ is simply defined to be the $n$-times composition of $R$ with itself, with the convention that $R^1 = R$.
We say that $\overline{R}$ is the transitive closure of $R$ iff (1) $\overline{R}$ is a transitive relation on $A$ s.t. $R \subseteq \overline{R}$, and (2) for any transitive relation $S$ with $R \subseteq S$, also $\overline{R} \subseteq S$.  This state of affairs is often summarized by saying $\overline{R}$ is the smallest transitive relation containing $R$.  We thus define the notation $tc(R) = \overline{R}$.
To show that $\cup_{n=1}^\infty R^n = tc(R)$ involves two demonstrations:


*

*$\cup_{n=1}^\infty R^n$ is a transitive relation that contains $R$

*Any transitive relation $S$ that contains $R$ also contains $\cup_{n=1}^\infty R^n$.


Sketch of proof (1):  The union includes $R^1 = R$ with $n=1$, so consider transitivity.  If $(x,y) \in \cup_{n=1}^\infty R^n$ and $(y,z) \in \cup_{n=1}^\infty R^n$, then there exist finite indexes $m,k$ s.t. $(x,y) \in R^m$ and $(y,z) \in R^k$.  By the definition of composition, $(x,z) \in R^{m+k} \subseteq \cup_{n=1}^\infty R^n$.  Thus the union is a transitive relation.
Sketch of proof (2):  For any transitive relation $S$ that contains $R^1 = R$, it can be shown by induction that each $R^n \subseteq S$.  The inclusion $\cup_{n=1}^\infty R^n \subseteq S$ follows.
