Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Multiensemble
Résumé
Un multiensemble (parfois appelé sac, de l'anglais bag utilisé comme synonyme de multiset) est une sorte d'ensemble dans lequel chaque élément peut apparaître plusieurs fois. C'est une généralisation de la notion d'ensemble : un ensemble ordinaire est un multiensemble dans lequel chaque élément apparaît au plus une seule fois ; ce qu'impose, pour les ensembles usuels, l'axiome d'extensionnalité.
On nomme multiplicité d'un élément donné le nombre de fois où il apparaît. Un multiensemble est fini si la somme des multiplicités de ses éléments est finie, ou plus simplement s'il n'a qu'un nombre fini d'éléments (les multiplicités étant toujours finies).
Formellement, un multiensemble est un couple où est un ensemble appelé support et une fonction de dans l'ensemble des entiers naturels, appelée multiplicité (notée ). Dans le multiensemble , l'élément apparaît fois.
Un multiensemble fini se note en utilisant des accolades doubles qui encadrent les éléments, ayant une multiplicité strictement positive, répétés autant de fois que celle-ci. Ainsi représente le multiensemble où est la fonction telle que , , et .
On peut également voir un multiensemble comme une liste commutative, c'est-à-dire dont on peut permuter les éléments, autrement dit comme un élément du monoïde commutatif libre sur A.
Une expression peut donc représenter des multiensembles distincts, comme et (avec ; ). On peut contourner cette difficulté en introduisant une relation d'égalité ad hoc, ou mieux en exigeant que la multiplicité d'un élément du support soit non nulle. Pour éviter cette ambiguïté, on prend comme référence un ensemble de base sur lequel on considère les multiensembles, ainsi si est donné, les multiensembles finis sont les applications , nulles partout sauf sur un sous-ensemble fini de , ainsi est défini sans ambiguïté, comme la fonction de vers qui vaut partout sauf en où elle vaut .
Si on munit d'un ordre , il est possible de définir un ordre entre les multiensembles de support que l'on appelle ordre multiensemble : est supérieur à pour l'ordre multiensemble si peut s'obtenir à partir de en remplaçant chaque élément de par un nombre quelconque d'éléments plus petits.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.