# Inclusion-Exclusion Number of Sets

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?

• 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! – Lord Shark the Unknown Feb 5 at 6:40

## 1 Answer

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

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

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