In a survey of 120 people, it is found that 78 like Marvel and 60 like DC. Find the number of people that like both.

Let the number of people that like Marvel = n(M) = 78The number of people that like DC = n(D) = 60The total number of people = n(M∪D) = 120We have to find the number of people that like both,i.e., n(M∩D)n(M∪D) = n(M) + n(D) - n(M∩D)Therefore, n(M∩D)= 78+60-120 = 18

Table of contents

Introduction

Inclusion-Exclusion Principle

2.1.

In case of two sets

2.2.

In case of three sets:

The Theorem

3.1.

Properties

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Inclusion-Exclusion Principle

Author Rushali Patnaik

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

The students are asked to choose Mathematics or Biology as their first optional subject in a class. Some students choose Mathematics, some choose Biology, and some choose both. How can we find out the number of students(n) in that class?

Let n1 = the number of students taking Mathematics,

n2 = the number of students taking Biology

and n3 = the number of students taking both

If asked how many students have taken either Mathematics or Biology, we add the number of students taking both the subjects, i.e., n = n1 + n2. By doing so, we have counted the students who have taken both subjects twice. So we need to subtract them once. Hence the solution is n = n1 + n2 -n3. This is nothing but the Inclusion-Exclusion principle of set theory.

Inclusion-Exclusion Principle

In case of two sets

In many problems, we must include contributions of more than one term in our answer. This results in the inclusion of the same term more than once; hence we use the inclusion-exclusion principle. Clearly, in set theory, the union of two sets A and B can be represented as :

|A ∪ B| = |A| + |B| − |A ∩ B| …….(i)

The Venn Diagram above provides a transparent understanding and proves eq(i). The event A ∩ B has been double-counted while adding the elements of A and B. Thus, this double-counting is corrected by subtracting the number of elements in A ∩ B. The co-related equation in probability theory is given by-

P(A ∪ B) = P(A) + P(B) − P(A ∩ B) .......(ii)

In case of three sets:

The cardinality of three finite sets, A, B, and C, i.e., |A ∪ B ∪ C|, we once again apply our provisional(incorrect) guess that it may be |𝐴|+|𝐵|+|𝐶|. That way, we tend to count some elements once and others more than once. In the Venn Diagram above, the cardinalities of |𝐴|, |𝐵| and |𝐶|(dark blue areas) are counted once, those of |𝐴 ∩ 𝐵|, |𝐴 ∩ 𝐶| and |𝐵 ∩ 𝐶|(light-blue areas) twice, and that of |𝐴 ∩ 𝐵 ∩ 𝐶|(centre region) is counted thrice. To fix this problem, we subtract the cardinalities of all the intersections of two sets, which ensures that the light blue areas are counted once. However, the formula is still wrong for the centre elements, counted three times and then un-counted three times for a net-zero time. Therefore, the cardinality of the centre needs to be added.

So, the final formula is:

|A∪B∪C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|...(iii)

The correlated equation in probability theory is given by:

P(A∪B∪C) = P(A)+P(B)+P(C)−P(A∩B)−P(A∩C)−P(B∩C)+P(A∩B∩C)...(iv)

The inclusion-exclusion principle is the generalisation of equations (ii) and (iv) to an arbitrary number of sets.

The Theorem

The Inclusion-Exclusion theorem says that for n finite sets A1, A2 ..., An, the cardinality of the union is the sum of individual cardinalities, minus all the cardinalities two set intersections, plus the cardinalities of all three set intersections, minus the cardinalities of four set intersections....plus (-1)i+1 cardinalities of all the i-set instructions. The equation for the same is given by eq(v):

The co-related equation in probability theory is given by equation(vi):

Properties

1. The Inclusion-Exclusion property calculates the cardinality(total number of elements) which satisfies at least one of the several properties.
2. It ensures that double-counting is prevented.

FAQs

State Inclusion-Exclusion Principle.
The Inclusion-Exclusion theorem says that for n finite sets A1, A2 ..., An, the cardinality of the union is the sum of individual cardinalities, minus all the cardinalities two set intersections, plus the cardinalities of all three set intersections, minus the cardinalities of four set intersections....plus (-1)ⁱ⁺¹ cardinalities of all the i-set instructions.
In a survey of 120 people, it is found that 78 like Marvel and 60 like DC. Find the number of people that like both.
Let the number of people that like Marvel = n(M) = 78
The number of people that like DC = n(D) = 60
The total number of people = n(M∪D) = 120
We have to find the number of people that like both,i.e., n(M∩D)
n(M∪D) = n(M) + n(D) - n(M∩D)
Therefore, n(M∩D)= 78+60-120 = 18
State the properties of Inclusion-Exclusion theorem.
1. The Inclusion-Exclusion property calculates the cardinality(total number of elements) which satisfies at least one of the several properties.
2. It ensures that double-counting is prevented.

Key Takeaways

In this article, we have extensively discussed the cardinalities of union of two sets, three sets, Inclusion-Exclusion principle, deriving equations and some questions related to this topic. We hope that this blog has helped you enhance your knowledge and if you wish to learn more, check out our playlist Basic Mathematics. You can also go through our Library. Do upvote our blog to help other ninjas grow.

Happy Learning!