Proof: $R^n=R$ where $R$ is relation I have a problem with this exercise:
Proove that if $R$ is a reflexive and transitive relation then $R^n=R$ for each $n \ge 1$ (where $R^n \equiv \underbrace {R \times R \times R \times \cdots \times R} _{n \ \text{times}}$).
This exercise comes from my logic excercise book. The problem is that I've proven $R^n=R$ is false for $n=2$ and non-empty $R$.
Here is how I've done it:
Let's take $n=2$. $R$ is a relation so it's a set. $R^2$ is, by definition, a set of ordered pairs where both of their elements belong to $R$. But $R$ is a set of elements that belong to $R$ - I mean it's not the set of pairs of elements from $R$. So $R^2\neq R$.
Please tell me something about my proof and this exercise. How would you solve the problem?
 A: It is enought to prove   that if a relation $R$ is transitive and reflexive then $R^2=R.$
By definition of transitive realtion we have  that $R^2 \subseteq R.$  Let us prove that $R \subseteq R^2.$  Let $(a,b) \in R$. Since $R$ is reflexive then $(b,b) \in R$. Then by definition of composition we get  that $(a,b) \in R^2.$
Thus $R^2=R.$
A: The problem makes more sense if we assume that the $\times$ that appear in it is not the Cartesian product, but an unusual notation for composition of relations, which is more commonly notated with $\circ$:
$$ R\circ S = \{ \langle a,c\rangle \mid \exists b: \langle a,b\rangle\in S \land \langle b,c\rangle\in R \} $$
In that case we can indeed have $R\circ R=R$, for example if $R$ relates everything to everything -- and in particular this is true if $R$ is reflexive and transitive.
A: I think you got the definition of $R^2$ wrong. Here is the correct definition:
Let $R$ be a relation on the set $A$. Then $R^2$ is defined by
$$R^2 = \{(x,y)\ |\ \exists z\in A\text{ such that } (x,y)\in R\text{ and }(y,z)\in R\}.$$
So $R^2$ is not a set of ordered pairs of elements from $R$. It is a set of ordered pairs of elements from $A$, the same type of object as $R$.
For instance, if $R=\{(1,1),(1,2),(2,3)\}$, then $R^2=\{(1,1),(1,2),(1,3)\}$.
A: Sorry, that was my mistake. I haven't read my book carefully. There's small paragraph saying: for relations we define $R^1\equiv R$ and $R^{n+1} \equiv R^n\circ R$.
Thanks for help. Next time I will read all the definitions carefully before I post a problem here :)
