Просмотр кода страницы Дедекиндово число

{{не путать|Дедекиндово сечение|дедекиндовыми сечениями|способом построения действительных чисел}}
<imagemap>
Файл:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right|Свободные дистрибутивные решётки монотонных булевых функций от 0, 1, 2 и 3 аргументов с 2, 3, 6 и 20 элементами соответственно <small>(наведите мышь на правую диаграмму, чтобы видеть описание)</small>
circle 659 623 30 [[Файл:Boolean function 0000 0000.svg|противоречие]]
circle 658 552 35 [[Файл:Boolean functions like 1000 0000.svg|A и B и C]]
circle 587 480 35 [[Файл:Boolean functions like 1000 1000.svg|A и B]]
circle 659 481 35 [[Файл:Boolean functions like 1010 0000.svg|A и C]]
circle 729 481 35 [[Файл:Boolean functions like 1100 0000.svg|B и C]]
circle 588 410 35 [[Файл:Boolean functions like 1010 1000.svg|(A и B) или (A и C)]]
circle 658 410 35 [[Файл:Boolean functions like 1100 1000.svg|(A и B) или (B и C)]]
circle 729 410 35 [[Файл:Boolean functions like 1110 0000.svg|(A и C) или (B и C)]]
circle 548 339 30 [[Файл:Boolean functions like 1010 1010.svg|A]]
circle 604 339 30 [[Файл:Boolean functions like 1100 1100.svg|B]]
circle 758 339 30 [[Файл:Boolean functions like 1111 0000.svg|C]]
circle 661 339 35 [[Файл:Boolean functions like 1110 1000.svg|(A или B) и (A или C) и (B или C) <====> (A и B) или (A и C) или (B и C)]]
circle 588 268 35 [[Файл:Boolean functions like 1110 1010.svg|(A или B) и (A или C)]]
circle 659 267 35 [[Файл:Boolean functions like 1110 1100.svg|(A или B) и (B или C)]]
circle 729 268 35 [[Файл:Boolean functions like 1111 1000.svg|(A или C) и (B или C)]]
circle 588 197 35 [[Файл:Boolean functions like 1110 1110.svg|A или B]]
circle 658 197 35 [[Файл:Boolean functions like 1111 1010.svg|A или C]]
circle 729 197 35 [[Файл:Boolean functions like 1111 1100.svg|B или C]]
circle 658 126 35 [[Файл:Boolean functions like 1111 1110.svg|A или B или C]]
circle 659 56 30 [[Файл:Boolean function 1111 1111.svg|тавтология]]
desc bottom-left
</imagemap>
'''Дедекиндово число''' — число <math>M(n)</math>, равное количеству [[Монотонная функция|монотонных булевых функций]] от <math>n</math> переменных. Эквивалентные определения: число [[Антицепь|антицепей]] подмножеств <math>n</math>-элементного множества; число элементов в {{не переведено 5|Дистрибутивная решётка|свободной дистрибутивной решётке||free distributive lattice}} с <math>n</math> производящими; число {{не переведено 5|Абстрактный симплициальный комплекс|абстрактных симплициальных комплексов||abstract simplicial complex}} с <math>n</math> элементами.

[[Числовая последовательность|Последовательность]] <math>(M(n))</math> — быстрорастущая, и хотя известны [[Асимптотическое разложение|асимптотические]] оценки <math>M(n)</math>{{sfn|Kleitman, Markowsky|1975}}{{sfn|Коршунов|1981}}{{sfn|Kahn|2002}} и точное выражение в виде [[Сумма (математика)|суммы]]{{sfn|Kisielewicz|1988}}, но явной [[Аналитическое решение|вычислительной формулы]] нет, в связи с чем точное нахождение дедекиндовых чисел остаётся крайне сложной вычислительной задачей; по состоянию {{на|2023}} точные значения известны для <math>n \leqslant 9</math><ref>{{OEIS|id=A000372}}</ref>:
: 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366.

