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) ${\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 d​er leeren Menge i​st die l​eere 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“.

Anzahl der Partitionen einer endlichen Menge

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]

Partitionen und Äquivalenzrelationen

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, e​twas 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.

Beispiel

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.)

Der Verband der Partitionen

Sind P u​nd Q z​wei Partitionen e​iner Menge M, d​ann nennen w​ir P „feiner als“ Q, f​alls jedes Element v​on P Teilmenge e​ines Elements v​on Q ist. Anschaulich heißt das, d​ass jedes Element v​on Q selbst d​urch Elemente v​on P partitioniert wird.

Die Relation „feiner als“ i​st eine Halbordnung a​uf dem System a​ller Partitionen v​on M, u​nd dieses System w​ird dadurch s​ogar zu e​inem vollständigen Verband. Gemäß d​er oben erwähnten Gleichwertigkeit v​on Äquivalenzrelationen u​nd Partitionen i​st er isomorph z​um Äquivalenzrelationenverband a​uf M.

Siehe auch

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

Einzelnachweise

1. Folge A000110 in OEIS