Lattice: Exercises

Try these ex­er­cises to test your knowl­edge of lat­tices.

Distributivity

Does the lat­tice meet op­er­a­tor dis­tribute over joins? In other words, for all lat­tices \(L\) and all \(p, q, r \in L\), is it nec­es­sar­ily true that \(p \wedge (q \vee r) = (p \wedge q) \vee (p \wedge r)\)? Prove your an­swer.

The fol­low­ing coun­terex­am­ple shows that lat­tice meets do not nec­es­sar­ily dis­tribute over joins.

A non-distributive lattice called as M3

<div><div>

com­ment: dot source:

di­graph G { node = 0.1, height = 0.1 edge = “none”

rankdir = BT; t → p t → q t → r p → s q → s r → s } <div>%%

In the above lat­tice, \(p \wedge (q \vee r) = p \neq t = (p \wedge q) \vee (p \wedge r)\). %%

Com­mon elements

Let \(L\) be a lat­tice, and let \(J\) and \(K\) be two finite sub­sets of \(L\) with a non-empty in­ter­sec­tion. Prove that \(\bigwedge J \leq \bigvee K\).

If \(J\) and \(K\) have a non-empty in­ter­sec­tion, then there ex­ists some lat­tice el­e­ment \(p\) such that \(p \in J\) and \(p \in K\). Since \(\bigwedge J\) is a lower bound of \(J\), we have \(\bigwedge J \leq p\). Since \(\bigvee K\) is an up­per bound of \(K\), we have \(p \leq \bigvee K\). By tran­si­tivity, we have \(\bigwedge J \leq p \leq \bigvee K\).

Another inequality

Let \(L\) be a lat­tice, and let \(J\) and \(K\) be two finite sub­sets of \(L\) such that for all \(j \in J\) and \(k \in K\), \(j \leq k\). Prove that \(\bigvee J \leq \bigwedge K\).

Rephras­ing the prob­lem state­ment, we have that ev­ery el­e­ment of \(J\) is a lower bound of \(K\) and that ev­ery el­e­ment of \(K\) is an up­per bound of \(J\). It the fol­lows that for \(j \in J\), \(j \leq \bigwedge K\). Hence, \(\bigwedge K\) is an up­per bound of \(J\), and there­fore it is greater than or equal to the least up­per bound of \(J\): \(\bigvee J \leq \bigwedge K\).

The min­i­max theorem

Let \(L\) be a lat­tice and \(A\) an \(m \times n\) ma­trix of el­e­ments of \(L\). Prove the fol­low­ing in­equal­ity:

$$\bigvee_{i=1}^m \bigwedge_{j=1}^n A_{ij} \leq \bigwedge_{j=1}^n \bigvee_{i=1}^m A_{ij}$$
.

To get an in­tu­itive feel for this the­o­rem, it helps to first con­sider a small con­crete in­stan­ti­a­tion. Con­sider the \(3 \times 3\) ma­trix de­picted be­low, with el­e­ments \(a,b,c,d,e,f,g,h\), and \(i\). The in­equal­ity in­stan­ti­ates to \((a \wedge b \wedge c) \vee (d \wedge e \wedge f) \vee (g \wedge h \wedge i) \leq (a \vee d \vee g) \wedge (b \vee e \vee h) \wedge (c \vee f \vee i)\). Why would this in­equal­ity hold?

$$\left[ \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \\ \end{array} \right]$$

No­tice that each paren­the­sized ex­pres­sion on the left hand side of the in­equal­ity shares an el­e­ment with each paren­the­sized ex­pres­sion on the right hand side of the in­equal­ity.This is true be­cause the paren­the­sized ex­pres­sions on the left hand side cor­re­spond to rows and the paren­the­sized ex­pres­sions on the right hand side cor­re­spond to columns; each row of a ma­trix shares an el­e­ment with each of its columns. The the­o­rem proven in the Com­mon el­e­ments ex­er­cise above then tells us that each paren­the­sized ex­pres­sion on the left hand side is less than or equal to each paren­the­sized ex­pres­sion on the right hand side.

Let \(J = \{ a \wedge b \wedge c, d \wedge e \wedge f, g \wedge h \wedge i \}\) and \(K = \{ a \vee d \vee g, b \vee e \vee h, c \vee f \vee i \}\). Then the hy­poth­e­sis for the the­o­rem proven in the Another in­equal­ity ex­er­cise holds, giv­ing us \(\bigvee J \leq \bigwedge K\), which is ex­actly what we wanted to prove. Ex­tend­ing this ap­proach to the gen­eral case is straight­for­ward. <div><div>

Parents:

  • Lattice (Order Theory)

    A poset that is closed un­der bi­nary joins and meets.

    • Order theory

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