Cardinal d'un ensemble fini — principe d'inclusion-exclusion — ensembles équipotents et bijections
Compter semble la plus simple des opérations ; c'est pourtant celle qui demande le plus de précautions. Dire card A = n, c'est affirmer qu'on peut numéroter les éléments de A de 1 à n sans en oublier ni en compter deux fois — autrement dit qu'il existe une bijection entre {1, …, n} et A. Tout le dénombrement découle de cette idée : quand une collection résiste au comptage direct, on la met en bijection avec une collection déjà connue. Et quand les ensembles deviennent infinis, la bijection survit là où le comptage abandonne.
L'univers est E = {1, …, 24}. Choisissez la partie A, puis l'ordre dans lequel vous voulez la parcourir : le comptage attribue les étiquettes 1, 2, 3, … aux jetons de A, une par jeton. Le dernier numéro attribué est le cardinal.
Les jetons de A sont maintenant rangés dans m tiroirs selon leur reste dans la division par m. Deux lectures en découlent : aucun rangement ne peut éviter qu'un tiroir contienne au moins ⌈n/m⌉ jetons, et si tous les tiroirs ont la même taille k, alors n = k × m — on a compté sans compter.
Ce que dit la planche. Le cardinal ne dépend pas de l'ordre du comptage : numéroter A de deux façons, c'est composer deux bijections, et la composée {1, …, n} → {1, …, n} ne peut exister que si les deux numérotations s'arrêtent au même nombre. L'ensemble vide a pour cardinal 0, un singleton 1. Et dès que n > m, ranger n jetons dans m tiroirs impose un tiroir à deux jetons : c'est le principe des tiroirs, qui dit exactement qu'il n'existe aucune injection d'un ensemble à n éléments dans un ensemble plus petit.
Sur E = {1, …, 60}, deux à quatre parties se recouvrent. Additionner leurs cardinaux compte plusieurs fois les éléments communs ; la formule corrige en alternant. Cliquez un jeton pour ouvrir son compte personnel : combien de fois il est ajouté, combien de fois retranché, et ce qu'il reste au total.
Un élément qui appartient à exactement j des parties est compté C(j,1) fois dans les termes simples, retranché C(j,2) fois dans les intersections deux à deux, rajouté C(j,3) fois, etc. Le solde vaut Σ (−1)i+1 C(j,i) = 1 dès que j ⩾ 1, et 0 sinon : chaque élément de la réunion est donc compté exactement une fois. La colonne « solde » ci-dessous ne contient que des 0 et des 1.
| appartient à j parties | effectif | détail du compte | solde | contribution au total |
|---|
Ce que dit la planche. Pour deux parties, card(A ∪ B) = card A + card B − card(A ∩ B) ; pour trois, on retranche les trois intersections deux à deux et on rajoute l'intersection triple. En général la formule compte 2k − 1 termes, avec le signe (−1)i+1 pour les intersections de i parties. Les sommes partielles encadrent le résultat en alternant au-dessus et en dessous : c'est ce que l'escalier montre à chaque marche.
Quand une collection résiste, on la met en correspondance terme à terme avec une collection déjà dénombrée. Le damier liste toutes les parties de {1, …, n}, une par ligne, dans l'ordre de leur écriture binaire : une case noircie signifie « cet élément est dans la partie ».
| rang | mot | partie | correspondant |
|---|
Ce que dit la planche. Une partie de {1, …, n}, c'est exactement un mot de n lettres prises dans {0, 1}, c'est-à-dire un entier écrit en binaire entre 0 et 2n − 1 : d'où card P(E) = 2n, sans rien énumérer. Le même procédé compte les parties sans deux éléments voisins — on retrouve la suite de Fibonacci — et démontre que les parties de cardinal pair sont aussi nombreuses que celles de cardinal impair : la bascule de l'élément 1 les apparie deux à deux, et cet appariement est sa propre réciproque.
Deux ensembles sont dits équipotents s'il existe une bijection de l'un sur l'autre. La définition ne mentionne aucun nombre — et c'est ce qui la rend utilisable quand il n'y a plus de nombre à mentionner.
Trois ensembles, deux bijections f : E → F et g : F → G. Le bouton « composer » efface l'étape intermédiaire : il reste une bijection directe de E sur G.
Galilée l'avait remarqué dès 1638 : il y a « autant » de carrés parfaits que d'entiers, puisque n ↦ n² les apparie un à un — alors que les carrés se raréfient jusqu'à disparaître de la vue.
| N | éléments de l'image ⩽ N | proportion |
|---|
Ce que dit la planche. L'équipotence se comporte comme une égalité : l'identité la rend réflexive, la réciproque d'une bijection la rend symétrique, la composée de deux bijections la rend transitive. Sur les ensembles finis, elle coïncide exactement avec l'égalité des cardinaux. Sur les ensembles infinis, elle s'en détache : une partie peut être infiniment plus rare que le tout — la proportion de carrés parfaits inférieurs à N tend vers 0 — et rester pourtant en bijection avec lui. La rareté et l'équipotence sont deux mesures différentes, et l'infini les sépare.
Comment comparer deux ensembles infinis dont aucune bijection n'est visible ? Le théorème de Cantor-Bernstein répond : s'il existe une injection de E dans F et une injection de F dans E, alors E et F sont équipotents — et la bijection se construit explicitement, en suivant les chaînes.
Prenons f(n) = 2n de ℕ dans ℕ et g(n) = 3n de ℕ dans ℕ : deux injections, aucune surjective. La construction partage ℕ en deux : les entiers issus de la chaîne des « sans antécédent par g » — on leur applique f — et tous les autres, à qui l'on applique g−1. Le résultat est une seule application, bijective.
Dernière conséquence, spectaculaire : la droite réelle tout entière est équipotente à un segment ouvert de longueur 2. L'application φ(x) = x / (1 + |x|) replie ℝ dans ]−1 ; 1[ sans jamais coller deux points ni atteindre les bords.
Ce que dit la planche. Cantor-Bernstein transforme deux inégalités en égalité : si E s'injecte dans F et F dans E, alors E et F sont équipotents. La démonstration n'est pas une formule magique, c'est un découpage : on suit chaque élément à rebours, on regarde si la remontée s'arrête faute d'antécédent, et l'on choisit en conséquence f ou g−1. Appliqué aux réels, il donne d'un coup l'équipotence de ℝ, de ]−1 ; 1[, de [0 ; 1] et de n'importe quel intervalle non réduit à un point : la longueur n'a rien à voir avec le nombre de points.