Satz von Dilworth

Die größte Mächtigkeit einer Antikette von ${\displaystyle (P,\leq )}$ ist gleich der kleinsten Anzahl von Ketten, die eine disjunkte Zerlegung der Grundmenge ${\displaystyle P\,}$ bilden.[4]

Ist   ${\displaystyle n\,}$   die Spernerzahl von   ${\displaystyle (P,\leq )}$ , so lässt sich die Grundmenge   ${\displaystyle P\,}$   in   ${\displaystyle n\,}$   Ketten   ${\displaystyle C_{1},\dots ,C_{n}}$   disjunkt zerlegen:

${\displaystyle P=C_{1}{\dot {\cup }}C_{2}{\dot {\cup }}\,\dots {\dot {\cup }}C_{n}}$.

Umgekehrt:

Ist   ${\displaystyle n\,}$   die kleinsten Anzahl von Ketten, welche eine disjunkte Zerlegung der Grundmenge   ${\displaystyle P\,}$   bilden, dann hat   ${\displaystyle (P,\leq )}$   die Spernerzahl   ${\displaystyle n\,}$  .

Es gibt eine disjunkte Zerlegung die Grundmenge   ${\displaystyle P\,}$ in Ketten und dazu ein Repräsentantensystem, welches zugleich eine Antikette von ${\displaystyle (P,\leq )}$ bildet.

Wenn in ${\displaystyle (P,\leq )}$ keine Antikette der Anzahl ${\displaystyle m+1}$ ${\displaystyle (m\in \mathbb {N} _{0})}$ existiert, so lässt sich die Grundmenge ${\displaystyle P}$ stets als Vereinigungsmenge von ${\displaystyle m}$ Ketten darstellen.[5]

Bewiesen wird der Satz von Dilworth in seiner vierten Version per vollständiger Induktion nach der Anzahl ${\displaystyle |P|}$ der Elemente von ${\displaystyle P}$:[8]

Im Falle ${\displaystyle |P|=0}$ ist nichts weiter zu zeigen, da die leere Menge stets als Vereinigungsmenge von beliebig vielen Kopien ihrer selbst darstellbar ist.

Nun gelte als Induktionsvoraussetzung, dass ${\displaystyle |P|>0}$ und dass der Satz schon für alle endlichen Halbordnungen einer Anzahl ${\displaystyle <|P|}$ gültig sei.

Dann lässt sich zunächst schließen, dass ${\displaystyle m>0}$ sein muss. Denn anderenfalls ergäbe sich aus der Voraussetzung, dass ${\displaystyle P}$ keine Elemente enthielte und damit ${\displaystyle |P|=0}$ wäre, was der Induktionsvoraussetzung widerspräche.

Weiterhin existiert aus Endlichkeitsgründen in ${\displaystyle P}$ eine maximale Kette, also eine Kette ${\displaystyle C}$, welche in ${\displaystyle P}$ keine andere Kette als echte Obermenge hat.[9]

Das größte Element von ${\displaystyle C}$[10] werde mit ${\displaystyle c^{+}}$, das kleinste mit ${\displaystyle c^{-}}$ bezeichnet. Offenbar ist ${\displaystyle c^{+}}$ ein maximales Element und ${\displaystyle c^{-}}$ ein minimales Element von ${\displaystyle P}$. Denn andernfalls ließe sich die Kette ${\displaystyle C}$ um ein Element erweitern, hätte also eine andere Kette als Obermenge – im Widerspruch zu ihrer Maximalität.

Für ${\displaystyle P\setminus C}$ werden nun zwei Fälle unterschieden:

Fall 1

In ${\displaystyle P\setminus C}$ existiert keine Antikette mit ${\displaystyle m}$ Elementen.

Dann ist wegen ${\displaystyle m=(m-1)+1}$ und der Induktionsvoraussetzung ${\displaystyle P\setminus C}$ Vereinigungsmenge von ${\displaystyle m-1}$ Ketten und folglich ${\displaystyle P=(P\setminus C)\cup C}$ als Vereinigungsmenge von ${\displaystyle m}$ Ketten darstellbar.

Fall 2

In ${\displaystyle P\setminus C}$ existiert eine Antikette ${\displaystyle A=\{a_{1},\cdots ,a_{m}\}}$ mit genau ${\displaystyle m}$ Elementen ${\displaystyle (m\in \mathbb {N} )}$.

