Discrete Mathematics(II) Spring 2012 Lecture 1: Lattice(I) Lecturer. yil 1 Introduction In the first half of the nineteenth century, George Boole's attempt to formalize propositional logic led to the concept of boolean algebras. While investigating the axiomatics of boolean algebras at the end of the nineteenth century, Charles S. Pierce and Ernst Schroder, both provided many Richard Dedekind's research on ideals of algebraic numbers also led to the same discover dently contributions to mathematical logic, found it useful to introduce the lattice concept. Indepe Although some of the early results of these mathematicians are very elegant and far from trivial they did not attract the attention of the mathematical community. It was the work of Garrett Birkhoff in the mid-1930s that kicked off the general development of lattice theory. In a brilliant series of papers, he demonstrated the importance of lattice theory and showed that it provides a unifying framework for hitherto unrelated developments in many mathematical disciplines. Birkhoff attempted to sell it to the general mathematical community, which he did with astonishing success in the first edition of his monograph Lattice Theory The explosive growth of this field continued. While the 1960s provided under 1, 500 papers and books, the seventies up to 2, 700, the eighties over 3, 200, the nineties almost 3, 600, and the first decade of this century about 4,000 There are numerous topics covered by lattice theory. Several monographs are on lattice theory include Birkhoff's classic. In our course, we only introduce some elementary concepts and results of this theory. Traditionally, lattice theory should be taught under the category of abstract algebra However, it can be explored from two different points of view. First, a Lattice is just a partial order with two special operations, which will be discussed latter in detail. Second, it can also be defined in algebra approach 2 Review of partial Order set In order to show a lattice from the orders perspective, we first simply review the partial order and some concepts associated with it, such as bound and extreme elements Definition 1. Given a set A and a relation R on it, A, R> is called a partially ordered set(poset in brief if r is reflexive, antisymmetric and transitive Once a order is defined, elements in the set could be compared between each other to distinguish the bigger or the smaller one. So it is intuitive to define some general terms such as extreme element as the followin Definition 2. Given a poset A, <> we have
Discrete Mathematics (II) Spring 2012 Lecture 1: Lattice(I) Lecturer: Yi Li 1 Introduction In the first half of the nineteenth century, George Boole’s attempt to formalize propositional logic led to the concept of boolean algebras. While investigating the axiomatics of boolean algebras at the end of the nineteenth century, Charles S. Pierce and Ernst Schr¨oder, both provided many contributions to mathematical logic, found it useful to introduce the lattice concept. Independently, Richard Dedekind’s research on ideals of algebraic numbers also led to the same discovery. Although some of the early results of these mathematicians are very elegant and far from trivial, they did not attract the attention of the mathematical community. It was the work of Garrett Birkhoff in the mid-1930s that kicked off the general development of lattice theory. In a brilliant series of papers, he demonstrated the importance of lattice theory and showed that it provides a unifying framework for hitherto unrelated developments in many mathematical disciplines. Birkhoff attempted to sell it to the general mathematical community, which he did with astonishing success in the first edition of his monograph Lattice Theory. The explosive growth of this field continued. While the 1960s provided under 1,500 papers and books, the seventies up to 2,700, the eighties over 3,200, the nineties almost 3,600, and the first decade of this century about 4,000. There are numerous topics covered by lattice theory. Several monographs are on lattice theory include Birkhoff’s classic. In our course, we only introduce some elementary concepts and results of this theory. Traditionally, lattice theory should be taught under the category of abstract algebra. However, it can be explored from two different points of view. First, a Lattice is just a partial order with two special operations, which will be discussed latter in detail. Second, it can also be defined in algebra approach. 2 Review of Partial Order Set In order to show a lattice from the order’s perspective, we first simply review the partial order and some concepts associated with it, such as bound and extreme elements. Definition 1. Given a set A and a relation R on it, is called a partially ordered set( poset in brief ) if R is reflexive, antisymmetric and transitive. Once a order is defined, elements in the set could be compared between each other to distinguish the bigger or the smaller one. So it is intuitive to define some general terms such as extreme element as the following. Definition 2. Given a poset , we have: 1
1. a is maximal if there does not exist b E A such that a< b 2. a is minimal if there does not exist b E A such that b< a 3. a is greatest if for every b∈A, we have b≤a 4. a is least if for every b∈A, we have a≤b When we consider a subset of a poset A. a bound of it could be found, which is a element in A Definition 3. Given a poset A. < and a set ScA 1.a∈ A is a upper bound of s if s≤ u for every s∈S. 2.l∈ A is a lower bound of s if l≤ s for every s∈S You can observe that there sometimes exist more than one upper/lower bound of a given subset We are specially interested in some special one, such as the least or the greatest. So the following concepts are derived Definition 4. Given a poset A, < and a set SCA 1. u is a least upper bound of S,(LUB(), if u is the upper bound of s and u s u' for any other upper bound uof s 2. I is a greatest lower bound of S,(GLB(S)), if l is the upper bound of s and l'< I for any other lower bound l of s Example 1. Given two poset described in Figure 1 Figure 1: Extreme element of poset They can demonstrate concepts mentioned before Theorem 5. A subset of a poset has at most one LUB Or gLB The proof is left as an exercise
1. a is maximal if there does not exist b ∈ A such that a ≤ b. 2. a is minimal if there does not exist b ∈ A such that b ≤ a. 3. a is greatest if for every b ∈ A, we have b ≤ a. 4. a is least if for every b ∈ A, we have a ≤ b. When we consider a subset of a poset A. A bound of it could be found, which is a element in A. Definition 3. Given a poset and a set S ⊆ A. 1. u ∈ A is a upper bound of S if s ≤ u for every s ∈ S. 2. l ∈ A is a lower bound of S if l ≤ s for every s ∈ S. You can observe that there sometimes exist more than one upper/lower bound of a given subset. We are specially interested in some special one, such as the least or the greatest. So the following concepts are derived. Definition 4. Given a poset and a set S ⊆ A. 1. u is a least upper bound of S, (LUB(S)), if u is the upper bound of S and u ≤ u 0 for any other upper bound u 0 of S. 2. l is a greatest lower bound of S, (GLB(S)), if l is the upper bound of S and l 0 ≤ l for any other lower bound l 0 of S. Example 1. Given two poset described in Figure 1. a0 a1 a2 a3 a4 a b c 1 0 Figure 1: Extreme element of poset They can demonstrate concepts mentioned before. Theorem 5. A subset of a poset has at most one LUB or GLB. The proof is left as an exercise. 2
3 Lattice In this section, we will illustrate lattice in two approaches. One is to define it on the base of a partial order. And another is to define it in traditionally algebraic style 3.1 Orders Perspective Definition 6. A lattice (structure) is a poset (A, s) in which any two elements a, b have a LUB(a, b)and a GLB(a, b) From now on, we define a Ub=LU B(a, b) and anb=GLB(a, b) in brief. We also call them join and meet respectively. With the following example, we show you why the notations are taken. Example 2.(P(A), S), with two operations U(union) and n(intersection), is a lattice The verification is simple. You just follow the definition of lattice There are several means to represent lattice. For lattice is generally a partial order, it can be described by Hasse diagram. Another way is to use table, for a lattice is also determined by two Example 3.(P(a, b), S), with two operations U(defined as union) and n(defined as intersection) It is a lattice according to previous Example 2. It can be described by a Hasse diagram as shown Figure 2 {a,b} b} Figure 2: Hasse diagram of (P(a, b9),s) It can aslo be described by joint and meet table as shown in the following Table 1. Obviously, 0{a}{b}{a,b} falfa fa fa, b] fa, bj {a}0{a}0 {b}{b}{a,b}{b}{a,b} {b}00{b}{b} {a,b}|{a,b}{a,b}{a,b}{a,b {a,b}0{a}{b}{a,b} (a)Joint table (b) Meet table Table 1:(P(a, b9),S) joint/meet table is symmetric. Sometimes, they could be merged into a table by taken upper/lower
3 Lattice In this section, we will illustrate lattice in two approaches. One is to define it on the base of a partial order. And another is to define it in traditionally algebraic style. 3.1 Order’s Perspective Definition 6. A lattice (structure) is a poset hA, ≤i in which any two elements a, b have a LUB(a, b) and a GLB(a, b). From now on, we define a ∪ b = LUB(a, b) and a ∩ b = GLB(a, b) in brief. We also call them join and meet respectively. With the following example, we show you why the notations are taken. Example 2. hP(A), ⊆i, with two operations ∪(union) and ∩(intersection), is a lattice. The verification is simple. You just follow the definition of lattice. There are several means to represent lattice. For lattice is generally a partial order, it can be described by Hasse diagram. Another way is to use table, for a lattice is also determined by two operations. Example 3. hP(a, b), ⊆i, with two operations ∪(defined as union) and ∩(defined as intersection). It is a lattice according to previous Example 2. It can be described by a Hasse diagram as shown in Figure 2. ∅ {a} {b} {a, b} Figure 2: Hasse diagram of hP({a, b}), ⊆i It can aslo be described by joint and meet table as shown in the following Table 1. Obviously, ∪ ∅ {a} {b} {a, b} ∅ ∅ {a} {b} {a, b} {a} {a} {a} {a, b} {a, b} {b} {b} {a, b} {b} {a, b} {a, b} {a, b} {a, b} {a, b} {a, b} (a) Joint table ∩ ∅ {a} {b} {a, b} ∅ ∅ ∅ ∅ ∅ {a} ∅ {a} ∅ {a} {b} ∅ ∅ {b} {b} {a, b} ∅ {a} {b} {a, b} (b) Meet table Table 1: hP({a, b}), ⊆i in table joint/meet table is symmetric. Sometimes, they could be merged into a table by taken upper/lower 3
triangle matrix respectively. For operation U(union) and n(intersection), there are many properties, uch as commutative law, associative law, idempotent law, and eve distributive law etc In previous example, we have found many properties. However, a lattice generally have the following common properties Proposition 7. The Lattice with operation n and U satisfies 1. Commutative:anb=b∩a,aUb=b∪a. 2. Associative:(anbnc=an(bnc),(aUbUc=aU(bUc) 3. Idempotent: ana=a, aUa=a 4. Absorption:(aUb)na=a,(anhua=a Proof. The proof is directly deduced from definition, which is left as an exercise 3.2 Algebraic Perspective In abstract algebra, we first learn semigroup. Then more and more complicated structure are introduced by adding more constraints. Similarly, We also introduce semilattice here. Definition 8. A semilattice is an algebra S=(S, *)satisfying, for all a, y, z ES, 2.x*y=y* 9.x*(y*2)=(x*y)* Example 4. Given a set A. Consider the partially ordered set((A), S). Then(P(A),U semilattice For this case, it is easy to verify that all three properties are satisfied Based on semilattice, we can furthermore define lattice by defining two operations n and U on some set as following Definition 9. Given a structure L=(L, n, U), it is a lattice if it subjects to 1.(L,n) and(L, n)are two semilattices 2.(aUb)na=a,(anhUa=a This is a typical style of defining a structure in algebra. In another word, Lattice is just a structure with two operations n and U on some set which meets 4 properties mentioned previously in Proposition 7. Therefore, we have the following theorem to guarantee the equivalence of two different definitions
triangle matrix respectively. For operation ∪(union) and ∩(intersection), there are many properties, such as commutative law, associative law,idempotent law, and eve distributive law etc.. In previous example, we have found many properties. However, a lattice generally have the following common properties. Proposition 7. The Lattice with operation ∩ and ∪ satisfies: 1. Commutative: a ∩ b = b ∩ a, a ∪ b = b ∪ a. 2. Associative: (a ∩ b) ∩ c = a ∩ (b ∩ c),(a ∪ b) ∪ c = a ∪ (b ∪ c). 3. Idempotent: a ∩ a = a, a ∪ a = a. 4. Absorption: (a ∪ b) ∩ a = a,(a ∩ b) ∪ a = a. Proof. The proof is directly deduced from definition, which is left as an exercise. 3.2 Algebraic Perspective In abstract algebra, we first learn semigroup. Then more and more complicated structure are introduced by adding more constraints. Similarly, We also introduce semilattice here. Definition 8. A semilattice is an algebra S = (S, ∗) satisfying, for all x, y, z ∈ S, 1. x ∗ x = x, 2. x ∗ y = y ∗ x, 3. x ∗ (y ∗ z) = (x ∗ y) ∗ z. Example 4. Given a set A. Consider the partially ordered set hP(A), ⊆i. Then hP(A), ∪i is a semilattice. For this case, it is easy to verify that all three properties are satisfied. Based on semilattice, we can furthermore define lattice by defining two operations ∩ and ∪ on some set as following: Definition 9. Given a structure L = (L, ∩, ∪), it is a lattice if it subjects to: 1. (L, ∩) and (L, ∩) are two semilattices. 2. (a ∪ b) ∩ a = a,(a ∩ b) ∪ a = a. This is a typical style of defining a structure in algebra. In another word, Lattice is just a structure with two operations ∩ and ∪ on some set which meets 4 properties mentioned previously in Proposition 7. Therefore, we have the following theorem to guarantee the equivalence of two different definitions. 4
Theorem 10. IfL is any set in which there are two operation defined as U and n satisfying the last four properties, then L is a lattice Proof. We first show that L has the following two properties: a∪b= a and a∩b= b are equivalent. if aUb=a, we get anb=(a∪b)∩b= b by absorption 2.<S, < is a poset if b a is defined by anb=b or aUb=a (i)aUa= a imply a≤ i) Suppose a≤ b and b≤a, we have a=aUb=bUa=b. (irfa≤b,b≤c, then au b=b,bUc=c. Hence, aUc=aU(buc=(aubuc=bUc=c We now prove that aUb is the LUB. Since(aUbna=a,asaUb. Similarly b< aUb. Now given any c such that a, b< c, we have aUc=c and bUc=c. Hence b)Uc=aU(bUc ∪c=c and aU b≤c. Similarly, we can prove that a n b is the glB. Totally, L is a lattice with U and n 4 Sublattice Similar to group given some subset, we have the following concep Definition 11. A subset s of a lattice L is called sublattice if it is closed under the operation U and∩ Example 5. Given two posets described in Figure 3 (a) Lattice (b)Sublattice igure 3: Sublattice of (20, 10, 5, 4, 2, 11, It obvious that lattice in Figure 3b is a sublattice of lattice in Figure 3a For sublattice is define relatively. Dually, we can also define a concept ertension as followin
Theorem 10. If L is any set in which there are two operation defined as ∪ and ∩ satisfying the last four properties, then L is a lattice. Proof. We first show that L has the following two properties: 1. a ∪ b = a and a ∩ b = b are equivalent. if a ∪ b = a, we get a ∩ b = (a ∪ b) ∩ b = b by absorption. 2. is a poset if b ≤ a is defined by a ∩ b = b or a ∪ b = a. (i) a ∪ a = a imply a ≤ a. (ii) Suppose a ≤ b and b ≤ a, we have a = a ∪ b = b ∪ a = b. (iii) If a ≤ b, b ≤ c, then a ∪ b = b, b ∪ c = c. Hence, a ∪ c = a ∪ (b ∪ c) = (a ∪ b) ∪ c = b ∪ c = c We now prove that a∪b is the LUB. Since (a∪b)∩a = a, a ≤ a∪b. Similarly b ≤ a∪b. Now given any c such that a, b ≤ c, we have a ∪ c = c and b ∪ c = c. Hence (a ∪ b) ∪ c = a ∪ (b ∪ c) = a ∪ c = c and a ∪ b ≤ c. Similarly, we can prove that a ∩ b is the GLB. Totally, L is a lattice with ∪ and ∩. 4 Sublattice Similar to group, given some subset, we have the following concept. Definition 11. A subset S of a lattice L is called sublattice if it is closed under the operation ∪ and ∩. Example 5. Given two posets described in Figure 3 1 2 5 4 10 20 (a) Lattice 1 2 5 10 (b) Sublattice Figure 3: Sublattice of h{20, 10, 5, 4, 2, 1}, |i It obvious that lattice in Figure 3b is a sublattice of lattice in Figure 3a For sublattice is define relatively. Dually, we can also define a concept extension as following: 5
Definition 12. If s is a sublattice of L, L is an extension of s In some case, we have the following special sublattice Definition13. The subset s of the lattice l is called convex纩fa,b∈S,c∈L,anda≤c≤b imply that c∈S Given two lattices, they sometimes have the same topology structure by means of Hasse diagram. Consider the following example Example 6. Given a poset ((1, 2, 3, 6],), it is isomorphic to(P(a,b1),9) They have the Hasse diagrams as shown in Figure 4. It is easy to construct a bijection between b} (a) (b) Figure 4: Finite Boolean algebra example 1, 2, 3, 6) and P(a, b). And the mapping is not unique Lattice is a specail type of a partial order. Generally, we have the assertion Theorem 14. Given two lattice L and L, a bijection f: L,L froml to L is an isomorphism f and only if a≤ b in L implies f(a)≤f(b)in. Proof. If f is isomorphic, f is order preserving. Suppose a b, we have a Ub=b. Then we have ∫(a∪b)=f(a)∪f(b)=f(b), which means f(a)≤f(b). Conversely,f(a)≤f(b) also implies a≤b because f is also a bijection Suppose f is an order preserving bijection, f is isomorphic. Given a, bE L, let d= aUb, we have f(a)Uf(b)≤∫(d) because a,b≤ d leads f(a),f(b)≤f(d). For any f(e)=e∈ L such that f(a),f(b)≤e', we have a,b≤e. So aub=d≤e. Then we have f(d)≤f(e)=e, which means f(aUb)=f(a)∫(b). Similarly, we can prove f(an∩b)=f(a)∩f(b) Exercies 1. Let A be the set of finitely generated subgroups of a group G, ordered by set inclusion. Prove that(A, S) is a join-semilattice, but not necessarily a lattice 2. Show that every chain is a lattice 3. Prove that the absorption identities imply the idempotency of U and n
Definition 12. If S is a sublattice of L, L is an extension of S. In some case, we have the following special sublattice. Definition 13. The subset S of the lattice L is called convex if a, b ∈ S, c ∈ L, and a ≤ c ≤ b imply that c ∈ S. Given two lattices, they sometimes have the same topology structure by means of Hasse diagram. Consider the following example. Example 6. Given a poset h{1, 2, 3, 6}, |i, it is isomorphic to hP({a, b}), ⊆i. They have the Hasse diagrams as shown in Figure 4. It is easy to construct a bijection between 1 2 3 6 (a) ∅ {a} {b} {a, b} (b) Figure 4: Finite Boolean algebra example {1, 2, 3, 6} and P({a, b}). And the mapping is not unique. Lattice is a specail type of a partial order. Generally, we have the assertion. Theorem 14. Given two lattice L and L 0 , a bijection f : L → L 0 from L to L 0 is an isomorphism if and only if a ≤ b in L implies f(a) ≤ f(b) in L 0 . Proof. If f is isomorphic, f is order preserving. Suppose a ≤ b, we have a ∪ b = b. Then we have f(a∪b) = f(a)∪f(b) = f(b), which means f(a) ≤ f(b). Conversely, f(a) ≤ f(b) also implies a ≤ b because f −1 is also a bijection. Suppose f is an order preserving bijection, f is isomorphic. Given a, b ∈ L, let d = a ∪ b, we have f(a) ∪ f(b) ≤ f(d) because a, b ≤ d leads f(a), f(b) ≤ f(d). For any f(e) = e 0 ∈ L 0 such that f(a), f(b) ≤ e 0 , we have a, b ≤ e. So a ∪ b = d ≤ e. Then we have f(d) ≤ f(e) = e 0 , which means f(a ∪ b) = f(a) ∪ f(b). Similarly, we can prove f(a ∩ b) = f(a) ∩ f(b). Exercies 1. Let A be the set of finitely generated subgroups of a group G, ordered by set inclusion. Prove that hA, ⊆i is a join-semilattice, but not necessarily a lattice. 2. Show that every chain is a lattice. 3. Prove that the absorption identities imply the idempotency of ∪ and ∩. 6
4. Show that a lattice L is a chain iff every nonempty subset of L is a sublattice. 5. Let L=P(S) be the lattice of all subsets of a set S under the relation of containment. Let T be a subset of S. Show that P(T)is a sublattice of L 6. Let L be a lattice and let a and b be element of L such that a s b. The interval a, b is defined as the set of all a E L such that a< a s b. Prove that [a, b] is a sublattice of L 7. Describe a practical method of checking associativity in a join-table and in a meet-table
4. Show that a lattice L is a chain iff every nonempty subset of L is a sublattice. 5. Let L = P(S) be the lattice of all subsets of a set S under the relation of containment. Let T be a subset of S. Show that P(T) is a sublattice of L. 6. Let L be a lattice and let a and b be element of L such that a ≤ b. The interval [a, b] is defined as the set of all x ∈ L such that a ≤ x ≤ b. Prove that [a, b] is a sublattice of L. 7. Describe a practical method of checking associativity in a join-table and in a meet-table. 7