---

119 $9. АКСИОМАТИЗИРУЕМЫЕ КЛАССЫ моделей К, то Л изоморфно вложима в подходящее ультрапроизве- дение моделей из К. М (M; о) и 21. Пусть D (M) т3 (м'; oUм) вложима в (M; о). системы = диаграмма есть — модель для D (M). Доказать, что М изоморфно 22. Пусть М - (M; о) ной сигнатуры. Доказать, что существует 3-предложение А сигнатуры а такое, что для любой системы М %3D (M; а) А истинно в Л тогда и только тогда, когда Л изоморфно вложима в М. — конечная алгебраическая система конеч- 23. Пусть о—конечная сигнатура, Я, - (M; о) (iE)-— система ко- нечных алгебраических систем сигнатуры а и существует п такое, что MS n. Доказать, что для любого ультрафильтра D над 1 существует iEl такое, что Пя/D « M,. 24. Пусть Т - (M; о) —алгебраическая система, А—непустое под- множество М и М, %3D (М; о) (1E)—семейство всех подсистем в Л та- ких, что Л2. Доказать, что М %3D (ОM; а) есть подсистема в M, = порожденная множеством А. 25. Доказать, что если и, 3 (м,; o) есть подсистема системы л, порожденная множеством А, то М, есть множество всех значений тер- мов сигнатуры о, когда переменные принимают значения в мно- жестве А. 26. Пусть Т %3D (M; о), А -непустое множество М. Доказать, что подсистема Л", порожденная множеством А, имеет мощность не более чем таx(4, д, к,1. 27. Доказать, что каждый аксиоматизируемый класс состоит из обеднений алгебраических систем некоторого универсально аксиома- тизируемого класса. 28. Доказать, что каждая система из аксиоматизируемого класса К конечной сигнатуры содержит конечную или счетную К-подсис- тему. 29. Пусть К- аксиоматизируемый класс, сигнатура о которого имеет мощность р и пусть M %3D (M; о) -некоторая К-система. Дока- зать, что каждое подмножество AСМ, имеющее мошность т, со- держится внутри подходящей К-подсистемы системы Л мощности не выше р + m + (теорема Левенгейма-Скулема).
Ч.П. МАТЕМАТИЧЕСКАЯ ЛОГИКА 120 30. Доказать, что каждая бесконечная система М %3D (M;B a) ак- сиоматизируемого класса К допускает К-расширение любой на.леред заданной мошности, большей М + о. 31'. Построить пример аксиоматизируемого класса К такого, что класс К содержит конечные модели со сколь угодно большим числом элементов, а все бесконечные модели из К имеют мощность не меньше мощности континуума. 32". Построить пример аксиоматизируемого класса К такого, что в К существует счетная модель, а все отличные от нее модели класса К, являющиеся расширениями этой модели, имеют мощность, не мень- шую мощности континуума. 33'. Доказать, что если аксиоматизируемый класс К содержит сис- тему мощности m2Xо, то для любого п>2 существует К-система Mощности п. 34. Предположим, что справедлива обобщенная гипотеза конти- нуума: для любых кардинальных чисел т, п из тsns2" следует, что m %3D n или n%3D2". Доказать, что тогда для любого аксиоматизи- руемого класса К справедливо в точности одно из следующих условий: (а) мощности конечных систем из К ограничены некоторым нату- ральным числом, и К состоит лишь из конечных систем; (б) мощности конечных систем из К ограничены некоторым нату- ральным числом, и существует бесконечное кардинальное число т такое, что для любого бесконечного кардинального числа п класс К содержит модель мощности п тогда и только тогда, когда nzm; (в) мощности конечных систем из К не ограничены, и существует бесконечное кардинальное число тS2"о такое, что К содержит систе- му бесконечной мощности п тогда и только тогда, когда пzm. Привести примеры классов для каждого из случаев (а), (б), (в). 35. Доказать, что если ф: М -М— элементарное отображение, то ф одно-однозначно и для каждой формулы А (х,, , х.) и любых т, ...., т, еЕМ имеем тA(т.... т,) л"НA ( (m, )..p (m,)). 36. Пусть П %3D (N; <), M %3D (M;B <), где N-множество натураль- ных чисел, М-множество положительных целых чисел. Показать, что Л и М элементарно эквивалентны, но Л не является элементарным расширением Т. 37. Пусть М-—множество четных чисел, M %3D (M;B <), N%3D (M; <), где — обычный порядок. Является ли Л элементарной подмо- делью 1?
$9. АКСИОМАТИЗИРУЕМЫЕ КЛАССЫ 121 С%3 38. Пусть R%3D (&; +, -) -поле действительных чисел, — (8; +, :)-поле комплексных чисел. Является ли € элементарным расширением &? 39. Доказать, что для любого ультрафильтра D над І каноническое отображение p: M- M'/D, oпределенное условием ф (Б) 3Dfl D, где f () 3D В для всех іEl, является элементарным вложением М в Т/D. Доказать, что если М - конечная система, то о есть изоморфизм M на Уn'/ D. 40. Пусть П, (м,; $) — линейно упорядоченные множества (nEN); M. содержит 2n +1 элемент. (а) Построить изоморфизм множества целых чисел (Z; <) в | /D, если D — неглавный ультрафильтр на . п EN (6) Будет ли этот изоморфизм элементарным отображением? 41. Пусть FD(18) есть полная диаграмма системы Л %3D (M; о) и In' %3D (M'; оUM)— модель для FD(N). Доказать, что Л элементарно вложима в (M'; о). 42. Доказать, что для любой бесконечной системы М 3 (M;B о) и любого кардинального числа т существует элементарное расширение системы Л мощности, большей т. 43. Пусть Т %3D (M;B о) есть подсистема системы M' %3D (M'; о). Дока- что для того, чтобы Т была элементарной подсистемой П", х, у) зать, необходимо и достаточно, чтобы для любой формулы А (х,, EМ из М ЗуА (т,, сигнатурыа и любых т, ..., т, т,, у) следо- .. n' вало существование такого тEM, что л A (т,,..., т,, т). 44. Доказать, что каждая бесконечная система конечной или счет- ной сигнатуры а являстся элементарным расширенисм счетной систе- мы сигнатуры а. 45. Пусть Пn - (M;B о)—бесконечная система, XСМ и m - такая мощность, что max (0, X, N<MSM. Доказать, что существуст эле- мснтарная подсистема M 3D (M'; а) мощности т такая, что ХСМ'. 46. Пусть М (M; о) казать, что И обладает элементарным расширением мощности т. 47°. Пусть Т,,. — бесконечная система и т2max{M, а}. До- т, ...-множество систем таких, что . i+1 ссть .ос элементарное расширенис И, для любого і Доказать, что UM, есть i элементарное расширение каждого N.
Ч.П. МАТЕМАТИЧЕСКАЯ ЛОГИКА 122 48°. Доказать, что класс К аксиоматизируем тогда и только тогда, когда К является абстрактным, замкнутым относительно ультрапро- изведений и замкнутым относительно взятия элементарных под- систем. 49°. Доказать, что класс К систем сигнатуры о универсально ак- сиоматизируем тогда и только тогда, когда для любой системы M сигнатуры о из т го, что каждое конечное обеднение каждой конечной подмодели систе ы М изоморфно вложимо в некоторую К-систему, следует, что Л п. инадлежит К. 50. Показать, что класс К тогда и только тогда универсально аксиоматизируем, когда К является замкнутым относительно ультра- произведений, абстрактным и наследственным (замкнутым относи- тельно взятия подсистем). 51. Пусть класс К аксиоматизируем, а SK- класс систем, изо- морфных подсистемам К-систем. Доказать, что класс SK универсаль- но аксиоматизируем. 52°. Доказать, что для того, чтобы М и Л, были элементарно эквивалентны, необходимо и достаточно, чтобы существовал такой ультрафильтр D над 1, для которого сушествует элементарное отобра- жение М в Лn;/D. 53. Доказать, что если Л и Л, элементарно эквивалентны и Л конечна, то л, конечна и изоморфна Л. 54. Доказать, что для того, чтобы непротиворечивая теория Т была полной, необходимо и достаточно, чтобы все ее модели были элемен- тарно эквивалентны. 55. Показать, что класс моделей категоричной теории состоит (с точностью до изоморфизма) из одной конечной системы. (Теория на- зывается категоричной, если все ее модели изоморфны.) 56. Пусть T-элементарная теория, не имеющая конечных моде- лей, которая т-категорична в некоторой бесконечной мощности т. Доказать, что Т-полная теория. (Теория называется т-категорич- ной, если все ее модели мощности т изоморфны.) 57. Доказать, что теория плотно упорядоченных множеств (см. за- дачу 13 из 5 части I) без наименьшего и наибольшего элементов является полной. 58. Пусть Г—полное множество предложений сигнатуры о, Го2г, г,2Г— два непротиворечивых множества предложений таких, что все предметные константы из Г. и все функциональные и предикатные 0 символы из Г, входят в о. Доказать, что множество Г. ОГ, непротиво- речиво.
89. АКСИОМАТИЗИРУЕМЫЕ КЛАССЫ 123 59. Пусть Г полное множество предложений сигнатуры о, А — предметные константы которого входят в предложение, все TU{A) непротиворечиво. Доказать, что если Г выполнимо в системе M 3D (M; с), то множество (А)UFD(M) непротиворечиво. о, (M; о,), 60. Пусть Т %3 (M; а) есть обеднение системы Л, , — (М,; о) — элементарное расширение Л. Доказать, что существу- ет элементарное расширение Л, — (M; о,) системы М, такое, что (МM,; о) есть элементарное расширение М2. 2 1 61°. Пусть Г-полное множество предложений сигнатуры о, А— предложение сигнатуры о 20, В —предложение сигнатуры а,20 и Па, константы В входят в о. Доказать, что если ГU{4} и ГU {В} непротиво- речивы, то U{A, B} непротиворечиво. —о, причем все предметные константы А и все предметные 62. Пусть Г-полное множество предложений сигнатуры о, А— предложение сигнатуры о,20 и 3 о. Доказать, что если ГU{A} и ГU{B} непротиворечивы, то предложение сигнатуры о,20, В — о. rU{А, B} непротиворечиво. 63'. Пусть А—предложение сигнатуры O В предложение сиг- (АЭВ) в Ип, а - А и В невыводимы в ИП. Доказать, что натуры о, и о3оПо, непусто и существует предложение С сигнатурыс такое, что н (А5С) и н (СЭВ) в иП (интерполяционная теорема для Ип).
ЧАСТЬ ШІ ТЕОРИЯ АЛГОРИТМОВ 81. ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ числовые функции /"(х,, ..., х,) (п %3D 1, 2, ...), т. е. функции, определенные на некотором под- Будем изучать частичные МCм" с натуральными значениями. Для любых множестве Ла, ...а) - ,а) не опреде- а, ..., а,EN и любых фуккций /* и д пишем если значения/ (;} -в а,я). е1иg (а, лены или эти значения определены и совпадают. п-мсстная функция /"(х,, ) называется всюду определенной, если д ". Следующие всюду определенные функции назовем простей- = шими: sx) %3D х + 1, о'(x) %3 0, *, ..., х,) %3 х, (при 1<m<n). т Будем говорить, что функция h" (x, ..., х) %3D" F (*, ... *),.( *) получается с помощью оператора суперпозиции из функций g", "......". Скажем, что функция A" (к..) 3" ( . получается с помощью оператора подстановки из функций g, Л. если из переменных, есть одна , . х, ), где х,, ..., х, или , есть одна из персменных х,, .., х,. Скажем, что функция /" (х,, ..., х, у) получается из функций 8" (х ... х,) и к**? (х,, ..., х , у, z) с помощью оператора при-
S1. ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ 125 митивной рекурсии, если она может быть задана схемой примитив- ной рекурсии: (x. ..., х, о) %3D2" (*р . х. " (x, ..., х,, у + 1) %3D"т* (х,, ..., х,, у, /7+1, X У)). Для п 3D 0 схема примитивной рекурсии имеет следующий вид: Г (0) %3D а, /у+ 1) %3D8 (у./ (), где а — постоянная одноместная функция, равная числу а. Будем говорить, что функция /" (х,, ..., х,) получается из функ- ции g1+1 (х, ..., х,, у) с помощью оператора минимизации (и-опе- ратора), и обозначать " (х ., х) % иуls"* (х, ..., х, у) — 0], если выполнено условие: /" (х,,., х) определено и равно у тогда и только тогда, когда g (х, 1" х,, 0), и не равны 0, a g (x,, ..., х,, у) — 0. ...., х,, у - 1) определены Функция /(х,, , х,) называется примитивно рекурсивной (прф), ссли она может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции и примитив- ной рекурсии. Функция /(х,, ..., х,) называется частично рекурсивной (чрф), если она может быть получена из проюстейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рскурсии и минимизации. Функция /(х,.., х,) называется общерекурсивной (орф),, если она частично рекурсивна и всюду определена. Говорим, что функция /"(х, х) получается из функций у1+1 (х,, ..., х,, у) и" (х,, ..., х,) с помощью ограниченного и-опе- му [+1 р..., х, и не болыше, чем h (x,, ратора, если (х,, ..., х,, у) %3D 01 определено для всех , к), и ) 3 иуis* "( (х, .... х у) %3 0ј.
Ч. Ш. ТЕОРИЯ АЛГОРИТмов 126 4. Говорим, что функция /"*1 получается из д", h"**+1 возвратной рекурсией, если она может быть задана схемой ,х, 0)%3D в" (х,. ... хр. (Х. n' , Ха У./ (х. у+1)3D hn+s+1, *р 4 (у + 1)), ... n' .( хр (у + 1))), где , (у + 1)sу, ..., , (у+ 1)sy. Используем обозначение " (x, . 3 дуs(x,....х, 9) — h (х,. х у) 1, , * если выполнено условие: (*,, ..., х,) определено и равно у тогда и и h (х,, ..., х, ) определены но 8 (x,, ..., х, ) %+ h (x,,..., х,, ) при i<у и когда в (х,, .. , хр ) только тогда, для і 3 0, 1, , у, 8 (xр.х у — һh (x. ...., у). Подобным образом используются обозначения: мyls (x, .... у) * h (x, .. х ), му!s (x,, .., х, у) sh (x, ... * У) , мyls (x,, ..., х, у) <h (x,, ..., х, у)1 и т. д. Будем говорить, что функция / (х) получается из функции g (x) с помощью итерации, и обозначать f (х) %3Dig (x), если J/(О) %3 0, Будем говорить, что функция / (х) получается из функции g (х) с помощью обращения, и обозначать / (х) %3Dg(х), если f (х) %3D ну!s (у) %3D х). Пусть G — некоторое семейство п-местных частичных функций. назовем универсальной функцией для G, если G%3D (F (0, х ... х,), F (1, х,, .., х,), ..3. Функцию F1+1 1. Доказать, что любая примитивно рекурсивная функция всюду определсна. 2. Доказать, что если функция /" (х,, .., х) примитивно рекур сивна, то следующие функции примитивно рекурсивны:
S1. ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦии 127 (а) 7, (х, * (6) f, (х,, *р .х%3D/(р х) %3D (х» х, . х) (перестановка аргументов)%; ..., х,, х,) (циклическая перестановка аргумснтов)%; х, х,*) %3D/ (х,. ... х,) (введение фиктивного аргу- (в) fs (xр. мента); (m /4 (х. ..., х-р 3/(х,, х,, .... х, -) (отождествление аргумен- тов). 3. Какие функции получаются из простейших с помощью лишь суперпозиций? 1 4. Доказать, что из о" и Г митивной рекурсии нельзя получить функции х + 1 и 2х. с помощью суперпозиций и схем при- 5. Доказать, что следующие функции примитивно рекурсивны: (а) f (х) %3D х + n; (б) / (х) %3D п; (в) / (х, у) %3D х + y; (г) f(х, у) %3D х*у; (д) /(х, у) %3D х (здесь 0°3 1); (е) / (х) 3D х! (здесь 0!- 1). 6. Какая функция получается из д и һс помощью схемы при- митивной рекурсии: (а) g (x) %3D х, h (х, у, г) - г"%; (б) g (х) %3D х, h (x, у, г) %3D х*? 7. Доказать, что следующие функции примитивно рекурсивны: |0, если х 3D 0, |1, если х>0%; (а) sg (x) %3D 0, если х>0, (6) Sg (х) %3D если х 3 0; если х - 0, |х — 1, если х>0; (в) х 1%3D 0, х - у, если х> у; если хSy, (г) х — у%3D (д) 1х — у1; (е) max (х, у); (ж) min (x, у). 8. Доказать следующие равенства: (а) х - у %3Ds (x) - s (у);