Dedekind-Zahl

Die freien distributiven Verbände der 0-, 1-, 2- und 3-stelligen, monotonen booleschen Funktionen, mit 2, 3, 6 bzw. 20 Elementen (Eine Mausbewegung über den Knoten des rechten Diagramms zeigt eine Beschreibung)

In der Mathematik sind die Dedekind-Zahlen eine schnell wachsende Folge ganzer Zahlen. Sie sind nach Richard Dedekind benannt, der sie 1897 definierte. Die Dedekind-Zahl $M(n)$ zählt die Anzahl der monotonen booleschen Funktionen in $n$ Variablen. Diese ist gleich der Anzahl der Antiketten in der Menge der Teilmengen einer $n$-elementigen Menge, der Anzahl der Elemente eines von $n$ Elementen frei erzeugten distributiven Verbandes oder gleich der Anzahl der abstrakten Simplizialkomplexe mit $n$ Elementen.

Für $M(n)$ kennt man exakte asymptotische Abschätzungen und exakte Ausdrücke in Form von Summationsformeln, aber das Dedekind-Problem, den genauen Wert zu ermitteln, bleibt schwierig. Es gibt bislang keine geschlossene Formel und der genaue Wert von $M(n)$ ist nur für $0\leq n\leq 8$ bekannt.

Definitionen

Eine n-stellige boolesche Funktion ist eine Funktion, deren Argumente $n$ boolesche Variable sind und deren Werte nur wahr oder falsch sein können, oder anders ausgedrückt, deren Ausgabe wieder eine boolesche Variable ist. Eine solche Funktion heißt monoton, wenn sich der Wert bei Änderung einer Eingangsvariable von falsch zu wahr nicht ändert oder ebenfalls von falsch zu wahr wechselt, aber niemals umgekehrt. Die Dedekind-Zahl $M(n)$ ist definiert als die Anzahl der verschiedenen $n$-stelligen, monotonen booleschen Funktionen.

Eine Antikette von Mengen, manchmal auch Sperner-Familie genannt, ist eine Familie von Mengen, bei der keine in einer anderen enthalten ist. Ist $V$ eine Menge von $n$ booleschen Variablen, so definiert eine Antikette $A$ von Teilmengen von $V$ eine $n$-stellige, monotone booleschen Funktion $f$, wobei der Funktionswert genau dann wahr ist, wenn die Menge der Eingangsvariablen mit Wert wahr ein Element der Antikette $A$ umfasst, und falsch sonst. Umgekehrt definiert jede $n$-stellige, monotone boolesche Funktion $f$ eine Antikette $A$, die aus allen minimalen Teilmengen von $V$ besteht, für die $f$ den Wert wahr annimmt, wenn mindestens die Eingangsvariablen dieser Teilmenge wahr sind. Daher ist die Dedekind-Zahl $M(n)$ gleich der Anzahl der verschiedenen Antiketten in der Potenzmenge einer $n$-elementigen Menge.

Eine dritte äquivalente Beschreibung dieser Anzahl verwendet Verbandstheorie. Für je zwei $n$-stellige, monotone boolesche Funktionen $f$ und $g$ erhält man zwei weitere solche Funktionen, nämlich $f\land g$ und $f\lor g$, das heißt deren logische Konjunktion und Adjunktion. Die Menge der $n$-stelligen, monotonen booleschen Funktionen bildet mit diesen Operationen einen distributiven Verband. Es handelt sich um den distributiven Verband, der sich gemäß dem Darstellungssatz von Birkhoff aus der partiell geordneten Menge ergibt, die durch die Teilmengen einer $n$-elementigen Menge mit der Inklusion als Ordnung entsteht. Diese Konstruktion erzeugt den freien distributiven Verband mit $n$ Erzeugenden. Die Dedekind-Zahl $M(n)$ ist also die Anzahl der Elemente des freien distributiven Verbandes mit $n$ Erzeugenden.

