Partition (Mengenlehre) – einfach erklärt

Grundidee und Definition

Eine Partition, auch Zerlegung oder Klasseneinteilung, ist in der Mengenlehre eine Aufteilung einer Menge M in nichtleere Teilmengen. Dabei muss jedes Element von M in genau einer dieser Teilmengen liegen. Anders gesagt: Eine Partition einer Menge ist eine Zerlegung dieser Menge in nichtleere, paarweise disjunkte Teilmengen. „Paarweise disjunkt“ bedeutet, dass zwei verschiedene Teilmengen kein gemeinsames Element haben.

Formal heißt ein System von nichtleeren Teilmengen A_i mit i ∈ I einer Menge A genau dann Partition oder Zerlegung von A, wenn die A_i paarweise disjunkt sind, also A_i ∩ A_j = ∅ für i ≠ j, und wenn ihre Vereinigung wieder die ganze Menge A ergibt: A = ⋃_{i ∈ I} A_i. Jede Partition ist damit auch eine Überdeckung der Menge, weil alle Elemente der ursprünglichen Menge durch die Teilmengen erfasst werden.

Beispiele und Gegenbeispiele

Ein Beispiel für eine Partition ist P = {{3,5},{2,4,6},{7,8,9}} der Menge M = {2,3,4,5,6,7,8,9}. Die drei Teilmengen sind nichtleer, überschneiden sich nicht und enthalten zusammen genau alle Elemente von M.

Dasselbe Mengensystem P ist aber keine Partition der Menge N = {1,2,3,4,5,6,7,8,9}, denn das Element 1 gehört zwar zu N, liegt aber in keiner Teilmenge von P. Damit wird N nicht vollständig überdeckt.

Die Mengenfamilie {{1,2},{2,3}} ist keine Partition irgendeiner Menge, weil die beiden Teilmengen das Element 2 gemeinsam enthalten. Sie sind also nicht disjunkt.

Kleine Mengen und Bellzahlen

Die Anzahl B_n der Partitionen einer n-elementigen Menge heißt Bellsche Zahl, benannt nach Eric Temple Bell. Die ersten Bellzahlen sind B_0 = 1, B_1 = 1, B_2 = 2, B_3 = 5, B_4 = 15, B_5 = 52, B_6 = 203, …

Dazu passen die Beispiele kleiner Mengen: Die leere Menge ∅ hat genau 1 Partition, nämlich ∅. Die Menge {1} hat genau 1 Partition: {{1}}. Die Menge {1,2} hat genau 2 Partitionen: {{1,2}} und {{1},{2}}. Die Menge {1,2,3} hat genau 5 Partitionen. Die Menge {1,2,3,4} hat genau 15 Partitionen.

Jede einelementige Menge {x} hat genau eine Partition, nämlich {{x}}. Jede nichtleere Menge M hat außerdem genau eine einelementige Partition {M}; sie heißt triviale Partition.

Zusammenhang mit Äquivalenzrelationen

Partitionen hängen eng mit Äquivalenzrelationen zusammen. Eine Äquivalenzrelation ist eine Relation, die Elemente nach Gleichwertigkeit in Klassen einteilt. Ist eine Äquivalenzrelation ~ auf einer Menge M gegeben, dann bilden ihre Äquivalenzklassen eine Partition von M. Diese Partition heißt auch Faktormenge M/~.

Umgekehrt definiert jede Partition P von M eine Äquivalenzrelation. Für Elemente x und y gilt x ~_P y genau dann, wenn es ein Element A in P gibt, in dem sowohl x als auch y enthalten sind. Formal: x ~_P y :⇔ ∃ A ∈ P: x ∈ A, y ∈ A.

Die Gleichheiten P = M/~P und ~{(M/~)} = ~ zeigen die Gleichwertigkeit von Partitionen und Äquivalenzrelationen: Jede Partition entspricht einer Äquivalenzrelation, und jede Äquivalenzrelation entspricht einer Partition.

Beispiel: Restklassen

Ein wichtiges Beispiel ist die Kongruenz modulo m. Für eine feste natürliche Zahl m heißen ganze Zahlen x und y kongruent modulo m, wenn ihre Differenz x − y durch m teilbar ist. Diese Kongruenz ist eine Äquivalenzrelation und wird mit ≡ bezeichnet.

Die zugehörige Partition der ganzen Zahlen ist die Zerlegung in Restklassen modulo m. Sie wird dargestellt als Z/≡ = {[0]≡, [1]≡, …, [m−1]≡}. Dabei ist [k]≡ = {…, k−2m, k−m, k, k+m, k+2m, …} die Restklasse, die k enthält. Der Artikel weist darauf hin, dass diese Notation für Restklassen nicht allgemein üblich ist, sondern zur Illustration der allgemeinen Konstruktion gewählt wurde.

Ordnung der Partitionen

Für zwei Partitionen P und Q einer Menge M nennt man P feiner als Q, wenn jedes Element von P Teilmenge eines Elements von Q ist. Anschaulich bedeutet das: Die Teilmengen von Q werden durch die Teilmengen von P noch weiter zerlegt.

Die Relation „feiner als“ ist eine Halbordnung auf dem System aller Partitionen von M. Eine Halbordnung ist eine Ordnungsrelation, bei der nicht unbedingt alle Elemente miteinander vergleichbar sein müssen. Das System aller Partitionen von M wird dadurch sogar zu einem vollständigen Verband. Wegen der Gleichwertigkeit von Äquivalenzrelationen und Partitionen ist dieser Verband isomorph zum Äquivalenzrelationenverband auf M.