Thread: Relation Question 2

1. Relation Question 2

Let R be a relation on $\mathbb{N}$, where $xRy \Leftrightarrow$ $x\equiv y$ mod 8

I have an answer saying this is an equivalence relationship; however, I can't seem to derive it myself. Maybe it is because my understanding of what mod 8 means... the way I understand the mod 8 term is that x = y with a remainder of 8 (or multiple of 8?), but why has $\equiv$ been used instead of $=$? Does it make a difference?

To check if the relation is reflexive would I say x = x + 8k for some integer k? It seems like that would not be true or only for k = 0. I'm am stuck for symmetry as well.

I think I can see transitive... If

$x = y + 8k$

and

$y = z + 8m$

then

$x = (z + 8m) + 8k$

$= z + 8(m + k)$

So there is a remainder that is a multiple of 8.

2. Re: Relation Question 2

Originally Posted by terrorsquid
Let R be a relation on $\mathbb{N}$, where $xRy \leftrightarrow$ $x\equiv y$ mod 8.
Look at this web page..
You can always to some research on the web.

For this question, I would use $a \equiv b\,\bmod (c)$ if and only if $a~\&~b$ have the same remainder when divided by $c$.

So $49 \equiv 25\,\bmod (8)$.

3. Re: Relation Question 2

Your relation is equivalent to x-y=8k for some integer k.

So for example, x-x=8*0 shows that the relation is reflexive.

4. Re: Relation Question 2

Originally Posted by DrSteve
Your relation is equivalent to x-y=8k for some integer k.

So for example, x-x=8*0 shows that the relation is reflexive.
Furthermore, we conclude that R is symmetric, since

xRy <=> x = y (mod8) <=> y - x = 8k for some integer k <=> x - y = 8(-k), where (-k) is also/still an integer <=> yRx

Transitivity is simple too. I'll let you fill in the middle, after I write the hypothesis and conclusion:

To prove (xRy and yRz) => (xRz)

(xRy and yRz) <=> (y - x = 8j and z - y = 8k for integers j, k) => ....... <=> xRz

5. Re: Relation Question 2

To prove (xRy and yRz) => (xRz)

(xRy and yRz) <=> (y - x = 8j and z - y = 8k for integers j, k) => ...

$\therefore$ x - z = (y-8j) - (8k +y) = 8(-j-k)

<=> xRz

6. Re: Relation Question 2

Yes. FYI, there should be an option to "mark question as solved" if/when you feel that is appropriate