Proving the Inclusion Exclusion Principle using Combinatorics

Question

The Generalization of the Inclusion-Exclusion Principle for $n$ sets is proved by the author as follows:

Although the proof seems very exciting, I am confused because what the author has proved is $1=1$ from the $LHS$ and $RHS$.

Thus, Is this still a valid proof? We need to prove that the total cardinality of LHS is the RHS. The RHS produces a $1$ for each member of the union of the sets.

I think in order to produce the cardinality of the union, an extra summation sign should be appended before the expression in RHS. Could someone please clarify. Thanks a lot!

Answer 1

This is an expanded version of my comment, perhaps makes more sense:

You can think the LHS of the equation as $$\left |\bigcup _{i\in [n]} A_i\right |=\sum _{x\in \cup _{i\in [n]} A_i}1,$$ so you what they are doing in the proof is making sure that the 1 that $x$ gives as contribution in the LHS is the same 1 in the RHS.
Edit: To clarify, to show the Inclusion exclusion expression, you can show that the two sides of the equation are equal to $$\sum _{x\in \cup _{i\in [n]} A_i}1,$$ so you take an arbitrary $x\in \cup A_i$ and check that the number of times it is counted in the RHS of the equation is $1.$ If you check that, you are showing that the RHS is equal to the expression which, by the equality above, is equal to the LHS, therefore the two expressions are the same.

Answer 2

I don't think the proof as it is stated is completed. But it would be if the following trivial observation were made.

For any finite set $A$ then $|A| = \sum\limits_{x\in A} 1=\sum\limits_{x\in U} \begin{cases}1&x\in A\\ 0 &x\not \in A\end{cases}$, for some universal set $U$.

Thus the RHS is $|\cup_{1\le i \le n}A_n| =\sum\limits_{x\in A} 1=\sum\limits_{x\in U}\begin{cases}1&x\in \cup_{1\le i \le n}A_n\\ 0 &x\not \in \cup_{1\le i \le n}A_n\end{cases}$ and the LHS is

$\sum\limits_{x\in U}[\sum\limits_{1\le i \le n}\begin{cases}1&x\in A_i\\ 0 &x\not \in A_i\end{cases}-\sum\limits_{1 \le i_1 \le i_2 \le n}\begin{cases}1&x\in A_{i_1}\cup A_{i_2}\\ 0 &x\not \in A_{i_1}\cup A_{i_2}\end{cases}+ ......]$

Then to prove the statement it would be sufficiennt to prove that for each $x \in \cup A_i$ that $[\sum\limits_{1\le i \le n}\begin{cases}1&x\in A_i\\ 0 &x\not \in A_i\end{cases}-\sum\limits_{1 \le i_1 \le i_2 \le n}\begin{cases}1&x\in A_{i_1}\cup A_{i_2}\\ 0 &x\not \in A_{i_1}\cup A_{i_2}\end{cases}+ ......] = 1$ and for each $x \not \in \cup A_i$ that $[\sum\limits_{1\le i \le n}\begin{cases}1&x\in A_i\\ 0 &x\not \in A_i\end{cases}-\sum\limits_{1 \le i_1 \le i_2 \le n}\begin{cases}1&x\in A_{i_1}\cup A_{i_2}\\ 0 &x\not \in A_{i_1}\cup A_{i_2}\end{cases}+ ......]=0$.

And that is precisely what the proof did do.