I'm currently preparing for my maths exam and one of the questions is to check whether or not a relation is transitive or not. I'm unsure on how to check if there is a transitive relation given an equation.

The questions I would be getting is like this.

Let $Q$ denote the relation on set $\mathbb Z$ of integers, where integers $x$ and $y$ satisfy $xQy$ if and only if

$$x - y = x^2 + y^2 - 2xy$$

I know how to figure out if it is symmetric and reflexive but I'm unsure on how to check the transitive part. Any help is appreciated, thank you.

  • $\begingroup$ $1Q0$,$2Q1$ but $2$ isn't related to $0$. $\endgroup$ – астон вілла олоф мэллбэрг Apr 11 '16 at 13:08
  • 1
    $\begingroup$ Hint: $x^2+y^2-2xy=(x-y)^2$ $\endgroup$ – Noy Soffer Apr 11 '16 at 13:09
  • $\begingroup$ Best way to approach problems like this is to start with some examples. In this case, the failure of transitivity becomes clear pretty fast. $\endgroup$ – lulu Apr 11 '16 at 13:12
  • $\begingroup$ I'm not sure if this how it is done but this is my way of going about it 1Q2 = (1-2)^2 = 1 2Q3 = (2-3)^2 = 1 1Q3 = (1-3)^2 = 4 so therefore x is not a relation to z, so it's not transitive? $\endgroup$ – MVantastic Apr 11 '16 at 13:22
  • 1
    $\begingroup$ It doesn't make sense to write "$1Q2 = \ldots$". The notation $xQy$ in this context is shorthand for "$x$ is related to $y$", so you're effectively saying, "$1$ is related to $2 = (1-2)^2 \ldots$", which is ungrammatical, so to speak. A correct way to write it would be, for example, "$1Q2$ since $1-2 = 1^2+2^2-2\cdot1\cdot2$." $\endgroup$ – Théophile Apr 11 '16 at 13:45

If the question is "Is this relationship transitive?" then you need a little bit of gut feeling to get started. If you suppose that it is transitive, then you'll need a general proof. If you think it's not transitive, then one example will suffice.

As noted by Noy Soffer, $x^2 + y^2 - 2xy = (x - y)^2$. We thus have $xQy$ if and only if $x - y = (x - y)^2$. For this, it is sufficient that $x = y$ (hence the relation is reflexive, as you probably already noticed). If $ x \neq y$, then we can divide both sides of the equation by $x - y$ and get $ 1 = x - y$. We conclude that $xQy$ means that one of the following hold $$ x - y = 1 \text{ or } x = y $$

That's just the basic analysis. Now what's your intuition? If the relationship would be transitive, then if $x - y = 1$ and $y - z = 1$, we would have to conclude that either $x - z = 1$ or that $x = z$. Can you find examples of $x, y$ and $z$ for which $x - y = 1$, $y - z = 1$, but neither $x = z$ nor $x - z = 1$? If so, then you've proven it's not transitive. If you can't seem to find counterexamples, then maybe the relationship is transitive. In that case, try proving that $x - y = 1$ and $y - z=1$ implies either $x - z =1$ or $x = z$. Let me know what you find.

  • 1
    $\begingroup$ If x = 3, y = 2 and z =1 we would have 3-2 = 1, 2-1 = 1 but 3 != 1 and 3-1 != 1 so therefore it's not transitive? $\endgroup$ – MVantastic Apr 11 '16 at 13:40
  • $\begingroup$ You got it! Good luck with your exam. $\endgroup$ – Bib-lost Apr 11 '16 at 14:18
  • $\begingroup$ Thanks a lot for the help! $\endgroup$ – MVantastic Apr 11 '16 at 15:17

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.