Reflexive and transitive relations

Question

In reviewing some old homework assignments, I found two problems that I really do not understand, despite the fact that I have the answers.

The first is: R(x, y) if y = 2^d * x for some nonnegative integer d. What I do not understand about this relation is how it can possibly be transitive (according to my notes it is). My understanding is that if the relation were transitive, the following would apply: if y = 2^d * x and x = 2^d * z, then y = 2^d * z. That seems impossible unless x = z. Am I missing something?

The second is: R(x, y) if x and y are both divisible by 17. What I do not understand about this relation is why it is not reflexive. My understanding is that if the relation is reflexive, if x is divisible by 17 then both x and x are divisible by 17. I think that I am possibly applying the quality of reflexiveness incorrectly to this relation, but I am not quite sure.

Thank you for any help in correcting these misunderstandings!

Answer 1

For your first relation, note you're allowed to use a different $d$ each time. So if $y = 2^dx$ and $x = 2^{d'} z$ then $y = 2^{d + d'} z$ so $R(y, z) $.

For your second relation, we need $R(x, x) $ for all $x$ in order to be reflexive, but (for example) 1 will not be related to 1 for this relation.

Answer 2

For the first problem: the integer $d$ is not fixed. And indeed, if $y = 2^d x$ and $x = 2^e z$ you get $y = 2^f z$ for $f=d+e$.

For the second problem: reflexivity means that for all $x$, $R(x,x)$. But if $x$ is not divisible by $17$, this does not hold!

Answer 3

1. If $x\mathop Ry$ and $y\mathop Rz$, then there are non-negative integers $d$ and $d'$ such that $y=2^dx$ and $z=2^{d'}y$. Therefore, $z=2^{d+d'}x$ and, since $d+d'$ is a non-negative integer, $x\mathop Rz$.
2. No, it is not reflexive. For instance, $1\not\mathop R1$.

Answer 4

Recall that the first relation has to hold for $\textit{some}$ integer $d$. Can you find it, given the ones that relate x to y and y to z?

For the second: x is related to x if and only if x and x are divisible by 17, which is the same as x being divisible by 17. This need not be true, right?

Hope this helps

Answer 5

What your missing where it concerns transitivity of $R$ is the fact that $d$ is not necessarily the same for each pair $x,y$ with $\langle x,y\rangle\in R$.

If $y=2^dx$ and $x=2^{d'}z$ for nonnegative integers $d,d'$ then $y=2^{d+d'}z$ for nonnegative integer $d+d'$.

---

The second relation you mention is not reflexive because we don not have $\langle x,x\rangle\in R$ for every $x$ (preassuming that $R$ is a relation on the set of integers).

E.g. $\langle 3,3\rangle\notin R$ since $3$ is not divisible by $17$.