Antikette

mathematischer Begriff aus dem Teilgebiet der Mengenlehre

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, der sich mit Fragestellungen zu Ordnungsrelationen befasst. Hier ist neben der Mengenlehre insbesondere die Kombinatorik der endlichen halbgeordneten Mengen (englisch combinatorial order theory) zu erwähnen. Zu den zentralen Ergebnissen zählen Sätze wie der Satz von Sperner, der Satz von Dilworth, der Heiratssatz und viele weitere.

Klärung des BegriffsBearbeiten

DefinitionBearbeiten

Eine Teilmenge   einer Halbordnung   heißt Antikette, falls für zwei verschiedene Elemente   weder   noch   gilt.

VeranschaulichungBearbeiten

Betrachtet man die Ordnungsrelation   nur innerhalb der Teilmenge  , so findet man dort keine zwei miteinander in Relation stehenden Elemente. Innerhalb der Antikette   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  . 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  , besteht also stets aus höchstens einem Element. So lässt sich der Begriff demnach auch fassen: Eine Teilmenge   einer halbgeordneten Menge   ist genau dann eine Antikette, wenn sie keine Kette von   in zwei oder mehr Elementen schneidet.

BeispieleBearbeiten

Die reellen ZahlenBearbeiten

Die reellen Zahlen   bilden mit der gewöhnlichen strengen Ordnung   eine Kette. Die einzigen Antiketten sind die trivialen: Die leere Menge   und die einelementigen Teilmengen.

Die PrimzahlenBearbeiten

Man betrachte die natürlichen Zahlen   als Trägermenge und als Ordnungsrelation   die bekannte Teilerrelation. Für zwei natürliche Zahlen   und   ist also   gleichbedeutend damit, dass   Teiler von   ist, also dass es eine natürliche Zahl   gibt, sodass   gilt.

Nach dieser Maßgabe ist in dieser halbgeordneten Menge   zum Beispiel die Menge aller Primzahlen eine Antikette.

Die Teiler von 60Bearbeiten

Als Trägermenge   wähle man die Menge der Teiler von 60 und als Ordnungsrelation   wieder die Teilerrelation. Dann ist   eine Antikette von  .

Mengen von endlichen Mengen derselben MächtigkeitBearbeiten

Man betrachte eine beliebiges Mengensystem   über der Grundmenge  . Als Ordnungsrelation   wähle man die Inklusionsrelation  .

Für   setze  , also ist   das System der  -elementigen Teilmengen von  . Dann ist jedes   Antikette von  .

OrbitsBearbeiten

Die Automorphismengruppe   der halbgeordneten Menge   operiert als Untergruppe der symmetrischen Gruppe   in natürlicher Weise auf  , indem als Verknüpfung   für   und   genommen wird.

Die dadurch gegebenen Orbits   mit   sind im Falle, dass   endlich ist, stets Antiketten von  .[1]

Die SpernerzahlBearbeiten

DefinitionBearbeiten

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

In der deutschsprachigen Literatur wird die Spernerzahl von   (entsprechend dem dafür in der englischsprachigen Literatur auch geläufigen Terminus width) manchmal auch die Breite von   genannt.

Formale DarstellungBearbeiten

 

Wenn aus dem Kontext klar ist, um welche geordnete Menge   es sich handelt, schreibt man kurz und einfach  .

ErläuterungBearbeiten

Die Spernerzahl   ist stets höchstens so groß wie die Mächtigkeit   der Trägermenge von  . Im Falle, dass   eine endliche Menge ist, ist auch die Spernerzahl endlich und damit eine natürliche Zahl. Dann wird das Supremum angenommen und es gilt:

 

BeispieleBearbeiten

Die reellen ZahlenBearbeiten

  hat wie jede nichtleere Kette  .

Die Teiler von 60Bearbeiten

Die oben angegebene Antikette   (siehe Hasse-Diagramm) ist die größtmögliche. Also gilt hier  .

Die PotenzmengenBearbeiten

Für die Potenzmenge   einer endlichen Menge   mit   Elementen gilt stets  . Denn genau dies besagt der Satz von Sperner.[2]

Für unendliches   der Mächtigkeit   gilt  .[3]

VerbandseigenschaftenBearbeiten

ErklärungBearbeiten

Das System   der Antiketten von   ist stets nichtleer und trägt die folgende Ordnungsrelation, welche die Ordnungsrelation von   in natürlicher Weise auf   fortsetzt:

Für zwei Antiketten   ist   dann und nur dann, wenn zu jedem   ein   existiert mit  .

Die so definierte Ordnungsrelation, welche ebenfalls mit   bezeichnet wird, gibt auf diesem Wege dem Antikettensystem   die Struktur eines distributiven Verbands.[4]

Das Resultat von DilworthBearbeiten

Bei endlichem   liegt nun ein spezielles Augenmerk auf dem Teilsystem   der Antiketten maximaler Größe:

 

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

