Una partizione di un insieme X è un insieme di parti non vuote di X disgiunte a coppie e la cui unione è X .
Sia X un insieme . Un insieme di parti di X è una partizione di X se:
L'insieme {1, 2, 3} ha le seguenti partizioni:
Nota che:
Nel caso in cui tutti gli elementi della partitura abbiano la stessa cardinalità, troviamo il lemma dei pastori .
La partizione vuota è una partizione dell'insieme vuoto (è peraltro l'unico) poiché tutti i suoi elementi (non ce n'è nessuno) hanno tutte le proprietà desiderabili (qui: essere non vuoto e disgiunto) e che la loro unione è vuota ( per definizione ).
Se viene data una relazione di equivalenza sull'insieme X , allora l'insieme di tutte le classi di equivalenza forma una partizione di X . Viceversa, se è data una partizione P di X , allora possiamo definire una relazione di equivalenza su X indicata con ~, con x ~ y se e solo se esiste, tra gli elementi di P , una parte di X che contiene in entrambi x e y . Le nozioni di relazione di equivalenza e partizione sono quindi fondamentalmente equivalenti.
L'insieme di tutte le partizioni di un insieme non vuoto X è parzialmente ordinato : per definizione, una partizione è più fine di un'altra se divide gli elementi dell'altra in parti più piccole. Questo ordine parziale forma un reticolo completo di cui l' elemento più piccolo (la partizione meno fine) è la partizione grossolana in una parte ( X ) e il più grande (la partizione più sottile) è la partizione in singoli .
Il numero di Bell , B n , è il numero di partizioni di un insieme di n elementi.
Il numero di partizioni diverse di un insieme con n elementi indistinguibili è il numero di partizioni di un intero .
Il numero delle sue partizioni in esattamente k sottoinsiemi è il numero di Stirling del secondo tipo S ( n , k ).