Partition einer Menge

In der Mathematik bezeichnet man als Partition einer Menge die Gruppierung ihrer Elemente in nichtleere Teilmengen , sodass jedes Element in genau einer Teilmenge enthalten ist.

Jede Äquivalenzrelation auf einer Menge definiert eine Partition dieser Menge, und jede Partition definiert eine Äquivalenzrelation. Eine Menge, die mit einer Äquivalenzrelation oder einer Partition ausgestattet ist, wird mitunter als Setoid bezeichnet , typischerweise in der Typentheorie und Beweistheorie .

Eine Partition einer Menge X ist eine Menge nichtleerer Teilmengen von X , sodass jedes Element x in X in genau einer dieser Teilmengen enthalten ist ^{[ 2 ]} (d. h. die Teilmengen sind nichtleere, paarweise disjunkte Mengen ).

Äquivalent dazu ist eine Familie von Mengen P genau dann eine Partition von X , wenn alle der folgenden Bedingungen erfüllt sind: ^{[ 3 ]}

• Die Familie P enthält nicht die leere Menge (das heißt ).${\displaystyle \emptyset \notin P}$
• Die Vereinigung der Mengen in P ist gleich X (d. h. ). Man sagt, die Mengen in P erschöpfen X vollständig oder überdecken es . Siehe auch kollektiv erschöpfende Ereignisse und Überdeckung (Topologie) .${\displaystyle \textstyle \bigcup _{A\in P}A=X}$
• Der Schnitt zweier beliebiger verschiedener Mengen in P ist leer (d. h. ). Die Elemente von P heißen paarweise disjunkt oder sich gegenseitig ausschließend. Siehe auch gegenseitiger Ausschluss .${\displaystyle (\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset }$

Die Mengen in werden als Blöcke , Teile oder Zellen der Partition bezeichnet . ^{[ 4 ]} Wenn dann bezeichnen wir die Zelle, die enthält, mit . Das heißt, ist die Notation für die Zelle, in der enthält . ${\displaystyle P}$${\displaystyle a\in X}$${\displaystyle a}$${\displaystyle [a]}$${\displaystyle [a]}$${\displaystyle P}$${\displaystyle a}$

Jede Partition kann mit einer Äquivalenzrelation auf identifiziert werden , nämlich der Relation, sodass für jedes gilt : genau dann, wenn (äquivalent: genau dann, wenn ). Die Notation legt die Idee nahe, dass die Äquivalenzrelation aus der Partition konstruiert werden kann. Umgekehrt kann jede Äquivalenzrelation mit einer Partition identifiziert werden. Daher sagt man umgangssprachlich manchmal: „Eine Äquivalenzrelation ist dasselbe wie eine Partition.“ Ist P die Partition, die mit einer gegebenen Äquivalenzrelation identifiziert wird , schreiben manche Autoren . Diese Notation legt die Idee nahe, dass die Partition die in Zellen unterteilte Menge X ist . Sie legt außerdem die Idee nahe, dass man aus der Äquivalenzrelation die Partition konstruieren kann. ${\displaystyle P}$${\displaystyle X}$${\displaystyle \sim _{\!P}}$${\displaystyle a,b\in X}$${\displaystyle a\sim _{\!P}b}$${\displaystyle a\in [b]}$${\displaystyle b\in [a]}$${\displaystyle \sim _{\!P}}$${\displaystyle \sim }$${\displaystyle P=X/{\sim }}$

• Die leere Menge besitzt genau eine Partition, nämlich . (Anmerkung: Dies ist die Partition, nicht ein Element der Partition.)${\displaystyle \emptyset }$${\displaystyle \emptyset }$
• Für jede nichtleere Menge X ist P = { X } eine Partition von X , die als triviale Partition bezeichnet wird .
  • Insbesondere besitzt jede einelementige Menge { x } genau eine Partition, nämlich { { x } }.
• Für jede nichtleere echte Teilmenge A einer Menge U bilden die Menge A und ihr Komplement eine Partition von U , nämlich { A , U \ A }.
• Die Menge {1, 2, 3} hat diese fünf Partitionen (eine Partition pro Element):
  • {{1}}, {{2}}, manchmal auch 1 | 2 | 3 geschrieben.
  • {{1, 2}, {3}}, oder 1 2 | 3.
  • {{1, 3}, {2}}, oder 1 3 | 2.
  • {{1}, {2, 3}}, oder 1 | 2 3.
  • {{1, 2, 3}}, oder 1 2 3.
• Folgende Mengen sind keine Partitionen von {1, 2, 3}:
  • {{}, {1, 3}, {2}} ist keine Partition (einer Menge), da eines ihrer Elemente die leere Menge ist .
  • {{1, 2}, {2, 3}} ist keine Partition (einer beliebigen Menge), da das Element 2 in mehr als einem Block enthalten ist.
  • {{1}, {2}} ist keine Partition von {1, 2, 3}, da keiner ihrer Blöcke die Zahl 3 enthält; sie ist jedoch eine Partition von {1, 2}.

Für jede Äquivalenzrelation auf einer Menge X ist die Menge ihrer Äquivalenzklassen eine Partition von X. Umgekehrt kann man aus jeder Partition P von X eine Äquivalenzrelation auf X definieren, indem man x ~ y genau dann setzt, wenn x und y im selben Teil von P liegen . Daher sind die Begriffe Äquivalenzrelation und Partition im Wesentlichen äquivalent. ^{[ 5 ]}

Das Auswahlaxiom garantiert für jede Partition einer Menge X die Existenz einer Teilmenge von X , die genau ein Element aus jedem Teil der Partition enthält. Daraus folgt, dass man zu einer gegebenen Äquivalenzrelation auf einer Menge aus jeder Äquivalenzklasse ein kanonisches Repräsentantenelement auswählen kann.

Eine Partition α einer Menge X ist eine Verfeinerung einer Partition ρ von X – und wir sagen, dass α feiner als ρ und ρ gröber als α ist – , wenn jedes Element von α eine Teilmenge eines Elements von ρ ist . Anschaulich bedeutet dies, dass α eine weitere Zerlegung von ρ ist . In diesem Fall schreibt man α ≤ ρ .

Diese „feiner-als“-Relation auf der Menge der Partitionen von X ist eine partielle Ordnung (daher ist die Notation „≤“ angemessen). Jede Menge von Elementen besitzt eine kleinste obere Schranke (ihre „Vereinigung“) und eine größte untere Schranke (ihren „Schnitt“), sodass sie einen Verband bildet , genauer gesagt (für Partitionen einer endlichen Menge) einen geometrischen und supersolvablen Verband. ^{[ 6 ] [ 7 ]} Der Partitionsverband einer 4-elementigen Menge hat 15 Elemente und ist im Hasse-Diagramm links dargestellt.

Schnittmenge und Vereinigung von Partitionen α und ρ sind wie folgt definiert. Die Schnittmenge ist die Partition, deren Blöcke die Schnittmengen eines Blocks von α und eines Blocks von ρ sind , mit Ausnahme der leeren Menge. Anders ausgedrückt: Ein Block von α ist der Schnitt zweier Blöcke von α und ρ , die nicht disjunkt sind. Um die Vereinigung zu definieren , bilden wir eine Relation zwischen den Blöcken A von α und den Blöcken B von ρ : A ~ B , falls A und B nicht disjunkt sind. Dann ist α die Partition, in der jeder Block C die Vereinigung einer Familie von Blöcken ist, die durch diese Relation verbunden sind. ${\displaystyle \alpha \wedge \rho }$${\displaystyle \alpha \wedge \rho }$${\displaystyle \alpha \vee \rho }$${\displaystyle \alpha \vee \rho }$

Aufgrund der Äquivalenz zwischen geometrischen Verbänden und Matroiden entspricht dieser Verband von Partitionen einer endlichen Menge einem Matroid, dessen Basismenge aus den Atomen des Verbandes besteht, also den Partitionen mit einelementigen Mengen und einer zweielementigen Menge. Diese atomaren Partitionen entsprechen eins zu eins den Kanten eines vollständigen Graphen . Der Matroidabschluss einer Menge atomarer Partitionen ist die feinste gemeinsame Vergröberung aller Partitionen; graphentheoretisch ausgedrückt ist er die Partition der Knoten des vollständigen Graphen in die Zusammenhangskomponenten des durch die gegebene Kantenmenge gebildeten Teilgraphen. Somit entspricht der Verband der Partitionen dem Verband der Flächen des grafischen Matroids des vollständigen Graphen. ${\displaystyle n-2}$

Ein weiteres Beispiel veranschaulicht die Verfeinerung von Partitionen aus der Perspektive von Äquivalenzrelationen. Ist D die Menge der Karten eines Standard-Kartenspiels mit 52 Karten, so besitzt die Relation „gleiche Farbe wie“ auf D – die mit ~ _C bezeichnet werden kann – zwei Äquivalenzklassen: die Mengen {rote Karten} und {schwarze Karten}. Die zu ~ _C gehörige zweiteilige Partition lässt sich verfeinern, wodurch die Relation „gleiche Farbe wie“ ~ _S entsteht , welche die vier Äquivalenzklassen {Pik}, {Karo}, {Herz} und {Kreuz} besitzt.

Eine Partition der Menge N = {1, 2, ..., n } mit der zugehörigen Äquivalenzrelation ~ heißt kreuzungsfrei, wenn sie die folgende Eigenschaft besitzt: Wenn vier Elemente a , b , c und d von N mit a < b < c < d die Bedingungen a ~ c und b ~ d erfüllen , dann gilt auch a ~ b ~ c ~ d . Der Name leitet sich von folgender äquivalenter Definition ab: Man stelle sich die Elemente 1, 2, ..., n von N als die n Eckpunkte eines regelmäßigen n -Ecks (gegen den Uhrzeigersinn) vor. Eine Partition lässt sich dann visualisieren, indem man jeden Block als Polygon zeichnet (dessen Eckpunkte die Elemente des Blocks sind). Die Partition ist genau dann kreuzungsfrei, wenn sich diese Polygone nicht schneiden.

Der Verband der sich nicht kreuzenden Partitionen einer endlichen Menge bildet eine Teilmenge des Verbandes aller Partitionen, aber keinen Unterverband, da die Vereinigungsoperationen der beiden Verbände nicht übereinstimmen.

Der nichtkreuzende Partitionsverband hat aufgrund seiner Rolle in der freien Wahrscheinlichkeitstheorie an Bedeutung gewonnen .

Die Gesamtzahl der Partitionen einer n -elementigen Menge ist die Bell-Zahl B _{_n} . Die ersten Bell-Zahlen sind B _₀ = 1, B _₁ = 1 , B _{₂ = 2,} B ₃ = 5, B _₄ = 15, B _₅ = 52 und B _₆ = 203 (Folge A000110 in der OEIS ). Bell-Zahlen erfüllen die Rekursionsgleichung

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}}$

