ДЛЯ любых значений Ху, . . Хп, взятых в произвольной полугруппе и удовлетворяюш;их в этой полугруппе соотношениям (4), значения термов л, р будут равны, т. е. когда формула

{УХп+1Хп2Хт-з) {ХпЦ-{Хп+2-Хтз) =

= (Xn+i • Хп+а) • з:,г+з) & (di = bicS: . . . & = ь) -> й = f (5)

тождественно истинна. Итак, для любого слова р

где через F (г) обозначено слово (5). Ясно, что словарная функция F (f) рекурсивна. Таким образом, креативное множество и in-сводится к рекурсивно перечислимому множеству £ и потому (п. 8.2) множество £ креативно.

Поело того как на р}гбеже прошлого и нашего столетий был окончательно описан язык исчисления предикатов, естественно возникла задача о нахождении всех логических законов, формулируемых на этом языке, т. е. о нахоядснии всех тождественно истинных формул, п о нахождении алгоритма, позволяющего для каждой данной формулы узнать, является ли она тожественно истинной. Последняя задача оставалась открытой в течение ряда лет и получила название проблемы разрешимости (Entscneidungsproblem) исчисления предикатов. В 1936 г. Ч ё р ч [2] показал, что если принять тезис, носящий ныне его имя (п.2.3), то проблема разрепшмо-сти решается отрицательно. Это был первый крупный успех только что родившейся в те годы теории алгоритмов. Теорема 2 представляет собой модернизированный вариант первоначальной теоремы Чёрча, так как понятие креативного множества было введено Постом много позже.

13.3. Арифметические множества. Рассмотрим натуральный ряд у, на котором отметим операции сложения -+-, умножения X и числа О, 1. Получившуюся модель

31 = <Ж; +, X, О, 1>

назовем арифметикой. Символы -Ь, X, О, 1 будем рассматривать как бинарные функциональные и предметные символы, значения которых фиксированы. Формула й исчисления предикатов называется арифметической, если она не содержит предикатных символов, каждый ее функциональный СИМВО.Л есть либо -г, либо X, предметные символы О, 1 в ней не связаны. Предметные символы О, 1, имеюшде фиксированные значения, называются индивидуальными. Остальные предметные символы, входяпще в формулу л, называются пред.четными пере.менны.ми. Арифметическая фор.мула, не имеющая свободных пред.

метных неременных, называется замкнутой. Каждая залшнутая арифметическая формула имеет на натуральном ряде значение И или Л. Те из них, которые имеют значение И, могут рассматриваться как выражающие свойства натурального ряда на языке исчисления предикатов.

