How to prove that $(R; S;R)^n \subseteq (R; S)^n;R$ for all $n \geqslant 1$.

Question

If $R; S$ be relations on a set $U$. Given $R$ is transitive.

How to prove that $(R; S;R)^n \subseteq (R; S)^n;R$ for all $n \geqslant 1$.

Answer 1

We want to show that $$ \overbrace{R;S;R;R;S;R;\cdots;R;R;S;R}^{S\text{ appears }n\text{ times}}\subseteq \overbrace{R;S;R;S;R;\cdots;S;R;S;R}^{S\text{ appears }n\text{ times}} $$ The normal way of doing that is to take an element of the left-hand set and show that it is an element of the right-hand set. So that is what we will do.

Assume $(x, y) \in (S;R;S)^n$. That means that there are $x_i, y_i, z_i$, with $1\leq i \leq n$ such that $$ xRx_1, \quad x_1Sy_1, \quad y_1Rz_1\\ z_1Rx_2, \quad x_2Sy_2, \quad y_2Rz_2\\ \vdots\\ z_{n-1}Rx_n, \quad x_nSy_n, \quad y_nRy $$ Now, every time we see $y_iRz_i$ and $z_iRx_{i+1}$ after one another, we can shorten that (since $R$ is transitive) into just $y_iRx_{i+1}$. That means we have the following chain of related elements: $$ xRx_1, \quad x_1Sy_1\\ y_1Rx_2, \quad x_2Sy_2\\ \vdots\\ y_{n-1}Rx_n, \quad x_nSy_n\\ \quad y_nRy $$ which you will recognize as confirmation that $(x, y) \in (R;S)^n;R$. We have therefore shown that any element in $(R;S;R)^n$ is also an element of $(R;S)^n;R$, which is to say that $(R;S;R)^n\subseteq (R;S)^n;R$.