Die Dedekind-Zahlen $M(n)$ sind auch (um eins größer als) die Anzahlen der abstrakten Simplizialkomplexe mit $n$ Elementen, das heißt der Familien von Mengen, die mit jeder Menge auch alle Teilmengen enthalten. Jede Antikette bestimmt einen abstrakten Simplizialkomplex, nämlich die Menge der Teilmengen der Antiketten-Elemente, und umgekehrt bilden die maximalen Simplizes eines abstrakten Simplizialkomplexes eine Antikette.

Beispiele

Für $n=2$ gibt es sechs monotone boolesche Funktionen und sechs Antiketten auf der Menge $\{x,y\}$, die einander wie folgt entsprechen.

• Die Funktion $f(x,y)=falsch$, das heißt die Funktion, die unabhängig von den Argumenten stets falsch zurückgibt, gehört zur leeren Antikette $\emptyset$.
• Die logische Konjunktion $f(x,y)=x\land y$ gehört zur Antikette $\{\{x,y\}\}$, die nur aus dem Element $\{x,y\}$ besteht.
• Die Funktion $f(x,y)=x$, das heißt die Projektion auf das erste Argument, entspricht der einelementigen Antikette $\{\{x\}\}$.
• Die Funktion $f(x,y)=y$, das heißt die Projektion auf das zweite Argument, entspricht der einelementigen Antikette $\{\{y\}\}$.
• Die logische Adjunktion $f(x,y)=x\lor y$ gehört zur Antikette $\{\{x\},\{y\}\}$, die aus den beiden Elementen $\{x\}$ und $\{y\}$ besteht.
• Schließlich korrespondiert die konstante Funktion $f(x,y)=wahr$ zur Antikette $\{\emptyset \}$, deren einziges Element die leere Menge ist.

Werte

Die exakten Werte der Dedekind-Zahlen $M(n)$ sind nur für $0\leq n\leq 8$ bekannt, diese sind:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788   (Folge A000372 in OEIS).

Die ersten sechs dieser Zahlen wurden von Church ermittelt. $M(6)$ wurde von Ward berechnet, $M(7)$ von Church, Berman & Köhler, und $M(8)$ geht auf Wiedemann zurück.

Ist $n$ gerade, so muss auch $M(n)$ gerade sein. Die Berechnung von $M(5)$ widerlegte die auf Garrett Birkhoff zurückgehende Vermutung, nach der $M(n)$ stets durch $(2n-1)(2n-2)$ teilbar sein sollte.

Summationsformeln

Kisielewicz hat die logische Definition von Antiketten in folgende arithmetische Formel zur Bestimmung der Dedekind-Zahlen übersetzt:

$M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{j}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right)$

Dabei ist $b_{i}^{k}$ das $i$-te Bit der Zahl $k$, was mittels der Abrundungsfunktion $\left\lfloor .\right\rfloor$ auch als

$b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor$

geschrieben werden kann. Allerdings ist diese Formel zur Bestimmung von $M(n)$ wegen der hohen Anzahl der Summanden für große $n$ nicht hilfreich.

Asymptotisches Wachstum

Die Logarithmen der Dedekind-Zahlen können durch die Ungleichungen

${n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).$

abgeschätzt werden. Die linke Ungleichung entsteht durch Abzählen der Antiketten mit genau $\lfloor n/2\rfloor$ Elementen und die rechte Ungleichung wurde von Kleitman und Markowsky bewiesen.

Korshunov erzielte noch genauere Abschätzungen:

$M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)$

für gerade $n$ und

$M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor +1}\exp(b(n)+c(n))$

für ungerade $n$, wobei

$a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),$

$b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3})$

und

$c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).$

Die wesentliche Idee hinter diesen Abschätzungen ist, dass die meisten Antiketten nur aus Mengen mit Mächtigkeiten nahe an $\textstyle {\frac {n}{2}}$ bestehen.