# Prove that a relation is an equivalence relation

1. Oct 14, 2008

### 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$$\in$$S$$\rightarrow$$ (x,x) $$\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 $$\leftrightarrow$$ y~x

Last edited: Oct 14, 2008
2. Oct 14, 2008

Suppose

$$x \sim y$$

so that

$$7 \mid x - y$$

To show that

$$y \sim x$$

you need to show that

$$7 \mid y - x$$

How can you do that?

For the transitive part, begin by assuming

\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

$$x \sim z$$

3. Oct 14, 2008

### HallsofIvy

Staff Emeritus
You mean "reflexive".

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

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)?)

4. Oct 14, 2008

### kenmcfa

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$$\leftrightarrow$$y~x.

5. Oct 14, 2008

### kenmcfa

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$$\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!