Proof: $R^n=R$ where $R$ is relation

Question

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?

Note that it is $...$ for math mode, not &...&. – hmakholm left over Monica Nov 27 '15 at 20:52 — hmakholm left over Monica, Nov 27 '15 at 20:52
Yes, it was my quite funny mistake ;) – Bartłomiej Sługocki Nov 27 '15 at 20:56 — Bartłomiej Sługocki, Nov 27 '15 at 20:56

Leox · Answer 1 · 2015-11-27T21:02:28.210

1

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.$

edited Nov 27 '15 at 21:02

answered Nov 27 '15 at 20:55

Leox

8,120

score 1 · Accepted Answer · answered Nov 27 '15 at 20:57

1

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.

answered Nov 27 '15 at 20:57

hmakholm left over Monica

286,031

But $\times$ is, unfortunetely, Cartesian product here. – Bartłomiej Sługocki Nov 27 '15 at 20:59
1

@BartłomiejSługocki: What makes you certain of that? I would sooner believe that there's a typo in the exercise than you're actually being asked to prove something nonsensical that is usually not true. – hmakholm left over Monica Nov 27 '15 at 21:01

score 1 · Answer 3 · answered Nov 27 '15 at 20:59

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)\}$.

score 0 · Answer 4 · answered Nov 27 '15 at 21:13

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 :)

Proof: $R^n=R$ where $R$ is relation

4 Answers4