Cardinality: Counting the Elements of a Set

In the previous two articles we defined what a set is and how to operate on it. Now we reach a natural question: how many elements does a set have? This simple question hides an important subtlety: when two sets overlap and we want to count their union, a plain \(n(A) + n(B)\) counts some elements twice. The Inclusion-Exclusion Principle fixes this and is the first combinatorial result of this series.

Cardinality

#

We say a set is finite when its cardinality is a nonnegative integer (\(0, 1, 2, \ldots\)). Saying “natural number” would not be enough: in this series, as we saw in the first article, \(0 \notin \mathbb{N}\), and the empty set, whose cardinality is 0, would be left out. When the enumeration does not end, the set is infinite (like \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{R}\)).

And what about infinite sets: do they all have the same size? The question seems meaningless, but answering it is what led Georg Cantor to create set theory.

It is worth noting that being finite does not mean being easy to count. The set of all people born before the year 2000 is finite, but its exact cardinality is not immediately available. What we want are formulas that compute cardinalities from simpler data.

Sum Rule: Disjoint Sets

#

Two sets are disjoint when they have no element in common, that is, when \(A \cap B = \emptyset\). This concept was introduced in the article Venn Diagrams and Operations; the figure below recaps it visually.

The simplest counting case occurs when the sets are disjoint: with no overlap, we just add.

The disjointness condition is essential. When there is an intersection, we need a more careful formula.

Inclusion-Exclusion Principle

#

When the sets are not disjoint, the plain sum \(n(A) + n(B)\) counts the elements of the intersection twice. The Inclusion-Exclusion Principle (PIE; see the Wikipedia entry) fixes this systematically: it adds the individual sizes, subtracts the pairwise overlaps, adds back the triple ones, alternating signs until each element is counted exactly once.

Two sets

#

The Venn diagram below helps visualize why the intersection is counted twice:

Why subtract the intersection? When adding \(n(A)\) and \(n(B)\), each element that belongs to both sets is counted twice, once when we count \(A\) and once when we count \(B\). Subtracting \(n(A \cap B)\) restores the correct count.

To derive the formula, we decompose the union into three disjoint regions:

By the sum rule:

But also:

Substituting:

Three sets

#

The logic is the same: we add the individual sizes, subtract the pairwise overlaps (which were counted twice), and add back the triple overlap (which was subtracted once more than it should have been). The following figure identifies each of these regions in the Venn diagram:

A direct derivation: apply the two-set case to \((A \cup B) \cup C\), using \(n(A \cup B)\) already worked out and the identity \((A \cup B) \cap C = (A \cap C) \cup (B \cap C)\).

To see why the formula is right, it is worth looking at the eight regions into which three sets divide the universe, numbered as in the article on Venn diagrams:

An element of region 7, which is in all three sets, is added 3 times in \(n(A) + n(B) + n(C)\), subtracted 3 times in the pairwise intersections, and added back 1 time in the triple one: \(3 - 3 + 1 = 1\). An element of regions 4, 5, or 6, which is in two sets, is added 2 times, subtracted 1 time, and does not appear in the triple one: \(2 - 1 = 1\). An element of regions 1, 2, or 3 is added once and appears in no other term, and those of region 8 enter no term at all. Each element of the union is counted exactly once.

Four sets

#

The formula for four sets follows the same pattern, alternating signs:

General formula

#

For \(k\) sets, the general formula of the Inclusion-Exclusion Principle is:

The pattern is clear: we add the individual sizes, subtract the pairwise intersections, add the triple ones, and so on, alternating signs.

Summary Table

#

The formulas developed throughout the article, gathered for quick reference:

In the three-set row, \(\sum n\) abbreviates the sum of the three individual sizes, \(\sum n(\cap_2)\) is the sum of the three pairwise intersections (\(n(A \cap B) + n(A \cap C) + n(B \cap C)\)), and \(n(\cap_3)\) is the triple intersection \(n(A \cap B \cap C)\). The complement and difference rows follow directly from the sum rule: just decompose the larger set into two disjoint parts and isolate the desired term.

Exercises

#

Sieve of Eratosthenes

#

Exercises 1 and 3 and item (v) of 4 follow the same scheme: define a set by divisibility, compute its cardinality with \(\lfloor n/k \rfloor\), use the PIE to gather multiples of different primes without double counting and, when necessary, take the complement to count the elements that satisfy none of the conditions. This pattern, counting by the complement after applying the PIE, is recurrent in combinatorics.

These divisibility exercises apply exactly the same reasoning as the Sieve of Eratosthenes, the oldest known algorithm for finding all prime numbers up to a limit \(n\), proposed by the Greek mathematician Eratosthenes of Cyrene in the 3rd century BC.

The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, …

How it works

#

Given an integer \(n > 1\), Eratosthenes’ method:

1. 1

   Build the list

   Create a list of consecutive integers from 2 to \(n\).
2. 2

   Start with 2

   Let \(p = 2\), the smallest prime.
3. 3

   Mark the multiples of \(p\)

   Mark as composite all multiples of \(p\) starting from \(2p\): \(2p,\ 3p,\ 4p,\ \ldots\). \(p\) itself is not marked.
