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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer

Your Answer


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.