Der Satz von Dilworth und der Satz von Hall

Inhaltsverzeichnis

0. Vorwort

1. Posets
1.1. Posets
1.2. Definition Poset
1.3. Gegenbeispiel zu Posets
1.4. Typische Beispiele für Posets

2. Ketten und Antiketten
2.1. Ketten und Antiketten
2.2. Definition
2.3. Beispiele

3. Satz von Dilworth
3.1. Robert Palmer Dilworth
3.2. Satz von Dilworth

4. Die ausgewogene Besetzung von Gremien
4.1. Das Proporzproblem der Politik
4.2. Beispiel Proporzproblem in einer Regierung

5. Satz von Hall
5.1. Satz von Hall
5.2. Philip Hall
5.3. Beispiel Proporzproblem in einer Regierung

6. Heiratssatz
6.1. Heiratssatz
6.2. Beweis Heiratssatz
6.3. Beispiel Heiratssatz

7. Literaturverzeichnis

0. Vorwort

Die folgende Ausarbeitung erfolgt im Rahmen des fachwissenschaftlichen Seminars I (Modul 6, Studiengang L2) der Universität Kassel, das im Sommersemester 2011 unter der Leitung des Dozenten Robert Labus stattgefunden hat.

Wenn nicht anders erwähnt, basieren die mathematischen Grundlagen auf dem Paper von Bruno Bosbach, einem unveröffentlichten Manuskript der Universität Kassel.

1. Posets

1.1. Posets

Der Begriff „Poset“ ist aus dem Englischen übernommen und steht für „Partially ordered set“. Ins Deutsche übertragen steht „Poset“ folglich für eine teilweise geordnete Menge, auch für eine Menge mit Halbordnung, Partialordnung, Teilordnung oder partielle Ordnung. Posets gehören somit zu den Ordnungsrelationen, einem Teilgebiet der Mengenlehre.

Ordnungsrelationen sind binäre Relationen, das heißt, dass zwei Elemente einer Menge in Relation zueinander stehen. Eine Ordnungsrelation, die üblicherweise durch das Symbol „[Abbildung in dieser Leseprobe nicht enthalten]“ dargestellt wird, ordnet zwei Elemente einer Reihenfolge in einer Menge zu. Die verschiedenen Ordnungen wie Halbordnungen, Quasiordnungen, totale Ordnungen etc. sind durch bestimmte Eigenschaften gekennzeichnet, unter denen immer die Transitivität enthalten ist.

Posets formalisieren die Anordnungen von Elementen einer Menge unter einer binären Relation. Die Elemente von einem bestimmten Paar aus der gegebenen Menge werden durch die binäre Relation geordnet, dabei geht ein Element jeweils dem anderen voraus. Eine Poset besteht also aus einer Menge und einer binären Relation. Es handelt sich dabei um partielle Ordnungen, da nicht alle Paare, die aus den Elementen gebildet werden können, in Relation zueinander stehen müssen. Es ist also nur eine partielle Ordnung vorhanden.

Posets sind durch Reflexivität, Antisymmetrie und Transitivität gekennzeichnet. Eine genaue Beschreibung liefert die folgende Definition:

1.2. Definition Poset

Abbildung in dieser Leseprobe nicht enthalten

Neben den bekannten Sprechweisen „kleiner gleich“ für „[Abbildung in dieser Leseprobe nicht enthalten]“ beziehungsweise „größer gleich“ für „≥“ sind auch die Formulierungen „liegt unterhalb“ oder „links von“ beziehungsweise „liegt oberhalb“ oder „rechts von“ üblich.

1.3. Gegenbeispiele zu Posets

Um den Unterschied von Posets zu Mengen mit anderen Ordnungen zu verdeutlichen, wird hier kurz ein Gegenbeispiel erläutert.

Eine Quasiordnung stellt keine Poset dar, da hier zwar die Reflexivität und Transitivität gilt, nicht aber die Antisymmetrie.

Beispiel:

Die Relation „…ist verwandt mit… “ ist eine Quasiordnung auf der Menge einer Familie:

Abbildung in dieser Leseprobe nicht enthalten

Das Beispiel zeigt, dass hier die Reflexivität und Transitivität erfüllt sind, jedoch ist diese Ordnung nicht antisymmetrisch, folglich stellt sie keine Halbordnung dar.

1.4. Typische Beispiele für Posets

Die nachfolgenden typischen Beispiele für Posets werden hier kurz aufgelistet und im Abschnitt 2, Ketten und Antiketten, ausführlicher aufgegriffen.

- Die Menge der natürlichen Zahlen betrachtet bezüglich der Relation „ist kleiner gleich“
- Die Potenzmenge einer Menge P betrachtet bezüglich der Relation „c“ (Teilmenge)
- Die Menge aller Teiler von 30 betrachtet der Relation „teilt“

2. Ketten und Antiketten

2.1. Ketten und Antiketten

Gegeben ist eine Poset P mit einer Menge P und einer Relation „[Abbildung in dieser Leseprobe nicht enthalten]“. Lässt sich eine Teilmenge Q aus P (Q C P) von der Relation „[Abbildung in dieser Leseprobe nicht enthalten]“ partial ordnen, dann bezeichnet man die Teilmenge Q als Kette. Wenn sich P komplett von der Relation „[Abbildung in dieser Leseprobe nicht enthalten]“ ordnen lässt, dann ist die Menge P total geordnet und wird Kette genannt.

Gilt hingegen für eine Teilmenge Q aus P (Q C P) weder a [Abbildung in dieser Leseprobe nicht enthalten] b noch b [Abbildung in dieser Leseprobe nicht enthalten] a, dann heißt die Teilmenge Q Antikette.

Eine einelementige Menge T aus P (T C P), auch singleton genannt, stellt gleichzeitig eine Kette und eine Antikette dar.

Die Länge einer Kette K C P (beziehungsweise eine Antikette A) wird als maximal bezeichnet, wenn keine Kette (beziehungsweise keine Antikette) - echt - mehr Elemente enthält.

Da jedes singleton aus einer Poset P eine Kette darstellt, kann jede Poset P in paarweise disjunkte Ketten zerlegt werden. Die Länge einer Kettenzerlegung kann unterschiedlich sein. Wird eine Poset P in genau eine Kette zerlegt, so beträgt die Länge 1. Wird die Poset P hingegen in die einzelnen singletons zerlegt, dann ist die Kettenzerlegung von P maximal. Ihre Länge entspricht der Anzahl der in P enthaltenen Elemente.

Eine Poset P hat auch immer eine Zerlegung minimaler Länge. Diese Länge wird als k(P) bezeichnet. Bei der Zerlegung einer Kette in eine minimale Zerlegung muss auf eine geschickte Zerlegung geachtet werden. Das heißt, dass bei der Zerlegung kein Element ausgelassen oder doppelt verwendet wird. Zusätzlich muss die Zerlegung in disjunkte Ketten so erfolgen, dass jede einzelne Kette maximale Länge besitzt. Dadurch wird die Poset in eine minimale Anzahl von Ketten, k (P), zerlegt.

Die minimale Länge einer Antikette entspricht der von einem singleton, sie ist Eins. Jede endliche Poset P besitzt auch Antiketten von maximaler Länge, sie wird als Dimension von P, d(P), bezeichnet.

[...]