Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 81
Текст из файла (страница 81)
Последнее соглашение изменяет прежнее изображение функ. циональных знаков, поскольку функция 5 Й, ... Й', у р " которой Йы ° ° Й, , суть попарно различные простые числа, ббльшие или равные 7, для нашей нынешней нумерации только тогда является изображением какого-либо функционального знака, когда либо г= 2 и пара простых чисел Й, и Й, совпадает с 11 с 11 н 17, либо простые числа Й,, ..., Й, совпадают с !он, !он+„... , причем и является номером некоторого терма, содернэс-1 хпеего г (и не больше) различных свободных индивидны р- менных. (Этот терм может в свою очередь содержать оди н или несколько явно определенных символов; но в этом случае опре- деляющее выражение любого из этих символов будет иметь номер, меньший номера данного терма.) изоб ажений Аналогичное ограничение справедливо и для изображени предикатных символов функциями вида 70 Й', Тем самым нумерация формализма (ЕР) по существу закон- чена.
Остается только условиться относительно номеров некото- рых конкретных переменных, которые мы возь возьмем теми же, что ') Подобного рода способ задания явных опр д оп е еленнй был впервые прнменен Р. Ккрнэпом я его кннге: Са1 пар ГС й у ГС ьо 1зсйе 3 п)эх бес ргяс е (см. с. бэ). Этот способ — с нзэестной моднфнкэпней — распространен н этой книге н ня рекурсивные определения. 371 .ЗТО ВЫХОД ЗА РАМКИ ТЕОРИИ ДОКАЗАТЕЛЬСТВ >гл ч ФОРМАЛИЗАЦИЯ АРИФМЕТИЧЕСКОГО ФОРМАЛИЗМА и раньше. Так, в частности, для переменных а, Ь и с мы снова возьмем номера 14, 22 и 25; для переменных х, у и е — номера 7, '!1 и 13, а формульную переменную А с одним аргументом мы изобразим функцией 10 7'. Построенная нумерация формализма (7„) является взаимно однозначной.
Это означает, что не только каждое выражение из (2„) имеет единственный вполне определенный номер, но и что номера двух отличных друг от друга выражений из (7.„) всегда различны. В этом можно убедиться точно так же, как мы это сделали ранее для нумерации исчисления предикатов '). Специальное рассмотрение требуется только для того, чтобы показать, что номера предикатных символов с аргументами отличаются от номеров формульных переменных, а также что номера явно определенных функциональных знаков и предикатных символов отличаются от номеров символов +,, =, ~ и (. Но мы это ,сделали уже при самом выборе нумерации').
Если в качестве номера последовательности выражений, имеющих номера и„..., п„мы возьмем число (аа». !З,а В точности так же, как это делалось в случае нумерации для исчисления предикатов, — то имеющаяся у нас нумерация выражений из (2„) даст некоторую нумерацию конечных последовательностей выражений из (Е ). в) Проверка условия б,) для формализма (Х„) и построеыной для него нумерации. А теперь мы убедимся, что выбранная нами нумерация удовлетворяет условию б,) и трем сформулированным ,выше») условиям на выводимость.
Рекурсивность изображения отрицания очевидна. В самом деле, функция е(п), которая изображает номер отрицания формулы в его зависимости от номера самой этой формулы,— это попросту функция З.п. Далее, легко определить такую рекурсивную функцию д(й, 1), которая будет изображать в зависимости от 1 и 1 номер выражения, которое получается из выражения с номером 1 в результате замены переменной а цифрой 1. С этим определением мы свяжем определение некоторой другой функции з!а (т, й, 1), которая соответствует введенной ранее (при рассмотрении исчисления предикатов) функции 31>(т, й, 1) ') и обладает тем свойством, что ее значение для любых цифр >и и 1, являющихся номерами выражений из (2 ), и для каждой цифры 1, являющейся номером какой-либо индивидной перемен- В См.
с. 269 а «елее, ») См. с. 367 — 369. а) См. с. 364 — 366. ») См. с. 288. ной или формульной переменной без аргументов, представляет. собой номер того !необязательно принадлежащего формализму (Хм)1 выражения, которое получается из выражения с номером >и в результате замены переменной с номером 1 (всюду, где она в это выражение входит) выражением с номером 1. Определение этой функции будет только незначительно отличаться от определения функции 31,(и, й, 1). Именно, оно дается с помощью следующего разбора случаев: «Если т=/г и й=>) р, где д — одно из чисел 1, 2 или 10' а р — простое число, большее или равное 7, то 3!» (и, /г, 1) = 1, Если и=2' 5 и, где и — составное число, не делящееся ни на одно из чисел 2, 3 и 5, то 31»(т, й, 1)=2" 5 П )ам'ы<" '> А '>.
Если т=д 25 р', >) является делителем 4, а р — простое число, большее или равное 7, то 3!» (т, и, 1) =4 25 (31(р, й, 1))»>'<' " '>. Если т=3 и и п~О, то 3!'(т, /г, 1)=3 31» (и, Й, 1). В остальных случаях з(е (и, й, 1) =т». Функцию З()с, 1) с нужными нам свойствами мы получим из функции 3! (>п, Й, 1), пОлОжиВ д (Й, 1) = 3!» (/г, 14, 2 3'). В дальнейшем мы еще воспользуемся функцией з(а (и, й, 1). Здесь же мы заметим, что если цифра >и является номером некоторого выражения из (Х„), а цифра 1 является номером какой- либо индивидной переменйой, то формула 31*(п>, 1, 2) ~>п рекурсивно изображает тот факт, что выражение с номером >и содержит переменную с номером 1.
Замечание. Что касается изображения рекурсивныхфункций в формализме (Е„), то для этих функций в (2„) могут быть взяты те же самые сймволы, которые ранее использовались нами в рекурсивной арифметике. Однако надо обратить внимание на то, что арифметическое изображение такого функционального знака в рамках нашей нумерации дается, если этот знак не принадлежит к числу основных, с помощью некоторого явного апре" '372 ВЪ|ХОД ЗА РАМКИ ТЕОРИИ ДОКАЗАТЕЛЬСТВ 1ГЛ Ч ФОРМАЛИЗАПИЯ АРИФМЕТИЧЕСКОГО ФОРМАЛИЗМА 373 деления, которое, вообще говоря, не является определением его ъ рекурсивной арифметике, а строится с использованием )г-символа.
Теперь, после того как для формализма (У„) оказались выполненными два из содержащихся в условии б,) специальных требований '), мы должны еще рассмотреть требование, относящееся к существованию рекурсивной формулы ю(т, и) (не содержащей отличных от пг и и переменных), обладающей тем свойством, что любая цифра и является номером какой-либо выводимой в (У ) формулы тогда и только тогда, когда можно указать такую цифру и1, что истинно отношение е(п1, и). Для формализма (У ) и для введенной нами нумерации выполняется не только это только что сформулированное требование, но и — аналогично тому, как это имело место в случае исчисления предикатов, — более сильное, содержащееся в допущении б,) условие '), что с помощью некоторой рекурсивной формулы кО(ПГ, П), НЕ СОДЕРжаЩЕй ОТЛИЧНЫХ От И И а ПЕРЕМЕННЫХ, МОжЕт сыть изображено высказывание «число т является номером некоторой последовательности выражений, являющейся выводом выражения с номером а».
Для доказательства нам потребуется некоторая модификация рассмотрения, проведенного ранее для формализма исчисления предикатов с включенными в него цифрами и функциональными знаками. С этой целью нужно в первую очередь четко представить себе различия, имеющиеся между средствами формализма (У„) и средствами ранее рассматривавшегося формализма. Прежде всего, важное различие заключается в том, что понятие терма и формулы в формализме (У ) нельзя сформулировать в отрыве друг от друга, потому что свойство выражения 1! 6(х) быть термом зависит от того, является ли формулой выражение г!(с). Следовательно, рекурсивное определение преднкатов «число и является номером некоторого терма» и «число л является номером некоторой формулы» мы должны сформулировать одновременно.
Но для этого нам не потребуется одновременная рекурсия для двух предикатов; будет достаточно дать только рекурсивное определение предиката «число а является номером некоторого терма или некоторой формулы», причем мы воспользуемся тем обстоятельством, что в силу свойств нашей нумерации (У ) число, удовлетворяющее этому предикату. является номером некоторого терма, если оно не делится на 10, и номером некоторой формулы, если оно делится на !О. Другое существенное отличие заключается в добавлении схемы явного определения, а также тех соглашений, которые были ') См.
с. 354. 4) бм. с. 339 и далее. приняты относительно способа изображения явно определенных символов ') в рамках рассматриваемой нумерации. Своеобразное осложнение возникает также вследствие того, что при подстановках вместо формульной переменной в формулах (р',) н (р„'), т. е. в формулах А(а)- А(п«А(х)) и )А(Р, А(х)) — »)4„А(х)=0, мы оказываемся вынужденными одновременно с выполнением подстановки производить (во избежание коллизий между связан- ными переменными) еще и некоторые переименования связанных переменных, подобно тому как это делалось при подстановках вместо формульной переменной, входящей в состав е-формулы'). Модификации, вызванные указанными обстоятельствами и не- обходимые для построения рекурсивной формулы к)(пг, и), ка- саются, во-первых, рекурсивного определения формулы С (и), изображающей предикат «число и является номером некоторого терма или некоторой формулы», во-вторых, рекурсивного изобра- жения предиката «число и является номером некоторого явного определения» н, наконец, рекурсивного изображения предиката «число а является номером некоторой формулы, получающейся из формулы (14!) или формулы ()4,',) в результате подстановки (быть может, в сочетании с переименованием связанных перемен- ных)».
Мы рассмотрим подходы к этим определениям подробнее. Чтобы определить формулу Я (и), мы сначала введем следую- щие обозначения. Пусть Х! (и) = М1 и (е„~ и, к(л так что при п--2 простое число 1»м(п) является наименьшим простым делителем и. Далее, обозначим через 6 (и) формулу ).1(п)>ЗА к)(х(х(Л(п)-»(1» ~м — »(а„„/п))й Ух[К -'и-+-(х+)!(п)==.)г(п) 81~()!(и), 2 (ек,а, 2)чь)г!(и))], которая в силу своей структуры изображает некоторый рекурсивный предикат. Число и, для которого )г!(и) является номером некоторого выражения к)1 из (У„),удовлетворяет этому предикату тогда и только тогда, когда, во-йервых, п является произведением степеней некоторых, следующих друг за другом простых чисел , наименьшее из которых больше 7, и, во-вто- 1+! к 1+к рых, в 21 входят те н только те свободные переменные, номерами которых являются числа 2. (»„2 )»4, ..., 2 1»з+г. !) См.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
