Partition (Mengenlehre)
In der Mengenlehre ist eine Partition einer Menge M eine Familie P aus nichtleeren, disjunkten Teilmengen von M, so dass jedes Element von M in genau einer Menge von P enthalten ist. Eine Partition wird auch als Klasseneinteilung bezeichnet.Beispiele
ist eine Partition von aber keine Partition von , da 3 und 7 nicht in den Teilmengen von P vorkommen.
Die Mengenfamilie 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
*
*
*
*
*
Anzahl der Partitionen einer endlichen Menge
Die Anzahl der Partitionen einer n-elementigen Menge nennt man Bellsche Zahl (nach Eric Temple Bell). Die ersten Bellzahlen sind
: ()
Mathematische Definition
Sei M eine Menge. Ein System P aus Teilmengen von M heißt Partition von M, falls
* die Vereinigung aller Elemente von P ganz M ist,
* P eine Äquivalenzrelation ~ auf der Menge M gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von M, die meist als M/~ geschrieben wird.
Ist umgekehrt eine Partition P von M gegeben, dann können wir eine Äquivalenzrelation definieren durch: x ~ y genau dann, wenn ein Element A in P existiert, in dem x und y enthalten sind. Als Formel lautet die Definition:
:
Es ergibt sich die Gleichheit der Partitionen P = M/~. Damit sind Äquivalenzrelationen und Partitionen im Grunde gleichwertig.
Definition der Faktormenge
Die Menge
aller Äquivalenzklassen
einer Äquivalenzrelation ~ heißt Faktormenge von M nach ~. Diese algebraische
Struktur stellt einen Teil des Zusammenhangs von Äquivalenzrelation und Partition dar.
Beispiel
Für eine feste natürliche Zahl heißen ganze Zahlen kongruent modulo , wenn ihre Differenz durch teilbar ist. Kongruenz ist eine Äquivalenzrelation. Die entsprechende Partition der Menge der ganzen Zahlen ist die Partition durch die Restklassen, d.h.
:
mit
:
(Man beachte, dass diese Notation für Restklassen nur gewählt wurde, um die obige allgemeine Konstruktion zu illustrieren; sie ist nicht allgemein üblich.)
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
