Partial Orders

Solved Problems

Solution.

1. \(R_1\) is a partial order since it is reflexive, antisymmetric, and transitive.
2. \(R_2\) is not transitive: \({\left( {1,3} \right), \left( {3,4} \right)} \in {R_2},\) but \({\left( {1,4} \right)} \notin {R_2}.\) Hence, \(R_2\) is not a partial order.
3. \(R_3\) is antisymmetric and transitive, but not reflexive. So it is not a partial order.
4. \(R_4\) is not antisymmetric since \({\left( {2,3} \right)} \in {R_4}\) and \({\left( {3,2} \right)} \in {R_4}.\) This means that \(R_4\) is not a partial order.

Solution.

\(R\) is reflexive since the matrix \(M_R\) contains all diagonal elements.

\(R\) is antisymmetric since all non-reflexive elements of the matrix symmetric about the main diagonal are not equal to each other:

For example,

The relation \(R\) is transitive:

Hence, the relation \(R\) is a partial order.

Solution.

Recall that the divisibility relation \("a\mid b"\) is defined as follows: the ordered pair \(\left( {a,b} \right)\) belongs to the relation "|" if and only if \(a \lt b\) and \(a\) divides \(b.\)

The set \(A\) contains the following non-comparable pairs of elements:

Solution.

Since \(R\) is reflexive, we have \(\left( {a,a} \right) \in R\) for all \(a \in A.\) By interchanging the first and second element, we obtain the same identity pair \(\left( {a,a} \right) \in R.\) Hence, \(\left( {a,a} \right) \in {R^{ - 1}},\) so the relation \({R^{ - 1}}\) is also reflexive.

The original relation \(R\) is antisymmetric:

Using the definition of \({R^{ - 1}},\) we can replace here \(\left( {a,b} \right) \in R\) with \(\left( {b,a} \right) \in {R^{ - 1}}\) and \(\left( {b,a} \right) \in R\) with \(\left( {a,b} \right) \in {R^{ - 1}}.\) Then the previous statement is written as

which means that the inverse relation \({R^{ - 1}}\) is antisymmetric.

Suppose that \(\left( {a,b} \right) \in {R^{ - 1}}\) and \(\left( {b,c} \right) \in {R^{ - 1}}.\) By definition of \({R^{ - 1}},\) we can write

Since \(R\) is transitive, we have

This proves the transitivity of \(R^{-1}.\)

Thus, the inverse relation \(R^{-1}\) is a partial order.

Solution.

We need to consider three properties for the intersection relation \(R \cap S:\) reflexivity, antisymmetry, and transitivity.

Since \(R\) and \(S\) are reflexive relations, then for any \(a \in A\) we have

Hence

for any \(a \in A,\) so \(R \cap S\) is also reflexive.

We prove the antisymmetry property by contradiction. Suppose that \(R \cap S\) is not antisymmetric. Then

where \(a \ne b.\) This means that

where \(a \ne b,\) which is false since both relations \(R\) and \(S\) are antisymmetric. Hence, the assumption is false and the intersection relation \(R \cap S\) is antisymmetric.

Let now

Then

Both relations \(R\) and \(S\) are transitive (as they are partial orders). Therefore,

so we have

that is, \(R \cap S\) is a transitive relation on set \(A.\)

This proves that the intersection relation \(R \cap S\) is a partial order. In other words, the property of partial ordering is closed under intersection.

Solution.

For any \(a \in A,\) we have

because the relations \(R\) and \(S\) are reflexive. Hence,

that is, the union relation \(R \cup S\) is reflexive.

Using a counterexample, we can show that the union relation \(R \cup S\) is not antisymmetric. Consider the set \(A = \left\{ {1,2,3} \right\}\) and two relations on it:

The relations \(R\) and \(S\) are partial orders since they are reflexive, antisymmetric, and transitive. Their union is given by

As it can be seen, every non-reflexive element has the corresponding reverse pair: \({\left( {1,2} \right)}\) and \({\left( {2,1} \right)},\) \({\left( {1,3} \right)}\) and \({\left( {3,1} \right)},\) \({\left( {2,3} \right)}\) and \({\left( {3,2} \right)}.\) This implies that \(R \cup S\) is not antisymmetric.

Consider now two other relations on the same set \(A = \left\{ {1,2,3} \right\}:\)

The relations \(X\) and \(Y\) are partial orders. The union relation \(X \cup Y\) is written in the form

As it can be seen, \(\left( {1,3} \right) \in X \cup Y,\) \(\left( {3,2} \right) \in X \cup Y,\) but \(\left( {1,2} \right) \notin X \cup Y,\) so the union relation in this example is not transitive.

Thus, the union of partial orders does not need to be a partial order.