Пусть й - арифметическая формула, свободные предметные переменные которой суть z/i, . . ., i/„. Говорят, что формула й истинна (или тождественно истинна) на 9f, если й истинна для каждых значений у, . . уп в Ж. Отсюда ясно, что формула й со свободными предметными переменными i/i, . . ., г/„ истинна на 3( тогда и только тогда, когда на % истинна замкнутая формула (Vj/i . . . . . . у„) й. В общем случае значение формулы будет зависеть от значений переменных у у, . . ., i/n и потому значение й можно рассматривать как значения га-местного предиката Р {уу, . . ., Уп), определяемого или «изображаемого» формулой й. Предикаты, которые определяются арифметическими формулами, называются арифметическими (или формульными) предикатами. Например, предикаты X < у я X \ у {х делит у) арифметические, так как х<у хфу & (3z) (rr -f Z = у), X \ у (3z) {у = X X z). Множество тг-ок натуральных чисел (у, . . УпУ называется арифметическим (но Гёделю), если арифметическим является тг-местный предикат, истинный на га-ках этого множества и ложный на остальных ?г-ках. Числовая частичная функция у = f {ху, . . ., Хп) называется арифметической, если график ее есть множество арифметическое.

Для краткости терм вида 1 -{- 1 + . . . -Ь 1 (а единиц) в арифметических формулах обозначается числом а. Говорят, что множество Ж или функция/изображаются формулой й, если формулой й изображается предикат, отвечаю-пщй М или /. Например, формула у = 2 представляет множество, состоящее из одного числа 2; формула (3z) (у = 2 X z) представляет совокупность всех четных чисел; формула

у Ф О&У Ф iSi (Vuy) {у = uv- и = ly V = i) представляет совокупность всех простых чисел; формула (Зи) ((z X Z) -f ц = у) &

& (Iv) {{z +i) X (z-hl) = у-\-р)&уФ

# (z -f 1) (z -Ь 1)

представляет функцию z = [Yу] и т. д.

Теорема 1 (Гёдель). Каждая частично рекур- щ сивная функция, а потому и каждое рекурсивно перечисли- 1 мое множество п-ок являются арифметическими.

Согласно следствию из теоремы 3 в п. 3.4 и теореме I о нормальной форме Клини (п. 6.1) каждая частично ре- 1 курсивная функция может быть получена из функций Г, 1 с, I, г, х-\-у, х - у, х-{-\, ГЦ операциями подстановки и минимизации. Поэтому теорема 1 будет доказана, если мы докажем, что все указанные исходные функции арифметические и что операции подстановки и минимизации, примененные к арифметическим функциям, дают функции арифметические. А) Суперпозиция

/ {Хх, . . ., Хт) = g.{gi {Xi, . . ., xJ, . . . , gn (Xi, . . ., Xm))

арифметических функций g, gu , gn есть функция арифметическая.

Действительно, если формулы G (xi, . . ., х, у) и Gt {хх, . . ., Хт, у), представляют функции g, gi, то формула

3zi... z„) (G(zi, . . ., Zn, у) & Gi {Xi, . . ., x,n, Zi) & . ..

...&Gn {Xu . . ., Xn,, Zn))

представляет,- очевидно, функцию у = f {xi, . . ., Xn).

Б) Если формула G {х, . . ., Xn-i, и) представляет частичную функцию g {х, . . ., Xn+i) = и, то формула

G{xu...,Xn, у, 0)&(Vz)(z<y-

(Эи) (G {xi, ...,Хп, Z, и) &иф 0)) представляет частичную функцию

у = II, (g {Xi, . . ., Хп, z) = 0).

Таким образом, оператор минимизации, примененный к арифметической функции, дает функцию арифметическую.

В) Функции +, X + 1, X - у. In изображаются соответственно формулами

z X -\- у, z = x+ i, {y<x-y + z = x)& {ху~> z = 0),

Z = 0-х, + . . . + Xm + . . . + 0-.Xn

И потому являются арифметическими.

Г) Функции х, [х/2], с {х, у), I (х), г (х) изображаются формулами

z = хХ X, (2 X Z < х) & (х < 2 X (z + 1)), 2xz = {x + y) + 3xx + y {ly)(x=c{z, у)), {Jy)(x=c{y, z))

и потому являются арифметическими.

Д) Функции Z = rest {х, у), z = Г {х, у) изображаются соответственно формулами

(Bu){x==uy-z&z<:y)\/{y = 0&z = x), z = Test(l{x), i + {y + l)r{x)).

Согласно приведенному выше замечанию из А) - Д) непосредственно вытекает теорема 1.

Каждая арифметическая формула может рассматриваться как слово в конечном алфавите J = {&, V> V, Э, (,), , +, X, =,0,1,0;, а), причем слова xt = {ха . . .а) можно употреблять в качестве кодов для предметных символов. Все слова в алфавите J, а значит, и все арифметические формулы имеют определенные алфавитные номера. MnoHtecTBO арифметических формул называется арифметическим, если арифметзаческим является множество номеров этих формул.

Следствие. Множество всех замкнутых истинных арифметических формул не рекурсивно и не рекурсивно перечислимо.

Пусть / (х) - примитивно рекурсивная функция, совокупность значений которой U не рекурсивна. Согласно теореме 1 суш;ествует арифметическая формула й (х, у), представ л яюш;ая функцию у = f (х), и, следовательно,

Уи (Зх) л {X, у) {у = О, 1, 2, . . .).

Таким образом, еслп бы суш;ествовал алгоритм, распознаю-ш;пй истинные замкнутые формулы, то нрп помоп1;и этого алгоритма можно было бы распознавать чпсла, прпнадле-жаш;ие U, а это противоречит нерекурсивности U.

