Results 1 to 4 of 4

Math Help - Equivalence Relations question

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    2

    Equivalence Relations question

    Ok, here's my problem:

    Let X={1,2,...,10}. Define a relation R on X*X by (a,b)R(c,d) if ad=bc.
    A. Prove R an equivalence relation.
    B. List the elements of [(5,4)].
    C. How many distinct equivalence classes are there?

    Ok, so here's what I've got so far:

    Part A, Prove R is an equivalence relation. So I must prove that R is reflexive, symmetric and transitive.

    Reflexive:
    I need to show that ((a,b),(a,b)) is an element of R, for the set X. So I will check that ab=ba. Since c=a and d=b, then ab=ba, thus R is reflexive.

    Symmetric:
    I must show that (a,b),(c,d) is an element of R and (c,d),(a,b) is contained in R. If (a,b),(c,d) is an element of R, then ad=bc and cb=da since multiplication is commutative. Therefore (c,d),(a,b) is contained in R.

    Transitive:
    I must show that if (a,b),(c,d) is contained in R and (c,d),(e,f) is contained in R then (a,b),(e,f) is contained in R. Assume that (a,b),(c,d) is contained in R and (c,d),(e,f) is contained in R. Then ad=cb and cf=ed. This implies that a/b=c/d and that c/d=e/f so a/b=e/f thus, af=eb. So, (a,b),(e,f) is contained in R.

    Part B:
    List the elements of [(5,4)]:

    I'm confused on this a bit, I am assuming they are asking what elements does the equivalence class [(5,4)] contain...
    {(5,4),....

    My thoughts here, if (a,b)=(5,4) and ad=bc, then 5d=4c, c=4/5d and d=5/4c, allowing that if c=5, d=4 and if c=10 then d=8.

    so, {(5,4), (10,8)} would be my answer. Is this correct?

    Ok and Part C...

    This I'm lost on how to figure it up. So any help or pointers in the correct direction would be great!

    Thanks in advance

    Ashley
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,715
    Thanks
    1642
    Awards
    1
    What you have done on parts a) & b) is correct.

    Here is a hint for part c). Think fractions as in \frac{5}{4}=\frac{10}{8}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    2
    Thanks so much for the quick response, by thinking in terms of fractions like you said, I came up with 19 distinct equivalence classes for this relation.
    1. (1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9 ,9),(10,10)
    2. (1,2),(2,4),(3,6),(4,8),(5,10)
    3. (1,3),(2,6),(3,9)
    4. (1,4),(2,8)
    5. (1,5),(2,10)
    6. (2,1),(4,2),(6,3),(8,4),(10,5)
    7. (2,3),(4,6),(6,9)
    8. (2,5),(4,10)
    9. (3,1),(6,2),(9,3)
    10. (3,2),(6,4),(9,6)
    11. (3,4),(6,8)
    12. (3,5),(6,10)
    13. (4,1),(8,2)
    14. (4,3),(8,6)
    15. (4,5),(8,10)
    16. (5,1),(10,2)
    17. (5,2),(10,4)
    18. (5,3),(10,6)
    19. (5,4),(10,8)

    The problem I have with this though, is that I'm working with a couple of students also in my class (this was a test question the whole class missed, so we have to figure it out in groups and resubmit), and on this particular part, she said the answer was 5, but she's not sure why that was correct if it was.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,715
    Thanks
    1642
    Awards
    1
    It cannot be only five.
    I did not carefully check your list.
    But is seems to be correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 PM
  2. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: April 29th 2010, 04:30 PM
  3. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  4. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 1st 2009, 11:14 AM
  5. Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 16th 2008, 01:08 PM

Search Tags


/mathhelpforum @mathhelpforum