Prove that a relation is an equivalence relation

**kenmcfa** · Oct14-08, 03:47 PM

Please be nice to me, I'm new here. Anyway, help to solve this maths problem would be much appreciated:
1. The problem statement, all variables and given/known data
Work out a detailed proof (below) that the relation on the integers defined by p~q if and only if 7|p-q is an equivalence relation:
a) the relation is reflexive
b) the relation is symmetric
c) the relation is transitive

2. Relevant equations
p~q if and only if 7|p-q

3. The attempt at a solution
a) (I'm pretty sure this is done right)
If relation is reflexive then:
x $LaTeX Code: \\in$ S $LaTeX Code: \\rightarrow$ (x,x) $LaTeX Code: \\in$ R
Therefore x~x
7|x-x since x-x=0 and 7|0
Therefore relation is reflexive.

That's the easy bit. Now:
b)If relation is symmetric then:
x~y $LaTeX Code: \\leftrightarrow$ y~x

And I don't know how to go on from there. Please help me!!

**statdad** · Oct14-08, 04:18 PM

Suppose

$LaTeX Code: x \\sim y$

so that

$LaTeX Code: 7 \\mid x - y $

To show that

$LaTeX Code: y \\sim x$

you need to show that

$LaTeX Code: 7 \\mid y - x $

How can you do that?

For the transitive part, begin by assuming

$LaTeX Code: \\begin{align*} x \\sim y & \\text{ so } 7 \\mid x - y \\\\ y \\sim z & \\text{ so } 7 \\mid y - z \\end{align*} $

Write out what these two statements mean, and you should see why it follows that

$LaTeX Code: x \\sim z $

**HallsofIvy** · Oct14-08, 04:33 PM

Originally Posted by kenmcfa

Please be nice to me, I'm new here. Anyway, help to solve this maths problem would be much appreciated:
1. The problem statement, all variables and given/known data
Work out a detailed proof (below) that the relation on the integers defined by p~q if and only if 7|p-q is an equivalence relation:
a) the relation is reflexive
b) the relation is symmetric
c) the relation is transitive

2. Relevant equations
p~q if and only if 7|p-q

3. The attempt at a solution
a) (I'm pretty sure this is done right)
If relation is reflexive then:
x $LaTeX Code: \\in$ S $LaTeX Code: \\rightarrow$ (x,x) $LaTeX Code: \\in$ R
Therefore x~x
7|x-x since x-x=0 and 7|0
Therefore relation is symmetric.

You mean "reflexive".

'quote]That's the easy bit. Now:
b)If relation is symmetric then:
x~y $LaTeX Code: \\leftrightarrow$ y~x

And I don't know how to go on from there. Please help me!![/quote]
x~y means 7 divides x-y which means x-y= 7n for some integer n.

y~ x means 7 divides y- x which means y- x= 7m for some m. Knowing that x- y= 7n, y- x= 7 times what?

"Transitive": if x~y and y~z then x~z.

Okay, you know x~y so x- y= 7n for some integer n.
You know y~ z so y- z= 7m for some integer m.
Therefore x- z= 7*what?
(hint: what is (x- y)+ (y- z)?)

**kenmcfa** · Oct14-08, 05:01 PM

Ok, focusing on the symmetric bit for now (sorry about that major typo, HallsofIvy):

x-y=7n
y-x=-7n
m=-7n

I can see that this is leading to some sort of a proof, but I don't really know what to write. Is something like the following enough for proof?:
m and n have a common factor of 7, so x-y and y-x are always divisible by 7. Therefore x~y $LaTeX Code: \\leftrightarrow$ y~x.

**kenmcfa** · Oct14-08, 05:17 PM

I've proved the transitivity now, thanks for the help you two. Unfortunately,I've just realised that there's more:
Fill in the blanks:
"The equivalence class containing 5 is given by
[5] = {n $LaTeX Code: \\in Z$ |n has remainder _ when divided by _}"
Am I supposed to put in 0 and 7? If it is, that seems like a bit of a random question. If it isn't, then I have no idea what's going on!