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

Речь идет о теории решеток . Другие результаты с похожими названиями см. в теореме Биркгофа (значения) .

В математике дистрибутивных теорема Биркгофа о представлении решеток утверждает, что элементы любой конечной дистрибутивной решетки могут быть представлены как конечные множества таким образом, что операции решетки соответствуют объединениям и пересечениям множеств. Здесь решетка представляет собой абстрактную структуру с двумя бинарными операциями : операциями «встреча» и «объединение», которые должны подчиняться определенным аксиомам; она дистрибутивна, если эти две операции подчиняются распределительному закону . Операции объединения и пересечения в семействе множеств, замкнутом относительно этих операций, автоматически образуют дистрибутивную решетку, и теорема о представлении Биркгофа утверждает, что каждая конечная дистрибутивная решетка может быть сформирована таким образом. Оно названо в честь Гаррета Биркгоффа , опубликовавшего его доказательство в 1937 году.

Теорему можно интерпретировать как обеспечивающую взаимно однозначное соответствие между дистрибутивными решетками и частичными порядками , между квазиординальными пространствами знаний и предпорядками или между конечными топологическими пространствами и предпорядками.

Название «теорема о представлении Биркгофа» также применялось к двум другим результатам Биркгофа, одному из них 1935 года о представлении булевых алгебр как семейств множеств, замкнутых относительно объединения, пересечения и дополнения (так называемые поля множеств , тесно связанные с кольца множеств, используемые Биркгофом для представления дистрибутивных решеток), и теорема Биркгофа HSP, представляющая алгебры как произведения неприводимых алгебр. Теорему Биркгофа о представлении также называют фундаментальной теоремой для конечных дистрибутивных решеток .

Предыстория и примеры

Многие решетки могут быть определены таким образом, что элементы решетки представлены множествами, операция соединения решетки представлена ​​объединением множеств, а операция встречи решетки представлена ​​пересечением множеств. Например, этим свойством обладает булева решетка, определенная из семейства всех подмножеств конечного множества. В более общем смысле любое конечное топологическое пространство имеет решетку множеств в качестве семейства открытых множеств. Поскольку объединения и пересечения множеств подчиняются дистрибутивному закону , любая решетка, определенная таким образом, является дистрибутивной решеткой. Теорема Биркгофа утверждает, что на самом деле все конечные дистрибутивные решетки могут быть получены таким образом, а более поздние обобщения теоремы Биркгофа утверждают то же самое для бесконечных дистрибутивных решеток.

Дистрибутивная решетка делителей числа 120 и ее представление в виде наборов степеней простых чисел.

Рассмотрим делители некоторого составного числа, например (на рисунке) 120, частично упорядоченные по делимости. Любые два делителя 120, например 12 и 20, имеют уникальный наибольший общий делитель 12 ∧ 20 = 4, наибольшее число, которое делит их оба, и уникальное наименьшее общее кратное 12 ∨ 20 = 60; оба этих числа также являются делителями 120. Эти две операции ∨ и ∧ удовлетворяют дистрибутивному закону в любой из двух эквивалентных форм: ( x ∧ y ) ∨ z = ( x ∨ z ) ∧ ( y ∨ z ) и ( x ∨ y ) ∧ z знак равно ( Икс ∧ z ) ∨ ( y ∧ z ), для всех x , y и z . Следовательно, дивизоры образуют конечную дистрибутивную решетку .

Каждому делителю можно сопоставить набор степеней простых чисел , которые его делят: так, 12 соответствует набору {2,3,4}, а 20 — набору {2,4,5}. Тогда 12 ∧ 20 = 4 соответствует множеству {2,3,4} ∩ {2,4,5} = {2,4}, а 12 ∨ 20 = 60 соответствует множеству {2,3,4 } ∪ {2,4,5} = {2,3,4,5}, поэтому операции соединения и соединения решетки соответствуют объединению и пересечению множеств.

Степени простых чисел 2, 3, 4, 5 и 8, выступающие в качестве элементов в этих наборах, сами могут быть частично упорядочены по делимости; в этом меньшем частичном порядке 2 ≤ 4 ≤ 8, и между другими парами нет отношений порядка. 16 наборов, связанных с делителями 120, представляют собой нижние множества этого меньшего частичного порядка, подмножества элементов, такие, что если x ≤ y и y принадлежит подмножеству, то x также должен принадлежать этому подмножеству. Из любого нижнего набора L вычислив наименьшее общее кратное простых степеней в L. можно восстановить соответствующий делитель , Таким образом, частичный порядок пяти простых степеней 2, 3, 4, 5 и 8 несет достаточно информации, чтобы восстановить всю исходную 16-элементную решетку делимости.

