# 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)$ ?

• What are $R^n$ and $tc(R)$? – Prahlad Vaidyanathan Dec 3 '13 at 10:54
• $tc(R)$ is the transitive closure of $R$ – gazok Dec 3 '13 at 10:57
• Welcome to Math.SE! Yes, it surely "has to do" with the transitive closure, but proving the countable union shown is a transitive relation comes first (we shouldn't call something a "transitive closure" that isn't transitive, should we?). Write down the definition of transitive relation and see what you can do with it here. – hardmath Dec 3 '13 at 11:24
• @hardmath - didn't get it, thanks anyway – gazok Dec 3 '13 at 19:57
• This doesn't have anything to do with the group, so I'm erasing the group-theory tag. Unless by $R^n$ you meant the power in the sense of group structure on $A^2$, but I doubt it. – tomasz Dec 4 '13 at 4:45

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:

1. $\cup_{n=1}^\infty R^n$ is a transitive relation that contains $R$
2. 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.