Derive and prove a general formula for the number of elements which are in an odd number of the sets $A_1,A_2,...,A_n$, written in terms of $|A1|$, $|A2\cap A7|$, $|A3\cap A4\cap A9|$, etc., possibly multiplied by coefficients.

I do not really understand this question, does it mean number of elements in total that are included in either $1$ set, $3$ sets, $5$ set, etc of any of the $n$ sets? Or does it mean we need to calculate the cardinality of a set like $|A_1|$ or $|A_1\cup A_2\cup A_3|$?

The later one is much easier to calculate, we just use the inclusion-exclusion principle. But if it was the first case, how can we possibly calculate number of elemnets without using the union symbol?

  • 1
    $\begingroup$ It's your first interpretation. For instance when $n=2$, it's $|A_1|+|A_2|-2|A_1\cap A_2|$. No unions there! $\endgroup$ – Lord Shark the Unknown Feb 5 at 6:40

To be found is:$$|\{x\mid\sum_{i=1}^n\mathbf1_{A_i}(x)\text{ is odd}\}|$$

It can be verified with induction that:$$\{x\mid\sum_{i=1}^n\mathbf1_{A_i}(x)\text{ is odd}\}=\Delta_{i=1}^n A_i$$For the induction step observe that: $$\sum_{i=1}^{n+1}\mathbf1_{A_i}(x)\text{ is odd}\iff $$$$\sum_{i=1}^{n}\mathbf1_{A_i}(x)\text{ is odd and }\mathbf1_{A_{n+1}}(x)=0\vee\sum_{i=1}^{n}\mathbf1_{A_i}(x)\text{ is even and }\mathbf1_{A_{n+1}}(x)=1$$

Also with induction it can be shown that:

$$1_{\Delta_{i=1}^n A_i}=\sum_{i=1}^n1_{A_i}-2\sum_{1\leq i<j\leq n}1_{A_i\cap A_j}+\cdots+(-2)^{n-1}1_{A_1\cap\cdots\cap A_n}$$

If $\mu$ denotes a measure and on both sides we integrate then we find:$$\mu(\Delta_{i=1}^n A_i)=\sum_{i=1}^n\mu(A_i)-2\sum_{1\leq i<j\leq n}\mu(A_i\cap A_j)+\cdots+(-2)^{n-1}\mu(A_1\cap\cdots\cap A_n)$$

Taking for $\mu$ the counting measure we find:$$|\Delta_{i=1}^n A_i|=\sum_{i=1}^n|A_i|-2\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\cdots+(-2)^{n-1}|A_1\cap\cdots\cap A_n|$$


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.