Proof of equivalence relation

In summary, the relation ∼ defined on Z by x ∼ y if and only if 5 | (2x + 3y) is an equivalence relation on Z. This is shown by proving that it is reflexive, symmetric, and transitive. For symmetry, we can convert 2x into 3x and show that the resulting expression is also divisible by 5, thus proving that the relation is symmetric.
  • #1
UOAMCBURGER
31
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:
Physics news on Phys.org
  • #2
UOAMCBURGER said:
<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
fresh_42 said:
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
UOAMCBURGER said:
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
UOAMCBURGER said:
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
UOAMCBURGER said:
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:
  • Like
Likes UOAMCBURGER
  • #7
UOAMCBURGER said:
what does resp mean?
respectively
 
  • #8
fresh_42 said:
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.
 

1. What is the definition of an equivalence relation?

An equivalence relation is a relation between two elements in a set that is reflexive, symmetric, and transitive. This means that every element is related to itself, if A is related to B then B is related to A, and if A is related to B and B is related to C, then A is also related to C.

2. How do you prove that a relation is an equivalence relation?

To prove that a relation is an equivalence relation, you must show that it satisfies the three properties: reflexive, symmetric, and transitive. This can be done by providing specific examples or by using logical reasoning to show that the properties hold true for all elements in the set.

3. What is an example of an equivalence relation?

An example of an equivalence relation is the relation "is the same age as" between people. This relation is reflexive (everyone is the same age as themselves), symmetric (if person A is the same age as person B, then person B is also the same age as person A), and transitive (if person A is the same age as person B and person B is the same age as person C, then person A is also the same age as person C).

4. How does proof of equivalence relation relate to mathematics?

In mathematics, equivalence relations are important because they help us classify objects into different categories based on their properties. By proving that a relation is an equivalence relation, we can show that certain objects belong in the same category and have similar properties.

5. Can a relation be both an equivalence relation and an order relation?

Yes, a relation can be both an equivalence relation and an order relation. An example of this is the relation "is a subset of" between sets. This relation is reflexive, symmetric, and transitive (making it an equivalence relation), but it also follows the properties of a partial order (making it an order relation).

Similar threads

  • Precalculus Mathematics Homework Help
Replies
11
Views
857
  • Precalculus Mathematics Homework Help
Replies
2
Views
803
  • Precalculus Mathematics Homework Help
Replies
1
Views
941
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
821
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
25
Views
355
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
Back
Top