Antikette

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Definition[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Die reellen Zahlen[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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, ≤)[Bearbeiten]

Die Automorphismengruppe 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) [1].

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

Definition[Bearbeiten]

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[Bearbeiten]

 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[Bearbeiten]

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[Bearbeiten]

Die reellen Zahlen[Bearbeiten]

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

Die Teiler von 60[Bearbeiten]

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

Die Potenzmengen[Bearbeiten]

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

Für unendliches    M \,   mit    |M| = \aleph_{\alpha}   gilt   w({\mathcal P(M)}) =  2^{\aleph_{\alpha}}   [3].

Verbandseigenschaften[Bearbeiten]

Erklärung[Bearbeiten]

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 [4].

Das Resultat von Dilworth[Bearbeiten]

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 [5] [6] [7]:

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}\cup{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[Bearbeiten]

Als Folgerung ergibt sich [8] [9]:

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| ) [10] [11].

Abgrenzung des Begriffs[Bearbeiten]

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 [12].

Literatur[Bearbeiten]

Originalarbeiten[Bearbeiten]

  • Hans-Joachim Burscheid: Über die Breite des endlichen kardinalen Produktes von endlichen Ketten. In: Mathematische Nachrichten. Bd. 52, 1971, ISSN 0025-584X, S. 283–295, doi:10.1002/mana.19720520121.
  • R. P. Dilworth: Some combinatorial problems on partially ordered sets. In :  Richard Bellman, Marshall Hall, Jr. (Hrsg.): Combinatorial Analysis. Proceedings of the Tenth Symposium in Applied Mathematics of the American Mathematical Society, held at Columbia University, april 24–26, 1958 (= Proceedings of Symposia in Applied Mathematics. Bd. 10, ISSN 0160-7634). American Mathematical Society, Providence RI 1960, S. 85–90.
  • Ralph Freese: An application of Dilworth's lattice of maximal antichains. In: Discrete Mathematics. Vol. 7, Nr. 1/2, 1974, ISSN 0012-365X, S. 107–109, doi:10.1016/S0012-365X(74)80022-1.
  • Curtis Greene, Daniel J. Kleitman: The structure of Sperner k-Families. In: Journal of Combinatorial Theory. Series A, Vol. 20, Nr. 1, 1976, ISSN 0097-3165, S. 41–68, doi:10.1016/0097-3165(76)90077-7.
  • Curtis Greene, Daniel J. Kleitman: Proof techniques in the theory of finite sets. In:  Gian-Carlo Rota (Hrsg.): Studies in Combinatorics (= Studies in Mathematics. Bd. 17). Mathematical Association of America, Washington DC 1978, ISBN 0-88385-117-2, S. 23–79.
  • D. Kleitman, M. Edelberg, D. Lubell: Maximal sized antichains in partial orders. In: Discrete Mathematics. Vol. 1, Nr. 1, 1971, S. 47–53, doi:10.1016/0012-365X(71)90006-9.
  • 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: Mathematische Zeitschrift. Bd. 27, Nr. 1, 1928, ISSN 0025-5874, S. 544-548, doi:10.1007/BF01171114.

Monographien[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  Scholz: S. 3.
  2.  Sperner in Math. Z. 27: S. 544 ff.
  3. Siehe Harzheim, "Ordered Sets", Theorem 9.1.25, S. 296; allerdings setzt letzteres Ergebnis die Gültigkeit des Auswahlaxioms voraus.
  4.  Kung / Rota / Yan: S. 130.
  5.  Dilworth in Proc. Symp. Appl. Math. (1958): S. 88 ff.
  6.  Greene / Kleitman in J. Combinatorial Theory (A), vol. 20: S. 45.
  7.  Kung / Rota / Yan: S. 131.
  8.  Kleitman / Edelberg / Lubell in Discrete Math. vol. 1: S. 47 ff.
  9.  Freese in Discrete Math. vol. 7: S. 107 ff.
  10.  Greene / Kleitman in : Studies in Combinatorics (1978): S. 27 ff.
  11.  Scholz: S. 6 ff.
  12.  Jech: S. 84 ff, 114 ff, 201 ff.