Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 82
Текст из файла (страница 82)
с, 368. 4) См. с. 31 — 32, 373 374 ВЫХОП ЗА РАМКИ ТЕОРИИ ДОКАЗАТЕЛЬСТВ г'л, ФОРМАЛИЗАЦИЯ АРИФМЕТИЧЕСКОГО ФОРМАЛИЗ'1А Кроме того, как и раньше'), мы используем некоторую функцию З1(т, Й), определение которой теперь мы дадим следующим разбором случаев: «Если т=З'.й и й — простое число, большее илн равное 7, то з1(т, /г) =2 ° 3". Если т=2' 3" 5'п, с)0 и п не делится ни на одно из чисел 2, 3 и 5, то 31(т, Ь) =2 3 . 5'- Д 1э"<ега к!»5 к<м В остальных случаях з1(т, й) =т». По отношению к (2 ) эта функция обладает свойствами, аналогичными свойствам функции с тем же обозначением в отношении ранее рассматривавшегося формализма. Именно, ее значение з10и, 1) для цифры а, являющейся номером некоторого выражения 21, и для цифры 1, являющейся номером некоторой связанной переменной х, равняется номеру того [не обязательно принадлежащего формализму (ХР)! выражения, которое получается нз 'Л в результате повсеместнол замены переменной х цифрой О, за исключением тех мест, где она фигурирует в качестве составной части какого-либо квантора всеобщности 1(Л или существования Чу или в качестве индекса у какого-либо )»-символа.
й теперь мы изложим определение предиката С(п) [сначала в содержательной метаматематической форме|. Термами и формулами являются следующие выражения: а) цифра О, свободные индивидные переменные, формульные переменные без аргументов; б) терм с идущим за ним штрих-симвзлом, формула со стоящим перед ней знаком отрицания; в) формульные переменные с термами в качестве аргументов, г) символы +, , =, ( и с термами в качестве аргументов; д) введенные посредством явных определений функциональные знаки и предикатные символы с термами в качестве аргументов; е) конъюнкция, дизъюнкция, импликация и эквивалентность двух формул; ж) выражения»УуЛ(Л', 3~21(х) и р Л(х), где й!(Т) — выражнеие, содержашее связанную переменную х [но не в области действия какого-либо одноименного с ней квантора или )д-символа! и такое, что 6(0) является формулой.
Условия, наложенные в пункте ж) на выражение й(у), можно сформулировать еще и следующим образом: если переменную х к) См. с. 280 и далее. всюду заменить цифрой О, за исключением тех мест, где она фигурирует в качестве составной части какого-либо квантора всеобщности )УЛ или существования Зй или в качестве индекса у какого-либо В-символа, то из Л(х) получится некоторая формула и эта формула будет отлична от 'Л(у). Перечисленным возможным типам термов и формул соответствуют следующие возможности наличия свойства ю(п) у числа п: а) п = 2 или п = 2 р, или п = 10 р, где р — простое число, большее или равное 7; б) п=З т, т~О и С(т); в) п=!0 т, где е.,(т)~3 и для любого х, меньшего т, либо ч(т, х) =О, либо 45(т(т, х)) й )(10! Р(т, х)); г) п имеет один из видов 5 1!' 13», 5.11' 17', 70 11" 13», 70 1!" 17', 70 13' 17', где всякий раз Я(а), 45(Ь), !(10~а) и -)(!О~Ь); д) и=4 5 т, где д=1, если Л,(т) не делится на 10, и 0=14, если 7;(т) делится на 10; кроме того, ХО(т), (О().,(т)) и для любого х, меньшего т, либо т (т, х) = О, либо С(т (т, х)) й !(10;т(т, х)); е) и=у 20 7' !1', а делит 8 и 45(а), С(Ь), 10/а и 10,Ь; ж) п=с7 25 р', д делит 4, р — простое число, большее или равное 7, з1(а, р) Фа, С(з((а, р)) и 10~ з1(а, р).
Из этои семичленнои альтернативы, которой без труда можно придать совершенно формальный вид, мы получим некоторую эквивалентность 45 (и) Е» (п) Ч 41» (п) 1/ ... Ч МЛг (и), из которой изложенным ранее') способом получим рекурсивное определение некоторой одноместной функции [(и), с помощью которой предикат Я(и) изобразится в виде ! (п) = О. [Для того чтобы можно было сформулировать это определение, существенно выполнение соотношений т (т, Й) -'т; 7., (т) т при т чь 0; 31 (а, р) ( р'.1 Сформулировав рекурсивное определение предиката С(п), мы легко получим изображения понятий т е р м а и ф о р м у л ы с помощью некоторых рекурсивных формул: именно, высказывание <число п является номером некоторого терма» изобразится формулой С(п)й )(10~и), а высказывание «число п является номером некоторой формулы» изобразится формулой С (п) й 10 ~ и.
Если определение предиката С(п) изменить, допустив, чтобы в пункте а) число п само могло быть простым числом, большим или равным 7, или, выражаясь формально, если дизъюнктивно к) См. с. 277 и далее. эп ФОРмАлиз»пия АРиФметического ФОРмАлизмл 377 378 выход зл»хм«и тио»ии док»з«тгльств >гл т добавить в члене 21>(п) выражение Рг(п)йигв7 и всюду, где стоит какое-либо выражение С(>), написать вместо него С',(1), то получится рекурсивное определение некоторого предиката Я>(и), который для любого п выполняется тогда и только тогда, когда оно является номером некоторого к в а вите р ма или некоторой к в а з и ф о р м у л ы, т.
е, такого выражения, которое либо само является термом или формулой, либо получается иэ терма или из формулы в результате замены одной или нескольких свободных индивидных переменных связанными. Формула С, (и) й ) (1О > и) изображает высказывание «число и является номером некоторого квазитерма», формула Я>(п)й10)ив высказывание «число и является номером некоторой квазиформулы». С другой стороны, если мы в пункте а) определения предиката О(и) оставим только условие п — 2, а кроме того, исключим пункт в) [так что вместо формулы Л>(п) будет стоять равенство п=2, а формула Я»(п) вовсе выпадет из дизъюнкции 3)д(п) ~/... ... '>7'91>(и)1, то придем к некоторой рекурсивной формуле 45«(п), которая изобразит высказывание «число п является номером некоторого терма или некоторой формулы без свободных переменных».
Так как в формализме (2 ) всякий терм без свободных переменных является выражением, определяющим некоторое число (т. е. выражением, формализующим однозначное определение некоторого конкретного числа), и так как и обратно — всякое такое выражение в (2„) является термом без свободных переменных, то для формализма (Х„) и для рассматриваемой нами нумерации свойство числа и быть номером выражения, определяющего какое-либо число, изображается с помощью рекурсивного предиката С, (п) й ) (10! и).
Таким образом, формализм (У ) удовлетворяет условию, которое ранее в этой главе') мы обозначили посредством в*). Еще одна интересная модификация определения предиката С (и) получается, если опустить дизъюиктивный член 8(» (и), а вместо 'Л>(и) взять формулу и=2 >/ (2! пйРг(п(и, 2)) й и==14). Эта модификация дает нам рекурсивное изображение понятий «формула без формульных переменных» и «терм без формульных переменных».
С помощью формулы 6(и), использованной нами при определении предиката С(и)'), мы теперь легко получим рекурсивное изображение высказывания «число и является номером некоторого ') См. с. ЗЗЗ. «) См. с 373. явного определения». Сначала мы представим это высказывание в виде дизъюнкции «число и является номером явного определения некоторого функционального знака или число и является номером явного определения некоторого предикатного символа».
Для того чтобы по возможности кратко записать изображения обоих членов этой дизъюнкции, мы обозначим посредством 6>(п) следующую рекурсивную формулу: Ч>у(у()>(п)й)>(и)~у — »т(п, у)=2.1»<„+»> м>„>), которая при п~2 выражает тот факт, что в разложении и на простые множители фигурируют все простые числа от 1»м>„> до 1»м„включительно и имеют при этом степени 2 1>„2 (»„... ..., 2 1»сх>„»>пм»+» соответственно. Тогда высказывание «число и является номером явного определения некоторого функционального знака» изобразится посредством формулы 70,11'ьь«> 13'оь«>й45(т(п 5))й~(10~т(и 5))й Зх(х(ийт(и, 4) =5 хйт(и, 5) =Х>(х) й6(х) й6>(х)), а высказывание «число п является номером явного определения некоторого предикатного символа» изобразится формулой и = 160 7»ы»> 1!" оь«> й Ю(т(п, 4)) й 10 ~ с(п, 4) й Зх (х п й т (п, 3) = 70.
х й т (п, 4) = Х> (х) й 6 (х) й 6> (х)). Теперь из подлежащих рассмотрению рекурсивных определений, требующих в формализме (У„) нового по сравнению с формализмом, рассмотренным в гл. 1>7, подхода, остается только определение предиката «число и является номером формулы, получающейся из формул ()>;) и (1>,') в результате подстановки вместе с возможными переименования каких-либо связанных переменных». Чтобы сформулировать это определение, мы сначала введем предикат Ч',(3), с помощью которого, используя функцию о(а, 6) и ее обращения ') о,(и) и о,(и), изобразим отношение между двумя квазитермами или квазиформулами, состоящее в их совпадении с точностью до обозначений связанных переменных.
Это может быть сделано аналогично тому, как мы ранее с помощью предиката Ч'>(3) изобразили отношение между двумя формулами, состоящее в том, что одна из них получается из другой в результате переименования некоторой связанной переменной в области действия соответствующего квантора').
') См. с. 272. «) См, с, 289 — 290. 379 ФОРМАЛИЗАЦИЯ АРИФМЕТИЧВСКОГО ФОРМАЛИЗМА 378 выход зА РАмки твоеии докАзАтвльств [ГЛ Р Рекурсивное определение этого предиката Ч',(з) получается с учетом того, что для любого числа п он должен выполняться тогда и только тогда, когда выполняется (:»(о,(з)) й(О«(О»(з)) и, кроме того, имеет место один из следующих случаев: а) О,(з) =О,(з); б) О,(з)=-25 а р', О,(з)=25 а 1», где а — делитель числа 4, а р и 1 — простые числа, ббльшие или равные 7, рч~1 и з(«(О,(з), р, 1) =О,(з); в) при я~2 имеет место равенство Р(О,(з), й)» Ф(о«(з), й), а при 3(й(з выполняется условие Ч7»(О(Р(од(З), 74), Р(О«(З), й))), А теперь с помощью рекурсивной формулы Ч', (з) можно рекурсивно изобразить высказывание «число п является номером некоторой формулы, получающейся из формулы ((4,') или из формулы (144) в результате подстановки вместе с возможным переименованием каких-либо связанных переменныхж Действительно, это высказывание равносильно следующему." «Существуют числа и и О, являющиеся номерами некоторых формул 6 (а) и 8 (а), которые содержат переменную а и не содержат переменной х, не имеют общих связанных переменных и отличаются друг от друга разве лишь обозначениями связанных переменных; эти числа и и О меньше числа п, являющегося номером одной из формул 6(а)-Р6(14„8(х)), 16(р 8(х))-Р)4„8(х)=О».
По этой формулировке мы получаем следующее формальное изображение этого высказывания с помощью формул (О(п), Ч',(з) и функции 81*(т, й, 1): Чи=(О (и(ай О( ай С(и) йй(п) йз(«(и, 14, 2) ~ и йз1*(О, 14, 2) ~вйз1«(и, 7, 2) =ийз1«(О, 7, 2) =О й 47'г(г(пйЗ-=.г- 81«(и, 1»„2) =и )/ з(«(О, (»„2) =О) йЧ« (О(и О)) й(п 80.7«, 11Я'(и, ы,гэг 'ы ' ° и) ~7 а — 5О. 7з М (, 14, ж 7 4 < ' ~4' 75 11М Ц»И7~~ ~Р'14' и, 15»ц Но по внешнему виду этой формулы легко заключить, что она переводима в некоторое равенство вида ((и) = О, где ((п)— одноместная рекурсивная функция.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
