Question

Show that the partition of the set of all identifiers in \(C\) formed by the equivalence classes of identifiers with respect to the equivalence relation \({R_{31}}\) is a refinement of the partition formed by equivalence classes of identifiers with respect to the equivalence relation \({R_8}\).(Compilers for “old” C consider identifiers the same when their names agree in their first eight characters, while compilers in standard C consider identifiers the same when their names agree in their first 31 characters.)

Short answer

Hence, the required result is found.

Step-by-step solution

Given data

\(S\) is the set of all identifiers in \(C\).

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 identifiers in \(C\).

Also, \({R_{31}}\) and \({R_{\rm{8}}}\) are the equivalence relation on set \(S\).

\(\begin{array}{l}{R_{31}} = \left\{ {\begin{array}{*{20}{l}}{(x,y)\mid x = y{\rm{ or }}x{\rm{ and }}y{\rm{ are identifiers withat least }}}\\{31{\rm{ characters that agree in their first }}3{\rm{ I characters }}}\end{array}} \right\}\\{R_8} = \left\{ {\begin{array}{*{20}{l}}{(x,y)\mid x = {\rm{ yor }}x{\rm{ and }}y{\rm{ are identifiers withat least }}}\\{8{\rm{ characters that agree in their first }}8{\rm{ characters }}}\end{array}} \right\}\end{array}\)

Let \({P_{31}}\) and \({P_8}\) are partitions of set \(S\) and correspond with the equivalence relation \({R_{31}}\) and \({R_8}\) respectively.

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

Here, \(x = y\) or \(x\) and \(y\) are identifiers with at least 31 characters that agree in their 31 characters.

\(x = \)yor \(x\) and \(y\) are identifiers with at least 8 characters that agree in their first 8 characters.

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

Thus, \({R_{31}} \subset {R_8}\).

Hence, \({P_{31}}\) is a refinement of \({P_8}\).

Hence, the required result is found.