Модальные квазинормальные логики без независимой аксиоматизации тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Горбунов Игорь Анатольевич

Модальные квазинормальные логики

без независимой аксиоматизации

01.01.06 - Математическая логика, алгебра и теория чисел

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Ярославль - 2006

Работа выполнена в Тверском государственном университете

Научный руководитель

доктор физико-математических наук»

профессор Чагров Александр Васильевич

Официальные оппоненты ;

доктор физико-математических наук,

профессор

Захарьящев Михаил Викторович

кандидат физико-математических наук,

доцент

Дудаков Сергей Михайлович

Ведущая

организация — Красноярский государственный университет

2006г. в//час. мин, на за-

Защита состоится ^С/х^-ОлЕ 2

седании диссертационного совета Д 212.002.03 при Ярославском государственном университете имени П. Г. Демидова по адресу: г. Ярославль, ул. Союзная, д. 144.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета имени П.Г.Демидова.

Автореферат разослан с £ » П> (Х^.Гы)^ У 2006г.

Учбыый секретарь диссертационного совета

С. И, Яблокова

Общая характеристика работы

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

Модальной логикой будем называть логику в языке классической Пропозициональной логики, к связкам которого добавлена одноместная связка которая в естественных языках обычно соответствует модальностям «необходимо», «известно», «доказуемо» и т. п. Все рассматриваемые в диссертационной работе модальные логики содержат формулы вида —> ф) —> (□<£> —> Оф) и все тавтологии классической логики. Правило подстановки и правило modus ponens принадлежат к постулированным для этих логик правилам вывода.

Множество формул Г будем называть (абсолютно) независимым в классе некоторых логик, имеющих одинаковые множества правил вывода, если для любой формулы tp из Г- верно, что из множества Г \ {<р} не выводима формула tp с использованием лишь постулированных в этом классе логик правил вывода. В том случае, когда класс логик фиксирован, такое можество формул будем называть независимым.

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

Множество формул Г будем называть независимым в классе некоторых логик над множеством формул Д, если для любой формулы <р из Г верно, что из множества не выводима формула <р с использованием лишь постулированных в этом классе логик правил

вывода и формул из множества Л.

Аксиоматизацию логики над некоторый непустым множеством формул будем называть относительной аксиоматизацией.

Задача о независимости системы аксиом — это одна из первых задач, возникших при становлении аксиоматического метода в математике. Чтобы оценить важность решения этой задачи, достаточно вспомнить о двухтысячелетием истории попыток доказательства пятого постулата из аксиоматики геометрии, приведённой в «Началах» Евклида. Независимость аксиоматизации означает наличие некоторого минимального (по включению} списка основных положений теории. Заметим, что для конечно аксиоматизируемых логик такой список всегда существует.

Открытие в 60-х годах прошлого века континуальности числа логик привело к тому, что перед исследователями встала задача изучения свойств бесконечных совокупностей логик и теорий. При этом большинство логик из изучаемых совокупностей обычно не имеют конечной аксиоматизации. Бели логика или теория не имеет конечной аксиоматизации, и значит, аксиоматизируется бесконечным множеством аксиом, то её независимая аксиоматизируемость, так же, как и в конечном случае, позволяет утверждать, что для этой логики существует некоторое минимальное (по включению) множество аксиом. Однако в этом случае вполне закономерен вопрос о том, всегда ли логика, не имеющая конечной аксиоматиза-цыи, имеет независимую аксиоматизацию?

Вопрос о существовании пропозициональных логик без независимой аксиоматизации впервые был опубликован, видимо, А. И. Цит-ниным в [1] (проблема 148) для суперинтуиционистских логик. Сходный вопрос для эквационалышх теорий был поставлен, например, в [22].

Вопрос о наличии логик а теорий без независимой аксиоматизации тесно связан с вопросом о существовании аксиоматического базиса для данной совокупности логик и теорий (аксиоматическим базисом называют независимое множество формул, позволяющих задавать любые теории или логики из интересующей нас их совокупности). Вопрос о наличии аксиоматических базисов исследовался для эквациональных и квазиэквапиональных логик, а также я области универсальных алгебр. Полученные результаты изложены, в частности, в работах [4], [6], [7], [8], [9], [10]Д17], [18], [19] и [22].

