Ensemble de puissance - Power set

Les éléments de l'ensemble de puissance de { x , y , z } ordonnés par rapport à l' inclusion .

En mathématiques , l' ensemble de puissance (ou powerset ) d'un ensemble S est l'ensemble de tous les sous - ensembles de S , dont l' ensemble vide et S elle - même. Dans la théorie des ensembles axiomatique (comme développé, par exemple, dans les axiomes ZFC ), l'existence de l'ensemble de puissance de tout ensemble est postulée par l' axiome de l'ensemble de puissance . L'ensemble de puissances de S est noté de diverses manières P ( S ) , ( S ) , P ( S ) , , ( S ) (en utilisant le " Weierstrass p ") ou 2 ^S . La notation 2 ^S , signifiant l'ensemble de toutes les fonctions de S à un ensemble donné de deux éléments (par exemple, {0, 1}), est utilisée parce que l'ensemble de puissance de S peut être identifié avec, équivalent ou bijectif à l'ensemble de toutes les fonctions de S à l'ensemble de deux éléments donné. ${\displaystyle \mathbb {P} (S)}$

Tout sous - ensemble de P ( S ) est appelé une famille de jeux sur S .

Exemple

Si S est l'ensemble { x , y , z } , alors tous les sous-ensembles de S sont

• {} (également noté ou , l' ensemble vide ou l'ensemble nul)${\displaystyle \varnothing }$${\displaystyle \emptyset }$
• { x }
• { y }
• { z }
• { x , y }
• { x , z }
• { y , z }
• { x , y , z }

et donc l'ensemble de puissance de S est {{}, { x }, { y }, { z }, { x , y }, { x , z }, { y , z }, { x , y , z }} .

Propriétés

Si S est un ensemble fini de cardinal | S | = n (c'est-à-dire que le nombre de tous les éléments de l'ensemble S est n ), alors le nombre de tous les sous-ensembles de S est | P ( S )| = 2 ⁿ . Ce fait ainsi que la raison de la notation 2 ^S désignant l'ensemble de puissance P ( S ) sont démontrés ci-dessous.

Une fonction indicatrice ou une fonction caractéristique d'un sous-ensemble A d'un ensemble S de cardinalité | S | = n est une fonction de S vers l'ensemble de deux éléments {0, 1}, noté I _A : S → {0, 1}, et il indique si un élément de S appartient ou non à A ; Si x dans S appartient à A , alors I _A ( x ) = 1, et 0 sinon. Chaque sous-ensemble A de S est identifié par ou équivalent à la fonction indicatrice I _A , et {0, 1} ^S comme l'ensemble de toutes les fonctions de S à {0, 1} se compose de toutes les fonctions indicatrices de tous les sous-ensembles de S . En d'autres termes, {0, 1} ^S est équivalent ou bijectif à l'ensemble de puissance P ( S ) . Puisque chaque élément de S correspond à 0 ou 1 sous n'importe quelle fonction dans {0, 1} ^S , le nombre de toutes les fonctions dans {0, 1} ^S est 2 ⁿ . Puisque le nombre 2 peut être défini comme {0,1} (voir, par exemple, les ordinaux de von Neumann ), le P ( S ) est également noté 2 ^S . Évidemment | 2 ^S | = 2 ^{| S |} tient. D'une manière générale, X ^Y est l'ensemble de toutes les fonctions de Y à X et | X ^Y | = | X | ^{| Y |} .

L'argument diagonal de Cantor montre que l'ensemble de puissance d'un ensemble (qu'il soit infini ou non) a toujours une cardinalité strictement plus élevée que l'ensemble lui-même (ou de manière informelle, l'ensemble de puissance doit être plus grand que l'ensemble d'origine). En particulier, le théorème de Cantor montre que l'ensemble de puissance d'un ensemble dénombrable infini est indénombrable infini. L'ensemble de puissance de l'ensemble des nombres naturels peut être mis en correspondance biunivoque avec l'ensemble des nombres réels (voir Cardinalité du continuum ).

L'ensemble puissance d'un ensemble S , ainsi que les opérations d' union , d' intersection et de complément , peuvent être considérés comme l'exemple prototypique d'une algèbre booléenne . En fait, on peut montrer que toute finie algèbre de Boole est isomorphe à l'algèbre booléenne de l'ensemble de puissance d'un ensemble fini. Pour les algèbres booléennes infinies , ce n'est plus vrai, mais chaque algèbre booléenne infinie peut être représentée comme une sous - algèbre d'un ensemble de puissance algèbre booléenne (voir le théorème de représentation de Stone ).

L'ensemble de puissance d'un ensemble S forme un groupe abélien lorsqu'il est considéré avec l'opération de différence symétrique (avec l'ensemble vide comme élément d'identité et chaque ensemble étant son propre inverse), et un monoïde commutatif lorsqu'il est considéré avec l'opération d'intersection . On peut donc montrer, en prouvant les lois de distribution , que l'ensemble des puissances considéré avec ces deux opérations forme un anneau booléen .