4. 4

   Move on to the next prime

   Find the smallest unmarked number in the list greater than \(p\). If there is none, stop. Otherwise, \(p\) takes this new value and go back to step 3.
5. 5

   Read off the primes

   When finished, the unmarked numbers are all the primes up to \(n\).

The central idea: every value taken by \(p\) is necessarily prime, because if it were composite, it would already have been marked as a multiple of some smaller prime. Note that, in this basic algorithm, some numbers may be marked more than once: 15, for example, is marked both when processing \(p = 3\) and when processing \(p = 5\).

Optimization: in step 3, it is enough to start at \(p^2\) instead of \(2p\), since every multiple \(k \cdot p\) with \(k < p\) has a prime factor \(q \leq k < p\) by which it was already marked in an earlier stage. With that, it is also enough to run step 3 while \(p^2 \leq n\): upon reaching a \(p\) with \(p^2 > n\), all the numbers still unmarked are necessarily prime.

For example, when processing \(p = 5\), the multiples before \(p^2 = 25\) have already been marked: \(10 = 2 \cdot 5\) was marked when \(p = 2\); \(15 = 3 \cdot 5\), when \(p = 3\); \(20 = 4 \cdot 5 = 2^2 \cdot 5\), again when \(p = 2\). The first multiple of 5 that can still be unmarked is \(25 = 5^2\), hence the start at \(p^2\).

The animation below illustrates the complete algorithm with the optimization applied, for all primes below 121:

Example for \(n = 30\), with primes in bold and composites struck through:

With \(p = 2\): 4, 6, 8, …, 30 are marked. With \(p = 3\): 9, 15, 21, 27 are marked (the even numbers were already marked). With \(p = 5\): 25 is marked. The next prime would be \(p = 7\), but \(7^2 = 49 > 30\): the only multiples of 7 in the range (14, 21, and 28) are already marked by smaller primes (2 and 3). All the numbers still unmarked are prime. Ten remain: the primes from 2 to 29.

Algorithm

#

The pseudocode below directly incorporates the \(p^2\) optimization:

Input:  integer n > 1
Output: all primes from 2 to n

A ← array[2..n] initialized with True

For i from 2 to √n:
    If A[i] is True:
        For j from i² to n with step i:
            A[j] ← False

Return all i with A[i] = True

The flowchart below represents the same algorithm visually:

