Re: Lattices--the distributive inequality
From: William Elliot (marsh_at_privacy.net)
Date: 06/30/04
- Next message: Van Jacques: "Re: Lattices--the distributive inequality"
- Previous message: William Elliot: "Re: 2 rings with a special property"
- In reply to: Van Jacques: "Lattices--the distributive inequality"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 30 Jun 2004 01:25:42 -0700
From: Van Jacques <calccurve-test23@yahoo.com>
Newsgroups: sci.math
Subject: Lattices--the distributive inequality
>Consider lattices L as posets with meet(a,b) == a /\ b == glb(a,b),
>and join(a,b) == a \/ b == lub(a,b), for any a,b in L.
>L.E. means "less than or equal to".
>(*) Prove that (a /\ b) \/ (a /\ c) L.E. a /\ (b \/ c)
the same in simpler Boolean algebra like notation
ab + ac <= a(b + c)
which I use unless notational conflict arises.
>With an equal sign, this is the distibutive law for distributive
>lattices.
Both
a(b + c) = ab + ac
and
a + bc = (a + b)(a + c)
is the distributive law for lattices
>We also have the dual to (*), obtained by interchanging /\ with \/,
>and changing L.E. to G.E.
a + bc <= (a + b)(a + c)
>Here are some examples of lattices:
>1) the power set 2^X == P(X) of X ordered by set-theoretic
>inclusion, including Boolean algebras.
>2) the integers Z with L.E. the usual order,
Exercise: show any linear or total order is distributive
lattice by glb = min, lub = max
>3) the positive integers ordered by divisibility, or dual to this
>4) the ideals of Z ordered by set-theoretic inclusion,
>5) the subgroups of a groups ordered by set-theoretic inclusion
>6) the intermediate fields of a extension E of a field F, again
> ordered by set-theoretic inclusion.
>I think all of these are distibutive, though
>though I haven't checked it except for P(X).
Check the subgroups of Z_2 x Z_2
{ (0,0) }
{ (0,0), (1,0) }
{ (0,0), (0,1) }
{ (0,0), (1,1) }
{ (0,0), (0,1), (1,0), (1,1) }
cf, second diagram example below
Also the lattice of topologies for a set with more than three points isn't
distributive.
>Also, a L.E. b <==> a \/ b = b <==> a /\ b = a
>follows from the definitions.
Yes, yet it depends upon how you define a lattice.
Tho ultimately do not all theorems follow from the definitions?
You can define a lattice simply from the order and the
requirement that lub x,y and glb x,y exist for all x,y.
Or you can define a lattice axiomatically
(S,*,+) is lattice when SS, S+S subset S,
x(yz) = (xy)z, xy = yx
x+(y+z) = (x+y)+z, x+y = y+x,
ie S is closed under associative and commutative operators * and +
with the added axiom, the order axiom
a+ab = a = a(a+b)
Then you define a <= b as a = ab and show
<= is an order and that
ab = glb a,b; a + b = lub a,b
Prior to doing that you'll want to show
aa = a = a+a; a = ab iff a + b = b
Just for fun, here's an extra for you
ab = a + b ==> a = b
Conversely from the order <= and the existence of glb a,b and lub a,b and
by notating ab = a*b = glb a,b and a+b = lub a,b, derive all the axioms
for a lattice.
>I thought perhaps this could be used to show that
>(*) is true, but I still don't see it.
b,c <= b + c; ab, ac <= a(b +c); ab + ac <= a(b + c)
I leave for you to show
a + bc <= (a + b)(a + c)
>I see that the distributive law is true, but I
No! Not all lattices are distributive, for (monospace!) example
1 1
/ \ /|\
u \ u v w
| w \|/
v / 0
\ /
0
>don't see how to prove the above inequality (*).
In a distributive lattice the inequality is trivial.
A classic reference is Davey, B. A.,
Introduction to Lattices and Order
----
- Next message: Van Jacques: "Re: Lattices--the distributive inequality"
- Previous message: William Elliot: "Re: 2 rings with a special property"
- In reply to: Van Jacques: "Lattices--the distributive inequality"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
