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

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

Содержание
Введение
1 Логики конечных областей
1.1 Отсутствие свойства Бета у интуиционистской логики
конечных областей
1.2 Расширения логики «7, не имеющие интерполяционного
свойства
1.3 Отсутствие свойства Бета у логики
1.4 Континуальные семейства суперинтуиционистских логик
без свойства Бета
1.5 Логики без равенства
2 Фрагмент интуиционистской логики конечных областей без дизъюнкции и квантора существования
2.1 Элиминация сечения в исчислении
2.2 Полнота исчисления относительно шкал Крип-
ке с конечными областями
2.3 Интерполяция и свойство Бета
Библиография

Введение
Теория неклассических логик — одна из важных областей современной логики. Особую роль среди многочисленных неклассических логик играет интуиционистская логика, возникшая в связи с критикой классической логики с позиций конструктивизма. На базе этой логики построены интуиционистская математика и конструктивная математика, основанные на конструктивном понимании существования математических объектов (см., например [1], [5]).
Формализация интуиционистской логики в виде исчисления, данная Гейтингом в 1930 году, подтолкнула интерес математиков к формулированию и изучению интуиционистских теорий с позиций классической математики. Основы такого подхода заложены в работах Геделя [17], Маккинси и Тарского [21], Новикова [8]. В данной работе мы также придерживаемся точки зрения классической математики при изучении неклассических логик.
Позднее возникли и изучались расширения интуиционистской логики. Классы формул, содержащие интуиционистское исчисление и замкнутые относительно выводимости, получили название суперинтуи-ционистских логик.
Доказанная Янковым в 1968 году континуальность семейства су-перинтуиционистских логик показывает невозможность эффективного описания всех суперинтуиционистских логик. Поэтому для изучения указанных семейств, как правило, выделяют классы логик, обладающих тем или иным свойством. К таким свойствам относятся, например, полнота по Крипке, разрешимость, дизъюнктивное, экзистенцио-нальное, интерполяционное свойство Крейга и свойство Бета.
Интерполяционная теорема для классической логики предикатов впервые была доказана В. Крейгом [14] в 1957 году. В 1962 году Шютте [27] доказал интерполяционную теорему для интуиционистской логики предикатов синтаксическим методом. Другие доказательства этого факта даны в работах Т. Нагашимы [23], Д. Габбая [16], X. Оно[24]. Д. Габбай в [16] представил семантическое доказательство интерполяционного свойства для некоторых расширений интуиционистской логики предикатов.

Л. Л. Максимова [6] доказала в 1977 году, что непротиворечивых пропозициональных суперинтуиционистских логик, имеющих интерполяционное свойство, только семь. Однако вопрос, поставленный X. Оно в [25], о том, какие предикатные суперинтуиционистские логики имеют интерполяционное свойство, остается открытым. Там же X. Оно полагает, что первым шагом к решению этой проблемы может явиться следующая задача: привести примеры предикатных логик, имеющих интерполяционное свойство. Естествен также и обратный вопрос, т. е. вопрос о примерах логик, не имеющих интерполяционного свойства. При этом можно отметить, что если предикатная логика имеет интерполяционное свойство, то ее пропозициональная часть тоже должна иметь его и, значит, все логики, имеющие интерполяционное свойство, должны содержаться в классе предикатных расширений вышеупомянутых семи пропозициональных логик.
В 1960 году Г. Крайзель [20] установил, что все пропозициональные суперинтуиционистские логики имеют свойство Бета. Для предикатных суперинтуиционистских логик такое утверждение не имеет места. Так, например, Ю. Гуревич в [18] доказал, что классическая логика конечных областей не обладает свойством Бета. Однако примеров логик без свойства Бета, промежуточных между интуиционистской и классической предикатными логиками, до настоящего времени не было известно.
Средствами интуиционистской логики свойство Бета можно вывести из интерполяционного свойства тем же способом, как это сделано в [14]. Отсюда получаем, что отсутствие у логики свойства Бета влечет отсутствие интерполяционного свойства.
Данная работа посвящена изучению интерполяционного свойства и свойства Бета для интуиционистской логики конечных областей с равенством Jfd, характеризуемой всеми интуиционистскими шкалами Крипке, у которых все предметные области конечны, и близкой к ней логики J*fd, характеризуемой всеми шкалами Крипке, у которых предметные области всех немаксимальных миров конечны. Поскольку справедливость указанных свойств существенно зависит от наличия в языке символа равенства (см., например, [11]), параллельно рассматривается также логика без равенства.

Л*-д (где Аг,А3-г — соответствующие сегменты области з-.); в противном случае берем элемент так, чтобы мощности
сегментов А?г,А?% были не меньше чем 2п~к~1 (мы можем это сделать, так как по предположению мощность сегмента А~г не меньше чем 2п~к). Получаем, что для / = 0,1 либо мощность сегмента равна мощности сегмента Л_г, либо мощности сегментов Л*7,Лур не меньше чем 2п~к~1.
Таким образом, после п ходов получаем соответствие а -Н- а
2. Допустим, существует такое предложение Ф сигнатуры {<}, что в любой модели М типа +4 имеет место следующая эквивалентность: предложение Ф истинно во всех мирах модели М тогда и только тогда, когда предметные области всех миров модели М имеют четные мощности. Пусть Я-б. (Ф) = п. Тогда возьмем такие модели мим2 типа +4, что мощность области Ои,1 равна 2П, мощность области Ои,2 равна 2п + 1, т.е. мощность предметной области минимального мира модели М четная, а мощность предметной области минимального мира модели М2 нечетная. Тогда для любого к < со формула Ф истинна в мире ги1к, но не истинна в мире П). Это противоречит первому пункту леммы.
3. Допустим, существует формула С (х) сигнатуры {<} такая, что для любой модели М типа +4, для любого мира множество элементов предметной области этого мира, на которых формула С{х) истинна, совпадает со множеством четных элементов этой области. Рассмотрим предложение Ф = Уж (3у (ж < у) —У Зг (ж < гк.С (г))) и докажем, что оно противоречит второму пункту леммы.
Если предложение Ф истинно во всех мирах модели М, возьмем в качестве ж предпоследний элемент предметной области какого-нибудь мира модели М. Так как в предметной области этого мира и у всех последующих миров есть элемент у такой, что ж < у (в качестве у можно взять последний элемент области), то по предложению Ф должен существовать такой элемент г, что выполнено