L'ensemble des parties P(E) et les fonctions indicatrices
L'ensemble des parties P(E) réunit tous les sous-ensembles de E, de ∅ jusqu'à E lui-même. Pour le manipuler, on remplace chaque partie A par sa fonction indicatrice 1A, qui vaut 1 sur A et 0 ailleurs. Les parties deviennent des suites de 0 et de 1, les opérations ensemblistes deviennent des calculs, et compter les éléments revient à faire une somme. Cette page fait voir cette traduction, l'utilise pour démontrer et pour dénombrer, et la suit jusqu'à l'intégrale de Lebesgue, aux codes correcteurs d'erreurs et au calcul des probabilités.
Vue d'ensemble
Pour un ensemble E, la fonction indicatrice d'une partie A est l'application 1A : E → {0, 1} définie par 1A(x) = 1 si x ∈ A et 1A(x) = 0 sinon. L'application A ↦ 1A est une bijection de P(E) sur l'ensemble {0, 1}E des fonctions de E dans {0, 1}. On note d'ailleurs souvent P(E) ≅ 2E. Si E a n éléments, P(E) en a donc 2n.
| Côté ensembles | Côté indicatrices |
|---|---|
| A ⊆ B | 1A ⩽ 1B en tout point |
| A ∩ B | 1A · 1B = min(1A, 1B) |
| A ∪ B | 1A + 1B − 1A1B = max(1A, 1B) |
| ∁A | 1 − 1A |
| A Δ B | (1A − 1B)² = 1A + 1B modulo 2 |
| card A (E fini) | Σx∈E 1A(x) |
| longueur, probabilité de A | ∫ 1A, et l'espérance E[1A] = P(A) |
Une partie est une fonction
Choisir une partie, c'est répondre oui ou non pour chaque élément.
Pour fabriquer une partie A de E = {1, …, n}, on passe en revue les éléments un par un et l'on décide pour chacun s'il entre dans A. Il y a n décisions à deux issues, donc 2n parties. La suite des réponses est la fonction indicatrice 1A. Lue comme un nombre écrit en base 2, avec l'élément k pour chiffre de poids 2k−1, elle donne un numéro entre 0 et 2n − 1. Le bouton « Parcourir P(E) » visite toutes les parties en ne changeant qu'un seul élément à chaque pas. C'est le code de Gray, un chemin qui passe une fois par chaque sommet du cube {0, 1}n. Cliquez sur les jetons pour composer A.
Les opérations deviennent du calcul
Intersection, réunion, complémentaire : un produit, une somme, une soustraction.
Comme 1A(x) et 1B(x) valent 0 ou 1, le produit 1A(x)·1B(x) vaut 1 exactement quand x est dans A et dans B : c'est 1A∩B. De même, 1 − 1A = 1∁A, et 1A + 1B − 1A1B = 1A∪B. Démontrer une loi ensembliste revient alors à faire un calcul algébrique. Pour De Morgan, 1 − ab = (1 − a) + (1 − b) − (1 − a)(1 − b) est une identité vraie pour tous les nombres a et b. D'autres lois demandent la règle propre aux indicatrices, a² = a (puisque 0² = 0 et 1² = 1). La distributivité de ∩ sur ∪ est dans ce cas. La page vérifie chaque formule élément par élément, puis sur toutes les parties d'un ensemble à six éléments.
Compter avec les indicatrices
card A = Σ 1A(x), et l'on peut sommer dans l'ordre qu'on veut.
Quelle est la somme des cardinaux de toutes les parties de E, avec card E = n ? Écrivons le tableau dont les lignes sont les parties A, les colonnes les éléments x, et la case 1A(x). En sommant ligne par ligne, on additionne les cardinaux. En sommant colonne par colonne, chaque élément x appartient à exactement la moitié des parties, soit 2n−1. On obtient donc Σ card A = n·2n−1 sans aucun calcul de coefficient binomial. C'est le principe du double comptage, et les indicatrices le rendent automatique. On montre de la même façon que Σ card(A ∩ B) = n·4n−1 sur tous les couples, et l'on retrouve la formule d'inclusion-exclusion en développant 1A∪B∪C = 1 − (1 − 1A)(1 − 1B)(1 − 1C).
Fonctions étagées : l'intégrale de Lebesgue avec des indicatrices
Toute fonction positive est la limite de sommes d'indicatrices.
Une fonction étagée est une combinaison c₁1A₁ + … + ck1Ak, et son intégrale vaut c₁·mes(A₁) + … + ck·mes(Ak). Lebesgue approche une fonction f ⩾ 0 en découpant non pas l'axe des x, mais celui des valeurs. Au niveau n, on empile des tranches horizontales d'épaisseur 2−n : φₙ = 2−n Σk 1{f ⩾ k·2−n}, ce qui revient à arrondir f par défaut au multiple de 2−n. L'intégrale de φₙ est donc 2−n Σ mes{f ⩾ k·2−n}, une somme de longueurs d'ensembles de niveau. Quand n augmente, φₙ monte vers f, et son intégrale vers ∫ f.
Signature : une partie de ℕ est un réel, un code qui corrige les erreurs, l'espérance par les indicatrices
Trois usages des indicatrices hors de la théorie des ensembles.
Une partie A de ℕ* = {1, 2, 3, …} a pour indicatrice une suite infinie de 0 et de 1. Lue après une virgule en base 2, elle donne un réel x(A) = Σn∈A 2−n de [0 ; 1]. Les nombres pairs donnent 0,0101…₂ = 1/3. Les nombres premiers donnent la constante des nombres premiers 0,4146825… Cette application de P(ℕ*) sur [0 ; 1] est surjective, et c'est ainsi qu'on voit que P(ℕ) a la puissance du continu. Elle n'est pourtant pas tout à fait injective : {1} et {2, 3, 4, …} donnent tous deux 1/2, car 0,1000…₂ = 0,0111…₂. Seuls les réels dyadiques ont deux antécédents, et il n'y en a qu'une infinité dénombrable. Cliquez sur les cases pour composer A.
Muni de la différence symétrique, P(E) est un espace vectoriel sur {0, 1}, et card(A Δ B) mesure le nombre de cases où 1A et 1B diffèrent : c'est la distance de Hamming. Le code de Hamming (1950) choisit 16 parties de E = {1, …, 7}, deux à deux à distance au moins 3. On transmet l'une d'elles. Si un seul élément est ajouté ou retiré en route, la partie reçue reste plus proche de la partie envoyée que de toutes les autres, et l'on corrige l'erreur. On peut aussi trouver la position fautive par le syndrome : on combine par OU exclusif les numéros des positions présentes, et le résultat donne directement la position de l'erreur. Choisissez un message de 4 bits, puis cliquez sur une case pour simuler une erreur.
On mélange n cartes numérotées. Combien, en moyenne, restent à leur place ? Le nombre X de points fixes s'écrit comme une somme d'indicatrices : X = 1A₁ + … + 1Aₙ, où Ai est l'événement « la carte i est à sa place ». L'espérance d'une indicatrice est la probabilité de l'événement, ici 1/n, et l'espérance d'une somme est la somme des espérances, même quand les événements ne sont pas indépendants. Donc E[X] = n × 1/n = 1, quel que soit n. Avec les produits 1Ai1Aj = 1Ai∩Aj, on trouve de même E[X²] = 2, donc une variance égale à 1.
Une brève histoire
En résumé
Partie = fonction
A ↦ 1A est une bijection de P(E) sur {0, 1}E ; si card E = n, P(E) a 2n éléments.
Opération = calcul
∩ devient un produit, ∁ une soustraction, ∪ une somme corrigée, Δ une addition modulo 2 ; les lois se démontrent en calculant, avec la règle a² = a.
Compter = sommer
Cardinal, longueur, probabilité : on somme ou on intègre une indicatrice, et l'on peut échanger l'ordre des sommes, ce qui donne le double comptage et l'espérance des sommes.
Pour aller plus loin
Le théorème de Cantor dit qu'il n'existe aucune surjection de E sur P(E) : la partie {x : x ∉ f(x)} n'est jamais atteinte. En termes d'indicatrices, c'est l'argument diagonal : 1D(x) = 1 − 1f(x)(x).
Les fonctions caractéristiques : en analyse, on dit « fonction caractéristique » ; en probabilités, ce nom désigne autre chose (la transformée de Fourier d'une loi), d'où la préférence pour « indicatrice ».
Liens. Les sous-ensembles et l'inclusion (diagramme de Hasse de P(A)), les opérations sur les ensembles, la combinatoire, l'algèbre de Boole, les probabilités, l'analyse (Riemann et Lebesgue).