Оператор закрытия - Closure operator

В математика, а оператор закрытия на набор S это функция ${ displaystyle operatorname {cl}: { mathcal {P}} (S) rightarrow { mathcal {P}} (S)}$ от набор мощности из S самому себе, которое удовлетворяет следующим условиям для всех множеств ${ displaystyle X, Y substeq S}$

${ Displaystyle X substeq OperatorName {cl} (X)}$	(cl - это обширный),
${ displaystyle X substeq Y Rightarrow operatorname {cl} (X) substeq operatorname {cl} (Y)}$	(cl - это монотонный),
${ Displaystyle OperatorName {cl} ( Operatorname {cl} (X)) = OperatorName {cl} (X)}$	(cl - это идемпотент).

Операторы замыкания определяются их закрытые наборы, т.е. множествами вида cl (Икс), поскольку закрытие cl (Икс) набора Икс - наименьшее замкнутое множество, содержащее Икс. Такие семейства «замкнутых множеств» иногда называют системы закрытия или же "Семьи Мур", в честь Э. Х. Мур который изучал операторы замыкания в своем 1910 г. Введение в форму общего анализа, в то время как концепция замыкания подмножества возникла в работе Фриджес Рис в связи с топологическими пространствами.^[1] Идея закрытия зародилась в конце XIX века, хотя в то время она не была официально оформлена, но при этом заметный вклад Эрнст Шредер, Ричард Дедекинд и Джордж Кантор.^[2]

Операторы закрытия также называются "операторы корпуса", что позволяет избежать путаницы с" операторами замыкания ", изученными в топология. Набор вместе с оператором замыкания на нем иногда называют закрытие пространства.

Приложения

У операторов замыкания есть много приложений:

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

{ displaystyle operatorname {cl} (X_ {1} cup dots cup X_ {n}) = operatorname {cl} (X_ {1}) cup dots cup operatorname {cl} (X_ { n})}

для всех ${ Displaystyle п в mathbb {N}}$ (Обратите внимание, что для ${ displaystyle n = 0}$ это дает ${ displaystyle operatorname {cl} ( varnothing) = varnothing}$ ).

В алгебра и логика, многие операторы замыкания операторы финального закрытия, т.е. они удовлетворяют

{ displaystyle operatorname {cl} (X) = bigcup left { operatorname {cl} (Y): Y substeq X { text {and}} Y { text {конечный}} right } .}

В теории частично упорядоченные наборы, которые важны в теоретическая информатика, у операторов замыкания есть более общее определение, которое заменяет ${ displaystyle substeq}$ с ${ displaystyle leq}$ . (Видеть § Операторы замыкания на частично упорядоченных множествах.)

Операторы замыкания в топологии

В топологическое замыкание подмножества Икс из топологическое пространство состоит из всех точек у пространства, так что каждый район из у содержит точку Икс. Функция, которая ассоциируется с каждым подмножеством Икс его замыкание является оператором топологического замыкания. И наоборот, каждый топологический оператор замыкания на множестве порождает топологическое пространство, замкнутые множества которого являются в точности замкнутыми множествами относительно оператора замыкания.

Операторы замыкания в алгебре

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

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

Линейная оболочка в векторном пространстве и аналогичное алгебраическое замыкание в поле удовлетворяют обменять недвижимость: Если Икс находится в закрытии союза А и {у} но не при закрытии А, тогда у находится в закрытии союза А и {Икс}. Оператор финитарного замыкания с этим свойством называется оператором матроид. В измерение векторного пространства, или степень превосходства поля (над его основное поле ) - это в точности ранг соответствующего матроида.

Функция, отображающая каждое подмножество данного поле к его алгебраическое замыкание также является оператором конечного замыкания и в целом отличается от оператора, упомянутого ранее. Операторы финитарного замыкания, обобщающие эти два оператора, изучаются в теория моделей как dcl (для определяемое закрытие) и acl (для алгебраическое замыкание).

В выпуклый корпус в п-размерный Евклидово пространство - еще один пример оператора конечного закрытия. Это удовлетворяет антиобменное имущество: Если Икс находится в замыкании объединения {у} и А, но не в объединении {у} и закрытие А, тогда у не является замыканием объединения {Икс} и А. Операторы финитарного замыкания с этим свойством порождают антиматроиды.

В качестве еще одного примера оператора замыкания, используемого в алгебре, если в некоторой алгебре есть универсум А и Икс представляет собой набор пар А, то оператор, присваивающий Икс наименьший соответствие содержащий Икс является оператором финального замыкания на А х А.^[3]