Diese Antikette hat die Eigenschaft, dass jedes Element von ${\displaystyle P}$ mit mindestens einem ihrer Elemente vergleichbar ist. Denn andernfalls entstünde ein Widerspruch zu der Voraussetzung, dass ${\displaystyle P}$ keine Antikette mit ${\displaystyle m+1}$ Elementen enthält.

Folglich lässt sich ${\displaystyle P}$ in der Form

${\displaystyle P=P^{-}\cup P^{+}}$

darstellen mit

${\displaystyle P^{-}=\{p\in P\mid \exists i\in \{1,\cdots ,m\}:p\leq a_{i}\}}$

${\displaystyle P^{+}=\{p\in P\mid \exists i\in \{1,\cdots ,m\}:p\geq a_{i}\}}$   .[11]

${\displaystyle A}$ ist dabei sowohl gleich der Menge der maximalen Elemente von ${\displaystyle P^{-}}$ als auch gleich der Menge der minimalen Elemente von ${\displaystyle P^{+}}$, wobei offenbar

${\displaystyle A=P^{-}\cap P^{+}}$

ist.

Also folgt weiter ${\displaystyle c^{+}\in P^{+}\setminus P^{-}}$ und gleichzeitig ${\displaystyle c^{-}\in P^{-}\setminus P^{+}}$ . Daher ist sowohl ${\displaystyle |P^{-}|<|P|}$ als auch ${\displaystyle |P^{+}|<|P|}$.

Nach Induktionsvoraussetzung lassen sich folglich Ketten ${\displaystyle {C_{1}}^{-},\cdots ,{C_{m}}^{-}}$ und ${\displaystyle {C_{1}}^{+},\cdots ,{C_{m}}^{+}}$ finden, welche die Gleichungen

${\displaystyle P^{-}={C_{1}}^{-}\cup \cdots \cup {C_{m}}^{-}}$

und

${\displaystyle P^{+}={C_{1}}^{+}\cup \cdots \cup {C_{m}}^{+}}$

erfüllen. Deren Indizierung kann dabei so gewählt werden, dass für jedes ${\displaystyle i\in \{1,\cdots ,m\}}$   ${\displaystyle a_{i}}$ zugleich das größte Element von ${\displaystyle {C_{i}}^{-}}$ und das kleinste Element von ${\displaystyle {C_{i}}^{+}}$ ist.

Fügt man für alle ${\displaystyle i\in \{1,\cdots ,m\}}$ jeweils ${\displaystyle {C_{i}}^{-}}$ und ${\displaystyle {C_{i}}^{+}}$ mittels Vereinigung zusammen, so entstehen ${\displaystyle m}$ neue Ketten

${\displaystyle C_{i}:={C_{i}}^{-}\cup {C_{i}}^{+}}$

von ${\displaystyle P}$.

Mit diesen ergibt sich nun insgesamt

${\displaystyle P=P^{-}\cup P^{+}=({C_{1}}^{-}\cup \cdots \cup {C_{m}}^{-})\cup ({C_{1}}^{+}\cup \cdots \cup {C_{m}}^{+})=C_{1}\cup \cdots \cup C_{m}}$

und damit die Schlussfolgerung, dass ${\displaystyle P}$ als Vereinigungsmenge von ${\displaystyle m}$ Ketten darstellbar ist.

Dies vollendet den Induktionsschritt und den Beweis.

Die engen Beziehungen zwischen der fünf genannten Sätzen (Sätze von Dilworth, Hall, König und Menger sowie das Max-Flow-Min-Cut-Theorem) werden deutlich anhand der Herleitungen, mit denen gezeigt wird, dass jeder einzelne jeden anderen nach sich zieht. Ein Beispiel hierfür gibt die Herleitung des Heiratssatzes aus dem Satz von Dilworth, die wie folgt dargestellt werden kann:[16]

Gegeben seien eine endliche Indexmenge ${\displaystyle I}$ und dazu eine Familie ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$ endlicher Mengen, welche der Hall-Bedingung

(H)  ${\displaystyle \left|\bigcup _{h\in H}A_{h}\right|\geq |H|}$   ${\displaystyle (H\subseteq I)}$

genüge. Es darf oBdA dabei angenommen werden, dass die Vereinigungsmenge

${\displaystyle X:=\bigcup _{i\in I}A_{i}}$

und die Indexmenge ${\displaystyle I}$ disjunkt sind.

Dazu wird die Menge ${\displaystyle P}$ mittels

${\displaystyle P:=X{\dot {\cup }}I}$

