Из (3) получаем, что Q. (Г) = И. Итак, эквивалентность (1) доказана, а вместе с нею доказана и теорема 2.

13.4. Формулы 2-й ступени. В рассмотренных выше предикатных формулах все предикатные и функциональные символы были свободными. Если правила образования формул а), б), в) из п. 13.2 дополнить еще правилом

г) если X - предикатный или функциональный символ, свободный в формуле 5Г, то формулами будут и слова (VZ)3f, {ЗХ)%,

то получающийся более широкий класс формул называется классом формул 2-й ступени. «Значение» формулы 2-й ступени при заданных значениях свободных предикатных, функциональных и предметных символов определяется так же, как и для формул 1-й ступени.

Формулы 2-й ступени, не содержащие ни функциональных, ни предикатных, ни предметных свободных символов, называются абсолютно замкнутыми. На любом непустом множестве Л£ абсолютно замкнутая формула либо истинна, либо ложна, причем значение этой формулы на М зависит лишь от числа элементов (мощности) М. Формула 2-й ступени (не обязательно абсолютно замкнутая) называется тождественно истинной, если она истинна на любом непустом множестве М при любых значениях на М всех ее свободных символов.

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

Пусть - одноместный, -Ь, X - двуместные функциональные символы, Р - одноместный предикатный символ, О, i, X, у - предметные символы. Рассмотрим следующую систему формул:

1. {Ух)(х ФО&О = 1),

2. {Vxy)(x = у X = у),

3. (VP)(P (0) & {Vx)iP (.г) Р (х)) (Уу) Р (у)),

4. (Va;)(a; + О = х),

5. (Vxy){x -Ь у = (х -Ь уУ),

6. {Vx){x X О = 0),

7. iVxy){x X у = (х X у) + х).

Смысл этих форлгул очевиден. Напрпмер, формула 3) является принципом полной пндукциц для натурального ряда. Обозначш! через © конъюнкцию формул 1)-7). Форму.11а © содержит свободные символы , -Ь, X, О, 1. Известно, что если на некотором множестве М значения 9ТЦХ символов заданы так, что формула © истцнна то

модель <Ж"; -Ь, X, О, 1> изоморфна обычной арифметике <Ж; -Ь, X, О, 1>, рассмотренной в п. 13.3. Поэтому для каждой замкнутой арифметической (в смысле п. 13.3) формулы f формула 2-й ступени

тождественно истинна тогда и только тогда, когда 5 истинна в арифметике (ZV"; -f, X, О, 1>.

Ясно, что совокупность всех замкнутых арифметических формул f (истинных и ложных) рекурсивна. Поэтому рекурсивна и совокупность 33? всех формул вида © -s- f. Если бы совокупность 2 всех тождественно истинных формул 2-й ступени была рекурсивно перечислимой, то пересечение ?£>? fl £ было бы также рекурсивно перечислимой совокупностью и ее формулы можно было бы выписать в рекурсивную последовательность

©->5о, ©->?1, ...,©->?„, ...

Но тогда рекурсивная последовательность fo, fi, . . • состояла бы из всех замкнутых арифметических истинных формул и, следовательно, совокупность всех последних формул была бы рекурсивно неречислимой вопреки основному результату п. 13.3.

Теорема 1 данного п. 13.4 и теорема 1 п. 13.2 выявляют глубокое различие между языками 1-й и 2-й ступени. Хотя множество законов, формулируемых на языке 1-й ступени, нерекурсивно, все же существует алгоритм, позволяющий постепенно строить все эти законы. Что касается логических законов, формулируемых на языке 2-й ступени, то совокупность их не только не рекурсивна, но и не неречислима.

Дополнения и примеры

1. Пусть S - ассоциативное псчпсление с порождающими эле-ментаьш с, . . ., и определяющиьш соотношениями = 6 (а = 1, . . ., Z). Для произвольного слова f в алфавите с, . . ., с, через X* обозначим слово в алфавите а, Ь, получающееся из j; заменой Ci = аЬаЧ (i = 1, . . ., s). Обозначим через (Е* ассоциативное исчисление с порождаюприт элементаапт а, Ь а опрсделяю-щтш соотношениями а* = 6* (а = 1, . . ., i). Показать, что для произвольных слов а, 6 в алфавите {с, . . ., с} а = 6 в исчислении S тогда и только тогда, когда й* = 6* в исчислении S*. В частностп, если в S проблема равенства неразрешима, то она неразрешима впсчисленпи g* (X о л л [1]).

2. Говорят, что в ассоциативном псчисленпи S разрешима проблема дели.ности сл?ва если существует алгоритм, позволяющий

ДЛЯ любых двух слов а, b из S сказать, существует ли решение j: уравнения = 6 в ®. Аналогично говорят, что в S разреши-ъш проблема делимости слева заданного элемента с, если существует алгоритм, позволяющий для любого слова а из g сказать, существует или нет решение f уравнения aj: С в £. Показать, что в ассоциативном исчислении А {%), построенном в п. 13.1 в процессе доказательства теоремы 3, проблема делимости слева элемента qov не разрешима (ср. А д я н [1]).

3. В предыдущем примере в ассоциативном исчислении А (S) рассматривались только непустые слова. Допуская в число слов и пустое слово, получаем ассоциативное исчисление с пустьш словом. Так как [Л] [а] = [Да] = [а] и [а] [Л] = [а], то пустое слово Л является представителем класса [Л], который служит единицей полугруппы, определяемой этим исчислением. Если среди определяющих соотношений исчисления находится соотношение вида й=Л, то правым элементарным преобразованием, отвечаюпщм этому соотношению, называется преобразование, переводящее заданное слово х\) в одно из слов ЛХ)), ха, У9й- -Левым элементарным преобразованием, отвечаюпщм указанному соотношению, называется преобразование й-*Л, переводящее слова вида axt), уар,ура в слово

