Модальные логики топологических пространств Шехтман, Валентин Борисович

Введение к работе

Актуальность темы. В настоящей диссертации исследуются аксиоматические теории топологических пространств, основанные на модальної"! логике.

Изучение логики модальностей было начато еще в античные времена и на протяжении многих столетий велось в рамках гуманитарных дисциплин (главным образом, в философии и лингвистике). Первые модально-логические исчисления были сформулированы только в начале 20-го века (К. Льюис, 1918), а осознание теории модальностей с математической точки зрения началось лишь в 1940-1950-е гг., благодаря работам А. Тарского, Дж. Маккннсн, Б. Йонссона, С. Крнпке н др. Появление многочисленных приложений модальных логик: в информатике, теории искусственного интеллекта, математической лингвистике, а также в основаниях математики, - привело в конце 1970-х гг. к стремительному росту этой области, который продолжается и сегодня. Современная модальная логика представляет собой сложившуюся математическую дисциплину с собственным кругом задач и методов; она оказывает влияние на развитие математической логики в целом и связана с рядом других областей математики, в особенности с универсальной алгеброй, теорией категорий и общей топологией.

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

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

С одной стороны, в теоретико-множественной топологии активно применяется аксиоматическая теория множеств; на этом пути был получен ряд глубоких результатов о независимости в топологии (и в частности, в дескриптивной теории множеств)¹,².

¹ И. Юхас. Результаты о непротиворечивости в топологии. В кн. Справочная книга по математической логике, подред.Дж. Барвайса. т.2: Теория множеств, с. 213-234. М. "Наука", 1982.

- В. Г. Кановей. Проективная иерархия Н.Н. Лузина: современное состояние теории. В кн. Справочная книга по математической логике, под ред. Дж. Барвайса, т. 2: Теория множеств, с. 273-364. М. "Наука", 1982.

С другой стороны, А. Робинсоном³ была поставлена проблема создания "топологической теории моделей", аналогичной теории моделей классической логики первого порядка. Принципиальная трудность здесь состоит в том, что топологические структуры невозможно определить средствами классической логики первого порядка, не прибегая к понятию множества, поскольку для задания топологического пространства нужно говорить и о точках, и о множествах точек. Поэтому приходится использовать либо аксиоматическую теорию множеств, либо теории второго порядка⁴,⁵. Достоинством теорий второго порядка является богатство их выразительных возможностей, а недостатком — алгоритмическая неразрешимость.

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

Сама идея построения простых исчислений "алгебраического типа", в которых можно доказывать топологические теоремы, принадлежит К.Куратовскому⁶. Предложенное им исчисление, как позднее заметили А.Тарский, М. Стоун, Тан, полностью эквивалентно известной модальной логике S4 Льюиса:

Аксиомы Куратовского Аксиомы S4

і(ХіпХ2) = ІХ-|ПІХ2 П(рілр2)~ПрілПр2

іХіеііХі QpinDDpi

XisXi Пріорі

І1 = 1 ПТ-Т
(і - оператор внутренности, 1 - все пространство; D - модальная связка
"необходимо", Т - константа "истина", г> — импликация, эквиваленция).

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

³ A. Robinson. Metamathematical problems. Journal о/Symbolic Logic, v. 38 (1973), 159-171.

⁴ J. Flum, M. Ziegler. Topological model theory. Lecture Motes in Mathematics, v. 769. Springer-Verlag,

Berlin, 1980.

⁵ J. Flum. Model theory of topological structures. In: Quantifiers: Logics, Models and Computation, v. I,

pp. 297-312. Ed. M. Krynicki et al. Kluwer Academic Publishers, 1995.

⁶ С Kuratowstci. Sur I'operation A de l'Analysis Situs. Fundamenta Matliematicae, v.3 (1922), 181-199.

Как явно отмечает автор, в этой работе принята аксиоматическая точка зрения: выводятся следствия из сформулированных им четырех аксиом и аксиом "алгебры логики" (т.е. булевых).

