Министерстве высшего а среднего специального образовашя РСФСР
МОСКОВСКИЙ ИНСТИТУТ ЭЛЕКТРОННОГО МАШИНОСТРОЕНИЯ
Ю.И.Ыашм
ЛЕКЦИИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ
Часть П
Учебиое пессбие для студентов
специальности 0647
Рекомендовано Редссветом института
в качестве учебного пособия
Москва - 1974

Содержание
§ I* Введение. Интуитивная вычислимость.
§ 2. Частично рекурсшвные функции.
§ 3. Примеры рекурсивных функций*
§ 4* Перечислимые множества.
§ 5. Формализация аржфметикш (результаты).
§ 6. Арвфметвзация формализма (регудьтаты).
§ 7. Теорема Геделя о неполноте.
§ 8. Формализация арифметики (доказательства).
§ 9. Нумерации.
§ 10. Арифметизация формализма (доказательства).

§ I. Введение. Интуитивная
1*1. Мы продолжаем формализованное ошсапе математики.
Основным объектом первой части курса бндо ^тематическое
локаватедьство: было показано, что его подходящим формаль-
формальным аналогом является понятие вывода в языке, после чете
самые интересные результаты утверждали невыводимое» седер-
жатедьвнх математических утверждений (например, гнвотеэы
континуума).
Основным объектом этой второй части курса будет детер-
детерминированный процесс вычисления, или переработки нечисловой
информации, короче, алгоритм. Будет построено подходящее
формальное описание алгоритмов (точнее, результатов их
действий), и саше интересные результаты окажутсн утвержде-
утверждениями о несуествовании алгоритмов, вычислимой содержательно
списываемые функции.
Обе теория - доказательства и вычисления - могут доволь-
довольно длительное время излагаться независимо, и мы предпочли
именно такое изложение, хотя оно не соответствует историчес-
историческому ходу открытий. Когда же техника обеих теорий окажется
уке достаточно развитой, можно будет эффективно применять
каждую из них для исследования другой.
В этом параграфе мы наметим основные опорные точки тео-
теории вычислимости на совершенно неформальном уровне строгости,
который можно назвать йиэическим. Характерной чертой нашего
подхода будет апоеляция к интуитивному представление читателя
о том, что такое алгоритм, пользуясь которым очень удобно
объяснить структуру основных понятий.

Однако при формализации этих понятий в следующем параг-
параграфе мы дадим точное описание не алгоритмов. а результатов
их работы, ю есть вычислимых функций. С нашей точки зрения,
понятие алгоритма слишком многс теряет при любой формализа-
формализации, тогда как понятие алгоритмической вычислимости, насколь-
насколько мы мокем судить, не теряет ничего существенного.
1.2. Введем несколько простых основных понятий. Пусть
Л, J/ - два множества. Частичной функцией (или отображе-
отображением) из X в У мы будем называть любую пару (^>(|), | ) t
состоящую из подмножества ^D)с л и отображе-
отображения ¦J.'ZYSJ—*-X • Здеоь "^(/J называется об-
областью определения J ; / определена в точке -с *• JC ,
если д; е- "^C/J I / нигде не определена, если "^(/)
пусто.
Через 2. = j I, 2, 3, ... j будем обозначать мно-
множество натуральных чисел, исключая нудь. Если к ъ / ,
через (Z*/ мы обозначим /г -кратное прямое произве-
произведение Л* на себя, то есть множество векторов (х, *^) ,
*• е z . удобно считать, что B*f - множество,
состоящее из одного элемента. Налил основным объектом будут
частичные функции из (Z*I" в (?*JK для различных
/wt n .В следующей ниже классификации этих функций по
степени их вычислимоств под слогом "программа" читатель
мсжет представлять себе программу для универсальней вычис-
вычислительной машины, написанную без учета ограничений на время
и память. Подразумевается, что каждая программа для вычисле-
вычисления функции содержит специальное "пустое место" для ввода
очередного значения аргумента.

1.3. Основное определение, а) Частичная функция
is (л* )™ г (г* "V" , » *о называется вычислимой,
если существует такая "программа", что при псдаче на ее
вход вектора xzfz*)'" мы получим на выходе
*) , если jc е- v
О , если х- </' i
(Здесь О - просто указатель того, что ¦/ яе определена
в X ; можно было бы разрешить в этом случае подучить на
выходе что угодно не из (Я*)*" ).
б) Частичная функция f из (гг*)"' в {¦?*) '
называется подувычисдамой.*если существует такая "программа",
что при подаче на ее вход Я- < (z J мы подучаем
на выходе ffxl * если х ^ х-^//// ; получаем на
выходе 0 или же программа работает бесконечно долго, если
В частности, вычислимые функции псдувычислимы. а всюду
определенные полувычислимые функции вычислимы.
в) Частвчнан функция ¦/ называется абсолютно иевычис-
лимой, если она не удовлетворяет условию б) и тем более а).
1.4. Пояснения, а) Из этих трех понятий основным явля-
является подувычислимссть. ибо вычислимость сводится к нему.
Действительно, для выделения вычислимых, функций из полувычис-
1ИЫЫХ мохвс поступить так.
Пусть X <¦ J два множества. Назовем характеристи-
ч-;сксй функцией подмножества X в У такую функцию

У —*¦ J? *" ,ч*о
(jc) Л ''^ "Х
[_ 2, если х/Х
Заметим, что Z^ определена всюду.
Теперь пусть f - полувычислимая функция ю(?*
в (ё*)"" * Если она даже вычислима, то вычислима
и характеристическая функция ее области определения
к вычисляющей * программе нужно добавить инструкции
"переработать 0в2,ане0в1и подать на выход".
Наоборот, если вычислима Х~ъ(/> ' то гычислима и г '•
перед программой, полувычисляющей / , нужно написать
программу, вычисляющую Х&/> • и подавать на выход
сразу 0, если X-*v/y (х) - 2 » кйл передавать
в программу для / , если /-ъг/i (х> "" ^
вычислима ф^> / полувычислима и
полувычисляма (и значит,
автоматически вычислима, ибс
всюду определена).
Правую часть этой импликации мы выберем в качестве формали-
формализации понятия вычислимости, когда полувычислимость будет
формализована.
б) Существуют абсолютно недычислимые функции, действи-
действительно, каждая программа - зто конечный текст под коночным
алфавитом, так чте множестве программ счетно, тогда как
множество всех функций 2 —^ Z. несчетно.
(Критику этого рассуждения см. ноже).

Конкретный пример абсолютно невычисджмсй функции.
Рассмотрим язык арифметики Lt Дч. , списанный в
главе I. Представим себе список всех замкнутых формул этого
языка, записанных, скажем, в лексикографвческом порядке
(алфавит предполагается конечным и упорядоченным). Определим
функцию 4 соглашением
I, если а: -я формула списка истшнна в
стандартной интерпретации;
не определена, если tC -я формула ложна.
функция /(к ) абсолютно навычисД|||*я (теорема Тарсжого).<
Иначе говоря, нельзя распознать (хотя бн в принципе)
все теоретико-числовые теоремы, написав одну (хотя бн очень
большую и сложную) программу для их распознавания по давно!
формулировке.
Доказательство этого результата, конечно, требует гораздо
более глубокого анализа понятия вычислимости.
в) Существуют подувычислимые, но не вычислимые функции.
Сначала привело:, характерный пример полувычжсляющей" программы.
Рассмотрим функцию / и г j / , определенную
через задачу Ферма.
j 1, есла существуй х,у,з? е- ?.
\ с условием х" ¦+ ук "¦«¦ я**
! *
{ае определена иначе
Вот nporpauua, полуаычислицай 4 : после тоге, как
яа вход подано /t , .-ttг-С5им1Ь вектора (Х,У.Ж) в
6

лексикографическом порядке и проверять для каждого вектора
условие **** + ?*!* * *"** . Если оно
выполнено, подать на вход I. Иначе, переходить к следующему
Значит, л полувычислима. Но мы дс сих пор не знаем,
вычислима ли -/ . Гипотеза Ферма состоит в том, что /'
нигде не определена (и,значит, вычислима!). Самые сильные
у
теоретические результаты, известные относительно ¦/ , -
так называемые критерии Кумиера, Вифериха, Вандивера и др. -
можно рассматривать как некоторое приближение именно к дока-
доказательству вычислимости У , а не того, что она нигде не
определена. Поэтому для последующей проверки гипотезы Ферма
для тех или иных значений -/ нужен еще (машинный) счет
(объем которого быстро растет с ростом я. ) для вычисления
/ъ(/) В Т0ЧКв ^ » "сгДв оно ВОЗМОЖНО.
Аналогичную природу имеет пример полувычислимой функции,
которая уже заведено не является вычислимой: установлено,
чте существует такой многочлен P(t> *г, ¦ > **-) с
целыми крэффициентами, что функция.
I, если уравнение Р A, х,} . , **. ) - О
разрешимо с х, > гк е- ? * ;
не определена иначе
не вычислима. Ее полувычислимость устанавливается точне также,
как для функции f , связанной с уравнением Ферма.
1.5. Критика предшествующих доказательств.
Прежде чем двигаться дальше, рассмотрим более критически,
скажем, рассуждение из п. 1Л а). Первое слабое место бро-

