Parties d'un ensemble
En mathématiques, la notion d’ensemble est première. Si l’on suit le raisonnement du mathématicien allemand Richard Dedekind, elle est même antérieure à celle d’entier naturel ! En effet, 0 est le cardinal de l’ensemble vide, 1 est celui de l’ensemble qui ne possède qu’un élément, etc.
Une notion qui en découle est celle de sous-ensemble, ou partie.
La théorie des ensembles s’appuie sur l’axiomatique de Zermelo-Fraenkel (ZF) dont l’un des axiomes stipule que pour tout ensemble, il existe son ensemble de parties. C’est à celui-ci que nous nous intéresserons ici, en nous limitant aux ensembles finis.
Sous-ensembles
Un ensemble contenu dans un autre est une partie de celui-ci. Par exemple, l’ensemble des Européens contient le sous-ensemble des Français, celui des Espagnols, celui des Belges, etc. Il contient même celui des Prussiens (ensemble vide).
Des éléments peuvent appartenir à plusieurs parties (dans notre exemple, les Européens possédant la double nationalité).
Ensemble des parties
L’ensemble des parties d’un ensemble fini \(E\) est celui des sous-ensembles de \(E\) ayant successivement 0, 1, 2, …, \(n\) éléments.
Il a existé de nombreuses façons de le noter. Nous utiliserons \(\mathcal{P}(E)\) (on lit P de E).
Si \(E = \{a\}\) alors \(\mathcal{P}(E)\) admet comme éléments \(\{\varnothing\}\) et \(\{a\}.\)
Si \(E = \{a,b\},\) \(\mathcal{P}(E)\) \(=\) \(\{\{\varnothing\} , \{a\}, \{b\}, \{a,b\} \}\)
D’une façon plus générale…
Si \(E\) contient \(n\) éléments : \(a_1,\) \(a_2,\) … \(a_n.\)
- \(\mathcal{P}(E)\) contient l’ensemble vide \(\{\varnothing\}.\)
- \(\mathcal{P}(E)\) contient les ensembles à un élément : \(\{a_1\},\) \(\{a_2\},\) …, \(\{a_n\}.\)
- \(\mathcal{P}(E)\) contient les ensembles à deux éléments : \(\{a_1, a_2\},\) \(\{a_1, a_3\},\) …, \(\{a_{n-1},a_n\}.\)
- …
- \(\mathcal{P}(E)\) contient les ensembles à \(p\) éléments : \(\{a_1, a_2, … a_p\},\) …, \(\{a_{n-p+1},… a_n\}.\)
- Et enfin \(\{E\},\) élément de lui-même.
Remarquons que l’ensemble des parties d’un ensemble \(E\) contient toujours deux éléments remarquables : l’ensemble vide et \(\{E\}.\)
Mais attention à une petite subtilité. Les sous-ensembles obtenus sont en fait les éléments de \(P(E).\) Il s’ensuit que si \(E\) est l’ensemble vide, alors \(\mathcal{P}(E) = \{\varnothing\}.\)
Ainsi \(\mathcal{P}(E)\) ne peut jamais être vide. \(\mathcal{P}(E) \ne \varnothing.\)
Dans le même ordre d’idée, la notation \(A \subset E\) a la même signification que \(A \in \mathcal{P}(E).\)
Exemple
Prenons l’exemple d’une société \(S\) de location de voitures possédant trois agences : Paris (\(P\)), Bruxelles (\(B\)) et Lyon (\(L\)).
L’ensemble des parties est \(\mathcal{P}(S)\) \(=\) \(\{\{\varnothing\},\) \(\{P\},\) \(\{B\},\) \(\{L\},\) \(\{P,B\},\) \(\{P,L\},\) \(\{B,L\},\) \(\{P,B,L\}\}.\)
Éventuellement, chacune d’elles peut être caractérisée concrètement (\(\{B, L\}\) : ferment à 22 h…) mais ce n’est pas notre propos !
Nombre de parties
Réécrivons ce que nous avons détaillé en extension avec \(E\) contenant \(n\) éléments.
- L’ensemble vide : un élément.
- \(n\) ensembles à un élément, que l’on peut écrire \(\left( {\begin{array}{*{20}{c}} n\\ 1 \end{array}} \right)\) ou \(C_n^1.\)
- Le nombre d’ensembles à \(p\) éléments s’établit à \(\left( {\begin{array}{*{20}{c}} n\\ p \end{array}} \right)\).
- Jusqu’à l’ensemble \(E\) lui-même, soit \(\left( {\begin{array}{*{20}{c}} n\\ n \end{array}} \right)\).
Ainsi, le cardinal de l’ensemble des parties de \(E\) est égal à la somme de combinaisons :
\(1 + \left( {\begin{array}{*{20}{c}} n\\ 1 \end{array}} \right)\) \(+\) … \(+\) \(\left( {\begin{array}{*{20}{c}} n\\ p \end{array}} \right)\) \(+\) … \(+\) \(\left( {\begin{array}{*{20}{c}} n\\ n \end{array}} \right)\).
Or, d’après la formule du binôme de Newton, cette somme vaut \(2^n.\)
On peut aussi le démontrer par récurrence.
Le nombre de parties qu’il est possible de constituer avec un ensemble de \(n\) éléments est \(2^n.\) On le vérifie d’ailleurs sur l’exemple vu plus haut : \(S\) était constitué de trois éléments et \(\mathcal{P}(S)\) de huit (soit \(2^3\)).
Ensembles de parties de parties
On pourrait aussi chercher \(\mathcal{P}(\mathcal{P}(E)).\) Prenons juste le cas d'un singleton.
\(E = \{a\}\)
\(\mathcal{P}(E)\) admet comme éléments \(\{\varnothing\}\) et \(\{a\}\) comme nous l’avons vu.
\(\mathcal{P}(\mathcal{P}(E))\) \(=\) \(\{\{\varnothing\}, \{\{\varnothing\}\}, \{\{a\}\}, \{\{\varnothing\}, \{a\}\}\}.\)
Opérations
Les opérations sur \(\mathcal{P}(E)\) sont l’union, l’intersection et le complémentaire.
Pour tout élément \(A\) de \(\mathcal{P}(E)\) le complémentaire de \(A\) dans \(E\) s’écrit \(\overline{A}.\)
Ces opérations sont détaillées en page d’ensemble mais aussi en page d’algèbre de Boole puisque \(\mathcal{P}(E)\) en constitue un bel exemple. Il est d’ailleurs très simple de passer de la théorie des ensembles à l’algèbre de Boole, plus pratique à manipuler.
