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

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?

• An example is almost never a proof. Here's a start: to show that $R$ is reflexive, you need to establish $n\,R\,n$ for all $n\in\mathbb{Z}$, in other words, $3\mid n^2-n^2$. Can you do that? If so, showing symmetry and transitivity isn't much more difficult. Commented Mar 14, 2016 at 23:42
• @RickDecker I don't think the question was asking for a proof all along. I think my professor just forgot to include the relation R. I've updated the question. Commented Mar 14, 2016 at 23:51
• You've still got a problem. Item 3 can't be correct, since any two equivalence classes must either be equal or disjoint. Commented Mar 14, 2016 at 23:55

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)

$$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.

• You reversed the names of reflexive and symmetric relations in (1) and (2). Commented Apr 11, 2016 at 2:00
• It's a small mistake. You may correct that if you like. Commented Apr 11, 2016 at 12:38