1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Equivalence Relations

  1. Mar 13, 2015 #1
    Prove that the following is an equivalence relation on the indicated set. Then describe the partition associated with the equivalence relation.

    1. In Z, let m~n iff m-n is a multiple of 10.



    2. The attempt at a solution

    Reflexive: m-n = 0

    0 Z, and 0 is a multiple of every number, therefore, m~n

    Symmetric:
    1. m~n
    2. m-n = 0 Z, and 0 is a multiple of every number
    3. -(m-n) = 0 Z, and 0 is a multiple of every number

    4. -(m-n) = n-m = 0 Z, and 0 is a multiple of every number
    5. Therefore, n~m

    Transitive:
    1. m~n and n~t
    2. m-n = 0 Z, and 0 is a multiple of every number
    . and n-t = 0 Z, and 0 is a multiple of every number
    3. (m-n)+(n-t) = m-t = 0 Z, and 0 is a multiple of every number
    4. Therefore, m~t

     
    Last edited: Mar 13, 2015
  2. jcsd
  3. Mar 13, 2015 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    You have have asserted that various numbers are "in the indicated set", but you haven't given any proof they are.
     
  4. Mar 13, 2015 #3
    I edited the problem.
     
    Last edited: Mar 13, 2015
  5. Mar 13, 2015 #4
    For part 2 I think what you mean to say is n - n = 0 (which is clearly divisible by 10). In this problem you're not looking for the difference to be 0, but rather a multiple of 10 (say 10x for some integer x), or that 10 divides their difference.
     
  6. Mar 13, 2015 #5
    Thank you fourier....can you take a look at the work I did for proving m~n and see if it is correct.
     
  7. Mar 13, 2015 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    To prove the relation is reflexive, what you must prove is that [itex] m \sim m [/itex].



    It isn't true that [itex] m-n [/itex] must be zero. You probably mean that [itex] m-n = 0 (mod \ 10) [/itex].

    It is not true that m-n must be zero.
     
  8. Mar 13, 2015 #7

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Please, only edit the Original Post to correct typos and/or errors in the statement of the problem. Additionally, edit the OP to supply any essential information you may have initially left out. It may help clarify matters, if you indicate what is changed in the edit.

    If you are making corrections to your solution of a problem, it's best to add another post to the thread. Otherwise it's nearly impossible to follow the sequence of events in the thread.
     
  9. Mar 13, 2015 #8
    for part 2 you start with ##m \sim n## which in this case means m - n = 10x for some x ∈ ℤ & you have to show ##n \sim m##. Part 3 is a bit more complicated because you have ##m \sim n## which means m - n = 10x for x ∈ ℤ & ##n \sim t## which means n - t = 10y for y ∈ ℤ.
     
    Last edited: Mar 13, 2015
  10. Mar 13, 2015 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You mean m~m. Then m- m= 0.

    No, if m~n then m- n is a multiple of 10, not necessarily 0.

    [/quote]
     
  11. Mar 13, 2015 #10
    Sorry I forgot to post this earlier....this is what I have came up with so far...

    Reflexive: m-n = m=n mod 10. ∈ ℤ and is a divisible by 10 (same as being a multiple) Therefore, m~n

    Symmetric: m~n = m-n = n mod 10. ∈ ℤ and is a divisible by 10. Then -(m-n)= n-m = n=m mod 10. Therefore, n~m

    Transitive: ?? I am kind of stuck here... I know that if m~n and n~t then show m~t.

    I think that it goes like this.....

    n= t= m mod 10. and m=n= t mod 10 therefore m~t.

    But I am not sure.
     
  12. Mar 13, 2015 #11
    You're trying to prove ##m \sim n## is an equivalence relation, where ##m \sim n## if ##m \equiv n\, (mod 10)##, so what does it mean when ##m \equiv n\, (mod 10)##? For symmetry for example the problem is to show if ##m \equiv n\, (mod 10)## then ##n \equiv m\, (mod 10)##, how would you do that?
     
  13. Mar 13, 2015 #12
    So I redid it again....here it goes.

    Reflexive: let n∈ℤ, then for any n∈ℤ n-n=0 is a multiple of 10. ∴ n~n

    Symmetric: Let m, n∈ℤ and m~n. Then m-n is a multiple of 10. That is m-n ≡ 10k, k∈ℤ and n-m ≡ 10(-k), -k∈ℤ. ∴ n-m is a multiple of 10 and n~m.

    Transitive: Let m, n, p∈ℤ and m~n, n~p. Then m-n, n-p are multiples of 10. That is m-n ≡ 10k1 and n-p≡10k2, k1, k2∈ℤ. Now (m-n)+(n-p) ≡ 10k1 + 10k2, k1, k2∈ℤ ≡ 10 (k1 + k2), k1, k2 ∈ℤ ≡ m-p ∴ m-p is a multiple of 10 and m~n, n~p shows that m~p.

    Partition:

    Fix n∈ℤ. Then m~n and m-n is a multiple of 10.
    m-n = 10k, k∈ℤ
    m= n+10k, k∈ℤ
    ∴ n= {m: m= n+10k, k∈ℤ} =n+10k : k, ∈ℤ
     
  14. Mar 13, 2015 #13
    I thought you had to show that you get a partition of the integers but they just want a description... I think I get what you did for that part but maybe you could clean it up & actually describe in words what all that means. The rest looks ok to me.
     
  15. Mar 14, 2015 #14

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Certainly your notation is bad- "n= {m: m= n+10k, k∈ℤ}" you have an integer, n, equal to a set of integers!
    Perhaps you meant "[n]' on the left, indicating the equivalence class n is in. Of course, there are only 10 such equivalence classes. You could just write each out:
    {0, 10, -10, 20, -20, ...}, {1, 11, -9, 21, -19, ...}, etc.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Equivalence Relations
  1. Equivalence Relation (Replies: 3)

  2. Equivalence Relations! (Replies: 2)

  3. Equivalence Relations (Replies: 5)

  4. Equivalence relation ? (Replies: 1)

  5. Equivalence Relations (Replies: 9)

Loading...