I am trying to write
$$|A_1\backslash\cup_{i=2}^{m}A_i|,$$
and
$$|\cup_{i=1}^{m}A_i|,$$
as intersections.
For example, for $m=3$, I can write
$$|A_1\backslash(A_2\cup A_3)|=|A_1|-|A_1\cap A_2|-|A_1\cap A_3|+|A_1\cap A_2\cap A_3|.$$
Also,
$$|A_1\cup A_2\cup A_3|=|A_1|+|A_2|+|A_3|-|A_1\cap A_2|-|A_2\cap A_3|-|A_1\cap A_3|+|A_1\cap A_2\cap A_3|.$$
Is it possible to generalize this for any $m$?
Best Answer
The second example is called the principle of inclusion-exclusion. Basically, it says that if you have a family of sets $F$ and you want to count the elements of $\cup F$, you can look at all subsets of $F$ and count the total number of elements in the intersection of each subset ... but with subsets with an odd number of things counting positively and subsets with an even number of things counting negatively. This is easy to see in the case where $F$ has two sets in it.
$$ | A \cup B | = -0 + |A| + |B| - |A \cap B|$$
In this case $F = \{A, B\}$, the singleton subsets have an odd number of elements, $F$ itself and the empty set each count negatively.
It can be succinctly written as:
$$ \left|\cup F \right| = \sum_{x \in P(F)} (-1)^{(|x|+1)} \cdot | \cap x | $$
With $P(F)$ being the powerset of $F$ (i.e. the set of all subsets).
The first example does not have a name, but is given by the following formula:
$$ \left| A \setminus (\cup F) \right| = \sum_{x \in P(F)} (-1)^{\left|x\right|} \cdot \left|A \cap (\cap x)\right| $$
Here's the derivation for this formula, assuming we believe the principle of inclusion-exclusion given above
start with expression we want.
$$ | A \setminus (\cup F) | $$
cardinality of relative complement.
$$ | A | - \left|A \cap \left(\bigcup_{B \in F} B \right)\right| $$
distributive property
$$ | A | - \left|\left(\bigcup_{B \in F} A \cap B \right)\right| $$ let $G$ be defined as $ \{ A \cap x \;\text{where}\; x \in F \} $. $$ |A| - |\cup G| $$
apply principle of inclusion-exclusion
$$ |A| - \sum_{x \in P(G)} (-1)^{(|x| + 1)} \cdot |\cap x| $$
Here's where we remember that $\cap x$ refers to the intersection of a subset of $G$. The elements of $G$ are the elements of $F$, except that I intersected each element with the set $A$. I can perform this intersection last instead of first, as below.
$$ |A| - \sum_{x \in P(F)} (-1)^{(|x|+1)} \cdot |A \cap (\cap x)| $$
combining into a single sum:
$$ \left| A \setminus (\cup F) \right| = \sum_{x \in P(F)} (-1)^{\left|x\right|} \cdot \left|A \cap (\cap x)\right| $$