Partition (Mengenlehre)

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

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 irgendeiner 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\}

Die einzige Partition der leeren Menge ist die leere Menge.

Anzahl der Partitionen einer endlichen Menge

Die Anzahl der möglichen Partitionen einer n-elementigen Menge nennt man Bellsche Zahl Bn (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 / ∼ 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_P}}\,\!. bzw. der Relationen {\sim_{(M/{\sim})}} = {\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 xy 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

  1. Folge A000110 in OEIS

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Partition — (lat. partitio ‚Abschnitt, Teil‘), auch Partitionierung (‚Aufteilung‘), bezeichnet: die Landesteilung in der Politik in der Mengenlehre eine Unterteilung von Mengen, siehe Partition (Mengenlehre) die Unterteilung von Datenträgern, siehe Partition …   Deutsch Wikipedia

  • Partition (Graphentheorie) — Ein Schnitt bezeichnet in der Graphentheorie eine Menge von Kanten eines Graphen G = (V,E), die zwischen zwei Mengen von Knoten bzw. zwischen einer Menge und der Restmenge liegt. Eine besondere Bedeutung kommt Schnitten im Zusammenhang mit… …   Deutsch Wikipedia

  • Triviale Partition — Darstellung einer kartographischen Färbung als Graph Eine Färbung eines ungerichteten Graphen ordnet jedem Knoten bzw. jeder Kante im Graphen eine Farbe zu. In der Graphentheorie beschäftigt man sich meist nur mit sogenannten „zulässigen“ oder… …   Deutsch Wikipedia

  • Komplement (Mengenlehre) — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses… …   Deutsch Wikipedia

  • Partitionen — Partition (lat. partitio ‚Abschnitt, Teil‘), beziehungsweise teils auch Partitionierung (‚Aufteilung‘), steht in der Politik für die Landesteilung für eine logische Unterteilung von Systemressourcen, siehe Partition (Festplatte) für die… …   Deutsch Wikipedia

  • Partitionieren — Partition (lat. partitio ‚Abschnitt, Teil‘), beziehungsweise teils auch Partitionierung (‚Aufteilung‘), steht in der Politik für die Landesteilung für eine logische Unterteilung von Systemressourcen, siehe Partition (Festplatte) für die… …   Deutsch Wikipedia

  • Partitionierung — Partition (lat. partitio ‚Abschnitt, Teil‘), beziehungsweise teils auch Partitionierung (‚Aufteilung‘), steht in der Politik für die Landesteilung für eine logische Unterteilung von Systemressourcen, siehe Partition (Festplatte) für die… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazent — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”