Теорема Биркгофа утверждает, что эта связь между операциями ∧ и ∨ решетки делителей и операциями ∩ и ∪ связанных с ними наборов простых степеней не является случайной и не зависит от конкретных свойств простых чисел и делимости: элементы таким же образом любая конечная дистрибутивная решетка может быть связана с нижними множествами частичного порядка.

В качестве другого примера рассмотрим решетку подмножеств -элементного множества n , частично упорядоченного по включению. Теорема Биркгофа показывает, что эта решетка образуется нижними множествами свободной дистрибутивной решетки с n образующими, число элементов которых задается числами Дедекинда .

Частичный порядок объединения-неприводимых

В решетке элемент x является несводимым к соединению, если x не является объединением конечного набора других элементов. Эквивалентно, x является несводимым к соединению, если он не является ни нижним элементом решетки (соединение нулевых элементов), ни соединением каких-либо двух меньших элементов. Например, в решетке делителей числа 120 нет пары элементов, соединение которых равно 4, поэтому 4 является несводимым по объединению. Элемент x является простым по соединению, если он отличается от нижнего элемента, и всякий раз, когда x ≤ y ∨ z , либо x ≤ y, либо x ≤ z . В той же решетке 4 является простым в соединении: всякий раз, когда lcm( y , z ) делится на 4, хотя бы один из y и z сам должен делиться на 4.

В любой решетке простой по соединению элемент должен быть неприводимым по объединению. Эквивалентно, элемент, который не является несводимым по соединению, не является простым по соединению. Ибо, если элемент x не является неприводимым в объединение, существуют меньшие y и z такие, что x = y ∨ z . Но тогда x ≤ y ∨ z , и x не меньше или равен ни y, ни z , что показывает, что он не является простым по соединению.

Существуют решетки, в которых простые по объединению элементы образуют собственное подмножество неприводимых по объединению элементов, но в дистрибутивной решетке эти два типа элементов совпадают. Предположим, что x неприводим к объединению и что x ⩽ y ∨ z . Это неравенство эквивалентно утверждению, что x = x ∧ ( y ∨ z ), а по дистрибутивному закону x = ( x ∧ y ) ∨ ( x ∧ z ). Но поскольку x неприводим к соединению, по крайней мере один из двух терминов в этом объединении должен быть самим x , показывая, что либо x = x ∧ y (эквивалентно x ≤ y ), либо x = x ∧ z (эквивалентно x ≤ z ).

Решетчатый порядок на подмножестве элементов, не приводимых в объединение, образует частичный порядок ; Теорема Биркгофа утверждает, что сама решетка может быть восстановлена ​​по нижним множествам этого частичного порядка.

Теорема Биркгофа

Решетка примера дистрибутива с неприводимыми в объединение элементами a,...,g (затененные узлы). Нижний набор, которому узел соответствует изоморфизму Биркгофа, показан синим цветом.

В любом частичном порядке нижние множества образуют решетку, в которой частичный порядок решетки задается включением множеств, операция соединения соответствует объединению множеств, а операция встречи соответствует пересечению множеств, поскольку объединения и пересечения сохраняют свойство быть нижний комплект. Поскольку объединения и пересечения множеств подчиняются дистрибутивному закону, это распределительная решетка. Теорема Биркгофа утверждает, что таким способом можно построить любую конечную дистрибутивную решетку.

Теорема . Любая конечная дистрибутивная решетка L изоморфна решетке нижних множеств частичного порядка неприводимых в объединение элементов L .

То есть существует взаимно однозначное соответствие между элементами L и нижними множествами частичного порядка. Нижний набор, соответствующий элементу x из L, представляет собой просто набор несократимых по соединению элементов L , которые меньше или равны x , а элемент L, соответствующий нижнему набору S несократимых по объединению элементов, представляет собой объединение С. ​

Для любого нижнего набора S неприводимых в объединение элементов пусть x будет объединением S и пусть T будет нижним набором неприводимых в объединение элементов, меньших или равных x . Тогда S = Т. ​Ибо каждый элемент S явно принадлежит T , и любой несводимый к соединению элемент, меньший или равный x , должен (по простоте соединения) быть меньше или равен одному из членов S и, следовательно, должен (по предположению что S — нижнее множество) принадлежат S. самому И наоборот, для любого элемента x из L пусть S меньшими или равными x , и пусть y будет объединением S. будет неприводимыми к соединению элементами , Тогда х = у . Ибо, как объединение элементов, меньших или равных x , y не может быть больше, чем x сам , но если x является несводимым к объединению, то x принадлежит S , а если x является объединением двух или более несводимых к соединению элементов, тогда они снова должны принадлежать S , поэтому y ≥ x . Следовательно, соответствие взаимно однозначно и теорема доказана.

Кольца наборов и предзаказов

