Partition (Mengenlehre)

In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge M eine Menge P, deren Elemente nichtleere, disjunkte Teilmengen von M sind, so dass jedes Element von M in genau einem Element von P enthalten ist.

Inhaltsverzeichnis

1 Beispiele
2 Anzahl der Partitionen einer endlichen Menge
3 Partitionen und Äquivalenzrelationen
- 3.1 Beispiel
4 Vergleich von Partitionen: Der "Partitionsverband"
5 Siehe auch
6 Einzelnachweise

Beispiele

Die Mengenfamilie $P = \left\{\left\{1,5\right\},\left\{2,4,6\right\},\left\{8,9\right\}\right\}$ ist eine Partition der Menge $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 möglichen Partitionen einer n-elementigen Menge nennt man Bellsche Zahl $B n$ (nach Eric Temple Bell). Die ersten Bellzahlen sind

$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$ ^[1]

Partitionen und Äquivalenzrelationen

Ist eine Äquivalenzrelation ~ auf der Menge $M$ gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von $M,$ die meist als $M/{\sim}$ geschrieben wird.

Ist umgekehrt eine Partition $P$ von $M$ gegeben, dann können wir eine Äquivalenzrelation definieren durch: $x\sim_P y\,\!$ genau dann, wenn ein Element $A$ in $P$ existiert, in dem $x$ und $y$ enthalten sind. Als Formel lautet die Definition:

$x \sim_P y\ :\Leftrightarrow\ \exists A \in P{:}\ {x\in A, y\in A}$

Es ergibt sich die Gleichheit der Partitionen $P=M/{\sim}$ bzw. der Relationen ${\sim_P}={\sim}\,\!.$ Damit sind Äquivalenzrelationen und Partitionen im Grunde gleichwertig.

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 und wird mit ${\equiv}$ bezeichnet. Die entsprechende Partition der Menge der ganzen Zahlen ist die Partition nach den Restklassen ganzer Zahlen modulo $m,$ sie hat die Form

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

wobei

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

die einzelnen Restklassen bezeichnet, also die Untermengen der Zahlen gleichen Restes bezüglich $m .$ (Man beachte, dass diese Notation für Restklassen nicht allgemein üblich ist, sie wurde nur gewählt, um die obige allgemeine Konstruktion zu illustrieren.)

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

Einzelnachweise

↑ Folge A000110 in OEIS

Kategorie: Mengenlehre

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History