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

/"» ,4 / / О, л

вв-У/

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 510.64

ТИШКОВСКИЙ ДМИТРИЙ ЕВГЕНЬЕВИЧ

АЛГЕБРАИЗАЦИЯ СУПЕРИНТУИЦИОНИСТСКИХ ПРЕДИКАТНЫХ ЛОГИК

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

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

Научный руководитель доктор физико-математических наук, профессор Л. Л. Максимова

Новосибирск 1999

Содержание

Введение 3

1. Дедуктивные системы для суперинтуиционистских предикатных логик 16

1.1. Суперинтуиционистские предикатные логики и теории 16

1.2. Суперинтуиционистские дедуктивные системы ... 20

1.3. Адекватность суперинтуиционистских дедуктивных систем суперинтуиционистским логикам..............24

1.4. Суперинтуиционистские дедуктивные системы как дедуктивные системы полимодальных логик .... 37

1.5. Свойства логик и свойства дедуктивных систем . . . 45

2. Квазицилиндрические алгебры 50

2.1. Определение и примеры..................................50

2.2. Размерность элементов ..............................56

2.3. Алгебры локально-конечной размерности............60

2.4. Означивания формул....................................62

2.5. Алгебры Расёвой—Сикорского..........................65

2.6. Алгебры Линденбаума—Тарского......................73

2.7. Теорема о полноте........................................78

3. Алгебраические эквиваленты некоторых свойств логик 80

3.1. Дизъюнктивное свойство................................80

3.2. Экзистенциальное свойство..............................82

3.3. Свойство Бета............................................83

3.4. Проективное свойство Бета..............................88

3.5. Интерполяционное свойство............................90

3.6. Соотношение свойств дедуктивных систем и свойств логик ......................................................96

Литература 98

Введение

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

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

Хорошим подспорьем в изучении свойств решётки однотипных логик является наличие единой семантики для этих логик. Так, например, решётке пропозициональных суперинтуиционистских логик соответствует решётка многообразий псевдобулевых алгебр. К сожалению, в случае предикатных логик такого удачного соответствия нет. Известно [25], что существует континуум суперинтуиционистских предикатных логик, которые неполны относительно семантики шкал Крипке, и существует континуум суперинтуиционистских предикатных логик, которые неполны относительно семантики псевдобулевых моделей Е. Расёвой и Р. Си-корского [8].

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

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

Алгебраическая логика берёт начало с работы Тарского [32]. В этой работе Тарский ввёл понятие алгебры пропозициональных формул. Он определил отношение = на множестве формул условием

А = В «$=>• Ь А э I? и \-BdA

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

Позднее метод Тарского был применён к алгебраизации пропозициональных модальных, суперинтуиционистских и многих других логик. Большой вклад в развитие алгебраческих методов исследования неклассических логик был внесён Е. Расёвой и Р. Си-корским [29,8]. Сам Тарский возглавил обширную исследовательскую программу по алгебраизации классической логики 1-го порядка [17]. Позднее эта программа была подхвачена различными школами алгебраической логики, среди которых следует особо отметить венгерскую школу [11,12,18,19,23,24,31].

В 1989 году метод Тарского был обобщён Блоком и Пигоц-ци [13] на случай алгебраизации произвольных пропозициональных логик. В указанной работе использовалось представление логик дедуктивными системами, и было введено понятие алгебраиз-уемости пропозициональной дедуктивной системы. Было доказано, что алгебраизуемой дедуктивной системе соответствует единственная эквивалентная алгебраическая семантика — некоторое квазимногообразие алгебр. В диссертации также используется представление предикатных логик дедуктивными системами.

Как отмечено в [13, Приложение С], алгебраизация предикатных логик является более сложной задачей, чем алгебраизация пропозициональных логик. Поясним это на следующих простых

примерах. Рассмотрим правило введения квантора всеобщности

А Э В(х) Ь Л э УхВ(х).

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

УхА(х) Э А(у),

где х не попадает в область действия квантора по переменной у в А(х), имеет недостаток той же природы. Действительно, выражения А{х) и А(у) формально различны, но их нельзя трактовать как различные переменные для формул. Наиболее полно сложность предикатных логик отражена в правиле подстановки формул 1-го порядка (см. параграф 1.1). Это правило, по сравнению с пропозициональным случаем, существенно усложнено условиями, которые не допускают коллизий переменных при использовании правила подстановки.

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

Существует несколько решений этой проблемы [13, Приложение С], [23]. Первое состоит в том, чтобы строить дедуктивную систему для предикатной логики в языке, в который непосредственно введены символы для всевозможных операций замены переменных. Следуя по этому пути при алгебраизации классической логики 1-го порядка, приходим к понятиям полиадических и квазиполиадических алгебр [16].

