Results 1 to 3 of 3

Math Help - Equivalence Classes & Partitions

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    3

    Equivalence Classes & Partitions

    A partition P1 is called a refinement of a partition P2 if every set in P1 is
    a subset of one of the sets in P2. Show that the partition of the set of bit strings of
    length 16 formed by equivalence classes of bit strings that agree on the last eight bits
    is a refinement of the partition formed by the equivalence classes of bit strings that
    agree on the last four bits.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,454
    Thanks
    1868
    Quote Originally Posted by Kathysubbu View Post
    A partition P1 is called a refinement of a partition P2 if every set in P1 is
    a subset of one of the sets in P2. Show that the partition of the set of bit strings of
    length 16 formed by equivalence classes of bit strings that agree on the last eight bits
    is a refinement of the partition formed by the equivalence classes of bit strings that
    agree on the last four bits.
    Look at a simplified example. Use bit strings of lenth 3, P1 the strings that agree on the last 2 bits and P2 the stings that agree on the last bit.
    There are 8 strings of length 3: 000, 001, 010, 011, 100, 101, 110, and 111.

    P1 contains 8/2= 4 sets: {000, 100}, {010, 110}, {001, 101}, and {011, 111}.

    P2 contains 8/4= 2 sets: {000, 100, 010, 110} and {001, 101, 011, 111}.

    Each member of P1 is a subset of P2.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    3
    Thank you very much for your example. It really helped me
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: October 5th 2011, 04:37 PM
  2. Set Theory - Partitions and Equivalence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 6th 2010, 10:31 AM
  3. Replies: 10
    Last Post: January 14th 2010, 01:28 PM
  4. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 07:36 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 04:39 AM

Search Tags


/mathhelpforum @mathhelpforum