www.wikidata.de-de.nina.az

Dedekind Zahl In der Mathematik sind die en eine schnell wachsende Folge ganzer Zahlen Sie sind nach Richard Dedekind be

Dedekind-Zahl

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 zählt die Anzahl der monotonen booleschen Funktionen in Variablen. Diese ist gleich der Anzahl der Antiketten in der Menge der Teilmengen einer -elementigen Menge, der Anzahl der Elemente eines von Elementen frei erzeugten distributiven Verbandes oder gleich der Anzahl der abstrakten Simplizialkomplexe mit Elementen.

A und BA und CB und C(A und B) oder (A und C)(A und B) oder (B und C)(A und C) oder (B und C)ABC(A oder B) und (A oder C) und (B oder C) <====> (A und B) oder (A und C) oder (B und C)(A oder B) und (A oder C)(A oder B) und (B oder C)(A oder C) und (B oder C)A oder BA oder CB oder CA oder B oder Cwahr
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)

Für 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 ist nur für bekannt. (Folge A000372 in OEIS)

Definitionen Bearbeiten

Eine n-stellige boolesche Funktion ist eine Funktion, deren Argumente 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 ist definiert als die Anzahl der verschiedenen -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 eine Menge von booleschen Variablen, so definiert eine Antikette von Teilmengen von eine -stellige, monotone booleschen Funktion , wobei der Funktionswert genau dann wahr ist, wenn die Menge der Eingangsvariablen mit Wert wahr ein Element der Antikette umfasst, und falsch sonst. Umgekehrt definiert jede -stellige, monotone boolesche Funktion eine Antikette , die aus allen minimalen Teilmengen von besteht, für die den Wert wahr annimmt, wenn mindestens die Eingangsvariablen dieser Teilmenge wahr sind. Daher ist die Dedekind-Zahl gleich der Anzahl der verschiedenen Antiketten in der Potenzmenge einer -elementigen Menge.

Eine dritte äquivalente Beschreibung dieser Anzahl verwendet Verbandstheorie. Für je zwei -stellige, monotone boolesche Funktionen und erhält man zwei weitere solche Funktionen, nämlich und , das heißt deren logische Konjunktion und Adjunktion. Die Menge der -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 -elementigen Menge mit der Inklusion als Ordnung entsteht. Diese Konstruktion erzeugt den freien distributiven Verband mit Erzeugenden. Die Dedekind-Zahl ist also die Anzahl der Elemente des freien distributiven Verbandes mit Erzeugenden.

Die Dedekind-Zahlen sind auch (um eins größer als) die Anzahlen der abstrakten Simplizialkomplexe mit 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 Bearbeiten

Für gibt es sechs monotone boolesche Funktionen und sechs Antiketten auf der Menge , die einander wie folgt entsprechen.

  • Die Funktion , das heißt die Funktion, die unabhängig von den Argumenten stets falsch zurückgibt, gehört zur leeren Antikette .
  • Die logische Konjunktion gehört zur Antikette , die nur aus dem Element besteht.
  • Die Funktion , das heißt die Projektion auf das erste Argument, entspricht der einelementigen Antikette .
  • Die Funktion , das heißt die Projektion auf das zweite Argument, entspricht der einelementigen Antikette .
  • Die logische Adjunktion gehört zur Antikette , die aus den beiden Elementen und besteht.
  • Schließlich korrespondiert die konstante Funktion zur Antikette , deren einziges Element die leere Menge ist.

Werte Bearbeiten

Die exakten Werte der Dedekind-Zahlen sind für bekannt (Folge A000372 in OEIS):

n M(n) erstmals berechnet
0 2 Dedekind (1897)
1 3
2 6
3 20
4 168
5 7.581 Church (1940)
6 7.828.354 Ward (1946)
7 2.414.682.040.998 Church (1965), verifiziert von Berman und Köhler (1976)
8 56.130.437.228.687.557.907.788 Wiedemann (1991)
9 286.386.577.668.298.411.128.469.151.667.598.498.812.366 gleichzeitig von Jäkel (2023) und Van Hirtum et al. (2023)

DorFuchs erstveröffentlichte am 31. Oktober 2023 auf YouTube Approximationen von Alex Fihman, der bereits die ersten Stellen von korrekt vorhergesagt hatte. Fihman berechnete den Wert von mit verschiedenen Berechnungsmethoden auf zwischen ca. 8,89197 · 1078 und 8,93619 · 1078.

