Русская Википедия:Оператор замыкания

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Оператор замыкания — обобщение интуитивной концепции замыкания. Именно: если <math>\langle P, \leqslant\rangle</math> — частично упорядоченное множество, оператор <math>C: P\to P</math> будет называться оператором замыкания, если выполнены три условия:

В роли множества <math>P</math> часто выступает булеан некоторого другого множества <math>S</math>; примеры этого можно найти в топологии, алгебре и логике.

Элементы вида <math>C(x)</math> называются замкнутыми, они образуют подмножество <math>C(P)</math> в исходном частично упорядоченном множестве <math>P</math>. Оператор замыкания полностью определяется множеством замкнутых элементов; а именно, замыкание элемента <math>x \in P</math> — это наименьший замкнутый элемент, больший или равный данного:

<math>C(x) = \inf\lbrace c \in C(P): c \geq x\rbrace</math>.

Множество всех замкнутых элементов иногда называют муровским семействомШаблон:Sfn в честь американского математика Элиакима Мура, исследовавшего замыкания в 1910 годуШаблон:Sfn. Некоторые частные случаи замыкания называют оболочкой (например, выпуклая оболочка или линейная оболочка) — это позволяет избегать путаницы с понятием замкнутого множества.

Примеры операторов замыкания можно найти в самых разных областях математики:

В топологии изучается замыкание множества. Топологическое замыкание «уважает» конечное объединение множеств:

<math>C(X_1 \cup\dots\cup X_n) = C(X_1)\cup\dots\cup C(X_n)</math> для любого <math>n \in \mathbb{N}</math>.

В частности, при <math>n = 0</math> эта формула превращается в <math>C(\varnothing) = \varnothing</math>.

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

<math>C(X) = \bigcup_{Y \in \mathcal{F}(X)} C(Y)</math>, где <math>\mathcal{F}(X)</math> — множество всех конечных подмножеств множества <math>X</math>.

В универсальной логике примером замыкания является оператор следствия (Шаблон:Lang-en).

Теоретическая информатика также очень широко применяет все наработки теории порядков в области операторов замыкания, включая определение на произвольных частично упорядоченных множествах.

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

Замыкание множества <math>X</math> в заданном топологическом пространстве состоит из тех точек пространства, любая окрестность которых имеет хотя бы одну общую точку с <math>X</math>. Функция, сопоставляющая каждому подмножеству данного пространства его замыкание, является оператором топологического замыкания (в смысле, определённом выше). И наоборот, любой оператор топологического замыкания <math>C: 2^S \to 2^S</math> задаёт топологию на множестве <math>S</math>, в которой множество <math>X \subseteq S</math> замкнуто тогда и только тогда, когда оно является элементом булеана <math>2^S</math>, замкнутым относительно оператора <math>C</math>.

Фактически, Шаблон:Нп5 — это система аксиом общей топологии, эксплуатирующая эту идею. Она выстраивает топологическую структуру, отталкиваясь от определения оператора топологического замыкания <math>C</math> как экстенсивного идемпотентного оператора, обладающего свойством <math>C(X \cup Y) = C(X) \cup C(Y)</math>.

Аксиома монотонности для оператора топологического замыкания является излишней, так как выводится из остальных аксиом.

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

Финитарное замыкание играет важную роль в универсальной алгебре, где традиционно называется алгебраическим замыканием. Любое подмножество <math>X</math> алгебры <math>A</math> определяет некоторую подалгебру: наименьшую из всех подалгебр, содержащих данное множество. Так вводится оператор замыкания на булеане <math>2^A</math>.

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

Операторы замыкания «линейная оболочка» и «наименьшее подполе, содержащее данное множество» обладают т. н. обменным свойством: если <math>a</math> принадлежит замыканию <math>X \cup \{b\}</math>, но не принадлежит замыканию множества <math>X</math>, то <math>b</math> принадлежит замыканию <math>X \cup \{a\}</math>. Финитарное замыкание, обладающее этим свойством, называется матроидом. Размерность векторного пространства и степень трансцендентности поля (над его простым полем) — это в точности ранг соответствующего матроида.

Функция, отображающее подмножество поля в его алгебраическое замыкание — тоже оператор финитарного замыкания, но отличающийся по своим свойствам от операторов, рассмотренных выше. Эти две разновидности замыкания изучаются в теории моделей, где они обозначаются <math>\operatorname{dcl}</math> (от Шаблон:Lang-en) и <math>\operatorname{acl}</math> (от Шаблон:Lang-en).

