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 | Quelltext bearbeiten]

Definition[Bearbeiten | Quelltext bearbeiten]

Eine Teilmenge einer (teilweise) geordneten Menge ist eine Antikette genau dann, wenn in Bezug auf die gegebene Ordnungsrelation die Eigenschaft hat, dass für je zwei verschiedene Elemente und von weder noch gilt. Das bedeutet: 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 (teilweise) geordneten Menge gegeben ist. Dies motiviert die Begriffsbildung.

Veranschaulichung[Bearbeiten | Quelltext bearbeiten]

Vom Begriff der Antikette erhält man eine gute Anschauung bei Betrachtung des Hasse-Diagramms der (teilweise) geordneten Menge . 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 | Quelltext bearbeiten]

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

Beispiele[Bearbeiten | Quelltext bearbeiten]

Die reellen Zahlen[Bearbeiten | Quelltext bearbeiten]

Die reellen Zahlen bilden mit der gewöhnlichen strengen Ordnung ≤ eine Kette. Die einzigen Antiketten sind die leere Menge und die 1-elementigen Teilmengen.

Die Primzahlen[Bearbeiten | Quelltext bearbeiten]

Man betrachte die natürlichen Zahlen als Grundmenge und als Ordnungsrelation die bekannte Teilerrelation.

Für zwei natürliche Zahlen und ist also gleichbedeutend damit, dass Teiler von 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 | Quelltext bearbeiten]

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

Mengen von endlichen Mengen derselben Mächtigkeit[Bearbeiten | Quelltext bearbeiten]

Man betrachte eine beliebige Menge von Mengen als Grundmenge . Als Ordnungsrelation wähle man die Inklusionsrelation .

Sei eine Teilmenge von und sei weiter eine natürliche Zahl gegeben derart, dass alle zu gehörenden Mengen aus genau Elementen bestehen. Dann ist Antikette von .

Die Orbits innerhalb (P, ≤)[Bearbeiten | Quelltext bearbeiten]

Die Automorphismengruppe der (teilweise) geordneten Menge operiert als Untergruppe der symmetrischen Gruppe in natürlicher Weise auf , indem als Verknüpfung ( , ) genommen wird.

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

Die Spernerzahl oder Breite von (P, ≤)[Bearbeiten | Quelltext bearbeiten]

Definition[Bearbeiten | Quelltext bearbeiten]

Die Spernerzahl (englisch Sperner number) der (teilweise) 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 Darstellung[Bearbeiten | Quelltext bearbeiten]

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

Erläuterung[Bearbeiten | Quelltext bearbeiten]

Die Spernerzahl liegt stets unterhalb der Mächtigkeit von . Im Falle, dass eine endliche Menge ist, ist also auch endlich und damit eine natürliche Zahl. Dann aber wird das Supremum angenommen und es gilt:

Beispiele[Bearbeiten | Quelltext bearbeiten]

Die reellen Zahlen[Bearbeiten | Quelltext bearbeiten]

hat wie jede nichtleere Kette .

Die Teiler von 60[Bearbeiten | Quelltext bearbeiten]

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

Die Potenzmengen[Bearbeiten | Quelltext bearbeiten]

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]

Verbandseigenschaften[Bearbeiten | Quelltext bearbeiten]

Erklärung[Bearbeiten | Quelltext bearbeiten]

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 Dilworth[Bearbeiten | Quelltext bearbeiten]

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 wird, welche bzgl. der induzierten Ordnungsrelation innerhalb     minimal (bzw. maximal) sind.

Das Resultat von Kleitman - Edelberg - Lubell - Freese und der Satz von Sperner[Bearbeiten | Quelltext bearbeiten]

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   (   ) 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 Potenzmengen[Bearbeiten | Quelltext bearbeiten]

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

Abgrenzung des Begriffs[Bearbeiten | Quelltext 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 [24].

Literatur[Bearbeiten | Quelltext bearbeiten]

Originalarbeiten[Bearbeiten | Quelltext bearbeiten]

Monographien[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Scholz: S. 3.
  2. Sperner: In: Math. Z. Band 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. Comb. Theory (A). Band 20, S. 45.
  7. Kung-Rota-Yan: S. 131.
  8. Kleitman-Edelberg-Lubell: In: Discrete Math. Band 1, S. 47 ff.
  9. Freese: In: Discrete Math. Band 7, S. 107 ff.
  10. Greene / Kleitman in : Studies in Combinatorics (1978): S. 27 ff.
  11. Scholz: S. 6 ff.
  12. a b c Greene-Kleitman: In: Studies in Combinatorics. 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. 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. Ganter: S. 43.
  24. Jech: S. 84 ff., 114 ff., 201 ff.