соответствуют формулы в модальном языке: тождество t = r, где t, г — термы, можно переписать в виде формулы логики высказываний, если заменить символы операций и константы Г\, и, -, 1, І соответственно на логические связки и константы л, v, -і, Т, , знак равенства - на ~, а предметные переменные Xi, Х2,... - на пропозициональные переменные pi, р2,... Обратно, каждой модальной формуле А отвечает тождество tA = 1 , где 1д - соответствующий топобулев терм. Это соответствие позволяет интерпретировать модальные формулы в топологических пространствах.

Систематическое изучение топобулевых алгебр было начато Маккинси и Тарским⁷. Здесь одной из центральных задач стало исследование многообразий, или, двойственным образом, эквациональных теорий топобулевых алгебр. Благодаря известной теореме Линденбаума, эти теории в точности соответствуют модальным Э4-логикам (т.е. нормальным расширениям S4).

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

С помощью перевода Гёделя - Тарского в логике S4 интерпретируется интуиционистская логика высказываний⁸. Этот перевод ставит в соответствие каждой интуиционистской формуле А модальную формулу т(А), которая получается навешиванием D на все подформулы А. Поэтому интуиционистские формулы также могут интерпретироваться в топологических пространствах. Посредством перевода т, суперинтуиционистские логики (т.е. расширения интуиционистской логики) оказываются фрагментами S4-noraK и потому могут рассматриваться в контексте общей теории модальных логик. Известно, что множество всех суперинтуиционистских логик (а следовательно, и всех 34-логик) имеет мощность континуума⁹.

Основным теоретико-модельным инструментом в исследовании модальных н суперинтуиционистских логик стала реляционная семантика Крипке. Ее можно рассматривать как частный случай окрестностной (топологической) семантики. В семантике Крипке формулы интерпретируются в реляционных системах (шкалах Крипке). Для случая S4-noniK — это квазиупорадоченные множества; они соответствуют топологическим пространствам, в которых пересечение любого

⁷ J.C.C. McKinsey, A. Tarski. The algebra of topology. Annals ofMatltematics, v. 45 (1944), 141-191.

⁸ J.C.C. McKinsey, A. Tarski. On closed elements in closure algebras. Annals ofMatltematics, v. 47 (1946),

122-162. ' В. А. Янков. Построение последовательности сильно независимых суперинтуиционистских исчислений. Доклады АН СССР, т. 181 (1968), N1, 33-34.

семейства открытых множеств открыто. Реляционные структуры обычно проще описываются, чем топологические; в частности, к ним применимы методы классической теории моделей. К середине 1990-х гг. исследование модальных S4-логик средствами-реляционной семантики бьио, в основном, завершено. В этой области был получен ряд глубоких результатов о полноте, разрешимости, первопорядковой определимости, допустимости правил вывода, интерполяционном свойстве и т.д.; большинство этих результатов изложено в недавней монографии.¹⁰

Напротив, свойства произвольных топологических моделей модальных логик после классических работ Маккинси — Тарского изучались недостаточно. Так, было доказано, что в топологической семантике не все логики полны¹¹, а из полноты в топологической семантике не следует полнота в реляционной семантике¹². Однако аналогичные проблемы для суперинтуиционистских логик, поставленные А.В. Кузнецовым в 1974 г.¹³, решены не полностью (эти вопросы исследуются и в настоящей диссертации, см. далее). С другой стороны, совсем недавно было установлено, что степени неполноты модальных логик в обеих семантиках совпадают¹⁴. Почти полвека оставались открытыми и вопросы Маккинси — Тарского о свойствах оператора деривации в евклидовых пространствах, которые решаются в данной диссертации.

В последние годы исследования модальных логик топологических пространств заметно оживились, благодаря развитию прикладных разделов математической логики. В этой связи полезным оказывается эквивалентное определение топологической семантики в терминах "возможных миров", предложенное Р. Монтегю¹⁵ и Д. Скоттом¹*: модальная формула оценивается как истинная или ложная в зависимости от точки наблюдения ("возможного мира"), причем формула DA истинна в мире t, если А истинна в некоторой окрестности t. Таким образом,

