Интерполяционные свойства в слабо тразитивных модальных логиках

• Автор: Карпенко, Анастасия Валерьевна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Новосибирск
• Количество страниц: 86 с.

Оглавление
Введение
1 Предварительные сведения
§1.1 Модальные логики. Интерполяционные свойства
§1.2 Модальные алгебры. Амальгамируемость
§1.3 Шкалы Крипке. Теорема о представлении
2 Простые слабо транзитивные модальные алгебры
§2.1 Простые транзитивные модальные алгебры
§2.2 Простые слабо транзитивные модальные
алгебры
§2.3 Шкалы АТ: описание и морфизмы
§2.4 Структура вложений простых ПТ-алгебр
§2.5 Классификация многообразий ПТ-алгебр
3 Интерполяция и амальгамируемость
§3.1 Необходимые условия амальгамируемое
§3.2 Амальгамируемые многообразия ПТ-алгебр
§3.3 Слабая интерполяция над К4 и
§3.4 Дедуктивное интерполяционное свойство в расширениях
логики неравенства
§3.5 Критерий слабой интерполяции над тК

Введение
Диссертационная работа посвящена изучению интерполяционных свойств модальных логик.
Первые модальные системы были построены К. Льюисом в начале XX века [12]. Многие известные на данный момент модальные системы ведут начало от таких областей знания, как философия, основания математики, информатика, когнитология и математическая лингвистика.
Наблюдающийся в последнее время интерес к математической логике обусловлен связью между этой логикой и логическими основаниями программирования. Благодаря данной связи стало возможным применение методов и результатов модальной логики в развитии теории программирования.
Алгебраическая семантика, а также реляционная семантика модальной логики, построенная С. Крипке [10], открыли возможность для изучения всей совокупности систем модальной логики. К этому направлению относятся исследования В. Блока, JI. JI. Максимовой, К. Сегербер-га, Е. Расевой, В. Раутенберга, В. В. Рыбакова, С. Томасона, К. Файна,
В. Б. Шехтмана, J1. Л. Эсакиа и многих других.
В нашей работе будут рассматриваться как расширения известных модальных систем К4, 54 и 55, так и менее известных wKA и DL. Логики 54 и 55 были получены при характеризации различных вариантов интерпретации оператора □ («необходимость»), в то же время системы К и wK4 появились из чисто технических соображений.
Логика wKA изучалась рядом авторов, среди которых отметим Л. Л. Эсакиа [37]. В работе [37] изучение логики wКА связано с рассмотрением шкал Крипке со слабо транзитивным отношением достижимости, удовлетворяющим условию (ж -f- zhxRijhyRz xRz). Данная логика

является промежуточной между минимальной модальной логикой К и логикой КА. Эсакиа нашел топологическую семантику для wKA и дал определение алгебр с деривацией, образующих алгебраическую семантику этой модальной системы. В диссертации мы будем называть данные алгебры слабо транзитивными.
Заключительный параграф работы [37] посвящен рассмотрению логики KS (Krister Segerberg). Данная логика построена К. Сегербергом в работе [20] при аксиоматизации модальной системы, характеризуемой шкалами (X, R), в которых отношение достижимости R совпадает с отношением неравенства. Логика KS позднее изучалась рядом авторов, среди которых можно отметить В. Горанко [8] и М. Де Рийке [5], и получила название логики неравенства DL (Difference logic). Кроме того, было отмечено (см., например, [11]), что добавление к другим модальным операторам модальности неравенства существенно увеличивает выразительность языка.
Как правило, при изучении модальных логик выделяются классы логик, обладающих теми или иными свойствами. К таким свойствам можно отнести полноту относительно семантики некоторого типа, разрешимость, финитную аппроксимируемость, табличность, дизъюнктивное и интерполяционные свойства. Под разрешимостью свойства Р мы будем понимать существование алгоритма, позволяющего по выбранной формуле А определить, обладает ли логика с аксиомой А этим свойством. Остановимся подробнее на последнем из перечисленных свойств, которому посвящена данная диссертационная работа.
Интерполяционная теорема была доказана В. Крейгом в 1957 г. для классической логики предикатов [4]. Это доказательство послужило поводом для изучения интерполяции в различных формальных теориях. В классической логике предикатов интерполяционная теорема Крейга имеет ряд эквивалентных формулировок, однако для модальных логик данные формулировки становятся неэквивалентными. В этой связи было сформулировано несколько основных вариантов интерполяционного свойства: интерполяционное свойство Крейга CIP, дедуктивное ин-терполяцинное свойство IPD, ограниченное интерполяционное свойства

Теорема 2.4. Слабо транзитивная алгебра 21 является простой тогда и только тогда, когда выполнено

1, при х = 1;
О, при х ф 1.
Доказательство. (4=) По предложению 1.2 множество V всех таких а £ 21, что а ~ 1, является открытым фильтром.
По лемме 2.6 в 21 существует в точности два открытых фильтра, тогда V совпадет либо с VI = {1}, либо с У2 = 21. Значит, возможных
конгруэнций окажется ровно две: 1) а ~ а; 2) а ~ Ъ для всех а, Ъ £ 21.
(=>) Нужно показать, что
1, х = 1,
О, хф1.
Заметим, что в слабо транзитивной алгебре И1 = 1&П I = 1, □ 0 — 0. Предположим, что Шж определен не так, как указано выше, то есть найдется у Е 21 такой, что у ^ 1 и И)/ / 0. Так как у ф 1, то (Ну = □у&у ф 1.
Обозначим □ у = Ь, тогда
□ 6 = Ь&пб — □ □ у — □у&у&п(пу&у) =
= □ у & у & □ □ у & □ у = □ у&у & □ □ у =
= □ у & □ □ у = □ у = Ь,
так как в слабо транзитивной алгебре □ у ^ □ у.
Таким образом, мы нашли Ш-открытый элемент Ь, отличный от 0 и 1. Тогда по лемме 2.5 отображение Н(а) = Ь&а будет гомоморфизмом 21 на интервал (Ь]я, причем /г(0) = 0&Ь = 0,Н(Ь) — Ь8гЬ = Ь, /г(1) — 1&6 = Ь, то есть /г разделяет 0 и Ь и склеивает Ь и 1. Таким образом, мы нашли собственный нетривиальный гомоморфизм, что противоречит простоте алгебры. □