2
$\begingroup$

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

enter image description here

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!

$\endgroup$
9
  • $\begingroup$ The author is showing that the contribution of each element in the RHS is 1 which is obviously the same contribution as the LHS. $\endgroup$ – Phicar Dec 16 '19 at 16:10
  • $\begingroup$ @Phicar but does that prove the original statement? $\endgroup$ – MathMan Dec 16 '19 at 16:11
  • 1
    $\begingroup$ Yes cause in the LHS there is the cardinal of the union. Because they are sets, each element there has 1 as a contribution on the size of the set. Therefore they are counting the same thing. $\endgroup$ – Phicar Dec 16 '19 at 16:14
  • 1
    $\begingroup$ I don't think this is the full and complete proof. The RHS is "the number of elements altogether" and the LHS is a manipulation of elements. This proof, such as it is, is that a single element $x$ provides exactly $1$ to the LHS. The text says "this completes the proof" but I think an observation needs to be made the if each single element $x$ provides exactly $1$ to the LHS then all the elements together will contribute the the number of elements to the LHS and the LHS will be precisely the number of elements. That would complete the proof. ... Maybe the author stated that somewhere $\endgroup$ – fleablood Dec 16 '19 at 18:01
  • 1
    $\begingroup$ If $x$, a single element, is a member of $r$ sets, then whenever you choose one of those sets you count it once. The number of ways to choose one of those $r$ sets is $C(r,1) = r$. So there are $r$ sets $A_i$ were $x \in A_i$.... Likewise if $x \in A_i \cap A_j$ you count it once in $\sum |A_i\cap A_j|$. For $x \in A_i\cap A_j$ we must have $x \in A_i$ and $x\in A_j$. There are $r$ sets that $x$ is in so we must choose two sets out of $r$ sets that $x$ is in. If $x$ is in $r$ sets there are ${r\choose 2}$ possible ($A_i, A_j$) so that $x$ is in both. $\endgroup$ – fleablood Dec 16 '19 at 18:36
3
$\begingroup$

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.

$\endgroup$
20
  • $\begingroup$ If $x \in \bigcup _iA_i$ then it also contributes to the cardinality of RHS. but, the RHS might contain other terms as well. Could you please clarify? $\endgroup$ – MathMan Dec 16 '19 at 16:30
  • $\begingroup$ I got it till this point: 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.$ Shouldn't that mean the LHS is a subset of RHS? $\endgroup$ – MathMan Dec 16 '19 at 16:42
  • $\begingroup$ But if $x$ is not in the union, then the contribution on the RHS is zero because every term in the expression is a subset of the union. $\endgroup$ – Phicar Dec 16 '19 at 16:45
  • $\begingroup$ So, i think i now get the gist of it. It is as follows: All elements in $\cup A_i$ contributes a count of $1$ in the RHS ( and of course to the LHS). which means, the RHS is composed exactly of the elements in the LHS. There are no elements which are outside of $\cup A_i$. Hence, the theorem is proved. Am I correct? $\endgroup$ – MathMan Dec 16 '19 at 16:56
  • $\begingroup$ well, ", the RHS is composed exactly of the elements in the LHS" this makes no sense in the sense that they are not sets, but is more like each element gives the same contribution. $\endgroup$ – Phicar Dec 16 '19 at 17:00
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer. I notice that the RHS produces $1$ for any element $'a'$ belonging to the the union of the sets. but it will produce the cardinality of the union if there is an extra summation sign appeneded before the expression on the RHS. Is this correct? $\endgroup$ – MathMan Dec 16 '19 at 19:24
  • $\begingroup$ this is exactly my source of confusion. The LHS is meant to produce cardinality of the union whereas the RHS produces a $1$ for every elements of the union. What do you think about this discrepancy $\endgroup$ – MathMan Dec 16 '19 at 20:23

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.