The Mini-Max theorem for lattices

Question

I'm asking for help on an exercise in Davey and Priestleys's Introduction to Lattices and Orders. For those with the book, the exercise is specifically 2.9.

Let $A=(a_{ij})$ be an $m\times n$ matrix with entries in a lattice $L$. Show that $$\bigvee_{j=1}^n\left(\bigwedge_{i=1}^m a_{ij}\right)\leq\bigwedge_{k=1}^m\left(\bigvee_{l=1}^n a_{kl}\right)$$

The left-hand-side represents the supremum of the cumulative infimums down the columns, and the right-hand-side represents the infimum of the cumulative supremums across the rows.

Now, I'm sure this could be accomplished by induction, but there has to be a cleaner way to do this. And I believe I found the result needed in the book to get a quick proof. For those with the reference, it's Lemma 2.27i). It reads:

Let $P$ and $Q$ be ordered sets. Let $\phi:P\rightarrow Q$ be an order-preserving map. Suppose $S\subseteq P$ is such that $\bigvee S$ exists in $P$ and $\bigvee\phi(S)$ exists in $Q$. Then $\bigvee\phi(S)\leq\phi(\bigvee S)$

However, I'm having difficulty in seeing what my $P$ and $Q$ and $\phi$ would be here from looking at the matrix $A$.

I think $P$ would be $L^m$ with its product order, and that $Q$ is $L^n$ with its product order. But then again, the inequality above only concerns elements of $L$ and not $L^m$ or $L^n$. So, I'm stuck.

Any help in completing this exercise is appreciated. Or a hint in the right direction would be nice if my approach is flawed.

Answer 1

Hint: Try to use the same approach which is used when proving usual distributive inequality. Start with the following inequalities: $$\bigwedge_{i = 1}^m a_{ij} \leqslant a_{kj} \leqslant \bigvee_{l = 1}^n a_{kl},\ k = \overline{1, m},\ j = \overline{1, n}.$$

Answer 2

Remember that, by definition of $\bigvee$, any inequality of the form $\bigvee_px_p\leq y$ is equivalent to saying that $x_p\leq y$ for every $p$. Similarly, any inequality of the form $w\leq\bigwedge_qz_q$ is equivalent to saying that $w\leq z_q$ for every $q$. In the situation of your question, both of these facts can be applied to simplify the problem. Then you can finish the job with Random Jack's hint.

Answer 3

the combination of the above two replies yields:

$\hspace{1em} \bigvee_{j=1}^n\left(\bigwedge_{i=1}^m a_{ij}\right)\leq\bigwedge_{k=1}^m\left(\bigvee_{l=1}^n a_{kl}\right) \\ \equiv\hspace{4em} \{ \text{$\vee$-characterization: } \bigvee X \leq u \equiv (\forall x \in X \bullet x \leq u)\} \\ \hspace{1em}\forall j \in 1..n \bullet \bigwedge_{i=1}^m a_{ij}\leq\bigwedge_{k=1}^m\left(\bigvee_{l=1}^n a_{kl}\right) \\ \equiv\hspace{4em} \{ \text{$\land$-characterization: } l \leq \bigwedge X \equiv (\forall x \in X \bullet l \leq x)\} \\ \hspace{1em}\forall j \in 1..n \bullet \forall k \in 1..m \bullet \bigwedge_{i=1}^m a_{ij}\leq\bigvee_{l=1}^n a_{kl} \\ \Leftarrow\hspace{4em} \{ \text{$\leq$-transitivity} \} \\ \hspace{1em}\forall j \in 1..n \bullet \forall k \in 1..m \bullet \bigwedge_{i=1}^m a_{ij}\leq a_{kj} \leq\bigvee_{l=1}^n a_{kl} \\ \equiv\hspace{4em} \{ \text{Weakening/strengthening: }\forall x \in X \bullet \bigwedge X \leq x \leq \bigvee X \} \\\hspace{1em} \mathsf{ true } $

Hope this helps :)