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

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

• $x\leqslant C(x)$ (экстенсивность),
• $x\leqslant y\Rightarrow C(x)\leqslant C(y)$ (монотонность)
• $C(C(x))=C(x)$ (идемпотентность)

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

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

$C(x)=\inf \lbrace c\in C(P):c\geq x\rbrace$.

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

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

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

$C(X_{1}\cup \dots \cup X_{n})=C(X_{1})\cup \dots \cup C(X_{n})$ для любого $n\in \mathbb {N}$.

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

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

$C(X)=\bigcup _{Y\in {\mathcal {F}}(X)}C(Y)$, где ${\mathcal {F}}(X)$ — множество всех конечных подмножеств множества $X$.

В универсальной логике примером замыкания является оператор следствия (англ. consequence operator).

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

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

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

Фактически, аксиоматика Куратовского — это система аксиом общей топологии, эксплуатирующая эту идею. Она выстраивает топологическую структуру, отталкиваясь от определения оператора топологического замыкания $C$ как экстенсивного идемпотентного оператора, обладающего свойством $C(X\cup Y)=C(X)\cup C(Y)$.

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

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

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

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

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

Функция, отображающее подмножество поля в его алгебраическое замыкание — тоже оператор финитарного замыкания, но отличающийся по своим свойствам от операторов, рассмотренных выше. Эти две разновидности замыкания изучаются в теории моделей, где они обозначаются $\operatorname {dcl}$ (от англ. definable closure) и $\operatorname {acl}$ (от англ. algebraic closure).

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

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

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

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

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

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

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

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

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

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

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

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

$x\leq C(y)\Leftrightarrow C(x)\leq C(y)$ для любых $x,y\in P$.

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

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

Монотонное идемпотентное отображение $I:P\to P$, обладающее двойственным свойством $I\leq \operatorname {id}$, называется оператором ядра (англ. kernel operator), оператором внутренности (англ. interior operator) или двойственным замыканием (англ. dual closure). Пример такой функции — операция получения внутренности множества в топологии. Другой пример даёт функция округления, рассматриваемая как оператор на вещественных числах с естественным порядком: округление к меньшему (англ. floor, $\lfloor x\rfloor$) — это оператор внутренности, а округление к большему (англ. ceil, $\lceil x\rceil$) — оператор замыкания. Ещё один пример: если $S$ — некоторое множество, и в нём зафиксировано произвольное подмножество $T$, то $\mu _{T}(X)=T\cap X$ является оператором внутренности на булеане $P=2^{S}$, а $\lambda _{T}(X)=T\cup X$ — оператором замыкания.

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

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

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

Если $P$ — полная решётка, то для того, чтобы подмножество $K\subseteq P$ было множеством замкнутых элементов какого-либо оператора $C$, необходимо и достаточно, чтобы $K$ образовывало муровское семейство на $P$, то есть множество, содержащее верхнюю границу $P$ и точную нижнюю грань любого подмножества множества $K$. Любое такое $K$ само является полной решёткой, причём отношение порядка и нижняя операция (инфимум) наследуются из $P$, а верхняя операция (супремум) может отличаться. Когда решётка $P$ введена как булева алгебра подмножеств некоторого множества $S$, муровское семейство называют системой замыканий (англ. closure system) множества $S$.

Операторы замыкания на полной решётке сами образуют полную решётку, отношение порядка на которой вводится поточечно: $C_{1}\leq C_{2}$ тогда и только тогда, когда $\forall x\in P\;C_{1}(x)\leq C_{2}(x)$.

История

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

Cм. также

• Замыкание (геометрия) и Внутренность
• Замыкание отношения
• Соответствие Галуа

Литература

• Birkhoff, G. Lattice Theory. — 3rd ed. — Providence, RI : American Mathematical Society, 1973. — vi, 418 p. — (American Mathematical Society Colloquium Publications ; vol. XXV). — ISBN 0-8218-1025-1. — .
  [Русский перевод: Биркгоф, Г. Теория решеток. — М. : Наука. Главная редакция физико-математической литературы, 1984. — 568 с. — 9400 экз.]
