Новые константы в предтабличных суперинтуиционистских логиках

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

Содержание
Введение

Глава 1. О метаматематике 92-логик

1.1 Метаматематика чистых шкал и логик

1.2 О предтабличных суперинтуиционистских логиках

1.3 Метаматематика ср-шкал и 99-логик

Глава 2. Классификационные теоремы для полных по Новикову расширений предтабличных суперинтуиционистских логик
2.1 Пополнения ЬС: классификация, примеры с одной и двумя константами и явные соотношения в них
2.2 Пополнения Ь2: классификация, примеры с одной и двумя константами и явные соотношения в них

2.3 Пополнения Ь3 классификация, примеры с одной константой

и явные соотношения в них

Глава 3. Вопросы аксиоматики и алгоритмической разрешимости
3.1 Построение канонической <р-модели
3.2 Аксиоматика полных по Новикову расширений предтабличных суперинтуиционистских логик
3.3 О некоторых алгоритмических вопросах
Список литературы

Введение
В исследовании какого-либо объекта (или класса объектов) при отыскании существенно новых свойств этого объекта часто применяется метод обогащения, при котором изучаемый объект становится частью другого объекта, при этом новый объект наделяется дополнительными атрибутами — отношениями, функциями и прочее. В некоторых случаях исходный объект представляет собой собственное подмножество нового объекта, в других — новый объект получается лишь заданием на старом дополнительных атрибутов.
Синтаксическим отражением такого обогащения является расширение языка. Утверждения и понятия, записанные на исходном языке, можно назвать реальными, а утверждения и понятия, использующие дополнительные атрибуты — идеальными. Например, к числу реальных понятий Д. Гильберт относил понятие алгоритмически вычислимой функции. К реальным утверждениям он относил формулы вида /х(/(ж) = д(х)) с вычислимыми функциями / и д. Мотивировка — любой частный случай этого равенства проверяется явно за конечное число шагов.
Пусть Т — базовая теория в базовом языке 8. Основа языка § — реальные понятия; основа теории Т — аксиомы и правила вывода реального языка. Добавление к базовому языку новых символов (например, функциональных, константных, предикатных), иначе говоря, введение в язык 3 идеальных понятий, или экстрапонятий, расширяет (другими словами — обогащает) его до языка §' :§ С 8'. Соответственно, введение в базовую теорию Т дополнительных аксиом (и, возможно, правил вывода) расширяет ее до теории Т' : Т с Т'. При этом новые аксиомы, или экстрааксиомы, отражают свойства экстрапонятий и их взаимосвязь с реальными понятиями. В математике примеров такого рода много. В теории натуральных чисел, например, ряд результатов был получен с помощью теории комплексных

чисел. В алгебре примером такого рода является задача о разложении многочлена хА + 1 = 0 на множители над полем действительных чисел (есть два способа решения: первый подразумевает отыскание комплексных корней, второй — выделение полного квадрата). Примерами из математической логики являются булевы алгебры с операторами, языки более высокого порядка, относительно элементарная определимость и другие.
Заметим, что при произвольном расширении теории Т' может оказаться противоречивой, даже если Т была непротиворечива. Поэтому важнейшее требование для такого расширения теорий — получаемая теория должна быть консервативна над исходной теорией, то есть экстрапонятия и новые аксиомы не должны нарушать базовую теорию:
А є §, Т'ЬЛ Т 1-А
(если утверждение реального языка выводимо в расширенной теории, то и в реальной теории оно должно быть выводимо).
Согласно Гильберту, основное назначение экстрапонятий — получение новых реальных, теорем, а также более ясное доказательство уже известных теорем. Иначе говоря, экстрапонятия повышают выразительную силу языка и упрощают доказательства прежних теорем.
Для пропозициональных исчислений экстрапонятиями являются, например, кванторы. Язык первого порядка позволил выразить практически все понятия, нужные для работы в привычных разделах математики. Следствием такой универсальности стали, например, неразрешимость логики первого порядка, неполнота арифметики, неформализуемость логики второго порядка.
Тем не менее, для решения ряда задач был найден промежуточный вариант — вместо кванторов использовать дополнительные пропозициональные связки, отражающие некоторые свойства кванторов. Известные связки

растающую цепь в д, поэтому в силу второго утверждения теоремы 2.1.1 (ц-цепь С имеет высоту не меиее чем т + 1.
Теперь «сотрем» в д и в С выделенные конусы с номерами п + т, п + пг — 1,..., п + 1. Получаем / : (Ж 5; Ф) (С; Ф).
Проведя описанное построение для всех конечных цепей Ст, получим искомый класс С д-цепей. □
Следствие 2.1.5. Любая консервагпивная над ЬС р-логика включена в р-логику некоторого конфиналъного класса конечных р-цепей.
Таким образом, для отыскания примеров полных по Новикову расширений ЬС достаточно рассматривать конфинальные классы конечных (ц-цепей.
п. 2. Прототипы и классификация полных по Новикову расширений логики ЬС
В работе [23] дапо описание полных по Новикову расширений логики ЬС для конечного случая констант. Для построения полных по Новикову расширений используется метод наростов.
В своих дальнейших рассуждениях вместо понятия «нарост» мы используем его цветовой аналог — «прототип».
Определение 2.1.1. Прототипом С называется конечная ^5-цепь 6 = (С, Ф1,..., Ф„), в которой все точки имеют попарно различные цвета.
Заметим, что всякая конечная д-цепь р^ -морфируется на некоторый прототип (для этого достаточно отождествить точки, имеющие одинаковый