Сходный вопрос о базисах допустимых правил вывода в модальных логиках исследовался, например, в [20] и [5].

Если в данной совокупности теорий или логик существуют теории или логики, не имеющие независимой аксиоматизации, то в этом случае очевидно, что аксиоматический базис для данной совокупности логик или теорий отсутствует. Поэтому параллельно поиску аксиоматических базисов шёл поиск логик и теорий без независимой аксиоматизации. Так, И. А. Мальцевым в (19} был построен пример квазимногообразия, не имеющего независимой аксиоматизации. Пример конечной решётки, не имеющей независимого базиса тождеств, был построен В. И. Тумановым в [21]. Континуальное множество квазиэхвациональных теорий без независимой аксиоматизации было построено А. В. Горбуновым в [17] и позднее И. А. Горбуновым в [11].

В области пропозициональных логик А. В. Чагровым и М. В. За-харьящевым в работе [2] были представлены суперинтуиционистская и нормальные модальные логики, не имеющие независимой ак*

. ■■ 1 ■

сиоматизации. (Модальную логику называем нормальной, если для нее постулировано правило вывода — так называемое правило Гёделя.) Пример нормальной модальной логики без независимой

аксиоматизации был также представлен М. Крахтам в [3].

В работе [2] в качестве частичного критерия отсутствия у построенных логик независимой аксиоматизации была использован-на лемма, доказанная Ю. Г. Клейманом в [18] для эквацистальных теорий групп. В [2] она была переформулированна для случая логик. Некоторые близкие по формулировке к лемме Ю. Г. Клеймана критерии отсутствия независимой аксиоматизации приведены А. В. Горбуновым в [17].

В силу критерия Клеймана, для того, чтобы доказать отсутствие у данной логики независимой аксиоматизации, достаточно показать, что она не имеет непосредственных предшественников по включению над некоторой конечно аксиоматизируемой своей подлогикой. Как известно, решётка нормальных расширений минимальной нормальной модальной логики К вкладывается в решётку ее квазинормальных расширений. (Логику Ь называем расширением логики Ьъ, если ¿о С Ь. Модальную логику называем квазинормллъмой, если для нее не пост?лированно правило Гёделя.) Поэтому логика может не иметь непосредственных предшественников в некотором интервале решётки нормальных модальных логик, но иметь непосредственных предшественников в решётке квазинормальных модальных логик. Поскольку при построении в [2] примеров модальных логик, не имеющих независимой аксиоматизации, существенно использовалось правило Гёделя, а вопрос о квазинормальных предшественниках построенных логик не исследовался, то вопрос о налиичии квазинормальных логик без независимой аксиоматизации был сформулирован в [2] в качестве открытого.

В качестве открытого вопроса в этой же работе сформулирован и вопрос об эквивалентности абсолютной независимой аксиоматизируемости логики и относительной независимой аксиоматизируемости

в

логики над её конечно аксиоматизируемой подлогшсой.

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

Среди модальных логик довольно большой интерес вызывают так называемые логики доказуемости (имеется в виду предикат доказуемости в фомальной арифметике), к которым относятся, например, логика Гёделя-Лёба и логика Соловая в, причём логика Соловая является существенно квазинормальной модальной логикой (т. е. в результате замыкания этой логики относительно правила Гёделя получается противоречивая логика). Таким образом, представляется вполне естественным решать вопросы, поставленные в [2], в первую очередь для расширений этих логик. *

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

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

Научная новизна« В диссертации получены следующие основные новые результаты:

• доказано, что абсолютная независимая аксиоматизируемость логики эквивалентна относительной независимой аксиоматизируемости вал некоторой её конечно аксиоматизируемой под-логикой;

• в расширениях логики в! построено счётное множество нормализуемых1 квазинормальных логик без независимой аксиоматизации;

• построено счётное множество логик без независимой аксиоматизации в расширениях логики Б;

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

Теоретическая и практическая ценность. Результаты, полученные в диссертации, носят теоретический характер. Полученные результаты и методы исследования, разработанные в данной диссертационной работе, могут найти применение в исследованиях свойств неклассических логик3, а также могут быть полезны специалистам, работающим в Московском государственном университете им. М. В. Ломоносова, Новосибирском государственном университете, Тверском государственном университете, Красноярском государственам университете и др.

