Cardinality of Finite Sets

Proof — Cardinality of a Complement

The sets \(A\) and \(\complement_\mathcal{D} A\) are disjoint by definition (the complement contains exactly those elements of \(\mathcal{D}\) not in \(A\)). Their union is \(\mathcal{D}\). Applying the disjoint union theorem:

\[|\mathcal{D}| \;=\; |A \cup \complement_\mathcal{D} A| \;=\; |A| + |\complement_\mathcal{D} A|\]

Subtracting \(|A|\) from both sides:

\[|\complement_\mathcal{D} A| \;=\; |\mathcal{D}| - |A|\]

as required. \(\blacksquare\)

Proof — Inclusion–Exclusion for Two Sets

We decompose \(A \cup B\) into disjoint pieces. Consider three sets:

• \(A \setminus B\) — elements in \(A\) but not in \(B\)

• \(B \setminus A\) — elements in \(B\) but not in \(A\)

• \(A \cap B\) — elements in both

These three sets are pairwise disjoint, and their union is \(A \cup B\). By repeated application of the disjoint union theorem:

\[|A \cup B| \;=\; |A \setminus B| + |B \setminus A| + |A \cap B| \qquad (\ast)\]

Now observe that \(A\) decomposes into the disjoint union \(A = (A \setminus B) \cup (A \cap B)\). Hence:

\[|A| \;=\; |A \setminus B| + |A \cap B| \quad\Longrightarrow\quad |A \setminus B| \;=\; |A| - |A \cap B|\]

By the same reasoning, \(|B \setminus A| = |B| - |A \cap B|\). Substituting into \((\ast)\):

\[|A \cup B| \;=\; \big(|A| - |A \cap B|\big) + \big(|B| - |A \cap B|\big) + |A \cap B| \;=\; |A| + |B| - |A \cap B|\]

as required. \(\blacksquare\)

Proof — Inclusion–Exclusion in General

We proceed by induction on \(n\), the number of sets.

Base case (\(n = 2\)). The identity \(|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\) was established in the two-set case above.

Inductive step. Fix \(n \geq 2\) and assume the formula holds for any \(n\) finite sets. We must prove it for \(n + 1\) sets \(A_1, A_2, \ldots, A_{n+1}\).

Set \(U = \bigcup_{i=1}^{n} A_i\). Applying the two-set formula to \(U\) and \(A_{n+1}\):

\[\left|\bigcup_{i=1}^{n+1} A_i\right| \;=\; |U \cup A_{n+1}| \;=\; |U| + |A_{n+1}| - |U \cap A_{n+1}| \qquad (\ast)\]

By the inductive hypothesis, \(|U|\) is given by the inclusion–exclusion formula for the \(n\) sets \(A_1, \ldots, A_n\). It remains to compute \(|U \cap A_{n+1}|\). Distributing the intersection over the union (Unit 2, Lesson 3):

\[U \cap A_{n+1} \;=\; \left(\bigcup_{i=1}^{n} A_i\right) \cap A_{n+1} \;=\; \bigcup_{i=1}^{n} (A_i \cap A_{n+1})\]

This is a union of \(n\) sets, namely \(B_i = A_i \cap A_{n+1}\) for \(i = 1, \ldots, n\). Applying the inductive hypothesis again:

\[|U \cap A_{n+1}| \;=\; \sum_{i} |B_i| - \sum_{i < j} |B_i \cap B_j| + \cdots + (-1)^{n+1} |B_1 \cap \cdots \cap B_n|\]

Substituting \(B_i = A_i \cap A_{n+1}\), each term \(B_{i_1} \cap \cdots \cap B_{i_k}\) becomes \(A_{i_1} \cap \cdots \cap A_{i_k} \cap A_{n+1}\) — that is, an intersection of \(k\) of the original sets together with \(A_{n+1}\).

Substituting both expansions (the one for \(|U|\) and the one for \(|U \cap A_{n+1}|\)) into \((\ast)\), and combining like terms, every intersection of any \(k\) of the sets \(A_1, \ldots, A_{n+1}\) appears with the sign \((-1)^{k+1}\):

• Intersections of \(k\) sets not involving \(A_{n+1}\) come from \(|U|\), with sign \((-1)^{k+1}\).

• The single term \(|A_{n+1}|\) appears in \((\ast)\) with sign \(+1 = (-1)^{1+1}\).

• Intersections involving \(A_{n+1}\) and \(k - 1\) of the others come from \(-|U \cap A_{n+1}|\) with sign \(-(-1)^{(k-1)+1} = (-1)^{k+1}\).

Hence every \(k\)-fold intersection of the sets \(A_1, \ldots, A_{n+1}\) appears with sign \((-1)^{k+1}\), which is precisely the inclusion–exclusion formula for \(n + 1\) sets.

By the Principle of Mathematical Induction, the formula holds for every \(n \geq 2\). \(\blacksquare\)