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

## Ordered sets

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

**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$). ^{1)}

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

**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
- 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
- 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

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

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

^{1)}But this relation is a preorder on $\mathbb Z$.