Выпуклая оболочка в евклидовом пространстве представляет ещё один пример финитарного замыкания. Этот оператор обладает антиобменным свойством: если <math>a</math> не принадлежит множеству <math>X \cup \{b\}</math>, но принадлежит его замыканию, то <math>b</math> не принадлежит замыканию <math>X \cup \{a\}</math>. Финитарные замыкания с этим свойством приводят к понятию Шаблон:Нп5.

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

Рассмотрим некоторый логический формализм, который позволяет, следуя определённым правилам, выводить новые формулы из имеющихся. Пусть <math>F</math> обозначает множество всех возможных формул, а <math>P = 2^F</math> — булеан этого множества, упорядоченный по включению. Для произвольного множества формул <math>X</math>, обозначим <math>C(X)</math> множество формул, выводимых из <math>X</math>. Тогда <math>C</math> — оператор замыкания, заданный на <math>P</math>.

Более строго можно определить <math>C</math> следующим образом. Пусть <math>J: P \to P</math> — оператор дедуктивного шага в монотонной логике; иными словами, <math>J(X)</math> — это множество формул, каждая из которых либо является аксиомой, либо принадлежит <math>X</math>, либо получена однократным применением какого-либо правила вывода к формулам из <math>X</math>. Заметим, что для любого направленного класса <math>T</math> выполняется равенство <math>J(\lim T) = \lim J(T)</math>, следовательно, оператор <math>J</math> непрерывен и к нему можно применить теорему о неподвижной точке. Тогда <math>C(X)</math> определяется как наименьшая неподвижная точка <math>J</math>, большая или равная <math>X</math>. В соответствии с такой точкой зрения, ТарскийШаблон:Sfn, Браун и СушкоШаблон:Sfn, а также другие авторы, предложили общий подход к математической логике, основанный на теории операторов замыкания. Та же идея нашла применение в логическом программированииШаблон:Sfn и нечёткой логикеШаблон:Sfn.

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

Около 1930 г. Альфред Тарский разработал абстрактную теорию дедукции, моделирующую некоторые свойства логических исчислений. С математической точки зрения, он описал финитарное замыкание на множестве высказываний. В универсальной логике за этим замыканием закрепилось название, придуманное Тарским: оператор следствия (Шаблон:Lang-en). Итак, пусть <math>S</math> — множество всех возможных высказываний, его подмножество <math>T</math> — теория; тогда <math>C(T)</math> — это множество высказываний, которые являются логическим следствием теории <math>T</math>. В настоящее время термин «оператор следствия» может применяться не только к финитарным операторам; в таком случае, если оператор всё же удовлетворяет условию финитарности, о нем говорят как об операторе конечного следствия (Шаблон:Lang-en).

Замкнутые множества

Пусть оператор замыкания <math>C</math> действует на булеане <math>P = 2^S</math>. Семейство замкнутых подмножеств <math>C(P)</math> образует подмножество в <math>P</math>. Любое пересечение множеств из <math>C(P)</math> снова лежит в <math>C(P)</math>, то есть <math>C(P)</math> — полная нижняя подполурешётка в <math>P</math>. Соответственно, если некоторое множество <math>K \subseteq 2^S</math> замкнуто относительно произвольных (возможно, бесконечных) пересечений, то функция, сопоставляющая каждому подмножеству <math>X \subseteq S</math> наименьшее множество <math>Y \in K</math>, содержащее <math>X</math>, является оператором замыкания.

Оператор замыкания называется топологическим, если семейство замкнутых множеств замкнуто относительно конечных объединений, то есть если <math>C(P)</math> образует подрешётку, полную относительно операции объединения. Даже если оператор <math>C</math> не является топологическим, множество <math>C(P)</math> всё равно обладает структурой решётки (с операциями <math>\wedge</math> и <math>\vee</math>, определёнными так: <math>X \wedge Y = X \cap Y</math>, <math>X \vee Y = C(X \cup Y)</math>); но в этом случае <math>C(P)</math> не является подрешёткой <math>P</math>, так как операции на них не согласованы.

Если оператор замыкания финитарный, замыканиями конечных множеств являются Шаблон:Нп5 множества <math>C(P)</math>. Следовательно, <math>C(P)</math> — Шаблон:Нп5 (или «алгебраическая решётка», если учитывать, что на <math>C(P)</math> действительно имеется структура решётки). И наоборот, если семейство замкнутых множеств является алгебраическим частично-упорядоченным множеством, то соответствующий оператор замыкания финитарный.

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

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

