- English only

# Lab for Automated Reasoning and Analysis 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 () 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.