Antikette

Eine Teilmenge ${\displaystyle A\subseteq P}$ einer Halbordnung ${\displaystyle (P,\leq )}$ heißt Antikette, falls für zwei verschiedene Elemente ${\displaystyle a,b\in A}$ weder ${\displaystyle a\leq b}$ noch ${\displaystyle b\leq a}$ gilt.

Betrachtet man die Ordnungsrelation ${\displaystyle \leq }$ nur innerhalb der Teilmenge ${\displaystyle A}$, so findet man dort keine zwei miteinander in Relation stehenden Elemente. Innerhalb der Antikette ${\displaystyle A}$ ist also die Situation entgegengesetzt der Situation, welche in einer Kette der Halbordnung gegeben ist.

Vom Begriff der Antikette erhält man eine gute Anschauung bei Betrachtung des Hasse-Diagramms der halbgeordneten Menge ${\displaystyle (P,\leq )}$. Antiketten erkennt man im Hasse-Diagramm als solche Teilmengen, für die keine zwei Elemente durch einen Kantenzug verbunden sind.

Die Schnittmenge einer Antikette mit einer Kette hat stets die Mächtigkeit ${\displaystyle \leq 1}$, besteht also stets aus höchstens einem Element. So lässt sich der Begriff demnach auch fassen: Eine Teilmenge ${\displaystyle A\subseteq P}$ einer halbgeordneten Menge ${\displaystyle (P,\leq )}$ ist genau dann eine Antikette, wenn sie keine Kette von ${\displaystyle (P,\leq )}$ in zwei oder mehr Elementen schneidet.

Die reellen Zahlen ${\displaystyle \mathbb {R} }$ bilden mit der gewöhnlichen strengen Ordnung ${\displaystyle \leq }$ eine Kette. Die einzigen Antiketten sind die trivialen: Die leere Menge ${\displaystyle \varnothing }$ und die einelementigen Teilmengen.

Man betrachte die natürlichen Zahlen ${\displaystyle \mathbb {N} =\{1,2,3,\ldots \}}$ als Trägermenge und als Ordnungsrelation ${\displaystyle \leq }$ die bekannte Teilerrelation. Für zwei natürliche Zahlen ${\displaystyle k}$ und ${\displaystyle l}$ ist also ${\displaystyle k\leq l}$ gleichbedeutend damit, dass ${\displaystyle k}$ Teiler von ${\displaystyle l}$ ist, also dass es eine natürliche Zahl ${\displaystyle n}$ gibt, sodass ${\displaystyle k\cdot n=l}$ gilt.

Nach dieser Maßgabe ist in dieser halbgeordneten Menge ${\displaystyle (\mathbb {N} ,\leq )}$ zum Beispiel die Menge aller Primzahlen eine Antikette.

Als Trägermenge ${\displaystyle P}$ wähle man die Menge der Teiler von 60 und als Ordnungsrelation ${\displaystyle \leq }$ wieder die Teilerrelation. Dann ist ${\displaystyle \{4,6,10,15\}}$ eine Antikette von ${\displaystyle (P,\leq )}$.

Man betrachte eine beliebiges Mengensystem ${\displaystyle {\mathcal {X}}}$ über der Grundmenge ${\displaystyle X}$. Als Ordnungsrelation ${\displaystyle \leq }$ wähle man die Inklusionsrelation ${\displaystyle \subseteq }$.

Für ${\displaystyle n\in \mathbb {N} }$ setze ${\displaystyle {\mathcal {X}}_{n}=\{\,A\in {\mathcal {X}}\;:\;\left|A\right|=n\,\}}$, also ist ${\displaystyle {\mathcal {X}}_{n}}$ das System der ${\displaystyle n}$-elementigen Teilmengen von ${\displaystyle X}$. Dann ist jedes ${\displaystyle {\mathcal {X}}_{n}}$ Antikette von ${\displaystyle ({\mathcal {X}},\subseteq )}$.

Die Automorphismengruppe ${\displaystyle \operatorname {Aut} (P,\leq )}$ der halbgeordneten Menge ${\displaystyle (P,\leq )}$ operiert als Untergruppe der symmetrischen Gruppe ${\displaystyle S_{P}}$ in natürlicher Weise auf ${\displaystyle P}$, indem als Verknüpfung ${\displaystyle \phi \cdot x=\phi (x)}$ für ${\displaystyle x\in P}$ und ${\displaystyle \phi \in \operatorname {Aut} (P,\leq )}$ genommen wird.

Die dadurch gegebenen Orbits ${\displaystyle \operatorname {Aut} (P,\leq )\cdot x=\{\,\phi (x)\;:\;\phi \in \operatorname {Aut} (P,\leq )\,\}}$ mit ${\displaystyle x\in P}$ sind im Falle, dass ${\displaystyle P}$ endlich ist, stets Antiketten von ${\displaystyle (P,\leq )}$.[1]

Die Spernerzahl (englisch Sperner number) der geordneten Menge ${\displaystyle (P,\leq )}$ ist definiert als das Supremum der Mächtigkeiten aller in ${\displaystyle (P,\leq )}$ vorkommenden Antiketten. Die Spernerzahl wird heute üblicherweise mit dem Buchstaben ${\displaystyle w}$ bezeichnet, entsprechend der Gepflogenheit in der englischsprachigen Literatur.

In der deutschsprachigen Literatur wird die Spernerzahl von ${\displaystyle (P,\leq )}$ (entsprechend dem dafür in der englischsprachigen Literatur auch geläufigen Terminus width) manchmal auch die Breite von ${\displaystyle (P,\leq )}$ genannt.

