$\newcommand{\divby}{\mathrel{\vdots}}$
===== Ordered sets =====
A **lattice** is actually a special type of a **partially ordered set**.

<box 100% round blue>
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**).
</box>
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$). ((But this relation is a [[http://en.wikipedia.org/wiki/Preorder|preorder]] on $\mathbb Z$.))

Similarly to the lattice of divisibility above, we can represent any finite poset via a **Hasse diagram**, e.g.:
<graphviz dot center>
digraph {
	rankdir=BT;
	node [shape = box];
        "{}" -> "{1}",
        "{1}" -> "{1,2}",
        "{}"-> "{3}"
}
</graphviz>

<box 100% round blue>
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.
</box>

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

<WRAP task>
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. |
<graphviz dot center>
digraph {
	rankdir=BT;
	node [shape = circle];
        "a" -> "b",
        "b" -> "c",
        "c"-> "d"
}
</graphviz>++ ++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.++
</WRAP>

<box 100% round blue>
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$.
</box>

<box 100% round blue>
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$.
</box>


-----------------------------------------------------------------------------------------------------------------------------------------