# lattice constraint decomposition

In lattice we have the following equivalences

$x \vee y \le z \Longleftrightarrow {x \le z } \space \& \space { y \le z}$

and, dually

$z \le x \wedge y \Longleftrightarrow z \le x \space \& \space z \le y$

However, I'm unable to decompose constraints

$z \le x \vee y$

$x \wedge y \le z$

and wonder why this skew of symmetry? Naively, I've expected logical disjunction, and more generally, is it possible to decompose lattice constraint into disjunction?

-
Look at the lattice $(\mathbb N, \mid)$. We have $4 \vee 9 = 36$ and $6 \mid 4 \vee 9$, but $6 \nmid 4$, $6 \nmid 9$ ... – martini Jul 2 '12 at 21:08
Mace4 exhibits even simpler 2-element BA counterexample. I still fail to intuitively grasp why this is the case. – Tegiri Nenashi Jul 2 '12 at 21:29
Oops, according to Alex answer 2-element BA (which is total order) should be fine. The counterexample is a structure with 4 elements (powerset $2^2$). – Tegiri Nenashi Jul 3 '12 at 0:02

This is true for a totally-ordered lattice, such as $(\mathbb R,\leq)$, as then $x\vee y$ and $x\wedge y$ are either $x$ or $y$. The problem arises when the lattice is not totally-ordered, so you can't necessarily compare $z$ and $x$ or $z$ and $y$ even if you can compare $z$ and $x\vee y$ or $x\wedge y$. Intuitively, this happens because when a lattice is not totally ordered, $x$ and $y$ may be "far away" from each other even if they are roughly as "high up" (for example, $\{0,1\}$ and $\{2,3\}$ are "far away" yet the same "height" in the lattice $(\mathcal P(\{0,1,2,3\}),\subseteq)$), so $x\vee y$ and $x\wedge y$ end up being far away from $x$ and $y$. We can modify your statement slightly to get around this difficulty:
If $z$ is comparable to $x$ and $y$ (i.e. either $z\leq x$ or $x\leq z$, similarly for $y$), then $$z\leq x\vee y\iff z\leq x\text{ or } z\leq y$$ $$x\wedge y\leq y\iff x\leq z\text{ or } y\leq z$$