Set Cardinality Activity

When sets intersect (or don't) in complicated ways, it can be tricky to determine how many elements lie in each part of a Venn Diagram. The simplest (and most useful) equality we will use is one which breaks down a set into its intersecting and non-intersecting areas: \[|A| = |A \setminus B| + |A \cap B|\]

Cardinality on 2 sets

Note that the above is actually a specific case of a more general useful property: any area can be broken into two pieces: one of which is the complement of the other with respect to the full area (in the above, we could have written \(|A| = |A \setminus B| + |A \setminus (A \setminus B)|\)). For an easier example, observe that \[|U| = |A \cup B| + |\overline{A \cup B}| = |A \cup B| + |U \setminus (A \cup B)|\]

Complement of union of 2 sets

There is a major theorem from combinatorics we will use to aid us in our counting, the inclusion-exclusion principle: \[|A \cup B| = |A| + |B| - |A \cap B|\]

Inclusion-exclusion on 2 sets

What this means is that to count how many elements lie in A or B, we sum the number of elements in A and B, and then subtract the number which they have in common (to avoid double-counting these). This principle can be extended to an arbitrary number of intersecting sets. It gets long pretty quickly, so we'll stop at the case of 3 sets (try drawing a picture to convince yourself of the equation's truth: \[|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\] (If you're curious about how it generalizes, it's an alternating sum (alternately \(+\) or \(-\)), where at each step we take all possible intersections of 1, 2, 3, 4, etc... many of the sets)

Finally, consider how we might combine the two preceding properties in a more complex case. With 3 sets A, B, and C, we can decompose A into its intersecting and non-intersecting areas. But to avoid double-counting, we have to apply inclusion-exclusion to the intersecting area: \[|A| = |A \setminus (B \cup C)| + |A \cap B| + |A \cap C| - |A \cap B \cap C|\]

A 3-set example

There are a variety of equalities which can be deduced from the elementary properties of sets: counting requires practice! In the following activity, you may find it helpful to make things concrete in your mind: think of \(U\) as the set of all students enrolled in a particular university, and think of \(A\), \(B\), and \(C\) as the sets of students enrolled in Anthropology, Biology, and Chemistry respectively.