MathWiki

$\newcommand{\divby}{\mathrel{\vdots}}$

Ordered sets

A lattice is actually a special type of a partially ordered set.

A relation $\prec$ on a set $X$ is a partial order if

$x \prec x$ for all $x \in X$
(i.e., $\prec$ is reflexive),
$x \prec y$ and $y \prec z$ imply $x \prec z$ for all $x,y,z \in X$
(i.e., $\prec$ is transitive),
$x \prec y$ and $y \prec x$ imply $x = y$ for all $x,y \in X$
(i.e., $\prec$ is antisymmetric).

A set with a partial order on it is called a partially ordered set (or simply a poset).

Examples of posets include, e.g.,

$\mathbb Z$, $\mathbb N$, or any other subset of the set of all reals $\mathbb R$ with the usual “less than or equal” relation $\le$ (or “greater than or equal” $\ge$),
any collection of sets with the inclusion relation $\subset$, e.g., $\{\{1\}, \{1,2\}, \{3\}, \emptyset\}$.
$\mathbb N$ with the division relation $\mid$.

Note that $\mathbb Z$ with the division relation is not a poset as this relation is not antisymmetric on $\mathbb Z$ (because, e.g., $1 \mid -1$ and $-1 \mid 1$ but $1 \neq -1$). ¹⁾

Similarly to the lattice of divisibility above, we can represent any finite poset via a Hasse diagram, e.g.:

A partial order $\prec$ on a set $X$ is total (aka linear) if

$x \prec y$ or $y \prec x$ for any two $x, y \in X$.

In other words, a poset is totally ordered if and only if no two of its elements are incomparable.

Of the examples above, sets in 1. are totally ordered, while the set in 3. is not, because, e.g., $2$ and $3$ are incomparable (neither $2 \mid 3$ nor $3 \mid 2$).

Which of the following sets are totally ordered?

The set on the Hasse diagram above. Answer No, because, e.g., $\{1\}$ and $\{3\}$ are incomparable.
The set given by the following diagram. Answer Yes.
The set of all integer pairs $\mathbb Z \times \mathbb Z$ with the coordinatewise comparison (i.e., $(x,y) \leq (v,w)$ if and only if $x \leq v$ and $y \leq w$). Answer No, because, e.g., (1,2) and (2,1) are incomparable.
The set of all integer pairs $\mathbb Z \times \mathbb Z$ with the lexicographical comparison (i.e., $(x,y) \leq (v,w)$ if and only if $x < v$, or $x = v$ and $y \leq w$). Answer Yes.

The least upper bound (aka supremum) of a subset $A$ of a partially ordered set $X$ (denoted $\sup A$) is an element $x \in X$ such that

$a \prec x$ for all $a \in A$ (i.e., $x$ is an upper bound of $A$),
$x \prec y$ for any other upper bound $y$ of $A$.

The least upper bound may not always exist, but when it does exist, it is unique.

The symmetrical notion, the greatest lower bound (aka infimum) of $A$ is denoted $\inf A$.

A lattice $X$ is a poset in which any two elements $x,y \in X$ have both the least upper bound $\sup(x,y) \in X$ and the greatest lower bound $\inf(x,y) \in X$.

¹⁾

But this relation is a preorder on $\mathbb Z$.