Class Notes (839,113)
ECSE 305 (5)
Lecture

# chap02.pdf

36 Pages
93 Views

Department
Electrical Engineering
Course Code
ECSE 305
Professor
Ioannis P.

This preview shows pages 1,2,3,4. Sign up to view the full 36 pages of the document.
Description
12 Chapter 2 Background material Chapter overview: ▯ Review of set theory ▯ Combinatorial methods 2.1 Set theory 2003 Be▯t Champagne Compiled January 12, 2012 2.1 Set theory 13 2.1.1 Basic terminology De▯nition of a set: ▯ A set is a collection of objects (concrete or abstract), called elements, that usually share some common attributes, but are not otherwise re- stricted in any fashion. ▯ The curly brackets f and g are used as delimiters when specifying the content of a set. This may be achieved by either listing all the elements of the set explicitly, as is f1;2;3;4;5;6g (2.1) or by stating the common properties satis▯ed by its elements, as in fa : a is a positive integer ▯ 6g (2.2) In the latter case, the notation \a :" should read \all a such that". ▯ To indicate that an object a is an element of a set A, we write a 2 A; we also say that a is a member of, or belongs to, A. If a is not an element of A, we write a 62 A. ▯ Two sets A and B are identical (or equal) if and only if (i▯) they have the same elements, in which case we write A = B. If A and B are not identical, we write A 6= B. ▯ Example: Let A = f1;2;:::;6g and B = f2;4;6g. Then A 6= B because 1 2 A while 1 62 B. 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 14 Subset: ▯ If every element of a set A is also an element of a set B, we say that A is contained in B, or that A is a subset of B, and write A ▯ B. ▯ If A is a subset of B but there exists b such that b 2 B and b 62 A, we sometimes say that A is a proper subset of B and write A ▯ B. ▯ The negations of the set relations ▯ and ▯ are denoted by 6▯ and 6▯, respectively. ▯ Example: let A = f1;2;:::;6g, B = f2;4;6g and C = f0;1g, then B ▯ A, B ▯ A, C 6▯ A, etc. Sample space and empty set: ▯ In practical applications of set theory, all sets of interest in a given situ- ation are usually subsets of a larger set called sample space, or universal set, and denoted by the letter S. ▯ It is also common practice to introduce a degenerate set containing no elements; the latter is called the empty set, or null set, and is denoted by the symbol ;. 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 15 Theorem 2.1: Let A, B and C denote arbitrary subsets of a sample space S. The following relations hold: (a) A ▯ A (b) A ▯ B and B ▯ C implies A ▯ C (c) A = B if and only if A ▯ B and B ▯ A (d) ; ▯ A ▯ S Proof: These basic properties follow directly from the preceding de▯nitions; their proof is left as an exercise to the reader. ▯ 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 16 Commonly used sets of numbers: ▯ Basic sets of numbers: - Positive integers, or natural numbers: N = f1;2;3;:::g - Integers: Z = f0;▯1;▯2;:::g a - Rational numbers: Q = f :ba;b 2 Z and b 6= 0g - Real numbers: R p - Complex numbers: C = fa + jb : a;b 2 Rg, where j = ▯1 Note that N ▯ Z ▯ Q ▯ R ▯ C. ▯ Let a and b be two arbitrary real numbers. The following subsets of R are called intervals from a to b: - Open interval: (a;b) = fx 2 R : a < x < bg - Closed interval: [a;b] = fx 2 R : a ▯ x ▯ bg - Left semi-open interval: (a;b] = fx 2 R : a < x ▯ bg - Right semi-open interval: [a;b) = fx 2 R : a ▯ x < bg Note that these intervals are empty, i.e. identical to the empty set ;, when a > b. 2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 17 Finite versus in▯nite sets: ▯ A set is called ▯nite if it is empty or contains a ▯nite number of elements; otherwise it is called in▯nite. ▯ A set is called countable if it is ▯nite (countably ▯nite) or if it is in▯nite but can be put into a one-to-one correspondence with the set of positive integers N (countably in▯nite). In the latter case, the elements of the set can be indexed sequentially. ▯ A set that is not countable is said to be uncountable or uncountably in▯nite. ▯ Examples: - The set S = f1;2;3;4;5;6g is countably ▯nite. - Examples of countably in▯nite sets include N, Z and Q. - Examples of uncountably in▯nite sets include R and the open inter- vals (a;b) for any a < b in R. 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 18 Product sets: ▯ Let A and B be two arbitrary sets, not necessarily associated to the same sample space. The product set of A and B, denoted A▯B, is the set of all ordered pairs (a;b) such that a 2 A and b 2 B. That is, A ▯ B = f(a;b) : a 2 A and b 2 Bg (2.3) 2 ▯ The product set A ▯ A is also denoted in a more compact form as A . ▯ The generalization of this concept to products of more than two sets is immediate. n ▯ As an example, the notation R , for n a positive integer, denotes the set of all n-tuples (a 1a ;2::;a n where a 2 i for i = 1;:::;n. Example 2.1: I (a) Consider a single toss of a coin. The set of all possible observable results, or outcomes, can be described as S1= fH;Tg where H denotes heads and T denotes tails. (b) Consider two consecutive tosses of a coin. The set of all possible outcomes is S2= fHH;HT;TH;TTg where, for example, the ordered sequence HT corresponds to H on the ▯rst toss and T on the second toss. Observe that S2= fH;Tg ▯ fH;Tg = S 1 The event that at least one head is observed can be represented by the subset A = fHH;HT;THg ▯ S 2 J 2003 Beno^ ▯t Champagne Compiled January 12, 2012 2.1 Set theory 19 2.1.2 Set operations De▯nitions: Let A and B be arbitrary subsets of a sample space S. We de▯ne the following operations: ▯ The union of the sets A and B, denoted A[B, is the set of all elements that belong to at least one of the sets A or B: A [ B = fx 2 S : x 2 A or x 2 Bg (2.4) ▯ The intersection of the sets A and B, denoted A \ B, is the set of all elements that belong to both A and B: A \ B = AB = fx 2 S : x 2 A and x 2 Bg (2.5) c ▯ The complement of the set A, denoted A , is the set of all elements of S that do not belong to A: A = fx 2 S : x 62 Ag (2.6) ▯ The di▯erence of the sets A and B, denoted A ▯ B, is the set of all elements of A that do not belong to B: A ▯ B = fx 2 S : x 2 A and x 62 Bg (2.7) 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 20 Remarks: ▯ In the above de▯nition of the union, the \or" is a logical one, meaning that x may be in A or B or both. ▯ In the probability literature, the symbol \ for the intersection is some- times omitted, so that the notations A \ B and AB are equivalent. ▯ If A \ B = ;, we say that A and B are mutually exclusive (or disjoint). ▯ Finally, note that A = S ▯ A and A ▯ B = A \ B . c c 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 21 Theorem 2.2: Let A, B and C be arbitrary subsets of a sample space S. The following identities hold: (a) Basic identities: A [ A = A and A \ A = A (2.8) A [ S = S and A \ S = A (2.9) A [ ; = A and A \ ; = ; (2.10) (b) Commutative laws: A [ B = B [ A and A \ B = B \ A (2.11) (c) Associative laws: (A[B)[C = A[(B [C) and (A\B)\C = A\(B \C) (2.12) (d) Distributive laws: A\(B[C) = (A\B)[(A\C) and A[(B\C) = (A[B)\(A[C) (2.13) (e) Complementarity laws: A [ A = S and A \ A = ; (2.14) c c c c (A ) = A; S = ; and ; = S (2.15) (f) DeMorgan’s laws: (A [ B) = A \ B c and (A \ B) = A [ B c (2.16) 2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 22 Proof: The proof of such properties is tedious but otherwise straightforward. For any of the above equalities, we have to show set inclusion in both direc- tion, that is: any arbitrary element of the set on the left-hand side is also an element of the set on the right-hand side, and vice versa. This requires the use and manipulation of logical assertions and operators. Familiarity with the latter concepts is assumed. As an example, consider the DeMorgan’s identity (A \ B) = A [ B . We c c have x 2 (A \ B) c () x 62 A \ B () x 62 A or x 62 B () x 2 A or x 2 B c c c () x 2 A [ B The other identities may be proved in a similar way; this is left as an exercise for the reader. ▯ 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 23 Example 2.2: I A die is rolled once. The set of possible outcomes is S = f1;2;3;4;5;6g De▯ne the subsets A = fx 2 S : x ▯ 3g = f1;2;3g B = fx 2 S : x even g = f2;4;6g We have: A \ B = f2g A [ B = f1;2;3;4;6g A c = f4;5;6g B c = f1;3;5g Let us verify DeMorgan’s Laws, i.e. Theorem 2.2 (f). From the above, we have (A [ B)c = f5g A \ B c = f5g which shows that the ▯rst identity in (2.16) is satis▯ed. In the same way, c (A \ B) = f1;3;4;5;6g c c A [ B = f1;3;4;5;6g which shows the validity of the second identity in (2.16). J 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 24 Venn diagrams: ▯ Venn diagrams provide a useful mechanism for visualizing various set- theoretic operations. ▯ Basic idea: - represent sets as planar areas delimited by closed contours; - these contours are included in a larger rectangular area representing the sample space S itself; - an operation between various sets is shown as a shaded area. ▯ This is illustrated in Figure 2.1 for the following operations: A [ B, A \ B, A and A ▯ B. S S A B A B (a)A▯ B (b)A▯ B S S A B A B c (c)A (d)A− B Figure 2.1: Use of Venn diagrams to illustrate set operations. 2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 25 ▯ Venn diagrams are often used as an intuitive device for gaining insight into complex set relations and operations, although their use in the for- mal proof of set properties is not quite appropriate. ▯ As an example, the following theorem may be easily justi▯ed on the basis of Venn diagrams. Theorem 2.3: Let A and B be arbitrary subsets of a sample space S. Anyone of the following conditions is equivalent to the inclusion A ▯ B: (a) A \ B = A (b) A [ B = B c (c) A \ B = ; c (d) A [ B = S (e) B ▯ A c Justi▯cation based on Venn diagrams: A Venn diagram’s interpretation of Theorem 2.3 (a) and (b) is illustrated in Figure 2.2. S S B B A A (a)A▯ B = A (b)A▯ B = B Figure 2.2: Interpretation of Theorem 2.3 based on Venn diagrams. c 2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 26 Some generalizations: ▯ Consider a sequence of indexed subsets of S, say A wiere the index i 2 I, with I being a subset (▯nite or in▯nite) of the natural numbers N. ▯ The union and intersection of the sets A , i 2 I, are de▯ned as i S A = fx 2 S : x 2 A for some i 2 Ig (2.17) i2I i i T A i fx 2 S : x 2 A fir all i 2 Ig (2.18) i2I S 1 T 1 When I = N, these may be denoted as i=1 and i=1, respectively. ▯ De Morgan’s laws admit immediate generalization to this case: S c T c T c S c ( A i = A i and ( A i = Ai (2.19) i2I i2I i2I i2I ▯ We say that the sequence A ;i 2 N, is increasing if A ▯ A ▯ A ▯ ::: i 1 2 3 In this case, we de▯ne S1 lim A = A (2.20) i!1 i i=1 i ▯ We say that the sequence A ii 2 N, is decreasing if 1 ▯ A 2 A ▯ 3:: In this case, we de▯ne T1 lim A = A (2.21) i!1 i i i=1 2003 Beno▯t Champagne Compiled January 12, 2012 2.1 Set theory 27 Example 2.3: 2 I Consider the real plane, S = R . De▯ne A as tie subsets of all points in on or inside a circle of radius i centered at the origin, where i is a positive integer. That is 2 2 2 2 A i f(x;y) 2 R : x + y ▯ i g; i 2 N Observe that A1▯ A ▯2A ▯ :3: so that the sequence Aiis increasing. This is illustrated in Figure 2.3. y A3 A 2 A1 1 2 3 x Figure 2.3: An increasing sequence of subsets. Also note that (try to prove it) S A i f(x;y) 2 R : (x;y) 2 A foi some ig = R 2 i=1 Therefore, lim Ai= R 2 i!1 J 2003 Beno^ ▯t Champagne Compiled January 12, 2012 2.1 Set theory 28 2.1.3 Sets of sets The elements of a set may themselves be sets. Such sets of sets are often called classes or families of sets. Sets having for elements subsets of a sample space S play a central role in probability. Below, we develop these concepts. Power set: ▯ The set of all the subsets of a set S is called the power set of S and is denoted by P ,Sor simply P. ▯ Since ; ▯ S and S ▯ S, we have by de▯nition of P that S 2 P and S S 2 P S ▯ For example, let S = f0;1g. Then P = S;;f0g;f1g;Sg Remarks: ▯ When the sample space S is uncountably in▯nite (e.g. S = R), the power set P Sill typically contain undesirable subsets that pose serious mathematical di▯culties. ▯ In such situations, it is usually desirable to work with a much smaller subset of PS, that do not include the undesirable subsets. ▯ This leads to the notion of set algebras. 2003 Beno^▯t Champagne Compiled January 12, 2012 2.1 Set theory 29 Set algebra: Let F be a set of subsets of S, that is F ▯ P . We saS that F is an algebra i▯ (a) S 2 F (b) A 2 F ) A 2 F c (c) A;B 2 F ) A [ B 2 F Remarks: c ▯ From (a) and (b), it follows that ; 2 F since ; = S . ▯ According to the above de▯nition, the algebra F is closed under the operations of complementation and union. ▯ Using DeMorgan’s laws, you should be able to show that F is also closed under the operation of intersection, that is: A;B 2 F ) A \ B 2 F. Example 2.4: I Let S = f0;1g. The corresponding power set is P S f;;f0g;f1g;Sg: It is easy to check that P is an algebra... S (a) S 2 P S (b) For any A 2 P S we have A 2 P. For example: c c ; = S 2 P ;S f0g = f1g 2 P S etc. (c) For any A;B 2 P ,Swe have A [ B 2 P .SFor example: ; [ ; = ; 2 PS; ; [ f0g = f0g 2 PS; etc. Not
More Less

Only pages 1,2,3,4 are available for preview. Some parts have been intentionally blurred.

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.