Содержание к диссертации
Введение
1 Исходные определения и факты 13
1.1 Нормальные и квазинормальные модальные логики 13
1.2 Выводимость, аксиоматизируемость, независимость 17
1.3 Обобщенные рафинированные шкалы, семантическое задание модальных логик 18
1.4 Логики, не имеющие независимой аксиоматизации 21
2 Некоторые вспомогательные результаты 24
2.1 Некоторые синтаксические аспекты независимой аксиоматизируемости 24
2.2 Конечные множества в рафинированных шкалах 30
2 3 Множества конечной иррефлексивной глубины 33
2 4 Семантические эквиваленты некоторых формул 38
2.5 О свойствах редукции 48
3 Расширения логики Гёделя-Лёба, не имеющие независимой аксиоматизации 53
3.1 Об интервалах логик, верхняя граница которых не имеет непосредственных предшественников 54
3.2 Счётное множество допускающих нормализацию квазинормальных логик, не имеющих независимой аксиоматизации 58
3.3 Счетное множество существенно квазинормальных логик без независимой аксиоматизации 67
3.4 Непосредственные предшественники логик без независимой аксиоматизации 77
Библиография 78
- Обобщенные рафинированные шкалы, семантическое задание модальных логик
- Конечные множества в рафинированных шкалах
- Об интервалах логик, верхняя граница которых не имеет непосредственных предшественников
- Счетное множество существенно квазинормальных логик без независимой аксиоматизации
Введение к работе
Общая характеристика работы
Актуальность темы исследования. В данной работе рассматриваются такие свойства модальных логик, как их независимая аксиоматизируемость и отсутствие у них независимой аксиоматизации.
Модальной логикой будем называть логику в языке классической пропозициональной логики, к связкам которого добавлена одноместная связка , которая в естественных языках обычно соответствует модальностям «необходимо», «известно», «доказуемо» и т. п. Все рассматриваемые в диссертационной работе модальные логики содержат формулы вида (^5 -) ф) -> (Dip -ї Оф) и все тавтологии классической логики. Правило подстановки и правило modus ponens принадлежат к постулированным для этих логик правилам вывода.
Множество формул Г будем называть (абсолютно) независимым в классе некоторых логик, имеющих одинаковые множества правил вывода, если для любой формулы tp из Г верно, что из множества Г \ {tp} не выводима формула tp с использованием лишь постулированных в этом классе логик правил вывода. В том случае, когда класс логик фиксирован, такое можес-тво формул будем называть независимым.
Логику будем называть (абсолютно) независимо аксиоматизируемой, если существует независимое множество формул, аксиоматизирующих эту
логику при постулированных правилах вывода. В том случае, когда логика не является независимо аксиоматизируемой, будем называть ее логикой без независимой аксиоматизации.
Множество формул Г будем называть независимым в классе некоторых логик над множеством формул Д, если для любой формулы у из Г верно, что из множества Г \ {ір} не выводима формула tp с использованием лишь постулированных в этом классе логик правил вывода и формул из множества А.
Аксиоматизацию логики над некоторым непустым множеством формул будем называть относительной аксиоматизацией.
Задача о независимости системы аксиом — это одна из первых задач, возникших при становлении аксиоматического метода в математике. Чтобы оценить важность решения этой задачи, достаточно вспомнить о двухты-сячелетней истории попыток доказательства пятого постулата из аксиоматики геометрии, приведённой в «Началах» Евклида. Независимость аксиоматизации означает наличие некоторого минимального (по включению) списка основных положений теории. Заметим, что для конечно аксиоматизируемых логик такой список всегда существует.
Открытие в 60-х годах прошлого века континуальности числа логик привело к тому, что перед исследователями встала задача изучения свойств бесконечных совокупностей логик и теорий. При этом большинство логик из изучаемых совокупностей обычно не имеют конечной аксиоматизации. Если логика или теория не имеет конечной аксиоматизации, и значит, аксиоматизируется бесконечным множеством аксиом, то её независимая аксиоматизируемость, так же, как и в конечном случае, позволяет утверждать, что для этой логики существует некоторое минимальное (по включению) множество аксиом. Однако в этом случае вполне закономерен вопрос о том, всегда ли логика, не имеющая конечной аксиоматизации, имеет независимую аксиоматизацию!
Вопрос о существовании пропозициональных логик без независимой аксиоматизации впервые был опубликован, видимо, А. И. Циткиным в [1] (проблема 148) для суперинтуиционистских логик. Сходный вопрос для эк-вапиональных теорий был поставлен, например, в [23].
Вопрос о наличии логик и теорий без независимой аксиоматизации тесно связан с вопросом о существовании аксиоматического о'азыеа для данной совокупности логик и теорий (аксиоматическим базисом называют независимое множество формул, позволяющих задавать любые теории или логики из интересующей нас их совокупности). Вопрос о наличии аксиоматических базисов исследовался для эквационапьных и квазиэквациональных логик, а также в области универсальных алгебр. Полученные результаты изложены, в частности, в работах [5], [7], [8], [9], [10], [11], [18], [19], [20] и [23].
Сходный вопрос о базисах допустимых правил вывода в модальных логиках исследовался, например, в [21] и [б].
Если в данной совокупности теорий или логик существуют теории или логики, не имеющие независимой аксиоматизации, то в этом случае очевидно, что аксиоматический базис для данной совокупности логик или теорий отсутствует. Поэтому параллельно поиску аксиоматических базисов шел поиск логик и теорий без независимой аксиоматизации. Так, И. А. Мальцевым в [20] был построен пример квазимногообразия, не имеющего независимой аксиоматизации. Пример конечной решётки, не имеющей независимого базиса тождеств, был построен В. И. Тумановым в [22]. Континуальное множество квазиэквациональных теорий без независимой аксиоматизации было построено А. В. Горбуновым в [18] и позднее И. А. Горбуновым в [12].
В области пропозициональных логик А. В. Чагровым и М. В. Захарьяще-вым в работе [2] были представлены суперинтуиционистская и нормальные модальные логики, не имеющие независимой аксиоматизации. (Модальную логику называем нормальной, если для неё поступировано правило вывода tp/Oip — так называемое правило Геделя.) Пример нормальной модальной
логики без независимой аксиоматизации был также представлен М. Крах-том в [4].
В работе [2] в качестве частичного критерия отсутствия у построенных логик независимой аксиоматизации была использованна лемма, доказанная Ю. Г. Клейманом в [19] для эквациональных теорий групп. В [2] она была пе-реформулированна для случая логик. Некоторые близкие по формулировке к лемме Ю. Г. Клеймана критерии отсутствия независимой аксиоматизации приведены А. В. Горбуновым в [18].
В силу критерия Клеймана, для того, чтобы доказать отсутствие у данной логики независимой аксиоматизации, достаточно показать, что она не имеет непосредственных предшественников по включению над некоторой конечно аксиоматизируемой своей подпогикой. Как известно, решётка нормальных расширений минимальной нормальной модальной логики К вкладывается в решётку ее квазинормальных расширений. (Логику L называем расширением логики Lo, если Lo Q L. Модальную логику называем квазинормальной, если для нее не постулирование правило Гедепя.) Поэтому логика может не иметь непосредственных предшественников в некотором интервале решётки нормальных модальных логик, но иметь непосредственных предшественников в решетке квазинормальных модальных логик. Поскольку при построении в [2] примеров модальных логик, не имеющих независимой аксиоматизации, существенно использовалось правило Гёделя, а вопрос о квазинормальных предшественниках построенных логик не исследовался, то вопрос о налиичии квазинормальных логик без независимой аксиоматизации был сформулирован в [2] в качестве открытого.
В качестве открытого вопроса в этой же работе сформулирован и вопрос об эквивалентности абсолютной независимой аксиоматизируемости логики и относительной независимой аксиоматизируемости логики над её конечно аксиоматизируемой подпогикой.
Кроме того, поскольку лемма Клеймана устанавливает взаимосвязь меж-
ду отсутствием у данной логики свойства независимой аксиоматизируемости и отсутствием у этой логики непосредственных предшественников над некоторой конечно аксиоматизируемой логикой, то представляется вполне разумным рассмотреть вопрос о наличии непосредственных предшественников у логик без независимой аксиоматизации.
Среди модальных логик довольно большой интерес вызывают так называемые логики доказуемости (имеется в виду предикат доказуемости в фомапьной арифметике), к которым относятся, например, логика Геделя-Лёба GL и логика Соловая S, причем логика Соловая является существенно квазинормальной модальной логикой (т. е. в результате замыкания этой логики относительно правила Геделя получается противоречивая логика). Таким образом, представляется вполне естественным решать вопросы, поставленные в [2], в первую очередь для расширений этих логик.
Цель и задачи исследования. Целью данной диссертационной работы является решение вопроса о существовании в решётке квазинормальных расширений логики К логик без независимой аксиоматизации, а также оценка числа таких логик. Выбор в качестве объектов исследования расширений логик доказуемости GL и S отчасти объясняется тем, что, в связи с особой ролью арифметики, это одни из наиболее важных и интересных модальных логик.
Методы исследования. В работе используются семантические и синтаксические методы теории модальных логик.
Научная новизна. В диссертации получены следующие основные новые результаты:
доказано, что абсолютная независимая аксиоматизируемость логики эквивалентна относительной независимой аксиоматизируемости над некоторой её конечно аксиоматизируемой подлогикой;
в расширениях логики GL построено счётное множество нормализуемых1 квазинормальных логик без независимой аксиоматизации;
построено счетное множество логик без независимой аксиоматизации в расширениях логики S;
показано, что логики без независимой аксиоматизации могут иметь непосредственных предшественников над некоторыми конечно аксиоматизируемыми логиками.
Теоретическая и практическая ценность. Результаты, полученные в диссертации, носят теоретический характер. Полученные результаты и методы исследования, разработанные в данной диссертационной работе, могут найти применение в исследованиях свойств неклассических логик2, а также могут быть полезны специалистам, работающим в Московском государственном университете им. М. В. Ломоносова, Новосибирском государственном университете, Тверском государственном университете, Красноярском государственом университете и др.
Апробация. По результатам диссертации делались доклады на семинаре по математической логике Тверского госуниверситета (2001, 2002 гг.), на научной конференции «Российской математике — триста лет» (2002 г., Тверь), на 3-ей (2001 г.) и 4-ой (2003 г.) международных конференциях «Смирновские чтения» (Москва).
Публикации. Основные результаты диссертации опубликованы в [13], [14], и [15]. Кроме того, в [12] представлены результаты, близкие к теме
1 Будем говорить, что квазинормальная логика нормализуема (или допускает нормализацию), если при замыкании её относительно правила Гёделя получаем непротиворечивую логику.
2См , например, [16], [17]
диссертации {касающиеся не логик, а квазимногообразий). С помощью разработанных в диссертации методов получены результаты, представленные в [16] и [17] (сами эти результаты не имеют прямого отношения к теме диссертации).
Структура и объём работы. Диссертация состоит из введения, трех глав и библиографического списка, включающего 23 наименования. Объём работы — 81 страница.
Содержание работы
Во введении обосновывается актуальность темы диссертации, формулируется цель работы, указываются методы исследования. Описываются основные результаты работы и даётся обзор всех разделов диссертации.
В первой главе приводятся основные определения. Определяется синтаксис используемого модального языка и дается определение квазинормальных модальных логик. Определяется реляционная семантика для рассматриваемого класса логик. Вводятся необходимые понятия, в частности, определяется понятие независимой аксиоматизации, приводится критерий независимой аксиоматизируемости.
Во второй главе представлены результаты, носящие в данной работе вспомогательный характер. Выделение этих результатов в самотоятельную главу связано с тем, что необходимость отсылки к ним возникает в процессе доказательтва многих основных результатов.
Некоторые из вспомогательных результатов имеют и самостоятельный интерес. В частности, на открытый вопрос, поставленный в [2], отвечает
Теорема 2.1.1 Если L — независимо аксиоматизируемая логика и Lq — её конечно аксиоматизируемая подлогика, то L независимо аксиоматизируема над Lq.
Из этой теоремы и леммы 2.1 из [2] следует, что относительная независимая аксиоматизируемость над некоторой конечно аксиоматизируемой логикой эквивалентна абсолютной независимой аксиоматизируемости.
В этой же главе приводятся и доказательства тех необходимых «фольклорных» фактов, для которых диссертант не нашёл доказательств в изученной литературе.
В разделе 2.1 этой главы рассматриваются синтаксические аспекты независимой аксиоматизируемости; в разделе 2.2 рассматриваются необходимые свойства конечных множеств в рафинированных шкалах; в разделе 2 3 вводится понятие иррефпексивного слоя в обобщенных шкалах и рассматриваются свойства слоев; в разделе 2.4 приводятся семантические эквиваленты формул, используемых для задания логик в третьей главе; в разделе 2.5 вводится понятие редукции и рассматриваются некоторые необходимые в дальнейшем ее свойства.
В третьей главе строятся примеры квазинормапьных модальных логик, не имеющих абсолютной независимой аксиоматизации в расширениях логик GL и S, строится счётные множества логик без независимой аксиоматизации, а также рассматривается некоторое свойство решёток логик.
Основные результаты третьей главы сформулированны в следующих утверждениях.
Теорема 3.2.1 В расширениях логики GL существует счётное множество допускающих нормализацию квазинормальных логик, не имеющих независимой аксиоматизации.
Теорема 3.3.1 В расширениях логики S существует счётное множество существенно квазинормалъных логик, не имеющих независимой аксиоматизации.
Теорема 3.4.1 Существуют логики без независимой аксиоматизации, у которых имеются непосредственные предшественники в интервалах,
начинающихся с логик, имеющих конечную аксиоматизацию.
Доказательства этих теорем изложены в разделах 3 2, 3.3 и 3.4 соответственно. В разделе 3.1 этой главы описывается некоторый способ построения интервала логик, верхняя граница которого не имеет непосредственных предшественников.
Обобщенные рафинированные шкалы, семантическое задание модальных логик
Рассмотрим пару {WtR)t где W — некоторое непустое множество, элементы которого будем называть мирами или точками, а Л — бинарное отношение на нем, называемое отношением достижимости Элемент d Є W будем называть корнем множества W, если для любого х Є W, кроме, может быть, х = d, существует такое конечное подмножество {UIQ,...,wn} множества W, что шойгої... wn-\Rwn и WQ = d, a wn = х.
Обобщенной шкалой с выделенным корнем будем называть такую четверку 5 = {W, R, П, d), что W — некоторое непустое множество, называемое множеством возможных миров, или точек; R — бинарное отношение (отношение достижимости) на W такое, что множество W имеет корень; П — некоторое подмножество множества 2W, содержащее W и замкнутое относительно булевых операций П, U, и операции , которую определим следующим образом: Q = {х х Є W и Vy Є W(xRy = у Є Q)}, {множество П называем множеством значений шкалы); d — корень множества W. Заметим, что множество її замкнуто также относительно операции О, которую определяют следующим образом: Мир х называем достижимым из мира у, если yRx. Если х — точка и из х не достижима ни одна точка шкалы, то называем х слепой точкой, или слепым миром шкалы $ Будем говорить, что мир х достижим из мира у за п шагов, если существует такая последовательность миров WQRWIR. ..Rwn, что Wo — у и wn = х.
Будем говорить, что мир х достижим из мира у не более чем за п шагов, если он достижим из мира у за m шагов, где т п, и не существует такой последовательность миров WQRWIR ... Rwn+i, что WQ = у иіі)пц = х Шкалу будем называть транзитивной, если транзитивно ее отношение достижимости. Цепью в транзитивной шкале будем называть такое подмножество 53 множества W, что для его элементов выполнено условие линейной упорядоченности: Vx,y Є 23 {х ф у = xRy или yRx). Подмножество 21 С W, называем антицепью в шкале $, если выполняется условие Ух,уЕ%{хфу =$ - xRy и -іуІїх).
Множество У С IV будем называть доелшжгшьш из лира х, если существует такой мир у Є V, что жЯу. Через аг будем обозначать множество всех миров, достижимых из мира а; за один шаг, х\_ = {х} U xf- Анти-цепъ будем называть достижимой из некоторого мира, если из этого мира достижим каждый элемент антицепи1. Ширина транзитивной шкалы —
В связи с тем, что доказательства многих фактов в этой работе возникли из наблюдений за антицепями в шкалах, в целях удобства изложения термин достижимость антицепи из некоторого мира существенно отличается от термина достижимость из некоторого мира множества состоящего из элементов антицепи это мощность максимальной в по включению антицепи. Ширину шкалы $ обозначаем bw.
Пару 9# = (5, і/) будем называть моделью, если J — обобщенная шкала, и — оценка пропозициональных переменных на П, то есть функция, отображающая множество пропозициональных переменных во множество значений шкалы.
Будем говорить, что в точке w шкалы # при оценке v истинна пропозициональная формула tp (обозначим этот факт как w \=" tp, или просто w \= tp, если ясно, о какой оценке идет речь), в следующих случаях:
Будем говорить, что формула р истинна в модели 9ЭТ (пишем 9ЭТ = з), если она истинна в корне шкалы. Формула общезначима на шкале # (пишем 5 = р), если истинна во всякой модели Й7Ї, построенной на шкале 5, то есть если она истинна в корне шкалы при любой оценке.
Множество шкал характеризует логику L, если для любой формулы tp имеет место, что tp є L -й VJ Є ( 1= ). Тот факт, что логика L характеризуется некоторым множеством шкал , будем обозначать следующим образом: L = Log( ). Будем говорить, что шкала # является шкалой логики L, если все формулы логики общезначимы на этой шкале. Множество всех шкал логики L будем обозначать как Fr[L). Класс шкал тотален для некоторого семейства логик, если каждая логика из этого семейства характеризуется множеством шкал из некоторого подкласса класса .
Обобщенную шкалу с выделенным корнем будем называть дифференцированной, если выполнено условие тесной, если выполнено условие рафинированной, если шкала является дифференцированной и тесной. Как известно ([3]), множество всех рафинированных обобщенных шкал с выделенным корнем тотально для множества ExtK. Для удобства изложения здесь мы примем следующее соглашение. Шкалу будем называть корневой, если любой мир шкалы, отличный от корня, достижим из корня шкалы. Далее везде, начиная с раздела 2 4, будут рассматриваться только корневые шкалы. Видимо, первые примеры модальных и суперинтуиционистской логик, не имеющих независимой аксиоматизации, представили М. В, Захарьящев и А. В. Чагров в работе [2]. Одна из предъявленных в [2] нормальных модальных логик находится в расширениях логики S4 и является модальным напарником суперинтуиционистской логики, не имеющей независимой ак сиоматизации. Другая нормальная модальная логика, не имеющая независимой аксиоматизации, аксиоматизируется над логикой.
Конечные множества в рафинированных шкалах
Будем говорить, что шкала & = {W, R, П, {d}} является ch-шкалой, если для любого иррефпексивного мира х шкалы, кроме, может быть корня, и для любого множества Q Є П верно, что из х достижимо не более одного слепого в Q мира, котороый является непосредственным последователем мира х. Лемма 2.4.9 В школе $ = (ТУ,/ї,П,{(і}), имеющей конечную ширину, общезначима формула Пег тогда и только тогда, когда шкала является ch-шкалой.
Доказательство (= ) Пусть шкала 5 не является ch-шкалой. То есть в шкале существует такой иррефлексивный мир х, что dRx и существует такое множество Q Є П, что в этом множестве существует два слепых в нем мира у\ и і/2і которые являются непосредственными последователями мира х. Как следует из леммы 2.2.4, множества {уі} и {уг} принадлежат множеству П. Рассмотрим следующую оценку и: v{p) = {уі,Уг} и y(d) = {уі}. При этой оценке в мирах уі и уі истинны формулы а{р) и П-іа(р), а также у\ \ Я - " (р) и у2 - q - Q(P). Таким образом, в мире х опровергаются формулы 0(q - ia(p)) и ( -» - а{р)). Допустим, что х ft Q2-ia(p). Следовательно, в шкале существует такой мир z, что xRz и z \fc Q-ia(p). То есть существует такой мир w, что zRw и и \= а(р), значит, w = ух или w = у2, но тогда либо х — рефлексивный мир, либо один из миров у\ или У2 не является его непосредственным последователем. Таким образом, х (= n2-ia(p)t и следовательно, в шкале опровергается формула Ua.
Пусть в шкале при некоторой оценке и опровергается формула Ua. Тогда в шкале существует такой мир х, что dRx и х У= а. То есть х \= а2 а{р) и х У= n(q -j. -ia(p)) V \3(- q -j. -na(p)).
Так как x П( / - - a(p)), то существует такой мир /i, что жіїуі и Уі И1 " "(Р)» значит, у\ \= q и у\ \= а{р). Таким образом, в сипу леммы 2.4.5, мир у\ является слепым миром множества v{p). Аналогично, поскольку х 0(-ig —ь a(p)), то существует такой мир у2, что хНуъ и Уч У= Я - 0((р), значит, у2 Я и У2 И а(р)- Таким образом, мир уч также ЯВЛЯетСЯ СЛеПЫМ МИрОМ МНОЖеСТВа v{p) И У\ ф J/2 Поскольку х \= D2-IQ(P), ТО для любого мира w, достижимого из мира х, верно, что w f= П іа[р). Следовательно, миры уі и уг не достижимы ни из одного мира, достижимого из х, откуда получаем, что х — иррефлексивный мир и миры 1/1, у2 являются его непосредственными последователями. Таким образом, в шкале 5 существует такой мир х, что два слепых во множестве v(р) мира являются его непосредственными последователями. Значит, шкала # не является ch-шкалой. Q Лемма 2.4.10 Формула 5П общезначима в шкале 5, если и только если в этой шкале „ = 0 или &п содержит только один мир. Доказательство (=) Пусть в шкале есть два мира ж и у такие, что {# у} Я п и пара множеств {X, Y} — это различающая система для множества {х,у}, причем ІЄІ. Тогда при оценке и(р) = X в корне шкалы опровергается формула 8П. { $=) Пусть в шкале при некоторой оценке опровергается формула 5П. Значит, в шкале есть такой мир х, что х \= D"X Л - Dn l± и при данной оценке х \= р. С другой стороны, в этой шкале существует такой мир у, что у = Оп1 Л -id""1 і. и при данной оценке у р. Таким образом, х ф у и, так как х \= Dnl Л -О1"1! и у f= "! Л -d""1!, то х Є 6„ и у Є 6„. Пусть # = {W, Л, П, {d}} — некоторая шкала. Для любого множества Q Є П областью интроспекции множества Q будем называть множество Q П OQ. Очевидно, что область интроспекции множества Q принадлежит множеству П. Лемма 2.4.11 Формула ref общезначима в шкале J = (W, R, П, {d}) тогда и только тогда, когда для любого множества Q Є П верно, что если корень шкалы принадлежит множеству Q, то он принадлежит и области интроспекции этого множества. Доказательство (= ) Пусть в шкале есть такое множество Q є П, что d Є Q, но d . OQ, то есть мир d является слепым в Q. Тогда при оценке v(p) = W \ Q в шкале опровергается формула ref. ( =) Пусть в шкале при некоторой оценке v опровергается формула ref. Значит в мире d \= Ор и d р. Таким образом, d принадлежит множеству v(p) Є П и не принадлежит его области интроспекции. D 2.5 О свойствах редукции Пусть 5 = {W, R, П, {d}) и 0 = {[/, 5, S, { }) — некоторые шкалы. Будем говорить, что отображение / : W -+ U является редукцией шкалы 5 к шкале 0, а (5 — это редукт Jjf, если выполняются следующие условия: Пусть шкала = {V, S, S, {д}} является редуктом шкалы "$ = (W, R, П, {d}) при некоторой редукпди /, мир х Є V и множество Q є Н, тогда через /-1(аг) будем обозначать множество всех прообразов мира х, при отображении /, а через /-1(0) будем обозначать объединение множеств прообразов всех миров из множества Q. Лемма 2.5.1 Пусть # = {W, R, П, {d}) — некоторая шкала и шкала = (У,,Е, { /}) является ее редуктом при некоторой редукции f. Пусть в обеих шкалах &п ф Яі. Тогда для любого п 1 выполняются следующие условия: /(„) = Єп С V; Доказательство В силу следствия 2.3.1, в любой шкале при любой оценке в каждом мире из множества @п истинна формула ПХЛ- ПП-1Х. Известно (см. [3]), что если шкала является редуктом шкалы J, то для любого мира х и для любой формулы р верно, что если при любой оценке в мире х шкалы $ справедливо х \= tp, то при любой оценке в шкале верно, что в мире f[x) \= tp. Таким образом /(6„) С Є„ С V и 6„ С /_1(6„) С W. Предположим, что f[&n) ф 6П С V. То есть, в шкале существует такой мир it, что и Є б„ и в шкале существует такой мир х Є /_1(u), что х $ 6„ С W. То есть, в мире х Е"Х Л -iD"-1±. Докажем что в этом случае и в мире и )ф П"Х Л - ПК-1Х. В силу сказанного выше /(Пп0) С П"0 Є V и /(П 0) С 0 0 є V, для любого п 1. То есть, если мир х Є W, мир и Є V и /(ж) - и, то ж = D"X u \= D"X.
Об интервалах логик, верхняя граница которых не имеет непосредственных предшественников
Пусть 5 = ОР. Тогда область интроспекции для множества 5 — это множество 5П 05 = OPn OOP. Корень шкалы принадлежит любому множеству ОХ, где X С W, если X не пусто и содержит миры, отличные от корня. В сипу индукионного предположения, корень шкалы принадлежит множеству ОР. Если он не принадлежит множеству OOP, то во множестве ОР нет миров, отличных от корня. Тогда все миры из множества Р, отличные от корня, являются слепыми в этом множестве, и значит, являются непосредственными последователями корня. Таких миров в шкалах нет.
Пусть 5 — Р. В этом случае область интроспекции множества 5 равна множеству Р П ОР. Если корень не принадлежит множеству Р, то он принадлежит множеству Р. Если он при этом не принадлежит области интроспекции этого множества, то он является в нем слепым, и тогда других миров это множество не содержит, что противоречит предыдущей лемме. Случай, когда корень принадлежит множеству Р, очевиден. Таким образом, верна Лемма 3.3.11 Для любого s \ классы шкал Э (1 п и) логики SLS не пусты. Как следует из леммы 2.4.10, для любых п 1 и з 1 формула $п общезначима в любой линейной шкале и любой шкале из класса Э . Тогда, в силу сказанного выше и леммы 3 3.5, для любых 1 і w и в 1, для каждой из логик SL3 выполняются все условия леммы 3.1.2. Значит, с учетом критерия Клеймана и конечной аксиоматизируемости логики К4, верна следующая Лемма 3.3.12 Каждая из логик Sl = Log(Q U Bf,) (s 1) не имеет независимой аксиоматизации. Непосредственным следствием предшествующих лемм является Теорема 3.3.1 В расширениях логики S существует счетное число существенно квазинормальных логик, не имеющих независимой аксиоматизации. Следствие 3.3.3 В расширениях логики GL существует счётное число существенно квазинормальных логик, не имеющих независимой аксиоматизации. Следствие 3.3.4 В расширениях любой модальной логики L такой, что К С і С S, ei/utecmej/em счётное число существенно квазинормальных логик, не имеющих независимой аксиоматизации. В данном параграфе мы рассмотрим вопрос об истинности утверждения, получаемого из критерия Клеймана заменой квантора существования на квантор всеобщности. Критерий Клеймана утверждает, что логики без независимой аксиоматизации не имеют непосредственных предшественников над некоторыми конечно аксиоматизируемыми логиками. Естественно, в этой ситуации поинтересоваться, а не является ли истинным следующее утверждение: логика без независимой аксиоматизации не имеет непосредственных предшественников в любом интервале, начинающемся с логики, имеющей конечную аксиоматизацию. ДЛЯ ТОГО, чтобы ответить на соответствующий вопрос, рассмотрим множество шкал логики М" = L2 = К4 + la + ПЬші + Wi Н-Ьшг- Обозначим через о множество всех шкал этой логики, которые имеют ширину один. Через Э2 обозначим множество всех шкал этой логики, имеющих ширину два. Как доказано выше, все шкалы этого множества имеют бесконечную ирре-флексивную глубину. Поскольку всякая конечная линейная шкала является шкалой Кринке и удовлетворяет всем условиям леммы 3.2.1, класс шкал о содержит все шкалы, предстовляющие собой конечные иррефлексивные цепи произвольной конечной длины. Пусть логика М = М + є„, где п 1. Как следует из следствия 2.3.1, формула єп опровергается в некоторой шкале тогда и только тогда, когда корень шкалы принадлежит множеству 6П (см. раздел 2.3). Таким образом, для любого п 1 формула єп общезначима во всех шкалах множества Э2. Следовательно, для любого п 1 множество шкал ширины два логики Мп совпадает со множеством S)2. Как доказано выше, это множество содержит шкалы из класса Э (непустота этого класса доказана выше). Обозначим через „ (п 0) множество, состоящее из всех шкал множества о, за исключением шкалы, представляющей собой иррефлексивную цепь из п миров. Как следует из леммы 2.4.10, для любого п 1 формула 5п общезначима в любой линейной шкале и любой шкале из класса 1. Таким образом, для любой из логик М" выполняются условия леммы 3.1.2, откуда, в силу тех же причин, что и выше, следует Лемма 3.4.1 Для любого п 0 логика MJJ = Log{n U 3) ) не имеет независимой аксиоматизации. Во множестве о существует шкала, опровергающая формулу єп для некоторого п (где п 1), причем эта шкала единственная. Такой шкалой является иррефлексивная цепь, состоящая из п миров. Значит, ни одна из формул е„ не принадлежит логике ВД. Таким образом, множества шкал логик М и М" отличаются только одной шкалой из множества шкал о, и значит, логика МГ является минимальным по включению расширением логики М. Следовательно, верна следующая Лемма 3.4.2 Для любого п 1 логика М = Io ?(„ U 5) ,) имеет непосредственного предшественника над конечно аксиоматизируемой логикой Ъ/f; таковым является логика М = Log(o U Э ). Таким образом, нами доказана следующая Теорема 3.4.1 Существуют логики без независимой аксиоматизации, у которых имеются непосредственные предшественники в интервалах, начинающихся с логик, имеющих конечную аксиоматизацию.
Счетное множество существенно квазинормальных логик без независимой аксиоматизации
Доказательство (=ф-) Пусть {х$, rci,..., хп} — антицепь в шкале 5. Тогда, в силу леммы 2.2.2 существует множество {QQ, QI, ..., Qn} С П, которое является точной системой для этой антицепи, и гсо Є Qa,Xi & Q\,..., хп Є Qn. Тогда при оценке v{pa) = Qa,v{pi) = Qu---,v{Vn) = Qn в корне шкалы опровергается формула bwn. (-=) Пусть в шкале 5 при некоторой оценке v опровергается формула bwn. Следовательно, в выделенном мире d истинна формула Д Ор,, и 0 Кп значит, множества (ро), v{pi),..., v{Pn) не являются пустыми. С другой стороны, d \ Y ( {Pi Л (Pj V Opj)) V 0(pj Л (pj V Opt))). Значит, для любых і и j (где 0 i 3 n)d\ (0(р, A(j3;V Op,)), следовательно, в любом достижимом из корня мире w верно, что w [= -iplV- (pjVOpJ). Таким образом, для любого мира vt Є v(pt) верно, что vt \= (р3 V Ор3), и значит, vt Є v{p3)f\Uv(p}). Следовательно, для любых г и j (где 0 г j n}u(pt)f\ "(Pj) = 0 и из каждого множества f (рг) не достижимы множества (р,), то есть, например, из множества f(po) не достижимо множество v(pi). Так же, для любых г ж j (где 0 i j 7i)rf (0(р, Л (pt V Opj)), следовательно, в любом достижимом из корня мире w верно, что w \= - р3 V - (pt V Орг), где 0 г j п. Таким образом, для любого мира v3 v{p3) верно, что v3 Н (P»VOp,), и значит, и Є у(р»)ПОі/(р,). Следовательно, для любых г и j (где 0 і j п) из каждого множества и(р3) не достижимы множества {р»), то есть из множества v(p2) не достижимы множества v(po) и f{pi), а из множества v{p\) не достижимо множество и(ра). Таким образом, для любых г к j (где 0 i,j п) из множества f(pj) недостижимо ни одно множество f(pj), если г ф j.
Пусть хо Є V(J)Q),XI Є у(рі),...,хп Є f(pn)i тогда, в силу сказанного выше, множество { 0)— антицепь в шкале J, и значит, ширина шкалы больше.
Транзитивную шкалу будем называть линейной, если множество всех миров шкалы является цепью. Транзитивную шкалу будем называть псевдолинейной, если любая антицепь достижима в ней, разве что, из корня. Таким образом псевдолинейная шкала может ветвиться только в корне. если и только если эта шкала является линейной шкалой или псевдолинейной шкалой с иррефлексивным корнем.
Доказательство (=$ ) Пусть в шкале существуют такие миры х, у и z, что dRz, zRx, zRy, - xRy и - yRx. Пусть QXiQy тесная система для антицепи {х,у} и х Є Qx У Є Qy. При оценке Цро) = Qx, уЬі) = Qv в мире z = ОроЛОрі,ивтожевремя z [ 0(poA(piVOpx)) и: 0(piA(p0vOpo))-Таким образом, при этой оценке d = Obuii. ( =) Пусть в шкале ПРИ некоторой оценке и опровергается формула nfrtt i. Следовательно, в в некотором мире и таком, что dRw опровергается формула Л Ой - V (0(й Л (р, V Ор,)) V 0(р, Л (р, V Ор,))). D t l 0 «J X Следовательно, в мире w истинна формула Д Ор,, и значит, множества 0 1 1 v(po) П wf, v[p\) П u f не являются пустыми. С другой стороны, to V ((Рг Л tPj V Pj)) V 0(pj Л (pt V Op,)). 0 I J 1 Значит, ІУ J (0{po Л (pi V Opi)), следовательно, в любом достижимом из мира w мире v истинна формула -ip0 V - (pi V Opt), Таким образом, для любого мира VQ Є v(po) Л ш верно, что w0 h= "ЧРІ V Opi), и значит, «о Є і (рі)ППе(рі). Следовательно, і/(ро)Пю Пу(рі) = 0 и из множества y(po)nu t не достижимо множество (рі) П ш. Так же, ш (0(pt Л (ро V Орп)), следовательно, в любом достижимом из мира w мире и истинна формула - pi V - (р0 V Ор0). Таким образом, для любого мира v Є v(p\) П wf верно, что v\ \= -i(po V Ор0), и значит, "і (ро) П Qivfpo). Следовательно, из множества f(pi) П twf не достижимо множество v[po) Г) wf. Пусть мир XQ Є f (ро) П wf, МИР #і Є (рі) П twf, тогда, в сипу сказанного выше, множество {л;о,:сі} — антицепь в шкале $, и значит, ширина шкалы не менее двух. Если w ф d, то шкала не является псевдолинейной, а если w = d, то при ширине не менее двух шкала имеет рефлексивный корень. тором мире го истинна формула а{р) тогда и только тогда, когда мир w является слепым во множестве v(p). Доказательство (= ) Пусть в шкале при некоторой оценке v в мире w истина формула рЛ Щ- р). Значит, w Є v{p) и ни один мир из множества у(р) из него не достижим, следовательно, мир ю является слепым миром в i/(p). ( =) Пусть в шкале при некоторой оценке и мир w является слепым в v{p). Тогда он принадлежит множеству i/(p) \ Oi/(p). Значит, он принадле жит множеству Qf(p). Следовательно, w \= р и to \= (—ip). Q Пусть 5 = (W, R, П, {d}} — некоторая шкала и множество Q Є П. Мир w будем называть индифферентным по отношению к множеству Q, если w g Q U OQ. Лемма 2.4.6 В шкале # = {W, Й,П, {d}} при некоторой оценке v в некотором мире w истинна формула 7(р, ц) тогда и только тогда, когда мир w является слепым во множестве v{p) и индифферентным к множеству Доказательство (= ) Пусть в шкале 5 при некоторой оценке v в мире w истина формула а(р) /\0[q), значит, в силу предыдущей леммы 2.4.5 мир w является слепым во множестве v[p)- С другой стороны, w \= -iq Л O(-ig), и значит, го $ v{q) и ни один мир из множества v(q) из него не достижим, следовательно, он является индифферентным миром ко множеству v{q).
