Zerlegung einer Menge

In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge M eine Menge P, deren Elemente nichtleere, disjunkte Teilmengen von M sind, so dass jedes Element von M in genau einem Element von P enthalten ist.

Beispiele

Die Mengenfamilie $P = \left\{\left\{1,5\right\},\left\{2,4,6\right\},\left\{8,9\right\}\right\}$ ist eine Partition der Menge $M = \left\{1,2,4,5,6,8,9\right\}$ aber keine Partition von $\left\{1,2,3,4,5,6,7,8,9\right\}$, da 3 und 7 nicht in den Teilmengen von P vorkommen.

Die Mengenfamilie $\left\{\left\{1,2\right\},\left\{2,3\right\}\right\}$ ist keine Partition von irgend einer Menge, da {1,2} und {2,3} beide die 2 enthalten, also nicht disjunkt sind.

Die Partitionen von {1, 2, 3} sind

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

Anzahl der Partitionen einer endlichen Menge

Die Anzahl der möglichen Partitionen einer n-elementigen Menge nennt man Bellsche Zahl B_n (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$ ^[1]

Partitionen und Äquivalenzrelationen

Ist eine Äquivalenzrelation ~ auf der Menge M gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von M, die meist als $M/{\sim}$ geschrieben wird.

Ist umgekehrt eine Partition P von M gegeben, dann können wir eine Äquivalenzrelation definieren durch: $x\sim_P y\,\!$ genau dann, wenn ein Element A in P existiert, in dem x und y enthalten sind. Als Formel lautet die Definition:

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

Es ergibt sich die Gleichheit der Partitionen $P=M/{\sim}$ bzw. der Relationen ${\sim_P}={\sim}\,\!.$ Damit sind Äquivalenzrelationen und Partitionen im Grunde gleichwertig.

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 entsprechende Partition der Menge der ganzen Zahlen ist die Partition nach den Restklassen ganzer Zahlen modulo m, sie hat die Form

$\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 einzelnen Restklassen bezeichnet, also die Untermengen der Zahlen gleichen Restes bezüglich m. (Man beachte, dass diese Notation für Restklassen nicht allgemein üblich ist, sie wurde nur gewählt, um die obige allgemeine Konstruktion zu illustrieren.)

Vergleich von Partitionen: Der "Partitionsverband"

Sind P und Q zwei Partitionen einer Menge M, dann nennen wir 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 X, und dieses System wird dadurch sogar zu einem Verband.

Siehe auch

• Partitionsfunktion
• Äquivalenzrelation

Einzelnachweise

1. ↑ Folge A000110 in OEIS