definiert und auf dieser die folgende Halbordnungsrelation ${\displaystyle \leq }$ :

Für ${\displaystyle p,q\in P}$ gelte ${\displaystyle p\leq q}$ dann und nur dann, wenn

${\displaystyle p=q}$ oder ${\displaystyle p\in X}$ und ${\displaystyle q\in I}$ und ${\displaystyle p\in A_{q}}$.

Dass ${\displaystyle \leq }$ die Halbordnungseigenschaften besitzt, ist offensichtlich und ebenso, dass ${\displaystyle X}$ eine Antikette von ${\displaystyle (P,\leq )}$ ist. Von grundlegender Bedeutung ist dabei, dass wegen der Hall-Bedingung in ${\displaystyle (P,\leq )}$ keine Antikette ${\displaystyle U}$ mit mehr Elementen als ${\displaystyle X}$ existiert. Dies zeigt die folgende Überlegung:

Angenommen es gibt eine Antikette ${\displaystyle U}$ mit ${\displaystyle |U|>|X|}$. Für diese ist die außerhalb von ${\displaystyle X}$ liegende Teilmenge gleich ${\displaystyle U\cap I}$. Die Antiketteneigenschaft von ${\displaystyle U}$ bedeutet, dass für ein Element ${\displaystyle x\in U\cap X}$ und für ein ${\displaystyle k\in U\cap I}$ niemals die Beziehung ${\displaystyle x\in A_{k}}$ bestehen kann.

Damit ergibt sich

${\displaystyle (U\cap X)\cap \left(\bigcup _{k\in U\cap I}A_{k}\right)=\emptyset }$

und zusammen mit (H) weiter

${\displaystyle |X|<|U|=|U\cap X|+|U\cap I|\leq |U\cap X|+\left|\bigcup _{k\in U\cap I}A_{k}\right|=\left|(U\cap X){\dot {\cup }}\left(\bigcup _{k\in U\cap I}A_{k}\right)\right|\leq |X|}$

und auf diesem Wege ein Widerspruch.

Das bedeutet: ${\displaystyle (P,\leq )}$ hat die Spernerzahl ${\displaystyle |X|}$ .

Nach dem Satz von Dilworth besitzt ${\displaystyle P}$ daher eine disjunkte Zerlegung

${\displaystyle P={\dot {\bigcup _{x\in X}}}C_{x}}$

in ${\displaystyle |X|}$ Ketten ${\displaystyle C_{x}}$ von ${\displaystyle (P,\leq )}$.

Aufgrund der Definition von ${\displaystyle (P,\leq )}$ bestehen hier alle ${\displaystyle C_{x}}$ aus höchstens zwei Elementen. D. h.: ${\displaystyle X}$ lässt sich aufteilen in die Menge ${\displaystyle X_{1}}$ derjenigen Elemente von ${\displaystyle X}$ mit ${\displaystyle |C_{x}|=1}$ und in die Menge ${\displaystyle X_{2}}$ derjenigen Elemente von ${\displaystyle X}$ mit ${\displaystyle |C_{x}|=2}$.

Nun ist zu berücksichtigen, dass jeder Index ${\displaystyle i\in I}$ von genau einer dieser Ketten ${\displaystyle C_{x}}$ erfasst wird. Dies bedeutet, dass die Teilmenge ${\displaystyle X_{2}}$ in einer bijektiven Zuordnung zu der Indexmenge ${\displaystyle I}$ steht, bei der zu jedem Element ${\displaystyle x\in X_{2}}$ umkehrbar eindeutig ein Index ${\displaystyle j(x)\in I}$ mit

${\displaystyle x\in A_{j(x)}}$

gehört.

Die Bijektion ${\displaystyle j\colon X_{2}\to I}$ liefert nun die gewünschte injektive Auswahlfunktion. Man nimmt nämlich die Umkehrabbildung ${\displaystyle a:=j^{-1}\colon I\to X_{2}}$, welche offenbar für ${\displaystyle i\in I}$ stets die Beziehung

${\displaystyle a(i)\in A_{j(a(i))}=A_{i}}$

erfüllt.

Die so gegebene Familie ${\displaystyle (a(i))_{i\in I}}$ ist damit ein vollständiges System von paarweise verschiedenen Repräsentanten für die Mengenfamilie ${\displaystyle {\mathcal {A}}=(A_{i})_{i\in I}}$.

Damit ist insgesamt gezeigt, dass der Satz von Dilworth den Heiratssatz nach sich zieht.