Antikette

Antikette ist ein mathematischer Begriff aus dem Teilgebiet der Mengenlehre und gehört in das Begriffsfeld der Ordnungsrelation. In der englischsprachigen Literatur entspricht ihm der Begriff antichain, manchmal auch als Sperner family oder Sperner system bezeichnet.

Der Begriff Antikette gehört – ebenso wie der Begriff der Kette – zum Kernbestand desjenigen Teils der Mathematik, welcher sich mit Fragestellungen zu Ordnungsrelationen befasst. Hier ist neben der Mengenlehre insbesondere die Kombinatorik der endlichen geordneten Mengen (englisch combinatorial order theory) zu erwähnen. Zu deren zentralen Ergebnissen zählen Sätze wie der Satz von Sperner, der Satz von Dilworth, der Heiratssatz und viele weitere.

Klärung des Begriffs

Definition

Eine Teilmenge $A$ einer (teilweise) geordneten Menge $(P, \leq)$ ist eine Antikette genau dann, wenn $A$ in Bezug auf die gegebene Ordnungsrelation $\leq$ die Eigenschaft hat, dass für je zwei verschiedene Elemente $a$ und $b$ von $A$ weder $a \leq b$ noch $b \leq a$ gilt. Das bedeutet: Betrachtet man die Ordnungsrelation $\leq$ nur innerhalb der Teilmenge $A$, so findet man dort keine zwei miteinander in Relation stehenden Elemente. Innerhalb der Antikette $A$ ist also die Situation entgegengesetzt der Situation, welche in einer Kette der (teilweise) geordneten Menge $(P, \leq)$ gegeben ist. Dies motiviert die Begriffsbildung.

Veranschaulichung

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

Zusammenhang Antiketten – Ketten

Charakteristisch ist, dass die aus einer Antikette und einer Kette gebildete Schnittmenge innerhalb $(P, \leq)$ stets Mächtigkeit $\leq 1$ hat, also stets aus höchstens einem Element besteht. So lässt sich der Begriff demnach auch fassen: Eine Teilmenge $A$ einer (teilweise) geordneten Menge $(P, \leq)$ ist genau dann eine Antikette, wenn $A$ keine Kette von $(P, \leq)$ in zwei oder mehr Elementen schneidet.

Beispiele

Die reellen Zahlen

Die reellen Zahlen $\mathbb{R}$ bilden mit der gewöhnlichen strengen Ordnung ≤ eine Kette. Die einzigen Antiketten sind die leere Menge $\varnothing$ und die 1-elementigen Teilmengen.

Die Primzahlen

Man betrachte die natürlichen Zahlen $\mathbb{N} = \{\, 1, 2, 3, \ldots \,\}$ als Grundmenge $(P, \leq)$ und als Ordnungsrelation $\leq$ die bekannte Teilerrelation.

Für zwei natürliche Zahlen $k$ und $l$ ist also $k \leq l$ gleichbedeutend damit, dass $k$ Teiler von $l$ ist.

Nach dieser Maßgabe ist in dieser (teilweise) geordneten Menge zum Beispiel die Menge aller Primzahlen (und damit überhaupt jede Menge von Primzahlen) eine Antikette.

Die Teiler von 60

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

Mengen von endlichen Mengen derselben Mächtigkeit

Man betrachte eine beliebige Menge $\mathcal X$ von Mengen als Grundmenge $(P, \leq)$ . Als Ordnungsrelation $\leq \,$ wähle man die Inklusionsrelation $\subseteq$.

Sei $\mathcal Y$ eine Teilmenge von $\mathcal X$ und sei weiter eine natürliche Zahl $n \,$ gegeben derart, dass alle zu $\mathcal Y$ gehörenden Mengen aus genau $n \,$ Elementen bestehen. Dann ist $\mathcal Y$ Antikette von $(\mathcal X , \subseteq )$.

Die Orbits innerhalb (P, ≤)

