Теорема Биркгофа о представлении

Теоре́ма Би́ркгофа о представле́нии — общая теорема о представлении произвольной дистрибутивной решётки набором множеств, образующих кольцо, впервые опубликованная американским математиком Гарретом Биркгофом в 1933 году^[1].

Записывается в двух формах разной степени детализации (с упоминанием кольца и без)^{[1][2][3][4][5]} и, кроме того, сопровождается:

• следствием (представлением в решётке натуральных чисел, упорядоченных по делимости)^[6][7];
• более сильным частным случаем (для конечных дистрибутивных решёток)^[2];
• более слабым обобщением (для произвольных решёток)^[3][8].

Аналог теоремы Стоуна для булевых алгебр^[2].

Теорема Биркгофа о представлении произвольной дистрибутивной решётки впервые опубликована в 1933 году под названием «теорема 25.2» в статье «О сочетании подалгебр» в британском журнале «Труды Кембриджского философского общества» Издательства Кембриджского университета американским математиком Гарреттом Биркгофом, в честь которого и названа^[1][9].

При первоначальном доказательстве этой теоремы Биркгоф использовал конструкцию, историческое исследование которой проведено американским математиком, учеником Гарретта Биркгофа, Маршаллом Стоуном, а первый пример применения этой конструкции, вероятно, был у польско-американского математика и логика Альфреда Тарского^[1][10][11].

Наиболее общая формулировка теоремы, без деталей изоморфизма, следующая^[2][3][4][5].

Теорема Биркгофа о представлении. Произвольная дистрибутивная решётка вкладывается в решётку множества всех подмножеств подходящего множества^[2][3], то есть изоморфна решётке некоторых подмножеств соответствующего множества^[4][5].

Первоначальная формулировка этой теоремы Биркгофа, использующая понятие кольца множеств, следующая^[1].

Теорема Биркгофа о представлении. Произвольная дистрибутивная решётка изоморфна кольцу множеств^[1].

Теорема имеет следующее практическое применение: дистрибутивные решётки можно визуализировать диаграммами Эйлера — Венна, при этом элементы решёток соотносят с подмножествам соответствующего множества, а решёточные операции — с теоретико-множественными^[2][6].

Также из теоремы Биркгофа о представлении вытекает следующий факт^[6].

Следствие теоремы Биркгофа о представлении. Произвольная конечная дистрибутивная решётка вкладывается в решётку натуральных чисел, которая упорядочена делимостью^[6][7].

В 1966 году итальянский математик Фридрих Бартолоцци предложил следующий индуктивный алгоритм представления конечной дистрибутивной решётки натуральными числами^[13][7]:

• наименьшему элементу ${\displaystyle 0}$ данной конечной дистрибутивной решётки приписывается натуральное число 1, а атомам решётки ${\displaystyle p_{1},\,p_{1},\,\dots ,\,p_{n}}$ — первые ${\displaystyle n}$ простых чисел;
• предположим, что натуральные числа приписаны всем элементам высоты ${\displaystyle h}$. Если некоторый элемент ${\displaystyle a}$ высоты ${\displaystyle h+1}$ покрывает несколько элементов меньшей высоты, то тогда ему приписывается наименьшее общее кратное всех чисел, приписанных покрываемым элементам;
• если же этот элемент ${\displaystyle a}$ покрывает ровно один элемент, которому приписано число ${\displaystyle k}$, то тогда ему приписывается число ${\displaystyle kp}$, где ${\displaystyle p}$ — наименьшее из неиспользованных простых чисел.

Теорема Биркгофа о представлении может быть усилена в случае конечных дистрибутивных решёток^[2].

Один из примеров дистрибутивной решётки — решётка ${\displaystyle J(A)}$ всех идеалов частично упорядоченного множества ${\displaystyle A}$. При этом бинарные операции ${\displaystyle +}$ и ${\displaystyle \cdot }$ на этих идеалах — это соответственно их теоретико-множественные объединение и пересечение как подмножеств ${\displaystyle A}$. Поскольку объединение и пересечение идеалов — идеал, а объединения и пересечения множеств дистрибутивно, то ${\displaystyle J(A)}$ есть дистрибутивная решётка. Обратное утверждение тоже истинно, если дистрибутивная решётка конечна. Это обратное утверждение называется «фундаментальной теоремой для конечных дистрибутивных решёток (ФТКДР)»^[14][15].

