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.

Partitie van een verzameling in zes delen weergegeven door een eulerdiagram

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}$.

Voetnoten

1. rij A000110 in OEIS