Take the 2-minute tour ×

Suppose I have $n+1$ sets of objects, $T_0,T_1,\dots,T_n$ and that I have $n$ mappings, $\alpha_1,\dots,\alpha_n$ such that $\alpha_i(T_j) \subseteq T_{j+1}$ for all $i=1,\dots,n$ and $j=0,\dots,n-1.$

What extra conditions are required for the following to hold: $$T_n = (\alpha_1+\alpha_2+\dots + \alpha_n)T_{n-1} - (\alpha_1 \alpha_2 + \alpha_1 \alpha_3 + \dots + \alpha_{n-1}\alpha_n)T_{n-2} \cdots +(-1)^{n-1} (\alpha_1 \alpha_2 \cdots \alpha_n) T_0$$ interpreted such that the objects on the left hand side appears exactly one time on the right hand side after cancellation.

Some natural conditions would be some or all of the following:

(1) $\alpha_i(\alpha_j(T_k)) = \alpha_j(\alpha_i(T_k)) =: \alpha_i \alpha_j T_k.$

(2) $T_n = (\alpha_1+\alpha_2+\dots + \alpha_n)T_{n-1}$ AS SETS, (but some objects appear multiple times on the right hand side).

(3) $t_1 \in T_k$, $\alpha_j(t_1) = \alpha_i(t_1) \Rightarrow i=j.$

(4) $t_1,t_2 \in T_k$, $\alpha_j(t_1) = \alpha_j(t_2) \Rightarrow t_1=t_2.$

(5) $t_1,t_2 \in T_k$, $\alpha_i(t_1) = \alpha_j(t_2) \Rightarrow \exists! t \in T_{k-1}: \alpha_i \alpha_j(t) = \alpha_i(t_1) = \alpha_j(t_2).$

All of the above holds for regular inclusion/exclusion where the $T_i$ are the subsets of $n$ of size $i,$ and $\alpha_i$ is interpreted as adding element $i.$

share|improve this question
What do you mean by "the $T_i$ are the subsets of $n$ of size $i$"? There are many such subsets, but only one $T_i$. Is $T_i$ meant to be the set of all such subsets? And $\alpha_i$ adds element $i$ to each of the subsets? But some of them already contain $i$ and wouldn't grow through this? –  joriki Jul 17 '12 at 10:18
$T_i$ is a set of objects. The objects in that particular instance are subsets of $1,2,...,n$ of size $i$. Yes, for the principle to work, one need to consider multi-sets, but notice that all such sets cancel in the RHS. –  Per Alexandersson Jul 17 '12 at 11:22
If I understand that correctly, then "the $T_i$ are the subsets of $n$ of size $i$" is wrong -- the $T_i$ are the sets of those subsets. –  joriki Jul 17 '12 at 11:34
Yes, exactly, but this is sort of a classic result. What I am after is the general setting, what conditions can be removed, and still have inclusion/exclusion to work...? –  Per Alexandersson Jul 17 '12 at 14:44

Your Answer



Browse other questions tagged or ask your own question.