{X, I) могут быть и пустыми словами). Говорят, что в ассоциативном исчислении с пустым словом разрешима проблема нахождения правого обратного элемента, если совокупность тех слов й, для которых уравнение at) = Л имеет решение в данном исчислении, является рекурсивной. Легко строится ассоциативное исчисление с пустым словом и неразрешимой проблемой нахождения правого обратного элемента. Для этого берем ассоциативное исчисление А {%), построенное в процессе доказательства теоремы 3 п. 13.1. К алфавиту этого исчисления добавляем новую букву и, к определяюпщм соотношениям добавляем соотношение uqv = Л и новое исчисление с пустым словом обозначаем через В (S). По аналогии с теоремой 2 п. 13.1 показать, что в исчислении В (S) uagwbv= А тогда и только тогда, когда aq-u,bv = = qv в исчислении А {%). Отсюда путем сравнения с предыдущей задачей видим, что в В (5t) не разрешима проблема нахождения правого обратного элемента.

4. Пусть Z - мапшна Тьюринга, правильно вычисляющая функцию £ (г), упомянутую в доказательстве теореьш 3 п. 13.1. Обозначим через 85 ассоциативное исчисление с порождаюпщми элементами О, 1, q, q, . . ., g„ и соотношениямп (5)-(7) п. 13.1 (по сравнению с А (Z) нет порождающего элемента v и соотношевшя (8)). Показать, что в проблема равенства разрешима, но неразрешима следующая проблема: поданным слзвам а, Ь узнать, существует ли натуральное число х такое, что аО" = бО.

5. Пусть / (г) -- рекурсивная числовая функция п ® - групповое исчисление с порождающими элементами а, a~i, Ь, Ъ~, с, с~, d, и (рекурсивно перечислимой) бесконечной совок}щностью определяющих соотношений

= ЬЬ-1 = сс-1 = dd- - - Л,

j/W (Ь-1)/М = (d-i)W (X = О, 1, 2, . . .).

