0

Let $\sim$ be define so that $a\sim b$ exactly when $a \times b$ is divisible by $3$. Is this an equivalence relation? If not, which of the three properties (reflexive, symmetric, transitive) does not hold?

Solution:

We need to test each of the following cases to see if they hold.

Here are my assumptions: $a\times b$ is divisible by $3$ in the following cases:

  • Case 1: $3\mid a $, and $3\nmid b$. Example: $a=3, b=2, a\times b=6$
  • Case 2: $3\nmid {a}$, and $3\mid b$. Example: $a=2, b=3, a\times b=6$
  • Case 3: $3\mid a$, and $3\mid b$. Example: $a=3, b=3, a\times b=9$

Reflexive Test:

  • $aRa: = \{(a,a): 3\mid a\times a\}$
  • $bRb: = \{(b,b): 3\mid b\times b\}$

This fails in $aRa$ when $a$ is not divisible by $3$ according to case 1. This also fails in $bRb$ when $b$ is not divisible by $3$ according to case 2.

Symmetric Test:

  • $aRb: = \{(a,b): 3\mid a\times b\}$
  • $bRa: = \{(b,a): 3\mid b\times a\}$

This works because if $a\times b$ is divisible by $3$, then $a$ is divisible by $a\times b$ and $b$ is divisible by $b\times a$.

Transitive Test: Honestly I am not exactly sure how to describe the relation here, since we need $a$, $b$ and $c$.

What is $c$ in this case, is it the result of $a\times b$?

Am I on the right track?

lucidgold
  • 1,054
  • $aRa$ is false if $3$ doesn't divide $a$. – GNUSupporter 8964民主女神 地下教會 Dec 07 '15 at 04:51
  • 2
    Strictly speaking, this question isn't well-posed - you need to specify a domain for the relation. Presumably the domain is the natural numbers, but this matters: if we take for instance the domain to be ${3}$, then the relation is an equivalence relation. – Noah Schweber Dec 07 '15 at 04:57
  • Well, this question comes from a book word-for-word. I did not modify it, for me is self-study. If the question is out of the this sites scope, I do not mind removing it. – lucidgold Dec 07 '15 at 05:00
  • @NoahSchweber: You said a very well point. Indeed, what I was thinking about it is that point. – Mikasa Dec 07 '15 at 05:00
  • 1
    @lucidgold This question is definitely appropriate for this site, and I didn't mean my comment as a criticism of you, just the question. I hope I don't come off as overly critical. I think my main advice is, go a bit more slowly, and think about what the definitions of "reflexive", "symmetric", "transitive" actually mean, before trying to solve the problem right off the bat. EDIT: Oh, I see, I wrote "you need to . . ." - I meant the abstract 'you' there :P, i.e., "one needs to . . ." – Noah Schweber Dec 07 '15 at 05:02
  • Understood. The book has many vague moments, and it doesn’t have a great rating (2.5) on amazon: http://www.amazon.com/Discrete-Mathematics-Ducks-Sarah-Marie-Belcastro/dp/1466504994 – lucidgold Dec 07 '15 at 05:04
  • x is always in relation with 3m and 3m is always in relation with y but xy can be non-divible by 3, so there is not transitivity – Piquito Dec 07 '15 at 17:26

3 Answers3

3

I think you're making things more complicated by using notation, rather than thinking about what the question means.

Reflexivity. Is it the case that, for every number $a$, $a^2$ is divisible by $3$? If yes, then the relation is reflexive. If no, then the relation is not reflexive.

Symmetry. Is it the case that, if $ab$ is divisible by $3$, then $ba$ is divisible by $3$? If yes, then the relation is symmetric. If no, then the relation is not symmetric.

Transitivity. Is it the case that, if $ab$ is divisible by $3$ and $bc$ is divisible by $3$, then $ac$ is divisible by $3$? If yes, then the relation is transitive. If no, then the relation is not transitive.

Do you see the answers to these questions?

Note that these questions are just translations, into words, of the usual formal definition. E.g., $R$ is reflexive iff for every $a$, we have $aRa$. In this case, "$xRy$" means "$xy$ is divisible by $3$," so the question "Is $R$ reflexive?" is the same as the question "Is it the case that, for every $a$, $a^2$ is divisible by $3$?"

Noah Schweber
  • 245,398
  • How do I "modify" the original relation to include $c$ so I can test for the Transitivity case? How does $c$ fit? – lucidgold Dec 07 '15 at 04:58
  • I don't understand what you mean by "modify the original relation to include $c$". To test if $R$ is transitive, you ask, "Is it the case that - for any $a, b, c$ - if $aRb$ and $bRc$, then $aRc$?" I think you're trying to jump straight to an algorithm for solving this type of problem, without thinking about what it means for long enough. – Noah Schweber Dec 07 '15 at 05:00
0

$3$ is prime, so $a\sim b \iff 3|ab \iff 3|a \text{ or } 3|b$.

$\sim$ is not transitive: $1\sim 3$ and $3\sim 1$, but not $1\sim 1$.

As just seen, $\sim$ is not reflexive.

It is symmetric, obviously.

BrianO
  • 16,579
0

It is not transitive! Take $3|(2\times 3),~~3|(3\times 4)$ but $3$ does not divide $2\times 4$.

Mikasa
  • 67,374
  • In fact, this shows that the relation is connected in a strong way - for any $a$ and $c$, there is some $b$ such that $aRb$ and $bRc$ (specifically, any $b$ which is divisible by $3$). – Noah Schweber Dec 07 '15 at 04:55
  • @NoahSchweber: Yes that's right. – Mikasa Dec 07 '15 at 04:57