Partition (Mengenlehre)

In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge <math>M</math> eine Menge <math>P</math>, deren Elemente nichtleere Teilmengen von <math>M</math> sind, sodass jedes Element von <math>M</math> in genau einem Element von <math>P</math> 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 <math>P = \left\{\left\{3,5\right\},\left\{2,4,6\right\},\left\{7,8,9\right\}\right\}</math> ist eine Partition der Menge <math>M=\left\{2,3,4,5,6,7,8,9\right\}</math>. Die Elemente von <math>P</math> sind dabei paarweise disjunkte Teilmengen von <math>M</math>. <math>P</math> ist jedoch keine Partition der Menge <math>N=\left\{1,2,3,4,5,6,7,8,9\right\}</math>, weil 1 zwar in <math>N</math>, aber in keinem Element von <math>P</math> enthalten ist.

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

Die Menge <math>\left\{1, 2, 3\right\}</math> hat genau 5 Partitionen:

• <math>\left\{\left\{1, 2, 3\right\}\right\}</math>
• <math>\left\{\left\{1\right\}, \left\{2, 3\right\}\right\}</math>
• <math>\left\{\left\{2\right\}, \left\{3, 1\right\}\right\}</math>
• <math>\left\{\left\{3\right\}, \left\{1, 2\right\}\right\}</math>
• <math>\left\{\left\{1\right\}, \left\{2\right\}, \left\{3\right\}\right\}</math>

Die einzige Partition der leeren Menge ist die leere Menge.

Jede einelementige Menge <math>\left\{x\right\}</math> hat genau eine Partition, nämlich <math>\left\{\left\{x\right\}\right\}</math>.

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

Anzahl der Partitionen einer endlichen Menge

Die Anzahl <math>B_n</math> der Partitionen einer <math>n</math>-elementigen Menge nennt man Bellsche Zahl (nach Eric Temple Bell). Die ersten Bellzahlen sind:

<math>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</math> <ref>Vorlage:OEIS</ref>

Partitionen und Äquivalenzrelationen

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

Ist umgekehrt eine Partition <math>P</math> von <math>M</math> gegeben, dann wird durch

„<math>x\sim_P y\,\!</math> genau dann, wenn ein Element <math>A</math> in <math>P</math> existiert, in dem <math>x</math> und <math>y</math> enthalten sind“

eine Äquivalenzrelation definiert, etwas formaler:

<math>x \sim_P y\ :\Leftrightarrow\ \exists A \in P{:}\ {x\in A, y\in A}</math>

In der Gleichheit <math>{P} = {M/{\sim_P}}</math> der Partitionen und der Gleichheit <math>{\sim_{(M/{\sim})}} = {\sim}</math> der Relationen manifestiert sich eine Gleichwertigkeit von Äquivalenzrelationen und Partitionen.

Beispiel

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

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

wobei

<math>[k]_\equiv = \{\ldots,k-2m,k-m,k,k+m,k+2m,\ldots\}</math>

die Restklasse bezeichnet, die <math>k</math> 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 <math>P</math> und <math>Q</math> zwei Partitionen einer Menge <math>M</math>, dann heißt <math>P</math> feiner als <math>Q</math>, falls jedes Element von <math>P</math> Teilmenge eines Elements von <math>Q</math> ist. Anschaulich heißt das, dass jedes Element von <math>Q</math> selbst durch Elemente von <math>P</math> partitioniert wird.

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

Siehe auch

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

Einzelnachweise

<references />