Zerlegung einer Menge

Zerlegung einer Menge

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 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 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/{\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 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:

  • Zerlegung — bezeichnet in der Mathematik: Primfaktorzerlegung, die Zerlegung von natürlichen Zahlen in Primfaktoren Partition (Mengenlehre), die Zerlegung (Partitionierung) einer Menge in mehrere, kleinere Mengen die Zerlegung eines Intervalls, siehe Riemann …   Deutsch Wikipedia

  • Zerlegung (Mathematik) — 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.… …   Deutsch Wikipedia

  • Zerlegung der Eins — In der Mathematik gibt es oft Situationen, in welchen zwischen einer lokalen und einer globalen Perspektive unterschieden werden muss, aber zwischen beiden hin und hergewechselt werden soll. Zum Beispiel: Um in der Analysis das Flächenintegral zu …   Deutsch Wikipedia

  • Unvollständige Cholesky-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • Unvollständige LR-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • Unvollständige LU-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • ILU-Zerlegung — Als ILU Zerlegung (von incomplete LU Decomposition) oder unvollständige LU Zerlegung bezeichnet man in der numerischen Mathematik die fehlerbehaftete Zerlegung einer Matrix in das Produkt einer unteren Dreiecksmatrix L und einer oberen… …   Deutsch Wikipedia

  • Mandelbrot-Menge — Die Mandelbrot Menge ist eine fraktal erscheinende Menge, die eine bedeutende Rolle in der Chaosforschung spielt. Der Rand der Menge weist eine Selbstähnlichkeit auf, die jedoch nicht exakt ist, da es zu Verformungen kommt. Die Visualisierung der …   Deutsch Wikipedia

  • Wold-Zerlegung — Shiftoperatoren werden im mathematischen Teilgebiet der Funktionalanalysis betrachtet. Beim unilateralen Shiftoperator (s.u.) handelt es sich um einen konkreten nicht normalen Operator auf einem Hilbertraum. Dieser Operator hat viele… …   Deutsch Wikipedia

  • Riemann-Zerlegung — Eine Riemann Zerlegung ist ein Paar einer Familie von Stützstellen ξ0 bis und Zwischenstellen α1 bis , die ein Intervall [a,b], folgendermaßen zerlegt …   Deutsch Wikipedia

Share the article and excerpts

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