elementary set theory - Inclusion–exclusion principle [Proof verification]

Please check if my proof contains any error! Thank you so much!

---

Lemma: Let $A=\{J\subseteq\{1,2,\cdots,k\}\mid J\neq\emptyset\}$ and $B=\{J\subseteq\{1,2,\cdots,k+1\}\mid J\neq\emptyset\}$, then $$B-A=\{\{k+1\}\}\cup\{\{k+1\}\cup x\mid x\in A\}$$

Proof:

$y\in B-A\Leftrightarrow\begin{cases}\ y\in B\\y\notin A\\\end{cases}\Leftrightarrow\begin{cases}\ y\subseteq\{1,2,\cdots,k+1\}\text{, and }y\neq\emptyset\\y\not\subseteq\{1,2,\cdots,k\}\text{, or }y=\emptyset\\\end{cases}\Leftrightarrow\begin{cases}\ y\subseteq\{1,2,\cdots,k+1\}\text{, and }y\neq\emptyset\\\exists m\in y\text{ such that } m\notin\{1,2,\cdots,k\}\text{, or }y=\emptyset\\\end{cases}\Leftrightarrow\begin{cases}\ y\subseteq\{1,2,\cdots,k+1\}\\m=k+1\in y\\\end{cases}\Leftrightarrow y\in\{\{k+1\}\}\cup\{\{k+1\}\cup x\mid x\in A\}$.

Equivalently, $B=A\cup\{\{k+1\}\}\cup\{\{k+1\}\cup x\mid x\in A\}.$ $$\tag*{$\blacksquare$}$$

Inclusion–exclusion Principle: Let $A_1,A_2,\cdots,A_n$ be finite subsets of a set $X$ and $A=\{J\subseteq\{1,2,\cdots,n\}\mid J\neq\emptyset\}$, then $$\left |\bigcup_{i=1}^nA_i\right|=\sum_{J\in A}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|$$

Proof of Inclusion–exclusion Principle:

It's trivial that the theorem is true for $n=2$. Assume that it is true for $n=k$, then $$\left |\bigcup_{i=1}^kA_i\right|=\sum_{J\in A}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|$$

First, notice that

$-\sum_{J\in A}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}(A_j\cap A_{k+1})\right|$

$=-\sum_{J\in \{\{k+1\}\cup x\mid x\in A\}}(-1)^{(\left|J\right|-1)-1}\left|\bigcap_{j\in J}A_j\right|$

$=\sum_{J\in \{\{k+1\}\cup x\mid x\in A\}}(-1)^{(\left|J\right|-1)-1+1}\left|\bigcap_{j\in J}A_j\right|$

$=\sum_{J\in \{\{k+1\}\cup x\mid x\in A\}}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|$

For $n=k+1$, we have that

$\left |\bigcup_{i=1}^{k+1}A_i\right|$

$=\left |(\bigcup_{i=1}^{k}A_i)\cup A_{k+1}\right|$

$=\left |\bigcup_{i=1}^{k}A_i\right|+\left |A_{k+1}\right|-\left |(\bigcup_{i=1}^{k}A_i)\cap A_{k+1}\right|$ [It's clear the theorem for $n=2$]

$=\left |\bigcup_{i=1}^{k}A_i\right|+\left |A_{k+1}\right|-\left |\bigcup_{i=1}^{k}(A_i\cap A_{k+1})\right|$

$=\sum_{J\in A}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|+\sum_{J\in \{\{k+1\}\}}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|-\sum_{J\in A}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}(A_j\cap A_{k+1})\right|$ $\text{ [We apply inductive hypothesis in which the theorem is true for $n=k$]}$

$=\sum_{J\in A}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|+\sum_{J\in \{\{k+1\}\}}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|+\sum_{J\in \{\{k+1\}\cup x\mid x\in A\}}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|$

$=\sum_{J\in A\cup\{\{k+1\}\}\cup\{\{k+1\}\cup x\mid x\in A\}}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|$

$=\sum_{J\in B}(-1)^{\left|J\right|-1}\left|\bigcap_{j\in J}A_j\right|$

Thus, the theorem is true for $n=k+1$. By principle of induction, Inclusion–exclusion Principle is proved. $$\tag*{$\blacksquare$}$$

Answer

Hint:

• The proof of the lemma is correct. In fact it states the clear relation, that with $[k]:=\{1,2,\ldots,k\}$ the powerset of $[k+1]$ minus the powerset of $[k]$ is the set of all subsets which contain the element $k+1$.
  $$
  \left.
  \begin{array}{rl}
  A&=\mathcal{P}\left([k]\right)\setminus\emptyset\\
  B&=\mathcal{P}\left([k+1]\right)\setminus\emptyset\\
  
  \end{array}
  \right\}
  \Longrightarrow B\setminus A=\mathcal{P}\left([k+1]\right)\cap\{\{k+1\}\}
  $$




• The proof of the Inclusion-Exclusion principle seems to be correct. Good work. We might skip the representation $$A_{k+1}=\sum_{J\in\{\{k+1\}\}}(-1)^{|J|-1}\left|\bigcap_{j\in J}A_j\right|$$ as it is not relevant for the proof and stick with $A_{k+1}$ enhancing readability.