Proof of The Principle of Inclusion and Exclusion

Write $U=\bigcup_{i=1}^{m}A_{i}$ and $Y=X\setminus U$. Throughout, $U$, $Y$, the sets $A_{S}$ and the sets $T(x)$ introduced below are subsets of the finite sets $X$ and $[m]$, hence finite (Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv)); $\mathcal{P}([m])$ is finite by Counting Subsets (ii); and $S\mapsto\#A_{S}$ and $S\mapsto\#S$ are maps on $\mathcal{P}([m])$ (The Maps i ↦ #C(i) and S ↦ #S (i), The Maps i ↦ #C(i) and S ↦ #S (ii)); and cardinalities are read in $\mathbb{R}$, where their sums keep their values (The Image of the Natural Numbers with Zero in a Commutative Ring Respects Zero, One, Sums, Products, Differences, Powers, and Finite Sums and Products (ii)).

Step 1 (which sets $A_{S}$ contain a given element). For $x\in X$ let $T(x)=\{i\in[m]:x\in A_{i}\}$. We claim that for every $S\subseteq[m]$,

$$x\in A_{S}\iff S\subseteq T(x).$$

For $S=\emptyset$ both sides hold, because $A_{\emptyset}=X$. For nonempty $S$ both sides say that $x\in A_{i}$ for every $i\in S$. Moreover, by the definition of the union, $T(x)=\emptyset$ if and only if $x$ lies in no $A_{i}$, that is, if and only if $x\in Y$.

Step 2 (each term as a sum over $X$). For $S\in\mathcal{P}([m])$ and $x\in X$ put

$$e(S,x)=\begin{cases}(-1)^{\#S}, & x\in A_{S},\\ 0, & x\notin A_{S}.\end{cases}$$

For fixed $S$ the map $e(S,\cdot)$ vanishes off $A_{S}$ and is constant on $A_{S}$, so by Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (iv) and Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (v)

$$\sum_{x\in X}e(S,x)=\sum_{x\in A_{S}}(-1)^{\#S}=(-1)^{\#S}\,\#A_{S}.$$

Step 3 (exchanging the order of summation). Summing Step 2 over $S$ and exchanging the two sums over $\mathcal{P}([m])\times X$ by Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (iv), applied to the addition of $\mathbb{R}$, we get

$$\sum_{S\in\mathcal{P}([m])}(-1)^{\#S}\,\#A_{S}=\sum_{S\in\mathcal{P}([m])}\ \sum_{x\in X}e(S,x)=\sum_{x\in X}\ \sum_{S\in\mathcal{P}([m])}e(S,x).$$

Fix $x\in X$. By Step 1, $e(S,x)=(-1)^{\#S}$ for $S\in\mathcal{P}(T(x))$ and $e(S,x)=0$ for the other $S\in\mathcal{P}([m])$; since $\mathcal{P}(T(x))\subseteq\mathcal{P}([m])$, Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (iv) gives

$$\sum_{S\in\mathcal{P}([m])}e(S,x)=\sum_{S\in\mathcal{P}(T(x))}(-1)^{\#S}.$$

Step 4 (the contribution of one element). Let $t=\#T(x)$. If $t=0$, then $T(x)=\emptyset$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii), its only subset is $\emptyset$, and the sum has the single term $(-1)^{\#\emptyset}=(-1)^{0}=1$ (Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii), Powers with Exponents in the Natural Numbers with Zero (ii)). If $t\neq0$, then $1\le t$, and $t=n+1$ for some $n\in\mathbb{N}_{0}$ (Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (vii)). Then Counting Subsets (iii), with $A=T(x)$ and $g:\mathbb{N}_{0}\to\mathbb{R}$, $g(j)=(-1)^{j}$, and Binomial Identities (ii) give

$$\sum_{S\in\mathcal{P}(T(x))}(-1)^{\#S}=\sum_{j=0}^{n+1}(-1)^{j}\binom{n+1}{j}=0.$$

By Step 1 and Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii), $t=0$ exactly when $x\in Y$. So the inner sum in Step 3 is $1$ for $x\in Y$ and $0$ for $x\in X\setminus Y$.

Step 5 ((i)). By Steps 3 and 4, together with Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (iv) and Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (v),

$$\sum_{S\in\mathcal{P}([m])}(-1)^{\#S}\,\#A_{S}=\sum_{x\in Y}1=\#Y=\#\Big(X\setminus\bigcup_{i=1}^{m}A_{i}\Big).$$

Step 6 ((ii)). The set $\mathcal{P}([m])$ is the disjoint union of $\{\emptyset\}$ and $\mathcal{P}([m])\setminus\{\emptyset\}$, and the term at $S=\emptyset$ is $(-1)^{0}\,\#A_{\emptyset}=\#X$. So by Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (ii) and Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (i), Step 5 reads

$$\#Y=\#X+\sum_{S\in\mathcal{P}([m])\setminus\{\emptyset\}}(-1)^{\#S}\,\#A_{S}.$$

Since $X$ is the disjoint union of $U$ and $Y$, $\#U+\#Y=\#X$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (v). For every $S$, $(-1)^{\#S+1}=(-1)^{\#S}(-1)^{1}=-(-1)^{\#S}$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality (i) and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality (ii). Hence, multiplying the sum by $-1$ term by term (Sums over Finite Sets in a Commutative Ring and in an Ordered Field: Distributivity, Products of Sums, Vanishing Terms, Sums over Pairs, Expanding Products of Sums, Counting, Comparison, Monotonicity and the Triangle Inequality (i)),

$$\#U=\#X-\#Y=-\sum_{S\in\mathcal{P}([m])\setminus\{\emptyset\}}(-1)^{\#S}\,\#A_{S}=\sum_{S\in\mathcal{P}([m])\setminus\{\emptyset\}}(-1)^{\#S+1}\,\#A_{S}.$$