сается в глаза: мы не уточнили, что такое программа. Однако
эю не так существенно: при люоом выбранной уточнении прог-
программа должна быть текстом над конечный алфавитом, чтобы
удовлетворять интуитивный представлениям, а таких текстов
счетное множество..Гораздо более сильное возражение состо-
состоит примерно в следующей: на каклм основании мы мохем рабо-
рать с одним уточненной понятия программы? Возмокно, сущест-
существует все возрастающая иерархия точно описываемых " вычислитель-
вычислительных средств", так что для каждой функции из ?* в ? +
можно подобрать свою программу, которая монет вычислять зту
функцию?
Фундаментальный открытием теории вычисления оыло то
обстоятельство, что на последний вопрос нужно дать отрица-
отрицательный ответ. К настоящему времени мы обладаем единствен-
единственным искончати .ьнии формальным понятием, которое выдержало
все проверки на tro соответствие интуитивному представлению
о полувычииьшости, и которое конструируется так:
1.6. Тезис Черча (слабейшая форма). Можьо явно указать
а) семейство простейших полувычислимых функций;
б) семействе элементарных операций, которые позволяют
строить по одним полувычислимьш .функциям другие полувычиедя-
мые функции; с тем свойством, что любая полувычислимая функ-
функция получается за конечное число шагов, каждый из которых
состоит ъ применении одной из элементарных операций к ранее
построенным, либо к простейшим функциям.
1.7. Пояснение. В следующем параграфе тезису Черча
будет придана течная формулировка: простейшие функции и
10

алементарные операции будут заданы явно. С этого времени
начнется точная математическая теория вычислимости. Однако
нам казалось ванным отметить принципиальное значение того
открытия, что семейства таких функций и операций вообще
существуют и могут быть явно указаны, что далеко не очевидно.
Это - экспериментйлышй факт, воэмокно, важнейший из
открытых логикой. Свидетельства в его пользу и его значение
будут обсуждены несколько позже.
§ 2. Частично рекурсивные функции.
2.1. Б этой параграфе мы изложим точное определение
и первоначальные свойства класса функций, который считается
адэкватной формализацией класса полувычислимых функций. Он
будет описан тем опособом, который указан в формулировке
тезиса Черча в § I.
2.2. Простейшие Функции.
1 -• IZ I —~ Z . / ^/. . *<J-- / л*^
¦ */
2.3. Элементарные операции над ча^тиаяими функциями.
а) Композиция (или г оде танов ка). (ha ставит в соответ-
соответствие паре функций / из (Ж+)М в (Ж*)*
мою (Z. / в (Z / . функцию h
из (?_ ) в {Л. )' , которая определяется так:
II

6) Соединение. Эта операция ставит в соответствие <
частичным функциям ? иэ (Z*) в (~Z*)^
О = ',- . ^/'Функцию f//t ... ,/^J из (Z*Г в
)*** которая определяется так:
в) Рекурсия. Эта операция ставит в соответствие паре
функций / иб B1+)*ъ Ж* и Я ив B? +) в 2.
функцию / из (ж*)л*1 в .2^, которая определяетсш
индукцией по последнему аргументу:
vr ^(начальное условие)
мы //с* / (индуктивным шаг)
Область определения "=~&A) описывается также
индуктивно:
12

г) Операция ас . Эта операция ставит в соответствие
частичной функции * из B / в ^ частичную
функцию / из (' Z47* в Z* , которая определяется
так:
Л (*t, .¦ х~. к ' ь ^
для воех /г # хь + , }
В общих чертах /к вводит функции, заданные "неявно",
как зю часто делается во многих областях математики. Три
особенности операции м эаолужлвают быть отмеченными
неиедленно.
Выбор минимального и с /(х, . .л *- , Я / " '
делается, конечно, для обеспечения однозначности функции % .
Область определения / на первый взгляд представля-
представляется иокусственно суженной: если, скажем, > J (*,, jc^^J-
а J(xr> Хь. f) не определено, ш очитаем
л ( х,, * *. ) не определенной, а не равной 2.
Причина этого состоит в желании сохранить интуитивную полу-
/
вычислимость функции А и будет несколько подробнее
прокомментировано ниже (см. п. 2.7 а).
Наконец, все описанные до /И операции, если их
применять к всюду определенным функциям, дают в результате
13

всюду определенную функцию. Для М это, очевидно, не так:
это единственная операция, ответственная за возникновение
чаотитных (*ункпий.
ZA. Определение, а) Последовательность частичных
функции •/ , • , /у называется чаотично рекурсивным
(соотв. примитивно рекурсивным) описанием функции /, " /
если
/, - одна из простейших функций;
/с - для всех / * <3 либо является проотейшей
функцией, либо получается применением одной
из элементарных операций к некоторым из функ-
u"(* ft. /j (соотв. одной иа
элементарных операций, кроме /и ).
б) Функция. / называется частично рекурсивной
(соотв. примитивно рекурсивной), если она допускает частично
рекурсивное (соотв. примитивно рекурсивное) описание.
(Аналогия с опрелелеиием вывода в формальном языке
бросаетоя в глаза и может быть попользована).
2.5. Тезис Черча (обычнан форма).
а) Функция / полувычислима, если и только если она
частично рекурсивна.
б) Функция / вычислима, если и только если /
и Х^,/ частично рекурсивны.
2.о. Использование тезяоа Черча. Прежде чем обе;ждать
,:..1.е аргументы в пользу тезиса Чер"а, укажем, как он
лопользуется г математической практике.
Два основных способа бросаются в глаза при изучении
литературы.

а) Определение алгоритмической веразреиимости.
Пусть имеетоя счетная последовательность математических
"задач" Р Р Р • Предполагается, далее,
что каждая задача имеет ответ "да" или "нет" и что по номеру
л условие задачи Рп выписывается "аффективно". Такая
последовательность Р - (Р*.) называется "массовой
проблемой". Свяжем о ней функцию J иг Z ь Z. :
ie Z+ | Р. имеет ответ "да"]
/ , если i €¦ 5S (f)
Массовая проблема Р называется алгоритмически разрешимой'.
если Дишсши J и / /, частично рекурсивны. В про-
тивном случав Р называется алгоритмически неразрешимой.
Заметим, что в принципе возможно еще различать случаи, когда
только /¦¦*>//) нв яв'яв'ся частично рекурсивной или
когда даже J ив частично рекурсивна. Вторая неразре-
инмос» «щ» "хуже" первой; примеры были указаны в § I.
Еще один известный пример массовой проблемы: проблема
тождества слов в гстпдах. Пусть G - некоторая группе,
at > — . аг € & ~ «eKoiopiie злементы. "Приведенное
слово" о» a, t... , а,г -«о выражение вида
af/ ... af« «и» а-* / ? ,_ * у и если
t'K * 4Л*^ t *о ?Л * ?afr • Расположим все
приведенные слова в алфавитном порядке и поотавим задачу
1 :
"Верно ли, что п. -е слово представляет единичный
элемент группы & ?°
15

"Массовая проблема" ( Рл ) алгоримшчеога разрешена
для одних групп 6 и моментов «, , • ¦ , at и
неразрешша для других (Новшюв. Буж). Функция f эдеоь
воегда частично рекурсивна.
б) Тезис Черча как эвристический принцип» Интуитивно
понятие "полувнчислимооти" представляется более широким,
чем понятие "частичной рекурсивности", и многие задачи о
чаотично рекуроивных функциях становятся значительно легче,
если подставить в их формулировку неформальные представления
и разрешить пользоваться ими в решении. Скажем, формула
е - &гк A * ? )* и алгоритм Эвкдида делают интуитивно
ясным, что функции 1\ ч : *- —*" >^-
J(ь) s п. -й деоятичшй знак разложения
о (м.) я /г-е простое число
вычислимы, тогда как проверка их рекурсивности требует до-
довольно кропотливых конструкций.
Тезио Черча позволяет разбить решение таких задач на
два этапа; I) отыскание неформального решения с использо-
использование»! любых интуитивных алгоритмов; 2) пооледуодя форма-
формализация. Второй этап предполагает мзвеотнув опытность в
отыскании частично рекурсивного описания самых разнообраз-
разнообразных полувычислиыых функций, а тезио Черча дает уверенность
в том, что такое описание оуцествует..
По мере накопления доказательств рекуроивности в литера-
литературе все чаще ограничиваются проведением лишь первого этапа
решения: ярким примером тому служит книга Х.Роджерса "Теория
рекурсивных функций и эффективная вычислимость", М., "мир",
16

1972. К концу лекций ш также позволим себе ряд вольностей
такого рода.
2.7. Аргументы в пользу тезиса Черча. а) Прежде всего,
представляется ясным, что простейшие функции вычислимы.
Далее, элементарные операции, примененные к полувычислимым
функциям, снова дают пслувычислииую функцию: программа,
полувычисляющая ее, без труда компонуется из полувычисляю-
полувычисляющих программ для данных функций. Мы рассмотрим подробнее
только случай м -оператора, оставив легкую конструкцию
остальных трех программ читателю.
В обозначениях п. 2.3. г. пусть / - полувычислимая
функция иэ (.Z. / в .2. •. Для вычисления /л**., , *.. )
будем перебирать в порядке возрастания последней координаты
вектора (х, ,X«J) ,(х,, ¦*» , «?) и вычислять
значения / в них. Если Iх,. ,-*~ ) €<2§/А/, где /f
получается из / применением и -оператора, то программа
для / последовательно вычисляет J (*,, ±П) (J,
>f(xr. ,x*,jf-'h и наконец, /(*¦, z~ ,J / /
Наименьшее такое у , если оно существует, нужно подать
на выход: это будет значение / в точке (*,, х*. )
Если же v не существует или хоть одно из значений /
в точке (xt ,-• ,х* , к) (до достижения У / )
окажется не определенным, то полугычисляющая / программа
либо даст ответ не из Ж - его нужно посла - на выход,
либо будет работать бесконечно долго; но по нашему сог лашению
п- в точке (х, t х\ ) тогда не определена, - такое
поведение программы для я согласуется с определением полу-
внчислимости К
2-1978
17

Из всего сказанного нужно сделать вывод, что частично
рекурсивные функции полувычислимы. Наиболее оильное утверж-
утверждение тезиса Черча состоит, таким образом, в том, что полу-
полувычислимые функции частично рекурсивны (определение вычисли-
вычислимости через полувычислимость мы проото перенесли без измене-
изменений из § I). Как было сказано, это экспериментальный факт.
Экспериментальные свидетельства в его пользу делятся на нес-
несколько классов, которые мы рассмотрим последовательно в под-
подпунктах б) - г).
б) В литературе имеется огромный набор рекурсивных
описаний различных (полу) вычиолимых функций. См., например,
книгу Р.Петер "Рекурсивные функции", II., Ил, 1954. Часть
этого описка мы приведем в следующем параграфе. Имеется
также набор приемов составления рекурсивных описаний, при-
применимых к целым классам (полу) вычислимых функции. Каждый
раз, когда какой-нибудь автор пытался найти частично рекур-
рекурсивное описание (полу) вычислимой функции, это описание
находилось.
в) Тьюринг предложил математическое описание абстракт-
абстрактной вычислительной машины и сильные аргументы в пользу того,
что эта машина является универсальной (то еоть может (полу)
вычислять все (полу) вычислимые функции), детально проанали-
проанализировав характерные черты процесса детерминированного вычис-
вычисления. (Обратите внимание, что мы совершенно не занимались
формализацией процесса вычисления, а только его результатами!).
Оказалось, что класс функций, полувычисляемых машиной
Тьринга, в точности совпадает с класоом чаотично рекурсивных
функций.