Теорема (ФТКДР, Биркгоф). Произвольная конечная дистрибутивная решётка изоморфна решётке всех идеалов некоторого частично упорядоченного множества^[14].

Для комбинаторных целей удобно даже определить конечную дистрибутивную решётку ${\displaystyle L}$ как любое частично упорядоченное множество вида ${\displaystyle J(A)}$, где произвольное частично упорядоченное множество ${\displaystyle A}$ конечно^[14].

Для доказательства ФТКДР для произвольной конечной дистрибутивной решётки ${\displaystyle L}$ конструируют кандидата ${\displaystyle A}$, а потом доказывают изоморфность ${\displaystyle L}$ и ${\displaystyle J(A)}$^[14].

Неразложимый в объединение элемент ${\displaystyle x}$ решётки ${\displaystyle L}$ — ненулевой элемент ${\displaystyle x\in L}$, для которого неверно, что ${\displaystyle x=y+z}$, где ${\displaystyle y<x}$ и ${\displaystyle z<x}$, то есть из ${\displaystyle x=y+z}$ вытекает либо ${\displaystyle x=y}$, либо ${\displaystyle x=z}$. По определению, нулевой элемент решётки ${\displaystyle 0}$ не считается неразложимым в объединение^[14][16].

Двойственным способом определяется неразложимый в пересечение элемент^[14].

Уточним формулировку ФТКДР^[15].

Теорема (ФТКДР, Биркгоф). Произвольная конечная дистрибутивная решётка изоморфна решётке всех идеалов частично упорядоченного множества её неразложимых элементов^[15].

Лемма. Множество ${\displaystyle \operatorname {Irr} J(A)}$ всех неразложимых элементов из решётки ${\displaystyle J(A)}$, которое есть (индуцированное) частично упорядоченное подмножество множества ${\displaystyle J(A)}$, изоморфно ${\displaystyle A}$. Поэтому ${\displaystyle J(A)}$ изоморфно ${\displaystyle J(B)}$ тогда и только тогда, когда ${\displaystyle A}$ изоморфно ${\displaystyle B}$^[2][14].

Теорема о представлении решёток обобщает теорему Биркгофа, представляет собой её ослабленный вариант и верна для произвольных решёток, а не только для дистрибутивных^[2][3].

Теорема о представлении решёток. Произвольная решётка вкладывается в упорядоченное включением множество всех подмножеств с сохранением всех своих точных нижних граней^[8][18].

А именно, любая решётка ${\displaystyle \langle A,\,\leqslant \rangle }$ вкладывается в множество всех подмножеств ${\displaystyle P(A)}$ отображением ${\displaystyle \varphi \colon A\to P(A)}$, которое каждому элементу ${\displaystyle x\in A}$ ставит в соответствие главный идеал ${\displaystyle J(x)\in P(A)}$^[18][19].

