The inclusion and exclusion criteria

Question

I've learned that in probability course, in the exercise we are asked to prove that: given $n$ sets $A_1,\ldots,A_n$,

$$ \left|\bigcup_i A_i\right| \ge \sum_i|A_i| - \sum_{i\ne j}|A_i\cap A_j|\;.$$

I know that the set that is defined by a cut of $\ge3$ sets is smaller than the one of $\ge2$ sets, but I don't know how to apply that to the question.

Answer 1

HINT: It’s a little easier to work with in the form

$$\sum_i|A_i|\le\left|\bigcup_iA_i\right|+\sum_{i\ne j}|A_i\cap A_j|\;.$$

Let $A=\bigcup_iA_i$, and for each $x\in A$ let $n(x)$ be the number of sets $A_i$ that contain $x$.

• Show that $\sum_i|A_i|=\sum_{x\in A}n(x)$.

Let $S=\{x\in A:n(x)\ge 2\}$, the set of points that are in at least two of the sets $A_i$.

• Show that $\sum_{i\ne j}|A_i\cap A_j|\ge\sum_{x\in S}n(x)$.

This reduces your problem to showing that

$$\sum_{x\in A}n(x)\le\sum_{x\in S}n(x)+|A|\;,$$

which isn’t hard.

Answer 2

I preassume that it must be shown that for each $n\in\mathbb N$ we have:$$\left|\bigcup_{i=1}^{n}A_{i}\right|\geq\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{i<j}^{n}\left|A_{i}\cap A_{j}\right|$$Note that this is a stronger statement than the statement in your question.This because:$$\sum_{i<j}^{n}\left|A_{i}\cap A_{j}\right|\leq\sum_{i\neq j}^{n}\left|A_{i}\cap A_{j}\right|$$

You can use induction. We have:

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

Our induction hypothese is: $$\left|\bigcup_{i=1}^{n}A_{i}\right|\geq\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{i<j}^{n}\left|A_{i}\cap A_{j}\right|$$ which can be combined with:$$\left|\left(\bigcup_{i=1}^{n}A_{i}\right)\cap A_{n+1}\right|\leq\sum_{i=1}^{n}\left|A_{i}\cap A_{n+1}\right|$$ to arrive at:$$\left|\bigcup_{i=1}^{n+1}A_{i}\right|\geq\sum_{i=1}^{n+1}\left|A_{i}\right|-\sum_{i<j}^{n+1}\left|A_{i}\cap A_{j}\right|$$