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