Еслп совокупность значений функции / не рекурсивна, то проблема равенства слов в (S неразрешима (Р а б и н [1], X и г-

6. Пусть S( - групповое исчисление с порождающими эле-,ментами а, а~, . . ., а, а~ и иекоторым бесконечным рекурсивно перечислимым множеством определяющих соотношений. Тогда существует групповое исчисление S с порождающими элементами %, а, . . ., fls, а~ и некоторыми дополнительными порождающидш элементами bi, b~, . . ,, b,, b имеющее конечное число определяющих соотношений и такое, что эквивалсптность произвольных двух слов в алфавите а[, . . ., а, а~} в группеS( равносильна эквивалентности этих слов в группе (т. е. 21 является подгруппой в группе аЗ). Беря в качестве % группу, построенную в предыдущей задаче, и конструируя для нее группу §5, получим групповое исчисление с конечным числом определяющих соотношений и неразрешимой проблемой равенства (X и г м с н [1]).

7. Пусть 5( - свободная полугруппа с свободными порождающими элементами а, Ь, % - декартов квадрат SJ, т. е. полугруппа пар (й, Ь) (й, 6 G 21), перемножаемых по закону

(а,Ь)(с,Ь)=(йС,ЬЬ),

Диагональная подполугруппа - это совокупность пар вида (й, й). Общая комбинаторная проблема Поста: существует ли алгоритм, позволяющий для любой конечной системы пар (ui, bi), («2,62)1 • • •> (й/, b<) решить, пусто или нет пересечение диагональной подполугруппы и подполугруппы, порожденной заданной системой пар.

Ограниченная комбинаторная проблема Поста: для фиксированного натурального числа s > О указать алгоритм, позволяюпщй для любой системы, состоящей из s пар (ai, bi), (uj, 62). • • • • • •! (us, bs) решить, пусто или нет пересечение диагональной подполугруппы и подполугруппы, порожденной упомянутыми s парами.

Показать, что ограничепная проблема Поста (для больших s) решается отрицательно (Пост [4], М а р к о в [2]).

8. В полугруппе всех целочисленных матриц 4-го порядка существует конечное чпсло матриц таких, что порождаемая ими под-полугрртпа нерекурсивна (Марков [3]).

9. Прямое произведение двух свободных групп с двумя порождающими элементами содержит нерекзфсивную подгруппу с конечным числом порождаюпщх элементов. Отсюда следует, что группа целочисленных матриц 4-го порядка с определителем 1 содержит перекурсивную подгруппу, имеющую конечное чпсло порождающих элементов (Михайлова [1]).

10. В п. 13.2 доказано, что элементарная теория класса всех иолугр}Т1п нерекурспвна. В книге Тарского, Мостов-ского п Р. Робинсона [1]ив обзоре Ершова, Лаврова, ТаймановапТайцлпна [1] подробно исследованы элементарные теории многих важных классов моделей и алгебр. Некоторые из относяпспхся сюда результатов указаны в этой п следуюнщх задачах.

Показать, что элементарная теория полугрлшпы iN; -[-> рекурсивна (Пресбургер, см. Ершов, Лавров, Таймановп Тапцлин [1]).

И. Совокупность всех истинных абсолютпо замкнутых формул 2-й ступени, не содер;кащпх функциональных символов и содержащих из предикатных символов лишь знак равенства и одноместные предикатные символы, является рекурсивной.

12. Элементарные теории кольца всех действительных чисел <С; х> и кольца всех комплексных чисел рекурсивны (Т а р-скийиМаккинси [1]).

13. Элементарная теорпя кольца всех целых чисел нерекурсивна.

14. Элементарная теория поля всех рациональных чпсел нерекурсивна (10. Робинсон).

15. Элементарные теории всех метабелевых групп и всех конечных метабелевых групп неразрешимы (Мальцев [1]).

16. Элементарные теории всех конечных симметрических групп и всех конечных простых групп неразрешимы (Ершов [1]}.

17. Говорят, что предикат Р (ж, . . ., ж„), определенный на множестве натуральных чисел N, принадлежит классу Ps иерархии Клини, если его можно представить в виде

P():)(Vt)i) (3t)2). .(Vt), i) (3t),) [F (у, t)i,. .., t),) = 0) (s четно) или соответственно в виде Р{Х) (3t)i.) (V92). . . (У9з ) (39) {F (X, 1)1, ...,DJ = 0) {s нечетно),

где F {X, Он • •> Vs) - подходящая общерекурсивная функция. Преди1ат Р называется принадлежащим классу если Р принадлежит классу Pj. Наконец, говорят, что предикат Р принадлежит классу jRs, если Р принадлежит одновременно классу Ps и классу Qs- Отсюда следует, что класс Р совпадает с классом всех рекур-. сивно неречислтшх предикатов, а класс - с классом рекурсивных предикатов. Далее,

РСР,,1, P,(ZQs,x, Q.CP,,i, Q,CQ3+r

Прп помощи нумерационных функций С", C„i легко доказывается, что каждый предикат Р (х) класса Ps представим в форме

Р (Г) (VFi) (BY,). . . (Vr,.) (3F ) (E (X, Fj, . . ., F ) = 0)

(F - общерекурспвная функция) для четных s и в аналогичной форме для нечетных s.

18. Объединение классов Р, Ро, . . . совпадает с классом всех арифметических предикатов.

19. Наряду с иерархией Клинп иногда рассматривают и ариф-метпческ5чо иерархию. А именно, говорят, что формула вида

(QiPi). .. (Qt)) а (Г, 1)1,...,9з),

