1
$\begingroup$

I am trying to understand if the relation $x \geq 2y$ is transitive. I think the answer is no for the following reasons. Can someone please let me know if I am correct or incorrect. If incorrect, why am I incorrect.

Definition of transitive: If $\left ( x,y \right )$ are elements of the relation, and $\left ( y,z \right )$ are elements of the relation, then this implies that $\left ( x,z \right )$ are elements of the relation.

Here is a counter example: $\left ( 4,2 \right )$ are elements of the relation because $4 \geq 2\times 2$. $\left ( 2,1 \right )$ are also elements of the relation because $2 \geq 2\times 1$. But, $\left ( 4,1 \right )$ are not elements of the relation because $4$ is not greater than or equal to $2 * 1$.

$\endgroup$
  • 7
    $\begingroup$ But 4 is greater than or equal to $2 \cdot 1 = 2$. $\endgroup$ – Julia Jackson Aug 6 '15 at 13:46
  • 3
    $\begingroup$ At the very end of the question you claim that $4$ isn't greater than (or equal to) $2$. Do you see something wrong with this? $\endgroup$ – Git Gud Aug 6 '15 at 13:46
  • 1
    $\begingroup$ Ok. Now I feel stupid. I guess it's a case where I'm not seeing the forest through all the trees. Thanks for answering. $\endgroup$ – user3457456 Aug 6 '15 at 13:58
1
$\begingroup$

$$x\ge2y\land y\ge2z\implies x\ge2y\land 2y\ge4z\implies x\ge 4z\implies x\ge2z.$$

Update: The last implication requires $z\ge0$.

$\endgroup$
  • $\begingroup$ This assumes, of course, that $x,y,z \geq 0$ $\endgroup$ – Omnomnomnom Aug 6 '15 at 13:58
  • $\begingroup$ @Omnomnomnom: no, why ? $\endgroup$ – Yves Daoust Aug 6 '15 at 14:00
  • $\begingroup$ Take $x = -3$, $z = -1$. We have $x \geq 4z$, but not $x \geq 2z$. $\endgroup$ – Omnomnomnom Aug 6 '15 at 14:00
  • $\begingroup$ Yep, stupid me, we need $4z\ge2z$. (But $x$ and $y$ can be negative.) $\endgroup$ – Yves Daoust Aug 6 '15 at 14:02
  • $\begingroup$ @Crostul your comment is good! Use \neg rather than \not. $\endgroup$ – Omnomnomnom Aug 6 '15 at 14:02
1
$\begingroup$

What set is your relation defined on? If it's for positive numbers, then it is transitive, as Yves Daoust showed.

If the numbers can be negative, we could have: $$x = -3, y =-\frac{7}{4}, z = -1$$ Then $x = -3 \geq-3.5 =2y$, $y =-\frac{7}{4} \geq -2 = 2z$, but $x = -3 < -2 = 2z$.

$\endgroup$
  • $\begingroup$ It only occurs because of $z<0$. $\endgroup$ – Yves Daoust Aug 6 '15 at 14:07
  • $\begingroup$ It seems to work if $x$ is non-negative. Suppose $x\geq 0$, and we have that $x\geq 2y$ and $y\geq 2z$, and $z < 0$. Then $x \geq 0 > 2z$. $\endgroup$ – Santeri Aug 6 '15 at 14:31
  • $\begingroup$ The original problem I was working on was defined on the naturals but I am very appreciative that you showed how the relation is not transitive if it includes negative numbers. $\endgroup$ – user3457456 Aug 6 '15 at 14:42
  • $\begingroup$ @Santeri: the transitivity can only be falsified when $z<0$, irrespective of the signs of $x$ and $y$. $\endgroup$ – Yves Daoust Aug 6 '15 at 15:38
  • $\begingroup$ I agree. I thought you meant 'if and only if' with your first comment. It's a necessary but not sufficient condition. $\endgroup$ – Santeri Aug 6 '15 at 15:49
0
$\begingroup$

Your relation is not transitive, since it fails to be transitive when you work with negative numbers. As an example, $$-4 \ge 2 \cdot (-2) \mbox{ and } -2 \ge 2 \cdot (-1)$$ but $$-4 \ge 2 \cdot (-1) \mbox{ is false}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.