1

I have a question to prove: If relations R is transitive, than R^2 is transitive. In the answer the professor says that if R is transitive than:

R^2 is a subset of R (I understand why, this is the definision) Therefore, R^2*R^2 is a subset of R^2. This is the part I don't understand. Is this like a multipication of two sides in an equation?

Thank you.

Alan
  • 2,791
  • A relation $R$ on a set $A$ is a subset of the cartesian product, that is, $R\subset A\times A$. – Sigur Nov 15 '13 at 16:44

2 Answers2

1

You believe that $R^2=R\times R\subseteq R$. Therefore, $$R^2\times R^2=(R\times R)\times (R\times R)\subseteq R\times R=R^2$$

vadim123
  • 82,796
  • thank you, but I still don't understand why. Is this because every parethesses are a subset of R? – Alan Nov 15 '13 at 16:44
  • 1
    That's right, if $A\subseteq B$ and $C\subseteq D$, then $A\times C\subseteq B\times D$. – vadim123 Nov 15 '13 at 16:45
1

I believe that you mean $$ R^2=\{(x,z):\text{there exists $y$ such that $(x,y)\in R$ and $(y,z)\in R$}\} $$ In particular, since $R$ is transitive, from $(x,z)\in R^2$ it follows $(x,z)\in R$. Therefore $R^2\subseteq R$.

Now, suppose $$ (a,b)\in R^2,\quad (b,c)\in R^2. $$ Then, by definition, $(a,c)\in R^2$, since you know that $(a,b)\in R$ and $(b,c)\in R$.

egreg
  • 238,574