Partitie (verzamelingenleer)

verzamelingenleer

In de verzamelingenleer is een partitie van een verzameling een opdeling van in niet-lege onderling disjuncte delen. De deelverzamelingen van , die samen de partitie van vormen, mogen niet leeg zijn, hun onderlinge doorsnede is steeds de lege verzameling en hun vereniging is . 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 bewerken

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

  •  : geen van de deelverzamelingen in de familie is leeg;
  • voor alle verschillende deelverzamelingen   is  : de familie bestaat uit onderling disjuncte deelverzamelingen;
  •  : de deelverzamelingen in   vormen gezamenlijk heel  .

Aantal bewerken

Het aantal partities van een verzameling van   elementen wordt gegeven door het  -de getal van Bell  .[1] Voor kleine   zijn dat, te beginnen met  :

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

Voorbeelden bewerken

Zij   dan is   een partitie van  . De familie   is geen partitie van  , omdat de leden niet onderling disjunct zijn en   is geen partitie, omdat de vereniging van de leden niet heel   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   van de gehele getallen. Algemener vormen de restklassen bij deling door een natuurlijk getal   een partitie van  .

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

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