A theorem on transitive relations
Theorem: The relation R on a set A is transitive iff Rn? ? R for all n.
(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.