Partizione (teoria degli insiemi)

In matematica una partizione di un insieme X è una divisione di X in sottoinsiemi, detti parti, classi o blocchi della partizione, che "coprono" X senza sovrapporsi. 

Più formalmente, una partizione di X è una collezione P di sottoinsiemi di X tali che:
i sottoinsiemi non sono vuoti;
l'unione di tutti i sottoinsiemi sia l'insieme X stesso (P è un ricoprimento di X);
dati due sottoinsiemi (distinti) qualsiasi di X, questi sono disgiunti.

Una partizione in due parti si dice bipartizione, una in tre parti tripartizione; con significato simile talora si usano termini come tetrapartizione o più in generale k-partizione.

Esempi 

 Per un qualsiasi insieme X, la partizione banale P={X}.
 Per un qualunque X, la partizione formata da tutti i singoletti degli elementi di X.
 Dato un sottoinsieme A di X, la partizione formata da A e dal suo complementare in X.
 Nell'insieme dei numeri naturali, la partizione formata dai numeri pari e dai numeri dispari.
 Nell'insieme dei numeri interi, la partizione formata dalle classi di resto modulo un qualsiasi numero n.

Partizioni e relazioni di equivalenza 

Ad ogni partizione P di un insieme X si può associare, in modo naturale, una relazione di equivalenza ρ sullo stesso X: due elementi sono in relazione secondo ρ se e solo se appartengono allo stesso elemento della partizione P. Viceversa, ad ogni equivalenza si può associare naturalmente una partizione, quella costituita dalle relative classi di equivalenza.

Questo rapporto è importante perché definisce una funzione biunivoca tra l'insieme delle partizioni e quello delle relazioni di equivalenza; inoltre "tornando indietro" si ritorna all'inizio, ovvero, data una relazione ρ e la partizione R ad essa associata, la relazione associata alla partizione non è altro che ρ.

Per queste situazioni si usano termini quali equivalenza canonica di una partizione e partizione associata canonicamente ad una equivalenza.

La proiezione canonica 
Data una partizione P, si può costruire una funzione suriettiva  che associa ad ogni elemento  il sottoinsieme  tale che . Questa funzione è detta proiezione canonica.

Questa funzione è sfruttata ad esempio nel costruire, a partire da una qualsiasi funzione, una funzione biunivoca. Data , si costruisce in X una partizione tale che due elementi di uno stesso sottoinsieme hanno la stessa immagine secondo f; la funzione definita dalla partizione all'immagine di X sarà quindi una funzione biunivoca. Questo processo è detto decomposizione di un'applicazione.

Ad esempio, la funzione parte intera definita sull'insieme  dei reali non negativi ha come partizione canonica associata la partizione costituita dagli intervalli chiusi a sinistra e aperti a destra  per diversi n interi non negativi; secondo l'equivalenza canonicamente associata a questa partizione, ovvero canonicamente associata alla funzione parte intera, sono equivalenti due reali positivi che presentano la stessa parte intera. Restringendo poi il codominio della funzione all'insieme dei numeri naturali si ottiene una funzione biunivoca da P a .

Altri ambiti 

Tra le partizioni di un insieme si definisce un importante ordine parziale stabilendo che una partizione  è più fine di una seconda  se ogni parte di  è contenuta in una (sola) parte di B. Munita di questo ordinamento, la collezione delle partizioni di un insieme costituisce un reticolo detto reticolo delle partizioni di un insieme, molto importante ad esempio nella combinatoria e anche nella meccanica statistica.

Ad ogni partizione di un insieme finito si associa canonicamente anche una partizione dell'intero fornito dalla sua cardinalità. 

La nozione di partizione viene sfruttata anche per il calcolo dell'integrale.

Numero di partizioni di un insieme finito 
Il numero di partizioni di un insieme di  elementi è il numero di Bell . I primi numeri di Bell sono: . I numeri di Bell soddisfano la ricorsione:

e hanno funzione generatrice esponenziale

I numeri di Bell possono essere calcolati usando il triangolo di Bell in cui il primo valore in ogni riga coincide con l'ultimo della riga precedente e i valori successivi sono calcolati sommando due numeri: il numero a sinistra e il numero in alto a sinistra rispetto alla posizione considerata. I numeri di Bell sono riportati lungo entrambi i lati di questo triangolo. In generale il numero  della riga  e colonna  del triangolo conta il numero di partizioni di un insieme con  elementi in cui è presente il singoletto  e tutti i singoletti presenti nella partizione contengono elementi minori di . Ad esempio  conta le partizioni dell'insieme  che hanno il singoletto  ma non il singoletto , che sono:
{1}, {2, 4}, {3}
{1, 4}, {2}, {3}
{1, 2, 4}, {3}.

Il numero di partizioni di un insieme di  elementi in esattamente  parti non vuote è il numero di Stirling di seconda specie

Note

Voci correlate 
Relazione di equivalenza
Partizione di un intervallo
Proprietà di tricotomia
Numeri di Bell
Dicotomia

Altri progetti

Collegamenti esterni 
 

Teoria degli insiemi
Matematica di base