Proving that $\bigcup_{n=1}^{\infty }R^n$ is a transitive relation on A

Question

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

Answer 1

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.