Lattice (Order Theory)

Try these exercises to test your knowledge of lattices.

Distributivity

Does the lattice meet operator distribute over joins? In other words, for all lattices and all $p, q, r \in L$ , is it necessarily true that $p \land (q \lor r) = (p \land q) \lor (p \land r)$ ? Prove your answer.

Solution

The following counterexample shows that lattice meets do not necessarily distribute over joins.

A non-distributive lattice called as M3

In the above lattice, $p \land (q \lor r) = p \neq t = (p \land q) \lor (p \land r)$ .

Common elements

Let $L$ be a lattice, and let $J$ and $K$ be two finite subsets of $L$ with a non-empty intersection. Prove that $⋀ J \leq ⋁ K$ .

Solution

If $J$ and $K$ have a non-empty intersection, then there exists some lattice element $p$ such that $p \in J$ and $p \in K$ . Since $⋀ J$ is a lower bound of $J$ , we have $⋀ J \leq p$ . Since $⋁ K$ is an upper bound of $K$ , we have $p \leq ⋁ K$ . By transitivity, we have $⋀ J \leq p \leq ⋁ K$ .

Another inequality

Let $L$ be a lattice, and let $J$ and $K$ be two finite subsets of $L$ such that for all $j \in J$ and $k \in K$ , $j \leq k$ . Prove that $⋁ J \leq ⋀ K$ .

Solution

Rephrasing the problem statement, we have that every element of $J$ is a lower bound of $K$ and that every element of $K$ is an upper bound of $J$ . It the follows that for $j \in J$ , $j \leq ⋀ K$ . Hence, $⋀ K$ is an upper bound of $J$ , and therefore it is greater than or equal to the least upper bound of $J$ : $⋁ J \leq ⋀ K$ .

The minimax theorem

Let $L$ be a lattice and $A$ an $m \times n$ matrix of elements of $L$ . Prove the following inequality: $m ⋁ i = 1 n ⋀ j = 1 A_{i j} \leq n ⋀ j = 1 m ⋁ i = 1 A_{i j}$ .

Solution

To get an intuitive feel for this theorem, it helps to first consider a small concrete instantiation. Consider the $3 \times 3$ matrix depicted below, with elements $a, b, c, d, e, f, g, h$ , and $i$ . The inequality instantiates to $(a \land b \land c) \lor (d \land e \land f) \lor (g \land h \land i) \leq (a \lor d \lor g) \land (b \lor e \lor h) \land (c \lor f \lor i)$ . Why would this inequality hold?

$⎡ ⎢ ⎣ \begin{matrix} a & b & c d & e & f g & h & i \end{matrix} ⎤ ⎥ ⎦$

Notice that each parenthesized expression on the left hand side of the inequality shares an element with each parenthesized expression on the right hand side of the inequality.This is true because the parenthesized expressions on the left hand side correspond to rows and the parenthesized expressions on the right hand side correspond to columns; each row of a matrix shares an element with each of its columns. The theorem proven in the Common elements exercise above then tells us that each parenthesized expression on the left hand side is less than or equal to each parenthesized expression on the right hand side.

Let $J = {a \land b \land c, d \land e \land f, g \land h \land i}$ and $K = {a \lor d \lor g, b \lor e \lor h, c \lor f \lor i}$ . Then the hypothesis for the theorem proven in the Another inequality exercise holds, giving us $⋁ J \leq ⋀ K$ , which is exactly what we wanted to prove. Extending this approach to the general case is straightforward.

LESSWRONG
LW

Lattice: Exercises

Distributivity

Common elements

Another inequality

The minimax theorem

LESSWRONG
LW

Lattice: Exercises

Distributivity

Common elements

Another inequality

The minimax theorem