A. Chagtov, М. Zakharyaschev. Modal logic. Oxford University Press, 1997.

M. Gerson. The inadequacy of the neighbourhood semantics for modal logic. Journal of Symbolic

Logic, v. 40 (1975), No.2, 141-147.

M. Gerson. An extension of S4 complete for the neighbourhood semantics but incomplete for the

relational semantics. Studia Logica, v. 34 (1975), 333-342. А.В. Кузнецов. О суперинтунционистских логиках. Математические исследования, т. 10

(1975), вып. 2, 150-157. L. Chagrova. On the degree of neighborhood incompleteness of norma! modal logics. In: Advances in

Modal Logic, volume 1. M.Kiacht, M. de Rijke, H. Wansing and M. Zakharyaschev, eds. CSLI

Publications, 1998, pp. 63-72. Автор отмечает неожиданность данного результата, поскольку

топологическая и реляционная семантика неэквивалентны. R. Montague. Pragmatics. In: Contemporary Philosophy. A survey. I. Ed. R. Klibansky. Florence, 1968,

pp. 102-122. D. Scott. Advice on modal logic. In: Philosophical Problems in Logic. Some Recent Development, ed.

K. Lambert Reidel, 1970, pp. 143-172.

"необходимость" понимается в топологической семантике как локальная истинность. Аналогичное описание реляционной семантики было дано С. Крипке¹⁷: формула DA истинна в мире t, если А истинна во всех мирах, достижимых из 1.

Из приложений топологической семантики модальных логик можно отметить лингвистический анализ локативов, времени и вида¹⁸ , начинающееся в последнее время использование модальных логик в релятивистской теории пространства-времени¹⁹, и особенно в задачах искусственного интеллекта. По мнению специалистов, можно говорить уже о развитии новой области — пространственной логики. Целью прикладных исследований здесь является создание логических исчислений, которые могут моделировать естественные качественные рассуждения о пространственных конфигурациях. Подобные задачи возникают в разнообразных информационных системах, работающих с графическими данными: географических, медицинских, биологических и т.д.²⁰,-¹. Исследователи в этой области постепенно перешли от классических теорий первого порядка к модальным логикам с топологической семантикой. Так, например, "исчисление связности областей" (RCC), введенное Д. Рэнделлом, 3. Кюи и А. Коном,²- оказалось интерпретируемым в модальной логике с локальной и универсальной модальностями,²³ которая изучается в настоящей диссертации.

В свою очередь, развитие приложений вызвало в последние годы новый интерес к общим проблемам топологической семантики модальных логик. Так, в недавней работе М. Аиелло — Й.Ван Бентема²⁴ изучается понятие бискмуляции для топлогических моделей и обсуждаются различные варианты модальных исчислений для описания топологии и геометрии. Как отмечают авторы (р. 39), "в целом, в старой доброй 'топологической интерпретации' обнаруживается гораздо больше, чем кажется на первый взгляд, лишь только мы начинаем обращаться к ее следствиям..."²⁵

¹⁷ S. Kripke. Semantical analysis of modal logic , I. Zeitschtift fur mathematische Logikund Crundlagen

der Mathematik, v. 9 (1963), 67-96.

¹⁸ L. Aqvist, F. Gunther. Fundamentals of a theory of verb aspect and events. In: Studies in Formal

Semantics, ed. F.Giinther and C.Rohrer. North Holland, 1978, pp. 167-200.

¹⁹ R. Goldblatt. Orthogonality and space-time geometry. Springer, !991.

²⁰ A. G. Cohn. Calculi for qualitative spatial reasoning. In: Artificial Intelligence and Symbolic
Matliemarical Computation. Lecture Notes in Computer Science, V. 1138, pp. 124-143. Springer, 1996.

²¹ D.S. Weld, 1. De Kleer, eds. Readings in qualitative reasoning about physical systems. Morgan
Kaufman, San Mateo, 1990.