Допустим теперь, что совокупность V всех истинных замкнутых арифметических формул рекурсивно неречислима. Пусть

7о, V,, . . . , Vn, . . .

- рекурсивная последовательность всех форм}л пз V. Тогда рекурсивная последовательность

]Vo, -]V„. . .,-] Vn, . .

была бы последовательностью всех ложных замкнутых ариф1метических формул, т. е. совокупность W всех ложных замкнутых арифметических формул была бы рекурсивно неречислимой. Ясно, что совокупность всех замкнутых арифметических формул рекурсивна. Эта совокупность разложена в сумму непересекаюш;ихся рекурсивно неречислимых множеств V и W. По теореме Поста отсюда следует, что V я W рекурсивны вопреки уже доказанной нерекурсивности множества V.

Согласно теореме 1 все рекурсивно перечислимые множества арифметические. Обратное, конечно, неверно. Пусть множество 31 определяется арифметической формулой ф. Тогда формула П 5) будет определять дополнение 3£ = ZV" - 3£. Поэтому дополнения к рекурсивно перечислимым множествам являются также арифметическими множествами. Можно легко построить и более сложные арифметические множества, не являющиеся ни рекурсивно перечислимыми, ни дополнениями к последним.

Теорема 2 (Тарский). Совокупность номеров всех истинных (замкнутых) арифметических формул не является арифметической.

Для доказательства используем обычный метод универсальных функций. А именно, предполагая теорему ложной, будем стремиться построить арифметическую формулу ф (х, у) с двумя свободными предметными переменными X, у, обладающую следующим свойством универсальности; если а - номер некоторой арифметической формулы О. (у), имеющей лишь одну свободную предметную переменную у, то для всех значений у

(а, у)й (у). (1)

Допустим, что такую формулу ф нам удалось найти. Пусть а - номер формулы "jsp (у, у). Из (1) получаем, что

{а, у) <Н> {У> у)

для произвольного значения у. Беря для у значение а, получаем противоречивое соотношение

sp (а, а) О ПФ «).

которое и доказывает теорему.

Итак, пусть теорема ложна и, следовательно, существует арифметическая формула S (у) с единственной свободной переменной у такая, что для каждого натурального

п S (7г) = И*) тогда и только тогда, когда п есть номер слова, являющегося истинной замкнутой арифметической формулой.

Для каждого натурального п через й„ (i) обозначим слово, получающееся следующим образом: если п есть номер слова а„, являющегося арифметической формулой, содержащей единственную свободную предметную переменную у, то полагаем

а„ (i) = Sb (ft„; у, Г);

если же п есть номер слова <?„, не удовлетворяющего указанным требованиям, то полагаем а„(г) = а„.

Номер слова а„ (i) обозначим через / (п, i). Таким образом, если а„ есть формула с единственной свободной предметной переменной у, то для любого натурального i

(7(п, i)) =ИЛп(г) = И. (2)

На основе результатов и. 11.2 легко показать, что функция / (п, i) рекурсивна. Поэтому существует арифметическая формула % (х, у, и) с тремя свободными предметными переменными х, у, и, представляющая отношение и = f (х, у). Положим

51) (х, у) Ф (Зи) (% (х, у,и)&Ъ (и))

и покажем, что формула 5р (х, у) удовлетворяет требованию (1). В самом деле, пусть п - номер формулы Q. (у). Тогда для любого натурального i формула U (Г) совпадает с формулой (j„(i) и потому в силу (2)

5В (/ (п, i)) й(1). (3)

Пусть й (Г) = И. Тогда S (а) = И, где положено = f (п, i). Из последнего равенства заключаем, что 5- Г, а) = И, g (п, I, а) & ?8 (а) = И п потому

5р (п, i) = (Зи) {% (п, i,u)& (и)) = И. (4)

Обратно, пусть для фиксированных п, i соотношение ("i) истинно. Это означает, что стцествует такое натура.ль-ноо число а, для которого

д (п, Г, а) & S (а) = .

Из 5 (п, Х, а) = И следует, что а = / (п, i) и, значит,

Ъ (Г (», i)) = S (а) = И.

*J п обозначает терм 1 -j- 1,