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

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

$X\subseteq \operatorname {cl} (X)$	(cl обширен ),
$X\subseteq Y\Rightarrow \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)$	(cl увеличивается ),
$\operatorname {cl} (\operatorname {cl} (X))=\operatorname {cl} (X)$	(cl идемпотент ).

Операторы замыкания определяются своими замкнутыми множествами , т. е. множествами вида cl( X ), поскольку замыкание cl( X ) множества X есть наименьшее замкнутое множество, X. содержащее Такие семейства «замкнутых множеств» иногда называют системами замыкания или « семействами Мура ». Множество вместе с оператором замыкания на нем иногда называют пространством замыкания . Операторы замыкания также называются « операторами оболочки », что позволяет избежать путаницы с «операторами замыкания», изучаемыми в топологии .

История

Э. Х. Мур изучал операторы замыкания в своем «Введении в одну из форм общего анализа» 1910 года , тогда как концепция замыкания подмножества возникла в работах Фридьеса Риса в связи с топологическими пространствами. Хотя идея закрытия в то время не была формализована, она возникла в конце 19 века благодаря заметному вкладу Эрнста Шредера , Рихарда Дедекинда и Георга Кантора .

Примеры

Выпуклая оболочка (красная) многоугольника ( желтая)

Обычное замыкание множества из топологии — это оператор замыкания. Другие примеры включают линейную оболочку подмножества векторного пространства , выпуклую оболочку или аффинную оболочку подмножества векторного пространства или нижнюю полунепрерывную оболочку. ${\overline {f}}$ функции $f\colon E\to \mathbb {R} \cup \{\pm \infty \}$, где $E$ например, нормированное пространство , определенное неявно $\operatorname {epi} ({\overline {f}})={\overline {\operatorname {epi} (f)}}$, где $\operatorname {epi} (f)$ это эпиграф функции $f$.

Относительный интерьер $\operatorname {ri}$ не является оператором замыкания: хотя он идемпотентен, но не возрастает, и если $C_{1}$ это куб в $\mathbb {R} ^{3}$ и $C_{2}$ является одним из его лиц, то $C_{2}\subset C_{1}$, но $\operatorname {ri} (C_{1})\neq \emptyset \neq \operatorname {ri} (C_{2})$ и $\operatorname {ri} (C_{1})\cap \operatorname {ri} (C_{2})=\emptyset$, поэтому оно не увеличивается.

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

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

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

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

$\operatorname {cl} (X)=\bigcup \left\{\operatorname {cl} (Y):Y\subseteq X{\text{ and }}Y{\text{ finite}}\right\}.$

В теории частично упорядоченных множеств , которая важна для теоретической информатики , операторы замыкания имеют более общее определение, которое заменяет $\subseteq$ с $\leq$. (См. § Операторы замыкания на частично упорядоченных множествах .)

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

Основная статья: аксиомы замыкания Куратовского

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

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

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

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

Линейная оболочка в векторном пространстве и аналогичное алгебраическое замыкание в поле удовлетворяют свойству обмена: если x находится в замыкании объединения A и { y }, но не в замыкании A , то y находится в замыкании объединения A и { x }. Оператор финитного замыкания, обладающий этим свойством, называется матроидом . Размерность простым векторного пространства или степень трансцендентности поля (над его полем ) равна в точности рангу соответствующего матроида.

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

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

Другой пример оператора замыкания, используемого в алгебре: если некоторая алгебра имеет универсум A и X представляет собой набор пар A , то оператор, присваивающий X наименьшее сравнение , содержащее X, является оператором финитного замыкания на A x A .

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

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

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

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

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

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

Закрытые наборы

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

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

Оператор замыкания на множестве является топологическим тогда и только тогда, когда множество замкнутых множеств замкнуто относительно конечных объединений, т. е. C является полной подрешеткой P ( S ). Даже для нетопологических операторов замыкания C можно рассматривать как имеющий структуру решетки. (Объединение двух множеств X , Y ⊆ P ( S ) равно cl( X $\cup$ Y ).) Но тогда C не является подрешеткой решетки P ( S ).

Учитывая оператор финитного замыкания на множестве, замыкания конечных множеств являются в точности компактными элементами множества C замкнутых множеств. Отсюда следует, что C — алгебраическое ЧУМ . Поскольку C также является решеткой, в этом контексте ее часто называют алгебраической решеткой. И наоборот, если C — алгебраическое ЧУМ, то оператор замыкания финитирен.

Псевдозамкнутые множества

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

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

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

( Частично упорядоченный набор poset) — это набор вместе с частичным порядком ≤, т.е. бинарное отношение , которое является рефлексивным ( a ≤ a ), транзитивным ( a ≤ b ≤ c подразумевает a ≤ c ) и антисимметричным ( a ≤ b ≤ a подразумевает а = б ). Каждое степенное множество P ( S ) вместе с включением ⊆ является частично упорядоченным множеством.

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

х ≤ кл( х )	(cl обширен )
x ≤ y подразумевает cl( x ) ≤ cl( y )	(cl увеличивается )
кл(кл( х )) = кл( х )	(cl идемпотент )

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