Représenter des sous-ensembles sous forme de fonctions

En théorie des ensembles , X ^Y est la notation qui représente l'ensemble de toutes les fonctions de Y à X . Comme "2" peut être défini comme {0,1} (voir, par exemple, les ordinaux de von Neumann ), 2 ^S (c'est-à-dire {0,1} ^S ) est l'ensemble de toutes les fonctions de S à {0,1} . Comme indiqué ci-dessus , 2 ^S et l'ensemble de puissance de S , P ( S ) , sont considérés comme identiques en théorie des ensembles.

Cette équivalence peut être appliquée à l' exemple ci - dessus , dans lequel S = { x , y , z } , pour obtenir l' isomorphisme avec les représentations binaires des nombres de 0 à 2 ⁿ − 1 , avec n étant le nombre d'éléments dans l'ensemble S ou | S | = n . Premièrement, l'ensemble énuméré { ( x , 1), ( y , 2), ( z , 3) } est défini dans lequel le nombre dans chaque paire ordonnée représente la position de l'élément apparié de S dans une séquence de chiffres binaires tels comme { x , y } = 011 ₍₂₎ ; x de S est situé au premier à partir de la droite de cette séquence et y est au deuxième à partir de la droite, et 1 dans la séquence signifie que l'élément de S correspondant à la position de celui-ci dans la séquence existe dans le sous-ensemble de S pour la séquence alors que 0 signifie que non.

Pour l'ensemble des puissances de S , on obtient :

Un tel mappage bijectif de P ( S ) aux entiers est arbitraire, donc cette représentation de tous les sous-ensembles de S n'est pas unique, mais l'ordre de tri de l'ensemble énuméré ne change pas sa cardinalité. (Par exemple, { ( y , 1), ( z , 2), ( x , 3) } peut être utilisé pour construire un autre bijectif de P ( S ) aux entiers sans changer le nombre de correspondances bijectives .)

Cependant, une telle représentation binaire finie n'est possible que si S peut être énuméré. (Dans cet exemple, x , y et z sont énumérés avec 1, 2 et 3 respectivement comme position des séquences de chiffres binaires.) L'énumération est possible même si S a une cardinalité infinie (c'est-à-dire le nombre d'éléments dans S est infini), comme l'ensemble des entiers ou des rationnels, mais pas possible par exemple si S est l'ensemble des nombres réels, auquel cas on ne peut pas énumérer tous les nombres irrationnels.

Relation avec le théorème du binôme

Le théorème du binôme est étroitement lié à l'ensemble des puissances. Une combinaison de k éléments d'un ensemble est un autre nom pour un sous-ensemble de k éléments, donc le nombre de combinaisons , noté C( n , k ) (également appelé coefficient binomial ) est un nombre de sous-ensembles avec k éléments dans un ensemble avec n éléments ; en d'autres termes c'est le nombre d'ensembles à k éléments qui sont des éléments de l'ensemble puissance d'un ensemble à n éléments.

Par exemple, l'ensemble de puissance d'un ensemble à trois éléments, a :

• C(3, 0) = 1 sous-ensemble avec 0 éléments (le sous-ensemble vide),
• C(3, 1) = 3 sous-ensembles avec 1 élément (les sous-ensembles singleton),
• C(3, 2) = 3 sous-ensembles avec 2 éléments (les compléments des sous-ensembles singleton),
• C(3, 3) = 1 sous-ensemble avec 3 éléments (l'ensemble original lui-même).

En utilisant cette relation, nous pouvons calculer en utilisant la formule : ${\textstyle \left|2^{S}\right|}$

$${\displaystyle \left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}}$$

On peut donc en déduire l'identité suivante, en supposant : ${\textstyle |S|=n}$

$${\displaystyle \left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}}$$

Définition récursive

Si est un ensemble fini , alors une définition récursive de procède comme suit : ${\style d'affichage S}$${\style d'affichage P(S)}$

• Si , alors .${\style d'affichage S=\{\}}$${\style d'affichage P(S)=\{\,\{\}\,\}}$
• Sinon, laissez et ; alors .${\displaystyle e\in S}$${\displaystyle T=S\setminus \{e\}}$${\displaystyle P(S)=P(T)\cup \{t\cup \{e\}:t\in P(T)\}}$

Dans les mots:

• L'ensemble de puissance de l' ensemble vide est un singleton dont le seul élément est l'ensemble vide.
• Pour un ensemble non vide , soit n'importe quel élément de l'ensemble et son complément relatif ; alors l'ensemble de puissance de est une union d'un ensemble de puissance de et d'un ensemble de puissance dont chaque élément est développé avec l' élément.${\style d'affichage S}$${\style d'affichage e}$${\style d'affichage T}$${\style d'affichage S}$${\style d'affichage T}$${\style d'affichage T}$${\style d'affichage e}$

Sous-ensembles de cardinalité limitée

L'ensemble des sous - ensembles de S de cardinalité inférieure ou égale à κ est parfois désigné par P _de ( S ) ou [ S ] ^κ , et l'ensemble des sous - ensembles avec cardinalité strictement inférieur à κ est parfois notée P _<κ ( S ) ou [ S ] ^<κ . De même, l'ensemble des sous-ensembles non vides de S pourrait être noté P ₁ ( S ) ou P ⁺ ( S ) .

Objet de puissance

Un ensemble peut être considéré comme une algèbre n'ayant pas d'opérations non triviales ou d'équations définissant. Dans cette perspective, l'idée de l'ensemble puissance de X comme l'ensemble des sous-ensembles de X se généralise naturellement aux sous-algèbres d'une structure algébrique ou algèbre.

L'ensemble de puissance d'un ensemble, lorsqu'il est ordonné par inclusion, est toujours une algèbre booléenne atomique complète, et chaque algèbre booléenne atomique complète apparaît comme le réseau de tous les sous-ensembles d'un ensemble. La généralisation aux algèbres arbitraires est que l'ensemble des sous-algèbres d'une algèbre, à nouveau ordonné par inclusion, est toujours un réseau algébrique , et chaque réseau algébrique apparaît comme le réseau de sous-algèbres d'une algèbre. Donc, à cet égard, les sous-algèbres se comportent de manière analogue aux sous-ensembles.

Cependant, il existe deux propriétés importantes des sous-ensembles qui ne s'appliquent pas aux sous-algèbres en général. Premièrement, bien que les sous-ensembles d'un ensemble forment un ensemble (ainsi qu'un réseau), dans certaines classes, il peut ne pas être possible d'organiser les sous-algèbres d'une algèbre comme elle-même une algèbre dans cette classe, bien qu'elles puissent toujours être organisées comme un treillis. Deuxièmement, alors que les sous-ensembles d'un ensemble sont en bijection avec les fonctions de cet ensemble à l'ensemble {0,1} = 2, il n'y a aucune garantie qu'une classe d'algèbres contienne une algèbre qui puisse jouer le rôle de 2 de cette manière .

Certaines classes d'algèbres jouissent de ces deux propriétés. La première propriété est plus courante, le cas d'avoir les deux est relativement rare. Une classe qui possède les deux est celle des multigraphes . Étant donné deux multigraphes G et H , un homomorphisme h : G → H consiste en deux fonctions, l'une mappant des sommets sur des sommets et l'autre des arêtes sur des arêtes. L'ensemble H ^G des homomorphismes de G à H peut alors être organisé comme le graphe dont les sommets et les arêtes sont respectivement les fonctions de sommet et d'arête apparaissant dans cet ensemble. De plus, les sous-graphes d'un multigraphe G sont en bijection avec les homomorphismes de graphe de G au multigraphe Ω définissable comme le graphe orienté complet sur deux sommets (donc quatre arêtes, à savoir deux auto-boucles et deux autres arêtes formant un cycle) augmentées de une cinquième arête, à savoir une seconde auto-boucle à l'un des sommets. On peut donc organiser les sous-graphes de G comme le multigraphe Ω ^G , appelé l' objet puissance de G .

La particularité d'un multigraphe en tant qu'algèbre est que ses opérations sont unaires. Un multigraphe a deux sortes d'éléments formant un ensemble V de sommets et E d'arêtes, et possède deux opérations unaires s , t : E → V donnant les sommets source (début) et cible (fin) de chaque arête. Une algèbre dont toutes les opérations sont unaires est appelée un préfaisceau . Chaque classe de préfaisceaux contient un préfaisceau Ω qui joue le rôle algèbres que 2 joue pour des sous - ensembles. Une telle classe est un cas particulier de la notion plus générale des élémentaires topos comme une catégorie qui est fermée (et d' ailleurs fermé cartésienne ) et un objet Ω , appelé un classificateur subobject . Bien que le terme « objet de puissance » est parfois utilisé comme synonyme objet exponentielle Y ^X , dans la théorie topos Y doit être Ω .

Fonctionneurs et quantificateurs

Dans la théorie des catégories et la théorie des topoi élémentaires , le quantificateur universel peut être compris comme l' adjoint droit d'un foncteur entre ensembles de puissance, le foncteur image inverse d'une fonction entre ensembles ; de même, le quantificateur existentiel est l' adjoint à gauche .

Voir également

• théorème de Cantor
• Famille d'ensembles
• Champ d'ensembles
• Combinaison

Les références

Bibliographie

• Devlin, Keith J. (1979). Fondements de la théorie des ensembles contemporaine . Universitexte. Springer-Verlag . ISBN 0-387-90441-7. Zbl  0407.04003 .
• Halmos, Paul R. (1960). Théorie des ensembles naïf . La série universitaire en mathématiques de premier cycle. Société van Nostrand. Zbl  0087.04403 .
• Puntambekar, AA (2007). Théorie des automates et langages formels . Publications techniques. ISBN 978-81-8431-193-8.

Liens externes

• Puissance réglée sur PlanetMath .
• Puissance réglée dans nLab
• Objet de puissance dans nLab
• Algorithme d'ensemble de puissance en C++