Skip main navigation

The inclusion/exclusion principle: counting intersections

The inclusion/exclusion principle: counting intersections
10.7
We know how to count the elements of a union of sets. But how to count the elements of intersection of sets, let us in an example, why it may be useful sometimes to know how to count elements of an intersection. Consider a group of 15 friends and 8 of them do not eat meat, 5 of them do not eat fish, and we know that 2 of them do not eat neither fish or meat. The question is, how many eat both meat and fish? That is the number of friends of the intersection of the complement of M, the event do not eat meat, and the complement of F, do not eat fish.
60.5
Before solving the programme, we need to revise a property of union and intersection of sets. Consider two subsets of a set X. So we will denote by AC or BC the complement of A or B in X. Well, the complement of the union of A with B is the intersection of the complements of A with the complement of B. It’s very simple to understand why. Assume that you are looking for an object in your house, and the object is not in the living room, not in the kitchen. So you have to look elsewhere, in the complement of the union of A with B, the living room and the kitchen.
115.6
And this means that the object is not in the living room and definitely not in the kitchen Let’s see how the proof works. Well, consider an element of X and assume that it belongs to the complement of the union A with B. So it does not belong to the union of A with B. So it does not belong to A, and it does not belong to B. But this means that it belongs to the complement of A, and it belongs to the complement of B. That is the intersection of the two complements.
158.4
The same holds for the complement of a finite union of sets. Assume that all are subsets of a set X. And we denote that the complement of a set, the complement of the set in X– so X minus the set. Well, the complement of the union of this n set is the intersection of the complements in X. And we are now ready to formulate the inclusion-exclusion principle for intersection of sets. More precisely, for intersection of complements, we consider n subset of a set X And we consider the intersection of the complements in X.
202.9
Well, it turns out that the number of elements of this intersection is the number of elements of X minus the alternate sum that appeared in the original inclusion-exclusion principle for unions. So number of elements of x minus sigma 1 plus sigma 2 and so on up to sigma n, which as a sine plus if n is even and minus if n is odd.
239.3
Well, the proof is immediate from the inclusion-exclusion principle. What is the intersection of the complements? Well, as we saw before, it is the complement in X of the union of the set A1, A2, An.
260
Therefore, the elements, the number of elements of the intersection of the complements is the number of elements of X minus the union of the sets A1, An So number of elements of X minus number of elements of the union of these sets and then it is enough to apply the inclusion-exclusion principle to the cardinality of the union of the sets A1, An.
292.6
Just a remark, it seems that you are able to compute cardinality of intersection of complements, is it a restriction? Not at all, because every set, B, can be seen as the complement of its complement. So this is actually a formula for any intersection of sets. Let us solve the problem of fish or meat. Let me recall you that we have a group of 15 friends. 8 of them do not eat meat. 5 do not eat fish. And 2 do not eat neither meat or nor fish. So we are looking for the number of friends that eat both meat and fish.
341.6
That is the number of elements of the intersection of the complements of the event do not eat meat that we call M and do not eat fish that we call F. We use the inclusion-exclusion principle for the intersection of complements. And we get number of elements of X minus the elements of M and the elements of F plus the elements of the intersection. And this gives 15 minus 13 plus 2. That is 4.
379.3
As a further example, with more than two sets, consider a class with 40 students. And we know that 8 of them do magic tricks, 5 of them play piano, and 7 of them play tennis. And, moreover, 3 of them play a play piano and do magic tricks. And 2 of them play piano and tennis. And 4 of them do magic tricks and play tennis. Finally, we also know that there is just one of them that does three things, magic, piano, and tennis. So how many of them do not practise any of these hobbies?
425.3
So we want to compute the number of students that do not belong to the set of those who do magic tricks, those who play piano, and of those who play tennis. So it is the intersection of the complements of the event M, magic tricks, P, piano, and T, tennis. And, of course, we use the inclusion-exclusion principle in the version of the intersection. That is the number of elements of x, which is 40 minus sigma 1 plus sigma 2 minus sigma 3. And thus, we obtain 40 minus 8 plus 5 plus 7 plus the number of intersections 2 by 2, 3 plus 2 plus 4 minus 1. And we get 28 students that do not practise any of these hobbies.

How about if we want to count the number of elements of the intersection of a finite number of sets? Well, there’s a nice formula that comes directly from the Inclusion/Exclusion Principle. Let’s see Carlo explaining it.

You can access the content of the video in the PDF file at the bottom of this step.

This article is from the free online

Combinatorics: Strategies and Methods for Counting

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education