L.A. Math: Romance, Crime, and Mathematics in the City of Angels
Page 20
Once a universal set has been defined, it makes sense to talk about all the objects in the universal set that are not in a given set. The complement of the set A, written A′, is {x : x ∈ U, x ∉ A}.
Example 3: Let U be the universal set consisting of positive whole numbers. If A = {1, 2, 3}, then describe A′ in two different ways, using both words and set-builder notation.
Solution: A′ is the set of all positive whole numbers greater than 3. Using set-builder notation, this would be A′ = {x : x is a positive whole number greater than 3}. ■
The complement of a set is a relative concept, in that it needs a universal set in order to make sense. In example 3, for instance, it is almost certain that we don’t want to have to worry about hippopotamuses when considering the set A′!
The Connection between Logic and Set Theory
Set theory has an extremely useful connection with logic. If P(x) is a proposition about the variable x (such as “x is a number greater than 7”), then P = {x : P(x) is true} is the set of all things for which P(x) is a true statement. In this case, P would be the set of all numbers greater than 7. Similarly, we define Q = {x : Q(x) is true}.
If both P(x) and Q(x) are propositions and the sets P and Q are defined as above, then the logical statement IF P(x) THEN Q(x) for all x supplies the same information as the set theory statement P ⊆ Q.
For example, if P(x) is the proposition that “x is a number greater than 7,” and Q(x) is the proposition that “x is a number greater than 4,” clearly P(x) ⇒ Q(x). Notice that if P = {x : x > 7} and Q = {x : x > 4}, then P ⊆ Q.
The Empty Set
The empty set is the set that contains no elements. If sets are lunch-boxes, there’s nothing in this lunchbox. The empty set is written ∅.
One of the most common mistakes is to confuse the empty set, ∅, with the number 0. As we shall see, there are certain similarities between the two objects, but they belong to different mathematical systems. It is as if one were to confuse the contents of an empty lunchbox (the empty set) with the cost of purchasing those nonexistent contents (zero).
The empty set has an extremely important property: it is a subset of every set! While this appears surprising at first, its proof simply involves the logical negation of the statement: ∅ ⊆ A. If it is false that ∅ ⊆ A, then there must be some element in ∅ that is not an element of A. But this is a contradiction because there are no elements in ∅—and once an assumption leads to a contradiction, that assumption must be false.
For example, the empty set is a subset of G, the set of all giraffes, for if it were not, there would be a giraffe in the empty set.
UNIONS AND INTERSECTIONS
We turn now to the question of how to combine two sets. Any interesting combination of two sets must itself be a set, just as the interesting ways to combine numbers (addition, subtraction, multiplication, and division) result in numbers. The two basic ways to combine sets are intersection and union.
The intersection of two sets A and B, written A ∩ B, is the set of all elements common to both sets. If we define this using set-builder notation, A ∩ B = {x : x ∊ A and x ∊ B}.
Example 4: Let A = {1, 2, 3} and B = {2, 3, 4}. Then A ∩ B = {2, 3}.
If A and B have no elements in common, then A and B are said to be disjoint. In this case, A ∩ B = ∅.
Example 5: If A = {1, 2, 3} and B = {4, 5}, then A and B are disjoint, and A ∩ B = ∅.
The other basic way of combining the two sets A and B, the union of A and B, written A ∪ B, is the set of all elements that belong to either (or both) of the two sets. If we define this union using set-builder notation, A ∪ B = {x : x ∈ A or x ∈ B}.
Notice that the “or” used in defining the union of two sets is the inclusive “or,” which is also the “or” of choice in logic. In day-to-day conversation, it is usually clear from context whether the inclusive or exclusive “or” is intended, but all the definitions of mathematics use the inclusive “or.”
Example 6: Let A = {rat, cat, cow} and B = {dog, rat, cat, pig, yak}. Then A ∩ B = {rat, cat}, and A ∪ B = {rat, cat, cow, dog, pig, yak}.
In example 6, although “cat” appeared in both A and B, it is not listed twice in A ∪ B. When one is asked the contents of a lunchbox, it is repetitive to say, “a ham sandwich, uh, a ham sandwich, a bag of potato chips, and an apple.”
When more than two sets are involved, parentheses are used to indicate which operations should be performed first, just as they are in arithmetic. Suppose that A = {Alan, Betty, Carol}, B ={Betty, David, Frank}, and C = {Alan, Carol, Edward}. Then (A ∪ B) ∩ C is determined first by computing A ∪ B = {Alan, Betty, Carol, David, Frank}, and then (A ∪ B) ∩ C = {Alan, Carol}. Notice that, if we were to compute A ∪ (B ∩ C), we would first determine B ∩ C = ∅, and then A ∪ (B ∩ C) = {Alan, Betty, Carol}. Therefore, the expression A ∪ B ∩ C must be parenthesized in order to be unambiguously determined.
Unlike arithmetic, where multiplication takes precedence over addition (so that, in the expression 2 + 3 × 4, the multiplication is performed first), there is no precedence hierarchy for the operations of union and intersection. Union and intersection are both associative operations, that is,
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)
If only unions are involved, or intersections, it is not necessary to parenthesize, but if both operations appear in the same expression, you must parenthesize them in order to avoid ambiguity.
One possible reason that the empty set gets confused with the number 0 is that the empty set behaves in a similar fashion, relative to the operations of union and intersection, that the number 0 behaves relative to the operations of addition and multiplication.
(1) A ∪ ∅ = A
and
(2) A ∩ ∅ = ∅
If one regards the empty set as the set-theory analog of the number 0, then (1) is analogous to the arithmetic property a + 0 = a, and (2) to the arithmetic property a × 0 = 0.
We have encountered both unions and intersections in the preceding story. If we let L denote the set of all members of Lisa’s animal rights group who planned on attending the lobbying effort and R denote the set of members who planned on raiding the laboratory, then L ∪ R is the set of all the activists, those members who planned to participate in at least one of the two activities. L ∩ R consists of the “hard core” who planned to participate in both.
Many of the most interesting sets have only a finite number of things in them. If A is such a set, then N(A) denotes the number of things in A. If A = {Alice, Betty, Carlos}, then N(A) = 3. Although there are many sets A for which N(A) = 3, there is only one set for which N(A) = 0, and that is the empty set.
The Fundamental Counting Principle
(Fundamental Counting Principle continued from p. 64)
In the preceding story, Pete makes use of an extremely important principle of counting.
If A and B are finite sets, then N(A ∪ B) = N(A) + N(B) − N(A ∩ B)
This valuable formula plays an important role in the study of probability, and so it is worth spending a little effort to verify it.
Pete’s explanation was that, when we add N(A) to N(B), obtaining N(A) + N(B), we are counting everything that appears in A ∩ B twice. Therefore, if we wish to compare N(A ∪ B) with N(A) + N(B), we must realize that N(A) + N(B) counts everything in A ∩ B twice. So N(A) + N(B) = N(A ∪ B) + N(A ∩ B) since elements that belong to A or B, but not both, are counted once on each side of the equation, and elements that belong to A ∩ B are counted twice on each side of the equation. Subtracting N(A ∩ B) from both sides now yields the Fundamental Counting Principle.
Example 7: A survey of the 140 customers at an electronics supply store who owned either a high-definition TV or a GoPro camera revealed that 105 of them owned an HDTV and 28 owned both. How many owned a GoPro camera?
Solution: It is certainly possible to simply “plug into” the Fundamental Counting P
rinciple. Let H be the set of HDTV owners, C the set of GoPro camera owners. Then N(H ∪ C) = 140. Since N(H) = 105 and N(H ∩ C) = 28, we have N(H ∪ C) = N(H) + N(C) − N(H ∩ C), so 140 = 105 + N(C) − 28 = 77 − N(C). Therefore, N(C) = 140 − 77 = 63. ■
The Difference of Two Sets
Another set that is of interest is the difference AB, which is defined as the set of all things in A but not in B. That is, AB = A ∩ B′, or, using set-builder notation, AB = {x : x ∈ A and x ∉ B}. In examples 5 and 6, we used the idea of AB before we had specifically defined it.
Example 8: If A = {dog, pig, rat, cat, yak} and B = {rat, cat}, what is AB? What is BA?
Solution: AB is the set of all things belonging to A but not to B, which is {dog, pig, yak}. BA is the set of all things belonging to B but not to A, which is ∅. ■
We have mentioned the analogy between arithmetic and set theory. There is a temptation to regard the set-theoretic difference as being analogous to subtraction because when we construct the set AB we are “taking away” the things in B from A. However, this analogy should not be taken too far. For example, if the number b is larger than the number a, the difference a − b is negative. If the set B is “larger” than the set A (i.e., B ⊇ A), the set-theoretic difference AB = ∅, the empty set. This situation occurs in the second part of example 7. There is no concept in set theory analogous to negative numbers.
APPENDIX 8
THE CHINESE RESTAURANT PRINCIPLE: COMBINATORICS IN “NOTHING TO CROW ABOUT”
The need for counting techniques arises because it is often necessary to count very large numbers of items. After all, if there are only five or so items in a set, one just counts them. On the other hand, if there are several hundred items in a set, counting them is likely to take some time, and there is the possibility of making a mistake. It may even happen that the number of items we wish to count is so large that we would never be able to do it directly.
We have already discussed one of the most important counting procedures, the Fundamental Counting Principle, which is summarized in the formula
N(A ∪ B) = N(A) + N(B) − N(A ∩ B)
In this appendix, you’ll learn about counting techniques based on successive choices. Many decisions can be viewed as a procedure based on successive choices. When we order dinner in a restaurant, we successively choose an appetizer, an entree, and a dessert. When a basketball coach selects a starting line-up, he or she chooses the center, the two forwards, and the two guards.
Mathematics started with the problem of counting, and counting problems still underlie many of the most important areas of mathematics, such as probability, statistics, and decision theory. The techniques in this section reappear throughout the remainder of this book.
WHERE THE CHINESE RESTAURANT PRINCIPLE COMES FROM
The Chinese Restaurant Principle Pete referred to in chapter 8 derives its name from the following situation. A staple of Chinese restaurants has been the fixed-price meal, consisting of one appetizer chosen from a list of many different appetizers, and one main course from a similar list. It is traditional for the menu to present these choices in the form of two columns.
Menu
Column A
Column B
Won Ton Soup
Sweet and Sour Pork
Spareribs
Lemon Chicken
Rumaki
Oyster Beef
Egg Roll
Moo Goo Gai Pan
Dumplings
Shrimp with Lobster Sauce
Mixed Fried Noodles
Pressed Duck
For a fixed price, the diner gets to choose one dish from Column A and one from Column B. An obvious question now arises: how many different possible fixed-price meals can one have?
Two meals are different if they have either different appetizers, or different main courses, or both. There is a straightforward way to write out all the different possible meals. First write out all the different meals with won ton soup as the appetizer, then all the different meals with spareribs as the appetizer, etc. This appears below, abbreviating with dots (…) to simplify the task.
Won Ton Soup—Sweet and Sour Pork
…
Won Ton Soup—Pressed Duck
This results in seven different meals with won ton soup as the appetizer.
Spareribs—Sweet and Sour Pork
…
Spareribs—Pressed Duck
Likewise, seven more meals, all different from the ones with won ton soup as the appetizer. Similarly, there would be seven different meals with rumaki as the appetizer, seven different meals with egg roll as the appetizer, and seven different meals with dumplings as the appetizer. This makes a total of 7 + 7 + 7 + 7 + 7 = 5 × 7 = 35 different meals.
The number 35 above is obtained by multiplying the number of different possible appetizers (5) by the number of different possible main courses (7). Although the different meals were counted by listing them by appetizer, it would have made no difference to the final tally if we listed them by entrees. Sweet and sour pork was the main course in five different meals, as was lemon chicken, etc. Counting this way gives 5 + 5 + 5 + 5 + 5 + 5 + 5 = 7 × 5 = 35 different meals, just as before.
It is important to realize that the choice of main course is independent of the choice of appetizer. That is, once you have chosen an appetizer, you are perfectly free to choose any of the possible main courses (or vice versa, if you decide to choose the main course first). If the choice of one depends on the choice of the other (for instance, if the restaurant has a rule preventing you from ordering a poultry main course when you have chosen rumaki as an appetizer, or if you are not allowed to order two pork dishes, such as spareribs and sweet and sour pork), the choices are no longer independent, and the counting procedure used here is no longer valid.
The Chinese Restaurant Principle (even professional mathematicians use that phrase, possibly because they often congregate in such establishments because, let’s face it, mathematicians are not rich and Chinese restaurants are generally not expensive) states that, if two choices can be made independently, the number of ways of making both choices is the product of the number of ways of making each choice separately. In the above example, “making both choices” corresponds to selecting a meal. The number of ways of making the appetizer choice is five, the number of ways of making the main course choice is seven, and so the number of ways of making both choices is 7 × 5 = 5 × 7 = 35.
Two Choices
If two choices can be made independently, and there are p ways of making the first choice and q ways of making the second choice, than the number of ways of making both choices is pq.
Several Choices
Since no meal is complete without dessert, let’s see what happens to the Chinese Restaurant Principle when you decide to have dessert as well. Suppose that the menu we were using before offers a complete dinner, including a choice of one appetizer from Column A (five choices), one main course from Column B (seven choices), and one dessert from Column C (three choices). How many different complete dinners are possible?
No lengthy analysis is needed to solve this one. A complete dinner can be viewed as the result of two independent choices: The first choice is the appetizer–main course combination, which you already know can be made in 35 different ways, and the second choice is the dessert, which can be made in three different ways. The Chinese Restaurant Principle thus enables us to conclude that there are 35 × 3 = 105 different complete dinners. Of course, 35 × 3 = 5 × 7 × 3.
As a result, the Chinese Restaurant Principle can be extended to any number of independent choices. If there are several different independent choices to be made, the number of different ways of making all choices is equal to the product of the number of ways of making each choice separately. This result is stated formally in the next section.
p Choices
Suppose that there are p independent choices to make, and the first choice can be made in N1 different ways, the second
in N2 different ways, …, and the pth choice in Np different ways. Then the number of different ways of making all choices is
N 1 × N 2 × … × Np
It is easy to envision the Chinese Restaurant Principle as simply being the number of different p-course meals, where there are N1 different first courses, N2 different second courses, …, and Np different last courses.
When the choices are not independent, you can often compute the total number of available choices by computing the number of possible choices and subtracting the number of excluded choices.
Example 1: Mammoth Tours offers fixed vacation packages from Los Angeles to either Honolulu, Acapulco, the Bahamas, or Puerto Rico. One can travel by boat or plane and can stay at a first-class, deluxe, or economy class hotel. How many different vacation packages are offered, if Mammoth Tours require that if you travel by boat, you must stay at a first-class hotel?
Solution: Since the choices of destination, method of travel, and accommodations are independent, by the Chinese Restaurant Principle there are 4 × 2 × 3 = 24 different vacation packages. However, the number of excluded choices can also be computed by the Chinese Restaurant Principle. There are four excluded destinations and two excluded types of accommodation once you decide to travel by boat, so the number of excluded packages is 4 × 2 = 8. Therefore, the total number of packages offered is 24 − 8 = 16. Alternatively, you could count the number of boat packages and plane packages separately and add them up. ■
APPENDIX 9
PROBABILITY AND EXPECTATION IN “THE WINNING STREAK”
Probability is a mathematical tool that has two primary functions. The first, and most straightforward, is to summarize existing information. The second, which is by far the more interesting, is to make predictions about the future. The crystal ball presented by probability is a little clouded, however, for the future that it uncovers is not a future of individual events but a future of long-term averages. The correct use of these long-term averages allows you to plan more sensibly for the future.