1 Будем говорить, что квазинормальвая логика нормализуема (или Запускает

нормализацию), «ели при замыкании её относительно правила Гёдел» получаем непротиворечивую логику,

3См., например, (15), [16].

Апробация. По результатам диссертации делались доклады на семинаре по математической логике Тверского госуниверситета (2001, 2002 гг.), на научной конференции «Российской математике — триста лет» (2002 г., Тверь), на 3-ей (2001 г.) и 4-сЙ (2003 г.) международных конференциях «Смирновские чтения» (Москва).

Публикации. Основные результаты диссертации опубликованы в [12], [13], и [14]. Кроме того, в [11] представлены результаты, близкие к теме диссертации (касающиеся не логик, а квазимногообразий). С помощью разработанных в диссертации методов получены результаты, представленные в [15] и [16] (сами эти результаты не имеют прямого отношения к теме диссертации).

Структура в объём работы. Диссертация состоит из введения, трёх глав и библиографического списка, включающего 23 наименования. Объём работы — 81 страница.

Во введении обосновывается актуальность темы диссертации, формулируется цель работы, указываются методы исследования. Описываются основные результаты работы и даётся обзор всех разделов диссертации.

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

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

Некоторые из вспомогательных результатов имеют и самостоятельный интерес. В частности, на открытый вопрос, поставленный в [2], отвечает

Теорема 2.1-1 Если Ь — независимо аксиоматизируемая логик а и Ьо — ее конечно аксиоматизируемая подлогика, то Ь независимо аксиоматизируема над1,а.

Из этой теоремы И леммы 2.1 из [2] следует, что относительная независимая аксиоматизируемость над некоторой конечно аксиоматизируемой логикой эквивалентна абсолютной независимой аксиоматизируемости.

В этой же главе приводятся и доказательства тех необходимых «фольклорных» фактов, для которых диссертант не нашёл доказательств в изученной литературе.

В разделе 2.1 этой главы рассматриваются синтаксические аспекты независимой аксиоматизируемости; в разделе 2.2 рассматриваются необходимые свойства конечных множеств в рафинированных шкапах; в разделе 2.3 вводится понятие иррефлексивного слоя в обобщённых шкалах и рассматриваются свойства слоев; в разделе 2.5 приводятся семантические эквиваленты формул, используемых для задания логик в третьей главе; в разделе 2.6 вводится понятие редукции и рассматриваются некоторые необходимые в дальнейшем её свойства.

В третьей главе строятся примеры квазинормалышх модаль-

ных логик, не имеющих абсолютной независимой аксиоматизации в расширениях логик СЬ и 8, строится счётные множества логик без независимой аксиоматизации, а также рассматривается некоторое свойство решёток логик.

Для формулировки основных результатов третьей главы нам понадобятся следующие определения.

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

Основные результаты третьей главы сформулированны в следующих утверждениях.

Теорема 3,2.1 Б расширениях логики СЬ существует счётное множество допускающих нормализацию квазинормалъных логик, не имеющих независимой аксиоматизации.

Теорема 3.3.1 В расширениях логики Б существует, счетное множество существенно квазинормалъных логик, не имеющих независимой аксиоматизации.

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

Доказательства этих теорем изложены в разделах 3.2, 3.3 и 3.4 соответственно. В разделе 3.1 этой главы описывается некоторый способ построения интервалов логик, верхняя граница каждого из которых не имеет непосредственных предшественников.

Литература

[1] Логическая тетрадь // Новосибирск., 1986.

[2] Chagrov А. V., Zakharyaschev M.V. On the Independent Axiomatizability of Modal and Intermediate Logics // Jomal Logic Computat., vol.5, No.3,1995, p.287-302.

[3] Kracht M. Tools and Techniques in Modal Logic // Studies in Logic and the Foundations of Mathematics, No. 142, Elsevier, Amsterdam, 1999.

[4] McKenzie R. Equation base* for lattice theories // Math. Scand., No. 27, 1970, p. 24-38.

[5] Rybakov V., Kiyatkin V., Terziler M. Independent Bases for Rules Admissible in Pretabular Logics // Logic Jomal of the IGPL., vol. 7, No. 2,1999, p. 253-266.

