Lattice (Order Theory) - AI Alignment Forum

A lattice is a partially ordered set that is closed under binary joins and meets.

Let be a lattice. Then for all $p, q, r \in L$ the following properties are necessarily satisfied.

Associativity of joins and meets: $(p \lor q) \lor r = p \lor (q \lor r)$ , and $(p \land q) \land r = p \land (q \land r)$

Commutativity of joins and meets: $p \lor q = q \lor p$ and $p \land q = q \land p$

Idempotency of joins and and meets: $p \lor p = p$ and $p \land p = p$

Absorption: $p \lor (p \land q) = p$ and $p \land (p \lor q) = p$

Proofs

Lemma 1: Let $P$ be a poset, $S \subseteq P$ , and $p \in P$ . If both $⋁ S$ and $(⋁ S) \lor p$ exist then $⋁ (S \cup {p})$ exists as well, and $(⋁ S) \lor p = ⋁ (S \cup {p})$ .

Proof: See the Join fu exercise in Join and meet: Exercises.

Associativity

Let $L$ be a lattice and $p, q, r, s \in L$ such that $s = p \lor (q \lor r)$ . We apply the above lemma, along with commutativity and closure of lattices under binary joins, to get $p \lor (q \lor r) = (q \lor r) \lor p = (⋁ {q, r}) \lor p = ⋁ ({q, r} \cup {p}) =$ $⋁ {q, r, p} = ⋁ ({p, q} \cup {r}) = (⋁ {p, q}) \lor r = (p \lor q) \lor r .$

By duality, we also have the associativity of binary meets.

Commutativity

Let $L$ be a lattice and $p, q \in L$ . Then $p \lor q = ⋁ {p, q} = q \lor p$ . Binary joins are therefore commutative. By duality, binary meets are also commutative.

Idempotency

Let $L$ be a lattice and $p \in L$ . Then $p \lor p = ⋁ {p} = p$ . The property that for all $p \in L$ , $p \lor p = p$ is called idempotency. By duality, we also have the idempotency of meets: for all $p \in L$ , $p \land p = p$ .

Absorption

Since $p \land q$ is the greatest lower bound of ${p, q}$ , $p \land q \leq p$ . Because $p \leq p$ and $(p \land q) \leq p$ , $p$ is an upper bound of ${p, p \land q}$ , and so $p \lor (p \land q) \leq p$ . On the other hand, $p \lor (p \land q)$ is the least upper bound of ${p, p \land q}$ , and so $p \leq p \lor (p \land q)$ . By anti-symmetry, $p = p \lor (p \land q)$ .

Closure under finite joins and meets

Let $L$ be a lattice and $S = {s_{1}, . . ., s_{n}}$ be some finite subset of $L$ . Then an inductive argument shows that $⋁ S$ exists.

Proof

Here again, we will need Lemma 1, stated in the proofs of the four lattice properties.

Our proof proceeds by induction on the cardinality of $S$ .

The base case is $⋁ {s_{1}} = s_{1} \in L$ . For the inductive step, we suppose that $⋁ {s_{1}, . . ., s_{i}}$ exists. Then, applying lemma 1, we have $⋁ {s_{1}, . . ., s_{i + 1}} = ⋁ {s_{1}, . . ., s_{i}} \lor s_{i + 1}$ . Applying our inductive hypothesis and closure under binary joins, we have $⋁ {s_{1}, . . ., s_{i}} \lor s_{i + 1}$ exists. Lattices are therefore closed under all finite joins, not just binary ones. Dually, lattices are closed under all finite meets.

Basic positive examples

Here are two Hasse diagrams of posets which are lattices.

A diamond shaped lattice

dot source:

digraph G { node = 0.1, height = 0.1 edge = "none" a = "" b = "" c = "" d = ""

rankdir = BT; a -> b a -> c b -> d c -> d }

A cube shaped lattice

dot source:

digraph G { node = 0.1, height = 0.1 edge = "none" a = "" b = "" c = "" d = "" e = "" f = "" g = "" h = ""

rankdir = BT; a -> b a -> c a -> d b -> e b -> f c -> e c -> g d -> f d -> g e -> h f -> h g -> h }

Basic negative examples

Here are two Hasse diagrams of posets which are not lattices.

A simple non-lattice

digraph G { node = 0.1, height = 0.1 edge = "none" a = "" b = "" c = "" d = "" e = "" f = "" g = "" h = ""

rankdir = BT; a -> b a -> c a -> d b -> e b -> f c -> e c -> g d -> f d -> g e -> h f -> h g -> h }

In the above diagram, the two bottom elements have no common lower bounds. Therefore they have no meet, and so the depicted poset is not a lattice. However, it should be easy to verify that this poset is closed under binary joins.

Another simple non-lattice

dot source:

digraph G { node = 0.1, height = 0.1 edge = "none" a = "" b = "" c = "" d = ""

rankdir = BT; a -> b c -> d }

The Hasse diagram of this poset has two connected components. No element from the left component will have a meet or a join with any element from the right component. The depicted poset is therefore not a lattice.

The connecting lemma

The connecting lemma states that for any lattice $L$ and $p, q \in L$ , $p \lor q = p \Leftrightarrow q \leq p$ and dually, $p \land q = p \Leftrightarrow q \geq p$ . This simple but important lemma is so named because it establishes a connection between the lattice's join operator and its underlying poset order.

Proof

We prove $p \lor q = p \Leftrightarrow q \leq p$ ; the other part follows from duality. If $p \lor q = p$ , then $p$ is an upper bound of both $p$ and $q$ , and so $q \leq p$ . Going the other direction, suppose $q \leq p$ . Since $p$ is and upper bound of itself by reflexivity, it then follows that $p$ is an upper bound of ${p, q}$ . There cannot be a lesser upper bound of ${p, q}$ because it would not be an upper bound of $p$ . Hence, $p \lor q = p$ .

Lattices as algebraic structures

It's also possible to formulate lattices as algebraic structures $⟨ L, \lor, \land ⟩$ satisfying the associativity, commutativity, idempotency, and absorption laws described above. A poset $⟨ L, \leq ⟩$ can then be defined such that for $p, q \in L$ , $p \leq q$ whenever $p \lor q = q$ . It can be shown that this poset is closed under binary meets and joins, and that these meets and joins are equal to the corresponding meets and joins of the algebraic lattice.

Additional material

For more examples of lattices, see Lattice: Examples. For some exercises involving the concepts introduced on this page, see Lattice: Exercises.