Bei endlichem   ist   Unterverband von  , wobei die zugehörigen Verbandsoperationen   und   die folgende Darstellung haben:
(1)  
(2)  
(  )

Dabei wird mit   bzw. mit   für   die Teilmenge derjenigen Elemente von   bezeichnet, welche bzgl. der induzierten Ordnungsrelation innerhalb   minimal bzw. maximal sind.

Das Resultat von Kleitman, Edelberg, Lubell und Freese und der Satz von SpernerBearbeiten

Als Folgerung ergibt sich:[8][9]

Eine endliche geordnete Menge   enthält stets eine Antikette maximaler Größe, welche von allen Automorphismen   auf sich selbst abgebildet wird.

Oder anders ausgedrückt:

Eine endliche geordnete Menge   enthält stets eine Antikette maximaler Größe, welche als Vereinigung gewisser Orbits   mit   darstellbar ist.

Hierdurch gelangt man auf direktem Wege zum Satz von Sperner. Denn im Falle, dass   mit endlicher Grundmenge   ist, sind die Orbits identisch mit den Mächtigkeitsklassen    .[10][11]

Anzahl der Antiketten endlicher PotenzmengenBearbeiten

Auf Richard Dedekind geht das Problem zurück, für   und   die Anzahl   aller Antiketten der Potenzmenge   zu bestimmen. Dieses Problem bezeichnet man daher als Dedekind-Problem (englisch Dedekind’s problem) und die Zahlen   als Dedekind-Zahlen (englisch Dedekind numbers).[12][13][14]

Die Zahl   ist (im Wesentlichen[15]) identisch mit der Anzahl der monoton wachsenden surjektiven Funktionen von   nach   und genauso identisch mit der Anzahl der freien distributiven Verbände mit   erzeugenden Elementen.[12][16]

Da diese Zahlen ein erhebliches Wachstum aufweisen, ist die exakte Bestimmung von   bislang allein für   gelungen:[17][18]

 [19]

Für eine Einschätzung der Größenordnung des Wachstums der   kennt man jedoch untere und obere Schranken, so zum Beispiel die folgenden, welche auf die Arbeit des Mathematikers Georges Hansel aus dem Jahre 1966 zurückgeht:[12]

 

Wie Daniel J. Kleitman und George Markowsky in 1975 zeigten, lässt sich die genannte obere Schranke weiter verschärfen zu:

 [20]

und man kennt sogar noch bessere Schranken.[21]

Das Dedekind-Problem ist noch ungelöst. Dem bedeutenden ungarischen Mathematiker Paul Erdős (1913–1996) wird die Bemerkung zugeschrieben, das Problem sei für dieses Jahrhundert zu schwer.[22] Zwar legte der polnische Mathematiker Andrzej P. Kisielewicz im Jahre 1988 eine korrekte Formel vor. Diese gilt jedoch als nutzlos, da mit ihr selbst die Verifikation der schon bekannten Dedekind-Zahlen aus Gründen des Rechenaufwands nicht möglich ist.[18]

Abgrenzung des BegriffsBearbeiten

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

LiteraturBearbeiten

Originalarbeiten

Monographien

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. Scholz: S. 3.
  2. Sperner: Math. Z. Band 27, 1928, S. 544 ff.
  3. Siehe Harzheim: Ordered Sets. Theorem 9.1.25, S. 296; allerdings setzt letzteres Ergebnis das Auswahlaxiom voraus.
  4. Kung-Rota-Yan: S. 130.
  5. Dilworth: Proceedings of Symposia in Applied Mathematics. 1958, S. 88 ff.
  6. Greene-Kleitman: J. Comb. Theory (A). Band 20, 1993, S. 45.
  7. Kung-Rota-Yan: S. 131.
  8. Kleitman-Edelberg-Lubell: Discrete Math. Band 1, 1971, S. 47 ff.
  9. Freese: Discrete Math. Band 7, 1974, S. 107 ff.
  10. Greene / Kleitman: Studies in Combinatorics. 1978, S. 27 ff.
  11. Scholz: S. 6 ff.
  12. a b c Greene-Kleitman: Studies in Combinatorics. 1978, S. 33.
  13. Ganter: S. 42–46.
  14. Kung-Rota-Yan: S. 147.
  15. Wenn man die beiden einelementigen Antiketten   und   nicht berücksichtigt.
  16. Die Anzahl der freien distributiven Verbände mit   Erzeugenden bezeichnet man mit   oder auch mit   . Es ist also   .
  17. Stand: 2013
  18. a b Ganter: S. 43.
  19. Folge A000372 in OEIS
  20.   ist das landausche Groß-O-Symbol.
  21. Kung-Rota-Yan: S. 147.
  22. Ganter: S. 42.
  23. Jech: S. 84 ff, 114 ff, 201 ff.