Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 59

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

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

Выполнение этого условия в нашей нумерации обеспечивается тем, что различные типы переменных и символов отличаются друг от друга степенями простых чисел 2, 3 и 5, входящих в качестве множителей в номера, представляющие те или иные выражения илн соответственно функции. Так, выражение, состоящее из какой-либо формульной переменной с аргументами или без них, характеризуется тем, что номер его делится на 10, но не делится ни на 20, ни на 25, ни на 30; выражения, являющиеся отрицаниями каких-либо других выражений, и только такие выражения имеют номера, делящиеся на 30; выражение, являющееся конъюнкцией двух других выражений, всегда имеет номер, делящийся на 4 и на 5, но не делящийся ни на какую более высокую степень чисел 2 и 5, а также на число 3; выражение, начинающееся квантором всеобщности, область действия которого распространяется на все это выражение, имеет номер, делящийся на 50, но не делящийся ни на 4, ни на 3.

Аналогичным образом характеризуются дизъюнкции, нмпликации и эквивалентности, а также выражения, начинающиеся квантором существования. Функциональный знак с аргументами имеет номер, делящийся на 5, но не делящийся ни на 2, ни на 3. Номера цифр характеризуются тем, что они не имеют простых делителей, ббльших 3. Количество аргументов выражения, состоящего из функционального знака или формульной переменной с одним или несколькими аргументами, может быть охарактеризовано как число тех простых множителей, которые входят в номер этого выражения в степени, большей единицы. (Номер формульной переменной без аргументов не содержит ни одного простого множителя в степени, большей единицы.) У любых двух различных свободных или соответственно связанных индивидных переменных, а также у любых двух различных формульных переменных с одним и тем же числом аргументов и у любых двух функциональных знаков с одним и тем же числом аргументов номера отличаются набором входящих в них простых множителей.

В номера различных цифр множитель 3 всегда входит в различных степенях. Из сказанного вытекает, что два выражения рассматриваемого формализма, отличающиеся друг от друга знаком внешней операции, всегда имеют различные номера, 'отсюда индукцией по числу знаков, содержащихся в рассматриваемом выражении, получается, что два любых различных выражения имеют различные номера. При этом надо учесть то обстоятельство, что все арифметические функции, которые, согласно нашим определениям, соответствуют составным формальным выражениям, устроены таким образом, что их значения оказываются больше значений АвиФметизлиия исчисления пггаикАтов азличным значениям аргументов или соот- их а г ментов и что ра значе- ветственно систем аргум н Р У ментов всегда отвечают различные В ф тические функции, сопоставленные ым о мальным выражениям, монотонно возрастают и по каждому из своих аргументов 1при сох н ных аргументов).

ой а ифметики. Теперь б) Вспомогательные средства рекурсивно ар, ак ст кт ные свойства выражений исчисления Р РУ УР предикатов и отношения м жду е этими выражениям в арифметические отношения ду меж изоб, ажающими эт ния номерами. В частност, у и мы видим, что для непосредс твенно тов и отнов вы аженнй исчисления предика определяемых своиств р й перевод дается шений между этими выраж ажениями а, и, метически о по рекурсивми нкциямн и предикатами. При этом под и аньшет), понимаем функцию, опредесий ю~ж~анов лчемую с помо1цью примитивных рекурси и по в том п е икат мы называем рекурсивным в местный числовои предик ре урсивную фупк- случае, если для него мож у можно казать такую ек бой наперед задан- цию 11ао ..., (, ..., а ) от 1 аргументов, что для лю нап ной си й системы значений аргументов „..., 1 * и ...

и значение 1(п„..., пс) и, ..., и этот равно тогда 0 и только тогда когда для системы ы ..., предикат нстннен. В формализме рекурсивной арифметики любая р ур я ек сивная функция изображает жается некоторым рекурсивным термом'), бо ные переменные взаазличные входящие в него сво дные п причем ра т а г ментам этой функции, а лю- имно однозначно соответствуют аргу б й сивный предикат изображается некоторым рав н бо рекурс 1=0, е 1 — ек сивный терм, а различные входящие в 1 свободные п р е еменные взаимно однозначйо соотв е иката.

И обратно, любое такое равенство, в кообо ная пе еменная изображает некоторый рекурсивный предикат. области рекурсивной арифметики: сведениями о рекур тех или иных чункци, функций а также о переводимости формул в равенства вида 1=0 ') См. т. 1, с. 332. 333, с. 390 вннву н с. 400, 401. в) См. т. 1, с.

390 в) См. т, 1, с. 331. 40гс МЕТОД АРИФМЕТИЗАЦИИ М!'ТАМАТРМАТИКИ !ГЛ ГТ [называемые рекурсивными формулами]'). Нам потребуются, в частности, следующие факты: 1, Рекурсивными являются: функции а+Ь, а.Ь и а', функция зппп, ноторая равна 0 при И=0 и 1 в остальных случаях; функция ядп и, которая равна ! при п = 0 и 0 в остальных случаях; функция а — Ь, равная 0 при а~Ь, а при а)Ь удовлетворяющая равенству а=Ь+(и — -Ь); функция б(п), совпадающая с и — -1; функции п(а, Ь) и р(а, Ь), которые при Ь чюО дают неполное частное н остаток от деления а на Ь и характеризуются условиями (и, Ь) Ь+Р(а, Ь), р(а, Ь)с- Ь (при Ь ~0), п(п, 0) О; функция 1»„которая дает и-е (и =.=О) простое число в нумерации простых чисел по их величине; функция т(т, )г), значение которой при т ныл равно показателю степени, с которым число 1»ь входит в разложение т на простые множители, а при т*=О равно 0; функция й(т), значение которой при т) 1 равно номеру наибольшего простого делителя числа гп, а в остальных случаях равно т.

