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

  • 2
    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
  • 1
    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
up vote 2 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.