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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Оператор замыкания — обобщение интуитивной концепции замыкания. Именно: если  — частично упорядоченное множество, оператор будет называться оператором замыкания, если выполнены три условия:

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

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

.

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

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

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

для любого .

В частности, при эта формула превращается в .

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

, где — множество всех конечных подмножеств множества .

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

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

Оператор замыкания в топологии[править | править вики-текст]

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

Фактически, аксиоматика Куратовского[en] — это система аксиом общей топологии, эксплуатирующая эту идею. Она выстраивает топологическую структуру, отталкиваясь от определения оператора топологического замыкания как экстенсивного идемпотентного оператора, обладающего свойством .

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

Оператор замыкания в алгебре[править | править вики-текст]

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

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

Операторы замыкания «линейная оболочка» и «наименьшее подполе, содержащее данное множество» обладают т.н. обменным свойством: если принадлежит замыканию , но не принадлежит замыканию множества , то принадлежит замыканию . Финитарное замыкание, обладающее этим свойством, называется матроидом. Размерность векторного пространства и степень трансциндентности[en] поля (над его простым полем) — это в точности ранг соответствующего матроида.

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

Выпуклая оболочка в евклидовом пространстве представляет ещё один пример финитарного замыкания. Этот оператор обладает антиобменным свойством: если не принадлежит множеству , но принадлежит его замыканию, то не принадлежит замыканию . Финитарные замыкания с этим свойством приводят к понятию антиматроида[en].

Оператор замыкания в логике[править | править вики-текст]

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

Более строго можно определить следующим образом. Пусть — оператор дедуктивного шага в монотонной логике; иными словами, — это множество формул, каждая из которых либо является аксиомой, либо принадлежит , либо получена однократным применением какого-либо правила вывода к формулам из . Заметим, что для любого направленного класса выполняется равенство , следовательно, оператор непрерывен и к нему можно применить теорему о неподвижной точке. Тогда определяется как наименьшая неподвижная точка , большая или равная . В соответствии с такой точкой зрения, Тарский[3], Браун и Сушко[4], а также другие авторы, предложили общий подход к математической логике, основанный на теории операторов замыкания. Та же идея нашла применение в логическом программировании[5] и нечёткой логике[6].

Оператор следствия[править | править вики-текст]

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

Замкнутые множества[править | править вики-текст]

Пусть оператор замыкания действует на булеане . Семейство замкнутых подмножеств образует подмножество в . Любое пересечение множеств из снова лежит в , т.е. полная нижняя подполурешётка в . Соответственно, если некоторое множество замкнуто относительно произвольных (возможно, бесконечных) пересечений, то функция, сопоставляющая каждому подмножеству наименьшее множество , содержащее , является оператором замыкания.

Оператор замыкания называется топологическим, если семейство замкнутых множеств замкнуто относительно конечных объединений, т.е. если образует подрешётку, полную относительно операции объединения. Даже если оператор не является топологическим, множество всё равно обладает структурой решётки (с операциями и , определёнными так: , ); но в этом случае не является подрешёткой , т.к. операции на них не согласованы.

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

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

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

для любых .

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

, где обозначает тождественную функцию.

Монотонное идемпотентное отображение , обладающее двойственным свойством , называется оператором ядра (англ. kernel operator[7]), оператором внутренности (англ. interior operator[8]) или двойственным замыканием (англ. dual closure[9]). Пример такой функции — операция получения внутренности множества в топологии. Другой пример даёт функция округления, рассматриваемая как оператор на вещественных числах с естественным порядком: округление к меньшему (англ. floor, ) — это оператор внутренности, а округление к большему (англ. ceil, ) — оператор замыкания. Ещё один пример: если — некоторое множество, и в нём зафиксировано произвольное подмножество , то является оператором внутренности на булеане , а — оператором замыкания.

Неподвижная точка отображения , т.е. элемент , обладающий свойством , называется замкнутым. Оператор замыкания на частично упорядоченном множестве полностью определяется множеством замкнутых элементов. Если элемент замкнут, то утверждение равносильно .

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

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

Если полная решётка, то для того, чтобы подмножество было множеством замкнутых элементов какого-либо оператора , необходимо и достаточно[11], чтобы образовывало муровское семейство на , т.е. множество, содержащее верхнюю границу и точную нижнюю грань любого подмножества множества . Любое такое само является полной решёткой, причём отношение порядка и нижняя операция (инфимум) наследуются из , а верхняя операция (супремум) может отличаться. Когда решётка введена как булева алгебра подмножеств некоторого множества , муровское семейство называют системой замыканий[12] (англ. closure system) множества .

Операторы замыкания на полной решётке сами образуют полную решётку, отношение порядка на которой вводится поточечно: тогда и только тогда, когда .

История[править | править вики-текст]

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

Cм. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Биркгоф, 1984, с. 148.
  2. 1 2 Blyth, 2005, p. 11.
  3. Tarski, 1956.
  4. Brown & Suszko, 1973.
  5. Lloyd, 1987.
  6. Gerla, 2000.
  7. Gierz et al., 2003, Definition O-3.8 (iii), p. 26.
  8. Erné et al., 1993, Definition 2 (1), pp. 104–105: «A closure (respectively, interior) operation».
  9. Blyth, 2005, p. 10.
  10. Blyth, 2005, Theorem 1.7, p. 10.
  11. Биркгоф, 1984, Теорема 1, с. 148.
  12. Биркгоф, 1984, Примечание 1), с. 149.

Литература[править | править вики-текст]

  • 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. — LCCN 66-23707.
    [Русский перевод: Биркгоф, Г. Теория решеток. — М. : Наука. Главная редакция физико-математической литературы, 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. — LCCN 2004-56612.
  • 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. — LCCN 81-1619.
    [Бесплатное электронное издание: 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.
    [Электронные препринты:
  • 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. — Zbl 0075.00702.
  • 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. — JSTOR 1968865.

Ссылки[править | править вики-текст]