Биркгоф (1937) определил кольцо множеств как семейство множеств , замкнутое относительно операций объединения и пересечения множеств; позже, движимые приложениями в математической психологии , Дуаньон и Фалмань (1999) назвали ту же структуру квазиординальным пространством знаний . Если множества в кольце множеств упорядочены по включению, они образуют дистрибутивную решетку. Элементам наборов может быть задан предварительный порядок , в котором x ≤ y , если какой-либо набор в кольце содержит x , но не y . Кольцо множеств само по себе тогда является семейством нижних множеств этого предпорядка, и любой предпорядок таким образом порождает кольцо множеств.

Функциональность

Теорема Биркгофа, как указано выше, представляет собой соответствие между отдельными частичными порядками и дистрибутивными решетками. Однако его можно распространить и на соответствие между сохраняющими порядок функциями частичных порядков и ограниченными гомоморфизмами соответствующих дистрибутивных решеток. В этой переписке направление этих карт изменено на противоположное.

Пусть 2 обозначает частичный порядок на двухэлементном множестве {0, 1} с отношением порядка 0 < 1 и (следуя Стэнли) пусть J(P) обозначает дистрибутивную решетку нижних множеств конечного частичного порядка P . Тогда элементы J(P) взаимно однозначно соответствуют функциям, сохраняющим порядок, от P до 2 . Ибо, если ƒ является такой функцией, ƒ ⁻¹ (0) образует нижний набор, и наоборот, если L — нижний набор, можно определить функцию, сохраняющую порядок, ƒ _L , которая отображает L в 0 и отображает оставшиеся элементы P в 1. Если g — любая функция, сохраняющая порядок из Q в P можно определить функцию g * из J(P) в J(Q) , которая использует композицию функций для отображения любого элемента L из J(P) в ƒ _L ∘ g . Эта составная функция отображает Q в 2 и, следовательно, соответствует элементу g *( L ) = (ƒ _L ∘ g ) ⁻¹ (0) из J(Q) . Далее, для любых x и y в J(P) g * ( x ∧ y ) = g *( x ) ∧ g *( y ) (элемент Q отображается с помощью g в нижнее множество x ∩ y , если и только если принадлежит как множеству элементов, отображенных в x , так и множеству элементов, отображенных в y ) и симметрично g *( x ∨ y ) = g *( x ) ∨ g *( y ). Кроме того, нижний элемент J(P) (функция, которая отображает все элементы P в 0) отображается g * в нижний элемент J(Q) , а верхний элемент J(P) отображается g * к верхнему элементу J(Q) . Т. е. g * — гомоморфизм ограниченных решеток.

Однако сами элементы P взаимно однозначно соответствуют ограниченным решеточным гомоморфизмам из J(P) в 2 . Ибо, если x является любым элементом P , можно определить ограниченный решеточный гомоморфизм j _x , который отображает все нижние множества, содержащие x, в 1, а все остальные нижние множества в 0. И для любого решеточного гомоморфизма из J(P) в 2 , элементы J(P), отображаемые в 1, должны иметь уникальный минимальный элемент x (объединение всех элементов, отображаемых в 1), который должен быть несводимым к объединению (он не может быть объединением любого набора элементов, отображенных в 0). ), поэтому каждый решеточный гомоморфизм имеет вид j _x для некоторого x . Опять же, из любого ограниченного решеточного гомоморфизма h из J(P) в J(Q) можно использовать композицию функций, чтобы определить сохраняющее порядок отображение h * из Q в P . Можно проверить, что g ** = g для любого сохраняющего порядок отображения g из Q в P и что h ** = h для любого ограниченного решеточного гомоморфизма h из J(P) в J(Q) .

В теории категорий терминологии J — контравариантный hom-функтор J = Hom(—, 2 ), определяющий двойственность категорий между, с одной стороны, категорией конечных частичных порядков и сохраняющими порядок отображениями, а с другой стороны категория конечных дистрибутивных решеток и ограниченных решеточных гомоморфизмов.

Обобщения

Бесконечные распределительные решетки

