Логика доказуемости и доказуемостно-интуиционистская логика

• Автор: Муравицкий, Алексей Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Кишинев
• Количество страниц: 110 c. : ил

ГЛАВА I. ЛОГИКА ДОКАЗУЕМОСТИ

§ I. Интуиционистская логика как фрагмент логики

доказуемости

§ 2. О расширениях логики доказуемости

§ 4. Класс 2. Д магариевых алгебр

ГЛАВА 2. ВОПРОСЫ МОДЕЛИРУЕМОСТИ ДОКАЗУЕМОСТНО-ИНТУИЦИОНИСТСКОЙ ЛОГИКИ

§ I. Определимость доказуемостно-интуиционистской

логики классом конечных шкал

§ 2. Немоделируемое расширение доказуемостно-интуиционистской логики

ГЛАВА 3. СООТВЕТСТВИЕ РАСШИРЕНИЙ ЛОГИКИ ДОКАЗУЕМОСТИ РАСШИРЕНИЯМ ДОКАЗУЕМОСТНО-ИНТУИЦИОНИСТСКОЙ ЛОГИКИ

§ I. Предварительные замечания о свойствах решеток

§ 2. Алгебраическая семантика
§ 3. Изоморфизм решеток и )£14
§ 4. Другие функториальные свойства изоморфизмар
ГЛАВА 4. СУПЕРИНТУИЦИОНЙСТСКИЕ ЛОГИКИ,АППРОКСИМИРУЕМЫЕ
АЛГЕБРАМИ С ОБРЫВОМ УБЫВАЮЩИХ ЦЕПЕЙ
§ I. Предварительные замечания
§ 2. Реляционная семантика
Литература

После того как в начале XX в., Л.Брауэр подвергнул критике классическую логику (признаваемую математиками до тех пор как достаточно надежную основу для обоснования математических доказательств), в частности отвергая ее закон исключенного третьего,в математике стало складываться интуиционистское направление, а применявшиеся в не умозаключения стали формировать интуиционистскую логику. Как ичисление последняя в 1930 г. была сформулирована А.Рейтингом. И хотя согласно интуиционистской традиции никакое формальное оформление интуиционистской логики "никогда не дает полного и определенного ее описания, так же как недостижима полная теория других явлений" £3], тем не менее под интуиционистской логикой принято понимать ту совокупность логических законов, которая была аксиоматизирована Рейтингом.
Желая лучше понять интуиционистскую критику или учесть ее, исходя из иных, чем интуиционисты (например, Брауэр (см.
[33 Д, с. 111-112)) философских предпосылок, были предприняты попытки описания интерпретаций законов интуиционистской логики, учитывающих эту критику. При этом большое значение, по-видимому,придавали интуиционистской идее о том, что всякое математическое высказывание "всегда требует проведения некоторого математического построения с некоторыми заданными свойствами",называемого доказательством этого высказывания,и что данное высказывание" можно утверждать,коль скоро это построение выполнено” [3]. Одной из первых была попытка В.Н.Колмогорова [603, предложившего истолкование интуиционистской логики как логики задач и связавшего истинность матеметическо-го высказывания с задачей его доказательства, а ложность его -с задачей его опровержения. Возникшие позже теория алгоритмов и конструктивное направление в математике связали закон исключенного третьего с задачей построения алгоритма, позволяющего установить истинность или ложность любого высказывания (т.е. доказать его или опровергнуть). При этом наличие алгоритмически неразрешимых массовых проблем подкрепляло интуиционистское сомнение в истинности этого закона.
Уточнения семантически неточной колмогоровской логики задач привели к логике рекурсивной реализуемости С.Клини и Дж. Роуоза (см. [5,703 ) и логике финитных задач Ю.Т.Медведева [183, отличными от интуиционистской и несравнимым между собой. Эти обстоятельства, а также сложность задания последних логик (особенно логики рекурсивной реализуемости) вынуждали к поиску новых интерпретаций,а наличие континуума логик,промежуточных между интуиционалистской логикой высказываний и классической, указывало на возможную сложность такого поиска. Между тем, выявленные трудности привели к идеи аппроксимации интуиционистской логики высказываний логиками из этого континуума, что породило устойчивый интерес ко всей совокупности этих логик. Результаты исследований их были подытожены в [58, 83.
Иное истолкование интуиционистской логики в 1933 г. было предложено К.Геделем [513. Остановимся на этом подходе подробнее, используя более распространенные обозначения чем в [51].С каждой из рассматриваемых нике пропозициональных логик мы бу-

Заметим, что для любых и любогоебХ имеет мес-

(38>
Это очевидно для случая <^<+уа . Если же °«Х<*./*>, то, используя $££)с. л^се) и предполагая по индуктивному предположению, что (38) верно для случая «:<У, получаем:
Хр *$(£),'г* <£%(£), Хс4<£.<$(А£.).
Теперь легко заметить, что отношение < является ирреф-лексивным на множестве V , так как, во-первых, о<<^+°<и, во-вторых, если »«А* +е*, то, используя (37),$<£)£43СО и (38), получаем: (£), хые4$С£), Я/ь^дСе), X* (4£)*4%Ы).
Противоречие.
Отношение на множестве V , определенное как
ы —Р *=7 =*<• £ ИЛИ Ы.-=1/Ь
является отношением частичного порядка.
Рассмотрим частично упорядоченное множество связанную с ним А -псевдобулеву (по лемме 2.1.6) алгебру <У,<> . Определим отображение Ч5 алгебры 01 в алгебру <Х г^так:
Ч: £ <~+{°<6-Ух«е№}для £ бЛ'.
Легко видеть, что отображение ^является разнозначным,а также для любых £> имеет место
ччегл^чсо&чс^;,
г С3“)
ч Се. ) = V (£.) V ч с<$-)
Докажем, что для любых таких £, (?е X , ЧТО (в дру-