[6] Белкин В. П. О квазитоокдестеаж некоторых конечных алгебр // Математические заметки, т. 22, N 3, 1S77, с. 335-338.

[7] Белкин В. П. Квазитождесгпва конечных колец и решёток // Алгебра и логика, т. 17, N 3,1978, с. 247-259.

[8] Будкин A.Q. Независимая аксиоматизируемость квазимногообразий групп Ц Математические заметки, т.31, N6, 1982, с. 817-826.

[9] Будкин А.И. Независимая аксиоматизируемость кеазимно-гообраэий обобщённо разрешимых групп // Алгебра и логика, т. 25, N3, 1986, с. 249-266.

[10] Будкин А. И. Независимая аксиоматизируемость квазимногообразий универсальных алгебр // Математические заметки, т. 56, N4,1994, с. 28-37.

[11] Горбунов И. А. О кеазимногообразиях, не имеющих независимого базиса // Учёные записки Тверского государственного университета, т. 6. Тверь, Издательство Тверского госуниверситета, 2000, с. 13-17.

[12] Горбунов И. А. О независимой аксиоматизируемости ке ази-нормальных модальных логик // Смирновские чтения. III Международная конференция. М., Издательство Института философии РАН, 2001, с. 29-31.

[13] Горбунов И. А. О логиках tt теориях не имеющих независимых аксиоматизаций // Российской математике — триста лет. Материалы юбилейной научной конференции 24-25 октября 2001 года. Тверь, Издательство Тверского госуниверситета, 2002, с. 95-102.

[14] Горбунов И. А. О независимой аксиоматизируемости расширений логики Р. Соло* ал Ц Смирновские чтения. IV Международная конференция. М., Издательство Института философии РАН, 2003, с. 31-32.

[15] Горбунов И. А, Разрешимое расширение логики доказуемости, не разрешимое в конечном fj Международная конференция «Колмогоров и совершенная математика» М., Издательство МГУ, 2003, с. 704-705.

[16] Горбунов И. A. A Decidable Modal Logic that is Undecidable on Finite Frames fj Международная конференция «Computer

Science Applications of Modal Logic» M., Издательство МЦН-МО, 2005, с. 15-15.

[17] Горбунов A.B. Алгебраическая теория квазимногообраэий jj Новосибирск., Научная книга, 1999.

[18] Клейман Ю.Г. О некоторых вопросах теории многообразий групп Ц Известия АН СССР. Сер. матем., т.47, 1983, с.37-74.

[19} Мальцев А. И. Универсально аксиоматизируемые подклассы локально конечных классов моделей // Сибирский математический журнал., т. VIII, N 5,1968, с. 1005-1014.

[20] Рыбаков В. В. Базисы допустимых правил вывода S4 « Int // Алгебра и логика, т. 24,1985, с. 55-68.

[21] Туманов В. И. О конечных ршётках,ке имеющих независимого базиса квазитождеств // Математические заметки, т. 36, N5,

1984, с. 625-633. *

[22] Янов Ю. И. Тождества в конечньгх алгебрах// Проблемы кибернетики, N8, 1962, с. 75-87.

Содержание

Введение

Общая характеристика работы.

Содержание работы.

1 Исходные определения и факты

1.1 Нормальные и квазинормальные модальные логики.

1.2 Выводимость, аксиоматизируемость, независимость.

1.3 Обобщенные рафинированные шкалы, семантическое задание модальных логик

1.4 Логики, не имеющие независимой аксиоматизации.

2 Некоторые вспомогательные результаты

2.1 Некоторые синтаксические аспекты независимой аксиоматизируемости

2.2 Конечные множества в рафинированных шкалах.

2 3 Множества конечной иррефлексивной глубины.

2 4 Семантические эквиваленты некоторых формул.

2.5 О свойствах редукции.

3 Расширения логики Гёделя-Лёба, не имеющие независимой аксиоматизации

3.1 Об интервалах логик, верхняя граница которых не имеет непосредственных предшественников.

3.2 Счётное множество допускающих нормализацию квазинормальных логик, не имеющих независимой аксиоматизации

3.3 Счетное множество существенно квазинормальных логик без независимой аксиоматизации.

3.4 Непосредственные предшественники логик без независимой аксиоматизации.

Общая характеристика работы

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

