Inclusion-Exclusion Proof without inverses

196 Views Asked by At

If $f$ is additive then it satisfies the inclusion-exclusion principle $$ f(\bigcup A) = \sum_{B \subset A} f(\bigcap B) \cdot (-1)^{|B|+1} $$ where $B$ is (here and henceforth) assumed to be nonempty. See \url{http://www.proofwiki.org/wiki/Inclusion-Exclusion_Principle#Comment}

All proofs I've seen rely on using subtraction and I am unable to avoid it in my attempted proofs.

Could you please proof the equivalent restatement (?), $$ f(\bigcup A) + \sum_{\text{ even }B \subset A} f(\bigcap B) = \sum_{\text{ odd } B \subset A} f(\bigcap B) $$

without using the notion of subtraction.

Motavation: we are in a setting where + has no inverse -.

Thank you :)

1

There are 1 best solutions below

2
On

You could do an induction proof just like in the link; however I think this should follow from the "usual case" by an "abstract-nonsense" sort of argument. Here is an attempt. (I will use the notation from the linked proofwiki page, since the one in the question is not consistent.)

We have $\cup_{i} A_i = \sqcup_{\alpha \neq \emptyset} A_\alpha$ where $\alpha \subset \{1, \ldots, n\}$ is an indexing set and $A_\alpha = \left(\cap_{i \in \alpha} A_i \right) \cap \left(\cap_{j \notin \alpha} A_j^\complement\right)$ - this just says that each element of the union of $A_i$'s is in some non-empty collection $\alpha$ of individual $A_i$'s and this collection is uniquely determined by the element. We have similar formulas for every subset $s$ of $\{1, \ldots, n\}$

$\cap_{i \in s} A_i = \sqcup_{s\subset \alpha} A_\alpha$

This says that an element which is in all $A_i$'s (for $i$ in $s$) must simply be contained in the set of $A_i$'s that includes $s$.

Thus on both sides of the equation

$f(\cup_{i} A_i)+\sum_{|s| even} f( \cap_{i \in s} A_i) = \sum_{|s| odd} f( \cap_{i \in s} A_i)$

$f$ is applied to some disjoint unions of $A_\alpha$'s. By additivity of $f$, this means that both sides are (positive integer) linear combinations of $f(A_\alpha)$'s. The only thing we need to know is that the coefficients of each $A_\alpha$ on both sides are the same. This is a purely combinatorial statement which is equivalent to the "usual" inclusion-excusion.

(For example, consider {subsets of $1,\ldots, n\}$, and define A_i={those subsets that don't contain i}. Then $A_\alpha$ has one element for each $\alpha$ ("the $\alpha$ itself), and applying usual inclusion-exclusion to additive $f$ with value $1$ on singleton set containing that element and $0$ on other singleton sets, proves that the coefficient of $A_\alpha$ on both sides of the equation is the same. Since this is true for all $\alpha$ the result follows.)