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

$P=\left\{\left\{1,5\right\},\left\{2,4,6\right\},\left\{8,9\right\}\right\}$ ist eine Partition von $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 Partitionen einer n-elementigen Menge nennt man Bellsche Zahl $B_{n}$ (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,\dots$ (Folge A000110 in OEIS)

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 disjunkte Mengenfamilie ist und
• die leere Menge nicht Element von P ist.

Partitionen und Äquivalenzrelationen als Faktormenge

Ist 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:

$x\sim y:\Leftrightarrow \exists A\in P:x\in A,y\in A$

Es ergibt sich die Gleichheit der Partitionen P = M/~. Damit sind Äquivalenzrelationen und Partitionen im Grunde gleichwertig.

Definition der Faktormenge

Die Menge $M_{/\sim }:=\left\{[x]_{\sim }\mid x\in M\right\}$
aller Äquivalenzklassen
$[x]_{\sim }:=\left\{y\mid y\in M\wedge (x,y)\in \sim \right\}$
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 $m$ heißen ganze Zahlen $x,y$ kongruent modulo $m$, wenn ihre Differenz $x-y$ durch $m$ teilbar ist. Kongruenz ist eine Äquivalenzrelation. Die entsprechende Partition der Menge der ganzen Zahlen ist die Partition durch die Restklassen, d.h.

$\mathbb {Z} _{/\equiv }=\{[0]_{\equiv },[1]_{\equiv },\ldots ,[m-1]_{\equiv }\}$

mit

$[k]_{\equiv }=\{k,k+m,k+2m,\ldots ,k-m,k-2m,\ldots \}.$

(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