Ensemble des parties d'un ensemble

En mathématiques, l'ensemble des parties d'un ensemble, parfois appelé ensemble puissance, est l'ensemble de tous les sous-ensembles d'un ensemble donné (y compris cet ensemble lui-même et l'ensemble vide).

Définition

Soit $E$ un ensemble. L'ensemble des parties de $E$ est l'ensemble, généralement noté ${\mathcal {P}}(E)$ , dont les éléments sont les sous-ensembles de $E$ :

A\in {\mathcal {P}}(E)\Longleftrightarrow A\subseteq E

Il est également parfois noté $P(E)$ , $2^{E}$ ou ${\mathfrak {P}}(E)$ (gothique), ou encore $\wp (E)$ (P de Weierstrass).

Dans la théorie des ensembles de Zermelo, l'existence, pour tout ensemble $E$ , d'un tel ensemble ${\mathcal {P}}(E)$ , est postulée par l'axiome de l'ensemble des parties, et son unicité résulte de l'axiome d'extensionnalité.

Propriétés

Cardinalité

${\mathcal {P}}(E)$ n'est jamais vide car l'ensemble vide $\varnothing$ et $E$ sont toujours des parties de $E$ : $\varnothing \in {\mathcal {P}}(E)$ , $E\in {\mathcal {P}}(E)$ .

Si deux ensembles E et F sont équipotents alors ${\mathcal {P}}(E)$ et ${\mathcal {P}}(F)$ le sont aussi.

Cardinalité finie

Soit $E$ un ensemble fini à n éléments. Alors, l'ensemble ${\mathcal {P}}(E)$ des parties de E est fini, et a 2ⁿ éléments.

Démonstration par récurrence

La propriété est vraie au rang 0 car l'ensemble vide a bien un seul sous-ensemble : lui-même. On suppose la propriété vraie au rang n. Soit E un ensemble ayant n + 1 éléments ; il est donc non vide ; soit a un élément de E. Les sous-ensembles de E se répartissent en deux classes : celle des sous-ensembles auxquels a appartient, et celle des sous-ensembles auxquels a n'appartient pas. La seconde classe a 2ⁿ éléments par hypothèse de récurrence ; la première également, puisqu'elle est en bijection avec la seconde, par l'opération qui consiste à ôter a. L'ensemble des parties de E a donc 2ⁿ + 2ⁿ = 2ⁿ⁺¹ éléments.

Démonstration via les n-uplets de bits

Sans perte de généralité, l'ensemble E à n éléments peut être supposé égal à {1, …, n}. Une bijection canonique (voir infra) montre alors que le cardinal de ${\mathcal {P}}(E)$ est égal à celui de l'ensemble de n-uplets $\{0,1\}^{n}$ , c'est-à-dire (cf. « Arrangement avec répétition ») à 2ⁿ.

Démonstration par la formule du binôme

Il y a ${n \choose k}$ parties de E contenant k éléments (k entre 0 et n) donc d'après la formule du binôme : $|{\mathcal {P}}(E)|=$ $\sum _{k=0}^{n}{n \choose k}=\sum _{k=0}^{n}{n \choose k}1^{n-k}1^{k}=(1+1)^{n}=2^{n}$ .

Cardinalité infinie

Pour tout entier naturel n, on a n < 2ⁿ. Ce résultat se généralise en cardinalité infinie. Le théorème de Cantor énonce que l'ensemble des parties d'un ensemble E (fini ou non) a une cardinalité strictement supérieure à celle de E : il existe une injection d'un ensemble dans l'ensemble de ses parties (par exemple celle qui associe à un élément le singleton auquel il appartient), mais aucune bijection.

Tout ensemble qui peut être mis en bijection avec ℕ, l'ensemble des entiers naturels, est dit dénombrable. Le théorème de Cantor montre en particulier que P(ℕ) n'est pas dénombrable, ce qui peut s'interpréter en disant que l'on ne peut « numéroter » de façon exhaustive les sous-ensembles de ℕ. C'est-à-dire que, dès que l'on a une suite de sous-ensembles de ℕ indexée par les entiers, on trouve forcément un sous-ensemble de ℕ qui n'apparaît pas dans cette suite.

Quelle peut-être la cardinalité d'un ensemble de parties de ℕ, c'est-à-dire d'un sous-ensemble de P(ℕ) ? Georg Cantor pensait qu'elle ne pouvait être que finie, dénombrable, ou celle de P(ℕ). C'est l'hypothèse du continu qui n'est ni démontrable ni réfutable dans la théorie des ensembles ZFC.

Algèbre de Boole

Article détaillé : Algèbre des parties d'un ensemble.

L'ensemble des parties de l'ensemble E, muni des opérations d'union, d'intersection et de complémentation, forme un exemple typique d'algèbre de Boole. On peut montrer, en particulier que toute algèbre booléenne finie est isomorphe à l'algèbre booléenne de l'ensemble des parties d'un ensemble fini. Cela n'est pas vérifié pour les algèbres booléennes infinies, mais toute algèbre booléenne infinie est une sous-algèbre d'une algèbre booléenne de l'ensemble des parties d'un ensemble.

Comme pour toute algèbre de Boole, on peut définir une structure d'anneau, en introduisant une opération définie à partir de la réunion et de l'intersection : la différence symétrique. L'ensemble des parties de l'ensemble E muni de la différence symétrique est un groupe abélien. L'élément neutre est l'ensemble vide. Chaque sous-ensemble est son propre opposé. Ce même ensemble est un semigroupe commutatif lorsqu'il est muni de l'opération d'intersection. On peut donc montrer (en utilisant les lois de la distributivité) que l'ensemble des parties d'un ensemble, muni de la différence symétrique et de l'intersection, est un anneau commutatif dont tout élément est idempotent (x² = x, ici le produit est l'intersection), c’est-à-dire un anneau de Boole (réciproquement à tout anneau de Boole on peut associer une algèbre de Boole).

Exemple

Soit $E=\{a,b,c\}$ un ensemble de trois éléments. Les sous-ensembles de $E$ sont :

$\varnothing$ et $E$ ;
les trois singletons $\{a\}$ , $\{b\}$ et $\{c\}$ ;
les trois paires $\{a,b\}$ , $\{a,c\}$ et $\{b,c\}$ .

L'ensemble des parties de $E$ est donc :

{\mathcal {P}}(E)=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},E\}

On vérifie au passage que l'on a bien $\mathrm {card} \,{\mathcal {P}}(E)=2^{\mathrm {card} \,E}=2^{3}=8$ .

Notation exponentielle

En théorie des ensembles, X^Y désigne l'ensemble des applications de Y dans X. Comme 2 peut être défini comme l'ensemble {0, 1} dans la construction des entiers naturels de von Neumann, 2^E peut désigner l'ensemble des fonctions de E dans {0, 1}.

Il existe une bijection canonique entre 2^E et ${\mathcal {P}}(E)$ . Il peut donc arriver que l'on identifie 2^E et ${\mathcal {P}}(E)$ .