Partition (Mengenlehre) - LinkFang.de





Partition (Mengenlehre)


In der Mengenlehre ist eine Partition (auch Zerlegung oder Klasseneinteilung) einer Menge M eine Menge P, deren Elemente nichtleere Teilmengen von M sind, sodass jedes Element von M in genau einem Element von P enthalten ist. Anders gesagt: Eine Partition einer Menge ist eine Zerlegung dieser Menge in nichtleere paarweise disjunkte Teilmengen.

Beispiele

Das Mengensystem (= die Mengenfamilie) [math]P = \left\{\left\{3,5\right\},\left\{2,4,6\right\},\left\{7,8,9\right\}\right\}[/math] ist eine Partition der Menge [math]M=\left\{2,3,4,5,6,7,8,9\right\}[/math]. Die Elemente von [math]P[/math] sind dabei paarweise disjunkte Teilmengen von [math]M[/math]. [math]P[/math] ist jedoch keine Partition der Menge [math]N=\left\{1,2,3,4,5,6,7,8,9\right\}[/math], weil 1 zwar in [math]N[/math], aber in keinem Element von [math]P[/math] enthalten ist.

Die Mengenfamilie [math]\left\{\left\{1,2\right\},\left\{2,3\right\}\right\}[/math] ist keine Partition irgendeiner Menge, weil [math]\left\{1,2\right\}[/math] und [math]\left\{2,3\right\}[/math] mit 2 ein gemeinsames Element enthalten, also nicht disjunkt sind.

Die Menge [math]\left\{1, 2, 3\right\}[/math] hat genau 5 Partitionen:

  • [math]\left\{\left\{1, 2, 3\right\}\right\}[/math]
  • [math]\left\{\left\{1\right\}, \left\{2, 3\right\}\right\}[/math]
  • [math]\left\{\left\{2\right\}, \left\{3, 1\right\}\right\}[/math]
  • [math]\left\{\left\{3\right\}, \left\{1, 2\right\}\right\}[/math]
  • [math]\left\{\left\{1\right\}, \left\{2\right\}, \left\{3\right\}\right\}[/math]

Die einzige Partition der leeren Menge ist die leere Menge.

Jede einelementige Menge [math]\left\{x\right\}[/math] hat genau eine Partition, nämlich [math]\left\{\left\{x\right\}\right\}[/math].

Jede nichtleere Menge [math]M[/math] hat genau eine einelementige Partition [math]\left\{M\right\}[/math], man nennt sie die „triviale Partition“.

Anzahl der Partitionen einer endlichen Menge

Die Anzahl [math]B_n[/math] der Partitionen einer [math]n[/math]-elementigen Menge nennt man Bellsche Zahl (nach Eric Temple Bell). Die ersten Bellzahlen sind:

[math]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[/math] [1]

Partitionen und Äquivalenzrelationen

Ist eine Äquivalenzrelation ~ auf der Menge [math]M[/math] gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von [math]M,[/math] die auch „Faktormenge“ [math]M/{\sim}[/math] von ~ auf [math]M[/math] genannt wird.

Ist umgekehrt eine Partition [math]P[/math] von [math]M[/math] gegeben, dann wird durch

[math]x\sim_P y\,\![/math] genau dann, wenn ein Element [math]A[/math] in [math]P[/math] existiert, in dem [math]x[/math] und [math]y[/math] enthalten sind“

eine Äquivalenzrelation definiert, etwas formaler:

[math]x \sim_P y\ :\Leftrightarrow\ \exists A \in P{:}\ {x\in A, y\in A}[/math]

In der Gleichheit [math]{P} = {M/{\sim_P}}[/math] der Partitionen und der Gleichheit [math]{\sim_{(M/{\sim})}} = {\sim}[/math] der Relationen manifestiert sich eine Gleichwertigkeit von Äquivalenzrelationen und Partitionen.

Beispiel

Für eine feste natürliche Zahl [math]m[/math] heißen ganze Zahlen [math]x,y[/math] kongruent modulo [math]m,[/math] wenn ihre Differenz [math]x-y[/math] durch [math]m[/math] teilbar ist. Kongruenz ist eine Äquivalenzrelation und wird mit [math]{\equiv}[/math] bezeichnet. Die zugehörige Partition der Menge der ganzen Zahlen ist die Zerlegung in die Restklassen modulo [math]m[/math]. Sie lässt sich darstellen als

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

wobei

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

die Restklasse bezeichnet, die [math]k[/math] 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 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 M, 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 M.

Siehe auch

Einzelnachweise

  1. Folge A000110 in OEIS

Kategorien: Mengensystem | Mengenlehre

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Partition (Mengenlehre) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.