0

There's a problem on my homework that asks if a "binary relation is transitive" and I'm really confused on how I should start this problem.

Most examples of proving transitivity online are of sets, but this question asks about the relation $R: R(x,y) = ∃k.9x + 15y = 21k$.

I know that the definition of transitivity is $∀x,y,z.R(x,y) ∧ R(y,z) → R(x, z)$. Can I use the variable $k$ as $z$?

the_fox
  • 5,805
Ellie Queens
  • 39
  • 1
    What you're looking to prove/disprove is that given $\exists k_1 : 9x+15y=21k_1$ and given $\exists k_2: 9y+15z=k_2$, can we say that $\exists k_3 : 9x+15z=21k_3$ ? – Theo C. Apr 29 '18 at 18:21
  • So in order to prove this statement, do k1, k2, and k3 have to be the same value? – Ellie Queens Apr 29 '18 at 18:30

1 Answers1

1

The problem is well posed only if we look for $k \in \mathbb{Z}$

Counterexample:

For $x=4, y=-1$ we have: $R(x,y): 9*4+15*(-1)=21*1$, so $k_1=1$

For $y=-1, z=2$ we have: $R(y,z):9*(-1)+15*2=21*1$, so $k_2=1$

But $R(y,z)$ implies that $\exists k_3:$

$9*4+15*2=66=21k_3$ which is simply not true.

MathematicianByMistake
  • 5,495