Компактный элемент

В математической области теории порядка компактные элементы или конечные элементы частично упорядоченного множества — это те элементы, которые не могут быть включены в супремум любого непустого направленного множества , которое уже не содержит членов выше компактного элемента. Это понятие компактности одновременно обобщает понятия конечных множеств в теории множеств , компактных множеств в топологии и конечно порожденных модулей в алгебре . (В математике существуют и другие понятия компактности .)

Формальное определение

В частично упорядоченном множестве ( P ,≤) элемент c называется компактным (или конечным ), если он удовлетворяет одному из следующих эквивалентных условий:

Для каждого направленного подмножества D из P , если D имеет супремум sup D и c ≤ sup D, то c ≤ d для некоторого элемента d из D.
Для каждого идеала I из P , если I имеет супремум sup I и c ≤ sup I, то c является элементом I.

Если частично упорядоченное множество P дополнительно является полурешеткой соединений (т.е. имеет бинарные супремумы), то эти условия эквивалентны следующему утверждению:

Для каждого подмножества S из P , если S имеет супремум sup S и c ≤ sup S , то c ≤ sup T для некоторого конечного подмножества T из S.

В частности, если c = sup S , то c является супремумом конечного подмножества S.

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

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

Примеры

Самый простой пример получается при рассмотрении множества мощности некоторого множества A , упорядоченного по включению подмножеств . В этой полной решетке компактные элементы — это в точности конечные подмножества A. Это оправдывает название «конечный элемент».
Термин «компактный» вдохновлен определением (топологически) компактных подмножеств топологического пространства T. Множество Y является компактным, если для любого набора открытых множеств S , если объединение по S включает Y как подмножество, то Y включается как подмножество объединения конечного поднабора S. Рассматривая множество мощности T как полную решетку с порядком включения подмножеств, где супремум набора множеств задается их объединением, топологическое условие компактности имитирует условие компактности в join-полурешетках, но с дополнительным требованием открытости.
Если он существует, то наименьший элемент частично упорядоченного множества всегда компактен. Может быть, это единственный компактный элемент, как показывает пример действительного единичного интервала [0,1] (со стандартным порядком, унаследованным от действительных чисел).
Каждый полностью простой элемент решетки компактен.

Алгебраические частично упорядоченные множества

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

Важный частный случай — алгебраическая решетка , представляющая собой полную решетку L , в которой каждый элемент x из L является супремумом компактных элементов, лежащих ниже x .

Типичный пример (послуживший мотивацией для названия «алгебраический») следующий:

Для любой алгебры A (например, группы, кольца, поля, решетки и т. д.; или даже просто множества без каких-либо операций) пусть Sub( A ) будет множеством всех подструктур A , т. е. всех подмножеств A , которые замкнуты относительно всех операций A (группового сложения, кольцевого сложения и умножения и т. д.). Здесь понятие подструктуры включает пустую подструктуру в случае, если алгебра A не имеет нуль-арных операций.

Затем:

Множество Sub( A ), упорядоченное по включению множеств, представляет собой решетку.
Наибольшим элементом Sub( A ) является само множество A.
Для любых S , T в Sub( A ) точная нижняя граница S и T является теоретико-множественным пересечением S и T ; наименьшая верхняя граница является подалгеброй, порожденной объединением S и T .
Множество Sub( A ) является даже полной решеткой. Наилучшей нижней границей любого семейства подструктур является их пересечение (или A , если семейство пусто).
Компактные элементы Sub( A ) — это в точности конечно порожденные подструктуры A .
Каждая подструктура является объединением своих конечно порожденных подструктур; следовательно, Sub( A ) является алгебраической решеткой.

Также справедливо своего рода обратное утверждение: каждая алгебраическая решетка изоморфна Sub ( A ) для некоторой алгебры A .

Есть еще одна алгебраическая решетка, которая играет важную роль в универсальной алгебре : для каждой алгебры A мы положим Con( A ) множество всех отношений конгруэнтности на A . Каждая конгруэнтность на A является подалгеброй алгебры произведения A x A , поэтому Con( A ) ⊆ Sub( A x A ). Снова имеем

Con( A ), упорядоченный по включению множеств, представляет собой решетку.
Наибольшим элементом Con( A ) является множество A x A , которое является конгруэнцией, соответствующей постоянному гомоморфизму. Наименьшая конгруэнция — диагональ A x A , соответствующая изоморфизмам.
Con( A ) — полная решетка.
Компактные элементы Con( A ) — это в точности конечно порожденные конгруэнции.
Con( A ) — алгебраическая решетка.

Опять же, есть и обратное: по теореме Георга Гретцера и Э. Т. Шмидта каждая алгебраическая решетка изоморфна Con( A ) для некоторой алгебры A .

Приложения

Компактные элементы важны в информатике в семантическом подходе, называемом теорией доменов , где они рассматриваются как своего рода примитивный элемент : информация, представленная компактными элементами, не может быть получена с помощью любого приближения, которое уже не содержит эти знания. Компактные элементы не могут быть аппроксимированы элементами, строго ниже их. С другой стороны, может случиться так, что все некомпактные элементы могут быть получены как направленные супремумы компактных элементов. Это желательная ситуация, поскольку множество компактных элементов часто меньше исходного частично упорядоченного множества — приведенные выше примеры иллюстрируют это.

Литература