Multiinsieme

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

Un multiinsieme, in matematica, e più in particolare nella combinatoria, nella logica matematica e nella teoria degli insiemi, è una generalizzazione del concetto basilare di insieme. Potrebbe definirsi con un elenco che ammette elementi ripetuti: si potrebbe ad esempio rappresentare con un elenco come $a,a,a,b,b,c$ . Una tale collezione, infatti, non corrisponde alla concezione prevalente di insieme come collezione di elementi tutti distinti tra loro. Ma nella definizione di multiinsieme, a differenza di quello che accade per un elenco o una lista, non è rilevante l'ordine in cui compaiono gli elementi.

Formalmente, un multiinsieme è definito come una coppia $M=(A,m)$ , dove $A$ è un insieme e $m\colon A\rightarrow \mathbb {N} ^{*}$ è una funzione a valori naturali positivi; $A$ viene detto insieme supporto del multiinsieme, i suoi elementi si dicono elementi del multiinsieme ed $m$ molteplicità del multiinsieme. Si può dire che la funzione molteplicità associa ad ogni elemento del multiinsieme un numero di ripetizioni che costituiscono il multiinsieme stesso; per esempio nel caso sopra menzionato si ha:

$m(a)=3,$
$m(b)=2,$
$m(c)=1.$

Si osservi che la sola funzione molteplicità individua completamente un multiinsieme: in effetti la nozione può ridursi a quella di funzione a valori interi positivi e per un generico multiinsieme, ricorrendo alla nozione di dominio, si può scrivere $(A,m)=(\mathrm {dom} (m),m)$ .

La somma dei numeri di ripetizioni esprime il numero delle coppie costituenti la funzione $m$ e quindi viene detta cardinalità del multinsieme.

Risulta utile servirsi dei termini e delle notazioni dei multiinsiemi per ragioni di pratica espositiva, come accade per i due primi esempi del paragrafo che segue e in varie questioni enumerative nella combinatoria e nella teoria dei gruppi.

Da quanto detto si evince in modo esplicito che se l'insieme immagine di $m$ (ossia l'insieme dei valori assunti da $m$ ) coincide con l'insieme $\{1\}$ , allora il multiinsieme si può confondere con il suo insieme sostegno.

Naturalmente, dato che ogni funzione si può presentare come insieme di coppie, ogni multiinsieme $M=(A,m)$ può essere presentato come l'insieme delle coppie ordinate $\{(a,m(a)):a\in A\}$ ; nell'esempio iniziale: $M=\{(a,3),(b,2),(c,1)\}$ .

Il numero dei multinsiemi di cardinalità $k$ di un insieme $A$ di cardinalità $n$ è dato dal coefficiente binomiale ${k-1 \choose n-1}$ ; è quindi uguale al numero delle composizioni di $k$ in $n$ parti.^{[non chiaro]}

Se si specifica un universo $U$ di cui $A$ sia sottoinsieme, la definizione di funzione molteplicità diviene $m_{u}\colon U\rightarrow \mathbb {N}$ ; in tal caso, la molteplicità degli elementi di $U$ non appartenenti ad $A$ è nulla.

Il numero di tali multinsiemi di cardinalità $k$ di un insieme $U$ di cardinalità $n$ viene detto, nella terminologia combinatoria classica, numero delle combinazioni con ripetizione di $n$ oggetti di classe $k$ .

La funzione molteplicità $m_{u}\colon U\rightarrow \mathbb {N}$ generalizza la funzione indicatrice di un insieme, quest'ultima essendo vincolata ad assumere solo i valori 0 o 1.

Esempi

La nozione di multiinsieme serve per individuare con chiarezza la collezione dei fattori primi di un dato numero naturale. Se per esempio si osserva che $720=2^{4}3^{2}5$ , si può affermare che il multiinsieme dei fattori primi di 720 è $A=\{(2,4),(3,2),(5,1)\}$ . Un altro esempio è dato dalle radici di un polinomio; ad esempio le radici del polinomio $x^{3}-5x^{2}+7x-3$ costituiscono il multiinsieme $\{(1,2),(3,1)\}$ .

Si osservi che nei due esempi precedenti, parlando di multiinsiemi si hanno enunciati piuttosto chiari e si evitano discorsi nei quali si usa a sproposito il termine insieme.

Nella pratica spesso un multiinsieme viene efficacemente individuato con una notazione esponenziale che si richiama alla fattorizzazione degli interi: per l'esempio del polinomio si potrebbe scrivere $\{{\text{radici di }}x^{3}-5x^{2}+7x-3\}=1^{2}3^{1}$ . Anche per questa notazione si conviene di evitare di scrivere gli esponenti uguali a 1. Talora un multiinsieme viene presentato con un istogramma formato da colonne di quadratini uguali sovrapposti.

Si potrebbero trattare anche multiinsiemi aventi come sostegno un insieme infinito: in effetti una successione di interi (come la successione di Fibonacci o la successione dei numeri di Catalan) potrebbe considerarsi un multiinsieme. Di solito però si considerano solo multiinsiemi con sostegno finito.