1
$\begingroup$

Lattices are kind of new to me and I'm not yet familiar with all of their properties so excuse me if what I'm asking here is extremely basic or easy.

How can I prove the following inequality for a lattice?

$$x\,(y+z) \geq (x\,y)+(x\,z)$$

  • 1
    My lattices usually have $\land$ and $\lor$ as operators, with order $a\leq b\Leftrightarrow a\land b = a$, while multiplication and addition are for boolean algebras; how are you defining order in your boolean algebra?2011-09-07
  • 0
    Well, I suppose it has to work for any given order... Also ∧ and ∨ work like * and + .2011-09-07
  • 0
    Of course not! If it did, how could it possibly apply to both one order and its reversal? There has to be a specific, "canonical" ordering you are selecting, just like there is a canonical ordering for a lattice (the one I mentioned).2011-09-07
  • 0
    oh! It is a grid after all! Sorry I get lost in translation so easily.2011-09-07
  • 0
    Huh? I'm afraid I don't understand your last comment. (And there are other definitions of "lattice" that are unrelated to the theory of partial orders; just exactly what kind of "lattice" are you working on?)2011-09-07
  • 0
    From what I've gathered so far it is a partially ordered lattice but there is no clear statement about it being a boolean algebra or not. And I can't find anything being mentioned about order so my first guess was that I had to prove it for all possible orders or something...2011-09-07
  • 0
    You should really write down the definitions you are using fully and clearly. If you are unsure about what the words mean, it is pretty hard to actually solve the problem... It is nigh-impossible to solve a problem about lattices if, when asked "What do you mean by 'lattice'?" the answer beings "From what I've gathered..." Can you imagine trying to solve a calculus problem in which you start by saying "From what I've gathered, a derivative is..." ?2011-09-07
  • 0
    The problem is that the question was given to me as is. So even though I know that the lattice has a partial order and even though I'm a bit familiar with the lub and glb terms and even though I know what it takes for a lattice to be a boolean algebra it doesn't get me closer to the answer :/ The author of the question is out of reach at the moment and that's why I asked here. The question is missing a lot of seemingly needed information but I don't think the guy who wrote it made a mistake. I just don't know what am I supposed to answer because it is too general... (no given order etc).2011-09-07
  • 1
    Since a lattice has a partial order, **that** is the order that is given. So, let me correct you, you **are** given an order. It's whatever order the lattice comes "equipped with" by the simple virtue of *being* a lattice.2011-09-07
  • 0
    Ooh thank you! I hadn't realised that.2011-09-07

1 Answers 1

2

Assuming we are dealing with a lattice in the following sense:

Definition. A lattice is a partially ordered set $(P,\leq)$ in which any two elements $a$ and $b$ have a least upper bound, which we will denoted $a+b$, and a greatest lower bound, which we will denote by $ab$.

(Usually, one uses $\lor$, the join, for the least upper bound, and $\land$, the meet, for the greatest lower bound).

You want to show that $x(y+z)\geq xy+xz$.

Well, since $y+z\geq y$, then $x(y+z)\geq xy$: for $xy\leq x$, and $xy\leq y\leq y+z$, so $xy$ is a lower bound for $x$ and for $y+z$; thus, it is less than or equal to the greatest lower bound of $x$ and $y+z$, which is $x(y+z)$.

Symmetrically, $xz\leq x(y+z)$ since $z\leq y+z$.

Therefore, $xz$ and $xy$ are both less than or equal to $x(y+z)$. Therefore, $x(y+z)$ is an upper bound for both $xz$ and $xy$, hence the least upper bound of $xy$ and $xz$, namely $xy+xz$, is less than or equal to $x(y+z)$. That is, $$xy+xz \leq x(y+z),$$ as claimed.

Added. On the other hand, you could be working on a complemented distributive lattice, which is equivalent to a boolean algebra. In that case, you have elements $1,0\in P$ such that $1\land a = a$, $1\lor a = 1$, $0\land b = 0$ and $0\lor b=b$ for all $a$ and $b$, and such that for every $a\in P$ there exists a unique $\neg a\in P$ such that $a\lor \neg a = 1$ and $a\land \neg a = 0$. In that case, one can define a boolean algebra structure by defining $ab = a\land b$ and $a+b = (a\lor b) \land \neg(a\land b)$ (the symmetric difference). But in a Boolean ring, multiplication distributes over addition, in which case $x(y+z)$ would be equal to $xy+xz$ (as can be easily seen: $x(y+z)$ is the intersection of $x$ and the symmetric difference of $y$ and $z$: if these are sets, it consists of the things that are in $x$ and are in either $y$ and $z$ but not both; while $xy+xz$ are the things that are in either $x$ and $y$, or in $x$ and $z$, but not in all three; you can prove equality using distributivity of $\land$ over $\lor$ and viceversa and expanding the definitions). Your question would then be trivial.

  • 0
    Thanks a lot. It looks brilliant :)2011-09-07