Основания математики (математическая логика)

Научная библиотека

Научная библиотека

Основания математики

Гильберт Д., Бернайс П. Основания математики.

Двухтомная монография Д. Гильберта и П. Бернайса занимает уникальное место в мировой математической литературе. Ее первое немецкое издание, вышедшее в тридцатых годах, подвело итог процессу становления математической логики как самостоятельной математической дисциплины со свой проблематикой и своими методами. Эта книга оказала решающее влияние на дальнейшее развитие математической логики.

Оглавление

ПРЕДИСЛОВИЕ РЕДАКТОРА РУССКОГО ПЕРЕВОДА
ГЛАВА I. ПРОБЛЕМА НЕПРОТИВОРЕЧИВОСТИ В АКСИОМАТИЧЕСКИХ ИССЛЕДОВАНИЯХ КАК ЛОГИЧЕСКАЯ ПРОБЛЕМА РАЗРЕШИМОСТИ
2. Пример: аксиомы геометрии.
3. Чисто логический подход к аксиоматике.
§ 2. Проблема разрешимости
1. Общезначимость и выполнимость.
2. Распознавание в случае конечных индивидных областей.
3. Метод построения модели.
§ 3. Вопрос о непротиворечивости в случае бесконечной индивидной области
2. Проблематика бесконечного.
3. Установление непротиворечивости как доказательство невозможности; метод арифметизации.
ГЛАВА II. ЭЛЕМЕНТАРНАЯ АРИФМЕТИКА. ФИНИТНЫЙ СПОСОБ РАССУЖДЕНИЙ И ЕГО ГРАНИЦЫ
§ 1. Рассуждения на интуитивном уровне и их применение в элементарной арифметике
2. Законы арифметических действий; полная индукция; умножение; делимость; простые числа.
3. Рекурсивные определения.
4. Одно доказательство невозможности.
§ 2. Дальнейшие применения интуитивных рассуждений
1. Отношение арифметики к учению о количестве.
2. Формальная точка зрения в алгебре.
§ 3. Финитная точка зрения; выход за ее пределы в области арифметики
2. «Tertium non datur» для целых чисел; принцип наименьшего числа.
§ 4. Нефинитные методы в анализе
2. Верхняя грань числовой последовательности; верхняя грань множества чисел.
3. Принцип выбора.
§ 5. Исследования, направленные на непосредственное финитное построение анализа; возврат к прежней постановке проблемы; теория доказательств
ГЛАВА III. ФОРМАЛИЗАЦИЯ ПРОЦЕССА ЛОГИЧЕСКОГО ВЫВОДА I: ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
1. Истинностные функции и их таблицы.
2. Заменимость; правила замены.
3. Примеры заменимости.
4. Двойственность; конъюнктивная и дизъюнктивная нормальные формы; тождественно истинные выражения; распознающая процедура.
5. Совершенная нормальная форма; распознавание заменимости; примеры.
§ 2. Применение теории истинностных функций к логическому выводу; формализация умозаключений в логике высказываний с помощью тождественно истинных выражений, правила подстановки и схемы заключения
§ 3. Дедуктивная логика высказываний
2. Одна система исходных формул для дедуктивной логики высказываний; полнота этой системы.
3. Позитивная логика; регулярные импликативные формулы; позитивно тождественные импликативные формулы; возможные упрощения.
§ 4. Доказательства независимости, проводимые методом оценок
2. Доказательетво независимости рассматриваемой системы исходных формул; еще одно доказательство независимости.
3. Применение метода оценок к вопросу о замене формул схемами.
§ 5. Возврат к рассмотренному в § 2 способу формализации вывода; сокращенные правила; замечание, касающееся противоречивости системы
ГЛАВА IV. ФОРМАЛИЗАЦИЯ ПРОЦЕССА ВЫВОДА II: ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
§ 1. Введение индивидных переменных; понятие формулы; правило подстановки; пример; параллель с содержательными рассуждениями
§ 2. Связанные переменные и правила для кванторов всеобщности и существования
2. Введение связанных переменных; кванторы всеобщности и существования; правило переименования переменных; предотвращение неоднозначностей; обобщение понятия формулы и правила подстановки.
3. Эвристическое введение правил для кванторов всеобщности и существования; содержательный смысл формул и схем.
4. Окончательная формулировка правил исчисления предикатов; изображение форм категорических суждений; случай пустой индивидной области.
§ 3. Выводимость
2. Вывод некоторых формул. Теперь перейдем к выводу некоторых формул исчисления предикатов.
§ 4. Вопросы систематики
1. Понятия t-тождественной формулы и формулы, тождественной в конечном; дедуктивная замкнутость совокупности t-тождественных формул; непротиворечивость исчисления предикатов; вопросы полноты.
2. Экскурс в теоретике-множественную логику предикатов; предварительные замечания к вопросу о полноте; проблема разрешимости и ее уточнение с дедуктивной точки зрения.
§ 5. Изучение формализма исчисления предпкатов
2. Приведение формул к предваренному виду; примеры; описание разрешимых случаев проблемы разрешимости с помощью предваренной нормальной формы.
3. Разложение формул одноместного исчисления предикатов в примерные формулы; пример.
§ 6. Дедуктивное равенство и дедукционная теорема
1. Понятие дедуктивного равенства; два существенных случая дедуктивного равенства; переводимость и дедуктивное равенство.
2. Дедукционная теорема.
3. Применения дедукционной теоремы: сведение вопросов, связанных с аксиоматикой, к вопросам выводимости формул в исчислении предикатов; рассмотрение одного распространенного способа умозаключения.
4. Дедуктивное равенство произвольной формулы подходящей сколемовской нормальной форме, а также нормальной дизъюнкции; упрощение этого перехода.
ГЛАВА V. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ С РАВЕНСТВОМ. ПОЛНОТА ОДНОМЕСТНОГО ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
1. Знак равенства; изображение высказываний о количестве; аксиомы равенства и формальные свойства равенства.
2. Применение аксиом равенства к различным преобразованиям, в частности к преобразованиям для оценок числа элементов в индивидной области; количественные формулы.
3. Разложение в примарные формулы для формул расширенного одноместного исчисления предикатов.
4. Обобщение понятия t-тождественной формулы; дедуктивная замкнутость совокупности t-тождественных формул; однозначность равенства.
5. Добавление функциональных знаков; понятие терма; выводимые формулы.
§ 2. Решение проблемы разрешимости; теоремы о полноте
1. Распознавание выводимости таких предваренных формул исчисления предикатов, у которых все кванторы всеобщности предшествуют всем кванторам существования; разрешимость в конечном.
2. Выводимость всякой тождественной в конечном формулы одноместного исчисления предикатов; доказательство с помощью прежней распознающей процедуры; теоретико-множественное доказательство и его финитное уточнение.
3. Нормальная форма формулы расширенного одноместного исчисления предикатов на основе дедуктивного равенства.
4. Теоремы о полноте для расширенного одноместного исчисления предикатов.
ГЛАВА I. НЕПРОТИВОРЕЧИВОСТЬ СУЩЕСТВОВАНИЯ БЕСКОНЕЧНЫХ ИНДИВИДНЫХ ОБЛАСТЕЙ. НАЧАЛА АРИФМЕТИКИ
1. Замена формульных переменных предикатными символами; одна зависимость между рассматриваемыми формулами.
2. Привлечение аксиом равенства; дедекиндово определение бесконечности; введение штрих-символа.
3. Переход к аксиомам без связанных переменных с усилением экзистенциальных аксиом; символ 0; цифры в новом смысле; аксиомы, Пеано; получившаяся система аксиом.
§ 2. Общелогическая часть доказательства непротиворечивости
1. Выбор заключительной формулы; исключение связанных переменных; разложение доказательства на нити.
2. Возвратный перенос подстановок; исключение свободных переменных; нумерические формулы; определение истинности и ложности; истинность всякой формулы, выводимой без использования связанных переменных.
3. Включение связанных переменных; мероприятия по сохранению схем при возвратном переносе подстановок; недостаточность прежних методов.
§ 3. Доказательство непротиворечивости с помощью процедуры редукции
1. Исключение квантора всеобщности; этапы редуцирования; понятие редукции формулы.
2. Верифицируемые формулы; теорема об однозначности; леммы.
3. Вернфицируемость выводимых формул, не содержащих формульных переменных; заменимость аксиом схемами аксиом.
§ 4. Переход к одной (в области формул, не содержащих формульных переменных) дедуктивно завершенной системе аксиом
1. Выводимость ряда верифицируемых формул в рассматриваемой системе аксиом; доказательство с помощью «цифр второго рода».
2. Подход к пополнению этой системы аксиом; выводимость ряда эквивалентностей как достаточное условие.
3. Дедуктивное сведение этих эквивалентностей к пяти добавляемым к этой системе аксиом формулам; система (А).
4. Полнота системы (А).
§ 5. Включение полной индукции
2. Упрощение рассматриваемой системы аксиом в результате добавления аксиомы индукции; система (В).
§ 6. Доказательства независимости
1. Невыводимость аксиомы индукции из формул системы (А).
2. Доказательства независимости с помощью метода подстановок.
3. Установление ряда других независимостей с помощью модификации процедуры редукции.
§ 7. Изображение принципа наименьшего числа при помощи выражающей его формулы; равносильность этой формулы аксиоме индукции на основе прочих аксиом системы (В)
ГЛАВА VII. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ
1. Простейшая схема рекурсии; формализация интуитивной процедуры вычисления; сопоставление явных определений с рекурсивными.
2. Доказательство непротиворечивости добавления рекурсивных определений в рамках элементарного исчисления со свободными переменными; привлечение схемы индукции.
3. Невозможность вывода непротиворечивости рекурсивных определений в качестве следствия непротиворечивости систем предыдущих аксиом
§ 2. Рекурсивная арифметика
2. Изображение высказываний равенствами вида t=0; суммы и произведения с переменным числом членов; изображение высказываний с ограниченными кванторами; изображение максимума и минимума.
3. Делимость; деление с остатком; наименьший отличный от 1 делитель; последовательность простых чисел; разложение числа на простые множители; нумерация конечных последовательностей чисел; нумерация числовых пар; наибольший общий делитель; наименьшее общее кратное.
§ 3. Некоторые обобщения схем рекурсии и индукции
1. Рекурсии, допускающие сведение к простейшей схеме рекурсии (примитивная рекурсия); рекурсии пробега, одновременные рекурсии.
2. Перекрестные рекурсии; несводимость перекрестных рекурсий определенного типа к примитивным рекурсиям.
3. Обобщенная схема индукции; устранимость этой схемы.
§ 4. Представимость рекурсивных функций; переход к удовлетворительной системе аксиом для арифметики
1. Возврат к полному формализму; система (С); понятие существенного расширения формализма; примеры несущественных расширений; представимость функции.
2. Доказательство того, что сумма и разность не представимы в формализме системы (В); рекурсивные равенства для сложения как аксиомы; система (D).
3. Доказательство непротиворечивости и полноты системы (D) с помощью метода редукции; непредставимость умножения в формализме системы (D).
4. Изменение ситуации в случае добавления рекурсивных равенств для умножения; система (Z).
§ 5. Дополнительное рассмотрение аксиом равенства
1. Замена второй аксиомы равенства аксиомами более специального характера.
2. Применение к системам (А), (В) и (Z).
3. Применение к проблеме разрешимости; устранимость аксиом равенства из выводов формул исчисления предикатов.
ГЛАВА VIII. ПОНЯТИЕ «ТОТ, КОТОРЫЙ» И ЕГО УСТРАНИМОСТЬ
1. Разъяснения неформального характера; введение i-правила; предотвращение коллизий; изображение функций посредством i-термов.
2. Вложение и подчинение; символы для сокращений.
3. Функция w(A); формализация понятия наименьшего числа с помощью функции mxA(x); формулы однозначности.
§ 2. Дедуктивное построение арифметики на основе системы аксиом (Z) с добавлением формализованного понятия наименьшего числа
2. Наименьшее общее кратное двух чисел и конечной последовательности чисел; максимум конечной последовательности чисел.
§ 3. Сведение примитивных рекурсий к явным определениям посредством функции mxA(x) на основе аксиом системы (Z)
2. Формальная реализация; возможность обобщения этого метода.
§ 4. Устранимость характеристик (i-символов)
2. Россеровский подход и его упрощение, произведенное Хазенъегером; подстановка i-термов; аксиома (i); свойства рассматриваемых формальных систем.
3. Определение редукции формулы и сведение требующегося доказательства к доказательству выводимости без i-символов для формул, построенных по определенным схемам.
4. Доказательство.
5. Формулировка теоремы об устранимости; переводимость всякой формулы в ее редукцию; сравнение различных методов устранения.
§ 5. Следствия, вытекающие из устранимости характеристик
2. Общий способ исключения функциональных знаков путем введения предикатных символов; исключение индивидных символов.
3. Применение этой процедуры к системе (Z); перспективы дальнейших исследований.
§ 6. Добавление: распространение теоремы о возможности замены аксиомы равенства (J2) в случае добавления i-правила