Модальной логикой будем называть логику в языке классической пропозициональной логики, к связкам которого добавлена одноместная связка □, которая в естественных языках обычно соответствует модальностям «необходимо», «известно», «доказуемо» и т. п. Все рассматриваемые в диссертационной работе модальные логики содержат формулы вида □(</? -> ф) -4 (□</? ^Ф) и все тавтологии классической логики. Правило подстановки и правило modus ponens принадлежат к постулированным для этих логик правилам вывода.

Множество формул Г будем называть (абсолютно) независимым в классе некоторых логик, имеющих одинаковые множества правил вывода, если для любой формулы ip из Г верно, что из множества Г \ {ip} не выводима формула ip с использованием лишь постулированных в этом классе логик правил вывода. В том случае, когда класс логик фиксирован, такое можес-тво формул будем называть независимым.

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

Множество формул Г будем называть независимым в классе некоторых логик над множеством формул Д, если для любой формулы ц> из Г верно, что из множества Г \ {ip} не выводима формула ip с использованием лишь постулированных в этом классе логик правил вывода и формул из множества Д.

Аксиоматизацию логики над некоторым непустым множеством формул будем называть относительной аксиоматизацией.

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

Открытие в 60-х годах прошлого века континуальности числа логик привело к тому, что перед исследователями встала задача изучения свойств бесконечных совокупностей логик и теорий. При этом большинство логик из изучаемых совокупностей обычно не имеют конечной аксиоматизации. Если логика или теория не имеет конечной аксиоматизации, и значит, аксиоматизируется бесконечным множеством аксиом, то её независимая аксиоматизируемость, так же, как и в конечном случае, позволяет утверждать, что для этой логики существует некоторое минимальное (по включению) множество аксиом. Однако в этом случае вполне закономерен вопрос о том, всегда ли логика, не имеющая конечной аксиоматизации, имеет независимую аксиоматизацию?

Вопрос о существовании пропозициональных логик без независимой аксиоматизации впервые был опубликован, видимо, А. И. Циткиным в [1] (проблема 148) для суперинтуиционистских логик. Сходный вопрос для эк-вациональных теорий был поставлен, например, в [23].

Вопрос о наличии логик и теорий без независимой аксиоматизации тесно связан с вопросом о существовании аксиоматического базиса для данной совокупности логик и теорий (аксиоматическим базисом называют независимое множество формул, позволяющих задавать любые теории или логики из интересующей нас их совокупности). Вопрос о наличии аксиоматических базисов исследовался для эквациональных и квазиэквациональных логик, а также в области универсальных алгебр. Полученные результаты изложены, в частности, в работах [5], [7], [8], [9], [10], [11], [18], [19], [20] и [23].

Сходный вопрос о базисах допустимых правил вывода в модальных логиках исследовался, например, в [21] и [6].

Если в данной совокупности теорий или логик существуют теории или логики, не имеющие независимой аксиоматизации, то в этом случае очевидно, что аксиоматический базис для данной совокупности логик или теорий отсутствует. Поэтому параллельно поиску аксиоматических базисов шел поиск логик и теорий без независимой аксиоматизации. Так, И. А. Мальцевым в [20] был построен пример квазимногообразия, не имеющего независимой аксиоматизации. Пример конечной решётки, не имеющей независимого базиса тождеств, был построен В. И. Тумановым в [22]. Континуальное множество квазиэквациональных теорий без независимой аксиоматизации было построено А. В. Горбуновым в [18] и позднее И. А. Горбуновым в [12].

В области пропозициональных логик А. В. Чагровым и М. В. Захарьяще-вым в работе [2] были представлены суперинтуиционистская и нормальные модальные логики, не имеющие независимой аксиоматизации. (Модальную логику называем нормальной, если для неё постулировано правило вывода tp/Oip — так называемое правило Геделя.) Пример нормальной модальной логики без независимой аксиоматизации был также представлен М. Крах-том в [4].

В работе [2] в качестве частичного критерия отсутствия у построенных логик независимой аксиоматизации была использованна лемма, доказанная Ю. Г. Клейманом в [19] для эквациональных теорий групп. В [2] она была пе-реформулированна для случая логик. Некоторые близкие по формулировке к лемме Ю. Г. Клеймана критерии отсутствия независимой аксиоматизации приведены А. В. Горбуновым в [18].

