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, 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 Begriffs

Definition

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

Veranschaulichung

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 Halbordnung gegeben ist.

Vom Begriff der Antikette erhält man eine gute Anschauung bei Betrachtung des Hasse-Diagramms der halbgeordneten Menge $(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 $\leq 1$, besteht also stets aus höchstens einem Element. So lässt sich der Begriff demnach auch fassen: Eine Teilmenge $A\subseteq P$ einer halbgeordneten Menge $(P,\leq )$ ist genau dann eine Antikette, wenn sie 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 $\leq$ eine Kette. Die einzigen Antiketten sind die trivialen: Die leere Menge $\varnothing$ und die einelementigen Teilmengen.

Die Primzahlen

Man betrachte die natürlichen Zahlen $\mathbb {N} =\{1,2,3,\ldots \}$ als Trägermenge 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, also dass es eine natürliche Zahl $n$ gibt, sodass $k\cdot n=l$ gilt.

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

Die Teiler von 60

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

Mengen von endlichen Mengen derselben Mächtigkeit

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

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

Orbits

Die Automorphismengruppe $\operatorname {Aut} (P,\leq )$ der halbgeordneten Menge $(P,\leq )$ operiert als Untergruppe der symmetrischen Gruppe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_P} in natürlicher Weise auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} , indem als Verknüpfung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi \cdot x = \phi(x)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in P} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi \in \operatorname{Aut}(P, \leq)} genommen wird.

Die dadurch gegebenen Orbits Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{Aut}(P, \leq)\cdot x = \{\, \phi(x) \;:\; \phi\in \operatorname{Aut}(P, \leq) \,\}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in P} sind im Falle, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} endlich ist, stets Antiketten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} .

Die Spernerzahl

Definition

Die Spernerzahl (englisch Sperner number) der geordneten Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} ist definiert als das Supremum der Mächtigkeiten aller in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} vorkommenden Antiketten. Die Spernerzahl wird heute üblicherweise mit dem Buchstaben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} bezeichnet, entsprechend der Gepflogenheit in der englischsprachigen Literatur.

In der deutschsprachigen Literatur wird die Spernerzahl von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} (entsprechend dem dafür in der englischsprachigen Literatur auch geläufigen Terminus width) manchmal auch die Breite von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} genannt.

Formale Darstellung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w(P, \le) = \sup \{\, |A| \;:\; A \text{ Antikette in } (P, \le) \,\}}

Wenn aus dem Kontext klar ist, um welche geordnete Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} es sich handelt, schreibt man kurz und einfach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} .

Erläuterung

Die Spernerzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} ist stets höchstens so groß wie die Mächtigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |P|} der Trägermenge von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} . Im Falle, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w(P, \le)\ = \max \{\, |A| \;:\; A \text{ Antikette in } (P, \le) \,\}.}

Beispiele

Die reellen Zahlen

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R} hat wie jede nichtleere Kette Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w = 1} .

Die Teiler von 60

Die oben angegebene Antikette Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{\, 4, 6, 10, 15 \,\}} (siehe Hasse-Diagramm) ist die größtmögliche. Also gilt hier Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w = 4} .

Die Potenzmengen

Für die Potenzmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{P}(X)} einer endlichen Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |X|=n} Elementen gilt stets Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w(\mathcal{P}(X)) = \binom{n}{\lfloor \frac n 2 \rfloor}} . Denn genau dies besagt der Satz von Sperner.

Für unendliches Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} der Mächtigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |X| = \aleph_{\alpha}} gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w({\mathcal{P}(X)}) = 2^{\aleph_{\alpha}}} .

Verbandseigenschaften

Erklärung

Das System Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{D} = \mathcal{D}(P, \leq)} der Antiketten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} ist stets nichtleer und trägt die folgende Ordnungsrelation, welche die Ordnungsrelation von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} in natürlicher Weise auf Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{D}} fortsetzt:

Für zwei Antiketten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A, B \in \mathcal{D}} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \leq B} dann und nur dann, wenn zu jedem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b \in B} ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \in A} existiert mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \leq b} .

