Class Note for MATH 796 at KU 3
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Class Note for MATH 796 at KU 3
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Monday 12808 Birkhoff s Theorem De nition A lattice L is distributive if the following two equivalent conditions hold acyzxyxz Vacy2EL xVyzxVyxz Vacy2ELi Recall that an order ideal of P is a set I Q P such that if ac E I and y 3 ac then y E It The poset JP of all order ideals of P ordered by containment is a distributive latticei It is a sublattice of the Boolean algebra Q7 where n lPl and is itself ranked of rank n iiei n because it is possible to build a chain of order ideals by adding one element at a time abcd abs and b d N as ed a c a c if P JP De nition The ideal generated by 951 an is x1uix 7 yELlnyl for someii So eg a d a c cl in the lattice abovei De nition Let L be a lattice An element x E L is joinirreducible if it cannot be written as the join of two other elements That is if ac y 2 then either ac y or ac 2 The subposet not sublatticel of L consisting of all joinirreducible elements is denoted lrrLi Provided that L has no in nite descending chains every element of L can be written as the join of join irreducibles but not necessarily uniquely eigi M5 All atoms are joinirreducible but not all joinirreducible elements need be atomsi An extreme and slightly trivial example is a chain every element is joinirreducible but there is only one atomi As a less trivial example in the lattice below a b c cl are all joinirreducible although the only atoms are a and cl L rrL Theorem 1 Birkhoff 1933 Fundamental Theorem of Finite Distributive Lattices FTFDL Up to isomorphism the nite distributive lattices are exactly the lattices JP where P is a nite poset Moreover L E JlrrL for every lattice L and P E lrrJP for every poset P Lemma 2 Let L be a distributive lattice and let p E L be joinirreducible Suppose that p 3 a1 an Then p 3 al for some i Proof By distributivity we have ppa1Va pa1pan and since p is joinirreducible it must equal p al for some i whence p 3 a D Analogue If a prime p divides a product of positive numbers then it divides at least one of them This is in fact exactly what Lemma 2 says when applied to the divisor lattice D7 Proposition 3 Let L be a distributive lattice Then every ac E L can be written uniquely as an irredundant join ofjoinirreducible elements Proof We have observed above that any element in a nite lattice can be written as an irredundant join of joinirreducibles so we have only to prove uniqueness So suppose that we have two irredundant decompo sitions 1 xp1VVpnq1Vqu with p qj E lrrL for all ij By Lemma 1 pl 3 qj for some j Again by Lemma 1 qj S p for some i lfi y 1 then pl 3 p which contradicts the fact that the p form an antichain Therefore p1 qj Replacing p1 with any joinirreducible appearing in 1 and repeating this argument we nd that the two decompositions must be identical D Sketch of proof of Birkho us Theorem The lattice isomorphism L A JlrrL is given by 4 06 P l P E ML 10 S 96 Meanwhile the joinirreducible order ideals in P are just the principal order ideals ie those generated by a single element So the poset isomorphism P A lrrJP is given by My ltygt These facts need to be checked as a homework problem Corollary 4 Every distributive lattice is isomorphic to a sublattice of a Boolean algebra whose atoms are the joinirreducibles in L Corollary 5 Let L be a nite distributive lattice TFAE 1 L is a Boolean algebra 2 lrrL is an antichain 3 L is atomic e every element in L is the join of atoms 4 Every joinirreducible element is an atom 5 L is complemented That is for each ac E L there exists y E L such that ac y 1 and ac y 6 L is relatively complemented That is whenever ac S y S 2 in L there exists u E L such that qu2 andyuac Proof 6 gt 5 Trivial 5 gt 4 Suppose that L is complemented and suppose that 2 E L is a joinirreducible that is not an atom Let ac be an atom in 0 z and let y be the complement of ac Then ach21zz aczyzacyz by distributivity Since 2 is joinirreducible we must have y 2 z ie y 2 2 But then y gt ac and y ac ac y O a contradiction 4 ltgt 3 Trivial 4 gt 2 Atoms are Clearly incomparable 2 gt 1 By FTFDL since L JlrrLi 1 gt 61fXQYQZaresetsthenletUXUYZi ThenY UXandYUUZi D 0 We could dualize all of this shoW that every element in a distributive lattice can be expressed uniquely as the meet of meetirreducible elements This might be a roundabout way to shoW that distributiVity is a selfdual conditioni
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'