Hauptmenü öffnen

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.

Inhaltsverzeichnis

BeispieleBearbeiten

Das Mengensystem (= die Mengenfamilie)   ist eine Partition der Menge  . Die Elemente von   sind dabei paarweise disjunkte Teilmengen von  .   ist jedoch keine Partition der Menge  , weil 1 zwar in  , aber in keinem Element von   enthalten ist.

Die Mengenfamilie   ist keine Partition irgendeiner Menge, weil   und   mit 2 ein gemeinsames Element enthalten, also nicht disjunkt sind.

Die Menge   hat genau 5 Partitionen:

  •  
  •  
  •  
  •  
  •  

Die einzige Partition der leeren Menge ist die leere Menge.

Jede einelementige Menge   hat genau eine Partition, nämlich  .

Jede nichtleere Menge   hat genau eine einelementige Partition  , man nennt sie die „triviale Partition“.

Anzahl der Partitionen einer endlichen MengeBearbeiten

Die Anzahl   der Partitionen einer  -elementigen Menge nennt man Bellsche Zahl (nach Eric Temple Bell). Die ersten Bellzahlen sind:

  [1]

Partitionen und ÄquivalenzrelationenBearbeiten

Ist eine Äquivalenzrelation ~ auf der Menge   gegeben, dann bildet die Menge der Äquivalenzklassen eine Partition von   die auch „Faktormenge“   von ~ auf   genannt wird.

Ist umgekehrt eine Partition   von   gegeben, dann wird durch

  genau dann, wenn ein Element   in   existiert, in dem   und   enthalten sind“

eine Äquivalenzrelation definiert, etwas formaler:

 

In der Gleichheit   der Partitionen und der Gleichheit   der Relationen manifestiert sich eine Gleichwertigkeit von Äquivalenzrelationen und Partitionen.

BeispielBearbeiten

Für eine feste natürliche Zahl   heißen ganze Zahlen   kongruent modulo   wenn ihre Differenz   durch   teilbar ist. Kongruenz ist eine Äquivalenzrelation und wird mit   bezeichnet. Die zugehörige Partition der Menge der ganzen Zahlen ist die Zerlegung in die Restklassen modulo  . Sie lässt sich darstellen als

 

wobei

 

die Restklasse bezeichnet, die   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 PartitionenBearbeiten

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 auchBearbeiten

EinzelnachweiseBearbeiten

  1. Folge A000110 in OEIS