Calculus

Set Theory

Set Theory Logo

Partial Orders

Definitions

A binary relation \(R\) on a non-empty set \(A\) is called a (non-strict) partial order relation or partial ordering if and only if the relation is

  • reflexive
  • antisymmetric, and
  • transitive.

To denote a partial order relation we use the notation \(\require{AMSsymbols}{\preccurlyeq,}\) so instead of \(aRb\) we often write \(a \preccurlyeq b.\)

If \(a \preccurlyeq b\) and \(a \ne b,\) then we usually write \(a \prec b.\) In this case, the relation is called a strict partial order on set \(A.\) It is irreflexive, antisymmetric, and transitive.

A set \(A\) together with a partial order relation \(\preccurlyeq\) is called a partially ordered set or poset and is denoted by \(\left( {A, \preccurlyeq } \right).\)

Two elements \(a\) and \(b\) of a partially ordered set \(\left( {A, \preccurlyeq } \right)\) are said to be comparable, if and only if, either \(a \preccurlyeq b\) or \(b \preccurlyeq a.\) Otherwise we say that \(a\) and \(b\) are noncomparable or incomparable.

In a partially ordered set, it is not necessary that every pair of elements \(a\) and \(b\) be comparable. When all the elements of a set \(A\) are comparable, the relation is called a total ordering.

Examples of Partial Order Relations

Subset Relation

The subset relation is denoted by \(\subseteq\) and is defined on the power set \(\mathcal{P}\left( A \right),\) where \(A\) is any set of elements.

For any subset \(A_i\) of \(\mathcal{P}\left( A \right),\) the following is true: \({A_i} \subseteq {A_i}.\) Hence, the relation \(\subseteq\) is reflexive.

Suppose \({A_1}, {A_2}\) are two any subsets of \(\mathcal{P}\left( A \right).\) If \({A_1} \subseteq {A_2}\) and \({A_2} \subseteq {A_1},\) then by definition of set equality, \({A_1} = {A_2}.\) This means that the subset relation is antisymmetric.

Let \({A_1} \subseteq {A_2}\) and \({A_2} \subseteq {A_3}.\) Consider an arbitrary element \(a \in {A_1}.\) Since \({A_1} \subseteq {A_2},\) we have \(a \in {A_2}.\) Similarly, since \({A_2} \subseteq {A_3},\) we have \(a \in {A_3}.\) Hence, the relation \(\subseteq\) is transitive.

We see that the subset relation on the power set \(\mathcal{P}\left( A \right)\) is reflexive, antisymmetric, and transitive. So it is a partial ordering.

Divisibility Relation

The divisibility relation, denoted by “|”, on the set of natural numbers \(\mathbb{N} = \left\{ {1,2,3, \ldots } \right\}\) is another classic example of a partial order relation.

The relation “|” is reflexive, because any \(a \in \mathbb{N}\) divides itself.

The relation “|” is antisymmetric. Indeed, if \(a \mid b,\) then \(ak = b,\) where \(k\) is an integer. Similarly, if \(b \mid a,\) then \(b\ell = a,\) where \(\ell\) is an integer. Hence,

\[ak\ell = a,\;\; \Rightarrow k\ell = 1.\]

The last equation holds if only \(k = \ell =1,\) which means that \(a = b.\)

The relation “|” is transitive. Suppose \(a \mid b\) and \(b \mid c.\) Then \(ak = b\) and \(b\ell = c,\) where \(k, \ell\) are certain integers. Hence \(ak\ell = c,\) and \(k\ell\) is an integer. This means that \(a \mid c.\)

Some Other Examples

The following relations are partial orders:

  • “The “less than or equal to” relation, denoted by \(\le,\) on the set of real numbers \(\mathbb{R}\) (which is in fact a total order);
  • Similarly, the “greater than or equal to” relation, denoted by \(\ge,\) on the set of real numbers \(\mathbb{R}\);
  • \(R = \left\{ {\left( {a,b} \right) \mid a,b \in Z, a = b + 1} \right\};\)
  • “\(a\) is an ancestor of \(b\)” is a partial order relation on the set of all people (provided each person is an ancestor of himself/herself);
  • The set of events in special relativity is described by a partial order. An event \(b\) can only be casually affected by an event \(a,\) if \(a \preccurlyeq b\) and both the events are in the future light cone.

Solved Problems

Click or tap a problem to see the solution.

Example 1