flowchart TD
    A([Start]) --> B["A ← array[2..n] = True
i ← 2"]
    B --> C{"i ≤ √n ?"}
    C -->|No| G[/"Return all i
with A[i] = True"/]
    G --> H([End])
    C -->|Yes| D{"A[i] = True ?"}
    D -->|No| F["i ← i + 1"]
    F --> C
    D -->|Yes| E["j ← i²"]
    E --> I{"j ≤ n ?"}
    I -->|No| F
    I -->|Yes| J["A[j] ← False"]
    J --> K["j ← j + i"]
    K --> I

In the pseudocode, the same optimization appears from two angles: the inner loop starts at \(i^2\) because earlier multiples have already been marked; the outer loop stops at \(\sqrt{n}\) because, when \(i > \sqrt{n}\), we have \(i^2 > n\), and there is no multiple of \(i\) from \(i^2\) on within the range. The two conditions are equivalent.

Time complexity: \(O(n \log \log n)\). The intuition: for each prime \(p \leq n\), the inner loop performs about \(n/p\) steps. The total cost is proportional to \(n \sum_{p \leq n} 1/p\), and by Mertens' theorem this sum grows like \(\log \log n\), much more slowly than \(\log n\) (the full harmonic series). In practice, for \(n = 10^9\), \(\ln \ln n \approx 3\): the algorithm is almost linear.

Space complexity: the pseudocode above allocates an array of \(n\) positions, hence \(O(n)\), infeasible for \(n = 10^9\). The Segmented Sieve is a variant that reduces the space to \(O(\sqrt{n})\) without increasing the time complexity. The idea in two phases: first, run the classic sieve up to \(\sqrt{n}\) to obtain all the small primes (this array fits in \(O(\sqrt{n})\)); then, divide \([2, n]\) into blocks of size \(\approx \sqrt{n}\) (sized to fit in the processor’s cache memory) and process one block at a time, marking the multiples of the small primes that fall in that range. The resulting pseudocode is longer than the one above, but the principle is the same.

Additions only: the sieve advances by counting in increments of \(p\), with no divisions or divisibility tests. This is what distinguishes it from trial division, which tests each candidate individually, and is the basis of its efficiency.

The connection with the PIE

#

Why does the sieve work mathematically? Every composite number \(m \leq n\) has at least one prime factor \(p \leq \sqrt{m} \leq \sqrt{n}\), so every composite falls in some \(A_p\) and is eliminated. What remains are the primes.

Back to the example with \(n = 30\): \(21 = 3 \times 7\) is composite and \(\sqrt{21} \approx 4.6\), so it has a prime factor \(\leq 4.6\) (indeed, 3) and was eliminated when \(p = 3\). Meanwhile \(25 = 5^2\) has \(\sqrt{25} = 5\), with prime factor \(5 \leq 5\), eliminated when \(p = 5\). No composite escapes: there is always a prime factor small enough to have marked it before the outer loop ends.

Eliminating the multiples of a prime \(p\) amounts to defining:

In words: \(A_p\) is the set of all integers from 1 to \(n\) that the sieve would mark when processing the prime \(p\). For example, for \(p = 3\) and \(n = 30\), we have \(A_3 = \{3, 6, 9, 12, \ldots, 30\}\). Each step of the algorithm does nothing more than build this set and strike out its elements.

The survivors of the sieve are the integers from 1 to \(n\) that belong to no \(A_p\), that is, the complement of the union of all these sets. Calling \(p_1, \ldots, p_r\) the primes up to \(\sqrt{n}\), the count of the survivors is:

(The number 1 also survives, since it is not divisible by any prime; \(p_1, \ldots, p_r\) themselves are excluded, since each \(p_i\) belongs to its own \(A_{p_i}\). The sieve starts at 2, which takes care of both in practice.)

To compute \(n(A_{p_1} \cup \cdots \cup A_{p_r})\), we apply the PIE. This requires knowing the cardinalities of the individual sets and of the intersections. The key is that the intersection of two sets of multiples is itself a set of multiples: \(A_p \cap A_q\) contains exactly the integers divisible by \(p\) and by \(q\), that is, the multiples of the product \(pq\) (which is the lcm of two distinct primes). Therefore:

• The cardinality of \(A_p\) is the number of multiples of \(p\) up to \(n\), given by the integer part \(\lfloor n/p \rfloor\).
• The cardinality of the intersection \(A_p \cap A_q\) is the number of multiples of \(pq\) up to \(n\), given by \(\lfloor n/(pq) \rfloor\).

You computed exactly this in item (v) of Exercise 4: with \(A\) = even numbers, \(B\) = multiples of 3, and \(E\) = multiples of 5 in the range \((1, 60)\), you applied the PIE to \(A_2 \cup A_3 \cup A_5\) and got 43. The exercise stopped there, but the sieve takes one more step: it takes the complement, \(58 - 43 = 15\), to count the survivors (the numbers from 2 to 59 not divisible by 2, 3, or 5, which include all primes greater than 5 in that range). The Sieve of Eratosthenes is this reasoning generalized to any \(n\) and any set of primes.

The Sieve of Eratosthenes is an algorithm: it iteratively marks multiples and counts what remains. What we did in this section was different: we expressed the same result as a closed-form formula via the PIE, directly computing \(n - n(A_{p_1} \cup \cdots \cup A_{p_r})\) without simulating the process step by step. This mathematical formalization is historically known as the Legendre sieve, named in honor of Adrien-Marie Legendre, who in the 19th century made explicit the PIE structure behind the sieve. The central formula of the method is called Legendre’s identity, and it generalizes the expression above using the Möbius function \(\mu(d)\). This function encodes exactly the alternating sign pattern of the PIE: for a number \(d\) that is a product of \(k\) distinct primes, \(\mu(d) = (-1)^k\); if \(d\) contains some squared factor, \(\mu(d) = 0\). With this, the whole PIE expansion (add the individual ones, subtract the pairs, add the triples, and so on) condenses into a single sum, which already gives the count of the survivors:

where \(P = p_1 \cdot p_2 \cdots p_r\) is the product of the primes up to \(\sqrt{n}\) and the sum runs over all divisors \(d\) of \(P\), including \(d = 1\). It is this term that plays the role of the initial \(n\): \(\mu(1) \lfloor n/1 \rfloor = n\). The prime divisors (\(\mu = -1\)) subtract the individual sets, the products of two primes (\(\mu = +1\)) add back the pairwise intersections, and so on. It is the same arithmetic as the PIE, rewritten compactly.

For \(n = 30\), the primes up to \(\sqrt{30}\) are 2, 3, and 5, and \(P = 30\). The eight divisors of 30 give:

These are exactly the eight survivors \(\{1, 7, 11, 13, 17, 19, 23, 29\}\): 1 is in, and the primes 2, 3, and 5 are out, as explained above.

The figure below puts this computation on the numbers themselves. Each integer from 1 to 30 gets a mark for each set \(A_2\), \(A_3\), \(A_5\) it belongs to, and those left with no mark are the survivors. Counting the marks of each color gives \(15\), \(10\), and \(6\). The pairwise intersections add up to \(5 + 3 + 2 = 10\): they are the seven cells with two marks (6, 10, 12, 15, 18, 20, and 24) plus 30, which has three marks and is therefore in all three pairwise intersections, and is, on its own, the triple one.

Next steps

#

With cardinality and the Inclusion-Exclusion Principle, we close the theoretical block of this stage of the series: defining, representing, operating on, and counting sets without double counting.

In the next article of the series, the same language appears in code: we will see how membership, inclusion, union, intersection, and cardinality translate directly into Python using set and frozenset, connecting theory to practice.

See you there!