Show that R is an equivalence relation and determine all distinct classes

Question

Let R be a relation on Z define as follows:

m R n <--> 3|($m^2$-$n^2$)

show that R is an equivalence relation and determine all distinct equivalence classes.

EDIT: I looked several places and found R to be defined on A as follows: A={-5,-4,-3,-2,-1,0,1,2,3,4,5), How would I solve this type of problem?

I tried solving this problem this way:

1. Equivalence relations are relations that are reflexive, symmetric, and transitive. Therefore we need a combination of sets that give these results.
2. Knowing that I came up with R to be (2,2), (2,4), (2, 5), (4,4), (4, 2), (4,5), (5,5), (5,2) and (5,4).

3. With my logic, I came up with the equivalence class of every element.

    [2] = {2,4}
    [4] = {2,4}
    [5] = {4,5}
   

4. I concluded that the distinct equivalence classes in the relation are: {2,4}, {4,5}.

I feel like this problem is incomplete though. This is what my professor gave us, but I just feel like he's supposed to give us R. Looking past this, is my logic correct in answering this problem?

Answer 1

$m R n \Leftrightarrow 3|m^2-n^2$.

To see that this is an equivalence relation, we show the three conditions explicitly:

1)Reflexivity: $\forall m, m^2-m^2=0 \implies 3|m^2-m^2 \implies m\ R\ m$

2)Symmetry: $m\ R\ n \implies 3|m^2-n^2 \implies 3|(-1)(m^2-n^2) \implies 3|n^2-m^2 \implies n\ R\ m$

3)Transitivity: $l\ R\ m, m\ R\ n \implies 3|l^2-m^2,3|m^2-n^2 \implies 3|(l^2-m^2+m^2-n^2) \implies 3|l^2-n^2 \implies l\ R\ n$.

Hence, the relation so defined is an equivalence relation.

To find the equivalence classes, we take any $a \in \mathbb{Z}$ and find all $b$ such that $a\ R\ b$.

Note that $(m^2-n^2)=(m-n)(m+n)$. So for $m\ R\ n$, it is enough that $3$ divides any one of $m-n$ or $m+n$.

1)Let $3|a$. Then for $3|a+b$, we must have $3|b$, and for $3|a-b$, we must have $3|b$ as well. So any $b$ related to $a$ must be a multiple of $3$, and all multiples of $3$ are related to each other, so it follows that the set of multiples of $3$ forms an equivalence class.

2)Let $3\nmid a$. Suppose that $a$ leaves a remainder of $1$, then note that $3|a+b$ whenever $b$ leaves a remainder of $2$, and $3|a-b$ whenever $b$ leaves a remainder of $1$. Thus, $a$ will be related to any $b$ such that $3\nmid b$, simply because if $b$ leaves a remainder of $1$ then $3|a-b$, and if $b$ leaves a remainder of $2$, then $3|a+b$.

You will ask why I did not take the leftover case, namely $a$ leaving a remainder of $2$. Well, that's the speciality of an equivalence relation. In the above, we have already shown that $a$ is related to all non-multiples of $3$, so if $a$ left a remainder of $2$, then it wouldn't matter, because it remains a non-multiple of $3$ and so falls back in the same equivalence class!

Hence, there are only two equivalence classes:

i)multiples of $3$

ii)non-multiples of $3$.

This seems miles away from what you've written in your post.

Answer 2

As it is given here, the solution is incomplete.

Item 1: You must prove that the relation is reflexive, symmetric and transitive. I will give a few hints.

• Is n R n?
• Is n R -n?
• Is it true that (3 | x) <=> (3 | -x)?
• Is it true that (a - b) mod 3 + (b - c) mod 3 = (a - c) mod 3? (mod is remainder of division)

Item 2: It was not required to explicitly list R as a subset of A^2. Omit it from the answer.

Item 3: What is [0] = { x such that 0 R x }? Find [n] for all n in A, then remove the duplicate sets (there are several). From each set, choose one element to be its representative.

Finally, a reference: Equivalence Relation (Wikipedia)