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$.
Asked
Active
Viewed 38 times
0
-
What does $(R;S;R)$ mean? – Arthur Oct 30 '15 at 12:13
-
; means composition here – TechJ Oct 30 '15 at 13:01
-
Ok, I've got a proof. Before I write it down, though: which "direction" have you defined composition of relations? Does $(x,y)\in R;S$ mean that there is a $z$ such that $xRz$ and $zSy$ (the intuitive way), or such that $zRy$ and $xSz$ (which fits the notation for function composition)? – Arthur Oct 30 '15 at 13:24
-
I guess the 1st one is what I require. – TechJ Oct 30 '15 at 13:49
1 Answers
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$.
Arthur
- 199,419