0

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.

Community
  • 1
user122661
  • 983
  • What have you tried? Do you know what an equivalence relation is? What do you need to prove/disprove to show that something is/is not an equivalence relation? – TMM Mar 07 '14 at 20:01
  • I understand that I must prove that the relation is transitive, symmetric, and reflexive, however I'm having trouble going through the actual proof and order of procedures that would help to prove (or disprove) each claim. – user122661 Mar 07 '14 at 20:07

2 Answers2

1
  • 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.

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
  • Thanks a lot! How would we find the equivalence classes of (2) and (3), however? – user122661 Mar 10 '14 at 17:29
  • @user122661: "Finding" them is something I confess I cannot do. But I'll tell you what they can surely be proven. For $(2)$, the equivalence class of $a \in \Bbb Z$ is all other integers $b$ such that $a \equiv b \pmod {15}$. For $(3)$ the equivalence class of $(x, y)$ is every point on the (perimeter of the) circle centered at the origin with radius equal to the distant from $(x, y)$ to the origin. – Ishfaaq Mar 11 '14 at 00:04
0

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.

DeepSea
  • 77,651