Explore BrainMass

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!

    Please help with the following problem regarding discrete math.

    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

    ADVERTISEMENT