Chapter 9: Relations

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}\).

Show that the relation \(R\) on a set \(A\) is antisymmetric if and only if \(R \cap {R^{ - 1}}\) is a subset of the diagonal relation \(\Delta = \{ (a,a)\mid a \in A\} \).

To determine an example of an infinite lattice with both a least and a greatest element.

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.)

To determine \(\left( {{Z^ + } \times {Z^ + }, \prec } \right)\) is a well ordered set.

To prove that the relation \(R\) on a set \(A\) is symmetric if and only if \(R = {R^{ - 1}}\) where \({R^{ - 1}}\) is the inverse relation.

To prove that the relation \(R\) on set \(A\) is anti-symmetric, if and only if \(R \cap {R^{ - 1}}\) is a subset of the diagonal relation \(\Delta = \{ (a,a)\mid a \in A\} \)

To determine \(\left( {{Z^ - }, \ge } \right)\)where \({Z^ - }\)is the set of negative integers and poset is well-defined.

Suppose that \({R_1}\) and \({R_2}\) are equivalence relations on a set A. Let \({P_1}\) and \({P_2}\) be the partitions that correspond to \({R_1}\) and \({R_2}\), respectively. Show that\({R_1} \subseteq {R_2}\) iff \({P_1}\) is a refinement of \({P_2}\).

To prove that \(R\) is reflexive if and only if \({R^{ - 1}}\) is reflexive.