Теоре́ма Би́ркгофа о представле́нии — общая теорема о представлении произвольной дистрибутивной решётки набором множеств, образующих кольцо, впервые опубликованная американским математиком Гарретом Биркгофом в 1933 году.
Записывается в двух формах разной степени детализации (с упоминанием кольца и без) и, кроме того, сопровождается: следствием (представлением в решётке натуральных чисел, упорядоченных по делимости); более сильным частным случаем (для конечных дистрибутивных решёток); более слабым обобщением (для произвольных решёток).
Аналог теоремы Стоуна для булевых алгебр.
Исторические сведения Теорема Биркгофа о представлении произвольной дистрибутивной решётки впервые опубликована в 1933 году под названием «теорема 25.2» в статье «О сочетании подалгебр» в британском журнале «Труды Кембриджского философского общества» Издательства Кембриджского университета американским математиком Гарреттом Биркгофом, в честь которого и названа.
При первоначальном доказательстве этой теоремы Биркгоф использовал конструкцию, историческое исследование которой проведено американским математиком, учеником Гарретта Биркгофа, Маршаллом Стоуном, а первый пример применения этой конструкции, вероятно, был у польско-американского математика и логика Альфреда Тарского.
Формулировки теоремы Биркгофа Наиболее общая формулировка теоремы, без деталей изоморфизма, следующая.
Теорема Биркгофа о представлении. Произвольная дистрибутивная решётка вкладывается в решётку множества всех подмножеств подходящего множества, то есть изоморфна решётке некоторых подмножеств соответствующего множества.
Первоначальная формулировка этой теоремы Биркгофа, использующая понятие кольца множеств, следующая.
Теорема Биркгофа о представлении. Произвольная дистрибутивная решётка изоморфна кольцу множеств.
Теорема имеет следующее практическое применение: дистрибутивные решётки можно визуализировать диаграммами Эйлера — Венна, при этом элементы решёток соотносят с подмножествам соответствующего множества, а решёточные операции — с теоретико-множественными.
Следствие теоремы Биркгофа Также из теоремы Биркгофа о представлении вытекает следующий факт.
Следствие теоремы Биркгофа о представлении. Произвольная конечная дистрибутивная решётка вкладывается в решётку натуральных чисел, которая упорядочена делимостью.
В 1966 году итальянский математик Фридрих Бартолоцци предложил следующий индуктивный алгоритм представления конечной дистрибутивной решётки натуральными числами: наименьшему элементу данной конечной дистрибутивной решётки приписывается натуральное число 1, а атомам решётки — первые простых чисел; предположим, что натуральные числа приписаны всем элементам высоты . Если некоторый элемент высоты покрывает несколько элементов меньшей высоты, то тогда ему приписывается наименьшее общее кратное всех чисел, приписанных покрываемым элементам; если же этот элемент покрывает ровно один элемент, которому приписано число , то тогда ему приписывается число , где — наименьшее из неиспользованных простых чисел.
Фундаментальная теорема для конечных дистрибутивных решеток Теорема Биркгофа о представлении может быть усилена в случае конечных дистрибутивных решёток.
Один из примеров дистрибутивной решётки — решётка всех идеалов частично упорядоченного множества . При этом бинарные операции и на этих идеалах — это соответственно их теоретико-множественные объединение и пересечение как подмножеств . Поскольку объединение и пересечение идеалов — идеал, а объединения и пересечения множеств дистрибутивно, то есть дистрибутивная решётка. Обратное утверждение тоже истинно, если дистрибутивная решётка конечна. Это обратное утверждение называется «фундаментальной теоремой для конечных дистрибутивных решёток (ФТКДР)».
Теорема (ФТКДР, Биркгоф). Произвольная конечная дистрибутивная решётка изоморфна решётке всех идеалов некоторого частично упорядоченного множества.
Для комбинаторных целей удобно даже определить конечную дистрибутивную решётку как любое частично упорядоченное множество вида , где произвольное частично упорядоченное множество конечно.
Для доказательства ФТКДР для произвольной конечной дистрибутивной решётки конструируют кандидата , а потом доказывают изоморфность и .
Неразложимый в объединение элемент решётки — ненулевой элемент , для которого неверно, что , где и , то есть из вытекает либо , либо . По определению, нулевой элемент решётки не считается неразложимым в объединение.
Двойственным способом определяется неразложимый в пересечение элемент.
Уточним формулировку ФТКДР.
Теорема (ФТКДР, Биркгоф). Произвольная конечная дистрибутивная решётка изоморфна решётке всех идеалов частично упорядоченного множества её неразложимых элементов.
Лемма. Множество всех неразложимых элементов из решётки , которое есть (индуцированное) частично упорядоченное подмножество множества , изоморфно . Поэтому изоморфно тогда и только тогда, когда изоморфно .
Теорема о представлении решёток Теорема о представлении решёток обобщает теорему Биркгофа, представляет собой её ослабленный вариант и верна для произвольных решёток, а не только для дистрибутивных.
Теорема о представлении решёток. Произвольная решётка вкладывается в упорядоченное включением множество всех подмножеств с сохранением всех своих точных нижних граней.
А именно, любая решётка вкладывается в множество всех подмножеств отображением , которое каждому элементу ставит в соответствие главный идеал .
Примечания
Литература
Категория:Теория решёток Категория:Теория множеств