Multiensemble

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

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Pour les articles homonymes, voir Sac (homonymie).

Un multiensemble (parfois appelé sac) est une paire $(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 apparaitre plusieurs fois, en l'occurrence dans le multiensemble $(A, m)$ , l'élément $x$ apparait $m (x)$ fois. Un multiensemble fini se note en utilisant des doubles accolades $\{\!\!\{\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.

[modifier] 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 strictement plus grand que $(A, n)$ pour l'ordre multiensemble si :

$m\neq n$ et
pour tout $a \in A$ , si $\,n(a) > m(a)$ alors il existe $a' \in A$ tel que $\,a' > a$ et $\,m(a') > n(a')$ .

Intuitivement, cela revient à dire qu'un nombre quelconque d'éléments de $(A, n)$ peut être remplacé par un élément plus grand pour obtenir $(A, m)$ .

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. Cette propriété est parfois appelée propriété de « Hydre de Lerne » ^{[réf. souhaitée]}: on suppose que, quand Hercule coupe une tête de l'hydre, un nombre quelconque (fini) de têtes peuvent repousser, mais elles sont toutes strictement plus petites ; alors on est sûr que Hercule viendra à bout de l'hydre.