• Support PF! Buy your school textbooks, materials and every day products Here!

Proof of equivalence relation

  • #1
<Moderator's note: Moved from a technical forum and thus no template.>

Not sure this should be under Linear and Abstract Algebra, but regardless I need help with a question in my mathematical proofs course.
Here it is:
Let ∼ be a relation defined on Z by x ∼ y if and only if 5 | (2x + 3y).
(a) Show that ∼ is an equivalence relation on Z

So I know for ~ to be an equivalence relation the relation needs to have the following properties;
1. Reflexive
2. Symmetric
3. Transitive

My attempt at the problems is this:
Proving the relation is reflexive seems easy enough, since if xRx (x~x) then 5 | (2x + 3x) = 5 | 5x where x is an element of Z, therefore we can clearly see the relation is reflexive since 5 does divide a multiple of 5.

Proving symmetric: Assume that xRy (x~y), that is 5 | (2x+3y) which is equivalent to 5a = 2x+3y right, where a is an element of Z. Now show that yRx (y~x), that is 5 | (2y+3x)..... but from here can i say this is also equivalent to 5a = 2y+3x or will i have to use another variable instead of a since 2x+3y does not necessarily equal 2y+3x?
This is where I am up to.
 
Last edited by a moderator:

Answers and Replies

  • #2
12,667
9,195
<Moderator's note: Moved from a technical forum and thus no template.>

Not sure this should be under Linear and Abstract Algebra, but regardless I need help with a question in my mathematical proofs course.
Here it is:
Let ∼ be a relation defined on Z by x ∼ y if and only if 5 | (2x + 3y).
(a) Show that ∼ is an equivalence relation on Z

So I know for ~ to be an equivalence relation the relation needs to have the following properties;
1. Reflexive
2. Symmetric
3. Transitive

My attempt at the problems is this:
Proving the relation is reflexive seems easy enough, since if xRx (x~x) then 5 | (2x + 3x) = 5 | 5x where x is an element of Z, therefore we can clearly see the relation is reflexive since 5 does divide a multiple of 5.

Proving symmetric: Assume that xRy (x~y), that is 5 | (2x+3y) which is equivalent to 5a = 2x+3y right, where a is an element of Z. Now show that yRx (y~x), that is 5 | (2y+3x)..... but from here can i say this is also equivalent to 5a = 2y+3x or will i have to use another variable instead of a since 2x+3y does not necessarily equal 2y+3x?
This is where I am up to.
If ##5a=2x+3y\,,## what is ##5x - 2x + 5y - 3y\,## resp. what can you say about the result's divisibilty?
 
  • #3
If ##5a=2x+3y\,,## what is ##5x - 2x + 5y - 3y\,## resp. what can you say about the result's divisibilty?
I don't understand where 5x−2x+5y−3y came from?
 
  • #4
I don't understand where 5x−2x+5y−3y came from?
oh right that is what we are tryign to prove right? that 5c = 5x−2x+5y−3y = 3x+2y for some c in Z ?
 
  • #5
oh right that is what we are tryign to prove right? that 5c = 5x−2x+5y−3y = 3x+2y for some c in Z ?
what does resp mean?
 
  • #6
12,667
9,195
I don't understand where 5x−2x+5y−3y came from?
Just for fun. Calculate it: ##5x−2x+5y−3y= 3x+2y=5(x+y)-5a=5(x+y-a)## and read it from right to left: ##5\,|\,5(x+y-a)=...##

Edit: The trick is to convert ##2x## into ##3x##. Since we don't have to bother multiples of ##5## nor signs, adding or subtracting ##5x## does no harm to the result.
 
Last edited:
  • #7
12,667
9,195
  • #8
Just for fun. Calculate it: ##5x−2x+5y−3y= 3x+2y=5(x+y)-5a=5(x+y-a)## and read it from right to left: ##5\,|\,5(x+y-a)=...##
Oh right, 3x+2y=5(x+y)-5a since 5a = 2x+3y. Then it is clear that 5(x+y-a) is divisible by 5 ie 5 | 5(x+y-a).
Hence symmetry is proven.
 

Related Threads on Proof of equivalence relation

Replies
2
Views
4K
Replies
4
Views
1K
  • Last Post
Replies
7
Views
598
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
4
Views
4K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
17
Views
3K
Replies
4
Views
24K
  • Last Post
Replies
7
Views
738
Top