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.

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

share|improve this question
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? –  Arturo Magidin Sep 7 '11 at 16:06
    
Well, I suppose it has to work for any given order... Also ∧ and ∨ work like * and + . –  Eternal_Light Sep 7 '11 at 16:45
    
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). –  Arturo Magidin Sep 7 '11 at 16:46
    
oh! It is a grid after all! Sorry I get lost in translation so easily. –  Eternal_Light Sep 7 '11 at 16:50
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. –  Arturo Magidin Sep 7 '11 at 17:21

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks a lot. It looks brilliant :) –  Eternal_Light Sep 7 '11 at 17:24

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.