1
$\begingroup$

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?

  • 0
    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$).2012-07-03

1 Answers 1

1

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 $