Proving the size of the unions of sets

Question

How should one go about proving the following with induction?

$$ \left| \bigcup_{i \in I} A_i \right| = \sum_{J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right| $$

I is just a finite set, and $A_i$ is just any set within it.

Answer 1

First prove the result for $\# \mathrm I = 2$. Then do the induction by splitting like this $$ \# (\cup_{i = 1}^n \mathrm A_i\cup \mathrm A_{n+1})$$

Answer 2

The formula is slightly incorrect: it’s important to require that the sets $J$ appearing in the summation be non-empty, so the formula should read

$$\left| \bigcup_{i \in I} A_i \right| = \sum_{\varnothing\ne J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right|\;.\tag{1}$$

For a proof by induction on $|I|$, start with the trivial verification that $(1)$ holds when $|I|=1$. Then assume that it holds for $|I|=n$ for some $n\ge 1$, let $\mathscr{A}=\{A_i:i\in I\}$ be a family of $n+1$ sets, and show that $(1)$ holds for $\mathscr{A}$. The natural way to approach this is to fix some $i_0\in I$ and let $I_0=I\setminus\{i_0\}$, so that $|I_0|=n$, and you can apply the induction hypothesis to $\{A_i:i\in I_0\}$. You’ll have

$$\left|\bigcup_{i\in I}A_i\right|=\left|A_{i_0}\cup\bigcup_{i\in I_0}A_i\right|\;,\tag{2}$$

and you know from the induction hypothesis that $$\left| \bigcup_{i \in I_0} A_i \right| = \sum_{\varnothing\ne J \subseteq I_0} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right|\;.$$

If you knew that the $|I|=2$ case of $(1)$ was true, you could apply it to $(2)$ to get

$$\begin{align*} \left|\bigcup_{i\in I}A_i\right|&=|A_{i_0}|+\left| \bigcup_{i \in I_0} A_i \right|-\left|A_{i_0}\cap\bigcup_{i \in I_0} A_i \right|\\\\ &=|A_{i_0}|+\left| \bigcup_{i \in I_0} A_i \right|-\left|\bigcup_{i\in I_0}(A_{i_0}\cap A_i)\right|\;, \end{align*}\tag{3}$$

and you can now apply the induction hypothesis to each of the last two terms, since $|I_0|=n$. You’ll still have a little work to do to combine the sums and see that you really do get $$\sum_{\varnothing\ne J \subseteq I} (-1)^{|J|+1} \left|\bigcap_{i \in J} A_i \right|\;,$$ and of course you still have to prove that $(1)$ holds when $|I|=2$ in order to use that to get $(3)$.

---

It’s entirely possible to prove $(1)$ without using induction. Indeed, one can give a rather shorter proof. I’ve included one below, spoiler-protected; mouse-over to see it.

For each $x\in\bigcup_{i\in I}A_i$ let $I(x)=\{i\in I:x\in A_i\}$. For each $J\subseteq I$ and $x\in\bigcup_{i\in I}A_i$, $x\in\bigcap_{i\in J}A_i$ if and only if $J\subseteq I(x)$. Thus, the contribution of $x$ to the sum on the righthand side of $(1)$ is $+1$ for each non-empty $J\subseteq I(x)$ such that $|J|$ is odd, and $-1$ for each non-empty $J\subseteq I(x)$ such that $|J|$ is even. Let $n(x)=|I(x)|$, the number of sets in the collection $\{A_i:i\in I\}$ containing $x$. It’s well-known (and proved a number of times on this site) that exactly half of the $2^{n(x)}$ subsets of $I(x)$ have even cardinality. The empty set has even cardinality, so if we exclude it, $I(x)$ has $2^{n(x)-1}$ subsets of odd cardinality and $2^{n(x)-1}-1$ subsets of even cardinality. Thus, each $x\in\bigcup_{i\in I}A_i$ contributes a total of $2^{n(x)-1}(1)+\left(2^{n(x)-1}-1\right)(-1)=1$ to the sum in $(1)$, which therefore must be $\left|\bigcup_{i\in I}A_i\right|$.