В силу критерия Клеймана, для того, чтобы доказать отсутствие у данной логики независимой аксиоматизации, достаточно показать, что она не имеет непосредственных предшественников по включению над некоторой конечно аксиоматизируемой своей подлогикой. Как известно, решётка нормальных расширений минимальной нормальной модальной логики К вкладывается в решётку ее квазинормальных расширений. (Логику L называем расширением логики Lq, если Lq С 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 страница.

1. Логическая тетрадь // Новосибирск., 1986.

2. Chagrov А. V., Zakharyaschev М. V. On the Independent Axiomatizability of Modal and Intermediate Logics // Jornal Logic Computat., vol.5, No.3, 1995, p. 287-302.

3. Chagrov A. V., Zakharyaschev M. V. Modal Logic. Oxford University Press, 1997.

4. Kracht M. Tools and Techniques in Modal Logic // Studies in Logic and the Foundations of Mathematics, No. 142, Elsevier, Amsterdam, 1999.

5. McKenzie R Equation bases for lattice theories // Math. Scand., No. 27, 1970, p. 24-38.

6. Rybakov V., Kiyatkin V., Terziler M. Independent Bases for Rules Admissible in Pretabular Logics // Logic Jornal of the IGPL., vol. 7, No. 2, 1999, p.253-266.

7. Белкин В. П. О квазитождествах некоторых конечных алгебр // Математические заметки, т. 22, N 3, 1977, с. 335-338.

8. Белкин В. П. Квазитождества конечных колец и решеток // Алгебра и логика, т. 17, N3, 1978, с. 247-259.

9. Будкин А И. Независимая аксиоматизируемость квазимногообразий групп // Математические заметки, т. 31, N6, 1982, с. 817-826.

10. Будкин А. И. Независимая аксиоматизируемость квазимногообразий обобщенно разрешимых групп // Алгебра и логика, т. 25, N3, 1986, с. 249-266.

11. Будкин А. И. Независимая аксиоматизируемость квазимногообразий универсальных алгебр // Математические заметки, т. 56, N4,1994, с. 28-37.

12. Горбунов И. А. О квазимногообразиях, не имеющих независимого базиса II Ученые записки Тверского государственного университета, т. 6. Тверь, Издательство Тверского госуниверситета, 2000, с. 13-17.

13. Горбунов И. А. О независимой аксиоматизируемости квазинормальных модальных логик // Смирновские чтения. III Международная конференция. М., Издательство Института философии РАН, 2001, с. 29-31.

14. Горбунов И. А. О логиках и теориях не имеющих независимых аксиоматизаций II Российской математике — триста лет. Материалы юбилейной научной конференции 24-25 октября 2001 года. Тверь, Издательство Тверского госуниверситета, 2002, с. 95-102.

15. Горбунов И. А. О независимой аксиоматизируемости расширений логики Р. Соловая // Смирновские чтения. IV Международная конференция. М., Издательство Института философии РАН, 2003, с. 31-32.

16. Горбунов И. А. Разрешимое расширение логики доказуемости, не разрешимое в конечном II Международная конференция «Колмогоров и соверменная математика» М., Издательство МГУ, 2003, с. 704-705.

17. Горбунов И. A. A Decidable Modal Logic that is Undecidable on Finite Frames // Международная конференция «Computer Science Applications of Modal Logic» M., Издательство МЦНМО, 2005, с. 15-15.

18. Горбунов А. В. Алгебраическая теория квазимногообразий // Новосибирск., Научная книга, 1999.

19. Клейман Ю.Г. О некоторых вопросах теории многообразий групп // Известия АН СССР. Сер. матем., т. 47,1983, с. 37-74.

20. Мальцев А. И. Универсально аксиоматизируемые подклассы локально конечных классов моделей // Сибирский математический журнал., т. VIII, N5, 1968, с. 1005-1014.

21. Рыбаков В. В. Базисы допустимых правил вывода S4 и Int // Алгебра и логика, т. 24, 1985, с. 55-68.

22. Туманов В. И. О конечных ршётках,не имеющих независимого базиса квазитождеств // Математические заметки, т. 36, N5, 1984, с. 625633.

23. Янов Ю.И. Тождества в конечных алгебрах // Проблемы кибернетики, N8, 1962, с. 75-87.