1. ↑ ^{1 2 3 4 5 6 7} Биркгоф Г. Теория структур, 1952, Глава IX. Дистрибутивные структуры. § 5. Общая теорема о предсталении, с. 200.
2. ↑ ^{1 2 3 4 5 6 7 8 9 10} Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры, 2013, 4.4. Дистрибутивные решётки, с. 155.
3. ↑ ^{1 2 3 4 5} Салий В. Н. Решетки с единственными дополнениями, 1984, Глава первая. § 4, Дистрибутивные решетки. 7, с. 34.
4. ↑ ^{1 2 3} Скорняков Л. А. Дистрибутивная решётка, 1979, стб. 230.
5. ↑ ^{1 2 3 4} Скорняков Л. А. Элементы теории структур, 1970, § 7. Дистрибутивные структуры, с. 127.
6. ↑ ^{1 2 3 4} Салий В. Н. Решетки с единственными дополнениями, 1984, Глава первая. § 4. Дистрибутивные решетки. 7, с. 35.
7. ↑ ^{1 2 3 4} Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры, 2013, 4.4. Дистрибутивные решётки, с. 158.
8. ↑ ^{1 2 3} Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры, 2013, 4.2. Решёточные гомоморфизмы, идеалы и фильтры, с. 141.
9. ↑ Garrett Birkhoff. On the combination of subalgebras, 1933, p. 458—459.
10. ↑ Stone M. H. The representation of boolean algebras, 1938, p. 812.
11. ↑ Tarski A. Une contribution à la théorie de la mesure, 1930.
12. ↑ Салий В. Н. Решетки с единственными дополнениями, 1984, Глава первая. § 4. Дистрибутивные решетки. 7, с. 34—35.
13. ↑ ^{1 2} Салий В. Н. Решетки с единственными дополнениями, 1984, Глава первая. § 4. Дистрибутивные решетки. 7, с. 36.
14. ↑ ^{1 2 3 4 5 6 7 8} Стенли Р. Перечислительная комбинаторика, 1990, 3.4. Дистрибутивные решетки, с. 161.
15. ↑ ^{1 2 3 4} Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры, 2013, 4.4. Дистрибутивные решётки, с. 156.
16. ↑ Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры, 2013, 4.4. Дистрибутивные решётки, с. 150.
17. ↑ Стенли Р. Перечислительная комбинаторика, 1990, 3.4. Дистрибутивные решетки, с. 162.
18. ↑ ^{1 2 3} Салий В. Н. Решетки с единственными дополнениями, 1984, Глава первая. § 2. Решётки. 9, с. 27.
19. ↑ Гретцер Г. Общая теория решёток, 1982, Глава II. Дистрибутивные решетки. § 1. Теоремы характеризации и теоремы представления, с. 90.

• Биркгоф Г. Теория структур = Garrett Birkhoff, Lattice theory. Revised Edition (1948) (рус.) / Пер. с англ. М. И. Граева. — М.: «Издательство иностранной литературы», 1952. — 407 с.: ил.
• Гретцер Г.. Общая теория решёток = George Grätzer. General Lattice Theory (1978) (рус.) / Пер. с англ. А. Д. Больбота, В. А. Горбунова и В. И. Туманова под ред. Д. М. Смирнова. — М.: «Мир», 1982. — 452 с.: ил. — 6000 экз.
• Гуров С. И. Булевы алгебры, упорядоченные множества, решётки: определения, свойства, примеры (рус.). — 2-е изд. — М.: URSS : Книжный дом «Либроком», 2013. — 221 с., ил. — (Основы защиты информации. Секретно для пользы = Secreto ad utilitatem). — ISBN 978-5-397-03899-7.
• Салий В. Н. Решетки с единственными дополнениями (рус.). — М.: «Наука», 1984. — 128 с., ил. — 4400 экз.
• Скорняков Л. А. Дистрибутивная решётка // Математическая энциклопедия : [в 5 т.] / Гл. ред. И. М. Виноградов. — М.: Советская энциклопедия, 1979. — Т. 2: Д — Коо. — Стб. 230. — 1104 стб. : ил. — 148 800 экз.
• Скорняков Л. А. Элементы теории структур (рус.). — М.: «Наука», 1970. — 148,[1] с., ил. — 12 000 экз.
• Стенли Р. Перечислительная комбинаторика = Richard P. Stanley. Enumerarive combinatorics. Volume I (рус.) / Пер. с англ. А. И. Барвинка, А. А. Лодкина под ред. А. М. Вершика. — М.: «Мир», 1990. — 440 с., ил. — 5500 экз. — ISBN 5-03-001348-2.
• Garrett Birkhoff. On the combination of subalgebras (англ.) // Proceedings of the Cambridge Philosophical Society : журнал. — Cambridge: Cambridge University Press for the Cambridge Philosophical Society, 1933. — 30 October (vol. 29, iss. 4). — P. 441—464. — ISSN 0305-0041. — doi:10.1017/S0305004100011464.
• Stone M. H. The representation of boolean algebras (англ.) // Bulletin of the American Mathematical Society : журнал. — New York City: American Mathematical Society, 1938. — Vol. 44. — P. 807—816. — ISSN 0273-0979. — doi:10.1090/S0002-9904-1938-06871-1.
• Tarski A. Une contribution à la théorie de la mesure (фр.) // Fundamenta Mathematicae : журнал. — Warszawa: Polska Akademia Nauk, 1930. — Vol. 15. — P. 42—50. — ISSN 0016-2736. — doi:10.4064/fm-15-1-42-50.