Игошин Математическая логика и теория алгоритмов (1019110), страница 94

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 94)

Множество Тй(Т) всех теорем формальной аксио мат ичесной теории Т перечислимо. До казател ь ство. Мы уже отметили, что множество аксиом формальной теории перечислимо, т.е. мы можем их эффективно перенумеровать Ан А,, А„... Поскольку все формулы состоят из конечного числа букв (символов), все выводы содержат конечное число формул и каждый вывод использует лишь конечное число аксиом, то ясно, что для каждого натурального и существует лищь конечное число выводов, имеющих не более чем и формул (щагов) и использующих только аксиомы (А„А„..., А„). Следовательно, двигаясь от и = ( к и = 2, п = 3 и т.д., можно эффективно перенумеровать все теоремы данной теории. Это и означает, что множество теорем перечислимо. П Теперь от произвольных формальных теорий будем переходить к таким, которые так или иначе имеют дело с натуральными числами.

Если мы хотим в нашей теории говорить о подмножестве (1 множества натуральных чисел, то мы должны иметь эффективный способ выписывания для каждого натурального и формулы И~, означающей, что и в Д Более того, если мы сможем доказать, что формула И'„является теоремой теории Т тогда и только тогда, когда и е Д, то будем говорить, что теория Тполуполна для Ц (или что в Т имеется полуполное описание Ц). Точнее, это определение сформулируем так. Определение 37.2. Теория Т называется полуполной для множества натуральных чисел Д а Ф, если существует перечислимое множество формул И",, И"„..., И'„, ..., такое, что Ц = (и: ь- И~„). Определение 37.3.

Теория Т называется полной для Д, если она полуполна для Ц и мы также имеем формулу И~„, которая интерпретируется как и я О, и мы можем доказать, что — И~ является теоремой теории Т тогда и только тогда, когда и я 9 Другими словами, теория Т полна для Ц, если в Т для каждого и мы можем установить, принадлежит оно Ц или нет. Точнее, это означает, что теория Т называется полной для множества натуральных чисел Ц, если она полуполна для Ц и полуполна для его дополнения О. Теорема 37.4. Если теория Т полуполна для множества Ц, то 0 перечислимо.

Доказательство. По определению полуполноты Т для 0 множество Ц есть множество номеров тех формул из некоторого перечислимого множества (И',, И'и ..., И~, ...) формул, которые являются теоремами теории Т, т. е, принадлежит и множеству 7й(Т) 378 Таким образом, О есть множество номеров всех формул из мно;кества ТМ Т) П ( Иы И'ь ..., И~, ...). Каждое из этих пересекаемых ,ножеств перечислимо: первое — по предыдущей теореме 37.1, второе — по сказанному в начале доказательства. Следовательно, я их пересечение, по теореме 35.5, перечислимо. Но тогда перечяслимо и множество номеров тех формул, которые входят в это пересечение. П Следствие 37.5.

Если Д перечислимое, но неразрешииое множество натуральных чисел, то никакая формальная теория не может бьипь полной для Д. Доказательство. Если множество Д перечислимо, но неразрешимо, то в силу теоремы 35.б его дополнение О неперечислимо. Тогда по теореме 37.4 никакая теория Тне является полуполной для Д.

Следовательно, никакая теория Т неполна для Ц. (3 От этого следствия до теоремы Геделя совсем недалеко. Для этого нужно средствами некоторой формальной теории Тразвить теорию натуральных чисел, причем так, чтобы принадлежность чисел данному множеству Ц можно было трактовать адекватно (т.е. число и принадлежит Д тогда и только тогда, когда некоторая эффективно сопоставленная ему формула теории Тявляется теоремой этой теории).

Это возможно только тогда, когда Д по меньшей мере перечислимо. Формальная арифметика и ее свойства. Формальная арифметика как формальная аксиоматическая теория строится на базе формализованного исчисления предикатов, рассмотренного в 5 25 и в Задачнике, В 11. Предметные переменные х„х,, х,, ... здесь будем называть числовыми, потому что вместо них будем подставлять натуральные числа.

Предметная переменная называется свободной в формуле, если она не стоит под знаком квантора (общности или сушествоваиия), и связанной — в противном случае. Формула называется замкнутой, если все ее предметные переменные связаны, и открытой, если в ней имеются свободные переменные. Замыканием формулы Р называется формула С(Е), получаюшаяся из Едописыванием спереди кванторов обшности по всем переменным, свободным в Р, Ясно, что для любой Е формула С(г) замкнута. Если Е замкнута, то С(Е) = Е Функция С(Е) вычислима. Отсюда следует, что класс замкнутых формул разрешим, поскольку рему принадлежит тогда и только ~огда, когда С(Р) = Р, и для распознавания этого равенства суШествует вычислительная процедура.

С понятием подстановки в формулу мы уже знакомы (см. конец в3). Если в формулу г" вместо символа (слова) Х везде, где он ~ходит в Е, вставить слово (формулу) Н, то получим новое слово (ФоРмУлУ), обозначаемое 5«нг и называемое РезУльтатом подстановки в г слова Н вместо слова Х. Тогда ясно, что 379 5"(- Г) «з — 5лГ; 5л(à — > 6) «з Б"à — ~ 5"6; если с « /, то 5„"(Ъхз)(Г) =- (Ъхз)Ю~Г, о'„'"(Зхз)(Г) - =(Зх)Ю„"Г, Имея дело с натуральными числами, мы хотели бы иметь воз можность полставлять их в формулы формальной теории (ариф метики), т.е.

иметь возможность говорить о числах на языке на шей формальной теории. Для этой цели в формальной теории не обходимо иметь слова, которые служили бы названиями натуральных чисел. Такие слова называются нумералами. Нумерал числа л обозначается и*. Требование к этим названиям (именам) вполне естественное: различные числа должны называться различными именами, т.е. если т «л, то гл* «и*. (Идея введения нумералов состоит в том, чтобы разделить вещи и имена этих вещей.) Таким образом„в формулы арифметики мы будем подставлять вместо числовых переменных х„хъ хъ ...

не сами натуральные числа и, и, lс, ..., а их нумералы (имена) в*, л*, /с*, ... соответственно. Наконец, мы можем сформулировать последнее требование (аксиому), которое мы предъявляем к формальной арифметике. Назовем его аксиомой арифметики: если предметная переменная х, не связана в Г, то (АА): 5„"'Г -э (Лх;)(Г).

Если ввести для Я„" Г обозначение Г(п'), то эта аксиома принимает вид: (АА): У(л*) -+ (Лх;)(Г). Это исключительно естественное требование: если формула Г превращается в истинное высказывание при подстановке в нее вместо переменной х; какого-нибудь натурального числа п*, то истинно и высказывание (Лх;)(Г). Никаких других ограничений на формализацию арифметики не накладывается. Неважно, в частности, как определяются сложение и умножение натуральных чисел, как вводится отношение порядка, чем мы скрупулезно занимались при построении теории натуральных чисел на основе системы аксиом Пеано.

Даже при таких самых общих допущениях на формализацию арифметики эта формализация будет подчиняться теореме Геделя: если она будет непротиворечива, то она будет неполной. Итак, определившись с понятием формальной арифметики, посвятим оставшуюся часть этого пункта понятиям а-непротиворечивости, адекватности и полноты этой формальной теории, участвующим в точной формулировке теоремы Геделя. Начнем с понятия непротиворечивости. Как и всякая аксиоматическая теория, формальная арифметика называется непротиворечивой, если в ней нельзя доказать какое-либо утверждение и его отрицание, т.е.

если не существует такой формулы Г, что одновременно ь- Г и ~- — Г 380 Предположим теперь, что для некоторой формулы 6(х), содер,ашей свободно единственную предметную переменную х, установ„ено, что ~- 6(п*) лля всех натуральных чисел и = О, 1, 2, 3, ... Даже ,ели в формальной арифметике невозможно доказать ~ — ('чх)(6(х)), ы конечно же можем считать это утверждение следствием приведенного списка теорем. Следовательно, если в теории удастся доказать теорему ~- — (чх)(6(х)), то такую формальную арифметику следует считать противоречивой. Определение 37.б. Формальная арифметика называется го-непромиворечивой, если в ней нет такой формулы 6(х) с единственной свободной предметной переменной х, что для всех натуральных чисел п справедливы теоремы ~- 6(п*) и ~- - (чх)(6(х)).

Теорема 37. 7. Если формальная арифметика го-непротиворечиво, мо она непротиворечива. Д о к аз а тел ь от в о. В самом деле, если бы она была противоречива, то, как доказано в ~ 27, после определения 27.1, все ее формулы были бы теоремами, в том числе и те, которые создают в-противоречивость формальной арифметики, и последняя была бы го-противоречива. 13 Определение 37.8. Назовем и-местный предикат Р(х„..., х„) над множеством натуральных чисел Х вполне представимым в формальной арифметике, если существует такая формула Р(хь ..., х„), свободными предметными переменными которой являются и переменных хь ..., х„(и только они), что: а) для каждого набора и натуральных чисел (ап ..., а„), для которого предикат Р превращается в истинное высказывание Р(а„..., а„), имеет место теорема: ь- Р(ап ..., а„*); б) для каждого набора и натуральных чисел (а„..., а„), для которого предикат Р превращается в ложное высказывание Р(а„..., а„), имеет место теорема: ь — — Р(ап ..., а„').

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

В теореме 37.4 мы показали, что лишь перечислимые множества чисел могут иметь полуполное описание в формальной теории, т.е. существует перечислимое множество формул И'ь, И"„И"2, ..., такое, что 0 = (и: ~ — И"„). Адекватность нашей формальной теории (арифметики) могла бы означать, что она является полуполной для каждого перечислимого множества натуральных чисел, т.е.

что в ней имеет полуполное ~писание всякое множество, которое вообще может иметь такое ~писание хотя бы в какой-нибудь теории. 381 В теореме 37.1 мы установили, что множество всех теорем фор. мальной теории перечислимо, т.е. все теоремы и, значит, приво дящие к ним выводы (доказательства) могут быть эффективно перенумерованы.

Возьмем наше множество Д и соответствующее ему множество теорем [И"ь, Ин Ип ...). Рассмотрим следующий предикат Р(х, у): «у — номер доказательства теоремы И'„». Если высказывание Р(т, п) истинно, то это означает, что и есть номер вывода теоремы И~„, что, в свою очередь, означает, что т в О т.е. и есть номер вывода о том, что т в Д Обратно, взяв конкретные числа т и и, мы можем эффективно построить теорему (фор мулу) И~ и эффективно построить и-й вывод, после чего эф фективно определить, является ли построенный вывод выводом теоремы И', т.е.

Характеристики

Список файлов книги