Vtyjkyuk

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.

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.

The left part is :
if $(a,b) in R $ and $(b,c) in R => (a,c) in R. $ ---1.1

if n = 1, then $R^n = R^1$ is transitive.

Assume $R^n$ is transitive, we want to prove $R^n + 1$ is transitive.

Because $R^n$ is transitive, we can know that

if $(a,b) in R^n $ and $(b,c) in R^n => (a,c) in R^n$ . --- 1.2

What we want is if $(a,b) in R^n+1 $ and $(b,c) in R^n+1 => (a,c) in R^n+1$ . ---1.3

By definition, $R^n+1 = R^n circ R$ --- 2.1

And if R is transitive, then $R^n subseteq R$. --- 2.2

In conclusion,

if $(a,b) in R^n+1 $ and $(b,c) in R^n+1$

=> if $(a,m1) in R $ and $(m1,b) in R^n$ and $(b,m2) in R$ and $(m2,c) in R^n$ //use 2.1

=> if $(a,m1) in R $ and $(m1,b) in R$ and $(b,m2) in R$ and $(m2,c) in R^n$ //use 2.2

=> if $(a,m2) in R $ and $(m2,c) in R^n$ // R is transitive

=> $ (a,c) in R^n+1 $ // use 2.1

#

So combine 1.1 and 1.2 we can prove 1.3.

We know: $R$ is transitive iff $R^nsubseteq R$ for $n=1,2,3,dots.$

To prove: If $S$ is transitive, $S^n$ is also transitive for $n=1,2,3,dots.$

Say $S$ is a relation on $A$. Suppose $S^n$ is transitive for some $nge1$. Let $(a,b), (b,c)$ both in $ S^n+1$ and $x,yin A$, so

$$beginalign
(a, x)&in S\
(x, b)&in S^nsubseteq S
endalign$$

and

$$beginalign
(b, y)&in S\
(y, c)&in S^nsubseteq S
endalign,$$

now since $(a,x),(x,b),(b,y)$ are in $S,$ $(a,y)in S,$ so by definition

$$(a,c)in S^n+1,$$

which should complete the induction part of the proof.