Partitie (verzamelingenleer)

Partitie van een verzameling in zes delen weergegeven door een eulerdiagram

In de verzamelingenleer is een partitie $P$ van een verzameling $A$ een opdeling van $A$ in niet-lege onderling disjuncte delen. De deelverzamelingen van $A$, die samen de partitie $P$ van $A$ vormen, mogen niet leeg zijn, hun onderlinge doorsnede is steeds de lege verzameling en hun vereniging is $A$. Een partitie is een familie van deelverzamelingen. De deelverzamelingen, die element van dezelfde partitie zijn, worden ook wel de klassen binnen die partitie genoemd.

Definitie

Een partitie van een verzameling $A$ is een familie $P$ van deelverzamelingen van $A$, die voldoet aan:

• $\varnothing \notin P$: geen van de deelverzamelingen in de familie is leeg;
• voor alle verschillende deelverzamelingen $D,E\in P$ is $D\cap E=\varnothing$: de familie bestaat uit onderling disjuncte deelverzamelingen;
• $\bigcup _{D\in P}D=A$: de deelverzamelingen in $P$ vormen gezamenlijk heel $A$.

Aantal

Het aantal partities van een verzameling van $n$ elementen wordt gegeven door het $n$-de getal van Bell $B_n$. Voor kleine $n$ zijn dat, te beginnen met $B_0$:

1, 1, 2, 5, 15, 52, 203, 877, 4140

Voorbeelden

Zij $A=\{1,2,3,4\}$ dan is $\{\{1,2\},\{3\},\{4\}\}$ een partitie van $A$. De familie $\{\{1,2\},\{2,3\},\{3,4\}\}$ is geen partitie van $A$, omdat de leden niet onderling disjunct zijn en $\{\{1\},\{3\},\{4\}\}$ is geen partitie, omdat de vereniging van de leden niet heel $A$ oplevert.

Het paar bestaande uit enerzijds de verzameling van de even getallen, en anderzijds de verzameling van de oneven getallen, vormt een partitie van de verzameling $\mathbb{Z}$ van de gehele getallen. Algemener vormen de restklassen bij deling door een natuurlijk getal $n>0$ een partitie van $\mathbb{Z}$.

De lege familie is de enige partitie van de lege verzameling.

Als $R$ een equivalentierelatie is op een verzameling $A$, dan vormen de equivalentieklassen van $R$ samen een partitie van $A$. De verzamelingen, die element zijn van een bepaalde partitie, kunnen omgekeerd als de equivalentieklassen van een equivalentierelatie $R$ worden geïnterpreteerd. Er is dus een bijectie tussen de partities van een verzameling $A$ en de equivalentierelaties op $A$.