 | В этой статье не процитировать какие - либо источники . ( декабрь 2008 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В математической области теории порядка , что компактные элементы или конечные элементы из более частично упорядоченного множества являются теми элементами , которые не могут быть отнесены на грани любого непустого направленного множества , которые уже не содержат член выше компактного элемента. Это понятие компактности одновременно обобщает понятия конечных множеств в теории множеств , компактов в топологии и конечно порожденных модулей в алгебре . (Есть и другие понятия компактности по математике.)
Формальное определение [ править ]
В частично упорядоченном множестве ( P , ≤) элемент c называется компактным (или конечным ), если он удовлетворяет одному из следующих эквивалентных условий:
- Для каждого направленного подмножества D в P , если D имеет грань вир D и C ≤ SUP D , то с ≤ D для некоторого элемента д из D .
- Для каждого идеала I из Р , если я имеет супремум вир I и гр ≤ вир I тогда C является элементом I .
Если ч.у.м. P дополнительно является полурешёткой соединения (т. Е. Если он имеет двоичную верхнюю границу), то эти условия эквивалентны следующему утверждению:
- Для каждого подмножества S из P , если S имеет грань SUP S и C ≤ SUP S , то с ≤ SUP Т для некоторого конечного подмножества Т из S .
В частности, если с = SUP S , то с является гранью некоторого конечного подмножества S .
Эти эквивалентности легко проверяются на основе определений задействованных понятий. В случае джойн-полурешетки любое множество можно превратить в направленное множество с той же супремумом, замкнувшись под конечной (непустой) супремумом.
При рассмотрении направленных полных частичных порядков или полных решеток дополнительные требования о существовании указанной супремумы, конечно, можно отбросить. Джойн-полурешетка, которая направленно полная, является почти полной решеткой (возможно, без наименьшего элемента ) - см. Подробности в полноте (теории порядка) .
Примеры [ править ]
- Самый простой пример получается при рассмотрении набора мощности некоторого множества A , упорядоченного по включению подмножества . В этой полной решетке, компактные элементы в точности конечные подмножества из А . Это оправдывает название «конечный элемент».
- Термин «компактный» объясняется рассмотрением полных решеток открытых множеств некоторого топологического пространства T , также упорядоченных по включению подмножеств . В таком порядке, компактные элементы являются только компактные подмножества из 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 .
Существует еще одна алгебраической решетки , которая играет важную роль в универсальной алгебре : Для каждой алгебра мы пусть Con ( ) множество всех отношений конгруэнтности на 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 .
Приложения [ править ]
Компактные элементы важны в информатике в семантическом подходе, называемом теорией предметной области , где они рассматриваются как своего рода примитивный элемент: информация, представленная компактными элементами, не может быть получена никаким приближением, которое еще не содержит этого знания. Компактные элементы не могут быть аппроксимированы элементами, находящимися строго под ними. С другой стороны, может случиться так, что все некомпактные элементы могут быть получены как направленные супремы компактных элементов. Это желательная ситуация, поскольку набор компактных элементов часто меньше, чем исходный poset - примеры выше иллюстрируют это.
Литература [ править ]
Смотрите литературу по заданной теории порядка и теории домена .
