1

Consider the relation on R on the reals where $xRy$ iff $xy=1$

I need to find $R^2, R^3, R^i $ and $R^*$

Ok, so I first started off with the following:

$$xR^2z \equiv \exists y: xRy\land yRz \\ \equiv\exists y: xy=1 \land yz=1 \\ \equiv xy + yz =y(x+z)=2$$

This to me doesn't seem right. Does the $\land$ represent addition in cases where you' re trying to find compositions of $R$ ? How would I find $R^3$ in this case? If my assumption of $R^2 = y(x+z)=2$ is correct, then would $R^i = yi(x+z)=2$ for some $i\ge1$?

I'm getting confused with the definition of $R \circ R$ and have a hard time applying it for $i\gt2$ and subsequent compositions.

Another point of confusion is with $R^*$. Given:

$$R^*= R\cup R^2 \cup R^3 \cdots\cup R^n = \bigcup_{i=1}^n R^n $$

How would you define what it $R^*$ look like if the set is infinite? Suppose we had $n=3$ then you would have 3x3 matrix and in this case $R^*=R\cup R^2 \cup R^3$. At this point if you're final matrix $R^3$ differs from $R$ then it's said that it wouldn't be transitive.

Dimitri
  • 1,287

1 Answers1

0

The definition of $R \circ S$ is: $x(R \circ S)z$ if and only if there exists a $y$ such that $xRy$ and $ySz$.

This symbol $\wedge$ is not a plus! It means "and", and like the name suggests, it means both statements must be true.

So, to the actual problem. Say $xR^2z$. Then there exists a $y$ such that $xy = 1$ and $yz = 1$. This implies $y = \frac{1}{x}$ and $y = \frac{1}{z}$. Because both are true, $\frac{1}{x} = \frac{1}{z}$, which means $x = z$. So $xR^2z$ iff $x = z$.

For $R^3$: Say $xR^3z$. Then there exists some $y$ such that $xR^2y$ and $yRz$. But we know that $xR^2y$ implies $y = x$. So we substitute into the second and get $xRz$. So $xR^3z$ iff $xRz$ (which makes intuitive sense, composing with $R^2$, the $=$ relation, shouldn't do anything)

To define $R^\ast$ when $n$ is infinite, you have $R^\ast = \bigcup_{i = 1}^\infty R^i$. In a union, you keep all the elements, so this means: $xR^\ast y$ iff $xR^i y$ for some $i$. In this case, we know that $xR^iy \iff xy = 1$ or $x = y$, depending if $i$ is even or odd. But $R^\ast$ is still transitive. Can you verify that?

Henry Swanson
  • 12,972
  • Okay, I'm trying to figure out this part: $\exists y: xy=1 \land yz=1$ . Basically we're trying to find a $y$ so that it would make this first part of the statement true, and then once you find that $y$, you substitute it into the the second part in order to find your $z$ ? – Dimitri Dec 04 '13 at 18:53
  • Almost. You're given $x$ and $z$ at the beginning. Then you look for a $y$. If you can find a $y$ that both statements are true, then $xR^2z$ is true. If you can't, then it's false. – Henry Swanson Dec 04 '13 at 19:19
  • Right, yes, both have to be true because of $\land$. But when you have something like $x^2 \le y \land y^2 \le z$, how is it we get $x^4 \le z$. Our $y$ needs to be squared to satisfy both parts, so how is it our $x^2$ become $x^4$? Meaning $x^{2n}$. – Dimitri Dec 04 '13 at 19:25
  • Yeah, then you substitute. – Henry Swanson Dec 04 '13 at 19:58