Ist gerade, so muss auch gerade sein. Die Berechnung von widerlegte die auf Garrett Birkhoff zurückgehende Vermutung, nach der stets durch teilbar sein sollte.

Summationsformeln Bearbeiten

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

Dabei ist das -te Bit der Zahl , was mittels der Abrundungsfunktion auch als

geschrieben werden kann. Allerdings ist diese Formel zur Bestimmung von wegen der hohen Anzahl der Summanden schon für nicht hilfreich.

Asymptotisches Wachstum Bearbeiten

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

abgeschätzt werden. Die linke Ungleichung entsteht durch Abzählen der Antiketten mit genau Elementen und die rechte Ungleichung wurde von Kleitman und Markowsky bewiesen.

Korshunov erzielte noch genauere Abschätzungen:

für gerade und

für ungerade , wobei

und

Die wesentliche Idee hinter diesen Abschätzungen ist, dass die meisten Antiketten nur aus Mengen mit Mächtigkeiten nahe an bestehen.

Einzelnachweise Bearbeiten

  1. Richard Dedekind: Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler. In: Gesammelte Werke. Band 2, 1897, S. 732–734.
  2. ↑ Daniel Kleitman, G. Markowsky: On Dedekind’s problem: the number of isotone Boolean functions. II. In: Transactions of the American Mathematical Society. Band 213, 1975, S. 373–390, doi:10.2307/1998052.
  3. ↑ A. D. Korshunov: The number of monotone Boolean functions. In: Problemy Kibernet. Band 38, 1981, S. 5–108.
  4. ↑ Jeff Kahn: Entropy, independent sets and antichains: a new approach to Dedekind’s problem. In: Proceedings of the American Mathematical Society. Band 130, 2002, S. 371–378, doi:10.1090/S0002-9939-01-06058-0.
  5. ↑ Andrzej Kisielewicz: A solution of Dedekind’s problem on the number of isotone Boolean functions. In: Journal für die Reine und Angewandte Mathematik. Band 386, 1988, S. 139–144, doi:10.1515/crll.1988.386.139.
  6. ↑ Randolph Church: Numerical analysis of certain free distributive structures. In: Duke Mathematical Journal. Band 36, 1940, S. 732–734, doi:10.1215/s0012-7094-40-00655-x.
  7. ↑ Randolph Church: Enumeration by rank of the free distributive lattice with 7 generators. In: Notices of the American Mathematical Society. Band 11, 1965, S. 724.
  8. ↑ Nejib Zaguia: Isotone maps: enumeration and structure. In: Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Kanada, 4. Mai 1991). 1993, S. 421–430.
  9. Morgan Ward: Note on the order of free distributive lattices. In: Transactions of the American Mathematical Society. Band 52, 1946, S. 423, doi:10.1090/S0002-9904-1946-08568-7.
  10. Joel Berman, Peter Köhler: Cardinalities of finite distributive lattices. In: Mitt. Math. Sem. Gießen. Band 121, 1976, S. 103–124.
  11. Doug Wiedemann: A computation of the eighth Dedekind number. In: Order. Band 8, 1991, S. 5–6, doi:10.1007/BF003858087.
  12. Christian Jäkel: A computation of the ninth Dedekind Number. 3. April 2023, arxiv:2304.00895 (englisch).
  13. Christian Jäkel: A computation of the ninth Dedekind Number. In: Journal of Computational Algebra. 2023, doi:10.1016/j.jaca.2023.100006 (englisch).
  14. Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, Christian Plessl: A computation of D(9) using FPGA Supercomputing. 6. April 2023, arxiv:2304.03039 (englisch).
  15. DorFuchs: Die 9. Dedekind-Zahl wurde nach 32 Jahren Suche gefunden! (ab 0:11:58) auf YouTube, 31. Oktober 2023.
  16. Koichi Yamamoto: Note on the order of free distributive lattices. In: Science Reports of the Kanazawa University. Band 1, 1953, S. 5–6.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Mathematik sind die Dedekind Zahlen eine schnell wachsende Folge ganzer Zahlen Sie sind nach Richard Dedekind benannt der sie 1897 definierte 1 Die Dedekind Zahl M n displaystyle M n zahlt die Anzahl der monotonen booleschen Funktionen in n displaystyle n Variablen Diese ist gleich der Anzahl der Antiketten in der Menge der Teilmengen einer n displaystyle n elementigen Menge der Anzahl der Elemente eines von n displaystyle n Elementen frei erzeugten distributiven Verbandes oder gleich der Anzahl der abstrakten Simplizialkomplexe mit n displaystyle n Elementen Die freien distributiven Verbande der 0 1 2 und 3 stelligen monotonen booleschen Funktionen mit 2 3 6 bzw 20 Elementen Eine Mausbewegung uber den Knoten des rechten Diagramms zeigt eine Beschreibung Fur M n displaystyle M n kennt man exakte asymptotische Abschatzungen 2 3 4 und exakte Ausdrucke in Form von Summationsformeln 5 aber das Dedekind Problem den genauen Wert zu ermitteln bleibt schwierig Es gibt bislang keine geschlossene Formel und der genaue Wert von M n displaystyle M n ist nur fur 0 n 9 displaystyle 0 leq n leq 9 bekannt Folge A000372 in OEIS Inhaltsverzeichnis 1 Definitionen 2 Beispiele 3 Werte 4 Summationsformeln 5 Asymptotisches Wachstum 6 EinzelnachweiseDefinitionen BearbeitenEine n stellige boolesche Funktion ist eine Funktion deren Argumente n displaystyle n nbsp boolesche Variable sind und deren Werte nur wahr oder falsch sein konnen oder anders ausgedruckt deren Ausgabe wieder eine boolesche Variable ist Eine solche Funktion heisst monoton wenn sich der Wert bei Anderung einer Eingangsvariable von falsch zu wahr nicht andert oder ebenfalls von falsch zu wahr wechselt aber niemals umgekehrt Die Dedekind Zahl M n displaystyle M n nbsp ist definiert als die Anzahl der verschiedenen n displaystyle n nbsp 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 displaystyle V nbsp eine Menge von n displaystyle n nbsp booleschen Variablen so definiert eine Antikette A displaystyle A nbsp von Teilmengen von V displaystyle V nbsp eine n displaystyle n nbsp stellige monotone booleschen Funktion f displaystyle f nbsp wobei der Funktionswert genau dann wahr ist wenn die Menge der Eingangsvariablen mit Wert wahr ein Element der Antikette A displaystyle A nbsp umfasst und falsch sonst Umgekehrt definiert jede n displaystyle n nbsp stellige monotone boolesche Funktion f displaystyle f nbsp eine Antikette A displaystyle A nbsp die aus allen minimalen Teilmengen von V displaystyle V nbsp besteht fur die f displaystyle f nbsp den Wert wahr annimmt wenn mindestens die Eingangsvariablen dieser Teilmenge wahr sind Daher ist die Dedekind Zahl M n displaystyle M n nbsp gleich der Anzahl der verschiedenen Antiketten in der Potenzmenge einer n displaystyle n nbsp elementigen Menge 4 Eine dritte aquivalente Beschreibung dieser Anzahl verwendet Verbandstheorie Fur je zwei n displaystyle n nbsp stellige monotone boolesche Funktionen f displaystyle f nbsp und g displaystyle g nbsp erhalt man zwei weitere solche Funktionen namlich f g displaystyle f land g nbsp und f g displaystyle f lor g nbsp das heisst deren logische Konjunktion und Adjunktion Die Menge der n displaystyle n nbsp stelligen monotonen booleschen Funktionen bildet mit diesen Operationen einen distributiven Verband Es handelt sich um den distributiven Verband der sich gemass dem Darstellungssatz von Birkhoff aus der partiell geordneten Menge ergibt die durch die Teilmengen einer n displaystyle n nbsp elementigen Menge mit der Inklusion als Ordnung entsteht Diese Konstruktion erzeugt den freien distributiven Verband mit n displaystyle n nbsp Erzeugenden Die Dedekind Zahl M n displaystyle M n nbsp ist also die Anzahl der Elemente des freien distributiven Verbandes mit n displaystyle n nbsp Erzeugenden 6 7 8 Die Dedekind Zahlen M n displaystyle M n nbsp sind auch um eins grosser als die Anzahlen der abstrakten Simplizialkomplexe mit n displaystyle n nbsp Elementen das heisst der Familien von Mengen die mit jeder Menge auch alle Teilmengen enthalten Jede Antikette bestimmt einen abstrakten Simplizialkomplex namlich die Menge der Teilmengen der Antiketten Elemente und umgekehrt bilden die maximalen Simplizes eines abstrakten Simplizialkomplexes eine Antikette 5 Beispiele BearbeitenFur n 2 displaystyle n 2 nbsp gibt es sechs monotone boolesche Funktionen und sechs Antiketten auf der Menge x y displaystyle x y nbsp die einander wie folgt entsprechen Die Funktion f x y f a l s c h displaystyle f x y falsch nbsp das heisst die Funktion die unabhangig von den Argumenten stets falsch zuruckgibt gehort zur leeren Antikette displaystyle emptyset nbsp Die logische Konjunktion f x y x y displaystyle f x y x land y nbsp gehort zur Antikette x y displaystyle x y nbsp die nur aus dem Element x y displaystyle x y nbsp besteht Die Funktion f x y x displaystyle f x y x nbsp das heisst die Projektion auf das erste Argument entspricht der einelementigen Antikette x displaystyle x nbsp Die Funktion f x y y displaystyle f x y y nbsp das heisst die Projektion auf das zweite Argument entspricht der einelementigen Antikette y displaystyle y nbsp Die logische Adjunktion f x y x y displaystyle f x y x lor y nbsp gehort zur Antikette x y displaystyle x y nbsp die aus den beiden Elementen x displaystyle x nbsp und y displaystyle y nbsp besteht Schliesslich korrespondiert die konstante Funktion f x y w a h r displaystyle f x y wahr nbsp zur Antikette displaystyle emptyset nbsp deren einziges Element die leere Menge ist Werte BearbeitenDie exakten Werte der Dedekind Zahlen M n displaystyle M n nbsp sind fur 0 n 9 displaystyle 0 leq n leq 9 nbsp bekannt Folge A000372 in OEIS n M n erstmals berechnet0 2 Dedekind 1897 1 32 63 204 1685 7 581 Church 1940 6 6 7 828 354 Ward 1946 9 7 2 414 682 040 998 Church 1965 7 verifiziert von Berman und Kohler 1976 10 8 56 130 437 228 687 557 907 788 Wiedemann 1991 11 9 286 386 577 668 298 411 128 469 151 667 598 498 812 366 gleichzeitig von Jakel 2023 12 13 und Van Hirtum et al 2023 14 DorFuchs erstveroffentlichte am 31 Oktober 2023 auf YouTube Approximationen von Alex Fihman der bereits die ersten Stellen von M 9 displaystyle M 9 nbsp korrekt vorhergesagt hatte Fihman berechnete den Wert von M 10 displaystyle M 10 nbsp mit verschiedenen Berechnungsmethoden auf zwischen ca 8 89197 1078 und 8 93619 1078 15 Ist n displaystyle n nbsp gerade so muss auch M n displaystyle M n nbsp gerade sein 16 Die Berechnung von M 5 displaystyle M 5 nbsp widerlegte die auf Garrett Birkhoff zuruckgehende Vermutung nach der M n displaystyle M n nbsp stets durch 2 n 1 2 n 2 displaystyle 2n 1 2n 2 nbsp teilbar sein sollte 6 Summationsformeln BearbeitenKisielewicz 5 hat die logische Definition von Antiketten in folgende arithmetische Formel zur Bestimmung der Dedekind Zahlen ubersetzt M n k 1 2 2 n j 1 2 n 1 i 0 j 1 1 b i k b j k m 0 log 2 i 1 b m i b m i b m j displaystyle 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 nbsp Dabei ist b i k displaystyle b i k nbsp das i displaystyle i nbsp te Bit der Zahl k displaystyle k nbsp was mittels der Abrundungsfunktion displaystyle left lfloor right rfloor nbsp auch als b i k k 2 i 2 k 2 i 1 displaystyle b i k left lfloor frac k 2 i right rfloor 2 left lfloor frac k 2 i 1 right rfloor nbsp geschrieben werden kann Allerdings ist diese Formel zur Bestimmung von M n displaystyle M n nbsp wegen der hohen Anzahl der Summanden schon fur n 6 displaystyle n 6 nbsp nicht hilfreich Asymptotisches Wachstum BearbeitenDie Logarithmen der Dedekind Zahlen konnen durch die Ungleichungen n n 2 log 2 M n n n 2 1 O log n n displaystyle 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 nbsp abgeschatzt werden Die linke Ungleichung entsteht durch Abzahlen der Antiketten mit genau n 2 displaystyle lfloor n 2 rfloor nbsp Elementen und die rechte Ungleichung wurde von Kleitman und Markowsky 2 bewiesen Korshunov 3 erzielte noch genauere Abschatzungen 8 M n 1 o 1 2 n n 2 exp a n displaystyle M n 1 o 1 2 n choose lfloor n 2 rfloor exp a n nbsp fur gerade n displaystyle n nbsp und M n 1 o 1 2 n n 2 1 exp b n c n displaystyle M n 1 o 1 2 n choose lfloor n 2 rfloor 1 exp b n c n nbsp fur ungerade n displaystyle n nbsp wobei a n n n 2 1 2 n 2 n 2 2 n 5 n 2 n 4 displaystyle a n n choose n 2 1 2 n 2 n 2 2 n 5 n2 n 4 nbsp b n n n 3 2 2 n 3 2 n 2 2 n 6 n 2 n 3 displaystyle b n n choose n 3 2 2 n 3 2 n 2 2 n 6 n2 n 3 nbsp und c n n n 1 2 2 n 1 2 n 2 2 n 4 displaystyle c n n choose n 1 2 2 n 1 2 n 2 2 n 4 nbsp Die wesentliche Idee hinter diesen Abschatzungen ist dass die meisten Antiketten nur aus Mengen mit Machtigkeiten nahe an n 2 displaystyle textstyle frac n 2 nbsp bestehen 8 Einzelnachweise Bearbeiten Richard Dedekind Uber Zerlegungen von Zahlen durch ihre grossten gemeinsamen Teiler In Gesammelte Werke Band 2 1897 S 732 734 a b Daniel Kleitman G Markowsky On Dedekind s problem the number of isotone Boolean functions II In Transactions of the American Mathematical Society Band 213 1975 S 373 390 doi 10 2307 1998052 a b A D Korshunov The number of monotone Boolean functions In Problemy Kibernet Band 38 1981 S 5 108 a b Jeff Kahn Entropy independent sets and antichains a new approach to Dedekind s problem In Proceedings of the American Mathematical Society Band 130 2002 S 371 378 doi 10 1090 S0002 9939 01 06058 0 a b c Andrzej Kisielewicz A solution of Dedekind s problem on the number of isotone Boolean functions In Journal fur die Reine und Angewandte Mathematik Band 386 1988 S 139 144 doi 10 1515 crll 1988 386 139 a b c Randolph Church Numerical analysis of certain free distributive structures In Duke Mathematical Journal Band 36 1940 S 732 734 doi 10 1215 s0012 7094 40 00655 x a b Randolph Church Enumeration by rank of the free distributive lattice with 7 generators In Notices of the American Mathematical Society Band 11 1965 S 724 a b c Nejib Zaguia Isotone maps enumeration and structure In Finite and Infinite Combinatorics in Sets and Logic Proc NATO Advanced Study Inst Banff Alberta Kanada 4 Mai 1991 1993 S 421 430 Morgan Ward Note on the order of free distributive lattices In Transactions of the American Mathematical Society Band 52 1946 S 423 doi 10 1090 S0002 9904 1946 08568 7 Joel Berman Peter Kohler Cardinalities of finite distributive lattices In Mitt Math Sem Giessen Band 121 1976 S 103 124 Doug Wiedemann A computation of the eighth Dedekind number In Order Band 8 1991 S 5 6 doi 10 1007 BF003858087 Christian Jakel A computation of the ninth Dedekind Number 3 April 2023 arxiv 2304 00895 englisch Christian Jakel A computation of the ninth Dedekind Number In Journal of Computational Algebra 2023 doi 10 1016 j jaca 2023 100006 englisch Lennart Van Hirtum Patrick De Causmaecker Jens Goemaere Tobias Kenter Heinrich Riebler Michael Lass Christian Plessl A computation of D 9 using FPGA Supercomputing 6 April 2023 arxiv 2304 03039 englisch DorFuchs Die 9 Dedekind Zahl wurde nach 32 Jahren Suche gefunden ab 0 11 58 auf YouTube 31 Oktober 2023 Koichi Yamamoto Note on the order of free distributive lattices In Science Reports of the Kanazawa University Band 1 1953 S 5 6 Abgerufen von https de wikipedia org w index php title Dedekind Zahl amp oldid 238687109