0
$\begingroup$

Let $R$ be the relation on $\Bbb{Z}$ such that $xRy$ if and only if $x-y=c$.

(a) Define $R^2$.

Can anyone help me with $R^2$? I am not sure where to start. From similar questions, I saw that it should be something like $\exists z: xRz \land zRy$.

In this case, $\exists z : x-z = c$ and $z-y=c$.

(b)Define $R^i$ for arbitrary $i\ge 1$.

(c)Define $R^*$, the transitive closure of $R$.

(d)Is $R$ an equivalence relation? Justify your answer.

(e)Is $R^*$ an equivalence relation? Justify your answer.

$\endgroup$
2
  • $\begingroup$ Let me see if I understand your relation correctly. You fix $c \in \Bbb{Z}$ and assert that $y + c$ is related to $y$ for each integer $y$ (and nothing else). $\endgroup$ Nov 24, 2013 at 7:13
  • $\begingroup$ Then for $R^2$, $y + 2c$ is related to $y$ for each $y \in \Bbb{Z}$ (and there are no other relations). You can probably see how this generalizes for $R^i$. $\endgroup$ Nov 24, 2013 at 7:16

1 Answer 1

2
$\begingroup$

You’re quite right that $x\,R^2\,y$ if and only if there is a $z\in\Bbb Z$ such that $x\,R\,z$ and $z\,R\,y$, and that this is the case if and only if there is a $z\in\Bbb Z$ such that $x-z=c=z-y$. Suppose that this is the case; then $$x-y=(x-z)+(z-y)=2c\;.$$ Conversely, suppose that $x,y\in\Bbb Z$, and $x-y=2c$. Let $z=x-c$; then $x-z=c$, so $x\,R\,z$, and $z-y=x-c-y=(x-y)-c=c$, so $z\,R\,y$. Thus, $x-y=2c$ if and only if $x\,R^2\,y$. Equivalently, $$R^2=\{\langle x,y\rangle:x-y=2c\}\;.$$

Similarly, $x\,R^3\,y$ if and only if there is a $z\in\Bbb Z$ such that $x\,R^2\,z$ and $z\,R\,y$. (You may have defined it the other way around: $x\,R^3\,y$ if and only if there is a $z\in\Bbb Z$ such that $x\,R\,z$ and $z\,R^2\,y$; if so, you’ll need to make some minor adjustments in what I’m about to say.) In other words, $z\,R^3\,y$ if and only if there is a $z\in\Bbb Z$ such that $x-z=2c$ and $z-y=c$. Now follow the pattern of the argument for $R^2$ to see exactly what $R^3$ is. Once you’ve done this, you should be able to see what $R^i$ is for any $i\ge 1$ (and even prove it by induction on $i$).

Transitivity of a relation $S$ says that if $x\,S\,y$ and $y\,S\,z$, then $x\,S\,z$. Informally, if the relation lets you ‘step’ from $x$ to $y$ and from $y$ to $z$, then it lets you step directly from $x$ to $z$. Now go back to $R$: if $x\,R\,y$ and $y\,R\,z$, the shortcut from $x$ directly to $z$ may not be in $R$, but it is in $R^2$. Thus, $R\cup R^2$ is a bit closer to being transitive than $R$ was. However, it may not contain all of its own shortcuts: it’s possible that $x\,R^2\,y$ and $y\,R\,z$, for instance, but $R\cup R^2$ doesn’t contain the shortcut from $x$ directly to $z$. If you handled $R^3$ correctly, you’ll be able to determine that it does contain that shortcut and many others that might be missing in $R\cup R^2$, so that $R\cup R^2\cup R^3$ comes even closer to being transitive. Now pursue this idea to its logical conclusion. Note, by the way, that we can express $R\cup R^2$ as

$$\begin{align*} R\cup R^2&=\{\langle x,y\rangle\in\Bbb Z\times\Bbb Z:x-y=c\text{ or }x-y=2c\}\\ &=\big\{\langle x,y\rangle\in\Bbb Z\times\Bbb Z:x-y\in\{c,2c\}\big\}\;; \end{align*}$$

you may find it useful to express $R\cup R^2\cup R^3$ in similar fashion.

For the last two parts of the question remember that equivalence relations are not just transitive but also reflexive and symmetric. You will have to split your answers into two cases, $c=0$ and $c\ne 0$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .