Le crible à trois ensembles

L’Atelier vous l’a promise, et la question Q15.c) du DM1 en a fait sentir le manque : quand trois ensembles se chevauchent, la soustraction naïve retire certains éléments plusieurs fois, et le décompte s’effondre. Voici l’outil qui manquait, la formule du crible à trois ensembles : son énoncé, sa démonstration complète (deux applications du cas à deux ensembles, rien de plus), un exemple intégralement vérifié, la forme générale en vitrine, et l’histoire, assez injuste, de son nom.

Le point de départ : deux ensembles

Le cours (§1) a établi le cas fondateur : pour tous ensembles finis $A$ et $B$,

$$\operatorname{Card}(A \cup B) = \operatorname{Card}(A) + \operatorname{Card}(B) - \operatorname{Card}(A \cap B).$$

L’idée tient en une phrase : la somme $\operatorname{Card}(A) + \operatorname{Card}(B)$ compte une fois les éléments qui sont dans un seul des deux ensembles, mais deux fois ceux de $A \cap B$ ; on retranche donc ce cardinal, et chaque élément de la réunion se retrouve compté exactement une fois. Ce mécanisme, compter large puis retrancher juste, est toute l’âme du crible : le reste de cette page ne fait que le répéter à plus grande échelle.

L’énoncé à trois ensembles

Théorème. Pour tous ensembles finis $A$, $B$ et $C$,

$$\begin{aligned} \operatorname{Card}(A \cup B \cup C) ={}& \operatorname{Card}(A) + \operatorname{Card}(B) + \operatorname{Card}(C)\\ &- \operatorname{Card}(A \cap B) - \operatorname{Card}(A \cap C) - \operatorname{Card}(B \cap C)\\ &+ \operatorname{Card}(A \cap B \cap C). \end{aligned}$$

La structure se lit à voix haute : additionner les trois cardinaux, retrancher les trois intersections deux à deux, rajouter l’intersection triple. Sept termes, signes alternés par étage.

La démonstration : l’associativité fait tout le travail

La réunion est associative : $A \cup B \cup C = (A \cup B) \cup C$. On peut donc voir la réunion des trois comme une réunion de deux ensembles, le bloc $A \cup B$ d’une part, $C$ d’autre part, et appliquer le cas du cours à ce couple :

$$\operatorname{Card}\bigl((A \cup B) \cup C\bigr) = \operatorname{Card}(A \cup B) + \operatorname{Card}(C) - \operatorname{Card}\bigl((A \cup B) \cap C\bigr).$$

Deux termes restent à ouvrir, et le cas à deux ensembles suffit pour chacun.

Premier terme. Directement :

$$\operatorname{Card}(A \cup B) = \operatorname{Card}(A) + \operatorname{Card}(B) - \operatorname{Card}(A \cap B).$$

Troisième terme. L’intersection se distribue sur la réunion : $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ (un élément de $C$ appartient à $A \cup B$ exactement lorsqu’il appartient à $A \cap C$ ou à $B \cap C$). C’est de nouveau une réunion de deux ensembles ; le cas du cours s’applique une troisième fois :

$$\operatorname{Card}\bigl((A \cap C) \cup (B \cap C)\bigr) = \operatorname{Card}(A \cap C) + \operatorname{Card}(B \cap C) - \operatorname{Card}\bigl((A \cap C) \cap (B \cap C)\bigr),$$

et $(A \cap C) \cap (B \cap C) = A \cap B \cap C$ : appartenir aux deux, c’est appartenir aux trois.

Assemblage. En reportant ces deux développements dans la première égalité :

$$\begin{aligned} \operatorname{Card}(A \cup B \cup C) ={}& \bigl[\operatorname{Card}(A) + \operatorname{Card}(B) - \operatorname{Card}(A \cap B)\bigr] + \operatorname{Card}(C)\\ &- \bigl[\operatorname{Card}(A \cap C) + \operatorname{Card}(B \cap C) - \operatorname{Card}(A \cap B \cap C)\bigr], \end{aligned}$$

ce qui, une fois les crochets ouverts, est exactement la formule annoncée. $\blacksquare$

Pourquoi les signes tombent juste. On peut relire la formule en suivant un élément à la trace. Un élément qui appartient à exactement un des trois ensembles est compté une fois au premier étage, et jamais ensuite : total $1$. Un élément de exactement deux ensembles est compté deux fois au premier étage, retranché une fois au deuxième : $2 - 1 = 1$. Un élément des trois est compté trois fois, retranché trois fois, rajouté une fois : $3 - 3 + 1 = 1$. Chacun finit compté exactement une fois : c’est cela, tamiser.

L’exemple : multiples de $2$, $3$ ou $5$ parmi les cinquante premiers entiers

Dans $E = \llbracket 1\,; 50 \rrbracket$, notons $A$, $B$ et $C$ les ensembles des multiples de $2$, de $3$ et de $5$ respectivement. Combien d’entiers de $E$ sont multiples d’au moins un de ces trois nombres ? Chaque cardinal se lit par division : les multiples de $d$ dans $\llbracket 1\,; 50 \rrbracket$ sont $d, 2d, \ldots$, au nombre de $\lfloor 50/d \rfloor$. Et une intersection est elle-même un ensemble de multiples : être multiple de $2$ et de $3$, c’est être multiple de $6$.

