Venn diagrams and counting a union
You know how many are in one group, how many are in another, and how many are in both. How many are in at least one, and how many in neither?
Where you are 15 in Sets
When you reach for it
A question asks how many things are in one group or another: students who take art or music, numbers divisible by 6 or by 15, households with a dog or a cat. Often it asks the opposite too, how many are in neither. The sizes of the two groups are known, and so is the size of their overlap, or enough to find it.
Adding the two sizes is the natural first move, and it is right only when the groups share nothing. The cardinality of a union counts each element once, while \lvert A\rvert + \lvert B\rvert counts every element of the overlap twice: once as a member of A and once as a member of B. This lesson removes that second count, and shows how a Venn diagram keeps track of all four regions at once.
The procedure
Throughout, A and B are finite sets inside a universal set U, and \lvert A\rvert is the number of elements of A.
Four regions. Two overlapping loops in a Venn diagram cut U into four regions: in A only, in both, in B only, in neither. Every element of U lies in exactly one of them, so the four region counts add up to \lvert U\rvert. The regions are linked to the given totals:
| Region | Its size |
|---|---|
| In both, A \cap B | \lvert A \cap B\rvert |
| In A only, A \cap B^{c} | \lvert A\rvert - \lvert A \cap B\rvert |
| In B only, B \cap A^{c} | \lvert B\rvert - \lvert A \cap B\rvert |
| In neither, (A \cup B)^{c} | \lvert U\rvert - \lvert A \cup B\rvert |
The second row holds because A is split into two pieces with nothing in common, the part inside B and the part outside it, and pieces with nothing in common add.
Counting the union. The union is the first three regions together. Adding \lvert A\rvert and \lvert B\rvert counts an element of A only once, an element of B only once, and an element of the overlap twice.
Subtracting \lvert A \cap B\rvert takes one count away from each element of the overlap and from nothing else, which leaves every element of the union counted exactly once:
This is the inclusion-exclusion count for two sets: include both sets, then exclude what was included twice. The same equation can be read for any one of its four numbers once the other three are known, so it also finds an overlap from a union, or a set’s size from the other three.
Disjoint sets. A and B are disjoint when they share no element, that is, when A \cap B = \varnothing. Then \lvert A \cap B\rvert = 0 and the sizes simply add:
This is the addition rule from Cardinality of a finite set, now seen as the special case with an empty overlap.
Counting neither. Everything in U is either in the union or outside it, so
Taking away both sets from U takes the overlap away twice, so it is added back once.
Filling in a Venn diagram. When totals are given, the overlap is the number to place first, because each of the other regions is a total with the overlap taken off. Once all four regions hold numbers, every question about the two sets (“A but not B”, “exactly one”, “neither”) is a sum of regions. Adding all four regions and comparing with \lvert U\rvert checks the work.
Worked examples
Art and music
A club has 120 students. 70 take art, 55 take music and 30 take both. How many take at least one of the two? How many take neither? Fill in a Venn diagram.
SolutionLet A be the art students and M the music students. “At least one” is “in A or in M”, the union. The 30 students who take both are among the 70 and also among the 55, so 70 + 55 counts each of them twice. Subtract the overlap once:
So 95 students take at least one. The rest of the club takes neither:
For the diagram, the overlap holds 30. Art only holds 70 - 30 = 40, since 30 of the 70 art students are already in the overlap, and music only holds 55 - 30 = 25. Neither holds 25.
Check. 40 + 30 + 25 + 25 = 120, the whole club.
Filling the regions from the totals
A survey of 90 households finds that 52 have a dog, 41 have a cat and 17 have neither. How many have both? Fill in all four regions of a Venn diagram, and say how many have exactly one of the two pets.
SolutionThis time the overlap is the unknown. Let D be the households with a dog and C those with a cat. Every household is in the union or in neither, so
The inclusion-exclusion count holds for these sets as for any two, so put in the three known numbers and solve for the fourth:
which gives \lvert D \cap C\rvert = 93 - 73 = 20. Twenty households have both.
Now that the overlap is known, the other regions follow from the totals. Dog only is 52 - 20 = 32 and cat only is 41 - 20 = 21, and neither was given as 17.
Exactly one pet means dog only or cat only, two regions with nothing in common, so 32 + 21 = 53 households.
Check. 32 + 20 + 21 + 17 = 90, every household once.
When the sizes simply add
Among the whole numbers from 1 to 60, how many (a) end in the digit 3 or are multiples of 5, (b) end in the digit 5 or are multiples of 3?
Solution(a) The numbers ending in 3 are 3, 13, 23, 33, 43, 53, six of them. The multiples of 5 are 5, 10, \dots, 60, which is \tfrac{60}{5} = 12 numbers. A multiple of 5 ends in 0 or 5, never in 3, so the two sets are disjoint and the sizes add:
(b) The numbers ending in 5 are 5, 15, 25, 35, 45, 55, six again, and the multiples of 3 are 3, 6, \dots, 60, which is \tfrac{60}{3} = 20. These sets do overlap: of the six numbers ending in 5, the multiples of 3 are 15 and 45 (digit sums 6 and 9; the others have digit sums 5, 7, 8 and 10). So
Same sizes for the first set, a different answer: before adding, decide whether the sets can share an element.
Counting multiples
How many whole numbers from 1 to 500 are divisible by 6 or by 15? How many are divisible by neither?
SolutionThe multiples of 6 up to 500 are 6 \cdot 1, 6 \cdot 2, \dots, 6 \cdot 83, since 6 \cdot 83 = 498 and 6 \cdot 84 = 504 is too big. So there are 83 of them, the whole-number part of \tfrac{500}{6}. In the same way there are 33 multiples of 15, since 15 \cdot 33 = 495.
The overlap is the numbers divisible by both 6 and 15. A number divisible by both is a common multiple of 6 and 15, and every common multiple is a multiple of the least one, 30. It is not 6 \cdot 15 = 90: the number 30 itself is divisible by 6 and by 15 but not by 90. The two numbers share the factor 3, which is why the least common multiple is smaller than the product. Up to 500 there are 16 multiples of 30, since 30 \cdot 16 = 480 and 30 \cdot 17 = 510. So
numbers are divisible by 6 or by 15, and 500 - 100 = 400 are divisible by neither.
Check. From 1 to 30 the multiples of 6 or 15 are 6, 12, 15, 18, 24, 30, six numbers, and the count gives 5 + 2 - 1 = 6.
How large can the overlap be?
A class has 32 students. 21 play soccer and 18 play chess. Nobody says how many do both. What are the smallest and largest numbers of students who could play both?
SolutionLet S and C be the two sets. Rearranging the inclusion-exclusion count,
so the overlap is large when the union is small and small when the union is large.
The union holds at most every student, 32, so the overlap is at least 39 - 32 = 7. That smallest overlap happens exactly when nobody plays neither: 14 soccer only, 7 both, 11 chess only, 14 + 7 + 11 = 32.
The overlap is a subset of C, so it holds at most 18 students. That happens when every chess player also plays soccer: then S \cup C = S, the union is 21, and 39 - 21 = 18.
Every number in between happens too. So the number who play both is at least 7 and at most 18. Without the overlap the two totals do not fix the union; they only fence it in, between 21 and 32.
Squares or cubes
How many whole numbers from 1 to 2000 are perfect squares or perfect cubes?
SolutionA perfect square up to 2000 is k^2 for k = 1, 2, \dots, 44, since 44^2 = 1936 and 45^2 = 2025. So there are 44 squares. A perfect cube up to 2000 is k^3 for k = 1, \dots, 12, since 12^3 = 1728 and 13^3 = 2197: 12 cubes.
A number that is both is a sixth power. If n is a square and a cube, each prime appears in n a number of times divisible by 2 and by 3, so by 6; and a sixth power m^6 is both (m^3)^2 and (m^2)^3. The sixth powers up to 2000 are 1, 64 and 729, since 4^6 = 4096 is too big. So
numbers from 1 to 2000 are squares or cubes, and the other 1947 are neither.
Boundaries
Finite sets only. The count adds and subtracts numbers of elements. An infinite set, such as all the even integers, has no such number (Infinite sets).
The overlap has to be known. \lvert A\rvert and \lvert B\rvert alone do not decide \lvert A \cup B\rvert. Example 5 shows the union can be anything from the larger of the two sizes up to their sum (or up to \lvert U\rvert, if that is smaller). The plain sum is right only for disjoint sets.
“Or” includes both. \lvert A \cup B\rvert counts the overlap once. “Exactly one of the two” is a different set, the union with the overlap removed, and its size is \lvert A\rvert + \lvert B\rvert - 2\lvert A \cap B\rvert.
“Neither” needs a universal set. The union can be counted with no U in sight, but the number in neither is \lvert U\rvert - \lvert A \cup B\rvert and means nothing until U is stated.
The numbers must be consistent. An overlap can be no larger than either set, and a union no larger than U. A survey reporting otherwise contains an error (Exercise 20).
Two sets, not three. With three sets, adding the three sizes and subtracting the three pairwise overlaps is still wrong: an element in all three is added three times and subtracted three times, so it is not counted at all. It has to be added back, which is inclusion-exclusion for three or more sets.
Where this goes next
With three or more sets the same idea, add and then correct for what was counted too often, runs on through inclusion-exclusion for three or more sets, which also counts the arrangements that leave nothing in its place. In probability an event is a set of outcomes, and dividing every count by the number of equally likely outcomes turns this lesson’s count into the general addition rule; the disjoint case becomes mutually exclusive events, whose probabilities simply add, and both feed Compound events. Splitting a set into disjoint pieces whose sizes add is also the idea behind a partition, met in Relations, equivalence classes and partitions. A Venn diagram of two sets holds the same four numbers as a two-way table, whose rows are “in A” and “not in A” and whose columns are “in B” and “not in B”.
Exercises
Using the count
- \lvert A\rvert = 14, \lvert B\rvert = 9 and \lvert A \cap B\rvert = 5. Find \lvert A \cup B\rvert.
- \lvert P\rvert = 23, \lvert Q\rvert = 31 and \lvert P \cup Q\rvert = 40. Find \lvert P \cap Q\rvert.
- \lvert A \cup B\rvert = 50, \lvert A\rvert = 32 and \lvert A \cap B\rvert = 12. Find \lvert B\rvert.
- C and D are disjoint, \lvert C\rvert = 17 and \lvert D\rvert = 26. Find \lvert C \cup D\rvert. If both sets lie in a universal set of 60 elements, how many elements are in neither?
- Let A be the prime numbers less than 15 and B the odd numbers from 1 to 15. Find \lvert A\rvert, \lvert B\rvert and \lvert A \cap B\rvert, then \lvert A \cup B\rvert, and check the last by listing A \cup B.
Venn diagrams from totals
- A sports center has 200 members. 112 swim, 75 use the gym and 40 do both. Fill in a Venn diagram, and find how many do (a) at least one, (b) neither, (c) exactly one.
- Of 75 people at a meeting, 38 speak French, 29 speak German and 21 speak neither. How many speak both? Fill in all four regions.
- At a library, 34 readers borrowed only fiction, 12 borrowed fiction and non-fiction, 19 borrowed only non-fiction and 15 borrowed neither. How many readers were there? How many borrowed fiction, and how many non-fiction?
- In a group of 45 hikers, 30 brought a map, 8 brought both a map and a compass and 10 brought neither. How many brought a compass?
- A box holds 48 tiles, and every tile is red or square or both. 30 are red and 25 are square. How many red square tiles are there, and how many red tiles are not square?
Counting numbers
- How many whole numbers from 1 to 200 are divisible by 4 or by 10?
- How many whole numbers from 1 to 300 are divisible by 7 or by 11? How many by neither?
- How many whole numbers from 1 to 1000 are divisible by neither 9 nor 12?
- How many three-digit numbers are divisible by 5 or by 9?
- How many two-digit numbers are perfect squares or perfect cubes?
- How many whole numbers from 1 to 100 are neither even nor multiples of 3?
How big the overlap can be
- In a universal set of 50 elements, \lvert A\rvert = 40 and \lvert B\rvert = 25. Find the smallest and largest possible values of \lvert A \cap B\rvert, and of \lvert A \cup B\rvert.
- Of 58 students, 41 have a phone and 30 have a bus pass. At least how many have both? At most how many?
Reasoning
- Explain why \lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert holds exactly when A and B are disjoint.
- Ferran reports a survey of 50 people: 30 like tea, 28 like coffee and 5 like both. Show that the numbers cannot all be right. What is the smallest number who like both that would fit the other two totals?
- Explain, using the regions of a Venn diagram, why the number of elements in neither set is \lvert U\rvert - \lvert A\rvert - \lvert B\rvert + \lvert A \cap B\rvert, and in particular why the overlap is added rather than subtracted.
- Someone counts the whole numbers from 1 to 100 divisible by both 4 and 6 as the whole-number part of \tfrac{100}{24}. Explain why that is wrong, give the right count, and use it to count the numbers from 1 to 100 divisible by 4 or by 6.
Answers
- 18. 14 + 9 - 5 = 18.
- 14. 40 = 23 + 31 - \lvert P \cap Q\rvert, so \lvert P \cap Q\rvert = 54 - 40 = 14.
- 30. 50 = 32 + \lvert B\rvert - 12, so \lvert B\rvert = 50 - 32 + 12 = 30.
- \lvert C \cup D\rvert = 43, since the overlap is empty: 17 + 26 = 43. In neither: 60 - 43 = 17.
- A = \{2, 3, 5, 7, 11, 13\} and B = \{1, 3, 5, 7, 9, 11, 13, 15\}, so \lvert A\rvert = 6, \lvert B\rvert = 8 and A \cap B = \{3, 5, 7, 11, 13\} has 5 elements. Then \lvert A \cup B\rvert = 6 + 8 - 5 = 9, and indeed A \cup B = \{1, 2, 3, 5, 7, 9, 11, 13, 15\}.
- Regions: swim only 112 - 40 = 72, both 40, gym only 75 - 40 = 35, neither 53. (a) 112 + 75 - 40 = 147. (b) 200 - 147 = 53. (c) 72 + 35 = 107.
- 13 speak both. The union is 75 - 21 = 54, so the overlap is 38 + 29 - 54 = 13. Regions: French only 25, both 13, German only 16, neither 21; 25 + 13 + 16 + 21 = 75.
- 80 readers: 34 + 12 + 19 + 15 = 80. Fiction 34 + 12 = 46, non-fiction 19 + 12 = 31. Check: 46 + 31 - 12 = 65 = 80 - 15.
- 13. The union is 45 - 10 = 35, and 35 = 30 + \lvert K\rvert - 8 for the set K of compass carriers, so \lvert K\rvert = 13 (of them 5 brought only a compass).
- 7 red squares and 23 red tiles that are not square. Every tile is in the union, so 48 = 30 + 25 - \lvert R \cap S\rvert and \lvert R \cap S\rvert = 7; then 30 - 7 = 23.
- 60. There are 50 multiples of 4 and 20 of 10. Both means a multiple of 20, the least common multiple, and there are 10: 50 + 20 - 10 = 60.
- 66 divisible by 7 or 11, and 234 by neither. There are 42 multiples of 7 (7 \cdot 42 = 294), 27 of 11 (11 \cdot 27 = 297) and 3 of 77: 42 + 27 - 3 = 66, and 300 - 66 = 234.
- 833. There are 111 multiples of 9 (9 \cdot 111 = 999), 83 of 12 (12 \cdot 83 = 996) and 27 of their least common multiple 36 (36 \cdot 27 = 972). So 111 + 83 - 27 = 167 are divisible by 9 or 12, and 1000 - 167 = 833 by neither.
- 260. The three-digit multiples of 5 run from 100 to 995: \tfrac{995 - 100}{5} + 1 = 180. Of 9, from 108 to 999: \tfrac{999 - 108}{9} + 1 = 100. Of 45, from 135 to 990: \tfrac{990 - 135}{45} + 1 = 20. So 180 + 100 - 20 = 260.
- 7. Squares 16, 25, 36, 49, 64, 81 make 6, cubes 27, 64 make 2, and 64 is both: 6 + 2 - 1 = 7.
- 33. There are 50 even numbers and 33 multiples of 3; both means a multiple of 6, and there are 16. So 50 + 33 - 16 = 67 are even or multiples of 3, and 100 - 67 = 33 are neither.
- \lvert A \cap B\rvert is at least 15 and at most 25; \lvert A \cup B\rvert is at least 40 and at most 50. The union is at most 50, so the overlap is at least 65 - 50 = 15. The overlap sits inside B, so it is at most 25, reached when B \subseteq A and the union is A, with 40 elements.
- At least 13, at most 30. The union is at most 58, so both is at least 41 + 30 - 58 = 13; both is a part of the 30 bus-pass holders, and all 30 is possible if every one of them has a phone.
- The count says \lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert - \lvert A \cap B\rvert, so the plain sum is right exactly when \lvert A \cap B\rvert = 0. A finite set has 0 elements only when it is empty, so this happens exactly when A \cap B = \varnothing, which is what disjoint means.
- The union would be 30 + 28 - 5 = 53 people, more than the 50 asked. The overlap must be at least 30 + 28 - 50 = 8, which would make everyone like tea or coffee.
- Taking \lvert A\rvert and then \lvert B\rvert away from \lvert U\rvert removes each element of A only once, each element of B only once, and each element of the overlap twice, once with A and once with B. Only the neither region is left untouched, but the overlap has been removed one time too many, so adding \lvert A \cap B\rvert back once corrects it. The result equals \lvert U\rvert - \lvert A \cup B\rvert, the neither region.
- Divisible by both 4 and 6 means a common multiple, and the least common multiple is 12, not 24, because 4 and 6 share the factor 2. The right count is 8 (12 \cdot 8 = 96); the whole-number part of \tfrac{100}{24} is 4, which misses 12, 36, 60 and 84. Then there are 25 multiples of 4 and 16 of 6, so 25 + 16 - 8 = 33 numbers are divisible by 4 or by 6.