Multiensemble

Pour les articles homonymes, voir Sac (homonymie).

Un multiensemble (parfois appelé sac) est un couple (A,m) où A est un ensemble appelé support et m une fonction de A dans l'ensemble des entiers naturels, appelée multiplicité.

Un multiensemble est dit fini si la somme des multiplicités des éléments de son support est finie.

Intuitivement, un tel objet peut être vu comme un ensemble d'éléments de A où un élément peut apparaître plusieurs fois, en l'occurrence dans le multiensemble (A,m), l'élément x apparaît m(x) fois. Un multiensemble fini se note en utilisant des accolades doubles $\{\!\!\{\ldots\}\!\!\}$ qui encadrent les éléments, ayant une multiplicité strictement positive, répétés autant de fois que celle-ci. Ainsi $\{\!\!\{a,b,a,b,b,d\}\!\!\}$ représente le multiensemble ({a,b,c,d},m) où m est la fonction telle que m(a) = 2, m(b) = 3, m(c) = 0 et m(d) = 1.

On peut également le voir 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 $\{\!\!\{a\}\!\!\}$ peut donc représenter des multiensembles distincts, comme ({a},m) et ({a,b},m') (avec m(a) = m'(a) = 1; m'(b) = 0). 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 ambigüité, on prend comme référence un ensemble de base M sur lequel on considère les multiensembles, ainsi si M est donné, les multiensembles sont les applications $M \rightarrow \mathbb{N}$, nulles partout sauf sur un sous-ensemble fini de M, ainsi $\{\!\!\{a\}\!\!\}$ est défini sans ambigüité, comme la fonction de M vers $\mathbb{N}$ qui vaut 0 partout sauf en a où elle vaut 1.

Ordre multiensemble

Si on munit A d'un ordre >, il est possible de définir un ordre entre les multiensembles de support A que l'on appelle ordre multiensemble : (A,m) est supérieur à (A,n) pour l'ordre multiensemble si (A,n) peut s'obtenir à partir de (A,m) en remplaçant chaque élément de (A,m) par un nombre quelconque d'éléments plus petits.

Exemple : si on ordonne les lettres dans l'ordre alphabétique (a < b < c < d), alors $\{\!\!\{a,a,c,d\}\!\!\}$ est strictement plus petit que $\{\!\!\{b,d,d\}\!\!\}$.

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

Notes et références

1. ↑ un article de Coupet-Grimal et Delobel

Voir aussi

Combinaison avec répétition