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