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 \({\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,

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}\);
• "\(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.