Partitionen

Eine Partition (Zerlegung oder Klasseneinteilung) einer Menge MM ist ein Mengensystem PP, deren Elemente nichtleere Teilmengen von MM sind, sodass jedes Element von MM in genau einem Element von PP enthalten ist.

Beispiele

Das Mengensystem (= die Mengenfamilie) P={{3,5},{2,4,6},{7,8,9}}P = \left\{\left\{3,5\right\},\left\{2,4,6\right\},\left\{7,8,9\right\}\right\} ist eine Partition der Menge M={2,3,4,5,6,7,8,9}M=\left\{2,3,4,5,6,7,8,9\right\}. Die Elemente von PP sind dabei paarweise disjunkte Teilmengen von MM. PP ist jedoch keine Partition der Menge N={1,2,3,4,5,6,7,8,9}N=\left\{1,2,3,4,5,6,7,8,9\right\}, weil 11 zwar in NN, aber in keinem Element von PP enthalten ist.
Die Mengenfamilie {{1,2},{2,3}}\left\{\left\{1,2\right\},\left\{2,3\right\}\right\} ist keine Partition irgendeiner Menge, weil {1,2}\left\{1,2\right\} und {2,3}\left\{2,3\right\} mit 22 ein gemeinsames Element enthalten, also nicht disjunkt sind.
Die Menge {1,2,3}\left\{1, 2, 3\right\} hat genau 5 Partitionen:
  • {{1,2,3}}\left\{\left\{1, 2, 3\right\}\right\}
  • {{1},{2,3}}\left\{\left\{1\right\}, \left\{2, 3\right\}\right\}
  • {{2},{3,1}}\left\{\left\{2\right\}, \left\{3, 1\right\}\right\}
  • {{3},{1,2}}\left\{\left\{3\right\}, \left\{1, 2\right\}\right\}
  • {{1},{2},{3}}\left\{\left\{1\right\}, \left\{2\right\}, \left\{3\right\}\right\}
Die einzige Partition der leeren Menge ist die leere Menge.
Jede einelementige Menge {x}\left\{x\right\} hat genau eine Partition, nämlich {{x}}\left\{\left\{x\right\}\right\}.
Jede nichtleere Menge MM hat genau eine einelementige Partition {M}\left\{M\right\}, die sogenannte "triviale Partition".
 
 

Anzahl der Partitionen einer endlichen Menge

Die Anzahl BnB_n der Partitionen einer nn-elementigen Menge nennt man Bellsche Zahl[1]. Die ersten Bellzahlen sind:
B0=1,B1=1,B2=2,B3=5,B4=15,B5=52,B6=203,…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

Partitionen und Äquivalenzrelationen

Ist eine Äquivalenzrelation ~ auf der Menge MM gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von M,M, die auch "Faktormenge" M/∼M/{\sim} von ~ auf MM genannt wird.
Ist umgekehrt eine Partition PP von MM gegeben, dann wird durch
x∼Py :⇔ ∃A∈P: x∈A,y∈Ax \sim_P y\ :\Leftrightarrow\ \exists A \in P{:}\ {x\in A, y\in A}
eine Äquivalenzrelation ∼P\sim_P definiert. In der Gleichheit P=M/∼P{P} = {M/{\sim_P}} der Partitionen und der Gleichheit ∼(M/∼)=∼{\sim_{(M/{\sim})}} = {\sim} der Relationen manifestiert sich eine Gleichwertigkeit von Äquivalenzrelationen und Partitionen (siehe Satz NZ38).

Beispiel

Für eine feste natürliche Zahl mm heißen ganze Zahlen x,yx,y kongruent modulo m,m, wenn ihre Differenz x−yx-y durch mm teilbar ist. Kongruenz ist eine Äquivalenzrelation und wird mit ≡{\equiv} bezeichnet. Die zugehörige Partition der Menge der ganzen Zahlen ist die Zerlegung in die Restklassen modulo mm. Sie lässt sich darstellen als
Z/≡={[0]≡,[1]≡,…,[m−1]≡},\mathbb Z/{\equiv}=\{ [0]_\equiv , [1]_\equiv , \ldots , [m - 1]_\equiv \},
wobei
[k]≡={…,k−2m,k−m,k,k+m,k+2m,…}[k]_\equiv = \{\ldots,k-2m,k-m,k,k+m,k+2m,\ldots\}
die Restklasse bezeichnet, die kk 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 PP und QQ zwei Partitionen einer Menge MM, dann nennen wir PP "feiner als" QQ, falls jedes Element von PP Teilmenge eines Elements von QQ ist. Anschaulich heißt das, dass jedes Element von QQ selbst durch Elemente von PP partitioniert wird.
Die Relation "feiner als" ist eine Halbordnung auf dem System aller Partitionen von MM, 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 MM.
 
1  Eric Temple Bell, 1883-1960, schottisch-amerikanischer Mathematiker

Ich stimme mit der Mathematik nicht überein. Ich meine, daß die Summe von Nullen eine gefährliche Zahl ist.

Stanislaw Jerzy Lec

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Partition (Mengenlehre) aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Relationen