Explore BrainMass

# Discrete Math- Equivalence Relations

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

I need a clear explanation of what an equivalence relation is with an examples. Specifically given 5|(m-n), where m and n are integers, please verify if this is an equivalence relation.

Please explain this clearly and in detail.

Â© BrainMass Inc. brainmass.com December 24, 2021, 10:46 pm ad1c9bdddf
https://brainmass.com/math/discrete-math/discrete-math-equivalence-relations-506432

## SOLUTION This solution is FREE courtesy of BrainMass!

Problem: I need a clear explanation of what an equivalence relation is with an examples. Specifically given 5|(m-n), where m and n are integers, please verify if this is an equivalence relation.

Solution:
I hope the following answer is clear. Thanks.

Solution:

First of all, I would like to give a definition of "equivalence relation":
A given binary relation ~ on a set A is said to be an equivalence relation if, and only if, it is reflexive, symmetric and transitive. Equivalently, for all a, b and c in A:
? a ~ a. (Reflexivity)
? if a ~ b then b ~ a. (Symmetry)
? if a ~ b and b ~ c then a ~ c. (Transitivity)

Now, we consider a binary relation ~ on the set of integers below:
For any integers m and n, m~n if, and only if, 5|(m-n) .............................(*)
To prove that the relation ~ is an equivalence relation on Z (the set of integers), we need to show that ~ is reflexive, symmetric, and transitive.

(1) To prove that the relation ~ is reflexive, we need to show that for every integer a in Z, a~ a.
[Proof] What does a~ a mean? By the definition (*), we need to show that 5|(a-a). As a-a=0, and 5|0 (5 divides 0), we conclude that 5|(a-a), and so a~a.

(2) To prove that the relation ~ is symmetric, we need to show that for any integers a and b, if a~b, then b~a.
[Proof] As a~b, by the definition (*), 5|(a-b). So, a-b=5k where k is an integer. So, b-a=-5k=5*(-k). As -k is also an integer when k is an integer, b-a=5*(-k) implies that 5|(b-a). So, b~a. Therefore, we have proved that for any integers a and b, if a~b, then b~a. Namely, R is symmetric.

(3) To prove that the relation ~ is transitive, we need to show that for any integers a, b, and c, if a~b and b~c, then a~c.
[Proof] As a~b, by the definition (*), 5|(a-b). So, a-b=5k, where k is an integer. As b~c, by the definition (*), 5|(b-c). So, b-c=5k', where k' is an integer. Hence,
a-c=(a-b)+(b-c)=5k+5k'=5(k+k') ......................................(**)
As both k and k' are integers, we have k+k' is also an integer. So, (**) indicates that a-c is divisible by 5, i.e., 5|(a-c). So, a~c.

From Proofs (1)-(3), we have shown that the relation ~ is reflexive, symmetric, and transitive. So, it is an equivalence relation on Z.

Thank you for using Brainmass.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Â© BrainMass Inc. brainmass.com December 24, 2021, 10:46 pm ad1c9bdddf>
https://brainmass.com/math/discrete-math/discrete-math-equivalence-relations-506432