Die so definierte Ordnungsrelation, welche ebenfalls mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \leq} bezeichnet wird, gibt auf diesem Wege dem Antikettensystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{D}} die Struktur eines distributiven Verbands.

Das Resultat von Dilworth

Bei endlichem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} liegt nun ein spezielles Augenmerk auf dem Teilsystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{S} = \mathcal{S}(P, \leq)} der Antiketten maximaler Größe:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{S} = \{\, A \in \mathcal{D} \;:\; |A| = w(P, \le) \,\}}

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

Bei endlichem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\mathcal{S},\leq)} Unterverband von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (\mathcal{D},\leq)} , wobei die zugehörigen Verbandsoperationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \land} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lor} die folgende Darstellung haben:

(1) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \land B = \operatorname{Min}({A}\cup{B})}

(2) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \lor B = \operatorname{Max}({A}\cup{B})}

(Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A, B \in \mathcal{S}} )

Dabei wird mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{Min}(X)} bzw. mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{Max}(X)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X \subseteq P} die Teilmenge derjenigen Elemente von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} bezeichnet, welche bzgl. der induzierten Ordnungsrelation innerhalb Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X} minimal bzw. maximal sind.

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

Als Folgerung ergibt sich:

Eine endliche geordnete Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} enthält stets eine Antikette maximaler Größe, welche von allen Automorphismen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \phi \in \operatorname{Aut}(P, \leq)} auf sich selbst abgebildet wird.

Oder anders ausgedrückt:

Eine endliche geordnete Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq)} enthält stets eine Antikette maximaler Größe, welche als Vereinigung gewisser Orbits Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{Aut}(P, \leq)\cdot x} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in P} darstellbar ist.

Hierdurch gelangt man auf direktem Wege zum Satz von Sperner. Denn im Falle, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (P, \leq) = (2^M, \subseteq)} mit endlicher Grundmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ist, sind die Orbits identisch mit den Mächtigkeitsklassen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {M\choose k}} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (k = 0,\dots, \left|{M}\right| )} .

Anzahl der Antiketten endlicher Potenzmengen

Auf Richard Dedekind geht das Problem zurück, für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n \in \N_0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle X = \{ 1, 2, \ldots, n\}} die Anzahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(n)} aller Antiketten der Potenzmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{P} (X)} zu bestimmen. Dieses Problem bezeichnet man daher als Dedekind-Problem (englisch Dedekind’s problem) und die Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(n)} als Dedekind-Zahlen (englisch Dedekind numbers).

Die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(n)} ist (im Wesentlichen) identisch mit der Anzahl der monoton wachsenden surjektiven Funktionen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{P} (\{ 1, 2, \ldots, n \})} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2 = \{ 0, 1 \}} und genauso identisch mit der Anzahl der freien distributiven Verbände mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} erzeugenden Elementen.

Da diese Zahlen ein erhebliches Wachstum aufweisen, ist die exakte Bestimmung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(n)} bislang allein für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n = 0, 1, \ldots, 8} gelungen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} M(0) &= 2 \\ M(1) &= 3 \\ M(2) &= 6 \\ M(3) &= 20 \\ M(4) &= 168 \\ M(5) &= 7.581 \\ M(6) &= 7.828.354 \\ M(7) &= 2.414.682.040.998 \\ M(8) &= 56.130.437.228.687.557.907.788 \\ \end{align} }

Für eine Einschätzung der Größenordnung des Wachstums der Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(n)} 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^{\tbinom{n}{\lfloor \frac{n}{2} \rfloor }} \leq M(n) \leq 3^{\tbinom{n}{\lfloor \frac{n}{2} \rfloor }}}

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M(n) \leq 2^{{\tbinom{n}{\lfloor \frac{n}{2} \rfloor }} \cdot \bigl( 1+ \mathcal{O}{(\frac{\ln (n)}{n})} \bigr) }}

