# 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. <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: