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

To denote a partial order relation we use the notation \({\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, transitive, and hence, asymmetric.

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:

See solved problems on Page 2.

Page 1 Page 2