<math>x \leq C(y) \Leftrightarrow C(x) \leq C(y)</math> для любых <math>x, y \in P</math>.

Если считать, что между отображениями определено поточечное сравнение, то свойство экстенсивности оператора <math>C: P \to P</math> можно кратко записать так:

<math>C \geq \operatorname{id}</math>, где <math>\operatorname{id}</math> обозначает тождественную функцию.

Монотонное идемпотентное отображение <math>I: P \to P</math>, обладающее двойственным свойством <math>I \leq \operatorname{id}</math>, называется оператором ядра (Шаблон:Lang-enШаблон:Sfn), оператором внутренности (Шаблон:Lang-enШаблон:Sfn) или двойственным замыканием (Шаблон:Lang-enШаблон:Sfn). Пример такой функции — операция получения внутренности множества в топологии. Другой пример даёт функция округления, рассматриваемая как оператор на вещественных числах с естественным порядком: округление к меньшему (Шаблон:Lang-en, <math>\lfloor x \rfloor</math>) — это оператор внутренности, а округление к большему (Шаблон:Lang-en, <math>\lceil x \rceil</math>) — оператор замыкания. Ещё один пример: если <math>S</math> — некоторое множество, и в нём зафиксировано произвольное подмножество <math>T</math>, то <math>\mu_T(X) = T \cap X</math> является оператором внутренности на булеане <math>P = 2^S</math>, а <math>\lambda_T(X) = T \cup X</math> — оператором замыкания.

Неподвижная точка отображения <math>C</math>, то есть элемент <math>c \in P</math>, обладающий свойством <math>C(c) = c</math>, называется замкнутым. Оператор замыкания на частично упорядоченном множестве полностью определяется множеством замкнутых элементов. Если элемент <math>c</math> замкнут, то утверждение <math>x \leq c</math> равносильно <math>C(x) \leq c</math>.

Как объясняется в статье, посвящённой соответствию Галуа, всякое такое соответствие порождает оператор замыкания. Более того, любой оператор замыкания можно получить из некоторого соответствия ГалуаШаблон:Sfn. Построить подходящее соответствие Галуа можно не единственным образом; универсальный способ состоит в следующем. Пусть <math>K</math> обозначает множество замкнутых элементов. Тогда <math>C</math> можно рассматривать как отображение <math>P \to K</math>; это будет нижняя сопряжённая функция соответствия Галуа. В качестве верхней сопряжённой функции возьмём вложение <math>K \to P</math>. Фактически, любая функция, являющаяся нижней сопряженной к вложению некоторого подмножества в <math>P</math>, и есть замыкание: «Операторы замыкания суть нижние сопряженные к вложениям.» Однако не для каждого вложения существует нижняя сопряженная функция!

Всякое частично упорядоченное множество <math>P</math> можно рассматривать как категорию, в которой стрелка <math>x \to y</math> существует (и единственна) тогда и только тогда, когда <math>x \leq y</math>. В такой интерпретации операторы замыкания соответствуют монадам

Если <math>P</math> — полная решётка, то для того, чтобы подмножество <math>K \subseteq P</math> было множеством замкнутых элементов какого-либо оператора <math>C</math>, необходимо и достаточноШаблон:Sfn, чтобы <math>K</math> образовывало муровское семейство на <math>P</math>, то есть множество, содержащее верхнюю границу <math>P</math> и точную нижнюю грань любого подмножества множества <math>K</math>. Любое такое <math>K</math> само является полной решёткой, причём отношение порядка и нижняя операция (инфимум) наследуются из <math>P</math>, а верхняя операция (супремум) может отличаться. Когда решётка <math>P</math> введена как булева алгебра подмножеств некоторого множества <math>S</math>, муровское семейство называют системой замыканийШаблон:Sfn (Шаблон:Lang-en) множества <math>S</math>.

Операторы замыкания на полной решётке сами образуют полную решётку, отношение порядка на которой вводится поточечно: <math>C_1 \leq C_2</math> тогда и только тогда, когда <math>\forall x \in P \; C_1(x) \leq C_2(x)</math>.

История

Понятие замыкания было введено Э. Г. Муром в монографии 1910 года Introduction to a Form of General Analysis. Концепция системы замкнутых подмножеств впервые была описана в работах Ф. Риса применительно к топологическим пространствамШаблон:Sfn.

Cм. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Оператор_замыкания&oldid=10518095