Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 75
Текст из файла (страница 75)
В этом случае из невыводимости формулы ((т) =0 получается, что невыводима также и формула гбх (1(х) = 0). Сделаем теперь относительно Р некоторое дополнительное допущение, представляющее собой усиление требования непротиворечивости этого формализма, а именно, будем считать, что если для каждой цифры и формула е((гг) выводима в Р, то формула ) Ууй((у) невыводима в Р. Тогда из того, что в Р для каждой цифры ! выводимо равенство ((!) =О, будет вытекать невыводимость в Р формулы ) ггх(((х) =0). Если мы, следуя Геделю, назовем непротиворечивый дедуктивный формализм, удовлетворяющий этому дополнительному условию, ш-н е п р от и в о р е ч и в ы м, то получим следующую теорему: Для всякого формализма Р, удовлетворяющего условиям аг) и б,), содержащего квантов всеобг ности (вместе с относящимися к нему формальными спо обами у с акмочений) и, кроме того, ш-непротиворечивого, можно указ ть такую формулу без свободных переменных, что ни сама она, ни е стриг)икие не будут выводимы в Р.
Однако, как недавно показал Баркли Россер '), предположение об ш-непротиворечивости Р из формулировки этой теоремы может быть исключено, т. е. вместо ш-непротиворечивости Р мы, как (ложного) предложения «каждое число равно нулю». Но отрицание етого предложеннн нзображзетсв не формулой а ~О, а формулой ) ггх(х=п), которая в действнтельностн выводима в арифметическом формализме. Таким образом, упомянутое предложеняе не является формально неразрешнмым в формализме арифметики. г) См. Ц аз ее г з. В. ЕХ1епяопз о1 зогпе йеогевз о!Соде! апд Сйнгсь.— ).
Еувьо!1е Еой)е, 1936, 1, № 3. ГРАНИЦЫ ИЗОВРАЗИМОСТИ И ВЫВОДИМОСТИ зез н раньше, можем говорить о непротиворечивости Р в обычном смысле этого слова. Для доказательства этого усиления теоремы Геделя целесообразно ввести предположение, что, кроме квантора всеобщности, формализм Р содержит еще и квантор существования вместе с относящимися к нему формальными способами умозаключений. Потом можно будет снять это предположение. Впрочем, по-прежнему должны быть выполнены предположения аг) и б,) и, кроме того, еще одно предположение б;): имеется такая рекурсивная функция е (и), которая номеру любой формулы формализма Р ставит в соответствие номер отрицания этой формулы.
Вместо фигурирующей в геделевском доказательстве формулы ~хт(т, б(а, а)) мы рассмотрим формулу Чх (В (х, б (а, а)) — Ву (у ~ х й 3 (у, е (б (а, а))))). Пусть» является номером этой формулы, а «является номером формулы тгх(6(х, б(1, »))-РЛу(у~хйЗ(у, е(б(», »))))), которую мы для краткости обозначим буквой Гз.
Тогда в Р будет выводимо равенство б(», »)=« а потому формула гв будет переводима в формулу ггх(6(х, «)- Эу(у==хйб(у, е(«)))), которую мы обозначим (Ег. Предположим, что Й выводима в Р. Тогда для некоторой цифры 1, являющейся номером вывода формулы Сь, будет иметь место отношение 6(1, «).
А тогда в Р будет выводима и формула ч)(1, «), а также и формула гзз. Из бз и 6(1, «) получается формула Лу(у 1й6(у, е(«))), которая с помощью выводимой средствами рекурсивной арифметики формулы с~! с=О )/ ...')) с=1 и с использованием аксиом равенства переводима в дизъюнкцию 6(0, е(«)) )/ ...')/6(1, е(«)), Эта дизъюнкция является формулой без переменных. Поэтому, вычисляя соответствующие рекурсивные функции и интерпретируя связки исчисления высказываний как истинностные функции, можно найти ее истинностное значение.
344 ВЫХОД ЗА РАМКИ ТЕОРИИ ПОКАЗАТЕЛЬСТВ [гл ч 4 П грлницы изоннлзимости и выводимости Если эта дизъюнкция является истинной, то истинна по край- ней мере одна из формул 6(О, е(е)), ..., 6((, е(е)), и тогда по крайней мере одна из цифр от 0 до! является номе- ром некоторого вывода формулы ~6, номер которой равен зна- чению е(ч).
Следовательно, в этом случае формула ) 6 выводима в Р, Но по нашему предположению в Р выводима и формула 6. Значит, в этом случае формализм Р противоречив. Если же дизъюнкция 6(0, е(а))'~ ... ~/ 6((, е(о)) является ложной, то ее отрицание истинно, а значит, и выводимо в Р, между тем как, с другой стороны, в Р выводима н сама эта днзъюикция. Тем самым формализм Р опять оказывается п о- тиворечивым. Предположим теперь, что в Р выводима формула ) 6. Тогда для некоторой конкретной цифры ( имеет место отношение 6((, е(1)), а тогда в Р выводима также и формула 6((, е(4)). Из этой формулы мы получаем формулу ( ( с — Р лу (у ~ с зе 6 (у, е (й))), а из нее 1 =(у (у ~ с й 6 (у, е (о))) -+. с = (, С другой стороны, предположенная выводимой формула ) 6 пере- водима в ) б„а эта в свою очередь — в формулу Лх(6(х, н) ое ) 'Зу(у(х ее6(у, е(о)))), Эта формула, взятая вместе с только что выведенной из 6 ((, е (о)) формулой, дает 'Зх (6 (х, Ч) се х ~ (), а эта формула с помощью ранее уже упоминавшейся эквивалентности с(( с=О ~/ ...
~/ с=( переводима в дизъюнкцию 6(0, Ч) У' ...'У' 6((, й). слч . У А теперь мы можем опять произвести соответствующий ра б р во лож ". Е у аев. Указанная дизъюнкция является либо истинной, л б но тог а о . иой. Если она истинна, то истинен один из ее чле нов, и д формула с номером д, т. е.
формула 6, выводима в Р, между тем как, с другой стороны, по предположению выводима формула ) 6; значит, в этом случае формализм Р противоречив. Если же эта дизъюнкцня ложна, то истинно ее отрицание, и тогда это отрицание выводимо в Р, между тем как, с другой стороны, выводима сама эта дизъюнкция.
Значит, и в этом случае формализм Р тоже противоречив. Таким образом, в целом получается, что и в том случае, когда в Р выводима формула 6, и в том случае, когда в Р выводима ) 6, этот формализм оказывается противоречивым, так что если формализм Р иепротнворечив, то формула 6 изображает некоторое формально неразрешимое в Р предложение. Впрочем, формула 6 может быть переведена в некоторую формулу вида 1йх(((х) = 0), где (( ) — рекурсивно определенный функциональный знак, так как формула 6(лт, з(р, р)) ЗуЬ( й6(у е(з( ° р)))1 задает некоторый рекурсивный предикат $(т).
Наше рассуждение также показывает, что если формализм Р непротиворечив, то для любой цифры ( формула 6((, н) ложна, и потому всякая нумерическая формула, получающаяся преобра- зованием формулы 6((, з(р, р))- Бу(у~(ее 6(у, е(з(р, р)))), является истинной, а потому и выводимой в Р формулой. (Тем самым в Р выводима и сама указанная формула.) Как уже отмечалось, из этого рассмотрения можно исключить предположение о наличии в формализме Р квантора существова- ния. Для этого достаточно всюду заменить выражения вида Бур((у) соответствующими им выражениями ) 1йр~р((у) и восполь- зоваться тем, что любая формула вида ) 1ре 1(е — 1 ХК(е)) где ( — цифра, может быть переведена сначала в формулу ) Чее(е ) )Й(е)) а затем с помощью формулы с =( -с=О у ...'у' с=( в формулу Упомянем еще одно замечание, которое Россер делает в его уже цитированной работе в связи с геделевским доказательством первой теоремы о неполноте'), а также в связи со своей моди') Это вемечннне относится, впрочем, н но второй ееореме Геделя о не- полн оте, 34б ГРАНИЦЫ ИЗОБРАЗИМОСТИ И ВЫВОДИМОСТИ 347 ВЫХОП ЗА РАМКИ ТЕОРИИ ДОКАЗАТЕЛЬСТВ !гл, ч фикацией этого доказательства.
В этих доказательствах предположение о том, что формула 6(т, п) является рекурсивным изображением отношения «число т является номером некоторого вывода в Р формулы с номером п», используется не в полном объеме. Из свойств формулы 6(т, п), кроме того, что она является рекурсивной формулой, не содержащей отличных от т и и переменных, используется только то, что цифра и является номером некоторой выводимой в г" формулы тогда и только тогда, когда для некоторой конкретной цифры ш имеет место отношение 6(ш, и). Условие, необходимое и достаточное для того, чтобы существовала рекурсивная формула 6(т, и), обладающая указанным свойством, заключается в том, что номера формул, выводимых в г", должны образовывать область значений некоторой одноместной рекурсивной функции Ь(п), так что последовательность значений этой функции Ь (О), Ь (О'), Ь (О"), будет представлять собой пересчет (может быть, с повторениями) номеров выводимых в г формул, Действительно, если это условие выполняется, то равенство Ь(т) =п представляет собой рекурсивную формулу, обладающую указанным свойством.
Но указанное условие является также и необходимым. Действительно, как это показал Клини1), для всякой рекурсивной формулы 6(т, п), для которой известна по крайней мере одна пара чисел ш и и такая, что формула 6(ш, и) является истинной, можно указать одноместную рекурсивную функцию Ь (и) такую, что для всякой пары чисел т и б такой, что б является значением Ь(т), можно указать цифру и, для которой формула 6(й, б) истинна, и для всякой пары чисел о и б такой, чтоформула 6(о, б) истинна, можно указать цифру т такую, что б является значением Ь(т). В самом деле, такую функцию Ь(п) можно получить следующим образом: будучи рекурсивной, формула 6 (т, и) допуснает перевод в равенство 1(и, и)-0, где 1(т, и) — некоторый рекурсивный терм. Пусть О,(п) и О, (п)— введенные в гл. ЧП т.
1 рекурсивные функции, обращающие рекурсивную функцию О(а, Ь), которая дает взаимно однознач- ) К! ее не 3. ИЛ Пенегв! гесцгзг«е !но«Вон» о1 пвщгв! ВшцЬегз,— Мврь йпп., 1933, 112, Ьй 5, теорема !!!. иое отображение числовых пар на числа'). Возьмем цифру п, входящую в какую-нибудь такую цифровую пару ш и и, что формула 6(ш, и) оказывается истинной. Тогда выражение и зйп (1 (О» (и), Оз (и))) + Оз (и) зйп (1(О1 (и), Ог (и))), как легко убедиться, задает некоторую функцию Ь(п), обладающую искомым свойством').
Таким образом, в допущении б,) условие, относящееся к формуле 6 (т, и), может быть заменено более слабым требованием, чтобы номера выводимых в г" формул образовывали область значений какой-либо одноместной рекурсивной функции ").
Итоговое допущение, которое таким образом появляется на месте предположения б,), мы обозначим через б",). Введя вместо бт) это допущение б,*) и объединив утверждение о существовании формально неразрешимых предположений с нашей формулировкой первой теоремы Геделя о неполноте, мы получаем следующий усиленный вариант этой теоремы: 1. Для всякого непротиворечивого дедуктивного формализма Р, удовлетворяющего условиям ат) и б",), »южно указать такую рекурсивную функцию ! (т), что равенство ((т) = О невыводимо в Р, в то время как для любой цифры 1 равенство ((1) = 0 является истинной и выводимой в г" формулой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
