Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 38 · Cardinality

Counting Finite Sets

Count elements of unions, products and power sets with inclusion-exclusion and the 2^n rule, and verify each formula with runnable Python.

Before we compare infinite sets, we should be completely comfortable with finite ones. For a finite set A, the cardinality |A| is simply the number of elements. In this lesson you will learn the four counting rules that everything else builds on: the sum rule, inclusion-exclusion, the product rule and the power set rule.

Each rule is also a statement about bijections, which is why it will later generalize to infinite cardinals.

Disjoint unions: the sum rule

Two sets are disjoint if they share no elements. For disjoint finite sets,

Text
|A ∪ B| = |A| + |B|

If A = {1, 2, 3} and B = {a, b}, the union has 5 elements. This rule is the definition of addition for cardinal numbers, as you will see in cardinal arithmetic.

Overlaps: inclusion-exclusion

When the sets overlap, adding the sizes counts the shared elements twice. Fix it by subtracting once:

Text
|A ∪ B| = |A| + |B| - |A ∩ B|

For three sets you add the singles, subtract the pairs, and add back the triple:

Text
|A ∪ B ∪ C| = |A| + |B| + |C|
              - |A ∩ B| - |A ∩ C| - |B ∩ C|
              + |A ∩ B ∩ C|

In general the signs alternate: add all single sets, subtract all pairwise intersections, add all triple intersections, and so on.

Python Inclusion-exclusion for any number of sets

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A classic use: how many integers from 1 to 100 are divisible by 2 or by 5? There are 50 multiples of 2, 20 multiples of 5, and 10 multiples of 10, so the answer is 50 + 20 - 10 = 60.

Products: the product rule

The Cartesian product A × B is the set of all ordered pairs (a, b) with a in A and b in B. If A has m elements and B has n, then there are m choices for the first coordinate and n for the second:

Text
|A × B| = |A| · |B|

A menu with 3 starters and 4 mains offers 12 two-course meals. Again, this is the definition of cardinal multiplication.

Power sets: the 2ⁿ rule

The power set P(A) is the set of all subsets of A, including the empty set and A itself. For A = {a, b}:

Text
P(A) = { ∅, {a}, {b}, {a, b} }

That is 4 subsets. In general a set with n elements has

Text
|P(A)| = 2^n

The reason: to build a subset you decide, for each of the n elements, "in" or "out". Two choices, n times, gives 2 · 2 ··· 2 = 2ⁿ. Equivalently, subsets correspond to functions A → {0, 1} that mark each element in or out. These are called characteristic functions, and the correspondence is a bijection.

Python List a power set and check the 2^n rule

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Subsets of a fixed size

How many subsets of an n-element set have exactly k elements? The answer is the binomial coefficient C(n, k) = n! / (k! (n - k)!). Adding over all k must give the total number of subsets, so

Text
C(n,0) + C(n,1) + ... + C(n,n) = 2^n

For n = 3 this is 1 + 3 + 3 + 1 = 8.

Whenever you are asked "how many ways", try to turn the question into "how many elements are in this set", then decompose the set with the sum, product or power set rule.

Why this matters for infinity

Every rule above counts by building a bijection. The product rule, for instance, says there is a bijection between A × B and a list of |A| blocks each containing |B| items. When we move to infinite sets, we cannot count, but we can still ask for bijections. The rules will survive; some of the answers will look strange.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A has 12 elements, B has 9, and A ∩ B has 4. How many elements are in A ∪ B?

    12 + 9 - 4 = 17. Adding without subtracting counts the 4 shared elements twice.
  2. 2. How many subsets does a 6-element set have?

    Each of the 6 elements is in or out, so there are 2^6 = 64 subsets, including the empty set and the whole set.
  3. 3. How many ordered pairs are in A × B if |A| = 5 and |B| = 7?

    The product rule gives 5 · 7 = 35 ordered pairs.
  4. 4. Which sum equals 2^n?

    Grouping all subsets by size gives the binomial coefficients, and together they are all the subsets, so they add to 2^n.

Summary

  • For disjoint finite sets, |A ∪ B| = |A| + |B|; with overlap subtract |A ∩ B| (inclusion-exclusion).
  • |A × B| = |A| · |B|.
  • A set with n elements has 2ⁿ subsets, one for each in/out choice.
  • The binomial coefficients C(n, k) count subsets of size k and add up to 2ⁿ.
  • Each rule is secretly a bijection, which is why it can be extended to infinite cardinals.

Next: Comparing Sizes and the Schröder–Bernstein Theorem