Ensemble des parties

Prenons trois objets nommés a, b et c. On peut ne rien choisir, en prendre un, en prendre deux ou garder les trois. La collection de tous ces choix est l'ensemble des parties de {a, b, c}.

Chaque objet a deux états, choisi ou non choisi. Avec trois objets, cela donne 2 × 2 × 2 = 8 sous-ensembles. Le choix vide et le choix complet en font partie : ils ne doivent pas être oubliés.

Soit E un ensemble. Son ensemble des parties, noté P(E) ou 2^E, est l'ensemble dont les éléments sont exactement tous les sous-ensembles de E. Autrement dit, pour tout ensemble A, l'appartenance à P(E) équivaut à l'inclusion dans E : $A\in \mathcal{P}(E)⟺A\subseteq EA\; \backslash in\; \backslash mathcal\{P\}(E)\; \backslash iff\; A\; \backslash subseteq\; E$. L'ensemble vide et E lui-même appartiennent donc toujours à P(E).

Si E possède un nombre fini n d'éléments, chaque élément peut être retenu ou écarté indépendamment. Le nombre de sous-ensembles est alors $\mathrm{\mid }\mathcal{P}(E)\mathrm{\mid }=2^n|\backslash mathcal\{P\}(E)|=2^n$. Cette formule compte les éléments de P(E) ; elle ne signifie pas que les sous-ensembles ont tous la même taille.

Ordonné par l'inclusion, P(E) forme un treillis complet. Pour toute famille de sous-ensembles de E, la réunion est le plus petit sous-ensemble qui les contient tous, tandis que l'intersection est le plus grand qu'ils contiennent tous. L'ensemble vide est le plus petit élément et E le plus grand. Le théorème de Cantor ajoute que, même lorsque E est infini, aucune bijection ne peut mettre E et P(E) en correspondance : P(E) a un cardinal strictement supérieur.

La construction repose sur cinq éléments liés. Le support E fixe les objets disponibles. Ses sous-ensembles sont tous les choix possibles parmi ces objets. Leur collection constitue P(E). La relation d'inclusion compare deux choix : A est inclus dans B lorsque tout élément de A appartient aussi à B. Enfin, la réunion et l'intersection combinent les sous-ensembles.

Le support détermine donc quels sous-ensembles peuvent entrer dans P(E), puis l'inclusion organise ces sous-ensembles du choix vide jusqu'au choix complet. La réunion fournit leur borne supérieure et l'intersection leur borne inférieure. Ces données suffisent à construire le treillis complet de P(E) et, lorsque E est fini, à contrôler son nombre de sommets par 2ⁿ.

On part de l'ensemble E = {a, b, c}. Les données sont ses trois éléments distincts, la possibilité de retenir ou non chacun d'eux et l'obligation de compter aussi le choix vide. L'organisation par inclusion place les sous-ensembles sur quatre niveaux, selon qu'ils contiennent zéro, un, deux ou trois éléments.

1. On écrit le sous-ensemble sans élément : ∅.

2. On écrit les trois sous-ensembles à un élément : {a}, {b} et {c}.

3. On écrit les trois sous-ensembles à deux éléments : {a, b}, {a, c} et {b, c}.

4. On ajoute le sous-ensemble à trois éléments, qui est E lui-même : {a, b, c}. On obtient donc la collection complète suivante.

Le résultat comporte 1 + 3 + 3 + 1 = 8 sous-ensembles. Le contrôle indépendant donne 2³ = 8, car chacun des trois éléments offre deux choix. Les deux comptes coïncident.

Pour dresser tous les choix possibles parmi un petit nombre d'objets, P(E) donne une liste exhaustive. Une liste directe convient si l'on peut vérifier chaque cas ; le codage « retenu ou écarté » est préférable dès qu'un oubli devient difficile à repérer.

Pour comparer des collections de choix, l'ordre par inclusion montre immédiatement lesquelles en contiennent d'autres. Un simple comptage suffit si seule la quantité importe ; le treillis est plus utile lorsque les relations entre sous-ensembles comptent aussi.

Pour combiner plusieurs sous-ensembles, la réunion rassemble tout ce qui apparaît au moins une fois et l'intersection conserve ce qui apparaît partout. Il faut choisir l'opération d'après ce critère observable, car elles répondent à deux questions différentes.

Ensemble des parties et sous-ensemble. Un sous-ensemble A est un seul choix d'éléments de E ; P(E) est la collection de tous ces choix. Avec E = {a, b, c}, {a, c} est un élément de P(E), mais n'est pas P(E).

Ensemble des parties et réunion. P(E) est un ensemble de sous-ensembles, tandis que la réunion d'une famille de sous-ensembles est un sous-ensemble de E. Pour {{a}, {b, c}}, la réunion vaut {a, b, c} ; l'ensemble des parties de E contient huit éléments.

Ensemble des parties et produit cartésien. P(E) contient des sous-ensembles de E ; un produit cartésien contient des couples ordonnés. Avec E = {a, b, c}, {a, b} appartient à P(E), alors que le couple (a, b) relève d'un produit cartésien.

Ensemble vide. Si E = ∅, il reste un sous-ensemble, l'ensemble vide lui-même. Ainsi P(∅) = {∅} possède un élément, en accord avec 2⁰ = 1. Écrire P(∅) = ∅ ferait disparaître ce choix vide.

Exposant fini. La formule « 2ⁿ sous-ensembles » suppose que E possède le nombre fini n d'éléments. Pour un ensemble infini, il faut parler de cardinal : le théorème de Cantor garantit toujours que le cardinal de P(E) est strictement supérieur à celui de E.

Inclusion et appartenance. Pour tester A ∈ P(E), il faut vérifier A ⊆ E. Le symbole d'appartenance relie A à la collection P(E), tandis que l'inclusion relie A au support E. Intervertir ces relations rend le type des objets ambigu.

Comptage incomplet. Ne compter que les sous-ensembles non vides, ou seulement les sous-ensembles propres, ne produit plus P(E). Le contrôle par niveaux doit retrouver le choix vide et E lui-même avant de totaliser 2ⁿ cas.

Le glossaire théorème de Cantor approfondit la comparaison des cardinaux qui rend P(E) strictement plus grand que E.

L'article L'ensemble et ses parties prolonge la notion dans un traitement consacré aux ensembles et à leurs parties.