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.

A diamond shaped lattice

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>

A cube shaped lattice

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.

A simple non-lattice

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.

Another simple non-lattice

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.

Ad­di­tional material

For more ex­am­ples of lat­tices, see Lat­tice: Ex­am­ples. For some ex­er­cises in­volv­ing the con­cepts in­tro­duced on this page, see Lat­tice: Ex­er­cises.

Children:

Parents:

  • Order theory

    The study of bi­nary re­la­tions that are re­flex­ive, tran­si­tive, and an­ti­sym­metic.