# Statements > [!NOTE] Theorem (Inclusion-Exclusion Principle for Cardinality) > Let $A_{1},A_{2},\dots,A_{n}$ be [[Finite Set|finite sets]]. Then $\begin{align} \left|\bigcup_{i=1}^nA_i\right|&=\sum_{\substack{I\subset \{1,\ldots,n\} \\ I \neq \emptyset}}(-1)^{|I|+1}\left|\bigcap_{i\in I}A_i\right| \\ &=\sum_{j=1}^{n} (-1)^{j+1} \sum_{1\leq i_{1}<i_{2} <\dots i_{j}\leq n} \left|\bigcap_{k=1}^{j}A_k\right|. \end{align}$ # Proofs ###### Proof of Inclusion-Exclusion Principle for Cardinality (Silversmith, MA241 [^1]) Each $x\in A_{1} \cup A_{2} \cup \dots \cup A_{n}$ is counted $\sum_{\substack{I \subseteq J \\ I\neq \emptyset}} (-1)^{\lvert I \rvert+1 }$ times in the right-hand sum, where $J=\left\{i \in\{1, \ldots, n\}: x \in A_i\right\}$Observe that $\sum_{\substack{I \subseteq J \\ I\neq \emptyset}} (-1)^{\lvert I\rvert+1 } = \sum_{k=1}^{|J|} (-1)^{k+1} \binom{|J|}{k} $and the [[Binomial Theorem|binomial theorem]] (or [[Alternating Sum of Binomial Coefficients|alternating sum of binomial coefficients]]) yields that $(-1 + 1)^{\lvert J \rvert} = \sum_{k=0}^{\lvert J \rvert } (-1)^{k+1} \binom{|J|}{k} = 1 + \sum_{k=1}^{|J|} (-1)^{k+1} \binom{|J|}{k}$ so $\sum_{\substack{I \subseteq J \\ I\neq \emptyset}} (-1)^{\lvert I \rvert+1 }=1$. # Bibliography [^1]: [[MA241-10 Combinatorics Notes]]