• English only

# 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 () and glb ().

Proof: is by induction!
Case where the set S has three elements x,y and z:
Let .
By definition of we have and .
The we have again by definition of , and . Thus by transitivity we have and .
Thus we have and a is an upper bound.
Now suppose that there exists such that . We want (a least upper bound):
We have and , thus . But , thus .
Thus 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 with standard ordering on reals is a lattice, the entire set has no lub. The set of all rationals of interval is a lattice, but the set has no lub.

Definition: A complete lattice is a lattice where every set of elemenbts has lub, denoted , and glb, denoted (this implies that there is top and bottom as and . This is because every element is an upper bound and a lower bound of : is valid, as well as ).

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, .
Proof:
We trivially have .
Let's prove that :
is an upper bound of and , is the least upper bound of and , thus .

Definition: A lattice is distributive iff

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

sav08/lattices.txt · Last modified: 2015/04/21 17:30 (external edit)

© EPFL 2018 - Legal notice