Question

Show that the partition of the set of all bit strings formed by equivalence classes of bit strings with respect to the equivalence relation \({R_4}\) is a refinement of the partition formed by equivalence classes of bit strings with respect to the equivalence relation \({R_3}\).

Short answer

Hence, the required result is found

Step-by-step solution

Given data

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

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 bit strings.

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

\(\begin{array}{l}{R_4} = \left\{ {\begin{array}{*{20}{l}}{(x,y)\mid x = {\rm{ yor }}x{\rm{ and }}y{\rm{ arestrings withat least }}}\\{{\rm{ fourbits that agree in their first fourbits }}}\end{array}} \right\}\\{R_3} = \left\{ {\begin{array}{*{20}{l}}{(x,y)\mid x = {\rm{ yor }}x{\rm{ and }}y{\rm{ are bit strings withat least }}}\\{{\rm{ three bitsthat agree in their first threebits }}}\end{array}} \right\}\end{array}\)

Let \({P_4}\) and \({P_3}\) are partitions of set \(S\) and correspond with the equivalence relation \({R_4}\) and \({R_3}\) respectively.

Assume that, \(x,y \in S,(x,y) \in {R_4}\).

Here, \(x = y\) or \(x\) and \(y\) are bit strings with at least four bit that agree in their first four bits.

\(x = y\)or\(x\) and \(y\) are bit strings with at least three bit that agree in their first three bits.

So, \((x,y) \in {R_3}\)

Thus, \({R_4} \subset {R_3}\).

Hence, \({P_4}\) is a refinement of \({P_3}\).

Hence, the required result is found.