und die exponentielle erzeugende Funktion besitzen

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.}$

Die Bell-Zahlen lassen sich auch mithilfe des Bell-Dreiecks berechnen. Dabei wird der erste Wert jeder Zeile vom Ende der vorherigen Zeile übernommen, und die nachfolgenden Werte ergeben sich aus der Summe zweier Zahlen: der Zahl links und der Zahl links oberhalb dieser Position. Die Bell-Zahlen werden auf beiden Seiten des Dreiecks wiederholt. Die Zahlen innerhalb des Dreiecks zählen die Partitionen, in denen ein bestimmtes Element das größte einzelne Element ist .

Die Anzahl der Partitionen einer n -elementigen Menge in genau k (nichtleere) Teile ist die Stirling-Zahl zweiter Art S ( n , k ).

Die Anzahl der sich nicht kreuzenden Partitionen einer n -elementigen Menge ist die Catalan-Zahl.

${\displaystyle C_{n}={1 \over n+1}{2n \choose n}.}$

• Exakte Abdeckung
• Blockdesign
• Clusteranalyse
• Liste der Partitionsthemen
• Laminierung (Topologie)
• MECE-Prinzip
• Partielle Äquivalenzrelation
• Partitionsalgebra
• Partitionsverfeinerung
• Punktendliche Sammlung
• Reimschemata durch Mengenpartitionierung
• Schwache Ordnung (geordnete Mengenpartition)

• Brualdi, Richard A. (2004). Einführung in die Kombinatorik (4. Aufl.). Pearson Prentice Hall. ISBN 0-13-100119-1Die
• Schechter, Eric (1997). Handbuch der Analysis und ihrer Grundlagen . Academic Press. ISBN 0-12-622760-8Die