In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge eine Menge , deren Elemente nichtleere Teilmengen von sind, sodass jedes Element von in genau einem Element von 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) ist eine Partition der Menge . Die Elemente von sind dabei paarweise disjunkte Teilmengen von . ist jedoch keine Partition der Menge , weil 1 zwar in , aber in keinem Element von enthalten ist.
Die Mengenfamilie ist keine Partition irgendeiner Menge, weil und mit 2 ein gemeinsames Element enthalten, also nicht disjunkt sind.
Die Menge hat genau 5 Partitionen:
Die einzige Partition der leeren Menge ist die leere Menge.
Jede einelementige Menge hat genau eine Partition, nämlich .
Jede nichtleere Menge hat genau eine einelementige Partition , man nennt sie die „triviale Partition“.
Anzahl der Partitionen einer endlichen Menge
Die Anzahl der Partitionen einer -elementigen Menge nennt man Bellsche Zahl (nach Eric Temple Bell). Die ersten Bellzahlen sind:
Partitionen und Äquivalenzrelationen
Ist eine Äquivalenzrelation ~ auf der Menge gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von die auch „Faktormenge“ von ~ auf genannt wird.
Ist umgekehrt eine Partition von gegeben, dann wird durch
eine Äquivalenzrelation definiert, etwas formaler:
In der Gleichheit der Partitionen und der Gleichheit der Relationen manifestiert sich eine Gleichwertigkeit von Äquivalenzrelationen und Partitionen.
Beispiel
Für eine feste natürliche Zahl heißen ganze Zahlen kongruent modulo wenn ihre Differenz durch teilbar ist. Kongruenz ist eine Äquivalenzrelation und wird mit bezeichnet. Die zugehörige Partition der Menge der ganzen Zahlen ist die Zerlegung in die Restklassen modulo . Sie lässt sich darstellen als
wobei
die Restklasse bezeichnet, die 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 und zwei Partitionen einer Menge , dann heißt feiner als , falls jedes Element von Teilmenge eines Elements von ist. Anschaulich heißt das, dass jedes Element von selbst durch Elemente von partitioniert wird.
Die Relation „feiner als“ ist eine Halbordnung auf dem System aller Partitionen von , 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 .
Siehe auch
- Klasseneinteilung (Statistik)
- Partitionsfunktion
- Äquivalenzrelation
- Stirling-Zahl#Stirling-Zahlen zweiter Art (Anzahl der k-elementigen Partitionen einer n-elementigen Menge)