ARE 210 Course Notes page 2 Date of last Update: 8/29/2003 page 2 BASIC CONCEPTS FOR THE ALGEBRA OF SETS Many types of study may be characterized by repeated experimentation under the same set of conditions. Each experiment has an outcome, but prior to the experiment the outcome cannot be predicted with certainty. If every possible outcome can be described a priori, and the experiment can be repeated, we have a random experiment. The collection of every possible outcome is the outcome set, or sample space. Generically, space means the totality of all elements, or outcomes. A sample space is a set C, a collection of members or elements, e, called events. Let C be a subset of C. That is, C is a collection of some of the possible out-comes. This is denoted C ⊂ C . Then C is an event. The outcomes, e, are elements (members) of the set of all possible outcomes, C. This is denoted e ∈C . The theory of probability is defined and developed axiomatically in terms of sets and an algebra system defined over sets. To develop an algebra of sets, we must have notions of order, equality, zero, addition, and multiplication similar to the algebra of numbers. Definitions: 1. Subset - A set C1 is a subset of the set C2, denoted CC12⊂ , if each element of C1 is also an element of C2. C C eC eC12 1 2⊂⇔∈⇒∈lq 2. Equality - If CC12⊂ and CC21⊂ , then CC12=. Two sets are equal if and only if they have exactly identical elements. 3. Null set - If C has no elements it is empty, the null set. This is de-noted C =∅. The null set is a subset of every other set. Logical note: If the hypothesis of a statement is false, then the conclusion always follows (the statement is vacuous). If e∈∅ (there are no such e's), then eC∈ for all C ⊂ C . If 11 0+=, then the world is flat. (Same type of statement.) 4. Union - The union of the sets C1 and C2, denoted CC12∪ , is the set of all elements in at least one of C1 or C2. 5. Intersection - The intersection of two sets C1 and C2 is the set of all elements belonging to both of the sets, CC eeC eC12 1 2∩ ≡∈ ∈: and lq Note: Intersections of sets satisfy commutative and associative laws. CC C C CC C CC12 3 1 23 2 13∩∩ ∩∩ ∩∩bg bgbg==. Similarly unions are commutative and associative. CC C C CC C CC12 3 1 23 2 13∪∪ ∪∪ ∪∪bg bgbg== Theorem: If CC12⊂ , then CC C12 2∪= and CC C12 1∩=. Proof: Suppose CC12⊂ . Then eC eC eC C∈⇒∈∈12 12& ∪ . Hence CCC212⊂ ∪ . eC C e C C C∈⇒∈⊂12 2 1 2∪ since . Hence CC C12 2∪ ⊂ . Therefore, CC C12 2∪=. eC eC eC C∈⇒∈∈12 12& ∩ . Hence CCC112⊂ ∩ . eC C eC∈⇒∈12 1∩ (by definition). Hence CC C12 1∩ ⊂ . Therefore, CC C12 1∩=. Q.E.D.ARE 210 Course Notes page 3 Date of last Update: 8/29/2003 page 3 DISTRIBUTIVE LAW FOR SETS CCCCC CC12 3 13 23∪∩ ∩∪∩bgbgbg= CCCCC CC12 3 13 23∩∪ ∪∩∪bgbgbg= eCC C eCC eC∈⇒∈ ∈12 3 12 3∪∩ ∪bg bg& ⇒∈eC1 or eC∈2 & eC∈3 Suppose eC∈1. Then eC∈1 & eC∈3 ⇒∈eCC13∩bg ⇒∈eCC CC13 23∩∪∩bgbg Suppose eC∈2. Then eCC eCC CC∈⇒∈23 13 23∩∩∪∩bgbgbg Hence CC C CC C C12 3 13 23∪∩ ∩∪∩bgbgbg⊂ . eCC CC eCC eCC∈⇒∈∈13 23 13 23∩∪∩ ∩ ∩bgbgor eC C eC∈⇒∈13 1∩ & eC eC C∈⇒∈312∪ & eC e C C C∈⇒∈3123∪∩bg eC C eC∈⇒∈23 2∩ & eC eC C∈⇒∈312∪ & eC e C C C∈⇒∈3123∪∩bg Hence CC C C C C13 23 12 3∩∪∩ ∪∩bgbgbg⊂ . Therefore, by definition of the equality of two sets, CC C CC C C12 3 13 23∪∩ ∩∪∩bgbgbg= . eCC C eCC eC∈⇒∈ ∈12 3 12 3∩∪ ∩bg bgor If eCC∈12∩bg, then eC∈1 & eC e C C∈⇒∈213∪bg & eCC∈23∪bg ⇒∈eCC CC13 23∪∩∪bgbg. If eC∈3, then eCC∈13∪bg & eCC∈23∪bg⇒∈eCC CC13 23∪∩∪bgbg Therefore, CC C CC C C12 3 13 23∩∪ ∪∩∪bgbgbg⊂ . eCC CC eCC eCC∈⇒∈∈13 23 13 23∪∩∪ ∪ ∪bgbgbgbg& ⇒∈eC1 & eC∈2, or eC∈3 ⇒∈eCC C12 3∩∪bg Therefore, CC C C CC C13 23 12 3∪∩∪ ∩∪bgbgbg⊂ Hence, CC C CC C C12 3 13 23∩∪ ∪∩∪bgbgbg= . 6. Complement If A ⊂ C , then the complement of A, denoted A*, is the set of all outcomes in C that are not in A. Ae eA*:≡∈ ∉Clq Examples: 1. C* =∅ 2. AAA⊂⇒=CC∪ * 3. AA∩ *=∅ 4. A∪CC= 5. AA∩C= 6. AA**bg= 7. AB B A∩=∅⇒⊂* 7. Partition: A partition of C is a collection of mutually exclusive events (subsets) whose union is C. CCN1,,…lq, CC ijij∩ =∅ ≠for all , CiiN==1∪C Examples: C,∅lq & CC,*lq for all C ⊂ C 8. De Morgan's Laws Theorem 1 AB A B∩∪bg***= eAB eAB∈⇒∉∩∩bg* ⇒∉eA or eB eA∉⇒∈* or eB e A B∈⇒∈***∪bg ⇒⊂AB A B∩∪bgb g*** eA B∈⇒**∪ eA∈* or eB∈* ⇒∉eA or eB∉ARE 210 Course Notes page 4 Date of last Update: 8/29/2003 page 4 ⇒∉ ⇒∈ ⇒ ⊂eAB eAB A B AB∩∩∪∩bg bgb gbg*** * Therefore, AB A B∩∪bg***= Theorem 2 AB A B∪∩bg***= eAB eAB∈⇒∉∪∪bg bg* ⇒∉eA and eB∉ ⇒∈eA* and eB e A B∈⇒∈***∩bg⇒⊂AB A B∪∩bgb g*** eA B∈⇒**∩bgeA∈ * and eB∈ * ⇒∉eA and eB∉ ⇒∉ ⇒∈eAB e AB∪∪bg* ⇒⊂AB AB** *∩∪bgbg Therefore, AB A B∪∩bg***= The class of subsets of the sample space C that will be relevant to the defini-tions and axioms of probability is called a σ-algebra: (1) Algebra - closed under ∪∩,,* (similar to real numbers and closure under +⋅, ); (2) σ ⇒ summability or countability - the algebraic properties hold for a countable number of operations.ARE 210 Course Notes page 5 Date of last Update: 8/29/2003 page 5 PROBABILITY SET FUNCTIONS C is the sample space of a random experiment. If C ⊂ C is an event, what is PCbg, the probability that the outcome is an element of C? What properties should such a function have? (THE AXIOMS) P: C →R, a probability set function, satisfies 1. PC Cbg≥⊂0for all C (non-negativity) 2. PC C PC PC12 1 2∪∪ bgbgbg=++ if CCij∩ =∅ for all ij≠ (mutually exclusive additivity) 3. P Cbg= 1 (something must happen) for all subsets of C such that a) ABAB⊂⊂⇒⊂CC C& ∪bg, AB AB*,*,⊂⊂ ⊂CC C∩bg b) Ci Ciii⊂=⇒FHGIKJ⊂=∞CC for all 1 21,,…∪ Such a class of subsets is called a σ-algebra on C. The probability set function is a special kind of function. Usually we think of a function in the form yfx=bg