В бесконечной дистрибутивной решетке может не быть так, чтобы нижние множества неприводимых в объединение элементов находились во взаимно однозначном соответствии с элементами решетки. Действительно, неприводимых соединений может вообще не быть. Это происходит, например, в решетке всех натуральных чисел, упорядоченных в порядке, обратном обычному порядку делимости (то есть x ≤ y , когда y делит x ): любое число x может быть выражено как объединение чисел xp и xq , где p и q — различные простые числа . Однако элементы в бесконечных дистрибутивных решетках по-прежнему могут быть представлены как множества с помощью теоремы Стоуна о представлении дистрибутивных решеток, формы двойственности Стоуна , в которой каждый элемент решетки соответствует компактному открытому множеству в определенном топологическом пространстве . Эту теорему об обобщенном представлении можно выразить как теоретико-категорную двойственность между дистрибутивными решетками и спектральными пространствами (иногда называемыми когерентными пространствами, но не тем же, что когерентные пространства в линейной логике ), топологическими пространствами, в которых компактные открытые множества замкнуты при пересечении. и сформировать основа топологии. Хилари Пристли показала, что теорему о представлении Стоуна можно интерпретировать как расширение идеи представления элементов решетки нижними множествами частичного порядка, используя идею Нахбина об упорядоченных топологических пространствах. Пространства Стоуна с дополнительным частичным порядком, связанным с топологией аксиомой разделения Пристли, также могут использоваться для представления ограниченных дистрибутивных решеток. Такие пространства известны как пространства Пристли . Кроме того, некоторые битопологические пространства , а именно попарные пространства Стоуна , обобщают оригинальный подход Стоуна, используя две топологии на множестве для представления абстрактной дистрибутивной решетки. Таким образом, теорема о представлении Биркгофа распространяется на случай бесконечных (ограниченных) дистрибутивных решеток по крайней мере тремя различными способами, суммированными в теории двойственности для дистрибутивных решеток .

Медианные алгебры и связанные с ними графы

Теорема Биркгофа о представлении также может быть обобщена на конечные структуры, отличные от дистрибутивных решеток. В дистрибутивной решетке самодвойственная медианная операция

$m(x,y,z)=(x\vee y)\wedge (x\vee z)\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)$

порождает медианную алгебру , а отношение накрытия решетки образует медианный граф . Конечные медианные алгебры и медианные графы имеют двойственную структуру.как множество решений случая 2-выполнимости ; Бартелеми и Константин (1993) формулируют эту структуру эквивалентно как семейство начальных стабильных множеств в смешанном графе . Для дистрибутивной решетки соответствующий смешанный граф не имеет неориентированных ребер, а исходные устойчивые множества представляют собой не что иное, как нижние множества транзитивного замыкания графа. Эквивалентно, для дистрибутивной решетки граф импликации экземпляра 2-выполнимости может быть разделен на два компонента связности : один для положительных переменных экземпляра, а другой для отрицательных переменных; транзитивное замыкание положительного компонента является основным частичным порядком дистрибутивной решетки.

Конечные присоединительно-распределительные решетки и матроиды

Другим результатом, аналогичным теореме о представлении Биркгофа, но применимым к более широкому классу решеток, является теорема Эдельмана (1980) о том, что любая конечная объединенно-дистрибутивная решетка может быть представлена ​​как антиматроид , семейство множеств, замкнутых относительно объединений, но в которых замыкание под пересечениями было заменено свойством, согласно которому каждое непустое множество имеет съемный элемент.

См. также

• Решетка устойчивых паросочетаний , также представляющая каждую конечную дистрибутивную решетку.

Ссылки

• Бартелеми, Ж.-П.; Константин, Дж. (1993), «Медианные графы, параллелизм и частично упорядоченные множества», Discrete Mathematics , 111 (1–3): 49–63, doi : 10.1016/0012-365X(93)90140-O .
• Биркгоф, Гарретт (1937), «Кольца множеств», Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215/S0012-7094-37-00334-X .
• Биркгоф, Гарретт ; Кисс, С.А. (1947), «Трнарная операция в распределительных решетках» , Бюллетень Американского математического общества , 53 (1): 749–752, doi : 10.1090/S0002-9904-1947-08864-9 , MR   0021540 .
• Дуаньон, Ж.-П.; Фальмань, Ж.-Кл. (1999), Пространства знаний , Springer-Verlag, ISBN  3-540-64501-2 .
• Эдельман, Пол Х. (1980), «Встреча-распределительные решетки и антиобменное замыкание», Algebra Universalis , 10 (1): 290–299, doi : 10.1007/BF02482912 .
• Джонстон, Питер (1982), «II.3 Согласованные места», Stone Spaces , Cambridge University Press, стр. 62–69, ISBN  978-0-521-33779-3 .
• Пристли, Х.А. (1970), «Представление дистрибутивных решеток с помощью упорядоченных пространств Стоуна», Бюллетень Лондонского математического общества , 2 (2): 186–190, doi : 10.1112/blms/2.2.186 .
• Пристли, Х.А. (1972), «Упорядоченные топологические пространства и представление дистрибутивных решеток», Труды Лондонского математического общества , 24 (3): 507–530, doi : 10.1112/plms/s3-24.3.507 , hdl : 10338 .dmlcz/134149 .
• Стэнли, Р.П. (1997), Перечислительная комбинаторика, Том I , Кембриджские исследования по высшей математике 49, Cambridge University Press, стр. 104–112 .