Операторы замыкания в логике

Предположим, у вас есть логический формализм который содержит определенные правила, позволяющие выводить новые формулы из заданных. Рассмотрим множество F всех возможных формул, и пусть п быть набор мощности из F, заказал ⊆. Для набора Икс формул, пусть cl (Икс) - множество всех формул, которые могут быть получены из Икс. Тогда cl - оператор замыкания на п. Точнее, cl можно получить следующим образом. Позвоните оператору "непрерывно" J так что для каждого направленный учебный класс Т,

J(lim T)= lim J(Т).

Это условие непрерывности основано на теореме о неподвижной точке для J. Рассмотрим одношаговый оператор J монотонной логики. Это оператор, связывающий любой набор Икс формул с множеством J(Икс) формул, которые являются либо логическими аксиомами, либо получены с помощью правила вывода из формул в Икс или находятся в Икс. Тогда такой оператор непрерывен, и мы можем определить cl (Икс) как наименьшую неподвижную точку для J больше или равно Икс. В соответствии с такой точкой зрения Тарский, Браун, Сушко и другие авторы предложили общий подход к логике, основанный на теории операторов замыкания. Также такая идея предлагается в логике программирования (см. Lloyd 1987) и в нечеткая логика (см. Герла 2000).

Операторы следствия

Около 1930 г. Альфред Тарский разработал абстрактную теорию логических выводов, которая моделирует некоторые свойства логических исчислений. Математически то, что он описал, является просто оператором конечного замыкания на множестве (множестве фразы). В абстрактная алгебраическая логика, операторы финитарного замыкания до сих пор изучаются под названием оператор следствия, который был придуман Тарским. Набор S представляет собой набор предложений, подмножество Т из S теория, а cl (Т) - это множество всех предложений, следующих из теории. В настоящее время этот термин может относиться к операторам закрытия, которые не обязательно должны быть конечными; операторы финитарного замыкания иногда называют операторы конечных последствий.

Замкнутые и псевдозамкнутые множества

Замкнутые множества относительно оператора замыкания на S сформировать подмножество C силовой установки п(S). Любое пересечение множеств в C снова в C. Другими словами, C является полной встречно-подполурешеткой п(S). Наоборот, если C ⊆ п(S) замкнута относительно произвольных пересечений, то функция, сопоставляющая каждому подмножеству Икс из S самый маленький набор Y ∈ C такой, что Икс ⊆ Y является оператором замыкания.

Существует простой и быстрый алгоритм генерации всех замкнутых наборов данного оператора замыкания.^[4]

Оператор замыкания на множестве топологичен тогда и только тогда, когда множество замкнутых множеств замкнуто относительно конечных объединений, т. Е. C является полной подрешеткой в п(S). Даже для нетопологических операторов замыкания C можно рассматривать как имеющую структуру решетки. (Соединение двух наборов Икс,Y ⊆ п(S) будучи cl (Икс ${ Displaystyle чашка}$ Y).) Но потом C это не подрешетка решетки п(S).

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

Каждый оператор замыкания на конечном множестве S однозначно определяется своими образами псевдозакрытый наборы.^[5]Они рекурсивно определены: множество псевдозакрытый если он не замкнут и содержит замыкание каждого из своих псевдозамкнутых собственных подмножеств. Формально: п ⊆ S псевдозамкнуто тогда и только тогда, когда

п ≠ cl (п) и
если Q ⊂ п псевдозамкнуто, то cl (Q) ⊆ п.

Операторы замыкания на частично упорядоченных множествах

А частично заказанный набор (poset) - это набор вместе с частичный заказ ≤, т.е. бинарное отношение что рефлексивно (а ≤ а), переходный (а ≤ б ≤ c подразумевает а ≤ c) и антисимметричный (а ≤ б ≤ а подразумевает а = б). Каждый набор мощности п(S) вместе с включением является частично упорядоченным множеством.

Функция cl: п → п из частичного заказа п к себе называется оператором замыкания, если он удовлетворяет следующим аксиомам для всех элементов Икс, у в п.

Икс ≤ cl (Икс)	(cl - это обширный)
Икс ≤ у следует cl (Икс) ≤ cl (у)	(cl - это увеличение )
cl (cl (Икс)) = cl (Икс)	(cl - это идемпотент )

Доступны более сжатые альтернативы: приведенное выше определение эквивалентно единственной аксиоме