Which of these relations on the set \(A = \left\{ {1,2,3,4} \right\}\) are partial orders?
  1. \({R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,4} \right)} \right\}.\)
  2. \({R_2} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {3,4} \right)} \right\},\) \(\kern-2pt\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.\)
  3. \({R_3} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {3,2} \right),\left( {3,4} \right),\left( {4,4} \right)} \right\}\)
  4. \({R_4} = \left\{ {\left( {1,1} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {2,4} \right),} \right.\) \(\kern-2pt\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\},\) \(\kern-2pt\left.{\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.\)

Example 2

Determine whether the relation \(R\) represented by the matrix is a partial order. \[{{M_R} = \left[ {{a_{ij}}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0\\ 0&1&0&0&0\\ 1&1&1&1&1\\ 0&0&0&1&0\\ 0&0&0&1&1 \end{array}} \right]}\]

Example 3

The divisibility relation is given on the set \(A = \left\{ {2,3,4,6,8,10} \right\}.\) List all the non-comparable pairs of elements of \(A.\)

Example 4

Suppose \(R\) is a partial order on a set \(A.\) Prove that \(R^{-1}\) is also a partial order.

Example 5

Let \(R\) and \(S\) be partial orders on a set \(A.\) Determine whether the intersection relation \(R \cap S\) is also a partial order on \(A.\)

Example 6

Let \(R\) and \(S\) be partial orders on a set \(A.\) Determine whether the union relation \(R \cup S\) is also a partial order on \(A.\)

Example 1.

Which of these relations on the set \(A = \left\{ {1,2,3,4} \right\}\) are partial orders?
  1. \({R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,4} \right)} \right\}.\)
  2. \({R_2} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {3,3} \right),\left( {3,4} \right)} \right\},\) \(\kern-2pt\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.\)
  3. \({R_3} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.\) \(\kern-2pt\left.{\left( {3,2} \right),\left( {3,4} \right),\left( {4,4} \right)} \right\}\)
  4. \({R_4} = \left\{ {\left( {1,1} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {2,4} \right),} \right.\) \(\kern-2pt\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\},\) \(\kern-2pt\left.{\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.\)

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 reflexive, antisymmetric, and transitive, so it is 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.

Example 2.

Determine whether the relation \(R\) represented by the matrix is a partial order. \[{{M_R} = \left[ {{a_{ij}}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0\\ 0&1&0&0&0\\ 1&1&1&1&1\\ 0&0&0&1&0\\ 0&0&0&1&1 \end{array}} \right]}\]

Solution.

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

\[\left( {1,1} \right),\left( {2,2} \right), \ldots ,\left( {5,5} \right).\]

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

\[{a_{ij}} \ne {a_{ji}} \text{ for } i \ne j.\]

For example,

\[{a_{12}} \ne {a_{21}},\;{a_{31}} \ne {a_{13}}.\]

The relation \(R\) is transitive:

\[{a_{31}} = 1, {a_{12}} = 1, \text{ and }{a_{32}} = 1;\]

\[{a_{35}} = 1, {a_{54}} = 1, \text{ and }{a_{34}} = 1.\]

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

Example 3.

The divisibility relation is given on the set \(A = \left\{ {2,3,4,6,8,10} \right\}.\) List all the non-comparable pairs of elements of \(A.\)

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:

\[{\left( {2,3} \right),\left( {3,4} \right),\left( {3,8} \right),\left( {3,10} \right),}\kern0pt{\left( {4,6} \right),}\kern0pt{\left( {4,10} \right),}\kern0pt{\left( {6,8} \right),\left( {6,10} \right),}\kern0pt{\left( {8,10} \right).}\]

Example 4.

Suppose \(R\) is a partial order on a set \(A.\) Prove that \(R^{-1}\) is also a partial order.

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:

\[{\text{If} \left( {a,b} \right) \in R \text{ and} \left( {b,a} \right) \in R,\;}\kern0pt{ \text{then } a = b.}\]

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

\[{\text{If} \left( {b,a} \right) \in R^{-1} \text{ and} \left( {a,b} \right) \in R^{-1},\;}\kern0pt{ \text{then } a = b,}\]

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

\[\left( {b,a} \right) \in R \text{ and} \left( {c,b} \right) \in R.\]

Since \(R\) is transitive, we have

\[{\left( {c,a} \right) \in R,}\; \Rightarrow {\left( {a,c} \right) \in {R^{ – 1}}.}\]

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

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

Example 5.

Let \(R\) and \(S\) be partial orders on a set \(A.\) Determine whether the intersection relation \(R \cap S\) is also a partial order on \(A.\)

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

\[\left( {a,a} \right) \in R \text{ and } \left( {a,a} \right) \in S.\]

Hence

\[\left( {a,a} \right) \in R \cap S\]

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

\[{\left( {a,b} \right) \in R \cap S \text{ and }}\kern0pt{ \left( {b,a} \right) \in R \cap S,}\]

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

\[\left( {a,b} \right) \in R,\;\left( {b,a} \right) \in R, \text{ and }\]

\[\left( {a,b} \right) \in S,\;\left( {b,a} \right) \in S,\]

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

\[{\left( {a,b} \right) \in R \cap S \text{ and }}\kern0pt{\left( {b,c} \right) \in R \cap S.}\]

Then

\[\left( {a,b} \right) \in R,\;\left( {b,c} \right) \in R, \text{ and }\]

\[\left( {a,b} \right) \in S,\;\left( {b,c} \right) \in S.\]

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

\[\left( {a,c} \right) \in R \text{ and } \left( {a,c} \right) \in S,\]

so we have

\[\left( {a,c} \right) \in R \cap S,\]

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.

Example 6.

Let \(R\) and \(S\) be partial orders on a set \(A.\) Determine whether the union relation \(R \cup S\) is also a partial order on \(A.\)

Solution.

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

\[\left( {a,a} \right) \in R \text{ and } \left( {a,a} \right) \in S,\]

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

\[\left( {a,a} \right) \in R \cup S,\]

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:

\[{R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,3} \right),\left( {3,3} \right)} \right\},}\]

\[{S = \left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {2,2} \right),\left( {3,1} \right),}\right.}\kern0pt{\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\}.}\]

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

\[{R \cup S = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,1} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right),}\right.}\kern0pt{\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\}.}\]

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

\[X = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,2} \right),\left( {3,3} \right)} \right\},\]

\[Y = \left\{ {\left( {1,1} \right),\left( {2,2} \right),\left( {3,2} \right),\left( {3,3} \right)} \right\}.\]

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

\[{X \cup Y = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\}.}\]

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.