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

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

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

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

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

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

• Для каждого подмножества S из P , если S имеет верхнюю грань sup S и c ⩽ sup S , то c ⩽ sup T для некоторого конечного подмножества T из S .

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

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

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

Примеры

• Самый простой пример получается при рассмотрении набора степеней некоторого множества A , упорядоченного по включению подмножества . Внутри этой полной решетки компактные элементы являются в точности подмножествами A . конечными Это оправдывает название «конечный элемент».
• Термин «компакт» вдохновлен определением (топологически) компактных подмножеств топологического пространства T . Множество Y компактно, если для каждой коллекции открытых множеств S объединение над S включает Y как подмножество, то Y включается как подмножество объединения конечного подмножества S . Рассматривая степенное множество T как полную решетку с порядком включения подмножества, где верхняя грань набора множеств задается их объединением, топологическое условие компактности имитирует условие компактности в соединении-полурешетках, но для дополнительного требования открытости.
• Если он существует, наименьший элемент ЧУМ всегда компактен. Возможно, это единственный компактный элемент, как показывает пример действительного единичного интервала [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 является подалгеброй произведения алгебры , AxA поэтому ( A ) ⊆ Sub( ) Con AxA . Опять у нас есть

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

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

Приложения

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

Литература

См. литературу по теории порядка и теории областей .