Multiinsieme

Da Wikipedia, l'enciclopedia libera.

In matematica, e più in particolare nella combinatoria, nella logica matematica e nella teoria degli insiemi, un multiinsieme è una generalizzazione del concetto basilare di insieme. Un multiinsieme potrebbe definirsi con un elenco che ammette componenti ripetuti: si potrebbe ad esempio presentare un multiinsieme 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:A \rightarrow \N è una funzione a valori naturali positivi; A viene detto insieme sostegno 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)=(\mbox{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 multi-insieme 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.

Se si specifica un universo \ U di cui \ A sia sottoinsieme, la definizione di funzione molteplicità diviene \ m_u: U \rightarrow \N_0, da \ U all'insieme \ \N_0=\{0,1,2,\dots\}; 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: U \rightarrow \N_0 generalizza la funzione indicatrice di un insieme, quest'ultima essendo vincolata ad assumere solo i valori 0 o 1.

Esempi[modifica | modifica sorgente]

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^43^25, 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 \{\mbox{radici di }x^3-5x^2+7x-3\}=1^23^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.

Voci correlate[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica