Question

Show that the partition of the set of bit strings of length \(16\) formed by the equivalence classes of bit strings that agree on the last eight bits is a refinement of the partition formed from the equivalence classes of the bit strings that agree on the last four bits.

Short answer

Hence, the required result is found.

Step-by-step solution

Given data

\(S\) is the set of all the bit strings of length \(16\).

Concept used of refinement of partition        

If all the set in\(A\)is a subset of some set in\(B\), then\(A\)is known as a refinement of the partition\(B\).

The partitions\({P_1}\)and\({P_2}\)correspond with the equivalence relation\({R_1}\)and\({R_2}\)on a set then\({R_1} \subset {R_2}\)iff\({P_1}\)is a refinement of\({P_2}\).

Show the refinement of partition

Let \(S\) be the set of all the bit strings of length 16 .

Also, \({R_1}\) and \({R_2}\) are the equivalence relation on set \(S\).

\({R_1} = \{ (x,y)\mid x\)and \(y\) agree on the last eight bits \(\} \)

\({R_2} = \{ (x,y)\mid x\)and \(y\) agree on the last four bits \(\} \)

Let \({P_1}\) and \({P_2}\) are partitions of set \(S\) and correspond with the equivalence relation \({R_1}\) and \({R_2}\) respectively.

Let \({S_1} \in {P_1}\).

Assume that, \(x \in {S_1} \cdot \) So, \((x,y) \in {R_1}\) for all \(y \in {S_1}\), here, \({S_1}\) is an equivalence class.

Also, \(x\) and \(y\) agree on the last eight bits.

\(x\)and \(y\) agree on the last four bits.

So, \((x,y) \in {R_2},\;\forall y \in {S_1}\).

So, \(x\) belongs to some set \({S_2}\).

Therefore, all the sets in \({S_1}\) is a subset of some set in \({S_2}\).

Hence, \({P_1}\) is a refinement of \({P_2}\).

Hence, the required result is found.