~ D.A. Randell, Z. Cui, A.G. Cohn. A spatial logic based on regions and connection. In: Proceedings of the 3^rJ International Conference on Knowledge Representation and Reasoning, pp. 165-176. Morgan Kaufman, San Mateo, 1992.

²³ B. Bennett. Modal logics for qualitative spatial reasoning. Logic Journal of the [GPL , v.4 (1996), No. 1,

23-45.

²⁴ M. Aiello, J. Van Benthem. Logical patterns in space. Manuscript, 1999. .

²⁵ В оригинале; "All in all, there is much more to the good old 'topological interpretation' than meets the

Цель работы. Исследование модальных и суперинтуиционистских логик высказываний с точки зрения топологической (окрестностнои) семантики: изучение свойств полноты н сильной полноты (компактности); построение и исследование модальных логик, описывающих конкретные виды топологических пространств: связные метрические, евклидовы, нульмерные и др. — в языках с локальной и универсальной модальностями; с деривационной модальностью; с временными и топлогическими модальностями.

Научная новизна. Все результаты диссертации явлются новыми. Основные результаты диссертации —следующие:

1. В классе расширений логики Гжегорчика построены модальные логики,
неполные в топологической семантике.

2. Доказана неэквивалентность топологической семантики и семантики Крипке
для сулеринтуиционистских логик.

1. Доказано, что для всех модальных логик, содержащих К4, и для всех суперинтуиционистских логик из полноты по Крипке следует сильная полнота в топологической семантике.

2. В языке с операторами локальной и универсальной истинности построена система аксиом и доказана финитная аппроксимируемость логики произвольного связного плотного в себе сепарабельного метрического пространства.

3. Построены системы аксиом и доказана финитная аппроксимируемость деривационных логик для пространств Rⁿ и для нульмерных плотных в себе подмножеств действительной прямой.

4. В языке с временными операторами и оператором локальной истинности построены системы аксиом и доказана финитная аппроксимируемость для логики рациональной прямой и логики класса всех линейных порядков.

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

eye, once one starts following through its implications..."

Теоретическая и практическая ценность. Диссертация имеет теоретический характер, ее результаты могут применяться в дальнейших исследованиях по модальной и алгебраической логике, теории моделей, обшей топологии, универсальной алгебре. Полученные результаты могут быть полезны и при решении прикладных задач описания пространственной информации.

Результаты работы могут найти применение в исследованиях, проводимых в Математическом институте РАН, его Петербургском отделении. Институте математики Сибирского отделения РАН; Московском, Тверском, Новосибирском, Красноярском государственных университетах, Институте прикладной математики РАН, Вычислительном центре РАН, других университетах и математических институтах.

Апробация работы. Результаты диссертации докладывались в течение 19S0 - 1999 гг. на научно-исследовательском семинаре кафедры математической логики и теории алгоритмов механико-математического факультета МГУ, на научном семинаре Института проблем передачи информации РАН, научных семинарах университетов Амстердама (Нидерланды), Лейпцига (Германия), Милана, Сиены (Италия), Хиросимы (Япония). Они были представлены и доложены на научных конференциях: 6-й Международный Конгресс по логике, философии и методологии науки (Ганновер, 1979), 8-я Всесоюзная конференции по логике и методологии науки (Паланга, 1982), Всесоюзный коллоквиум по логике и лингвистике (Телавн, 1983), Европейский логический коллоквиум (Берлин, 1989), Итальянская конференция по логике и философии науки (Виареджо, 1990), Конференция по истории логики (Краков, 1990), Совещание проекта MEDLAR (Лондон, 1991), Европейский логический коллоквиум (Клермон-Ферран, 1994), 1-я и 2-я Международные конференции по модальной логике (Берлин, 1996; Уппсала, 1998), Александровские чтения (Москва, 1999).

Публикации. Основное содержание диссертации опубликовано в 8 работах; их список приведен в конце автореферата.

Структура и объем диссертации. Диссертация объемом 187 страниц состоит из введения, шести глав, разбитых на 42 параграфа, списка литературы и указателя терминов. Библиография содержит 126 наименований, включая 21 работу автора.