3
$\begingroup$

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$}$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi @MarkusScheuer, I'm sorry for not being clear enough (I've edited my post for more clarity). Let $A_1,A_2,\cdots,A_n$ be finite subsets of a set $X$. I meant to use the lemma to prove Inclusion-exclusion Principle, so the proof at the end is the proof of Inclusion-exclusion Principle itself. Please have a check on that proof! $\endgroup$ – Le Anh Dung May 21 '18 at 1:22
  • $\begingroup$ Hi @MarkusScheuer, please have a look at my edited proof! I've been waiting for your response :) $\endgroup$ – Le Anh Dung May 21 '18 at 9:05
  • 1
    $\begingroup$ @CrazyGuy: I have checked your updated post and I've updated my answer accordingly. Everything seems to be fine. Good work. $\endgroup$ – Markus Scheuer May 21 '18 at 10:01
  • $\begingroup$ Thank you so much! You made my day :) $\endgroup$ – Le Anh Dung May 21 '18 at 10:04
  • $\begingroup$ @CrazyGuy: You're welcome. Besides the content you also show a good technical skill. $\endgroup$ – Markus Scheuer May 21 '18 at 10:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.