г) Черч, Пост, Марков, Колмогоров, Успенский и др.
предложили другие детерминированные схемы переработки инфор-
информации (не обязательно числовой) общего характера. Во всех
случаях оказалось, что при подходящей "эффективной" нумерации
множеств входов и выходов эти способы приводят к такому классу
отображений из Z в Z . который совпадают с соот-
соответствующим подклассом частично рекурсивных функций.
За дальнейшим обсуждением тезиса Черча мы отсылаем
читателя к литературе.
§ 3, Примеры рекурсивных функций
3.1. В этом параграфе будет приведен краткий список час-
частично рекурсивных функции почти все они будут даже примитивно
рекурсивными) и выборка первоначальных приемов доказательств
рекурсивности. В дальнейшем изложении этот список будет по-
пополняться по мере надобности.
Вводя новые функции, мы будем все больше сокращать их
рекурсивные описания, по мере увеличения опыта читателя.
3.2. a) SUm(X,X )*Х, + Хг: (Z *)*-> Z \ Обычное
индуктивное описание Х( ¦*• Хл индукций по второму аргумен-
аргументу таково:
начальное значение (X,-f)'Xf^'f'r SU
выражение К * 1 -го
значения через (к-е)- X, * К * < - (Xt* к)*/
Значит, SUn? получается рекурсией из функций (см. формулы
из § 2):
19

/
Sl/C :
O - SUC ° Ptj' : U? 7
Рекурсивным описанием SOOi является последовательность
/• W ,/>*'/', J ' sue yt'J' J sum
6) sumn (/,,/< , .,/J-/' *> /fc ш и >. з
Так как SUtnH (/,. .. /л ) =
(справа отоит композиция функций i (У/^Z и ооедине-
ния SL/m рг л , индукцией по И получаем,
что эта сумма также примитивно рекурсивна).
3.3. a) Ptof/ (/, , /л /-/,'<
Результат применения рекурсии к функции
, ,<;-<•.
Индукция по >г , как в предыдущем пункте.
3.4. а) X->. / - Z* -~ Z.
20

/- / , если X* г
[ / , если X - 1
Рекурсия применяется к функциям
— Z+ (с)
(Заметим, что л — / зависит от одного аргумента,
должна зависеть от U аргументов, а 9 - от
двух, формула рекурсии превращается в *(<*¦*)*у(«, *?{*))¦
б) /,^/л .. fz+)" -, z+ ^
/ _i / , ] X - ^ , если X, > Хл + f
[ / , если Xf ¦< X, * /
Эта "усеченная разность" получается применением рекурсии
к функциям:
*, - /
Теперь мы в состоянии доказать уже общий результат,
который часто будет полезен:
3.5. Предложение. Пусть г (^i ••• Хл / - многочлен
с целыми значениями, который при всех СX, ¦¦ Хл ) 6 (Ж )
принимает значения ^ / . Пусть далее /f t . /
любые частично рекурсивные функции (от каких угодно аргументов).
2*-1978
21

Тогда композиция *" < ff , • , f*. / является
частично рекурсивной дикцией. Она примитивно рекурсивна, если
// примитивно рекурсивны.
Дзказательство. Достаточно проверить, что F (Х<, ., С )
примитивно рекурсивна.
Если все коэффициенты F неотрицательны, то F
является суммой произведений Xt . Из 3.2. и 3.3. легко
следует, что F примитивно рекурсивны (например, Xt /}
есть композиция ргос/• ( pi'*1 ^ fi^'t f1'3') ).
В общем случае представим F в виде F - F ,
где у F и А - все коэдйящиенты неотрицательны. Из
3.4 б) мы можем заключить, что усеченная разность /- — F
является примитивно рекурсивной функцией; но так как, по
предложению, для всех допустимых значений аргументов
F - F ^ / t эта усеченная разность совпадает с
обыкновенной.
Вот типичная ситуация, в которой мы будем использовать
предложение 3.5. Пусть /, 9 • (Z. *) -> Z * две
частично рекурсивные функции. Предполомш, что нас интере-
интересует множество точек, где J - я . Оно совпадает с мно-
/ и/в ,^
жеством точек, где функция (¦/ - о ) * / принимает
значение I. Последняя функция частично рекурсивна, по предло-
предложению 3.5, и поэтому такое описание часто бывает удоонее
предыдущего.
Продолжим наш список рекурсивных цуккции.
3.6.
22

Рекурсия к J(') = / и * (<, /л ) -- 2.
I а * + +
Аналогично описывается любая функция A Z. —¦ Z ,
принимающая в точке I значение Л , в точках > <2
значение о .
3.7.
^^у fl при /-i
1 [ не определена при / ? <?
Эта функция, конечно, не может быть примитивно рекур-
рекурсивной, потому что она не всюду определена.
Ее можно получить, например, применяя А - оператор
к функции ( Kfj (Kf * *л ) — / , которая прими-
примитивно рекурсивна по предыдущему:
3.8. гет (х,у) -
[остаток от деления у на X
)
если он не нулевой;
X. , если у делится на X .
На этом примере можно продемонстрировать искусственный
прием, полезный при отыскании рекурсивных описании. Напишем
сначала очевидную индуктивную формулу:
I I/* X** л / tf *t it
У
если
I , если г&ш (хч ) =
Нам нужно теперь показать примитивную рекурсивносгь
функции справа, заданной "кусочно".
23

Заметим прежде всего, чтс если определить примитивно
рекурсивную функцию У7 формулой
. I 2 при Z * /
ШУ) ~-*((г*«(М-ф1)% гда Ч>(Ж)А
I I при Z *?
то мы получим
Отсюда находим:
2еи( (/,y*Jj* г St/c (ъет(*, у)) - У (Л, У )¦ sue (чет (х, yf
что немедленно доставляет способ описать fe/n рекурсией.
3.9. Опишем этот прием в достаточно общем виде. Дэпустш»,
что функция /(К, ¦ i ^ ) задана предписанием:
(*,.XX если ^Л, Л А- /
Мы будем считать, что "множества 1-уровней" {/[ = /
попарно не пересекаются. Кроме того, можно считать, что $
принимает значения только I или 2: если это не так, то
нужно заменить У. на ^((^i'^)*^) » гД
Wx) = г при / */ , ^Л- /при / *г .
Тогда
24

Если, скажем, все 9: и % примитивно рекурсивны,
то отсюда видно, что и У примитивно рекурсивна, Заметим,
что в п. 3.8., а также ниже, в пунктах 3.10 и З.П этот спо-
способ нужно применять для доказательства рекурсивности вспомо-
вспомогательной функции, к которой затем применяется рекурсия.
ЗЛО.
целая часть
если ^
, если j|
Очевидно, имеем
4*(х,и
, если
если
I , еСЛИ Si ¦ i * <
Поэтсму можно применить прием, описанный в пи. 3.8 и 3.9.
Ч итателю будет полезно восстановить детали.
З.П. tad{x)= целая часть
xad(i). 1 ¦
Имеем:
гас!(t+i) -- ,
Ыах *¦
25

Прежний прием позволяет показать после этого, что 7аа
примитивно рекурсивна.
3.12. Min (х, у; j max (x, у) .
Доказательство оставляется читателю в качестве упражнения.
§ 4. Перечислимые множества
4.1.Определение. Множество Е <^ (-Z /
называется перечислимым, если существует такая частично
рекурсивная функция ф , что Е =<Г&{У) (область
определения ¦/ ).
Обсуждение в § I и § 2 показывает, что интуитивный
смысл перечислимости Е. таков: существует программа, кото-
которая распознает элементы X , принадлежащие Е. , но, воз-
возможно, не умеет распознавать элементы, не принадлежащие Е .
Позже будет дано другое интуитивное списание перечислимых
множеств, более яснс указывающее на происхождение названия:
это множества, все элементы которых могут быть получены
(возможно, с повторениями и в неизвестном порядке) с по-
помощью некоторой "порождающей" их программы.
Понятие перзчислимого множества, наряду с понятием
частично рекурсивной функции, занимает центральное место во
всей теории. Из дальнейших результатов будет видно, что любое
из них может быть сведено к другому, однако, в доказательствах
необходимую гибкость дает лишь использование обоих понятий.
Начнем со следующего простого факта.
26

4.2. Предложение. Класс перечислимых множеств совпадает
с классом множеств уровней (и даже 1-уровней) частично рекур-
рекурсивных функций.
Доказательство. Напомним, что множеством т. -уровня
(или просто Ш. -уровнем) функции /из (Z )
в -Z * называется множество ? <¦ *Z> (/) t
X е ? <М> /()
Е
а) Пусть Е перечислимс, ? ' ^у' , где
частично рекурсивна. Тогда
? = / I-уровень функции (У- *) * /
Функция (f ~ м ) + / частично рекурсивна в силу пред-
предложения 3.5.
б) Пусть ? I-уровень частично рекурсивной функции
W • Положим
, •
Очевидно, д частично рекурсивна и /z - cr^ (?) ¦
Основной теоремой этого параграфа будет следующее гораздо
более трудное утверждение и его следствия:
4.3. Теорема. Следующие два класса множеств совпадают:
а) Перечислимые множества.
б5 Проекции множеств уровня примитивно рекурсивных
функций.
4.4. Первая часть доказательства. Напомним прежде всего,
что если дано некоторое множество ? с ( Z *)" ' , то
его проекцией ("на перше п. координат") называется множество
F с (, Z J , которое определяется так:

Аналогично определяется проекция "на координаты о номерами
( гг ¦ ' *к)с(*' > HJ"' xtlicM> #1 УДОбно называть кораамер-
ностью проекции. Каноническое отображение проекции ? -*¦ F
также принято называть проекцией; это не может привести к
путанице.
Назовем временно проекции уровней примитивно рекурсивных
функций примитивно перечислимыми множествами.
Первая часть доказательства будетоостоять в установлении
того факта, что примитивно перечислимые множества перечислимы;
вторая - в проверке обратного включения.
Итак, пусть /(*,, Л, С С/
некоторая прмитивно рекурсивная функции, ? - проекция ее
I-уровня на первые /г -координат. A-уровнями можно огра-
ограничиться в силу уже использованного соображения: К -уровень
1 совпадает с 1-уровнем / - (J - к} + 4 . Построим
явно такую частично рекурсивную функци а , что ? =c?foJ
Разберем отдельно три случая, в зависимости от кораз-
коразмерности проекции: /п - О, 1 , или » «2
Случай a) tn - О . Тогда Е - / - уровень J $ ?
перечислимо по предложение 4.2 ) я построена тэм явно).
Случай б) т - / . Положим
9(*f,-
28

Очевидно, в частично рекурсивна и ty
(обратите внимание на то, как здесь используетол сбсоятель-
ство <*>(/)* (**7*" J.
Случай в) w « ? .Мы сведем этот случай к предыдущему
с помощью следующей леммы, важной во многих других вопросах и
имеющей принципиальный интерес. (Отсутствие понятия размерности
в "рекурсивной геометрии"):
4.5. Лемма. Для всех /я ? / существует дакое взаимно
однозначное отображение i - X —>- B. *) > что
а) пункции tt = уО?_ , t примитивно
рекурсивны, / * ' г т ;
б) обратная сункция Т*^' • fiV* —>- 2.*
примитивно рекурсивна.
4.6. Использование леммы. Предположим, что .:г-«ма верна.
Применим ее к ситуации п. 4.4, случай в) так: пvombi при n>.R,
су
Очевидно, й примитивно рекурсивна вместе с J . Легко
проверяется, что ? совпадает с проекцией I-уровня функции
Ч на первые tt координат. Так как это проекидя коразмер-
коразмерности I, мы свели этот случай к уже разобранному.
4.7. /рказательство леммы. Случай /я - / тривиален.
Проведем индукцию по Ш , начиная с /п - Л ,
Конструкция 4 . Сначаяа построим явно <^ :
2Э