Die Automorpismengruppe $Aut(P, \leq)$ der (teilweise) geordneten Menge $(P, \leq)$ operiert als Untergruppe der symmetrischen Gruppe $S_P \,$ in natürlicher Weise auf $P \,$, indem als Verknüpfung $\phi \cdot x := \phi(x)$ ($x \in P$ , $\phi \in Aut(P, \leq)$ genommen wird.

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

Die Sperner-Zahl oder Breite von (P, ≤)

Definition

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

In der deutschsprachigen Literatur wird die Sperner-Zahl von $(P, \leq)$ oft auch die Breite von $(P, \leq)$ genannt.

Formale Darstellung

$w \mathcal (P, \le)\ = \sup \{|A| : A \subseteq \mathcal (P, \le)\ \mathrm{Antikette} \}$

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

Erläuterung

Die Sperner-Zahl $w \,$ liegt stets unterhalb der Mächtigkeit von $(P, \leq)$. Im Falle, dass $(P, \leq)$ eine endliche Menge ist, ist also auch $w \,$ endlich und damit eine natürliche Zahl. Dann aber wird das Supremum angenommen und es gilt:

$w \mathcal (P, \le)\ = \max \{|A| : A \subseteq \mathcal (P, \le)\ \mathrm{Antikette} \}.$

Beispiele

Die reellen Zahlen

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

Die Teiler von 60

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

Die endlichen Potenzmengen

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

Verbandseigenschaften

Erklärung

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

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

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

Das Resultat von Dilworth

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

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

Hier gilt nämlich das folgende fundamentale Resultat von Robert Dilworth :

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

(1) $A \land B = Min({A}\cap{B})$  

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

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

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

Das Resultat von Kleitman - Edelberg - Lubell - Freese und der Satz von Sperner

Als Folgerung ergibt sich :

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

Oder anders ausgedrückt:

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

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

Abgrenzung des Begriffs

In der Mengenlehre wird der Begriff der Antikette teilweise auch anders benutzt. Die Antiketteneigenschaft wird in gewissen Zusammenhängen an die Inkompatibilität zweier verschiedener Elemente geknüpft oder bei Booleschen Algebren an Disjunktheitsbedingungen. Über Einzelheiten gibt die Monographie von Thomas Jech Auskunft .

Literatur

Originalarbeiten

• Hans-Joachim Burscheid: Über die Breite des endlichen kardinalen Produktes von endlichen Ketten. In: Math. Nachr.. 52, 1972, S. 283–295. MR

• R. P. Dilworth: Some combinatorial problems on partially ordered sets in :  Richard Bellman and Marshall Hall, Jr. (eds.): Combinatorial Analysis. Proceedings of the Tenth Symposium in Applied Mathematics of the American Mathematical Society (1958). American Mathematical Society, Providence, Rhode Island 1960, S. 85-90.

• R. Freese: An application of Dilworth's lattice of maximal antichains. In: Discrete Math.. 7, 1974, S. 107-109.

• Curtis Greene und Daniel J. Kleitman: The structure of Sperner k-Families. In: J. Combinatorial Theory (A). 20, 1976, S. 41-68.

• Curtis Greene und Daniel J. Kleitman: Proof techniques in the theory of finite sets in :  G. C. Rota (ed.): Studies in Combinatorics. Mathematical Association of America, Washington, DC 1978, S. 23-79.

• D. J. Kleitman, M. Edelberg und D. Lubell: Maximal sized antichains in partial orders. In: Discrete Math.. 1, 1971, S. 47-53.

• Hans-Josef Scholz: Über die Kombinatorik der endlichen Potenzmengen im Zusammenhang mit dem Satz von Sperner. Dissertation, Universität Düsseldorf (1987).

• Emanuel Sperner: Ein Satz über Untermengen einer endlichen Menge. In: Math. Z.. 27, 1928, S. 544–548. MR

Monographien

•  Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie. Springer-Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1.

•  Martin Aigner: Combinatorial Theory. Springer-Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3.

•  Martin Aigner: Diskrete Mathematik. 6. Auflage. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8.

•  Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5.

•  Oliver Deiser: Grundbegriffe der wissenschaftlichen Mathematik: Sprache, Zahlen und erste Erkundungen. Springer, Heidelberg (u. a.) 2010, ISBN 978-3-642-11488-5.(Auszug in der Google Buchsuche)

•  Thomas Jech: Set Theory. The Third Millennium edition, revised and expanded. 3. Auflage. Springer-Verlag, Berlin [u.a.] 2003, ISBN 3-540-44085-2.

•  Konrad Engel: Sperner Theory. Cambridge University Press, Cambridge (u. a.) 1997, ISBN 0-521-45206-6.

•  Egbert Harzheim: Ordered Sets. Springer Verlag, New York 2005, ISBN 0-387-24219-8.

•  Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way. Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4.

•  Stasys Jukna: Extremal Combinatorics. Springer-Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9.

Weblinks

• Lectures on extremal set systems and two-colorings of hypergraphs von Gy. Károlyi
• [1] Kombinatorische Methoden in der Informatik (Skript einer Vorlesung von Prof. Dr. Peter Hauck, Uni Tübingen, SS 2008)