On my assignment it asks

Determine with reason if the binary relation is reflexive, symmetric, antisymmetric or transitive.

$$R = \{(a, b) \in \mathbb{Z} \times \mathbb{Z} \mid a \text{ is an integer multiple of }b\}$$

I believe it is reflexive because a number is a multiple of itself

But I think it is not symmetric because take $(12,3)$, $12$ is a multiple of $3$, so $(12,3)$ exists in $R$, but $3$ is not a multiple of $12$ therefore $(3,12)$ is not in $R$. Making it not symmetric

The part that I can't make up my mind is about is whether or not it's antisymmetric, our textbook says a binary relation $R$ on a set $A$ is antisymmetric if and only if $a,b \in R$ and both $(a,b)$ and $(b,a)$ are in $R$, then $a=b$.

And in that case would it be antisymmetric if I use $(1,1)$ as $(a,b)$? since $1$ is a multiple of $1$, then $(a,b)$ and $(b,a)$ are both in $R$, and $a=b$, making it antisymmetric?

I would really appreciate it if someone can help me out on this, thanks.

  • 4
    $\begingroup$ Consider $(a,-a)$ for $a \not=0$. $\endgroup$ – sqtrat Jun 2 '16 at 19:10
  • 3
    $\begingroup$ No, it is not enough to exhibit a single example. Because there could exist other $a,b$ such that $(a,b), (b,a)\in R$ while $a\ne b$. You must prove that $a|b\land b|a\implies a=b$. $\endgroup$ – Yves Daoust Jun 2 '16 at 19:12

You are correct about $R$ being reflexive and not symmetric.

However, you have not proved that it is antisymmetric. You have only given a case that is antisymmetric, namely $(1,1)$, but you would need to show that it is true for all cases. You would need to prove the following statement:

For all $(a,b)\in \mathbb{Z}\times \mathbb{Z}$ the following holds: If $(a,b)\in R$ and $(b,a) \in R$, then $a=b$.

However, you will not be able to prove the statement because it is false. To demonstrate that it is false you need only one counter example. Can you see why any case of the form $(-a,a)$, where $a\neq 0$ makes it false?

| cite | improve this answer | |
  • $\begingroup$ Oh I see, so when you say any case of the form (-a,a) where a is not 0 makes it false is because all numbers, including its negatives are a multiple of itself. so (-20, 20) are both multiples of itself but -20 is not equal to 20. And the same holds for all other integers. Am I on the right track? $\endgroup$ – notmyname Jun 2 '16 at 19:52
  • $\begingroup$ Exactly! $20$ is an integer multiple of $-20$ and $-20$ is an integer multiple of $20$, which means that $(20,-20)$ and $(-20,20)$ are both in $R$, but $20\neq -20$, so $R$ is not antisymmetric. $\endgroup$ – M47145 Jun 2 '16 at 19:59
  • $\begingroup$ And all you needed was one case to show that antisymmetry does not always hold in $R$, so $(20,-20)$ and $(-20,20)$ is a perfectly good pair and that's all you need. $\endgroup$ – M47145 Jun 2 '16 at 20:02

Let $(a,b) \in \mathbb{Z}^2$.

If $(a,b) \in R$, then $a = m b$ for some $m \in \mathbb{Z}$.

If $(b,a) \in R$, then $b = n a$ for some $m \in \mathbb{Z}$.

So if $(a,b), (b, a) \in R$ then $$ a = m b = m (n a) = (m n) a \iff m n = 1 \iff m = n = 1 \vee m = n = -1 $$ The first case means $a = b$ and the second means $a = -b$.

The second case gives us counter examples. e.g. $(1, -1) \in R$ and $(-1, 1) \in R$, but $-1 \ne 1$.

| cite | improve this answer | |

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.