{{Якорь|Задача Дедекинда}}Числа от <math>M(0)</math> до <math>M(4)</math> вычислил [[Дедекинд, Рихард|Дедекинд]] в [[1897 год в науке|1897 году]] и сформулировал ''задачу Дедекинда'' — найти способ вычисления последующих чисел. Число <math>M(5)</math> вычислил [[Чёрч, Алонзо|Чёрч]] в 1940 году{{sfn|Church|1940}}, результат опроверг гипотезу [[Биркгоф, Гаррет|Биркгофа]], что <math>M(n)</math> всегда делится на <math>(2n-1)(2n-2)</math>{{sfn|Church|1940}}. Числа <math>M(6)</math>, <math>M(7)</math>, <math>M(8)</math>, <math>M(9)</math> были вычислены соответственно в 1946{{sfn|Ward|1946}}, 1965{{sfn|Church|1965}}{{sfn|Berman, Köhler|1976}}, 1991{{sfn|Wiedemann|1991}} и 2023<ref>{{статья|arxiv=2304.00895|заглавие=A computation of the ninth Dedekind Number|издание=Arxiv.org|автор=Christian Jäkel|год=2023}}</ref> годах.

Для нахождения <math>M(8)</math> использовался суперкомпьютер {{iw|Cray 2}}. Число <math>M(9)</math> было получено двумя независимыми группами математиков: [[Якель, Кристиан|Кристиан Якель]] из Германии применил техники [[Анализ формальных понятий|анализа формальных понятий]] и для вычислительной процедуры использовал [[GPGPU|графический ускоритель]] (5311 машиночаса на [[Nvidia A100]]); второй группе математиков из Бельгии потребовалось 47 тыс. машиночасов вычислений на [[ПЛИС]] {{iw|Stratix}} 10 GX под управлением [[суперкомпьютер]]а ''Noctua 2''<ref>{{Cite web |url=https://top500.org/system/180071/ |title=Noctua 2 - BullSequana XH2000, AMD EPYC 7763 64C 2.45GHz, InfiniBand HDR100 {{!}} TOP500<!-- Заголовок добавлен ботом --> |access-date=2023-06-29 |archive-date=2023-06-29 |archive-url=https://web.archive.org/web/20230629201531/https://top500.org/system/180071/ |deadlink=no }}</ref>, занявших около трёх месяцев<ref>{{cite web | url = https://nplus1.ru/news/2023/06/27/dedekind-nine | title = Математики нашли девятое дедекиндово число. В нем оказалось 42 знака. Это 286386577668298411128469151667598498812366 | website = [[N + 1]] | date = 2023-06-27 | author = Александр Дубов | access-date = 2023-06-28 | archive-date = 2023-06-28 | archive-url = https://web.archive.org/web/20230628161007/https://nplus1.ru/news/2023/06/27/dedekind-nine | deadlink = no }}</ref><ref>{{статья | arxiv = 2304.03039 | заглавие = A computation of D(9) using FPGA Supercomputing | автор = Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, Christian Plessl | дата = 2023-04-06}}</ref>. Обе группы получили одинаковый результат вычислений числа <math>M(9)</math>, Якель опубликовал препринт на три дня раньше бельгийских коллег.

Если <math>n</math> чётно, то <math>M(n)</math> также должно быть чётным{{sfn|Yamamoto|1953}}.

Точная формула для вычисления дедекиндовых чисел на основе логического определения [[Антицепь|антицепей]] была выведена в 1988 году{{sfn|Kisielewicz|1988}}:
: <math>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)</math>,
где <math>b_i^k</math> является <math>i</math>-м [[бит]]ом числа <math>k</math>,
который может быть записан с помощью [[Целая часть|округления вниз]]:
: <math>b_i^k=\left\lfloor\frac{k}{2^i}\right\rfloor - 2\left\lfloor\frac{k}{2^{i+1}}\right\rfloor</math>,
однако она бесполезна для практического вычисления значений <math>M(n)</math> для больших <math>n</math> ввиду большого числа членов суммирования.

В 2014 году был найден ещё один вариант формулы, с помощью которой суммированием можно найти дедекиндовы числа:

: <math>M(n+2)=\sum_{\alpha,\beta\in M_n} \left(|[\bot,\alpha]|2^{C_\alpha,\beta}|[\beta,\top]|\right)</math>

Эта формула позволяет разложить решетку антицепей на подрешетки в пространствах меньшей размерности.

[[Логарифм]] дедекиндова числа можно оценить с помощью границ:
: <math>{n\choose \lfloor n/2\rfloor}\leqslant \log_2 M(n)\leqslant {n\choose \lfloor n/2\rfloor}\left(1+O\left(\frac{\log n}{n}\right)\right)</math>,
где неравенство слева подсчитывает число антицепей, в которых каждое множество имеет в точности <math>\lfloor n/2\rfloor</math> элементов; правая часть неравенства установлена в 1975 году{{sfn|Kleitman, Markowsky|1975}}.

В 1981 году{{sfn|Коршунов|1981}} были даны более точные оценки{{sfn|Zaguia|1993}}:
: <math>M(n)=(1+o(1)) 2^{n\choose \lfloor n/2\rfloor}\exp a(n)</math>
для чётных <math>n</math> и:
: <math>M(n)=(1+o(1)) 2^{n\choose \lfloor n/2\rfloor + 1}\exp (b(n)+c(n))</math>
для нечётных <math>n</math>, где
: <math>a(n)={n\choose n/2-1}(2^{-n/2} + n^2 2^{-n-5} - n2^{-n-4})</math>,
: <math>b(n)={n\choose (n-3)/2}(2^{-(n+3)/2} + n^2 2^{-n-6} - n2^{-n-3})</math>,
: <math>c(n)={n\choose (n-1)/2}(2^{-(n+1)/2} + n^2 2^{-n-4})</math>.
Основная идея этих оценок заключается в том, что в большинстве антицепей все множества имеют размеры, очень близкие к <math>n/2</math>{{sfn|Zaguia|1993}}. Для <math>n=2, 4, 6, 8</math> формула даёт оценку, которая имеет ошибку в 9,8 %, 10,2 %, 4,1 % и −3,3 % соответственно{{r|Brown}}.

== Пример ==
Для <math>n=2</math> существует шесть монотонных булевых функций и шесть антицепей подмножеств двухэлементного множества <math>\{x,y\}</math>:
* функция <math>f(x,y) = \bot</math>, игнорирующая входные значения и всегда возвращающая <math>\bot</math>, соответствует [[Пустое множество|пустой антицепи]] <math>\varnothing</math>;
* [[Конъюнкция|логическая конъюнкция]] <math>f(x,y)=x\wedge y</math> соответствует антицепи <math>\{\{x,y\}\}</math>, содержащей единственное множество <math>\{x,y\}</math>;
* функция <math>f(x,y)=x</math>, игнорирующая второй аргумент и возвращающая первый аргумент, соответствует антицепи <math>\{\{x\}\}</math>, содержащей единственное множество <math>\{x\}</math>;
* функция <math>f(x,y)=y</math>, игнорирующая первый аргумент и возвращающая второй аргумент, соответствует антицепи <math>\{\{y\}\}</math>, содержащей единственное множество <math>\{y\}</math>;
* [[Дизъюнкция|логическая дизъюнкция]] <math>f(x,y)=x \vee y</math> соответствует антицепи <math>\{\{x\},\{y\}\}</math>, содержащей два множества <math>\{x\}</math> и <math>\{y\}</math>;
* функция <math>f(x,y)=\top</math>, игнорирующая входные значения и всегда возвращающая истинное значение, соответствует антицепи <math>\{\varnothing\}</math>, содержащей только пустое множество.

== Примечания ==
{{примечания|2|refs=
<ref name=Brown>{{citation|first=K. S.|last=Brown|заглавие=Generating the monotone Boolean functions|url=https://www.mathpages.com/home/kmath094/kmath094.htm}}</ref>
}}

== Литература ==
* {{статья
|автор=Joel Berman, Peter Köhler
|ref=Berman, Köhler
|mr=0485609
|издание=Mitt. Math. Sem. Giessen
|страницы=103–124
|заглавие=Cardinalities of finite distributive lattices
|том=121
|год=1976}}
* {{статья
|ref=Church
|автор=Randolph Church
|mr=0002842
|издание=Duke Mathematical Journal
|страницы=732–734
|заглавие=Numerical analysis of certain free distributive structures
|ссылка=https://archive.org/details/sim_duke-mathematical-journal_1940_6/page/732
|том=6
|год=1940
|doi=10.1215/s0012-7094-40-00655-x}}.
* {{статья
|ref=Church
|автор=Randolph Church
|издание=Notices of the American Mathematical Society
|страницы=724
|заглавие=Enumeration by rank of the free distributive lattice with 7 generators
|том=11
|год=1965}}. Как процитировано Видерманом ({{harvtxt|Wiedemann|1991}}).
* {{книга
|автор=[[Дедекинд, Юлиус Вильгельм Рихард|Richard Dedekind]]
|ref=Dedekind
|часть=Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler
|страницы=103–148
|заглавие=Gesammelte Werke
|том=2
|год=1897}}
* {{статья
|ref=Kahn
|автор=Jeff Kahn
|doi=10.1090/S0002-9939-01-06058-0
|mr=1862115
|выпуск=2
|издание=Proceedings of the American Mathematical Society
|страницы=371–378
|заглавие=Entropy, independent sets and antichains: a new approach to Dedekind's problem
|том=130
|год=2002}}
* {{статья
|ref=Kisielewicz
|автор=Andrzej Kisielewicz
|doi=10.1515/crll.1988.386.139
|mr=936995
|издание=Journal für die Reine und Angewandte Mathematik
|страницы=139–144
|заглавие=A solution of Dedekind's problem on the number of isotone Boolean functions
|том=386
|год=1988
}}
* {{статья
|автор=Kleitman D., Markowsky G.
|ref=Kleitman, Markowsky
|mr=0382107
|издание=Transactions of the American Mathematical Society
|страницы=373–390
|заглавие=On Dedekind's problem: the number of isotone Boolean functions. II
|том=213
|год=1975|doi=10.2307/1998052}}.
* {{статья
|автор=Коршунов А. Д. 
|ref=Коршунов
|mr=0640855
|издание=Проблемы кибернетики
|страницы=5–108
|заглавие=О числе монотонных булевых функций
|том=38
|год=1981
}}
* {{статья
|ref=Ward
|автор=Morgan Ward
|издание=Bulletin of the American Mathematical Society
|страницы=423
|заглавие=Note on the order of free distributive lattices
|том=52
|doi=10.1090/S0002-9904-1946-08568-7
|год=1946}}
* {{статья
|ref=Wiedemann
|автор=Doug Wiedemann
|doi=10.1007/BF00385808
|mr=1129608
|выпуск=1
|издание={{iw|Order (журнал)|Order||Order (journal)}}
|страницы=5–6
|заглавие=A computation of the eighth Dedekind number
|том=8
|год=1991}}.
* {{статья
|ref=Yamamoto
|автор=Koichi Yamamoto
|mr=0070608
|выпуск=1
|издание=Science Reports of the Kanazawa University
|страницы=5–6
|заглавие=Note on the order of free distributive lattices
|том=2
|год=1953}}
* {{книга
|ref=Zaguia
|автор=Nejib Zaguia
|часть=Isotone maps: enumeration and structure
|ответственный=Sauer N. W., Woodrow R. E., Sands B.
|mr=1261220
|страницы=421–430
|издательство=Kluwer Academic Publishers
|заглавие=Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991)
|год=1993}}

{{Классы натуральных чисел }}

[[Категория:Целочисленные последовательности]]
[[Категория:Перечислительная комбинаторика]]
[[Категория:Математическая логика]]
[[Категория:Теория решёток]]
[[Категория:Семейства множеств]]