Ensemble	Description	Cardinal
$A$	multiples de $2$	$25$
$B$	multiples de $3$	$16$
$C$	multiples de $5$	$10$
$A \cap B$	multiples de $6$	$8$
$A \cap C$	multiples de $10$	$5$
$B \cap C$	multiples de $15$	$3$
$A \cap B \cap C$	multiples de $30$	$1$

Le crible donne alors :

$$\operatorname{Card}(A \cup B \cup C) = 25 + 16 + 10 - 8 - 5 - 3 + 1 = 36.$$

On peut refaire le calcul en suivant pas à pas la démonstration, bloc par bloc : $\operatorname{Card}(A \cup B) = 25 + 16 - 8 = 33$, puis $\operatorname{Card}\bigl((A \cup B) \cap C\bigr) = 5 + 3 - 1 = 7$, et enfin $33 + 10 - 7 = 36$. Même verdict. Et le contrôle ultime, l’énumération brutale des cinquante entiers un par un (une machine s’en charge volontiers), confirme : la réunion compte bien $36$ éléments. Les deux membres de la formule valent $36$, et par contrecoup $50 - 36 = 14$ entiers de $\llbracket 1\,; 50 \rrbracket$ échappent aux trois diviseurs.

Notez ce que la soustraction naïve aurait donné : $25 + 16 + 10 = 51$, plus que d’entiers disponibles. C’est le naufrage de Q15.c), reproduit ici en pleine lumière : sans les corrections, un nombre comme $30$, membre des trois ensembles, est compté trois fois.

La forme générale, en vitrine

Le même mouvement se poursuit : pour tous ensembles finis $A_1, A_2, \ldots, A_p$ (avec $p \geqslant 1$),

$$\operatorname{Card}\left(\bigcup_{i=1}^{p} A_i\right) = \sum_{j=1}^{p} (-1)^{j+1} \sum_{1 \leqslant i_1 < i_2 < \cdots < i_j \leqslant p} \operatorname{Card}\bigl(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}\bigr) :$$

additionner tous les cardinaux, retrancher toutes les intersections deux à deux, rajouter toutes les intersections trois à trois, et ainsi de suite en alternant les signes jusqu’à l’intersection de tous. La démonstration est une récurrence sur $p$ dont le pas est exactement le geste de cette page : isoler $A_p$, écrire $\bigcup_{i=1}^{p} A_i = \bigl(\bigcup_{i=1}^{p-1} A_i\bigr) \cup A_p$, appliquer le cas à deux ensembles, distribuer l’intersection par $A_p$, puis invoquer deux fois l’hypothèse de récurrence (une fois pour les $A_i$, une fois pour les $A_i \cap A_p$). Nous ne la rédigeons pas : seul le cas à deux ensembles est exigible en terminale, le cas à trois est un prolongement raisonnable, le cas général vous attend dans le supérieur. Mais vous savez désormais d’où il sortira.

Plusieurs pères, aucun nom

Cette formule est un cas d’école de ce que les historiens appellent la loi de Stigler : aucune découverte ne porte le nom de son premier auteur. Adrien-Marie Legendre en utilise un cas particulier dès 1808, dans la seconde édition de son Essai sur la théorie des nombres, précisément pour compter les entiers qui échappent à une liste de diviseurs premiers : notre exemple des multiples de $2$, $3$ et $5$ est, à cinquante entiers près, le sien. Le principe général est ensuite dégagé plusieurs fois, indépendamment : par Daniel Augusto da Silva à Lisbonne en 1854, dans un mémoire sur les congruences présenté à l’Académie des sciences de Lisbonne ; par James Joseph Sylvester en 1883 ; puis par Henri Poincaré, dont un traité de 1896 installera durablement l’énoncé dans l’enseignement français. Certains font même remonter un germe de l’idée à de Moivre en 1718, attribution disputée.

Da Silva est le plus méconnu du quatuor : officier de la marine portugaise, professeur à l’école navale de Lisbonne, à la santé fragile, il précède Sylvester de vingt-neuf ans. Le monde mathématique dit pourtant « principe d’inclusion-exclusion », « formule du crible », parfois « formule de Poincaré » ; personne ne dit « formule de da Silva ». Le principe a plusieurs pères, et le nom n’en retient aucun.

La formule, elle, se moque des baptêmes : elle travaille. La preuve dans l’extra suivant, où elle dénombre enfin les surjections que le DM avait dû laisser en suspens.

Sources

• Cours du chapitre A2, §1 : principe additif et crible à deux ensembles ; DM1 du chapitre A2, question Q15.c), où la soustraction naïve échoue.
• Adrien-Marie Legendre, Essai sur la théorie des nombres, seconde édition, Paris, 1808 : décompte des entiers premiers avec une liste de nombres donnés.
• Daniel Augusto da Silva, mémoire sur les congruences présenté à l’Académie des sciences de Lisbonne, 1854 ; sur sa vie, F. Silva et R. Duarte, portrait disponible sur arXiv (1812.06267).
• Sur la paternité multiple du principe (Legendre, da Silva, Sylvester, Poincaré) : British Journal for the History of Mathematics, vol. 37 (2022).
• Vérification numérique de l’exemple : énumération machine des entiers de $1$ à $50$, les deux membres valent $36$.