x ≤ cl( y ) тогда и только тогда, когда cl( x ) ≤ cl( y )

для x , y в P. всех

Используя поточечный порядок функций между частично упорядоченными множествами, можно альтернативно записать свойство экстенсивности как id _P ≤ cl, где id — тождественная функция . Самоотображение k , которое является возрастающим и идемпотентным, но удовлетворяет двойственному свойству экстенсивности, т. е. k ≤ id _P , называется оператором ядра , внутренний оператор или двойное закрытие . Например, если A является подмножеством множества B , то самоотображение на множестве степеней B , заданное формулой µ _A ( X ) = A ∪ X , является оператором замыкания, тогда как λ _A ( X ) = A ∩ X является оператором замыкания. оператор ядра. Функция потолка от действительных чисел к действительным числам, которая присваивает каждому действительному x наименьшее целое число , не меньшее x , является еще одним примером оператора замыкания.

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

Каждое соединение Галуа (или резидуированное отображение ) порождает оператор замыкания (как объясняется в этой статье). Фактически, каждый оператор замыкания возникает таким образом из подходящей связности Галуа. Связность Галуа не определяется однозначно оператором замыкания. Одно соединение Галуа, которое приводит к оператору замыкания cl, можно описать следующим образом: если A — множество замкнутых элементов относительно cl, то cl: P → A — нижний сопряженный связности Галуа между P и A , причем верхним сопряжением является вложение A в P . Более того, каждый нижний сопряженный вложения некоторого подмножества в P является оператором замыкания. «Операторы замыкания — это нижние сопряжения вложений». Однако обратите внимание, что не каждое вложение имеет нижний сопряженный.

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

Если P — полная решетка , то подмножество A в P является множеством замкнутых элементов для некоторого оператора замыкания на P тогда и только тогда, когда A — семейство Мура на P , т. е. наибольший элемент P находится в A , а нижняя грань (встреча) любого непустого подмножества A снова находится в A . Любой такой набор A сам по себе является полной решеткой с порядком, унаследованным от P (но операция супремума (объединения) может отличаться от операции P ). Когда P — степенная булева алгебра множества X , то семейство Мура на называется системой замыкания на X. P

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

См. также

• Оператор закрытия Čech – Оператор закрытия. Страницы, отображающие краткие описания целей перенаправления.
• Замыкание (топология) - все точки и предельные точки в подмножестве топологического пространства.
• Связь Галуа - Особое соответствие между двумя частично упорядоченными множествами.
• Внутренняя алгебра – Алгебраическая структура
• Интерьер (топология) - наибольшее открытое подмножество некоторого заданного набора.
• Аксиомы замыкания Куратовского - математическая концепция. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Оператор предварительного закрытия – Оператор закрытия

Ссылки

• Гаррет Биркгоф . 1967 (1940). Теория решеток, 3-е изд . Американское математическое общество.
• Беррис, Стэнли Н. и HP Санкаппанавар (1981) Курс универсальной алгебры Springer-Verlag. ISBN   3-540-90578-2 Бесплатное онлайн-издание .
• Браун, DJ и Сушко, Р. (1973) «Абстрактная логика», Mathematical Dissertations 102-9-42.
• Кастеллини, Г. (2003) Операторы категориального замыкания . Бостон, Массачусетс: Биркхойзер.
• Эдельман, Пол Х. (1980) Дистрибутивные решетки и антиобменное замыкание, Algebra Universalis 10: 290-299.
• Гантер, Бернхард и Объедков, Сергей (2016) Концептуальное исследование . Спрингер, ISBN   978-3-662-49290-1 .
• Герла, Г. (2000) Нечеткая логика: математические инструменты для приближенного рассуждения . Академическое издательство Kluwer .
• Ллойд, JW (1987) Основы логического программирования . Спрингер-Верлаг .
• Тарский, Альфред (1983) «Основные концепции методологии дедуктивных наук» в логике, семантике, метаматематике . Хакетт (изд. 1956 г., Oxford University Press ).
• Альфред Тарский (1956) Логика, семантика и метаматематика . Издательство Оксфордского университета .
• Уорд, Морган (1942) «Операторы замыкания решетки», Annals of Mathematics 43: 191–96.
• Г. Гирц, К. Х. Хофманн, К. Кеймель, Дж. Д. Лоусон, М. Мислов, Д. С. Скотт: непрерывные решетки и области , издательство Кембриджского университета, 2003 г.
• Т. С. Блит, Решетки и упорядоченные алгебраические структуры , Springer, 2005, ISBN   1-85233-905-5 .
• М. Эрне, Дж. Козловски, А. Мелтон, Дж. Э. Стрекер, Букварь по связям Галуа , в: Материалы летней конференции 1991 года по общей топологии и приложениям в честь Мэри Эллен Рудин и ее работ, Анналы Нью-Йоркской академии. наук, Vol. 704, 1993, стр. 103–125. Доступно онлайн в различных форматах файлов: PS.GZ PS.

Внешние ссылки

• Стэнфордская энциклопедия философии : « Алгебраическая логика высказываний » — Рамон Джансана.