Finding Powers of Relations

Question

I have been trying to work on this question and this up to were I was able to go, but I am stuck and I do not know if I am going the right way.

Answer 1

Hint: From $x-y=c$ and $y-z=c,$ we cannot conclude that $x-z=c.$ However, we can we conclude that $x-z=2c.$ (Hence, we can only conclude that $R$ is transitive if $2c=c$--that is, if $c=0$.) There are a few nice ways to see this. The simplest by far (and the easiest to generalize so that you can prove things about $R^i$ in general) is to note that $$x-z=x-y+y-z=c+c=2c.$$ Alternatively, note that $x=y+c$ and $y=z+c,$ so $x=(z+c)+c=z+2c,$ so $x-z=2c.$ So, we see that:

• $(x,y)\in R$ if and only if $x-y=c$
• $(u,v)\in R^2$ if and only if $u-v=2c$

Does this give you any inkling of what we can say about $R^i$ for $i\ge 1$ in general?

Also, it is more saying that $(x,z)\in R^2$ is the same as saying $$\exists y\::(x\:R\:y\wedge y\:R\:z).$$ Saying $$(\exists y\::x\:R\:y)\wedge(\exists y\::y\:R\:z)$$ is the same as saying that $x$ is in the domain of $R$ and that $z$ is in the range of $R$. In general, this need not imply that $(x,z)\in R^2$ (though it is certainly implied by it, and the implication certainly holds true for this particular relation $R$). You have a similar problem with the two statements that follow it. They are both equivalent to your erroneous statement, but not to the statement $(x,z)\in R^2$.

Answer 2

How about:

$(x,y)\in R^i$ if and only if $\exists x_1,x_2,x_3\ldots,x_{i+1}$ with $x=x_1$ and $y=x_{i+1}$, and $(x_j,x_{j+1})\in R$ for each $1\leq j\leq i$.