Determining whether relations are equivalence classes, and finding the equivalence classes

Question

Determine if each of the following relations is an equivalence relation. If so, determine the equivalence classes.

1. $S = \Bbb Z$, $a \sim b \iff a \equiv b \pmod 3$ or $a \equiv b \pmod 5$.
2. $S = \Bbb Z$, $a \sim b \iff a \equiv b \pmod 3$ and $a \equiv b \pmod 5$.
3. $S = \Bbb R \times \Bbb R$, and $(x,y) \sim (u,v) \iff x^2 + y^2 = u^2 + v^2$.

This is the first question that came up on my last equivalence relations midterm that I couldn't figure out (all three). If anybody would be kind enough to outline the steps required to begin and get to the solution to all three parts of this question.

Please help, this stuff will be on the final which is in a month and I can't seem to find anything in the notes to guide me through. A quick F.Y.I. This is a proofs course and the standard proof procedure is required in all solutions. I wasn't very strong with modulo during that unit either.

Answer 1

1) No. Not transitive.Example: 1 = 4 ( mod 3 ) , and 4 = 9 ( mod 5 ) but 1 is not 9 ( mod 3 ) or 9 ( mod 5).

2) Yes.

3) Yes.

Answer 2

• For the first question it should be apparent that there is something wrong with it. Obviously a relation defined by modular congruence is reflexive and symmetric. But since this relation is defined by the "or" conjunction it need not be transitive. Your argument should go something like this.

Disproving by counter-example:

Just choose $a = 0, b = 3$ and $c = 8$.

Let $a \sim b$ since $a \equiv b \pmod 3$ and $b \sim c$ since $b \equiv c \pmod 5$ but $c - a = 8$ which is not divisible by $3$ or $5$ implying that $a$ is not related to $c$ and hence the relation is not transitive.

• Again for the second question proving that it is reflexive and transitive is easy since $a \equiv b \pmod n \iff n \ | \ (a - b) \iff n \ | \ (b - a)$ and since $n \ | \ 0 = a - a$.

To prove transitivity. Let $a, b, c, \in \Bbb Z$ such that $a \sim b$ and $b \sim c$

Then $a \equiv b \pmod 3$ and $b \equiv c \pmod 3$. Since congruence it self is a transitive relation $a \equiv c \pmod 3$. You can prove this if you wish by taking $ 3 \ | \ (a - b)$ and $ 3 \ | \ (b - c)$ then $3$ divides any linear combination of the two and hence $3 \ | \ (a - b) + (b - c) = (a - c) \iff a \equiv c \pmod 3 $. you can show that $a \equiv c \pmod 5$ in a similar way. Note that the "and" operator is used so you need to show "both" conditions are transitive. Q.E.D.

• As for the third. Let $(x, y), (u, v), (p, q) \in \Bbb R \times \Bbb R$

$x^2 + y^2 = x^2 + y^2 \implies (x, y) \sim (x, y) \implies S$ is reflexive.

$ (x, y) \sim (u, v) \iff x^2 + y^2 = u^2 + v^2 \iff u^2 + v^2 = x^2 + y^2 \iff (u, v) \sim (x, y)$ which implies that $S$ is symmetric.

$(x, y) \sim (u, v)$ and $ (u, v) \sim (p, q) \implies x^2 + y^2 = u^2 + v^2 $ and $u^2 + v^2 = p^2 + q^2 \implies x^2 + y^2 = p^2 + q^2 \implies (x, y) \sim (p, q)$ proving the relation is transitive. Q.E.D.