2.6. ALGEBRAS OF SETS Theorem 82 Given any collection C of subsets of x, there is a smallest algebra A which contains C Proof.(Sketch) It is sufficient to show there is an algebra A containing C such that if B is any algebra containing C, then BDA. Let f be the family of all algebras that contain C(which is nonempty since P(X)E F) LetA=∩{B:B∈升}. Then C is a subcollection of A since each B in F contains C. All that remains to be shown is that A is an algebra (i.e. if A and B are in A, then AU B and A are in n(B: BE F). It follows from the definition of A that BD A. See Figure 2.6.1 Exercise 2.6.1 Finish the proof of Theorem 82. If A and B are in A, then for each B∈J, we have a∈ B and B∈B. Since b is an algebra,AUB ∈B. Since this is true for every B∈F, we have AU B∈∩{BB∈F Similarly,vfA∈A, then a°∈A We say that the smallest algebra containing C is called the algebra gen erated by C. By construction, the smallest algebra is unique. Notice the proof makes clear that the intersection of any collection of algebras is itself an algebra Example 83 Let X=a, b,c. The following three collections are algebras C1=0, X), C2=0,a, b, c, X, C3= P(X). The following two collec- tions are not algebras: C4=0, a, X) since, for instance, a=b, c E C4 and Cs= 0, a, b, b, c), X) since 0= fa, c Cs. However, the smallest algebra which contains CA is just C2. To see this, we can apply the argument in Theorem 82. Let F=[C2, P(X)) be the family of all algebras that contain Ca. But A=C2nP(X)=C2 Exercise 2.6.2 Let X=N. Show that the collection A=Ai: Ai is finite or N\Ai is finite is an algebra on n and that it is a proper subset of P(N) The next theorem proves that it is always possible to construct a ne collection of disjoint sets from an existing algebra with the property that its union is equivalent to the union of subsets in the existing algebra. This will become very useful when we begin to think about probability measures Theorem 84 Let A be an algebra comprised of subsets A: iE A].Then there is a collection of subsets Bi: iE A in A such that B, Bm=0 for n≠ m and IeA B2=Ui∈AA 1i Note that the index set a can be countably or even uncountably infinite
2.6. ALGEBRAS OF SETS 39 Theorem 82 Given any collection C of subsets of X, there is a smallest algebra A which contains C. Proof. (Sketch) It is sufficient to show there is an algebra A containing C such that if B is any algebra containing C, then B ⊃ A. Let F be the family of all algebras that contain C (which is nonempty since P(X) ∈ F). Let A = ∩{B : B ∈ F}. Then C is a subcollection of A since each B in F contains C. All that remains to be shown is that A is an algebra (i.e. if A and B are in A, then A ∪ B and Ac are in ∩{B : B ∈ F}). It follows from the definition of A that B ⊃ A. See Figure 2.6.1 Exercise 2.6.1 Finish the proof of Theorem 82 .If A and B are in A, then for each B ∈ F, we have A ∈ B and B ∈ B. Since B is an algebra, A ∪ B ∈ B. Since this is true for every B ∈ F, we have A ∪ B ∈ ∩{B|B ∈ F}. Similarly, if A ∈ A, then Ac ∈ A. We say that the smallest algebra containing C is called the algebra generated by C. By construction, the smallest algebra is unique. Notice the proof makes clear that the intersection of any collection of algebras is itself an algebra. Example 83 Let X = {a, b, c}. The following three collections are algebras: C1 = {∅, X}, C2 = {∅, {a}, {b, c}, X}, C3 = P(X). The following two collections are not algebras: C4 = {∅, {a}, X} since, for instance, {a}c = {b, c} ∈/ C4 and C5 = {∅, {a}, {b}, {b, c}, X} since {b}c = {a, c} ∈/ C5. However, the smallest algebra which contains C4 is just C2. To see this, we can apply the argument in Theorem 82. Let F = {C2,P(X)} be the family of all algebras that contain C4. But A = C2 ∩ P(X) = C2. Exercise 2.6.2 Let X = N. Show that the collection A = {Ai : Ai is finite or N\Ai is finite} is an algebra on N and that it is a proper subset of P(N). The next theorem proves that it is always possible to construct a new collection of disjoint sets from an existing algebra with the property that its union is equivalent to the union of subsets in the existing algebra. This will become very useful when we begin to think about probability measures. Theorem 84 Let A be an algebra comprised of subsets {Ai : i ∈ Λ}. 11 Then there is a collection of subsets {Bi : i ∈ Λ} in A such that Bn ∩ Bm = ∅ for n 6= m and ∪i∈ΛBi = ∪i∈ΛAi. 11Note that the index set Λ can be countably or even uncountably infinite
CHAPTER 2. SET THEORY Proof.( Sketch) The theorem is trivial when the collection is finite(see Ex- ample 85 below ). When the collection is indexed on N, we let B1= A1 and for each n∈N{1l} define An\[A1UA2U…UA1-1] AnnA1∩A2∩…∩A-1 Since the complements and intersections of sets in A are in A, Bn EA and by construction Bn C An. The remainder of the proof amounts to showing that the above constructed sets are disjoint and yield the same union as the algebra.口 Exercise 2.6. 3 Finish the proof of Theorem 84 above. See Royden Prop2 p Note that Theorem 84 does not say that the new collection Bi: iEAl is necessarily itself an algebra. The next example shows this Example 85 Let X= a, b, cl and algebra A= P(X) with A1= a A2={6},A3={c},A4={a,6},A5={a,},A6={b,},Ar=0,As=X Let B1= A1. By construction B2=A2A1=16, B3= A3 A1 U A21 ich, Bn= AnA1U A2U... U An-11=0 for n>4. Note that the new ollection a, b, c is not itself an algebra, since it's not closed under complementation and that if we chose a different sequence of Ai we could obtain a different collection B;: iEAN In the next chapter, we will learn an important result: any(open)set of real numbers can be represented as a countable union of disjoint open ntervals. Hence we cannot guarantee that the set is in an algebra, which is closed only under finite union, even if all the sets belong to the algebra Thus we extend the notion of an algebra to countable collections that are closed under complementation and countable union Definition 86 A collection x of subsets of x is called a a-algebra of sets if()A(=X4)∈A∈ a and(ii) UnEN An∈ a if each An∈孔 As in the case of algebras,0,X∈ d and n∞1An=(u=m1A)∈ which means that a o-algebra is closed under countable intersections as well Furthermore, we can always construct the unique smallest o-algebra con- taining a given collection a(called the a-algebra generated by a)by forming the intersection of all the o-algebras containing a). This result is an exten- Sion of theorem 82
40 CHAPTER 2. SET THEORY Proof. (Sketch)The theorem is trivial when the collection is finite (see Example 85 below). When the collection is indexed on N, we let B1 = A1 and for each n ∈ N\{1} define Bn = An\ [A1 ∪ A2 ∪ ... ∪ An−1] = An ∩ Ac 1 ∩ Ac 2 ∩ ... ∩ Ac n−1. Since the complements and intersections of sets in A are in A, Bn ∈ A and by construction Bn ⊂ An. The remainder of the proof amounts to showing that the above constructed sets are disjoint and yield the same union as the algebra. Exercise 2.6.3 Finish the proof of Theorem 84 above. See Royden Prop2 p. 17. Note that Theorem 84 does not say that the new collection {Bi : i ∈ Λ} is necessarily itself an algebra. The next example shows this. Example 85 Let X = {a, b, c} and algebra A = P(X) with A1 = {a}, A2 = {b}, A3 = {c}, A4 = {a, b}, A5 = {a, c}, A6 = {b, c}, A7 = ∅, A8 = X. Let B1 = A1. By construction B2 = A2\A1 = {b}, B3 = A3\{A1 ∪ A2} = {c}, Bn = An\{A1 ∪ A2 ∪ ... ∪ An−1} = ∅ for n ≥ 4. Note that the new collection {{a}, {b}, {c}} is not itself an algebra, since itís not closed under complementation and that if we chose a different sequence of Ai we could obtain a different collection {Bi : i ∈ Λ}. In the next chapter, we will learn an important result: any (open) set of real numbers can be represented as a countable union of disjoint open intervals. Hence we cannot guarantee that the set is in an algebra, which is closed only under finite union, even if all the sets belong to the algebra. Thus we extend the notion of an algebra to countable collections that are closed under complementation and countable union. Definition 86 A collection X of subsets of X is called a σ−algebra of sets if (i) Ac (= X\A) ∈ X if A ∈ X and (ii) ∪n∈NAn ∈ X if each An ∈ X. As in the case of algebras, ∅, X ∈ X and ∩∞ n=1An = (∪ =∞ n=1 Ac n) c ∈ X which means that a σ-algebra is closed under countable intersections as well. Furthermore, we can always construct the unique smallest σ-algebra containing a given collection X (called the σ-algebra generated by X) by forming the intersection of all the σ-algebras containing X ). This result is an extension of Theorem 82
2.6. ALGEBRAS OF SETS 4 Theorem 87 Given any collection of subsets of x, there is a smallest o-algebra that contains Exercise 2.6.4 Prove Theorem 87 Exercise 2.6.5 Let C, d be collections of subsets of X.(i) Show that the smallest algebra generated by c is contained in the smallest a-algebra generated by C.(ii)IfC Cd, show the smallest o-algebra generated by C is contained in the smallest o-algebra generated by D
2.6. ALGEBRAS OF SETS 41 Theorem 87 Given any collection X of subsets of X, there is a smallest σ-algebra that contains X. Exercise 2.6.4 Prove Theorem 87. Exercise 2.6.5 Let C , D be collections of subsets of X. (i) Show that the smallest algebra generated by C is contained in the smallest σ-algebra generated by C. (ii) If C ⊂ D , show the smallest σ-algebra generated by C is contained in the smallest σ-algebra generated by D
CHAPTER 2. SET THEORY for Sections 2.1 to 2.2 Figure 2.1.1: Set O Fi 2.1.2: Distributive Property Figure 2.1.3: DeMorgan's Laws Figure 2.2.1: Cartesian Produ Figure s2.3to2,4 Figure 2.3. 1: Illustrating Partial vs Total Ordering Figure 2.3.3: A Partially Ordered Set that's not a Lattice Figure 2.3.4: Chains and Upper Bounds Figure 2.4.1a: f: A-B and 2.4.1b: Not a function Figure 2.4.2a: Graph of f in A X B and 2.4.2b: Not a function in A X B Figure 2.4.3a: Image Set and Figure 2.4.3b: Inverse Image Set F 4.4a: Graph of Fi Figure 2. 4.5 Figure 2.4. 6: Inverse Function Figure 2.4.7. Surjection .8. Graph 2.4.9. Graph of a Figures for Section 2.5 Figure 2.5.1: Countability ofN X N Figure 2.5.2: Uncountability of 10, 19 Figures for Section 2.6 Figure 2.5. 1: Smallest g-algebras
42 CHAPTER 2. SET THEORY Figures for Sections 2.1 to 2.2 Figure 2.1.1: Set Operations Figure 2.1.2: Distributive Property Figure 2.1.3: DeMorganís Laws Figure 2.2.1: Cartesian Product Figures for Sections 2.3 to 2.4 Figure 2.3.1: Illustrating Partial vs Total Ordering Figure 2.3.2: A Lattice Figure 2.3.3: A Partially Ordered Set thatís not a Lattice Figure 2.3.4: Chains and Upper Bounds Figure 2.4.1a: f : A → B and 2.4.1b: Not a function Figure 2.4.2a: Graph of f in A × B and 2.4.2b: Not a function in A × B Figure 2.4.3a: Image Set and Figure 2.4.3b: Inverse Image Set Figure 2.4.4a: Graph of 1 a Figure 2.4.4b: Restriction of 1 a and Figure 2.4.4c: Extension of 1 a Figure 2.4.5: Composition Figure 2.4.6: Inverse Function Figure 2.4.7. Surjection Figure 2.4.8. Graph of 2a Figure 2.4.9. Graph of a2 Figures for Section 2.5 Figure 2.5.1: Countability of N × N Figure 2.5.2: Uncountability of {0, 1}ω Figures for Section 2.6 Figure 2.5.1: Smallest σ−algebras
2.7. BIBLIOGRAPHY FOR CHAPTER 2 2.7 Bibliography for Chapter 2 Sections 2.1 to 2.2 drew on Bartle(1978, Ch 1), Munkres(1975, Ch 1), and Royden(1988, Ch 1, Sec. 1, 3, 4). The material on relations and correspon- dences in Section 2.3 is drawn from Royden(1988, Chl, Sec 7), Munkres (1975, Chl, Sec 3), Aliprantis and Border(1999, Ch 1, Sec 2), and Mas- Collel, Whinston, and Green(1995, Ch 1, Sec B). The material on functions in Section 5.2 is drawn from Bartle(1976, Ch 2)and Munkres(1975, Ch1 Sec 2). Section 2.5 drew from Munkres(1975, Chl, Sec 6-7) and Bartle (1976,Ch.3)
2.7. BIBLIOGRAPHY FOR CHAPTER 2 43 2.7 Bibliography for Chapter 2 Sections 2.1 to 2.2 drew on Bartle (1978, Ch 1), Munkres (1975, Ch.1), and Royden (1988, Ch 1, Sec. 1,3,4). The material on relations and correspondences in Section 2.3 is drawn from Royden (1988, Ch1, Sec 7), Munkres (1975, Ch1, Sec 3), Aliprantis and Border (1999, Ch.1, Sec 2),and MasCollel, Whinston, and Green (1995, Ch 1, Sec B). The material on functions in Section 5.2 is drawn from Bartle (1976, Ch 2) and Munkres (1975, Ch1, Sec 2). Section 2.5 drew from Munkres (1975, Ch1, Sec 6-7) and Bartle (1976, Ch.3)