The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: SAT-I, GMAT, AMC-8, AMC-10, Math Kangaroo 5-6, Math Kangaroo 7-8, Math Kangaroo 9-10.

Cardinality of a Finite Set: the number of elements that belong to the set.

Notation: the cardinality of a set is denoted by vertical bars, similarly to the notation for absolute values.

Example: the cardinality of the set A of chemical elements with atomic number smaller than 4:

equation

Definition: the set without any elements is the empty set. It is denoted by the Greek capital letter phi.

The cardinality of the empty set is 0.

equation

Of course, some sets have an infinite number of elements. However, we will only discuss sets that have a finite number of elements.

The inclusion-exclusion principle computes the number of elements (cardinality) of the union of two sets.

Two sets may be disjoint or not. If they are disjoint then the cardinality of their union is simply the sum of the cardinalities of the two sets:

equation

figure

If the two sets have a non-empty intersection (are not disjoint):

figure

The principle of inclusion-exclusion says that the cardinality of the union is the sum of the cardinalities of the two sets minus the cardinality of their intersection:

equation

This is because we have to count all the elements in both sets only once. The elements that belong to the intersection should not be counted twice.

Example:

Of the 17 meals that Flax-n-Soy can sell, 13 come with flax and 15 come with soy. If he chooses a meal at random, what is the probability that Healthman will receive a meal containing both flax and soy?

Apply the principle of inclusion-exclusion to find the number of meals that come with both flax and soy, denoted with x:

equation

Solve for x:

equation

The probability is the ratio between the number of favorable events and the total number of events:

equation

This method can be generalized to any number of sets and all sorts of operations with sets.

Proof of the inclusion-exclusion principle:

Take the set differences:

equation

and

equation

According to the principle for disjoint sets, the cardinalities satisfy:

equation

equation

and allow us to compute the cardinality of the union as:

equation

equation

equation