Prove that a relation is an equivalence relation

In summary, the relation on the integers defined by p~q if and only if 7|p-q is an equivalence relation is reflexive, symmetric, and transitive.
  • #1
kenmcfa
3
0
Please be nice to me, I'm new here. Anyway, help to solve this maths problem would be much appreciated:

Homework Statement


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

Homework Equations


p~q if and only if 7|p-q

The Attempt at a Solution


a) (I'm pretty sure this is done right)
If relation is reflexive then:
x[tex]\in[/tex]S[tex]\rightarrow[/tex] (x,x) [tex]\in[/tex]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 [tex]\leftrightarrow[/tex] y~x

And I don't know how to go on from there. Please help me!
 
Last edited:
Physics news on Phys.org
  • #2
Suppose

[tex] x \sim y [/tex]

so that

[tex]
7 \mid x - y
[/tex]

To show that

[tex] y \sim x [/tex]

you need to show that

[tex]
7 \mid y - x
[/tex]

How can you do that?


For the transitive part, begin by assuming

[tex]
\begin{align*}
x \sim y & \text{ so } 7 \mid x - y \\
y \sim z & \text{ so } 7 \mid y - z
\end{align*}
[/tex]

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

[tex]
x \sim z
[/tex]
 
  • #3
kenmcfa said:
Please be nice to me, I'm new here. Anyway, help to solve this maths problem would be much appreciated:

Homework Statement


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


Homework Equations


p~q if and only if 7|p-q


The Attempt at a Solution


a) (I'm pretty sure this is done right)
If relation is reflexive then:
x[tex]\in[/tex]S[tex]\rightarrow[/tex] (x,x) [tex]\in[/tex]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 [tex]\leftrightarrow[/tex] 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)?)
 
  • #4
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[tex]\leftrightarrow[/tex]y~x.
 
  • #5
I've proved the transitivity now, thanks for the help you two. Unfortunately,I've just realized that there's more:
Fill in the blanks:
"The equivalence class containing 5 is given by
[5] = {n[tex]\in Z[/tex]|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!
 

1. What is an equivalence relation?

An equivalence relation is a type of binary relation that is reflexive, symmetric, and transitive. This means that for any elements in the relation, it must satisfy these three properties.

2. How do you prove that a relation is reflexive?

To prove that a relation is reflexive, you must show that every element in the relation is related to itself. This can be done by showing that (a,a) is a part of the relation for all elements a.

3. What is symmetry in relation to equivalence relations?

Symmetry in equivalence relations means that if two elements are related, then the reverse relation must also hold true. In other words, if (a,b) is in the relation, then (b,a) must also be in the relation.

4. How do you prove that a relation is symmetric?

To prove that a relation is symmetric, you must show that for every pair of related elements (a,b), the reverse relation (b,a) is also in the relation.

5. What is transitivity in relation to equivalence relations?

Transitivity in equivalence relations means that if two elements are related to each other, and one of those elements is also related to a third element, then the first and third element must also be related. In other words, if (a,b) and (b,c) are in the relation, then (a,c) must also be in the relation.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
887
  • Set Theory, Logic, Probability, Statistics
2
Replies
35
Views
261
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
Back
Top