# Formule du crible/Démonstration de la formule du crible

Soient n ensembles A$_1$, A$_2$, … , A$_n$ (non nécessairement disjoints). Pour tout ensemble d'indices $I\subset \{1,\dots ,n\}$, notons $A_{I}$ l'intersection correspondant à ces indices :
    $A_{I}:=\bigcap _{i\in I}A_{i}$.
Le cardinal de l'union des n ensembles est alors donné par :
    $\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)=\sum _{\varnothing \neq I\subset \{1,\dots ,n\}}(-1)^{\operatorname {card} (I)-1}\operatorname {card} \left(A_{I}\right)$.
Initialisation.
Dans le cas n = 1, nous avons :
    $\operatorname {card} (A_{1})=\operatorname {card} (A_{1}),$
ce qui ne fait aucun doute.
Le cas n = 2 est la formule :
    $\operatorname {card} (A_{1}\cup A_{2})=\operatorname {card} (A_{1})+\operatorname {card} (A_{2})-\operatorname {card} (A_{1}\cap A_{2})$,
qui est démontrée dans Introduction aux mathématiques/Rudiments de combinatoire.
Hérédité.
Soit n ≥ 2. Supposons la formule du crible vraie à l’ordre n et montrons qu'alors, elle est vraie à l’ordre n + 1. D'après le cas n = 2,
    $\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)+\operatorname {card} (A_{n+1})-\operatorname {card} \left(\left(\bigcup _{i=1}^{n}A_{i}\right)\cap A_{n+1}\right)$.
L'intersection étant distributive par rapport à la réunion, on obtient :
    $\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)+\operatorname {card} (A_{n+1})-\operatorname {card} \left(\bigcup _{i=1}^{n}\left(A_{i}\cap A_{n+1}\right)\right)$.
On peut alors appliquer l’hypothèse de récurrence sur le premier et le troisième terme du second membre.
    ${\begin{aligned}\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)&=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\operatorname {card} (A_{n+1})-\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(\bigcap _{i\in I}\left(A_{i}\cap A_{n+1}\right)\right)\\&=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\operatorname {card} (A_{n+1})+\sum _{k=1}^{n}(-1)^{k}\sum _{n+1\in J\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (J)=k+1}\operatorname {card} \left(A_{J}\right).\end{aligned}}$
Faisons un glissement d’indice dans le dernier terme.
    $\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\operatorname {card} (A_{n+1})+\sum _{k=2}^{n+1}(-1)^{k-1}\sum _{n+1\in J\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (J)=k}\operatorname {card} \left(A_{J}\right)$.
On remarque que si l’on fait k = 1 dans la dernière somme, on obtient card(A$_{n+1}$), qui est justement le deuxième terme du second membre. On peut donc écrire :
    $\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\left(\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)\right)+\sum _{k=1}^{n+1}(-1)^{k-1}\sum _{n+1\in J\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (J)=k}\operatorname {card} \left(A_{J}\right)$.
Nous remarquons que le premier terme de la somme contient toutes les intersections des A$_i$ où ne figure pas A$_{n+1}$ et le deuxième terme de la somme contient toutes les intersections des A$_i$ où figure A$_{n+1}$. Nous pouvons donc réunir ces deux sommes en une seule de la manière suivante :
    $\operatorname {card} \left(\bigcup _{i=1}^{n+1}A_{i}\right)=\sum _{k=1}^{n+1}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n+1\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)$,
ce qui nous montre que la formule du crible est vraie à l’ordre n + 1.
Conclusion.
On a bien :
    $\forall n\in \mathbb {N} ^{*}\qquad \operatorname {card} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop \operatorname {card} (I)=k}\operatorname {card} \left(A_{I}\right)$.
La fonction (définie sur $A:=\cup A_{i}$)
    $(1-\chi _{A_{1}})(1-\chi _{A_{2}})\cdots (1-\chi _{A_{n}})$
étant identiquement nulle, on en déduit, en développant ce produit :
    $0=1+\sum _{\varnothing \neq I\subset \{1,\dots ,n\}}(-1)^{\operatorname {card} (I)}\chi _{A_{I}}$,
ou, de façon équivalente :
    $\sum _{\varnothing \neq I\subset \{1,\dots ,n\}}(-1)^{\operatorname {card} (I)-1}\chi _{A_{I}}=1$.
On conclut en faisant, de part et d'autre de cette égalité de fonctions, la somme des valeurs quand la variable parcourt $A$.

## Remarque

    L'énoncé du théorème reste valide pour n = 0, puisqu'une union indexée par ∅ est vide et qu'une somme indexée par ∅ est nulle.
| Définition | Exemple d'application |