# Calculus

## Set Theory # 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,

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

See solved problems on Page 2.