${\displaystyle w(P,\leq )=\sup\{\,|A|\;:\;A{\text{ Antikette in }}(P,\leq )\,\}}$

Wenn aus dem Kontext klar ist, um welche geordnete Menge ${\displaystyle (P,\leq )}$ es sich handelt, schreibt man kurz und einfach ${\displaystyle w}$.

Die Spernerzahl ${\displaystyle w}$ ist stets höchstens so groß wie die Mächtigkeit ${\displaystyle |P|}$ der Trägermenge von ${\displaystyle (P,\leq )}$. Im Falle, dass ${\displaystyle P}$ eine endliche Menge ist, ist auch die Spernerzahl endlich und damit eine natürliche Zahl. Dann wird das Supremum angenommen und es gilt:

${\displaystyle w(P,\leq )\ =\max\{\,|A|\;:\;A{\text{ Antikette in }}(P,\leq )\,\}.}$

${\displaystyle \mathbb {R} }$ hat wie jede nichtleere Kette ${\displaystyle w=1}$.

Die oben angegebene Antikette ${\displaystyle \{\,4,6,10,15\,\}}$ (siehe Hasse-Diagramm) ist die größtmögliche. Also gilt hier ${\displaystyle w=4}$.

Für die Potenzmenge ${\displaystyle {\mathcal {P}}(X)}$ einer endlichen Menge ${\displaystyle X}$ mit ${\displaystyle |X|=n}$ Elementen gilt stets ${\displaystyle w({\mathcal {P}}(X))={\binom {n}{\lfloor {\frac {n}{2}}\rfloor }}}$. Denn genau dies besagt der Satz von Sperner.[2]

Für unendliches ${\displaystyle X}$ der Mächtigkeit ${\displaystyle |X|=\aleph _{\alpha }}$ gilt ${\displaystyle w({{\mathcal {P}}(X)})=2^{\aleph _{\alpha }}}$.[3]

Das System ${\displaystyle {\mathcal {D}}={\mathcal {D}}(P,\leq )}$ der Antiketten von ${\displaystyle (P,\leq )}$ ist stets nichtleer und trägt die folgende Ordnungsrelation, welche die Ordnungsrelation von ${\displaystyle (P,\leq )}$ in natürlicher Weise auf ${\displaystyle {\mathcal {D}}}$ fortsetzt:

Für zwei Antiketten ${\displaystyle A,B\in {\mathcal {D}}}$ ist ${\displaystyle A\leq B}$ dann und nur dann, wenn zu jedem ${\displaystyle b\in B}$ ein ${\displaystyle a\in A}$ existiert mit ${\displaystyle a\leq b}$.

Die so definierte Ordnungsrelation, welche ebenfalls mit ${\displaystyle \leq }$ bezeichnet wird, gibt auf diesem Wege dem Antikettensystem ${\displaystyle {\mathcal {D}}}$ die Struktur eines distributiven Verbands.[4]

Bei endlichem ${\displaystyle (P,\leq )}$ liegt nun ein spezielles Augenmerk auf dem Teilsystem ${\displaystyle {\mathcal {S}}={\mathcal {S}}(P,\leq )}$ der Antiketten maximaler Größe:

${\displaystyle {\mathcal {S}}=\{\,A\in {\mathcal {D}}\;:\;|A|=w(P,\leq )\,\}}$

Hier gilt nämlich das folgende fundamentale Resultat von Robert Dilworth:[5][6][7]

Bei endlichem ${\displaystyle (P,\leq )}$ ist ${\displaystyle ({\mathcal {S}},\leq )}$ Unterverband von ${\displaystyle ({\mathcal {D}},\leq )}$, wobei die zugehörigen Verbandsoperationen ${\displaystyle \land }$ und ${\displaystyle \lor }$ die folgende Darstellung haben:

(1) ${\displaystyle A\land B=\operatorname {Min} ({A}\cup {B})}$

(2) ${\displaystyle A\lor B=\operatorname {Max} ({A}\cup {B})}$

(${\displaystyle A,B\in {\mathcal {S}}}$ )

Dabei wird mit ${\displaystyle \operatorname {Min} (X)}$ bzw. mit ${\displaystyle \operatorname {Max} (X)}$ für ${\displaystyle X\subseteq P}$ die Teilmenge derjenigen Elemente von ${\displaystyle X}$ bezeichnet, welche bzgl. der induzierten Ordnungsrelation innerhalb ${\displaystyle X}$ minimal bzw. maximal sind.

Als Folgerung ergibt sich:[8][9]

Eine endliche geordnete Menge ${\displaystyle (P,\leq )}$ enthält stets eine Antikette maximaler Größe, welche von allen Automorphismen ${\displaystyle \phi \in \operatorname {Aut} (P,\leq )}$ auf sich selbst abgebildet wird.

Oder anders ausgedrückt:

Eine endliche geordnete Menge ${\displaystyle (P,\leq )}$ enthält stets eine Antikette maximaler Größe, welche als Vereinigung gewisser Orbits ${\displaystyle \operatorname {Aut} (P,\leq )\cdot x}$ mit ${\displaystyle x\in P}$ darstellbar ist.

Hierdurch gelangt man auf direktem Wege zum Satz von Sperner. Denn im Falle, dass ${\displaystyle (P,\leq )=(2^{M},\subseteq )}$ mit endlicher Grundmenge ${\displaystyle M}$ ist, sind die Orbits identisch mit den Mächtigkeitsklassen ${\displaystyle {M \choose k}}$ ${\displaystyle (k=0,\dots ,\left|{M}\right|)}$.[10][11]