Partition (Mengenlehre)

In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge $M$ eine Menge $P$, deren Elemente nichtleere Teilmengen von $M$ sind, sodass jedes Element von $M$ in genau einem Element von $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.

Beispiele

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

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

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

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

Die einzige Partition der leeren Menge ist die leere Menge.

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

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

Anzahl der Partitionen einer endlichen Menge

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

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

Partitionen und Äquivalenzrelationen

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

Ist umgekehrt eine Partition $P$ von $M$ gegeben, dann wird durch

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

eine Äquivalenzrelation definiert, etwas formaler:

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

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

Beispiel

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

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

wobei

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

die Restklasse bezeichnet, die $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.)

Der Verband der Partitionen

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

Die Relation „feiner als“ ist eine Halbordnung auf dem System aller Partitionen von $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 $M$.

Siehe auch

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