und man kennt sogar noch bessere Schranken.

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. 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.

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: Mathematische Nachrichten. Band 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. Band 10). American Mathematical Society, 1960, ISSN 0160-7634, S. 85–90. 
• Ralph Freese: An application of Dilworth's lattice of maximal antichains. In: Discrete Mathematics. Band 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, Band 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 on the Theory of Finite Sets. In: Gian-Carlo Rota (Hrsg.): Studies in Combinatorics (= Studies in Mathematics. Band 17). Math. Assoc. America, Washington, D.C. 1978, ISBN 0-88385-117-2, S. 23–79 (MR0513002). 
• D. Kleitman, M. Edelberg, D. Lubell: Maximal sized antichains in partial orders. In: Discrete Mathematics. Band 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. Band 27, Nr. 1, 1928, ISSN 0025-5874, S. 544–548, doi:10.1007/BF01171114.
• Georges Hansel: Sur le nombre des fonctions booléennes monotones de n variables. In: C. R. Acad. Sci. Paris Sér. A. Band 262, 1966, S. 1088–1090 (MR0224395). 
• Andrzej Kisielewicz: A solution of Dedekind’s problem on the number of isotone Boolean functions. In: J. Reine Angew. Math. Band 386. Washington, D.C. 1988, S. 139–144, doi:10.1515/crll.1988.386.139 (MR0936995). 
• D. Kleitman, G. Markowsky: On Dedekind’s problem: The number of Isotone Boolean functions. II. In: Trans. Amer. Math. Soc. Band 213, November 1975, S. 373–390, JSTOR:1998052 (MR0382107). 

Monographien

• Martin Aigner: Kombinatorik II: Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07949-1, doi:10.1007/978-3-642-66235-5 (MR0460127). 
• Martin Aigner: Combinatorial Theory (= Grundlehren der Mathematischen Wissenschaften. Band 234). Springer Verlag, Berlin (u. a.) 1979, ISBN 3-540-90376-3 (MR0542445). 
• Martin Aigner: Diskrete Mathematik (= Dokumente zur Geschichte der Mathematik. Band 6). 6. Auflage. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8 (MR1085963). 
• Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford 1987, ISBN 0-19-853367-5 (MR0892525). 
• Oliver Deiser: Grundbegriffe der wissenschaftlichen Mathematik. Sprache, Zahlen und erste Erkundungen. Springer Verlag, Heidelberg u. a. 2010, ISBN 978-3-642-11488-5 (Auszug in der Google-Buchsuche). 
• Konrad Engel: Sperner Theory (= Encyclopedia of Mathematics and its Applications. Band 65). Cambridge University Press, Cambridge u. a. 1997, ISBN 0-521-45206-6 (MR1429390). 
• Bernhard Ganter: Diskrete Mathematik: Geordnete Mengen (= Springer-Lehrbuch). Springer Spektrum, Berlin / Heidelberg 2013, ISBN 978-3-642-37499-9. 
• Egbert Harzheim: Ordered Sets (= Advances in Mathematics. Band 7). Springer Verlag, New York 2005, ISBN 0-387-24219-8, S. 206 ff. (MR2127991). 
• Thomas Jech: Set Theory. The Third Millennium edition, revised and expanded (= Springer Monographs in Mathematics). Springer Verlag, Berlin u. a. 2003, ISBN 3-540-44085-2 (MR1940513). 
• Stasys Jukna: Extremal Combinatorics (= Texts in Theoretical Computer Science). Springer Verlag, Heidelberg (u. a.) 2011, ISBN 978-3-642-17363-9 (MR2865719). 
• Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way (= Cambridge Mathematical Library). Cambridge University Press, Cambridge (u. a) 2009, ISBN 978-0-521-73794-4 (MR2483561). 

Weblinks

• Gy. Károlyi: Lectures on extremal set systems and two-colorings of hypergraphs. (PDF; 237 kB)
• Kombinatorische Methoden in der Informatik. (PDF; 1,36 MB; Skript einer Vorlesung von Peter Hauck, Uni Tübingen, SS 2008)