# Lattice (Order Theory)

A lat­tice is a par­tially or­dered set that is closed un­der bi­nary joins and meets.

Let $$L$$ be a lat­tice. Then for all $$p,q,r \in L$$ the fol­low­ing prop­er­ties are nec­es­sar­ily satis­fied.

• As­so­ci­a­tivity of joins and meets: $$(p \vee q) \vee r = p \vee (q \vee r)$$, and $$(p \wedge q) \wedge r = p \wedge (q \wedge r)$$

• Com­mu­ta­tivity of joins and meets: $$p \vee q = q \vee p$$ and $$p \wedge q = q \wedge p$$

• Idem­po­tency of joins and and meets: $$p \vee p = p$$ and $$p \wedge p = p$$

• Ab­sorp­tion: $$p \vee (p \wedge q) = p$$ and $$p \wedge (p \vee q) = p$$

Lemma 1: Let $$P$$ be a poset, $$S \subseteq P$$, and $$p \in P$$. If both $$\bigvee S$$ and $$(\bigvee S) \vee p$$ ex­ist then $$\bigvee (S \cup \{p\})$$ ex­ists as well, and $$(\bigvee S) \vee p = \bigvee (S \cup \{p\})$$.

Proof: See the Join fu ex­er­cise in Join and meet: Ex­er­cises.

## Associativity

Let $$L$$ be a lat­tice and $$p,q,r,s \in L$$ such that $$s = p \vee (q \vee r)$$. We ap­ply the above lemma, along with com­mu­ta­tivity and clo­sure of lat­tices un­der bi­nary joins, to get

$$p \vee (q \vee r) = (q \vee r) \vee p = (\bigvee \{q, r\}) \vee p = \bigvee (\{q, r\} \cup \{p\}) =$$
$$\bigvee \{ q, r, p \} = \bigvee (\{p, q\} \cup \{r\}) = (\bigvee \{p, q\}) \vee r = (p \vee q) \vee r.$$

By du­al­ity, we also have the as­so­ci­a­tivity of bi­nary meets.

## Commutativity

Let $$L$$ be a lat­tice and $$p,q \in L$$. Then $$p \vee q = \bigvee \{ p, q \} = q \vee p$$. Bi­nary joins are there­fore com­mu­ta­tive. By du­al­ity, bi­nary meets are also com­mu­ta­tive.

## Idempotency

Let $$L$$ be a lat­tice and $$p \in L$$. Then $$p \vee p = \bigvee \{ p \} = p$$. The prop­erty that for all $$p \in L$$, $$p \vee p = p$$ is called idem­po­tency. By du­al­ity, we also have the idem­po­tency of meets: for all $$p \in L$$, $$p \wedge p = p$$.

## Absorption

Since $$p \wedge q$$ is the great­est lower bound of $$\{p,q\}$$, $$p \wedge q \leq p$$. Be­cause $$p \leq p$$ and $$(p \wedge q) \leq p$$, $$p$$ is an up­per bound of $$\{p, p \wedge q\}$$, and so $$p \vee (p \wedge q) \leq p$$. On the other hand, $$p \vee (p \wedge q)$$ is the least up­per bound of $$\{p, p \wedge q\}$$, and so $$p \leq p \vee (p \wedge q)$$. By anti-sym­me­try, $$p = p \vee (p \wedge q)$$.

<div><div>

## Clo­sure un­der finite joins and meets

Let $$L$$ be a lat­tice and $$S = \{ s_1, ..., s_n \}$$ be some finite sub­set of $$L$$. Then an in­duc­tive ar­gu­ment shows that $$\bigvee S$$ ex­ists.

Here again, we will need Lemma 1, stated in the proofs of the four lat­tice prop­er­ties.

Our proof pro­ceeds by in­duc­tion on the car­di­nal­ity of $$S$$.

The base case is $$\bigvee \{ s_1 \} = s_1 \in L$$. For the in­duc­tive step, we sup­pose that $$\bigvee \{s_1, ..., s_i \}$$ ex­ists. Then, ap­ply­ing lemma 1, we have $$\bigvee \{s_1, ..., s_{i+1} \} = \bigvee \{s_1, ..., s_i \} \vee s_{i+1}$$. Ap­ply­ing our in­duc­tive hy­poth­e­sis and clo­sure un­der bi­nary joins, we have $$\bigvee \{s_1, ..., s_i \} \vee s_{i+1}$$ ex­ists. Lat­tices are there­fore closed un­der all finite joins, not just bi­nary ones. Dually, lat­tices are closed un­der all finite meets. <div><div>

## Ba­sic pos­i­tive examples

Here are two Hasse di­a­grams of posets which are lat­tices. com­ment:

dot source:

di­graph G { node = 0.1, height = 0.1 edge = “none” a = “” b = “” c = “” d = “”

rankdir = BT; a → b a → c b → d c → d } <div> com­ment:

dot source:

di­graph 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 }

<div>

## Ba­sic nega­tive examples

Here are two Hasse di­a­grams of posets which are not lat­tices. com­ment:

di­graph 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 }

<div>

In the above di­a­gram, the two bot­tom el­e­ments have no com­mon lower bounds. There­fore they have no meet, and so the de­picted poset is not a lat­tice. How­ever, it should be easy to ver­ify that this poset is closed un­der bi­nary joins. com­ment:

dot source:

di­graph G { node = 0.1, height = 0.1 edge = “none” a = “” b = “” c = “” d = “”

rankdir = BT; a → b c → d }

<div>

The Hasse di­a­gram of this poset has two con­nected com­po­nents. No el­e­ment from the left com­po­nent will have a meet or a join with any el­e­ment from the right com­po­nent. The de­picted poset is there­fore not a lat­tice.

## The con­nect­ing lemma

The con­nect­ing lemma states that for any lat­tice $$L$$ and $$p,q \in L$$, $$p \vee q = p \Leftrightarrow q \leq p$$ and du­ally, $$p \wedge q = p \Leftrightarrow q \geq p$$. This sim­ple but im­por­tant lemma is so named be­cause it es­tab­lishes a con­nec­tion be­tween the lat­tice’s join op­er­a­tor and its un­der­ly­ing poset or­der.

We prove $$p \vee q = p \Leftrightarrow q \leq p$$; the other part fol­lows from du­al­ity. If $$p \vee q = p$$, then $$p$$ is an up­per bound of both $$p$$ and $$q$$, and so $$q \leq p$$. Go­ing the other di­rec­tion, sup­pose $$q \leq p$$. Since $$p$$ is and up­per bound of it­self by re­flex­ivity, it then fol­lows that $$p$$ is an up­per bound of $$\{p, q\}$$. There can­not be a lesser up­per bound of $$\{p, q\}$$ be­cause it would not be an up­per bound of $$p$$. Hence, $$p \vee q = p$$.

<div><div>

## Lat­tices as alge­braic structures

It’s also pos­si­ble to for­mu­late lat­tices as alge­braic struc­tures $$\langle L, \vee, \wedge \rangle$$ satis­fy­ing the as­so­ci­a­tivity, com­mu­ta­tivity, idem­po­tency, and ab­sorp­tion laws de­scribed above. A poset $$\langle L, \leq \rangle$$ can then be defined such that for $$p, q \in L$$, $$p \leq q$$ when­ever $$p \vee q = q$$. It can be shown that this poset is closed un­der bi­nary meets and joins, and that these meets and joins are equal to the cor­re­spond­ing meets and joins of the alge­braic lat­tice.