Второе решение состоит в том, чтобы выразить операцию замены переменных в самом языке 1-го порядка. Это становится возможным, если в языке 1-го порядка присутствует символ равенства Тогда указанную выше аксиому можно заменить, например, на VхА(х) э Зх{х & у а Следуя в этом на-

правлении, при алгебраизации классической логики 1-го порядка получим многообразие цилиндрических алгебр [17].

Если же в языке нет символа равенства, но есть бесконечное количество предметных переменных, то существует промежуточное решение — выразить операции замены нескольких переменных через операции замены одной переменной. Исходя из этой предпосылки, алгебраизуя классическую логику предикатов, получим многообразие (цилиндрических) алгебр Пинтера (с подстановками) [27]. Указанные алгебры являются наиболее простыми алгебрами, которые годятся в качестве алгебраического эквивалента для классической логики 1-го порядка [23]. В данной работе мы используем именно такой подход.

Несмотря на множество подходов к алгебраизации предикатных логик (см. [12,17,23]), суперинтуиционистские предикатные логики до сих пор не были алгебраизованы.

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

если логика Ь полна относительно класса К алгебр, то Ь имеет свойство V тогда и только тогда, когда К обладает свойством А1д(Г).

Через А1д(V) здесь обозначен алгебраический эквивалент свойства V, формулируемый на языке алгебр и гомоморфизмов.

Большой вклад в теорию алгебраизации свойств пропозициональных логик внесён Максимовой Л. Л. В работах [5-7,21,22] найдены и изучены алгебраические эквиваленты для многих свойств пропозициональных суперинтуиционистских и мономодальных логик. В частности, алгебраизованы дизъюнктивное свойство, свойство Бета, проективное свойство Бета и интерполяционное свойство пропозициональных суперинтуиционистских логик. Близкие результаты в области алгебраической характери-зации свойств определимости Бета и интерполяционного свойства различных логик были получены сравнительно недавно учеными

венгерской школы [18-20,31].

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

В последнее время в алгебраической логике классическую логику 1-го порядка связывают с пропозициональными полимодальными логиками [24,33]. Во многом подобная связь мотивирована представлением логики дедуктивной системой, которая в случае предикатных логик может трактоваться и как дедуктивная система для пропозициональных полимодальных логик. В работе также исследуется этот вопрос. Устанавливается связь между суперинтуиционистскими предикатными логиками и пропозициональными интуиционистскими полимодальными логиками [1]. Параллельно алгебраизации свойств суперинтуиционистских предикатных логик, проведённой в диссертации, могут быть алгебраизова-ны и соответствующие свойства интуиционистских полимодальных логик, такие как дизъюнктивное свойство, свойство Бета, проективное свойство Бета, интерполяционное свойство выводимости и импликативное интерполяционное свойство.

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

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

В диссертации использованы семантические методы теории не-

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

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

Основные результаты диссертации:

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

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

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

Работа носит теоретический характер. Ее методы и результаты могут использоваться специалистами в области неклассических логик и теоретической информатики, для чтения лекций и спецкурсов в Московском, Новосибирском, Красноярском, Новосибирском педагогическом и др. госуниверситетах.

Основные результаты, полученные в диссертации, докладывались на:

• заседаниях семинаров "Алгебра и логика" и "Нестандартные логики" кафедры алгебры и математической логики механико-математического факультета НГУ,

• русско-японском коллоквиуме по нестандартным логикам и логическим аспектам информатики N81/95 (Иркутск, 1995),

• международной конференции "Универсальная алгебра и теория решеток" (Сегед, Венгрия, 1996),

• международной конференции " Логика, алгебра и информатика", посвященной памяти Елены Расевой (Варшава, 1996),

• международной конференции "Мальцевские чтения" (Новосибирск, 1998),

• международных научных студенческих конференциях "Студент и научно-технический прогресс" (Новосибирск, 1993,1995,1996),

• логическом коллоквиуме ЬС'98 (Прага, 1998).

Результаты диссертации опубликованы в девяти работах автора [34-42].

Остановимся более подробно на содержании работы. В главе 1 исследуются синтаксические аспекты суперинтуиционистских предикатных логик.

В параграфе 1.1 приводятся необходимые определения и формулировки известных теорем о суперинтуиционистских предикатных логиках. В частности, определяется правило подстановки формул 1-го порядка.

В параграфе 1.2 вводятся понятие суперинтуиционистской дедуктивной системы и понятие вывода формулы 1-го порядка в дедуктивной системе. Следует отметить, что язык дедуктивных систем заранее фиксируется, и все рассматриваемые в работе дедуктивные системы записаны в едином пропозициональном языке. Пропозициональные переменные этого языка служат буквами для обозначения произвольных формул 1-го порядка. Поэтому формулы языка дедуктивных систем названы схемами формул, что согласуется с известными понятиями схемы аксиом и частного случая схемы аксиом [3]. Обычным образом определяется понятие вывода схемы формул в дедуктивной системе.

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

адекватной логике, если данная логика совпадает с множеством формул, выводимых в данной дедуктивной системе. Возникает вопрос: для всякой ли суперинтуиционистской предикатной логики существует ей адекватная дедуктивная система? В параграфе 1.3 изучается подобное отношение между дедуктивными системами и суперинтуиционистскими предикатными логиками и теориями. Приводятся примеры логик и адекватных им дедуктивных систем. Всякой суперинтуиционистской предикатной логике можно поставить в соответствие наибольшую суперинтуиционистскую дедуктивную систему .05(1,), включив в схемы аксиом все схемы формул, любые частные случаи которых принадлежат логике Ь. Доказана важная теорема о существовании для произвольно взятой суперинтуиционистской предикатной логики адекватной ей дедуктивной системы:

ТЕОРЕМА 1.21. Для любой предикатной суперинтуиционистской логики Ь дедуктивная система ПБ(Ь) адекватна Ь.

Ключевую роль в доказательстве указанной теоремы играет построение трансляции А Ф[А] формул 1-го порядка в схемы формул, обладающей двумя "хорошими" свойствами. Во-первых, одним из частных случаев схемы Ф[А] является сама формула А. Во-вторых, если формула А принадлежит логике Ь, то все частные случаи схемы Ф[А] также принадлежат данной логике Ь.

В параграфе 1.4 проводится параллель между суперинтуиционистскими дедуктивными системами и интуиционистскими полимодальными пропозициональными логиками. Отмечается, что язык рассматриваемых дедуктивных систем является пропозициональным языком полимодальных логик с модальностями V*, 3* и (г,] < и). Доказывается, что множества схем формул, выводимых в расширениях некоторой фиксированной базовой дедуктивной