Ensemble des parties d'un ensemble

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, si S désigne un ensemble, l'ensemble des parties de S, noté , P(S) ou 2^S, est l'ensemble de tous les sous-ensembles de S. Dans la théorie axiomatique des ensembles, sous-tendue notamment par les axiomes ZFC, l'existence d'un tel ensemble est postulée par l'axiome de l'ensemble des parties. On appelle famille d'ensembles sur S tout sous-ensemble F de P(S).

Par exemple, si S est formé par les éléments a, b et c — on note S = {a, b, c} —, alors la liste complète des sous-ensembles de S est la suivante :

• { } (l'ensemble vide)
• {a}
• {b}
• {c}
• {a, b}
• {a, c}
• {b, c}
• {a, b, c}

L'ensemble des parties de l'ensemble S est donc donné comme suit :

Si S est un ensemble de cardinal fini noté |S| = n éléments, alors P(S) contient |P(S)| = 2ⁿ éléments. On peut représenter — et cela est parfois le cas en informatique — les éléments de P(S) par des nombres codés sur n-bits ; le n-ième bit dénote la présence ou l'absence de l'élément n de S. On dénombre ainsi 2ⁿ possibilités de codage, chaque possibilité correspondant à un élément de P(S).

On peut aussi considérer l'ensemble des parties d'ensembles infinis. L'argument de la diagonale de Cantor permet de montrer que l'ensemble des parties d'un ensemble (infini ou non) a une cardinalité strictement supérieure à celle de l'ensemble de référence. Informellement, l'ensemble des parties d'un ensemble est donc plus « grand » que l'ensemble originel. Par exemple, on peut mettre en correspondance l'ensemble des parties de l'ensemble des entiers naturels avec l'ensemble des nombres réels (voir puissance du continu).

L'ensemble des parties de l'ensemble S, muni des opérations d'union, d'intersection et de complémentation, forme l'exemple typique d'une algèbre booléenne. En fait, on peut montrer 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 d'un ensemble des parties d'un ensemble.

L'ensemble des parties de l'ensemble S forme un groupe abélien lorsqu'il est muni de l'opération de différence symétrique (l'ensemble vide constitue l'unité ; chaque sous-ensemble est aussi son propre inverse) et 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 des deux opérations précédentes, forme un anneau commutatif.

[modifier] Notation 2^S

En théorie des ensembles, X^Y désigne l'ensemble des fonctions de Y dans X. Comme 2 peut être défini par {0, 1} (voir à ce sujet l'article sur les entiers naturels), 2^S peut désigner l'ensemble des fonctions de S dans {0, 1}.

En associant une fonction de 2^S avec l'ensemble-antécédent correspondant de 1, on peut noter une bijection entre 2^S et , où chaque fonction est la fonction caractéristique du sous-ensemble de avec lequel il a été identifié.

En terme de théorie des ensembles, 2^S et peuvent donc être considérés comme identiques.