Partial order

A partial ordering on a set is a binary relation that is reflexive, antisymmetric, and transitive.

In most cases, we denote the partial ordering with the \(\boldsymbol{\preceq}\) symbol and sometimes with the \(\boldsymbol{\le}\) symbol.

Thus, for a set \(X\), \(\preceq\) is a partial order on \(X\) if

1. For every \(x\in X\): \(x\preceq x\);
2. For all \(x,y\in X\): if \(x\preceq y\) and \(y\preceq x\), then \(x=y\);
3. For all \(x,y,z\in X\): if \(x\preceq y\) and \(y\preceq z\), then \(x\preceq z\).

A partial orderong \(\preceq\) is called a total ordering or linear ordering on \(X\) if for all \(x,y\in X\): \(x\preceq y\) or \(y\preceq x\), or both.

Examples

The relation "is less than or equal to" on the set of real numbers is a total ordering.

The relation "is greater than or equal to" on the set of real numbers is a total ordering.

The relation "is a divisor of" on the set \(\mathbb{N}\backslash\{0\}\) is a partial ordering. This is not a total ordering because, for example, \(2\) is not a divisor of \(5\), and \(5\) is also not a divisor of \(2\).

The relation "is a divisor of" on the set \(\{1,2,4,8\}\) is a total ordering.

The relation "is a subset of" on the power set \({\Large\wp}(X)\) of a certain set \(X\) is a partial ordering. This is not a total ordering, unless \(X\) is the empty set or contains only one element.

Lower and upper bounds

Let \(X\) be a set with a partial ordering \(\preceq\), and \(S\subset X\).

• \(y\in X\) is called an upper bound of \(S\) if \(x\preceq y\) for all \(x\in S\).
• \(z\in X\) is called a least upper bound or supremum of \(S\), denoted as \(z=\mathrm{sup}(S)\), if \(z\) is an upper bound of \(S\) and moreover for every (other) upper bound \(y\) of \(S\): \(z\preceq y\).
• Similarly, \(y\in X\) is called a lower bound of \(S\) if \(y\preceq x\) for all \(x\in S\).
• \(z\in X\) is called a greatest lower bound or infimum of \(S\), denoted as \(z=\mathrm{inf}(S)\), if \(z\) is a lower bound of \(S\) and moreover for every (other) lower bound \(y\) of \(S\): \(y\preceq z\).

If a supremum or infimum of \(S\) exists, then it is unique.

Example

We consider the partial ordering "is a divisor of" on the set \(X=\{1,2,3,4,6,8,9,12,18,24\}\).

For \(S=\{4,6\}\), \(1\) and \(2\) are the lower bounds of \(S\) and \(\mathrm{inf}(S)=2\). The numbers \(12\) and \(24\) are upper bounds of \(S\) and \(\mathrm{sup}(S)=24\).

For \(S=\{3,4,6\}\), \(1\) is the only lower bound of \(S\) and thus \(\mathrm{inf}(S)=1\). The numbers \(12\) and \(24\) are the upper bounds of \(S\) and \(\mathrm{sup}(S)=12\).

For \(S=\{4,6,9\}\), \(1\) is the only lower bound of \(S\) and thus \(\mathrm{inf}(S)=1\). There does not exist an upper bound of \(S\).