The principle of inclusion and exclusion is a way of reasoning about the membership of sets which overlap.
For example, suppose set A had elements {2, 3, 6, 8, 9} and set B had elements {4, 5, 6, 7, 9}.
Then the principle of exclusion simply says that if we combine both sets together, the combined set will consist of all the elements of A together with all the elements of B, minus the number that exists in both. The reason is simply that we will have counted twice those elements which exist in both, and we therefore need to subtract that number from the total to get the correct count.
So in set A we have five elements and in set B we have another five elements which makes ten in total. However, the elements 6 and 9 occur in both so we subtract two from the total leaving eight. The eight elements that are formed by combining set A with set B are therefore eight in number being {2, 3, 4, 5, 6, 7, 8, 9}.
We the sets do not have any elements in common, the total number of elements in the union of A and B would be the simple sum of the number in each set. The principle of Inclusion-Exclusion simply allows for the overlap and subtracts the double counted elements.
Of course the principle can be extended to more than two sets. For example if all three sets, A, B and C, overlap then the total number of elements is formed by adding the number of elements in each set, then subtracting the overlap of A with B, B with C, and A with C, and then finally adding back in the number of elements in the overlap of all three. An example will make this clearer but drawing out the diagram for yourself on paper with overlapping circles will also help.
A = {2, 3, 7, 9}
B = {3, 9, 12, 15}
C = {7, 12, 14, 16}
The total elements of all three combined is given by
total in A + total in B + total in C
minus (overlap A and B) minus (overlap B and C) minus (overlap A and C)
then add those in the overlap of A and B and C.
That comes to 4 + 4 + 4 = 12
Then subtract 2 – because elements 3 and 9 are common to A and B
Then subtract 1 – because element 12 is common to B and C
Then subtract 1 – because element 7 is common to A and C
Which gives the running total of 8.
Now add on the number of common elements in A and B and C which in this case is zero.
The total number of elements in A combined with B combined with C is therefore eight and these are:
{2, 3, 7, 9, 12, 14, 15, 16}
The principle has applications in number theory, including the study of prime numbers and theorems based on the exclusion principle underpin the use of primes in public key cryptography, the security measures that are implemented in web commerce, banking and more generally across the financial sector.