Икс ≤ cl (у) тогда и только тогда, когда cl (Икс) ≤ cl (у)

для всех Икс, у в п.

С использованием поточечный порядок на функциях между посетами можно альтернативно записать свойство экстенсивности как id_п ≤ cl, где id - функция идентичности. Самостоятельная карта k которая возрастает и идемпотентна, но удовлетворяет двойной свойства экстенсивности, т.е. k ≤ id_п называется оператор ядра,^[6] оператор интерьера,^[7] или же двойное закрытие.^[8] Например, если А является подмножеством множества B, то собственно карта на powerset B данный μ_А(Икс) = А ∪ Икс является закрывающим оператором, тогда как λ_А(Икс) = А ∩ Икс является оператором ядра. В функция потолка от действительные числа к действительным числам, который присваивается каждому действительному Икс наименьший целое число не меньше чем Икс, является еще одним примером оператора закрытия.

А фиксированная точка функции cl, т.е.элемент c из п что удовлетворяет cl (c) = c, называется закрытый элемент. Оператор замыкания на частично упорядоченном множестве определяется его замкнутыми элементами. Если c является замкнутым элементом, то Икс ≤ c и cl (Икс) ≤ c являются эквивалентными условиями.

Каждый Связь Галуа (или же остаточное отображение ) вызывает оператор закрытия (как объясняется в этой статье). Фактически, каждый Таким образом, оператор замыкания возникает из подходящей связи Галуа.^[9] Связность Галуа не определяется однозначно оператором замыкания. Одна связность Галуа, которая порождает оператор замыкания cl, может быть описана следующим образом: если А - множество замкнутых элементов относительно cl, то cl: п → А является нижним сопряжением связи Галуа между п и А, причем верхним сопряженным является вложение А в п. Кроме того, каждый нижний сопряженный элемент вложения некоторого подмножества в п является оператором замыкания. «Операторы замыкания - это нижние сопряжения вложений». Однако обратите внимание, что не каждое вложение имеет нижний сопряженный элемент.

Любой частично упорядоченный набор п можно рассматривать как категория, с единым морфизмом из Икс к у если и только если Икс ≤ у. Операторы замыкания на частично упорядоченном множестве п тогда не что иное, как монады по категории п. Эквивалентно, оператор закрытия можно рассматривать как эндофунктор в категории частично упорядоченных множеств, которые имеют дополнительные идемпотент и обширный характеристики.

Если п это полная решетка, то подмножество А из п - множество замкнутых элементов для некоторого оператора замыкания на п если и только если А это Семья Мур на п, т.е. самый большой элемент п в А, а инфимум (встретить) любого непустого подмножества А снова в А. Любой такой набор А представляет собой полную решетку с порядком, унаследованным от п (но супремум (присоединение) операция может отличаться от операции п). Когда п это powerset Булева алгебра набора Икс, затем семья Мур на п называется система закрытия на Икс.

Операторы замыкания на п образуют собой целостную решетку; порядок операторов замыкания определяется cl₁ ≤ cl₂ если только cl₁(Икс) ≤ cl₂(Икс) для всех Икс в п.

Смотрите также

Примечания

^ Блит стр.11
^ Марсель Эрне, Закрытие, в Frédéric Mynard, Elliott Pearl (редакторы), Помимо топологии, Современная математика т. 486, Американское математическое общество, 2009.
^ Клиффорд Бергман, Универсальная алгебра, 2012, Раздел 2.4.
^ Гантер, Алгоритм 1
^ Гантер, Раздел 3.2
^ Гертц, стр. 26
^ Эрне, стр. 2, использует операцию закрытия (или внутреннюю)
^ Блит, стр. 10
^ Блит, стр. 10

внешняя ссылка

Стэнфордская энциклопедия философии: "Алгебраическая логика высказываний "- Рамон Янсана.

[1] Блит стр.11

[2] Марсель Эрне, Закрытие, в Frédéric Mynard, Elliott Pearl (редакторы), Помимо топологии, Современная математика т. 486, Американское математическое общество, 2009.

[3] Клиффорд Бергман, Универсальная алгебра, 2012, Раздел 2.4.

[4] Гантер, Алгоритм 1

[5] Гантер, Раздел 3.2

[6] Гертц, стр. 26

[7] Эрне, стр. 2, использует операцию закрытия (или внутреннюю)

[8] Блит, стр. 10

[9] Блит, стр. 10

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]