Page d'aide sur l'homonymie Pour les articles homonymes, voir Sac (homonymie).

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).

Définition formelleModifier

Formellement, un multiensemble est un couple    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    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  .

Ordre multiensembleModifier

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.

Exemple : si on ordonne les lettres dans l'ordre alphabétique ( ), alors   est strictement plus petit que  .

Si on suppose que l'ordre sur   est bien fondé, alors l'ordre multiensemble ainsi défini l'est aussi[1].

Notes et référencesModifier

Voir aussiModifier

Article connexeModifier

BibliographieModifier

(en) Wayne D. Blizard, « The development of multiset theory », Modern Logic, vol. 1, no 4,‎ , p. 319-352 (lire en ligne)