Is a Relation to a certain power composed with itself commutative?

Question

I'm doing some proof right now and I can't remember what my professor said in class regarding whether

$$R^n\circ R = R\circ R^n$$

for an arbitrary n.

Answer 1

There's definitely a worrying flavor to this - relation composition in general isn't commutative (can you find an explicit example of relations $A,B$ with $A\circ B\not=B\circ A$?), so why should commutativity hold in this case?

However, despite first appearances this isn't really a commutativity problem: the relevant property is associativity. Consider the case $n=2$. Then we're asking whether $(R\circ R)\circ R=R\circ (R\circ R)$. But this is exactly asking whether composition of relations is associative.

So, can you see how to use associativity to prove the general case? HINT: use proof by induction ... Incidentally, to actually make this fully rigorous you'll need to look back at the original precise definition of "$R^n$" - which may have felt unnecessarily complicated at the time to the extent that composition is "obviously" associative (you may have wondered "Why isn't it just '$R$ composed with itself $n$ times'? well, because that presupposes that that's not ambiguous, and that's exactly what you're proving here!).