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 ${\displaystyle {\mathcal {B}}}$ av delmengder av S med dei følgjande eigenskapane:

• mengdene er ikkje tome: ${\displaystyle \emptyset \not \in {\mathcal {B}}}$
• mengdene er disjunkte: ${\displaystyle \forall B\neq C\in {\mathcal {B}}:B\cap C=\emptyset }$
• unionen av mengdene er lik S: ${\displaystyle \bigcup _{B\in {\mathcal {B}}}B=S}$

Kvar mengd ${\displaystyle B\in {\mathcal {B}}}$ 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.^[1]

• 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 ${\displaystyle {\mathcal {B}}}$ av S, kan vi definere ein funksjon ${\displaystyle f:S\to {\mathcal {B}}}$ 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) ${\displaystyle {\mathcal {B}}}$ 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 ${\displaystyle {\mathcal {B}}}$ svarer til fibrane åt funksjonen f: mengdene {x ∈ S: f(x) = b} for kvart element b ∈ B.

Fine og grove partisjonar

Gjeven to partisjonar ${\displaystyle {\mathcal {B}},{\mathcal {C}}}$ av den same mengda S, så seier me at ${\displaystyle {\mathcal {B}}}$ er finare enn ${\displaystyle {\mathcal {C}}}$ (eller likeins at ${\displaystyle {\mathcal {C}}}$ er grovare enn ${\displaystyle {\mathcal {B}}}$) dersom det for kvar blokk ${\displaystyle B\in {\mathcal {B}}}$ finst ei blokk ${\displaystyle C\in {\mathcal {C}}}$ slik at ${\displaystyle B\subseteq C}$. Relasjonen «${\displaystyle {\mathcal {B}}}$ er finare enn ${\displaystyle {\mathcal {C}}}$» 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, …^[2] 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.