A theorem on transitive relations

(IF:) Assume Rn?? R, for all n.

In particular, R2?? R, i.e. R?R?R.

To show that R is transitive, suppose aRb and bRc.

Then, by the definition of ?, a(R?R)c. Hence (as R?R?R), aRc.

Thus, aRb and bRc implies aRc, which means that R is transitive.

(ONLY IF:) Assume R is transitive.

Show, by mathematical induction, that Rn?? R for all n?1.

Basis: R1? R because, by the definition of powers, R1= R .

Inductive step: Assume Rn?? R. Show that then Rn+1?? R.

Indeed, let aRn?+1b. Then,by the definition of powers, a(Rn ? R)b.

This means that for some c, we have aRnc and cRb.

So, since Rn?? R, we have aRc and cRb.

Then, by the transitivity of R, aRb.

Thus, aRn?+1b implies aRb, which means Rn+1?? R.