• Blyth, T. S. Lattices and Ordered Algebraic Structures. — London : Springer-Verlag, 2005. — ix, 303 p. — (Universitext). — ISBN 1-85233-905-5. — doi:10.1007/B139095. — .
• Brown, D. J. Abstract Logics / D. J. Brown, R. Suszko // Dissertationes Mathematicae. — 1973. — Vol. CII. — P. 9–41. — ISSN 0012-3862.
• Burris, S. A Course in Universal Algebra / S. Burris, H. P. Sankappanavar. — New York, NY : Springer-Verlag, 1981. — xvi, 276 p. — (Graduated Texts in Mathematics ; vol. 78). — ISBN 0-387-90578-2. — .
  [Бесплатное электронное издание: Burris, S. A Course in Universal Algebra / S. Burris, H. P. Sankappanavar. — The Millenium Edition, 2012 Update. — 2012. — xiv, 276 p. : 36 illus. — ISBN 978-0-9880552-0-9.]
• Castellini, G. Categorical Closure Operators : [арх. 30 декабря 2015]. — Boston, MA : Birkhäuser, 2003. — xii, 300 p. — (Mathematics: Theory & Applications). — ISBN 978-1-4612-6504-7. — doi:10.1007/978-0-8176-8234-7.
• Edelman, P. H. Meet-distributive Lattices and the Anti-exchange Closure // Algebra Universalis. — 1980. — Vol. 10, no. 1. — P. 290–299. — ISSN 0002-5240. — doi:10.1007/BF02482912.
• Erné, M. A primer on Galois connections / M. Erné, J. Koslowski, A. Melton … [et al.] // Annals of the New York Academy of Sciences. — 1993. — Vol. 704 : Papers on General Topology and Applications. — P. 103–125. — ISSN 0077-8923. — doi:10.1111/j.1749-6632.1993.tb52513.x.
  [Электронные препринты:
  • Erné, M., et al. A primer on Galois connections : [PS.GZ] / prep. by J. Koslowski // Jürgen Koslowski's Home Page. — 1991/92.
  • Erné, M., et al. A primer on Galois connections : non-RPN version : [PS.GZ] / prep. by J. Koslowski // Jürgen Koslowski's Home Page. — 1991/92.
  • Erné, M., et al. A primer on Galois connections : [PS] / prep. by G. E. Strecker // George E. Strecker (Home Page).]
• Gerla, G. Fuzzy Logic : Mathematical Tools for Approximate Reasoning. — Dordrecht : Kluwer Academic Publishers, 2001. — xii, 269 p. — (Trends in Logic ; vol. 11). — ISBN 0-7923-6941-6. — doi:10.1007/978-94-015-9660-2.
• Gierz, G. Continuous Lattices and Domains / G. Gierz, K. H. Hoffman, K. Keimel … [et al.]. — New York, NY : Cambridge University Press, 2003. — xxxvi, 591 p. — (Encyclopedia of Mathematics and its Applications ; vol. 93). — ISBN 0-521-80338-1.
• Lloyd, J. W. Foundations of Logic Programming. — 2nd ext. ed. — Berlin : Springer-Verlag, 1987. — xii, 212 p. — (Artificial Intelligence. Ser. Symbolic Computation). — ISBN 3-540-18199-7. — ISBN 978-3-642-83191-1. — doi:10.1007/978-3-642-83189-8.
• Tarski, A. Fundamental Concepts of the Methodology of Deductive Sciences = Fundamentale Begriffe der Methodologie der deduktiven Wissenschaften : [orig. 1930] // Logic, Semantics, Metamathematics. Papers from 1923 to 1938 by Alfred Tarski / transl. by J. H. Woodger. — Oxford : Clarendon Press, 1956. — P. 60–109. — .
• Ward, M. The Closure Operators of a Lattice // Annals of Mathematics. — 1942. — Vol. 43, no. 2. — P. 191–196. — ISSN 0003-486X. — doi:10.2307/1968865. — .

Ссылки

• Jansara, Ramon. Algebraic Propositional Logic / Edward N. Zalta (ed.) // Stanford Encyclopedia of Philosophy. — Metaphysics Research Lab, Stanford University, 2016. — 12 December.