Partition (Mengenlehre)

In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge ${\displaystyle M}$ eine Menge ${\displaystyle P}$, deren Elemente nichtleere Teilmengen von ${\displaystyle M}$ sind, sodass jedes Element von ${\displaystyle M}$ in genau einem Element von ${\displaystyle P}$ enthalten ist. Anders gesagt: Eine Partition einer Menge ist eine Zerlegung dieser Menge in nichtleere paarweise disjunkte Teilmengen. Insbesondere ist jede Partition einer Menge auch eine Überdeckung der Menge.

Das Mengensystem (= die Mengenfamilie) ${\displaystyle P=\left\{\left\{3,5\right\},\left\{2,4,6\right\},\left\{7,8,9\right\}\right\}}$ ist eine Partition der Menge ${\displaystyle M=\left\{2,3,4,5,6,7,8,9\right\}}$. Die Elemente von ${\displaystyle P}$ sind dabei paarweise disjunkte Teilmengen von ${\displaystyle M}$. ${\displaystyle P}$ ist jedoch keine Partition der Menge ${\displaystyle N=\left\{1,2,3,4,5,6,7,8,9\right\}}$, weil 1 zwar in ${\displaystyle N}$, aber in keinem Element von ${\displaystyle P}$ enthalten ist.

Die Mengenfamilie ${\displaystyle \left\{\left\{1,2\right\},\left\{2,3\right\}\right\}}$ ist keine Partition irgendeiner Menge, weil ${\displaystyle \left\{1,2\right\}}$ und ${\displaystyle \left\{2,3\right\}}$ mit 2 ein gemeinsames Element enthalten, also nicht disjunkt sind.

Die Menge ${\displaystyle \left\{1,2,3\right\}}$ hat genau 5 Partitionen:

• ${\displaystyle \left\{\left\{1,2,3\right\}\right\}}$
• ${\displaystyle \left\{\left\{1\right\},\left\{2,3\right\}\right\}}$
• ${\displaystyle \left\{\left\{2\right\},\left\{3,1\right\}\right\}}$
• ${\displaystyle \left\{\left\{3\right\},\left\{1,2\right\}\right\}}$
• ${\displaystyle \left\{\left\{1\right\},\left\{2\right\},\left\{3\right\}\right\}}$

Die einzige Partition der leeren Menge ist die leere Menge.

Jede einelementige Menge ${\displaystyle \left\{x\right\}}$ hat genau eine Partition, nämlich ${\displaystyle \left\{\left\{x\right\}\right\}}$.

Jede nichtleere Menge ${\displaystyle M}$ hat genau eine einelementige Partition ${\displaystyle \left\{M\right\}}$, man nennt sie die „triviale Partition“.

Die Anzahl ${\displaystyle B_{n}}$ der Partitionen einer ${\displaystyle n}$-elementigen Menge nennt man Bellsche Zahl (nach Eric Temple Bell). Die ersten Bellzahlen sind:

${\displaystyle B_{0}=1,\quad B_{1}=1,\quad B_{2}=2,\quad B_{3}=5,\quad B_{4}=15,\quad B_{5}=52,\quad B_{6}=203,\quad \ldots }$ ^[1]

Ist eine Äquivalenzrelation ~ auf der Menge ${\displaystyle M}$ gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von ${\displaystyle M,}$ die auch „Faktormenge“ ${\displaystyle M/{\sim }}$ von ~ auf ${\displaystyle M}$ genannt wird.

Ist umgekehrt eine Partition ${\displaystyle P}$ von ${\displaystyle M}$ gegeben, dann wird durch

„${\displaystyle x\sim _{P}y\,\!}$ genau dann, wenn ein Element ${\displaystyle A}$ in ${\displaystyle P}$ existiert, in dem ${\displaystyle x}$ und ${\displaystyle y}$ enthalten sind“

eine Äquivalenzrelation definiert, etwas formaler:

${\displaystyle x\sim _{P}y\ :\Leftrightarrow \ \exists A\in P{:}\ {x\in A,y\in A}}$

In der Gleichheit ${\displaystyle {P}={M/{\sim _{P}}}}$ der Partitionen und der Gleichheit ${\displaystyle {\sim _{(M/{\sim })}}={\sim }}$ der Relationen manifestiert sich eine Gleichwertigkeit von Äquivalenzrelationen und Partitionen.

Für eine feste natürliche Zahl ${\displaystyle m}$ heißen ganze Zahlen ${\displaystyle x,y}$ kongruent modulo ${\displaystyle m,}$ wenn ihre Differenz ${\displaystyle x-y}$ durch ${\displaystyle m}$ teilbar ist. Kongruenz ist eine Äquivalenzrelation und wird mit ${\displaystyle {\equiv }}$ bezeichnet. Die zugehörige Partition der Menge der ganzen Zahlen ist die Zerlegung in die Restklassen modulo ${\displaystyle m}$. Sie lässt sich darstellen als

${\displaystyle \mathbb {Z} /{\equiv }=\{[0]_{\equiv },[1]_{\equiv },\ldots ,[m-1]_{\equiv }\},}$

wobei

${\displaystyle [k]_{\equiv }=\{\ldots ,k-2m,k-m,k,k+m,k+2m,\ldots \}}$

die Restklasse bezeichnet, die ${\displaystyle k}$ enthält. (Man beachte, dass diese Notation für Restklassen nicht allgemein üblich ist. Sie wurde nur gewählt, um die obige allgemeine Konstruktion zu illustrieren.)

Sind ${\displaystyle P}$ und ${\displaystyle Q}$ zwei Partitionen einer Menge ${\displaystyle M}$, dann heißt ${\displaystyle P}$ feiner als ${\displaystyle Q}$, falls jedes Element von ${\displaystyle P}$ Teilmenge eines Elements von ${\displaystyle Q}$ ist. Anschaulich heißt das, dass jedes Element von ${\displaystyle Q}$ selbst durch Elemente von ${\displaystyle P}$ partitioniert wird.

Die Relation „feiner als“ ist eine Halbordnung auf dem System aller Partitionen von ${\displaystyle M}$, und dieses System wird dadurch sogar zu einem vollständigen Verband. Gemäß der oben erwähnten Gleichwertigkeit von Äquivalenzrelationen und Partitionen ist er isomorph zum Äquivalenzrelationenverband auf ${\displaystyle M}$.

• Klasseneinteilung (Statistik)
• Partitionsfunktion
• Äquivalenzrelation
• Stirling-Zahl#Stirling-Zahlen zweiter Art (Anzahl der k-elementigen Partitionen einer n-elementigen Menge)

1. ↑ Folge A000110 in OEIS