LARA

Lattices

Definition: A lattice is a Partial order in which every two-element set has a least upper bound and a greatest lower bound.

Lemma: In a lattice every non-empty finite set has a lub ($\sqcup$) and glb ($\sqcap$).

Proof: is by induction!
Case where the set S has three elements x,y and z:
Let $a=(x \sqcup y) \sqcup z$.
By definition of $\sqcup$ we have $z \sqsubseteq a$ and $ x \sqcup y \sqsubseteq a $.
The we have again by definition of $\sqcup$, $x \sqsubseteq x \sqcup y$ and $y \sqsubseteq x \sqcup y$. Thus by transitivity we have $x \sqsubseteq a$ and $y \sqsubseteq a$.
Thus we have $S \sqsubseteq a$ and a is an upper bound.
Now suppose that there exists $a^\prime$ such that $S \sqsubseteq a^\prime$. We want $a \sqsubseteq a^\prime$ (a least upper bound):
We have $x \sqsubseteq a^\prime $ and $x \sqsubseteq a^\prime $, thus $x \sqcup y \sqsubseteq a^\prime$. But $z \sqsubseteq a^\prime $, thus $((x \sqcup y) \sqcup z) \sqsubseteq a^\prime $.
Thus $a$ is the lub of our 3 elements set.

Lemma: Every linear order is a lattice.

If a lattice has least and greatest element, then every finite set (including empty set) has a lub and glb.

This does not imply there are lub and glb for infinite sets.

Example: In the oder $([0,1),\le)$ with standard ordering on reals is a lattice, the entire set has no lub. The set of all rationals of interval $[0,10]$ is a lattice, but the set $\{ x \mid 0 \le x \land x^2 < 2 \}$ has no lub.

Definition: A complete lattice is a lattice where every set $S$ of elemenbts has lub, denoted $\sqcup S$, and glb, denoted $\sqcap S$ (this implies that there is top and bottom as $\sqcup \emptyset = \bot$ and $\sqcap \emptyset = \top$. This is because every element is an upper bound and a lower bound of $\emptyset$ : $\forall x. \forall y \in \emptyset. y \sqsubseteq x$ is valid, as well as $\forall x. \forall y \in \emptyset. y \sqsupseteq x$).

Note: if you know that you have least upper bounds for all sets, it follows that you also have greatest lower bounds.

Proof: by taking the least upper bound of the lower bounds. Converse also holds, dually.

Example: Every subset of the set of real numbers has a lub. This is an axiom of real numbers, the way they are defined (or constructed from rationals).

Lemma: In every lattice, $x \sqcup (x \sqcap y) = x$.
Proof:
We trivially have $x \sqsubseteq x \sqcup (x \sqcap y)$.
Let's prove that $x \sqcup (x \sqcap y) \sqsubseteq x$:
$x$ is an upper bound of $x$ and $x \sqcap y$, $x \sqcup (x \sqcap y)$ is the least upper bound of $x$ and $x \sqcap y$, thus $x \sqcup (x \sqcap y) \sqsubseteq x $.

Definition: A lattice is distributive iff

\begin{equation*} \begin{array}{l} x \sqcap (y \sqcup z) = (x \sqcap y) \sqcup (x \sqcap z) \\ x \sqcup (y \sqcap z) = (x \sqcup y) \sqcap (x \sqcup z) \end{array} \end{equation*}

Example: Lattice of all subsets of a set is distributive. Linear order is a distributive lattice. See examples of non-distributive lattices in Distributive lattice and the characterization of non-distributive lattices.

References