где символы Qj означают кванторы V, 3, Qj = Qii, щ = (yj, . . . • •, У1т>< S( - арифметическая форм5-ла, не содержащая кванторов и, следовательно, построенная из предметных символов О, 1, II, . . ., хп, Ух], функциональных символов -J-, X и логических символов =, &, V, ~1, имеет тип Qj . . . Qj. Например, формула

(Vxy) (Эк)(Уу) (x + у = Q М (х + у) (и + v) фО)

имеет тип V3V. Определенный на натуральном ряде предикат Р (х) пазывается предикатом типа Qi. . . Qj, если существует такая арифметическая формула % (х) данного тина, что Р (х) а (х), где 21 не содержит свободных предметных переменных, отличных от х-х, . . .,-Хп.. Каждый арифметический предикат типа (V3) принадлежит классу jPgs иерархии Клини и, аналогично, арифметические предикаты типов 3 (V3)% (V3)V, (3V) принадлежат соответственно классам Pas+ii Qas+i. Qas-

20. В п. 16.2 показано, что каждый рекурсивный предикат имеет одновременно типы V3 и 3V. Поэтому предикат класса Ps заведомо имеет тип (V3)V.

21. Множество натзфальных чисел М имеет данный класс в иерархии Клини, если этот класс имеет соответствующий одномест-Есый предикат. Аналогично определяется и арифметический тип множества. Показать, что множество номеров замкнутых истинных арифметических формул тина (V3) имеет класс jPjs, типа (3V) имеет класс Qjs и т. д. Обратно, каждое множество класса Ps имеет тип (V3)V и т. д.

22. Легко видеть, что если бы для некоторого s все мнолмства класса Ps принадлежали классу Qs или все множества класса Qs принадлежали классу Ps, то все высшие классы Ps+i, Ps+i., • • • совпадали бы и, следовательно (см. предыдущую задачу), совокупность номеров всех истинных арифметических формул была бы арифметической. Таким образом, для каждого S JPj Qs, Qs Ps (теорема иерархии Клини) (см., например, Д е в и с[1], с. 156).

23. Пересечение и объединение конечного числа множеств, принадлежапщх одному из классов Ps, Qs, В, принадлежит тому же классу. Класс множества не меняется ири взашшо однозначных рекурсивных отображениях натурального ряда на себя. Если Mq - мтгожество четных чисел, имеющее класс jPj и не принадлежащее клаосу Qs, а Jlfi - множество нечетных чисел, имеющее класс Q и по принадлежащее классу Pg, то Л1"о U Mi принадлежит классу Bf+i и не принадлежит классам Ps, Qs.

24. Если Р (1, . . ., Хт) - предикат одного из классов Клини и / (xi, . . ., ж„) - общерекурсивная функщш, то предикат Р а (хх, . . ., Хп), х2, . . ., Жда) принадлежит тому же классу, что и Р.

25. Классом частичной функции называется класс ее графика. Класс предиката содержится в классе его характеристической функции. Если предикат класса Р или класса Qs, то характеристическая функцпя этого предиката лежит в классе Rs+i-

26. Доказать формулы

(Эх < z) (Vy) Р (x, у, и) (Vy) (Эх < Z) Р (x, Г (у, х), и), (Vx < z) (Эу) Р (x, у, и) (Эу) (Vx < 2) Р (x, Г (у, х), и),

где Р - произвольный предикат, Г (х, у) - функция Гёделя.

27. Стгерпозпцпя всюду определенных функций класса Rg принадлежит тому же классу Rg.

28. Если функцпя / (х, у, z) принадлежит классу Rs и фтакция g (х, у) = U- (/ (х, у, z) = 0) всюду определена, то функцпя g принадлежит также классу Rs (см. формулы, указанные в задаче 26). Из этого результата и результата, жазанного в предыдущей задаче, вытекает следчошая теоре.ча Поста о кванторно.ч представлении: еслп всюду определенные флнкцип fi, ...,/„; принадлел;ат классу Rs, то каждая всюду определенная функция, рекурсивная