how to prove transitivity

Question

I'm never really sure how to prove transitivity when it comes to relations. I know how to disprove transitivity, by simply providing a counter example.

For example, in this problem, I have to prove whether or not this relation is reflexive, symmetric/anti-symmetric, and transitive. The relation is defined as the relation $R$ on $\Bbb R$ (real numbers) where $aRb$ means $a = 1/b$ is an element of $\Bbb Z$ (integers).

I proved it was reflexive and that it was symmetric, but I don't know how to prove if this is transitive or not.

I also can't seem to find a counter example where it isn't transitive.

Answer 1

Suppose that $x\,R\,y$ and $y\,R\,z$. Then $x-y\in\Bbb Z$ and $y-z\in\Bbb Z$, and we want to show that $x-z\in\Bbb Z$. How might we get $x-z$ from $x-y$ and $y-z$? A little thought shows that we can add them: $x-z=(x-y)+(y-z)$, and the sum of two integers is an integer, so $x-z\in\Bbb Z$, and $x\,R\,z$. This shows that $R$ is transitive.

Added 22 February 2023: Please note that this is an answer to the question as it was originally asked: in that version $a\mathrel{R}b$ was defined to mean that $a-b\in\Bbb Z$. The $R$ of the current version is also transitive, but the argument is completely different.

Suppose that $x,y,z\in\Bbb R$, $x\mathrel{R}y$, and $y\mathrel{R}z$; then $x=\frac1y\in\Bbb Z$, and $y=\frac1z\in\Bbb Z$. In particular, both $y$ and $\frac1y$ are integers, so either $y=1$ or $y=-1$. In either case $y=\frac1y$, so $x=y=\frac1z$, $x\mathrel{R}z$, and $R$ is transitive.

That is, we have both $x\mathrel{R}y$ and $y\mathrel{R}z$ only when $x=y=z=1$ or $x=y=z=-1$, so those are the only cases in which we actually have to check transitivity. And in both of those cases we do have $x\mathrel{R}z$, so $R$ is transitive.

Answer 2

I also can't seem to find a counter example where it isn't transitive.

Indeed.

You prove transitivity by showing, for any $a,b,c$ in the domain, that $a\operatorname Rb$ and $b\operatorname Rc$ must entail that $a\operatorname Rc$.   That involves proving that a counter example cannot exist, either directly or indirectly (ie by a conditional proof, or a proof by reduction to absurdity).

---

• Begin with the definition for $\operatorname R$ as $\{\langle x,y\rangle\in\Bbb R^2: x-y\in\Bbb Z\}$
  • Assume, for arbitrary real values $a,b,c$, that $a\operatorname R b\wedge b\operatorname Rc$.
  • This assumption entails $a-b\in\Bbb Z$ and $b-c\in\Bbb Z$ by the definition.
  • That entails $(a-b)+(b-c)$ is the sum of two integers.
  • Of course $a-c=(a-b)+(b-c)$ by algebra.
  • Thus entailing that $a-c\in\Bbb Z$ by the additive closure of the integers.
  • Thus entailing that $a\operatorname R c$ by the definition for $\operatorname R$.
• Therefore $\forall a{\in}\Bbb R~\forall b{\in}\Bbb R~\forall c{\in}\Bbb R~(a\operatorname R b\wedge b\operatorname R c\to a\operatorname R c)$.
• Done.   Our $\operatorname R$ is transitive.