?М:(л '/-> Ж \ положив
Легко проверяется, что если перенумеровать пары
f/f ,ХЛ)(г (Ж. V в "канторовоком порядае", расположив
их по возрастанию /, ¦* Хг ,а внутри группы с данными
Хг ¦* /^ - по возрастанию /f , то 7"и>(У,, fj)
С5удет как раз номером пары (^1t Хг ) в этом списке.
Тем самы^, 7 взаимно однозначна и примитивно рекурсивна
(использовать предложение 3.5 и рекурсивность 4-t , п. 3.10
f , /
для учета j ).
Восстановление пары (X, t Уг ) по ее номеру у
является элементарной задачей и приводит к следующим формулам
для обратной функции i " :
Здесь [ ? 7 означает целую часть Z . Проверку
примитивной рекурсивности этих функций с помощью результатов
(и приемов) § 3 мы оставляем читателю в качестве упражнения.
Конструкция ? , /у * J . Предположим, что
f) 7ZTT)
« , 7" уже построены и проверены их свойства.
Положим прежде всего
30

Ясно,что v примитивно рекурсивна и взаимно однозначна.
Решая уравнение 9*ы1 (Г(~' " (А, . Л,-,), Уя ) --у
в два приема, получим для обратной функции / " формулы:
По индуктивному предположению, t ~ примитивно рекурсивны.
Этим завершается доказательство леммы и шесте с ним
первая часть доказательства теоремы 4.3.
Вторая часть доказательства. Теперь мы должны устано-
установить, что всякое перечислимое множество примитивно перечислимо.
Начнем со следующего свойства класса примитивно перечис-
перечислимых множеств.
4.8. Демма. Класс примитивно перечислшых множеотв
замкнут относительно следующих операций: конечное прямое
произведение, конечное пересечение, конечное объединение,
проекция.
Джазательотво. Пусть ?? ?' <B. ) t ?f <(Ж*) -
три примитивно перечислимых множества, проекции 1-уровней
примитивно рекурсивных функций <?,-? и J соответственно:
31

Тогда имеем:
E * ?, проекция 1-уровня функции (/-/<}(К *<;У, *)
HUE' проекция I-уровня функции (/- /)(/'' */ ?
Е.ПЕ' проекция I-уровня функции (/•/ )(^, У, Z/
Устойчивость относительно проекций заложена в определение.
Пусть теперь ? - некоторое перечислимое множество.
Реализуем его как 1-уровень частично рекурсивной функции f
из (я I в ?. по предложению 4.2 и заметим, что
для доказательства примитивной перечислимости ?¦ достаточно
проверить примитивную перечиолимость графика f) с (Ж V * 2- •
Действительно, ясно, что ? = 1-уровень / = проекция на
первые к координат множества О /l[(Z4) **{i}] •
Кроме того, множество f*j с Ж* примитивно перечислимо,
например, по п. 3.6. Если мы докажем, что *'/ примитивно
перечислимо, из леммы 4.6 будет оледовать то же самое для ? •
Итак, окончательная редукция нашей задачи выглядит так:
доказать, что граХшш частично рекурсивных функций J
примитивно перечиолимы. С этой целью мы проверим, что а) гра-
графики простейших функций примитивно перечислимн; б) если А^ш
функции с примитивно перечислимыми графиками, то у функции,
которая получается из них применением одной из элементарных
операций, также примитивно перечислимый график.
32

Графики простейших функций.
1-уровень (/, * /- /л )*
-уровень /„.,,
J - I-у
Устойчивость относительно соединения.
Пуоть / у - частичные отображения из (О? 'У * (Ж /
и B.*)$ соответственно. Предположим, что Q и Л>
примитивно перечислимы. Тогда ^/'jGB/ < (% *)( * B- /v
совпадает с пересечением
Здесь ^е^ J (Z.*)"-B.У * *2* )^(г+)~(г*
операция, которая меняет местами два последних сомножителя:
Из леммы 4.6 видно, что (f.4) примитивно перечислим.
Устойчивость относительно композиции. Пусть Q
частичное отображение на (Ж+У в (Ж. ) , ¦/ -
то же из ( Х- / в ( А. /' , А = S-* . Тогда
/J - проекция множества ( С ' B'У)Л((Z- J * /1 J
на
Как выше, если у и Г примитивно перечислимы,
то же верно для // по лемме ч.&.
Устойчивость относительно рекурсии и р - оператора
является значительно более тонким пактом. Нам понадобиться
следующая красивая и полезная лемма.
33

4.9. Демма. Существует примитивно рекурсивная функция
Gd (к, t) (функция Геделя) со следующим овойством:
для любого Nfr 2. и любой конечной последователь-
последовательности #<¦, , а j * (Ж ) длины *
существует такое /t Z , что Grd(K.i) • &к
при всех /*¦<«¦//
(Иными словами, Gd (x.t ) - это такая последова-
последовательность функций от аргумента к , пронумерованная
значениями параметра Г , что любая функция от К на
сколь угодно большом интервале /t л/ может быть
имитирована подходящим членом последовательности).
Доказательство. Сначала полежим
и покажем, что ч* обладает тем же свойством, что и
Go. , если разрешить подбирать ( &, t ) (- (Z у
После этого можно будет поломить Gd (*Х) - 9* CKit Су).
изоморфизм из леммы 4.5. (Избавление от лишнего параметра
несущественно, не в дальнейшем укоротит формулы).
Итак, пусть даны а, ( a.j е Ж ' .Сначала
выберем X <- Z с условиями X * ^ , / •* /с / '
для всех / *¦ к < N . Лалее, положим / - X / .
Легко видеть, что если *"r / at, , *f , к± < ™ ,
то / * кй X ' и f + *гл У ' взаимно просты:
их общий делитель должен был бы делить ( Kf - хл ) X / ,
то есть состоять из простых чисел <¦ X , но ни одно из
34

них не делят / * *V * !
По элементарной теореме теории чисел, существует решение
ft (- 2 * системы сравнений
U 2 <2, mod D
/J , /* к * а/
Очевидно, отсюда вытекает, что
( кл и, t ) ' ?&iz (/* /ett U ) -
Теперь продолжим доказательство теоремы 4.3.
4.10. Устойчивость относительно fit - операции.
Пусть / - частичная функция из (z*)**'
в 7L+ t и пусть
Напомним, что область определения ч состоит из тех
- Хь. ) , для которых пЛи. v существует и
Xi, ,Xbt К) €cJb(/)juisL всех К , меньших этого
/
/>
хотим доказать, что если // примитивно пец-чис-
/т 7
лим, то /_ такуе примитлв1)О перечислим.
Пусть // является проекцией i-уровня (на перше л ¦ /
координат) примитивно рекурсивной функции F ;
35

(буквой У мы обозначили тот аргумент F , который ета-
ноштся значением <с ). Как в п. 4.4 достаточно раоомотрать
случай Ш = 4 : если /f * Д, , то воспользоваться
леммой 4.5 доя замены вектора ( У* > • ^*- ^ одним
числом V , а если *н * О , то ввести "фиктивный
аргумент ^ , от которого /" на самом деле не эашоит.
Итак, пусть #*? / , Введем функцию Сг от
аргументов /f , , У*. , / у У, ? j *, , положив
о
Здесь П - i по определению.
Легко убедиться, что 6 примитивно рекурсивна;
она получается рекурсией по аргументу У из двух других
функций, примитивная рекурсивность которых очевидна.
Мы покажем, что /\ является проекцией на координаты
(К • . ^ . / ) I-уровня функции С
Включение pi (G=l)c/l. Пусть (/<, . >^*,/>?> ?,*,
фиксированная точка на 1-уровне & . Мы должны проверить,
что (/<, , У.)еЪ{р)ж что j - ? (К , - , К )
Иными словами, нужно установить, что
/
. */ определена и > /
для всех < * /Г'1
36

Так как G ~ 1 в данной точке, все сомножители G
равны I в этой точке. В частности, F(Уи ¦, К. ,jf, *, У) - /,
откуда и следует, что /(/i , , У*. , у ) - ? , ибо
Г/ есть проекция I-уровня F . Если Г - /
больше проверять нечего.
Пусть у > i . Обращение в I К. -го сомножителя
в П дает тогда:
= / ^ ?</(«.*)*
Это доставляет треубемое.
Включение ЛГ <-' [>ч (&-- /J. Пусть f ^, ,^,Г)^ /I
Мы должны подобрать значения остальных координат у, f) t (
так, чтобы, еле дать все сомножители в соответствую-
соответствующей точке равными I.
Прежде всего, (/f t J У1 ^ г; / / е /J
согласно определению ? . Поднимая эту точку с //
на 1-уровень /¦ , найдем нужное значение У . В случае
~ / значения ^ > ?f можно взять люоыми.
/
Пусть JT >¦ / . Найдем тогда t из системы урав-
уравнений
JT
(Правые части существуют в силу определения ^--^ (у) ).
37

Наконец, при кавдом К ¦? Г - J поднимем точку
г У А/
до точки на г * 1 с дополнительной координатой -V ,
пооле чего найдем / из системы уравнений ^
Зто обратит в единицу все сомножители в
d,потомучто
.Л
при X < / - /
по определению С t t f
4.II. Устойчивость относительно рекурсии.
Нам осталось провести последыш этап доказательства
теоремы 4.3.
Пусть / и - частичные ф"i кции от А , Я * &
переменных соответственно, а л- ауосция от >t / /
переменной, которая получается из них с номодью рекурсии:
38

Мы должны установить, что если fy t Г„ примитивно
rr Iff
перечислимы, то и f ? примитивно перечислим.
Пусть F (г - примитивно рекурсивные функции,
1-уровни которых проектируются на Г/ Г„ соответственно:
1
(как в п« 4.10 достаточно ограничиться случаем, когда кораз-
коразмерность проекции равна I).
Построим явно функцию п , 1-уровень которой проек-
проектируется на Гу .Ее аргументами будут /Y t ,Уп411/7 ;
t } t ( n аргумент, который станет значением ^ ).
Положим:
* Л %(*>* ? при
*.• Л; *-*; &?(*-<>*)&(«**№(*>*<)
(Мы очитааа, что /7 - / , еоли /,,* / г / ). Как в
п. 4.10 легко проверяется, что И примитивно рекурсивна.
39

что
Включение pt ( Н- 1)с f\ . Пусть f/t /_, *>
У , t, ~t t ) ~ точка на // = / . Ш должны проверить.
Так как второй сомножитель равен I, получаем
прежде всего: v -. Get (/^ +, г' ) .
Если к тому же Хн / f = / , то равенство /
первого сомножителя Н дает с учетом предыдущего:
Пусть теперь и «. ^, > / .В таком случае из
равенства Ск - 1 находим при всех ? ¦? л? * ХА
4,
а из раг^нс"ва F - i и определелия к.
[I д'имагсь по / от К - 4 до X' ^ч -и г
пользуясг с курсивным определением /г , убеждаемся индукцией
по К , что Gd («,*)= ? (S<> > С*)
И, В ЧаСТЧО Ти,
Включение 'I *• Р* (Н- О, Дана точка
40

мы должны подобрать такие значения у, i', i f
обратить H в I.
Если VK4 t - / , выберем Г так, чтобы
&(<,?) -- '?(/<, -,**. Sj*/{K, </ После
этого поднимем точку (/< , -,/*., ба1(V, /^ ^- /^
до точки на /" = / ; это даст нужное значение ^ ; /г
можно выбирать как угодно. </
Цусть, наконец, У*/, > / • Сначала выберем
как решение системы уравнений:
Затем, подняв точку (/{> /к / Got(l, +))t-
на I-уровень / , отыщем v ' . Это обратит в I первые два
сомножителя // . V
После этого поднимем точки ( Л < )С < *u+i
с- (*) *
на уровень 1г , дооавив координаты Z , и решим
относительно t< систему уравнений
3-1Я78
41

Это обеспег оорадение в I сомножителей (t^ ,
Дрказате .тво теорем. 4.3. окончено.
4.12. 0бг кснение терт.г-.а "деречислимое множество".
Теорема 4.3. показывает, что если ? перечислимо, то
существует программа, "порождающая С. " (ср. п. 4.1).
Действительно, .;усть ? - проекция на первые /?• координат
I-урозня примитивно рекурствйсй функции f (/ч ,, . /^ у)
Порождающая Е программа долила перебирать ректоры "
(/<, . /и у ) в каком-нибудь порядке, вычислять /¦
и подавать на выход (/4 ) t /^ ) в том и только том
случае, когда значение А равно 1. В отличие от "распозна-
вающей" программы, типа описанной в § I, которая может навечно
застрять на элементе, не принадлежащем ? , поровдающая
программа рано или поздно выпишет люоой элемент ? и ничего
кроме них. Однако, если ? пусто или конечно, мы может
никогда этого не узнать.
В заключение этого параграфа мы обсудим свойства так
называемых разрешимых множеств.
4.13. Определение. Множество Е с( X ) называется
разрешимым, если оно перечислимо и его дополнение перечислимо.
(Одним пз центральных результатов теории состоит в дсч \~
зателъстве тою, что существуют перечислимте, но не разрешиуые
множества. At не /спеем привести доказательство по ь 1а?ку
времени; но эт;т результат тесно связан с трг г. Г о
неполноте, ког ^ая будет доказана довольно пс >о).
42

4.14. Чеорема. Следуювдае три класса множеств совнадают:
а) множества, характе1*»стическая-функция которых (частично)
рекурсивна;
б) множества уровня всюду определенных частично рекур-
рекурсивных функций;
в) разреиимые множества.
Дзказательство. Соотношения а) = б) с в) очевидны из
уже доказанного. Поэтому остается проверить включение в) С а).
Пуоть С- cl? J - разрешимое множество, с - его
дополнение. По определению, ? с ^(f ) , Е - <7^'(/' J
для некоторых частично рекурсивных шункций ? , / . Можно
даже считать, что ¦/ - / , / = *L (там, где они
определены). Расомотрим Г/ (/ Г/, с (jt*) *(%*)
Очевидно, это объединение является графиком /Т характерис-
характеристической функции % множества ?. . Из леммы 4.8" и даль-
дальнейшего обсуждения ясно, что /t перечислим вместе с /у
и fy' . Поэтому частичная рекурсивность я будет выте-
вытекать из оледующего результата, который представляет самостоя-
самостоятельный интерес.
4.15. Предложение. /1ля того, чтооы частичная функция &
Л / в ? была частично рекурсивной, неооходамо
и достаточно, чтобы ее iрафик /^ был перечислим.
Дрказательство. Необходимость уже установлена.
Проверим достаточность. Так как /I перечислим,
существует такая примитивно рекурсивная функция GfK, *-.},
(см. п. 4.10), что
43

/о -
проекция на [У,, ¦¦• , У и. , / / 1-уровня С ,
/ ,U) s , 1.B) / I 1
где tf •—а- / tf {*/, сл (*t//~ примитивно рекурсивный
изоморфизм Z f ^r- (%*) , описанный в пп. 4.5. и 4.7.
Очевидно, Н примитивно рекурсивна. Наконец, положим
Это частично рекурсивная, область определения которой сошадает
с "^Й (я ) и которая, как легко видеть, позволяет вычислить
.
Тем сашш, 9 достаточно рекурсивна, чем завершается дока-
доказательство предположения 4.15 и теоремы 4.14.
4.16. Следствие, для любой частично рекурсивной функция
а существует описание, в котором операция м приме-
няется один раз.
4.17. Следствие. Если частично рекурсивная функция я
всюду определена, то существует ее описание <tf t . я j =• о
в котором все функции всюду определены.
^йствительно, описание, конец которого (начиная с G ),
построен в п. 4.15, обладает этим свойством.
§ 5. Формализация арифметики (результаты).
5.1. Ближайшие параграфы будут посвящены классической
теореме логики - теореме Геделя о неполноте формальных систем.
44

В ней органически сочетаются идеи теории формальных языков и
теории рекурсивный функций. Чтобы возможно слгее выпукло
показать идею теоремы Геделя, мы проведем изложение по сле-
следующему плану:
а) формализация арифметики. Мы напомним структуру языка
арифметики L. st^ и сформулируем основной результат об
описании разрешимых множеств на этом языке.
б) АриФметизашя формализма. Мы опишеи ^еделевскую нуме-
нумерацию формул, термов и выводов в языке Lf fl^ и сформули-
сформулируем основной результат о разрешимости множества пар номеров
(формула - ее вывод) специального вида.
в) Теорема Геделя. Мы сформулируем и докажем эту теорему,
опираясь на результаты а) и б).
После этого доказательствам а) и б) будут посвящены
отдельные параграфы.
5.2. Алфавит /¦/ -"У . Он состоит иэ счетного множества
символов переменных Х11 /, t ... константы О ; символов
операций ,^~ , ' t и символа отношения = ; скобок, связок
и кванторов.
Стандартная интерпретация в X : интерпретируем О
как О , штрих как прибавление единицы; остальное ясно.
Удобные сокращения:
6)
И := терм( F) , . , . - ) [^ штрихов , и- (-
t id-' 3v ( Ь 14 -- *
45

Аксиомы лх "i. . Это логические аксиомы Яж и
Лх . аксиомы равенства (см. первую часть курса), а также
следующие собственные аксиомы.
А. Аксиома сложения и умножения (ср. 3.2 и 3.3).
< * х'А — *< -- ** •,
О * х' •
я, + о = *« ^
х/ 0 - б .
Б. Схема,аксиом индукции.
р(о) _* ( V X ( Р(У) — РС^1» -* V/PM)
где Р(^) - любая формула со свободной переменной X
Напомним, что если Р(X) интерпретировать как "
обладает свойством Р ", то формальная аксиома индукции
будет относиться лишь к счетному множеству свойств, выразимых
на языке L, К , тогда как в интуитивной математике ак-
сиома индукции относится к любому из 2. " свойств
(т.е. подмножеств 2 U I ° } ).
За остальными определениями общих понятий, относящихся
к языкам Ь< , мы отсылаем читателя к первой части курса.
б.З. Определение. Множеотво Е с (, 2 ) называется
выразимым (в L( Д^ ), если существует такая формула
<> ¦><**) с К свободншли переменными, что для любых
46

целых *,,••-,-* ' w имеем:
(I,,... ,ик ?~* ал
5.4. Лемма о выразимости. Следующие дна класса множеств
Е с B *)*" (всевозможные п_ ) совпадают:
а) Разрешимые.
б) Выразимые в L( ^г .
Доказательство мы отложим до § 8. Вот интуитивные пояснения.
б) С а). Пусть Е - множество, Р - выражающая его
формула. Мы хотим написать программу, распознающую элементы
из Е и из дополнения к ?. . Она может быть устроена так:
после подачи на вход ( к, г 4л ) программа перебирает
(скажем, в алфавитном порядке) конечные последовательности
символов языка с пробелами; проверяет их на свойство "быть
выводом P(t, , - , t^ ) или т Р(t, , . , X ) "
и подает на выход I или 2, когда добирается до такого вывода.
а) С б). Это - просто утверждение о том, что наш фор-
формальный язык настолько богат, что процесс вычисления рекурсивной
функции / в точке ( A i , «^ ) , приводящий к ра-
венству /( й, t .,«л/ = / , можно превратить в формальный
вывод некоторой форафгди Р (к11 ,'<*).
Для доказательства теоремы Геделя нужна только вторая
часть леммы.
47

§ 6. АтуФмвтип<щр|я Формализма (результаты).
6.1. Пусть М - некоторое множество. Нумераций
мы назовем взаимно однозначное ооотвеотвие между М и
некоторым подмножеством «? ; элементу чп ь М ставится
в соответствие его номер. В важаит для нас случаях М будет
состоять из последовательностей символов языка />, -^
(или выражений языка). Тогда имеет смысл говорить о вычислимой
нумерации, подразумевая под этим существование программы, которая
по выражению вычисляет его номер, а по целому числу узнает,
является ли оно номером выражения, и если да, то какого.
Мы считаем в этом параграфе, что раз навсегда выбраны
и зафиксированы три вычислимых нумерации:
в) символов языка L 4 /г ;
б) выражений (конечных последовательностей символов)
в) конечных последовательностей выражении.
Их реальная конструкция будет дана в § 9.
у +
6.2. Определение. Пусть я ь А - такое целое
число, что выражением с номером а является некоторая
формула Р(^<) языка /, А^ , содержащая фик-
фиксированную переменную /, в качестве единственной свободной
переменной.
Тогда "диагонализацией формулы номер Л " называется
формула Р (о.) .
(Напомним, что л - "цифра" в языке L, Л*, ,
обозначающая число Л )„
48

