How to prove "If $R$ is transitive, then $R^n$ is transitive."?

4.9k Views Asked by At

I can understand $R^n$ is $R$'s subset, but I can't understand why $R^n$ is transitive,too. I used mathematical induction:

Basis step: Let $n = 2$. If $a R^2 b$, $b R^2 c$, I need to prove $a R^2 c$. Because $a R^2 b$, it follows that there exists $x \in A$ (assume $R$ is a relation on $A$) such that $a R x$ and $x R b$. From $R$'s transitivity we can get $a R b$. WLOF, we can get $b R c$. By relation's composition, $a R^2 c$ holds.

Inductive step: Assume $R^n$ is transitive, I need to prove $R^{(n+1)}$ is also transitive. That is, I need to prove if $a R^{(n+1)} b$ and $b R^{(n+1)} c$, then $a R^{(n+1)} c$. If $a R^{(n+1)} b$, then there exists $x$ such that $a R x$ and $x R^n b$. If $b R^{(n+1)} c$, then there exists $y$ such that $b R y$ and $y R^n c$.....

I don't know how to continue.

1

There are 1 best solutions below

2
On

In general, $R$ is transitive iff $R \circ R \subseteq R$. From this you can prove directly:

If $R,S$ are transitive relations on the same set which commute ($R \circ S = S \circ R$), then $R \circ S$ is transitive.

By induction, if $R_1,\dotsc,R_n$ are pairwise commuting transitive relations, then $R_1 \circ \dotsc \circ R_n$ is also transitive.