- Ensemble des parties d'un ensemble
-
En mathématiques, l'ensemble des parties d'un ensemble désigne l'ensemble des sous-ensembles de cet ensemble.
Sommaire
Définition
Soit E un ensemble. L'ensemble des parties de E est :
.
Il est noté
, P(E), 2E, ou encore 
(écriture gothique).Dans la théorie des ensembles, de Zermelo et celle de Zermelo-Fraenkel, l'existence, pour tout ensemble E, d'un tel ensemble est postulée par l'axiome de l'ensemble des parties.
Propriétés
Cardinalité
Cardinalité finie
Soit E un ensemble à n éléments. Alors, l'ensemble
des parties de E est fini, et a 2n éléments.DémonstrationLa démonstration repose sur une récurrence sur le cardinal n.
- L'ensemble vide a un seul sous-ensemble : lui-même. (ce qui établit la propriété pour n=0, on a bien 20 = 1)
- Supposons que nous avons établi la propriété pour un ensemble de m éléments. Soit E un ensemble ayant n=m+1 éléments, il est donc non vide, soit a un élément de E. Les sous-ensembles de E se divisent en deux parties disjointes : celles des sous-ensembles auxquels a n'appartient pas, et celle des sous-ensembles auxquels a appartient. Par hypothèse de récurrence, la première partie a 2m éléments. C'est le cas pour la seconde également, puisqu'elle est en bijection avec la première, par l'opération qui consiste à ajouter/ôter a. Nous avons donc au total, 2 * 2m = 2m + 1 = 2n sous-ensembles. Par conséquent, la propriété est établie pour n=m+1 éléments.
Nous avons donc bien prouvé que l'ensemble des parties de E a 2n éléments, pour n=0 et par récurrence, pour tous les successeurs de 0.
Démonstration pour les informaticiensUn vecteur de n bits peut prendre 2n valeurs différentes, et chacun de ses bits peut prendre la valeur Vrai ou Faux. Posons E, un ensemble de n éléments. Spécifions que l’état de chaque bits représente l’absence ou la présence d’un élément de E dans le sous ensemble représenté par un vecteur de bits de longueur n : ceci constitue une représentation valide du contenu d’un sous ensemble de E, sous la condition que le cardinal de E ne soit pas infini. Chaque combinaison de bits représente le contenu d’un sous ensemble, et nous avons comme avec tout nombre binaire ou vecteur de bits, 2n combinaisons possibles, qui s’interprètent comme autant de 2n sous ensemble de E possibles, pour E, un ensemble dont le cardinal n’est pas infini.
Cardinalité infinie
On a pour tout entier naturel n, n < 2n. 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 (fini ou non) a une cardinalité strictement supérieure à celle de l'ensemble de départ : 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 (x2=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).
Exemples
Soit E = {a,b,c} un ensemble de trois éléments. Les sous-ensembles de E sont :
, l'ensemble vide- {a}
- {b}
- {c}
- {a,b}
- {a,c}
- {b,c}
- E = {a,b,c}
L'ensemble des parties de E est donc :
.
On vérifie au passage que l'on a bien
.Notation exponentielle
En théorie des ensembles, XY désigne l'ensemble des fonctions de Y dans X. Comme 2 peut être défini comme l'ensemble {0, 1} dans la construction des entiers naturels de von Neumann, 2E peut désigner l'ensemble des fonctions de E dans {0, 1}.
En associant une fonction de 2E avec l'ensemble antécédent de 1 par cette fonction, on établit une bijection immédiate entre 2E et
, où chaque fonction est la fonction caractéristique du sous-ensemble de avec lequel il a été mis en correspondance.Il peut donc arriver que l'on identifie 2E et
.Voir aussi
Liens internes
Liens externes
- (en) Power Set (MathWorld)
Catégories :- Algèbre
- Système d'ensembles
- Théorie des ensembles
Wikimedia Foundation. 2010.