Кроме того, с помощью рекурсивной функции о(а, Ь) и ее обращений а,(п) и а,(п) мы получаем такую [начинающуюся с пары (О, 0)] нумерацию числовых пар, при которой паре (О, с) предшествуют те и только те пары, у которых оба члена являются числами, меньшими с'). ') Зго употребление термина «ренурснвная формулаз, которого мы в дальнейшем н будем придерживаться, является несколько более узким, чем употребленне его в смысле определения, приведенного а гл. УП т.

! на с, 399, з) См. т. 1, с. 395. Вместо использованного здесь способа нумерации можно взять н такой, прн котором порядок будет устанавливаться сначала цо наибольшему нз чисел, входящих в пару, а затем лехснхографнчесхн. Прн атом способе паре (О, с) тахже предшествуют все ге пары (а, Ь), у которых оба числа а н Ь меныне с. Фуннцня а'(а, Ь), которая описывает зту нумерацию, н ее обращения а,*(л) н а, (л) могут быть оаределены с Помощью фунхцнн [!' л], ставящей чнслу и в соответствие наибольшее нз чисел, квадрат которых не превосходит л (ренурснвное определение втой функции ем. в т, ! 773 АРИФМЕТИЗА ИИЯ ИСЧИСЛЕИИЯ ПРЕДИКАТОВ В ез льтате комбинирования Рекур сивных нкций всегда У 2. Если 1(а) — рекурсивный терм, то и-членная сумма х йй 1 х, авно как и ~ч, 1(х) и и и-членное произведение ищи «Си б ть изображены некоторыми рекурсивными 1(х), могут ыть и и термами.

к сивной является, например, функ- Вследствие сказанного рекурсивно ма ая и и п«О значение О, а при п ция, принимающая 1 р ожителей входящих в разравное числу р азличных простых множи быть п едставлена выражением ложение п, так как она может ыть п ~ зяп(ч(п, х)). и<и мы будем обозначать через (и) Вту Ункц 3. Рекурсивными я-яют,'я„'.б . .., я равенством (а — Ь) 4- + и изображается равенством з|п(Ь вЂ” ' Ь вЂ” а) =0; и =0; редиката ' Ь, котоРый изо авенством а †' Ь О' . 'Ь, который изо ражается а я на Ь или соответственно Ь делит п, п с т ы м который зобракатов в езультате применения к ним я п едикаты снова являющиеся рекурсизквивалентносги получ р ости, от ицание предиката, из ра вными.

В части, р ством 1 О, изображается ра авен ством здп 1 =, конъюнк З=О и 1=0, изображается дикатов, и зображаемых равенствами З= ' и здб), н следуюнгнх ренурснй1 Ь) (а ! ),з) .зйн РЬ а)+(а~-~- +Ь) ' зйн (Ь (л) = (л — [) л] ) Я (([ « †] (([ )«" ]з +[)гл]) л) л +[)' "]) л)+ [Р „-]., (([Р' ]'+[)г ]) 'л)+ [Р, ], [)г ]) ) (л ([)«л]з+[)' л])) ' зйп (( л + имании мы уже употребляли чая гам с ИОмОщью другого Определенна. Раньше(см. т.

1, е. 496), хотя он еводнлся гам с и 276 »гиемгтизлпия исчисления пгелик»тое 274 метод»еиемгтизхцпи мвт»м»тем»тики [гл ш равенством 6+1 О, а их дизъюнкция изображается равенством В 1=0. 5. Если $ (а) — рекурсивный предикат (который, кроме а, может зависеть и от каких-нибудь других аргументов), то высказывания «для всех чисел х, меньших и, ямеет место я)(х)» и «существует число х, меньшее л и такое„что имеет место (() (х)» представляют собой рекурсивные предикаты от входящих в них свободных параметров.

То же самое будет верно и в том случае, если в рассматриваемых высказываниях заменить требование: «х меньше и» требованием: «х не превосходит и». Замечание. Отметим, что в обоих только что приведенных высказываниях переменная х не является параметром, тогда как переменная и входит как параметр. Далее, для любого рекурсивного предиката ф (а) можно указать такой рекурсивный терм, который изображает функцию М(п'4) (х), т.

е. функцию, значение которой (для любой системы »(» значений фигурирующих в 7 (а) параметров) равно наименьшему из чисел х, не превосходящих и и таких, что $ (х) имеет место, а в случае, когда таких чисел нет, это значение равно О. б, Если в выражении для рекурсивного предиката (заданном словесно или с помощью какой-либо формулы) мы заменим один или несколько его аргументов рекурсивными функциями, аргументы которых частично или полностью могут быть идентифицированы с аргументами этого предиката, то получившийся прн этом предикат тоже будет рекурсивным. 7. Если рекурсивный предикат изображается равенством 1=0 с рекурсивным термом 1, то он изображается и равенством здп1=0, причем терм зйп1 для тех систем значений аргументов (свободных переменных), для которых этот предикат выполняется, принимает значение О, а для прочих — значение 1.

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

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