Partitionen

In der Mathematik bedeutet eine Partition eines Satzes, die Elemente des Satzes in kleinere, nicht-leere Teile zu teilen, sodass jedes Element genau in einem Teil landet und zusammen diese Teile den gesamten Satz abdecken. Anders gesagt: Die Partition 'teilt' den gesamten Satz in disjunkte Gruppen auf.

Die Elemente der Partition heißen 'Teilmengen' oder 'Blöcke'. Jedes Element gehört genau zu einem Block, kann nicht in zwei gleichzeitig sein, und kein Element wird ausgelassen.

Formale Definition

Sei A eine Menge. Eine P ist eine Partition von A, wenn P eine Sammlung von Mengen ist, für die Folgendes gilt:

• Jeder Teil ist nicht-leer: ∀ S ∈ P, S ≠ ∅.
• Die Teile sind disjunkt: ∀ S, T ∈ P, wenn S ≠ T, dann S ∩ T = ∅.
• Die Vereinigung der Teile ist A: ∪_{S ∈ P} S = A.

Alltagsbeispiele

• Schüler in Klassen einteilen: Jede Klasse ist ein Block, Schüler können nicht in zwei Klassen sein, und alle Schüler sind zugewiesen.
• Früchte nach Typ in Körbe sortieren: Äpfel in einen, Orangen in einen anderen – keine Überlappung, vollständige Abdeckung.
• Einen Kuchen in Stücke schneiden: Jedes Stück ist ein Teil, kein Stück bleibt übrig, keine überlappenden Stücke.

Mathematische Beispiele

• Partition von {1,2,3,4} in {{1,2}, {3,4}}: Zwei Blöcke, disjunkt, decken den gesamten Satz ab.
• Singleton-Partition: {{1}, {2}, {3}, {4}} – Jedes Element in seinem eigenen Block.
• Triviale Partition: {{1,2,3,4}} – Der gesamte Satz als ein Block.

Zusammenhang mit Äquivalenzrelationen

Es gibt eine tiefe Verbindung zwischen Äquivalenzrelationen und Partitionen. Jede Äquivalenzrelation induziert eine Partition: Die Äquivalenzklassen sind die Blöcke der Partition, wobei zwei Elemente im selben Untermenge sind, wenn sie äquivalent sind.

Umgekehrt definiert jede Partition eine Äquivalenzrelation: Zwei Elemente sind äquivalent, wenn sie zum selben Untermenge gehören.

Daher repräsentieren Äquivalenzrelationen und Partitionen zwei Seiten desselben mathematischen Phänomens: Eine in der Sprache der Verbindungen, die andere in der Sprache der Satzteilung, die Äquivalenz ausdrückt.

Zusammenfassung

Eine Partition ist eine Teilung der Elemente eines Satzes, bei der es keine Überlappung und kein fehlendes Element gibt. Sie hängt eng mit Äquivalenzrelationen zusammen: Jede Äquivalenzrelation bestimmt eine Partition, und jede Partition entspricht einer Äquivalenzrelation.

Übungsaufgabe