876
CHAPTER 12
12.1
Counting and Probability
Sets and Counting OBJECTIVES
1 2 3 4
Find All the Subsets of a Set Find the Intersection and Union of Sets Find the Complement of a Set Count the Number of Elements in a Set
A set is a well-defined collection of distinct objects. The objects of a set are called its elements. By well-defined, we mean that there is a rule that enables us to determine whether a given object is an element of the set. If a set has no elements, it is called the empty set, or null set, and is denoted by the symbol ¤. Because the elements of a set are distinct, we never repeat elements. For example, we would never write 51, 2, 3, 26; the correct listing is 51, 2, 36. Because a set is a collection, the order in which the elements are listed is immaterial. 51, 2, 36, 51, 3, 26, 52, 1, 36, and so on, all represent the same set.
EXAMPLE 1
Writing the Elements of a Set Write the set consisting of the possible results (outcomes) from tossing a coin twice. Use H for heads and T for tails.
Solution
In tossing a coin twice, we can get heads each time, HH; or heads the first time and tails the second, HT; or tails the first time and heads the second, TH; or tails each time, TT. Because no other possibilities exist, the set of outcomes is 5HH, HT, TH, TT6
1 Find All the Subsets of a Set ✓ We now look at ways that two sets can be compared, beginning with set equality. If two sets A and B have precisely the same elements, we say that A and B are equal and write A = B. If each element of a set A is also an element of a set B, we say that A is a subset of B and write A 8 B. If A 8 B and A Z B, then we say that A is a proper subset of B and write A ( B. If A 8 B, every element in set A is also in set B, but B may or may not have additional elements. If A ( B, every element in A is also in B, and B has at least one element not found in A. Finally, we agree that the empty set is a subset of every set; that is, ¤ 8 A,
EXAMPLE 2
for any set A
Finding All the Subsets of a Set Write down all the subsets of the set 5a, b, c6.
Solution
To organize our work, we write down all the subsets with no elements, then those with one element, then those with two elements, and finally those with three elements. These will give us all the subsets. Do you see why?
Copyright © 2006 Pearson Education, Inc., publishing as Pearson Prentice Hall
SECTION 12.1
0 Elements ¤
1 Element 5a6, 5b6, 5c6
2 Elements 5a, b6, 5b, c6, 5a, c6
NOW WORK PROBLEM
Sets and Counting
877
3 Elements 5a, b, c6
25.
2 Find the Intersection and Union of Sets ✓ If A and B are sets, the intersection of A with B, denoted A ¨ B, is the set consisting of elements that belong to both A and B. The union of A with B, denoted A ´ B, is the set consisting of elements that belong to either A or B, or both.
EXAMPLE 3
Finding the Intersection and Union of Sets Let A = 51, 3, 5, 86, B = 53, 5, 76, and C = 52, 4, 6, 86. Find: (a) A ¨ B
Solution
(c) B ¨ 1A ´ C2
(b) A ´ B
(a) A ¨ B = 51, 3, 5, 86 ¨ 53, 5, 76 = 53, 56 (b) A ´ B = 51, 3, 5, 86 ´ 53, 5, 76 = 51, 3, 5, 7, 86 (c) B ¨ 1A ´ C2 = 53, 5, 76 ¨ 351, 3, 5, 86 ´ 52, 4, 6, 864
= 53, 5, 76 ¨ 51, 2, 3, 4, 5, 6, 86 = 53, 56
NOW WORK PROBLEM
9.
3 Find the Complement of a Set ✓ Usually, in working with sets, we designate a universal set U, the set consisting of all the elements that we wish to consider. Once a universal set has been designated, we can consider elements of the universal set not found in a given set. If A is a set, the complement of A, denoted A, is the set consisting of all the elements in the universal set that are not in A.*
EXAMPLE 4
Finding the Complement of a Set If the universal set is U = 51, 2, 3, 4, 5, 6, 7, 8, 96 and if A = 51, 3, 5, 7, 96, then A = 52, 4, 6, 86. It follows that A ´ A = U and A ¨ A = ¤. Do you see why?
Figure 1
NOW WORK PROBLEM
Universal set
B A C
17.
It is often helpful to draw pictures of sets. Such pictures, called Venn diagrams, represent sets as circles enclosed in a rectangle, which represents the universal set. Such diagrams often help us to visualize various relationships among sets. See Figure 1. *
Some books use the notation A¿ for the complement of A.
Copyright © 2006 Pearson Education, Inc., publishing as Pearson Prentice Hall
878
CHAPTER 12
Counting and Probability
If we know that A ( B, we might use the Venn diagram in Figure 2(a). If we know that A and B have no elements in common, that is, if A ¨ B = ¤, we might use the Venn diagram in Figure 2(b). The sets A and B in Figure 2(b) are said to be disjoint. Figure 2
Universal set
Universal set
B A
A
B
(b) A B ∅ disjoint sets
(a) A B proper subset
Figures 3(a), 3(b), and 3(c) use Venn diagrams to illustrate the definitions of intersection, union, and complement, respectively.
Figure 3
Universal set
A
B
(a) A B intersection
Universal set
Universal set
A
A
B
(b) A B union
A
(c) A complement
4 Count the Number of Elements in a Set ✓ As you count the number of students in a classroom or the number of pennies in your pocket, what you are really doing is matching, on a one-to-one basis, each object to be counted with the set of counting numbers 1, 2, 3, Á , n, for some number n. If a set A matched up in this fashion with the set 51, 2, Á , 256, you would conclude that there are 25 elements in the set A. We use the notation n1A2 = 25 to indicate that there are 25 elements in the set A. Because the empty set has no elements, we write n1¤2 = 0 If the number of elements in a set is a nonnegative integer, we say that the set is finite. Otherwise, it is infinite. We shall concern ourselves only with finite sets. Look again at Example 2. A set with 3 elements has 2 3 = 8 subsets. This result can be generalized. If A is a set with n elements, then A has 2 n subsets. For example, the set 5a, b, c, d, e6 has 2 5 = 32 subsets.
Copyright © 2006 Pearson Education, Inc., publishing as Pearson Prentice Hall
SECTION 12.1
EXAMPLE 5
Sets and Counting
879
Analyzing Survey Data In a survey of 100 college students, 35 were registered in College Algebra, 52 were registered in Computer Science I, and 18 were registered in both courses. (a) How many students were registered in College Algebra or Computer Science I? (b) How many were registered in neither course?
Solution
(a) First, let A = set of students in College Algebra B = set of students in Computer Science I Then the given information tells us that n1A2 = 35
Figure 4 Universal set
A
B 17 18 34
31
n1B2 = 52
n1A ¨ B2 = 18
Refer to Figure 4. Since n1A ¨ B2 = 18, we know that the common part of the circles representing set A and set B has 18 elements. In addition, we know that the remaining portion of the circle representing set A will have 35 - 18 = 17 elements. Similarly, we know that the remaining portion of the circle representing set B has 52 - 18 = 34 elements. We conclude that 17 + 18 + 34 = 69 students were registered in College Algebra or Computer Science I. (b) Since 100 students were surveyed, it follows that 100 - 69 = 31 were registered in neither course. NOW WORK PROBLEMS
33
AND
39.
The solution to Example 5 contains the basis for a general counting formula. If we count the elements in each of two sets A and B, we necessarily count twice any elements that are in both A and B, that is, those elements in A ¨ B. To count correctly the elements that are in A or B, that is, to find n1A ´ B2, we need to subtract those in A ¨ B from n1A2 + n1B2.
Theorem
Counting Formula If A and B are finite sets, then n1A ´ B2 = n1A2 + n1B2 - n1A ¨ B2
(1)
Refer back to Example 5. Using (1), we have n1A ´ B2 = n1A2 + n1B2 - n1A ¨ B2 = 35 + 52 - 18 = 69 There are 69 students registered in College Algebra or Computer Science I. A special case of the counting formula (1) occurs if A and B have no elements in common. In this case, A ¨ B = ¤, so n1A ¨ B2 = 0.
Theorem
Addition Principle of Counting If two sets A and B have no elements in common, that is, if A ¨ B = ¤, then n1A ´ B2 = n1A2 + n1B2 We can generalize formula (2).
Copyright © 2006 Pearson Education, Inc., publishing as Pearson Prentice Hall
(2)
880
CHAPTER 12
Counting and Probability
Theorem
General Addition Principle of Counting If, for n sets A 1 , A 2 , Á , A n , no two have elements in common, then n1A 1 ´ A 2 ´ Á ´ A n2 = n1A 12 + n1A 22 + Á + n1A n2
EXAMPLE 6
(3)
Counting As of June, 2002, federal agencies employed 93,445 full-time personnel authorized to make arrests and to carry firearms. Table 1 lists the type of law-enforcement officer and the corresponding number of full-time officers. No officer is classified as more than one type of officer.
Table 1
Type of Officer
Number of Full-time Federal Officers
Criminal (investigation/enforcement)
37,208
Police response and patrol
20,955
Corrections
16,915
Noncriminal (investigation/inspection)
12,801
Court operations
4,090
Security/protection
1,320
Other
156
SOURCE: Bureau of Justice Statistics
(a) How many full-time law-enforcement officers in the United States federal government were criminal officers or corrections officers? (b) How many full-time law-enforcement officers in the United States federal government were criminal officers, corrections officers, or noncriminal officers?
Solution
Let A represent the set of criminal officers, B represent the set of corrections officers, and C represent the set of noncriminal officers. No two of the sets A, B, and C have elements in common since a single officer cannot be classified as more than one type of officer. Then n1A2 = 37,208
n1B2 = 16,915
n1C2 = 12,801
(a) Using formula (2), we have n1A ´ B2 = n1A2 + n1B2 = 37,208 + 16,915 = 54,123 There were 54,123 officers that were criminal or corrections officers. (b) Using formula (3), we have n1A ´ B ´ C2 = n1A2 + n1B2 + n1C2 = 37,208 + 16,915 + 12,801 = 66,924 There were 66,924 officers that were criminal, corrections, or noncriminal officers. NOW WORK PROBLEM
43.
Copyright © 2006 Pearson Education, Inc., publishing as Pearson Prentice Hall
