Partisjon i mengdelære

Ein partisjon av ei mengd er ei oppstykking av mengda i mindre, ikkje-overlappande mengder.

Definisjonar

Gjeven ei mengd S, så er ein partisjon av S ei mengd  av delmengder av S med dei følgjande eigenskapane:
 mengdene er ikkje tome: 
 mengdene er disjunkte: 
 unionen av mengdene er lik S: 

Kvar mengd  vert kalla ei blokk eller ein part av partisjonen.

For kvar ikkje-tome mengd S finst det to «trivielle» partisjonar av S: Den tome partisjonen {S} der heile mengda ligg i éi blokk, og den fulle partisjonen {{s}: s ∈ S} der kvart element ligg i kvar si blokk.

Den einaste moglege partisjonen av den tome mengda ∅, er ∅.

Samanheng med andre matematiske strukturar

Partisjonar er likeverdige med ekvivalensrelasjonar og surjektive funksjonar på den måten at desse strukturane kan omformast til kvarandre.

 Ekvivalensrelasjon til partisjon: Gjeven ei mengd S og ein ekvivalensrelasjon ≡S over S, så er det velkjent at ekvivalensklassene åt ≡S gjev ein partisjon av S.

 Partisjon til surjeksjon: Gjeven ei mengd S og ein partisjon  av S, kan vi definere ein funksjon  slik: for kvar s ∈ S er f(s) = B viss s ∈ B. Det er klart at f er ein funksjon som er surjektiv viss (og berre viss)  er ein partisjon.

 Surjeksjon til ekvivalensrelasjon: Gjeven to mengder S, B og ein surjektiv funksjon f: S → B, kan vi definere ein ekvivalensrelasjon ≡S slik: for kvar a, b ∈ S er a ≡S b viss f(a) = f(b).

Partisjonen  svarer til fibrane åt funksjonen f: mengdene {x ∈ S: f(x) = b} for kvart element b ∈ B.

Fine og grove partisjonar

Gjeven to partisjonar  av den same mengda S, så seier me at  er finare enn  (eller likeins at  er grovare enn ) dersom det for kvar blokk  finst ei blokk  slik at . Relasjonen « er finare enn » utgjer ei delvis ordning av alle moglege partisjonar av ei mengd, og er også eit gitter, med den fulle partisjonen som det minste elementet og den tome partisjonen som det største.

Antal partisjonar av endelege mengder

Antalet partisjonar av ei endeleg mengd vert gjeve av Bellfølgja: 1, 1, 2, 5, 15, 52, … Så kvar ei mengd med tre element kan partisjonerast på fem måtar, medan kvar mengd med fem element kan partisjonerast på femtito måtar.

Kjelder

Bakgrunnsstoff




Kategori:Mengdelære
Kategori:Diskret matematikk