×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

15

0

3

# Class Note for MATH 796 at KU 3

Marketplace > Kansas > Class Note for MATH 796 at KU 3

No professor available

These notes were just uploaded, and will be ready to view shortly.

Either way, we'll remind you when they're ready :)

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

COURSE
PROF.
No professor available
TYPE
Class Notes
PAGES
3
WORDS
KARMA
25 ?

## 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

×

×

### What is Karma?

#### 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

×

×

### BOOM! Enjoy Your Free Notes!

×

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'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com