Partitie (verzamelingenleer)

In de verzamelingenleer is een partitie ${\displaystyle P}$ van een verzameling ${\displaystyle A}$ een opdeling van ${\displaystyle A}$ in niet-lege onderling disjuncte delen. De deelverzamelingen van ${\displaystyle A}$, die samen de partitie ${\displaystyle P}$ van ${\displaystyle A}$ vormen, mogen niet leeg zijn, hun onderlinge doorsnede is steeds de lege verzameling en hun vereniging is ${\displaystyle 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 ${\displaystyle A}$ is een familie ${\displaystyle P}$ van deelverzamelingen van ${\displaystyle A}$, die voldoet aan:

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

Aantal

Het aantal partities van een verzameling van ${\displaystyle n}$ elementen wordt gegeven door het ${\displaystyle n}$-de getal van Bell ${\displaystyle B_{n}}$.^[1] Voor kleine ${\displaystyle n}$ zijn dat, te beginnen met ${\displaystyle B_{0}}$:

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

Voorbeelden

Zij ${\displaystyle A=\{1,2,3,4\}}$ dan is ${\displaystyle \{\{1,2\},\{3\},\{4\}\}}$ een partitie van ${\displaystyle A}$. De familie ${\displaystyle \{\{1,2\},\{2,3\},\{3,4\}\}}$ is geen partitie van ${\displaystyle A}$, omdat de leden niet onderling disjunct zijn en ${\displaystyle \{\{1\},\{3\},\{4\}\}}$ is geen partitie, omdat de vereniging van de leden niet heel ${\displaystyle 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 ${\displaystyle \mathbb {Z} }$ van de gehele getallen. Algemener vormen de restklassen bij deling door een natuurlijk getal ${\displaystyle n>0}$ een partitie van ${\displaystyle \mathbb {Z} }$.

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

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