# Thread: Equivalence Classes & Partitions

1. ## 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.

2. Originally Posted by Kathysubbu
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.

3. Thank you very much for your example. It really helped me