Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 1 down vote accepted

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 $$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.