б.з. Лемма о разрешимости. Пусть E - некоторое мно-
множество формул языка Lj Лх . содержащее Л. А и
имеющее разрешимое множество номеров. Тогда следующее множество
С- < 2^ * Я разрешимо:
(a. i)cr G- 1 ^ есть номер
| диагонализещии формулы номер л)
Интуитивные пояснения. Программа, распознающая элементы
из G , может работать так.
После подачи на вход ( а, *)*•(# ) программа
выписывает выражение номер 9* и проверяет, ^юрмула ли это
(возможность автоматического синтаксического анализа заложена
в определение формул), если да, входит ли туда свободно только
X., ; если да, строит диагонализацшо формулы.
латем программа выписывает иоследова'тельность выражении
номер *. , проверяет, является ли последнее выражение
построе .ной ранее диагонализациеи. ьсли да, она проверяет,
яаояются ли все остальные выражения формулами. Если и это так,
остается проверить, является ли эта последовательность выводом
из §> . Для этого нужно перебирать все формулы последователь-
последовательности по очереди. Синтаксический анализ покажет, получается ли
оче ueir-cut (^юрмула применением iHP или Gen. из предыдущих,
если нет, остается лишь проверить, принадлежит ли она б , для
этого нужно вычислить ее номер, пользуясь вычислимостью номе-
номеров ?
49

§ 7. Теорема Геделя о неполное.
7.1. Система аксиом а^метики, «„'Ормализованная в
Lt А? , была результатом дли*е.чьногг анализа нашгс представ-
лепим о целых числах, долгое ь;<-мя ка„длось естественным, что
она содержит всю "интуитивно чеч.: ,,ую" *:ьуг ацию, из которой
лс туктавнши рассуеденг гл-и „южно полупить льоую теорему теории
чисел. Отголоску, эти; представлений остэ/лоя непрекращающиеся
з cpr,'Q спид'аяисто!- по теории чисел попытки получить "элемен-
"элементарно" различные результаты, которые формулируются элементарно,
но доказываются, скажем, ам ^тштическл (с ъ/см дзета-функ-
ции, ¦.с^лфных ^юргл ...) или воо'. »е "не ^пштко" (оценки чи-
чисел ранения срсхашгни.'. по А.Зейчо). лотл ьрегля от времени
г ivv-e v.'k т; • j .ji-чоя, теорема ! деля показывает, что по краи-
Iе-,. wei i - "iropii!4 тсоретико-ч;:олоше иотшщ нельзя получить
;\ 77 : ¦:'-:. : с.улситлт з [.'..клутые Гиормудд /у А . истин-
истинные в станг'лртрой ;.чтерпретадки. но не р^водимые из А ^г .
"irr', тот ж. реду„штат остается верным, если как угодно
г^ . . ¦". систему аксиом, лшиь бы аксиомы оставались алгорит-
. рлгпоз:-.1вае.лыми i иначе мол;но было бы взять в качестве
3 '".ом все .^ормулы, истинные в са лндартнои интерпретации),
7.°,. Чтобы точно «рормулировать теорему Геделя, рас-
рассмотрим множество & > А Яг формул языка Ь, J?^ ,
C'd^flaioqce двумя свокстЕ'иц':
а) ;.;ноАест«к> номероз С разрешимо.
б) Кета '°1^) - такая формула, что С f- ?^ 7 / "
то какая-'..1будь из формул Р (ь ) ( К=<;, ',-*,*, ¦ '
невыводигла пз ? .
50

