Discrete Mathematics(II) Spring 2013 Lecture 2: Lattice(Im) 1 Introduction In this lecture, we will introduce some special lattices. And a very special structure called a Boolean algebra will be discussed in detail, which has a great many applications in computer science 2 de We have already learned ideal of a ring. A lattice is an algebraic structure which looks like a ring for both have two operations. Similarly, a lattice also has a special structure named as the same Definition 1. A subset I of a lattice L is an ideal if it is a sublattice of L and a E I and aE L imply that a∩a∈I Specially, A proper ideal I of L is prime if a,b∈ L and an b∈ I imply that a∈Iorb∈I. Specially, (0f and L itself are two trivial ideals. Let's consider the following example ad i ample 1. Given a lattice and two sublattices P and I as shown in Figure 1, where P=a, 0f Figure 1: Ideal and prime ideal According to the definition, P is a prime ideal and I is just an ideal. Why is I not prime? Since the intersection of any number of conver sublattices(ideals)is a convex sublattice(ideal) unless void, we can define the convex sublattice generated by a subset H, and the ideal generated by a subset h of the lattice L, provided that H=0. The ideal generated by a subset H will be denoted by id(H), and if H= fal, we write id(a) for id(a); we shall call id(a)a principal ideal. A commonly used notation for id(H)is(H and for id(a) it is(a We first introduce a concept. For an order P, a subset A C P is called down-set if E A and y<a imply that y∈A
Discrete Mathematics (II) Spring 2013 Lecture 2: Lattice(II) Lecturer: Yi Li 1 Introduction In this lecture, we will introduce some special lattices. And a very special structure called a Boolean algebra will be discussed in detail, which has a great many applications in computer science. 2 Ideal We have already learned ideal of a ring. A lattice is an algebraic structure which looks like a ring for both have two operations. Similarly, a lattice also has a special structure named as the same as ideal. Definition 1. A subset I of a lattice L is an ideal if it is a sublattice of L and x ∈ I and a ∈ L imply that x ∩ a ∈ I. Specially, A proper ideal I of L is prime if a, b ∈ L and a ∩ b ∈ I imply that a ∈ I or b ∈ I. Specially, {0} and L itself are two trivial ideals. Let’s consider the following example. Example 1. Given a lattice and two sublattices P and I as shown in Figure 1, where P = {a, 0} and I = {0}. 0 a b 1 I P Figure 1: Ideal and prime ideal According to the definition, P is a prime ideal and I is just an ideal. Why is I not prime? Since the intersection of any number of convex sublattices(ideals) is a convex sublattice(ideal) unless void, we can define the convex sublattice generated by a subset H, and the ideal generated by a subset H of the lattice L, provided that H = ∅. The ideal generated by a subset H will be denoted by id(H), and if H = {a}, we write id(a) for id(a); we shall call id(a) a principal ideal. A commonly used notation for id(H) is (H] and for id(a) it is (a]. We first introduce a concept. For an order P, a subset A ⊆ P is called down-set if x ∈ A and y ≤ x imply that y ∈ A. 1
Theorem 2. Let l be a lattice and let h and I be nonempty subsets of L 1. I is an ideal if and only if the following two conditions hold (a)a,b∈ I implies that a b∈I (b)I is a down-set 2.I= id(h)if and only if I={x|x≤hoU…Uhn-1 for some n≥1 and ho,…,hn-1∈H} Fora∈L id(a)={∩alx∈D} Proof. We prove the theorem one by one. 1. Let I be an ideal. Then a, bE I implies that a I, since I is a sublattice, verifying(a) Ifx≤a∈I, then ar=rna∈r,and(b) is verified. Conversely, let I satisfy(a)and(b). Let a,b E I. Then aUb E I by(a), and, since anb≤a∈I, we also have anb∈Iby(b); thus i is a sublattice.Finl,fr∈ L and a∈I, then an z≤a∈I, thus ana∈rby(b), proving that I is an ideal 2. Let Io be the set on the right side of the displayed formula in 2. Using 1, it is clear that Io is an ideal, and obviously H C lo. Finally, if H CJ and J is an ideal, then Io Cj, and thus To is the smallest ideal containing H: that is, I= lo 3. This proof is obviously simple or direct to applying 2 It is proved 3 Special Lattice Before Boolean lattice is given, we first introduce some lattice with some special properties Definition 3. A lattice L is complete if any(finite or infinite) subset A=ailie I where I is a subset of inder set of L, has a least upper bound Uierai and a greatest lower bound nierai We all know Q, rational number, is close under +,-,x,:. But when you consider a special infinite subset in which there is a sequence converging to a irrational number. The irrational number is the bound but it does not in Q. R instead of Q is complete, which is the truth we have already learned in Calculus Definition 4. A lattice L is bounded if it has a greatest element 1 and a least element o Theorem 5. Finite lattice L=(a1,.,an, is bounded Proof. Let 1= Ui=1@i and 0=n1a
Theorem 2. Let L be a lattice and let H and I be nonempty subsets of L. 1. I is an ideal if and only if the following two conditions hold: (a) a, b ∈ I implies that a ∪ b ∈ I, (b) I is a down-set. 2. I = id(H) if and only if I = {x|x ≤ h0 ∪ · · · ∪ hn−1 for some n ≥ 1 and h0, . . . , hn−1 ∈ H}. 3. For a ∈ L, id(a) = {x ∩ a|x ∈ L}. Proof. We prove the theorem one by one. 1. Let I be an ideal. Then a, b ∈ I implies that a ∪ b ∈ I, since I is a sublattice, verifying (a). If x ≤ a ∈ I, then x = x ∩ a ∈ I, and (b) is verified. Conversely, let I satisfy (a) and (b). Let a, b ∈ I. Then a ∪ b ∈ I by (a), and, since a∩b ≤ a ∈ I, we also have a∩b ∈ I by (b); thus I is a sublattice. Finally, if x ∈ L and a ∈ I, then a ∩ x ≤ a ∈ I, thus a ∩ x ∈ I by (b), proving that I is an ideal. 2. Let I0 be the set on the right side of the displayed formula in 2. Using 1, it is clear that I0 is an ideal, and obviously H ⊆ I0. Finally, if H ⊆ J and J is an ideal, then I0 ⊆ J, and thus I0 is the smallest ideal containing H; that is, I = I0. 3. This proof is obviously simple or direct to applying 2. It is proved. 3 Special Lattice Before Boolean lattice is given, we first introduce some lattice with some special properties. Definition 3. A lattice L is complete if any(finite or infinite) subset A = {ai |i ∈ I} where I is a subset of index set of L, has a least upper bound ∪i∈Iai and a greatest lower bound ∩i∈Iai. We all know Q, rational number, is close under +, −, ×, ÷. But when you consider a special infinite subset in which there is a sequence converging to a irrational number. The irrational number is the bound but it does not in Q. R instead of Q is complete, which is the truth we have already learned in Calculus. Definition 4. A lattice L is bounded if it has a greatest element 1 and a least element 0. Theorem 5. Finite lattice L = {a1, . . . , an} is bounded. Proof. Let 1 = ∪ n i=1ai and 0 = ∩ n i=1ai . 2
Definition 6. A lattice L with0 and 1 is said to be complemented if for every a EL there exist an a' such that aUa=l and ana=0 Here, a' is also called a complement of a. Sometimes, we can relax the restrictions by defining complement of b relative to a as bUb=a, bnb=0 if b, 1 is complemented for any nonempty set s It is easy to verify that LU B(Al, A2)= Al U A2 and GLB(A1, A2)= A1n A2 where U and n is the operation union and intersection respectively And we know n and U on set is complemented Example 3. Given a poset 10, a, b, c, 11, R>described in Figure 2. Figure 2: Complemented Lattice We can see that a has two complements b and c n and U on set is distributive. Similarly, we have Definition 7. A lattice L is distributive if for any a, b,cEL such that 1.a∩(bUc)=(a∩b)U(anc) 2. aU(bnc=(abn(auc If a lattice is not distributive. we call it non-distributive Example 4. is distributive for any nonempty set S Based on Example 2, we have that n and U on set is distributive. 4 Boolean algebra Historically, Boolean algebras were the first lattices to be studied. They were introduced by Boole in order to formalize the calculus of propositions. Actually, the theory of Boolean algebra is equivalent to the theory of a special class of rings
Definition 6. A lattice L with 0 and 1 is said to be complemented if for every a ∈ L there exists an a ′ such that a ∪ a ′ = 1 and a ∩ a ′ = 0. Here, a ′ is also called a complement of a. Sometimes, we can relax the restrictions by defining complement of b relative to a as b ∪ b1 = a, b ∩ b1 = 0 if b, b1 ≤ a. Example 2. is complemented for any nonempty set S. It is easy to verify that LUB(A1, A2) = A1 ∪ A2 and GLB(A1, A2) = A1 ∩ A2 where ∪ and ∩ is the operation union and intersection respectively. And we know ∩ and ∪ on set is complemented. Example 3. Given a poset described in Figure 2. a b c 1 0 Figure 2: Complemented Lattice. We can see that a has two complements b and c. ∩ and ∪ on set is distributive. Similarly, we have Definition 7. A lattice L is distributive if for any a, b, c ∈ L such that: 1. a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c). 2. a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c). If a lattice is not distributive, we call it non-distributive. Example 4. is distributive for any nonempty set S. Based on Example 2, we have that ∩ and ∪ on set is distributive. 4 Boolean Algebra Historically, Boolean algebras were the first lattices to be studied. They were introduced by Boole in order to formalize the calculus of propositions. Actually, the theory of Boolean algebra is equivalent to the theory of a special class of rings. 3
First, we just pay attention to the structure P(S), C>. It is used as an example for every property of a lattice in previous sections including ones in lecture 1. It is so special and named as Definition 8. A Boolean algebra is a lattice with0 and l that is distributive and complemented Example 5. is a Boolean algebra. Consider a special set A= a, b], its Hasse diagram is Figure 3. Figure 3: P(A), where A= (a, bl According to Example 2 and Example 4, it is a boolean algebra Example 6. is a boolean algebra First, we can verify that it is distributive and complemented. But it is tedious. In Example ?? we have proved is isomorphic to P(a, bn),c> We know the mapping keep the properties of operations n, U. So is also a Boolean Generally, we have the following theorem Theorem 9(Stone, 1936). Every finite Boolean algebra is isomorphic to the Boolean algebra of subsets of some finite set s In order to prove it, Bo sented in another form, which is out of the scope of this course. It is hard and the proof is not easy to be understood. However, the result is elegant Corollary 10. Every finite Boolean algebra has 2" elements for some n According to this Corollary, if a finite lattice has not 2"elements, it must not be a Boolean algebra Theorem 11. The complement a' of any element a of a Boolean algebra b is uniquely determined The mapping is a one-to-one mapping of B onto itself. It satisfies the conditions (aUb)=a∩b,(a∩b)=a'ub Proof. We prove the theorem one by one a' and al. We Ua!=1,a∩a′=0.aU ana1=0. So a1=a101=a1n(aUa)=(aina(aina)=alna Similarly, we can also prove a'=a1 na. And it means a'=al
First, we just pay attention to the structure . It is used as an example for every property of a lattice in previous sections including ones in lecture 1. It is so special and named as: Definition 8. A Boolean algebra is a lattice with 0 and 1 that is distributive and complemented. Example 5. is a Boolean algebra. Consider a special set A = {a, b}, its Hasse diagram is Figure 3. ∅ {a} {b} {a, b} Figure 3: P(A), where A = {a, b}. According to Example 2 and Example 4, it is a Boolean algebra. Example 6. is a Boolean algebra. First, we can verify that it is distributive and complemented. But it is tedious. In Example ??, we have proved is isomorphic to . We know the mapping keep the properties of operations ∩, ∪. So is also a Boolean algebra. Generally, we have the following theorem. Theorem 9 (Stone, 1936). Every finite Boolean algebra is isomorphic to the Boolean algebra of subsets of some finite set S. In order to prove it, Boolean algebra is to be represented in another form, which is out of the scope of this course. It is hard and the proof is not easy to be understood. However, the result is elegant. Corollary 10. Every finite Boolean algebra has 2 n elements for some n. According to this Corollary, if a finite lattice has not 2n elements, it must not be a Boolean algebra . Theorem 11. The complement a ′ of any element a of a Boolean algebra B is uniquely determined. The mapping ′ is a one-to-one mapping of B onto itself. It satisfies the conditions. (a ∪ b) ′ = a ′ ∩ b ′ , (a ∩ b) ′ = a ′ ∪ b ′ Proof. We prove the theorem one by one. 1. Suppose a has two complement a ′ and a1. We have a ∪ a ′ = 1, a ∩ a ′ = 0, a ∪ a1 = 1 and a ∩ a1 = 0. So a1 = a1 ∩ 1 = a1 ∩ (a ∪ a ′ ) = (a1 ∩ a) ∪ (a1 ∩ a ′ ) = a1 ∩ a ′ . Similarly, we can also prove a ′ = a1 ∩ a ′ . And it means a ′ = a1. 4
2. For every a E B, a is a complement of a' according to definition, so(a)=a. It means that ′ is a bijection. 3.Leta≤b,a∩b≤bnb=0.So, we have bn1=bn(aUa)=(bna)u(na)=bna, hich implies b< a. It also means 'inverts the order. Given a,b,letd=aUb, we have a,b≤ d and d≤a,b. Then we have a"≤a∩b. But for anye≤a'∩b, we have el≤a, b and a,b≤e, which imply e≤aUb=d.Soe'≤ d and it means(aUb)=(a′nb) Similarly, we can also prove(a∩b)=a∪b. It is proved The technique used in this proof is the same as the one used in the last theorem of the previous lecture 4.1 Ring and Boolean algebra Finally, we will establish a connection between a ring and a Boolean algebra. Actually a boolean algebra is equivalent to a special class of ring Given a Boolean algebra B, we first show you how to derive a ring. The point is to define two operations and. of a ring. We define them by n and U as the following 1. Addition: a+b=(anb)u(a'nb), it is also called the symmetric difference of a and b 2. Multiplication:a·b=a∩b. The remaining task is to check these two operations satisfying all laws required by a ring, which is tedious and left as an exercise. Then a boolean algebra introduces a ring. Furthermore it is a special ring with a+a=0 and aa=a Conversely, a special ring can also introduce a Boolean algebra. We first introduce a concept Definition 12. A ring is called Boolean if all of its elements are idempotent Given a Boolean ring B with an identity, we just define aUb=a+b-ab and anb= ab. It is easy to check that(B, U, n) is a Boolean algebra Then we have the following theorem Theorem 13. A Boolean algebra is equivalent to a Boolean ring with identity Exercise 1. A lattice is said to be modular if, for all a, b, c, a s c implies that aU(bnc=(aubnc (a) Show that a distributive lattice is modular
2. For every a ∈ B, a is a complement of a ′ according to definition, so (a ′ ) ′ = a. It means that ′ is a bijection. 3. Let a ≤ b, a ∩ b ′ ≤ b ∩ b ′ = 0. So, we have b ′ ∩ 1 = b ′ ∩ (a ∪ a ′ ) = (b ′ ∩ a) ∪ (b ′ ∩ a ′ ) = b ′ ∩ a ′ , which implies b ′ ≤ a ′ . It also means ′ inverts the order. Given a, b, let d = a ∪ b, we have a, b ≤ d and d ′ ≤ a ′ , b′ . Then we have d ′ ≤ a ′ ∩ b ′ . But for any e ′ ≤ a ′ ∩ b ′ , we have e ′ ≤ a ′ , b′ and a, b ≤ e, which imply e ≤ a ∪ b = d. So e ′ ≤ d ′ and it means (a ∪ b) ′ = (a ′ ∩ b ′ ). Similarly, we can also prove (a ∩ b) ′ = a ′ ∪ b ′ . It is proved. The technique used in this proof is the same as the one used in the last theorem of the previous lecture. 4.1 Ring and Boolean Algebra Finally, we will establish a connection between a ring and a Boolean algebra. Actually a Boolean algebra is equivalent to a special class of ring. Given a Boolean algebra B, we first show you how to derive a ring. The point is to define two operations + and · of a ring. We define them by ∩ and ∪ as the following: 1. Addition: a + b = (a ∩ b ′ ) ∪ (a ′ ∩ b), it is also called the symmetric difference of a and b. 2. Multiplication: a · b = a ∩ b. The remaining task is to check these two operations satisfying all laws required by a ring, which is tedious and left as an exercise. Then a Boolean algebra introduces a ring. Furthermore, it is a special ring with a + a = 0 and a · a = a. Conversely, a special ring can also introduce a Boolean algebra. We first introduce a concept. Definition 12. A ring is called Boolean if all of its elements are idempotent. Given a Boolean ring B with an identity, we just define a ∪ b = a + b − ab and a ∩ b = ab. It is easy to check that ⟨B, ∪, ∩⟩ is a Boolean algebra. Then we have the following theorem. Theorem 13. A Boolean algebra is equivalent to a Boolean ring with identity. Exercise 1. A lattice is said to be modular if, for all a, b, c, a ≤ c implies that a ∪ (b ∩ c) = (a ∪ b) ∩ c. (a) Show that a distributive lattice is modular. 5
Figure 4: Lattice b)Show that the lattice in shown in the Figure 4 is a nondistributive lattice that is modular 2. how that any complete lattice has a0 and a 1 3. Prove that a partially ordered set with 1 in which every nonempty set has a g.1.b. is a complete lattice 4. In a bounded distributive lattice, an element can have only one complement 5. Show that in a Boolean algebra the following statements are equivalent for any a and b (a)a∪b=b (b)a∩b=a (c)aUb=l (d)a∩b=0 (e)a≤b 6. Let A=a,b,c, d, e, f, g, h) and R be the relation defined by 1110000 01010000 00110000 00010000 M 01010101 00110011 (a) Show that the poset(A, R)is complemented and give all pairs of complements (b)Prove or disprove that(A, R)is a Boolean algebra 7. Prove Theorem 1
a b c 1 0 Figure 4: Lattice (b) Show that the lattice in shown in the Figure 4 is a nondistributive lattice that is modular. 2. Show that any complete lattice has a 0 and a 1. 3. Prove that a partially ordered set with 1 in which every nonempty set has a g.l.b. is a complete lattice. 4. In a bounded distributive lattice, an element can have only one complement. 5. Show that in a Boolean algebra the following statements are equivalent for any a and b. (a) a ∪ b = b (b) a ∩ b = a (c) a ′ ∪ b = 1 (d) a ∩ b ′ = 0 (e) a ≤ b 6. Let A = {a, b, c, d, e, f, g, h} and R be the relation defined by MR = 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 (a) Show that the poset (A, R) is complemented and give all pairs of complements. (b) Prove or disprove that (A, R) is a Boolean algebra. 7. Prove Theorem 13. 6