Свойство б) называется W - непротиворечивостью.
Если ? > Ах -А* ь)- непротиворечиво, то и б пепготи-
воречиво. Дзйствительно, все формулы т (О - *¦ ) выводимы
из /х А ; значит формула ?* ( ° ' * ' ) не может
быть выводима из § в силу "•> - непротиворечивости, а если
бы ? было противоречиво, из него можно было бы вывести
что угодно.
С другой стороны, и) - непротиворечивость - вполне
естественное свойство любой приличней системы аксиом: произ-
произвольное множество формул, истинных в стандартной интерпрета-
интерпретации, очевидно, и> - непротиворечиво.
7.3. Теорема. Если множество рормул & * $* ">
удовлетворяет условиям п. 7.2 а), б), то существует такая
замкнутая формула 1( , что как ?/ , так и г и
нешводиш из © .
Кроме того, It истинна в стандартно* интерпретации.
Доказательство, а) КонЬтрукция 1/ . Рассмотрим
множество & с 2 * Ж t построенное в лемме о разрешимости
6.3 :
( , /f 6- *^> « ? есть номер вывода из ? диа-
диагонали зации формулы номер tc ".
В силу леммы о выразимости 5.4 существует такая фор-
формула Q ( X,, X ^ /с двумя свободными переменными, что
51

Рассмотрим формулу * хл 7 *< Iх' > *л) и
обозначим через С - ее номер. Наконец, положим:
<К -. формула У Хл 7 Q (с t х^ ) =
= диагонализация формулы номер ? .
б) Стандартная интерпретация 4/ . По определению стан-
стандартной интерпретации имеем:
stf истинна в стандартной интерпретации «?=>
- нет такого а , что Q ( с~г « ) истинна
- нет такого а , что Q С с, * ) выводима из Ях ^>
- нет такого с( , что (с </) е Q- (по определению С-
- нет вывода из <§ диагонализации формулы номер С
-нет выюда W из G .
(Обратите внимание на эквивалентность второй и третьей
строк: если все B(е,я) не выводимы из ^> , то все
(С, ^ ) </ & так что 7 4 ( <', ^ ) выводимы
из /> , и значит, Q ( 7, « ) не истинны.
Итак, формула tf утверждает: "я невиводима!11. Следова-
Следовательно, когда мы докажем, что она действительно не выводима,
мы убедимся, что она истинна в стандартной интерпретации.
в) If нешводима. Действительно, предположим, что *U
выводима из ? ; пусть к, - номер вывода.
Тогда (с, I) €- & =?=- ?i-Q. (*.?)
Кроме того, ? /- У*д 7 Q (с, 7"д/откуда по ИР и
логической аксиоме Yх Р (*¦) —"» Р (+) получим
мгут быть выводимы из о одновременно, ибо <р непротиворе-
непротиворечива.
52

г) 7 *U невыводима. Действительно, предположим, что
<? /- у1/'. Пользуясь явным видом V и аксиомой опэре-
становке 7 и ? , получаем ё л- ^ хл $ ( С , я^ )
С другой стороны, мы уже знаем, что t/ невыводима,
так что ( с, и ) <- О- для всех /*• (ибо ^ - даагона-
лизация формулы номер ? ). Поэтому ЛД ^ 7 Г /У", л У
для всех /I . Поскольку <j? ^ Ах Л^ , одновременная
выводимость 3 xi Q ( с > Х±) и v Q ( ё, *¦ )
противоречит ^ - непротиворечивости © .
7.4. Одной из самых удивительных особенностей суормулы
Геделя ^/_ является то обстоятельство, что хотя мы устанавли-
устанавливаем ее нешводшость из наличного запаса аксиом § , ее
содерьсательная истинность для нас очевидна. .Лы готовы присо-
присоединить ее к в в качестве новой аксиомы; но это изменит Щ. ,
увеличит количестзо выводимых из % формул, изменит тем
самыгл Gr , а вместе с б? и формулу Q и, значит, опре-
определяемую но Ц формулу 1/ : появится новая формула &' ,
невыводимая из <© U f i/ j , в содержательной истинности
которой, однако, мы по-прежнему не сомневаемся.
Принятие стандартной интерпретации есть неформальный акт
мышления, с помощью которого мы каждый раз "угадываем" (не вы-
выводим! ) истинность ооормулы Геделя. Ь.сли записать tf в виде
обычного утверждения о целых числах, это будет очень длинная
арифметическая теорема странного вдаа, прямое доказательство
которой, скорее всего, представит огрочше трудности и заведомо
потребует введения новых (по сравнению с ^ ) принципов.
53

Можно думать, что типологически такой акт мышления род-
родствен тем, с которыми связаны все вообще крупные математичес-
математические открытия (в том числе открытие Геделя). Феферман доказал
замечательный результат о том, что все истинные (±юрмущ ариф-
арифметики можно вывести из аксиом и формул геделевского типа.
§ 8. Формализация арифметики (доказательства).
8.1. Этот naivxr.a±i посвящен (сокращенному) доказательству
леммы о дорэзимости, точнее, той ее части, которая нулна для
теоремы Геделя: разрешимые множества выразимы.
В доказательстве уюОнез рассматривать вместо множеств
функции, так что мы качнем с июрмулировки параллельного свой-
свойства для щункты.
• B*) -* /'
называется предо газимок (в A>f л} ), если существует такая
формула Р ( X,, , Х
a
) , что
АЛ
t
А А
Здесь -7 /'У ("существует единственный У
со свойством Р ) есть сокращенная запись для формулы
--У )
54

8.3. Предложение. Рекурсивные функции предстанимы в I,
8.4. Вывод леммы о выразимости иэ предложения 8.3.
Пусть Е <~ (% V- некоторое разрешимое множество.
По предложению 4.13 его характеристическая срункция it рекур-
рекурсивна и, значит, по предложению 8.3. ova upfдстаатсна некото-
некоторой формулой Р ( Xi , .'. }Х л-Н'
По ^«им Q ( Хц..> ^ib} —Pf^t, ¦ •,К/У* покажем,
что Е. 1ГРе чстаняено .ю^дулои ^ . 1да этого лосхаточно
доказать, что
(I.
Первая има^кация немедленно следует из пе^ж1,* имплика-
импликации в определении представимости * . Вторая ~j -бует более
окольных рассуждений: v^
Кроме того, по вторс^лу уати^ао представимости 'i riBi' югпи
q а /г -~ 41
пригиенАя aKci^wy У /(,/rJ - - ^(/J
получаем
55

Тавтология ( tg ~* R. / "* f~r& "*" 7 "с/ и МР дают
Формула 7( * : 2 ) выводима из аксиом; кроме того, имеется
тавтология г (Р * 4 ) ~> ( ^ •* 7 <* ) ; наконец, мы уже
знаем, что Р ( > 2 ) выводима из J* &г
Окончательно получаем
что и является вторым условием выразимости. ¦
ш провели эту.часть доказательства довольно подробно,
чтобы напомнить читателю о технике формального вывода. Если
в формулировке предадуцих определений и лемм заменить выводи-
выводимость из ^х ^ч содержательной истинностью (в стандартной
интерпретации), то все доказательство стало бы интуитивно проз-
прозрачнее и короче; основной технической работы требует перевод
этого доказательства на формальный язык.
Ш опустим такой перевод в оставшейся части параграфа,
отсылая читателя за подробностями к книге Мендельсона (стр. 133
и дальше).
8.5. ^эказательство предложения 8.3 (план).
Мы покажем, что простейшие функции представимы и что при-
применение элементарных операций сохраняет представимость. Напом-
Напомним, что согласно следствию 4.14 из рекурсивной функции имеется
описание, состоящее из всюду определенных функций. Поэтому все
фигурирующие нике функции предполагаются всюду определенными.
56

а) Простершие фушцш Представляющие $ощуды
лис х, vx'
б) Устойчивое!.> относительно композиции. Пусть даны
Функции Представляющие Формулы
чД](,,...
Тогда <|j икцея *- 111 , , Ч ) представлена формулой
у,, x,/..
связешн^с переменные Ч, , ,,, у -J „ суть "времен
обозначения" для л чешш 3 а ) • • ¦» Я "^ ь точке *
¦1 ¦>
, юто i" ^j шчо вычислить, преаде чем под-
ставить их в i в качестве аргументов.
•4-1Т'8
57

(Мы обозначаем одними и теми же буквами аргументы функ-
функций f , Ч: в метаязыке и переменные в /. J/x ; в этом
контексте не мохет возникнуть путаницы).
в) Устойчивость относительно ш -операции»
Пуоть функция УfК > ¦>?,, + ,) представлена
формулой Р(У,>~',Х„*Х) . Тогда функция
a(/fi .. XJ ¦-
представлена формулой
г) Устойчивость относительно рекурсии. Формальные выводы
в этой части доказательства особенно длинны и нетривиальны, да
и структура представляющей формулы не очевидна. Пусть функция
w f^t ¦ , /„., J определена рекурсией по последнему
аргументу, исходя из функций у {?* , - , f 1% )
и о (ff;. ., /^ ( VH,, , /fc 11 ) . Тогда даш вычисления
мы до-?jiu вычислить переменное количество Xп 4 2 - /
проиелуточных значений й (А, -, Хи, к. ) я. * /Л4.
Непосредственно ввеоти для них вспомогательные обозначения,
как в пункте б), мы поэтому не можем.
Естественная идея состоит в том, чтооы воспользоваться
для имитации последовательности » {/+, , К., * ), * <¦ ^„
функцией Геделя 4eht f / * Хл Zb , 2\ ) .
Итак, пусть J. представлена формулой Р ;
формулой С[ ; моано проверить, что letn. (fJ
представлена формулой
58

Формула, представляющая о , выглядит так:
ющая о ,
ЛиГл P
л *
Читателю следует, по крайней мере, проверить, что эта
форвсула становится содержательно истинной после подстановки
Указания. ( t( , i> ) - параметры в функции Геделя,
позволяющие имитировать ее промежуточные значения -Л ;
ъГ - имя переменной, по которой происходит рекурсия.
9.1. В этом параграфе ш проведем подготовку к конструк-
конструкции конекретной нумерации алфавита, шралодшй и последовательностей
выражений языков Ь f , свойства которой будут использованы
в § 10 для доказательства леммы о разрешимости и дальнейших
выводов из возможности арифметизации.
9.2. Пусть JJ - некоторое счетное множество. Положим
iS(M/ • fi UЛ t//.... Элементы из ft <¦ ?>($)т отождеств-
ляем с последовательностью (о, , ,<*-.) элементов М
Длины п .
Напомним, что нумерацией Л называется взаимно одно-
59

значное соответствие Н •' л —¦*- % % д/(а.) еоть
номер &, ; /v/~Y*ACTb элемент Jt с номером к .
В дальнейшем мы ограничимся рассмотрением таких нумераций,
для которых *J (Л) = Z
9.3. Конструкция нумерации Д(а/до нумерации J) .
Построим отображение Л^ ¦ ^(А> -*>%*, полозшв
Нетрудно убедиться, что n f является нумерацией (см. а. 4.7).
Пусть, далее, (af г , &„ ) я ( /.¦ , . , S* ) - два элемента
*/f - номер последовательности (<?,, -,ар/¦>> ?
однозначно определяется //, -номерами (а^, ,^я)ъ (/,, , if
Поэтому существует функция 2* * 2* •—¦>• 2 .•/*•,*
со свойствами
9.4. Предложение, а) Функция •* * и. рекурсивна.
б) t*\* л -* »nait (t«,^)
Доказательство, а) Начиная с этого места, мы будем
ограничиваться установлением того, что многие интересующие
нас (уункщш вычислимы в интуитивном смысле слова, оставляя
техническую проверку их рекурсивности читателю. Для *i*k
вычислимость легко установить. В самом деле, будем считать
для сокращения заиси, что f отождествлено с д. посред-
посредством n' . Положим также, что для ь % а. е- 2
60

Тогда инеем в обозначениях п. 4.7 :
откуда ь#ь * ~
и вычислимость >и jf и. становится очевидной.
б) Дгн доказательства неравенства »и* и > (
достаточно ограничиться сдучаем, когда длина to или И_
равна I. Заметим прежде всего, что 9"B) ( *, ч ) * •*.** /*.
и что функции 9"*'1 ч i « <,А , _ во являются строго воз-
возрастающими по любому из своих аргументов.
Неравенство Г(гв'(а(> ,ар . О > Г'~) («,, .aj
,af))
Г
Таккак pW>f и rT'N,, ,. O-^'V'K. у, О-
подучаем требуемое.
Неравенство ^<о°^^аг, .O..J» г'~"/*,, *р
61

Достаточно ограничиться случаем * = 1 . Имеем:
Поэтому достаточно проверить, что Т'Г*' ( f • а ,, > йл ) * ^ ' (°,'
Выраиая Т Р ' ,  г«р®а Т * и 9* t 9" г без труда
получаем возможность провести индукцию по Р . Первый шаг
9* (<,*¦} > й- , очевидно, обоснован. ¦
Свойство 9.4 б) будет использоваться всегда так:
если последовательность ( а( , .. , &• ) входит в («t ,-,'«)
как часть, то есть если для некоторого * имеем 1„ - о, ,
«1ч, * аг , - .*,-,„., г а.» , то N, -номер ( ^, , . ,t- )
строго больше ь'^ -номера ( ft4 , • , Л„ )
§ 10. Атяйметизацая формализма (доказательства).
10.1. Пусть Lj - произвольный формальный язык первого
порядка с условием: количество символов операций и отношений
в L1 конечно. Языки А, Яг и Lf*e.t удовлетворяют
этому условию; но его можно было заменить более общим
ценой несущественных технических усложнений (доказательств),
которые читатель без труда сможет провести сам. Пусть Л -
алфавит «у •
Фиксируем нумерацию п ' А —^ Z . Потребуем,
чтобы символ а/ (¦f) был связкой и чтобы множества номеров
символов переменных и констант были разрешимы. Построим по N
нумерацию n1 множества выражений 4 (Л' и затем по л/
62

нумерацию N? множества конечных последовательностей выражений
«^ ( $ ( Л )) как в § 9.
Мы покажем в этом параграфе возможность "автоматичес-
"автоматического синтаксического анализа" для языка L, . Для этого мы
будем последовательно строить такие рекурсивные функции, что
по их значению на номере выражения мы сможем установить, явля-
является ли это выражение термом или формулой, входит ли туда
свободно переменная с данным номером и т.п. В конце конструкции
мы, в частности, сможем доказать лемму о разрешимости.
10.2. Переменные и константы. Положим прежде всего:
I, если vA ( к) не является выражением,
состоящим из одной переменной,
2 иначе.
I, если к!4 [к) не является выражением,
СлиЛ1*-)г^ состоящим из одной константы,
2 иначе.
Эти функции рекурсивны в силу предположения о нумера-
' . Действительно, kJ, (ft) = (переменная / \^>
к - <Г(оо) ( U d(*)) - -rOJG&ty^a множество ^ -номеров
переменных | n(*}J рекурсивно по предположению.
10.3. Термы. Мы покатай, что существует рекурсивная
функция Texw, ( «.) со свойством:
TeivM. ( «.) г { <^-э» N41 ( k ) не терм#
Следующий план конструкции с теми или иными вариациями
63

не терн
(
2
t
будет многократно повторяться в дальнейшем. Из определения
термаи свойства 9.4 б) ясно, что
|J4 (r.) не терм-константа (•*•);
не терм-переменная (д );
не выражение вида
, , * ч) • рда
- символ операции ранта
t, , , tt - термы с
йл - номерами s к- \
гЛы построим для каждого из условий («*),(А),(*Л') такую
функцию от к. , что ее обращение в I будет равносильно выпол-
выполнению соответствующего условия, а затем перемноаим все эти
функции.
Дня условий (л ) и (а) достаточно взять Ом>Л
и va*. ( 4 ) соответственно. Для условия (р ) положим:
(f)
(^
где Л(")-- 1,Л(*)** •*«. ^* 1
Окончательно полодим:
при
к>,1
64

Вычислимость I«ли*. ( и.) очевидна. Рекурспвность, однако,
требует дальнейшей работы, ибо для вычисления Ten.**.( R.)
№ы пользуемся всеми вычисленшми ранее значениями I**** [ л ) t
Тет.~.(к-1), а не только одним предыдущим. Мы опускаем эту
часть.
10.4. Атомарные 'ютжулы. Построим рекурсивную функцию
JH:( P-) со свойством:
jjt (Р-/ - 4 Ф?> К»< ( V. ) не атомарная формула.
Атомарные формулы имеют вид Р (^ < > — t г ) >
где р - отношение ранга t , a i1 , , "tt - термы.
Поэтому, как в предыдущем пункте, достаточно полояить:
п- п п
Ч Р "
1Сак и выше, вычислимость ясна, а рекурсивность требует
аналогичной проверки.
10.5. ФОРМУЛЫ. ПОСТРОИМ рекурСИВНуЮ ФУНКЦИЮ Гоа«.('К.)
со свойством:
(
Гегиил 1«.) = i «5е-> М ( (^) не (формула.
Имеем:
05

p
Р не атомарная формула;
Р не имеет вида т (Q ) , (<^, )•(<?»).
где • - одна из связок;
не формула ^5» не V < Q ,-?*<? , где Q,
Q, t t?^ - с^ормулы с меньшими номе-
номерами, а X - переменная с меньший
номером.
Положим Fom*. (-1) = 4 и для каждого из условий за
фигурнш/и скобками построю/, соответствующую функцию от 'К. ,
считая, что Тепм*.D ) , ... } \-епм*. {к. -А ) уде вычислены.
Читателю уже должно быть ясно, как это делать. Ограничимся
двумя конструкциями.
Р не имеет вида ( Q, ) ¦—^ \ Ц ) (, где Ml)-*)
П
1
P не имеет вида V/ Q «#=^ ВD) = ^ , где 8 (-0--<
10.6. Подстановка терма в теда. Построим рекурсивную функ-
функцию от трех переменных
N^ -
номер мерта, результата
подстановки терма ^
в терм ^, ( * ) вместо
переменной ^, ( ^ )
1 , если предыдущий рецепт не
применим.
66

(Так как, по соглашению, N ( < ) - связка,
}1~л ( 4 ) - выражение длины I, состоящее из этой связки и,
значит, не терм,так что значение I для j&.&t ( к, < , г?)Не
может бить смешано с номером терма).
Как выше, начнем со словесного описания. Буквами о( , Р> ,
Г~, о обозначим фигурирующие в нем условия.
0 Имеем: АрЫ{к^^)-
= I, если ( <*) : ^< («-)не терм ила NM ( ( ) Не терм
или ff 4 ( ^) не переменная;
= «. , если
( А ) :
А):
в ^ , если ( А):не (*) и ^ i & и N, (О есть
терм-константа или терм-переменная;
если Г о ).• не [4-) и существуют термы t4j ^г
с д/( номерами i 4 , t, и знак
операции / тшше, что ^i*(?)¦•/(i,, ,*
Заметим, что ( S* J зависит от чисел Nlf 4', '< > > ^ г ,
не превосходящих 2 .
Допустим теперь, что цы построим функции от R , ( , ^ }
Ч , - , ^ , •• : ?л , Fp , *Y - F^ . которые
вычислимы, принимают лишь значения 1 и 2 такие, что
Р^ - 1 ^=s> выполняется условие ( * )
Fa - 1 **=э. выполняется условие (д) ... и т.д.
Тогда по аналогии с приемами, описанными в п.9.9, мы сможем
положить:
67

(суммирование по о относится к 1ЛЛ -,*»,*•, D /* **• ).
Ото будет индуктивное правило для вычисления >4u* t ; рекур-
сивность, как выше, должна будет проверяться дополнительно.
Остается построить F . Нетрудно проверить, что годятся
следующие формулы. Пусть лНI^, »(¦* / * Д» при ^* &.;
Х - 1 , Х(У) - \ при * >- Л . Тогда:.
10.7. Подстановка терма в Фошуду. Совершенно аналогично
строится рекурсивная функция:
номер формулы, результата подстановки
терма ы \ я) вместо всех свобод-
свободных вхождением переменной
в формулу N1 (I ) ;
если этот рецепт не применим.
(& )
Мы впускаем подробности.
68

10.8. Читателю у&е доллен быть ясен принцип
конструкций, и мы ограничшся лишь несколькими краткими заме-
замечаниями.
а) Мы должны проверить, что лно,-ество (номеров) аксиом
арифметики разрелп/о, чтобы г<-рант..роват1 wmew с «и, теоремы
Гсделя в простейшее интересное случае. Дда. этою еле чует пере-
перебрать по очереди (конечное) ы>.э*и;ство аксиом и схем аксиом,
логических и собственных, и для кандои из них построить сзов
рекурсивную функцию от номера, равную 2, зсли п>з этим лт-сроы
стоит частный случай данной схемы и i лначе, после чего пере-
перемножить эти функции.
Для индуктивное консарукци; чак раз ц придетат пользо-
пользоваться функциями, которые рсСйознаот тер;.^, форлуш, вычисляют
результат подстановки к т.п.
б) Нужно построить рекурсивную <$у>п цшо
Р(-,,. Ii \ N< Сдиагоналнзашм v ор^улы Ni .
\J i I , если этот рецепт не применим.
в) Нужно построи1Ь ре1 /рсивную фу!1Кцию
. 1, если N^ (r) есть вывод
rt(i,b)- i формулы oi;4i )
2 иначе.
г) Наконец, нужно заметить, что множество Геделя б-
является 1-уровнем функции Рч ( Й1ол Са ) t с ) ;
G ^
69

Поди h печати 25.12.73. '' 77383 Ф 60x80/18.
Физ и j 4,5. Уч -ни и 3,0.
Зл-аз 1878. Тираж 500 ЭКЗЛДена 8 кон
Типоф^фия Пза-в?| MPV Москва, .'Кнгорм