И.А. Лавров,Л.Л. Максимов-Задачи по теории множеств, математической логике и теории алгоритмов (Учебник Лаврова 2006-го года), страница 38

Тогда 1)1' 1— : К', 1)1 ! * 1 = (М,; !у) — конечная или счетная К-подсистема %. 29. Аналогично задаче 28. 30. Пусть Х вЂ” система аксиом для К, т > % + о, % = (М; о')— ! 1' модель для Х 1.1 21(1)1) мощности большей, чем ш 1см. задачу 18) . Пусть М С А с М, л = т. Далее применяем задачу 29. 1' 31. Пусть о= (Р ~ уЕ 2 ), Х вЂ” система всех формул вида у ЛхР (х)длявсеку Е 2 иформул вида(Эх! ... 3х (!х,= х $-!х,= 4' = х 8... $ -! х, = х ) ~ Ы х(! Р (х) ч -! Р (х))) для л = 2~, (у(0), ...

..., у(л! — 1)) ы (а(0), ..., а(ун — 1)), ун = 1, 2, ... Класс К всех моделей для Х содержит конечные модели мощностей 2'в (ло = О, 1, 2, ...); все бесконечные модели из К имеют мощность ге с. 223 Ч и. МАТЕЫАТИЧПСКАЯ ЛОГИКА Я 9) 32. Пустьа= (г [ у(=2 ) () (а [ уЕ2 ), где [у) =(у(0), .4' , у(т — 1)), Х вЂ” система всех формул вида а = а[3 для [у[ м [о1„, Уз(а )=а дляд,уЕ2 3' 4' )( х(ях) = у (х) ~ч х = а,.), где 1 = 2 ' О ...(3 2 (Е( Ф' = [О, 1, ...,/с — Ц, [о[ Ф [у1 Ф' тогда (м(а), где м= О 2 '", а = [у[, /3([у[ ) = [о1 есть счетная модель для Х, все собственные расширения которой имеют мощность не меньше, чем с.

33. Пусть К есть класс всех обеднений универсально аксиоматизируемого класса К' сигнатуры а' (см. задачу 27), % = (М; о) Е К, % = ш. Возьмем Й' = (М; а') Е К'. Пусть|", Лв Е сг', полагаему" — к" Ф1'"(т1, ..., т„) = д "(т,, ..., т ) для любых т,, ... ..., т Е М. Из каждого класса эквивалентности выберем по одному функциональному символу, о' получается изо'опусканиемостальных функциональных символов. Тогда о' содержит не более, чем 2 функциональных символов.

Пусть К" — класс, система аксиом которого получается из системы аксиом для К' заменой функциональных символов из а' на эквивалентные им из о", % — система из К" мощности и, > и (см. задачу [8), 3)[ — подсистема й, порожденная мно- 1' жеством мощности п. Тогда уй = п (см.

задачу 25), й Е К" и 3[( 2 2 2 может быть обогащена до системы 3В Е К'. Тогда обеднение сисгемы 3 % досигнатурыавходитвК. 34. Следует из задач 6 и ЗЗ. Примеры: (а) В = (г 1; (б)Х=[(Ю З8л~,),(8 ЭЮ ),...); (в) К. ч' 35. 3[( ~ -~ т,= т ~ Й' ~ -~(г(т ) = р(т ); % 'у'А(т, ..., т„) ~ ~ 5[( ~-~А(т(, ..., т ) 9Я' ~-ъА(р(т1), ...,у>(т )).

224 ОТВЕТЫ, РЕШЕНИЯ. УКАЗАНИЯ 36. Отображение у:.4' М, где р(п) = п + 1, есть изоморфизм 8) на %, поэтому 5) и % элементарно эквивалентны. Возьмем А(х) = Чу (х и у). Тогда % 'р А(1), 8) 'р А(1). 37. Нег. Например, формула 3 х (х Я 28 -! х = 08 -! х = 2) истинна в 5), но ложна в%. 38, Нет. Например, формула Ч х 3 у (у.у = х) истинна в 8, нолож- на в В. 39.

% р А (Ь, ..., Ь ) ~ (! ~ % у А (Ь,, ..., Ь )) = / Е Р ~ П%./Р ~А(/,/Р, ...,/ /Р), где/(!) = Ь. (/= 1, ..., гп). Если % 1Е1 конечна, то %1/Р = %. 40, (а) Например, положим для п Е 4', ! 1Е,Х 11, ЕСЛИ ! < П,, ( -й ЕСЛИ ! < П, ~(п)(!) (и если ! > гг р( и)(!) ~-п если !' > п Тогда Р(п) = !/ (и)/Р есть изоморфное вложение Я' в П % /Р. ае ~У !б) Нет. Формула Эльбу(х Я у) истинна в П %./Р, но ложна ! 1П Х в Я'. 42. Из задачи 18 следует, что теория Т = ЬР(%) имеет модель %1 такую, что %, > ш. Тогда % элементарно вложима в %, (см.

задачу 41). 43. Доказать индукцией по числу шагов построения формулы В (х,, ..., х„), что для любых !и, ..., гп Е М % ~В(п!1,.„., Е) %, ЬВ(гп,, ..., !п2). 44. Пусть % = (М; а) бесконечна, А — счетное подмножество М. Положим А = А. Далее, если А уже определено, то для любой о и формулы А(х, ..., х,у) и любых а, ..., а Е А таких, что % РЭуА(а,, ..., аг, у), выбираем а = 6(А, а, ..., а ) Е М такой, что % ~А (и, ..., а„, а). Тогда А есть объединение А и множества всех Ь (А а, ..., а ), а % = ( 11 А; о/ есть счетная элементарная л !!н 4' подмодель % (см. задачу 43). 45.

Аналогично задаче 44. 4б. Следует из задач 42 и 45. Ч. 11. МАТЕМАТИЧЕСКАЯ ЛОГИКА [5 9[ 225 47. Доказывается индукцией по числу шагов в построении формулы А. Рассмотрим лишь случай А = Ы хВ (х). Пусть й. [ Ы хВ(х), но 1 й [1Ы ХВ(Х). ТОГда й Г 3 Х -а В (Х) И й 'р-1 В(а) дпя НЕКОтОрОГО а Е М. Имеем а Е М.

для некотороп11 > 1. По предпололсению индук- 1 ции для формулы В имеем %. )(В(а), отсюда й. ~3х.~В(х) и ! 1 й. ~ 3 х -1 В (х), так как й ..с й Противоречие. 48. Пусть Х есть множество предложений, истинных в К, %в модель для Х. Пусть б — конечная совокупность предложений из ГР(й),А (с,, ..., с ) — конъюнкция формул из б,с,, ...,с — все предметные константы, не входящие в щ Тогда имеем й ') 3 х, ... 3 х А (х,, ..., х ) и, следовательно, существует система й Е К такая, что й ~3х ... 3х А (х, ...,х ); существуют элементы И~, ..., 11~ нз й такие, что й рА (о,к, ..., оА). Для с из й положим с1 (с) = с[,, если с = с,; с( (с) равно произвольному элемен- А А . А ту из й, если с Ю (с,, ..., с ).

Пусть 1 есть множество всех конечных 1' ''"' а ' совокупностей Л С ВР(й), Р— фильтр над 1, содержащий все множества 1„= (б' ~ йд, рА„(с1А, ..., Р)), й, = П% 1Р. Для с нз й Ан) полагаем [о(с) =1 /Р, где 1 (Ь) = Р (с);(о(с) есть элементарное вложение й в %1. Обратное утверждение следует из задач 3 н 4. 49. Пусть класс К универсально аксиоматизируем, й — система сигнатуры о н каждое конечное обеднение конечной подмоделн й изоморфно вложимо в подходящую К-систему. Тогда (см. задачи 4 н 20) 5Й иаоморфно вложима в К-систему и й Е К. Обратно.

Пусть Х вЂ” семейство всех Ы-формул, истинных на всех системах из К, и система й есть модель для Х. Покажем, что если выполнены условия задачи, то й Е К. Пусть й, есть конечное обеднение конечной подмодели й, А есть 3-формула для й из задачи 22. 1 Тогда й вложима в некоторую К-систему, так как в противном слу- 1 чае Х в ч А (ч А эквивалентно Ы-формуле) н й ~ и А. Поэтому й Е К. 50. Следует из задач 20, 48 и 49. 5Е Следует из задачи 50. 52. Использовать указание к задаче 48. Взять класс всех систем, элементарно эквивалентных %1, в качестве К и й, в качестве й . 53. Если й содержит и элементов, то й, тоже.

Из задач 52 и 39 следует й, = й. 3 И.А. 1!варов, Л.Л. Максимова 226 ОТВЕТЫ, РЕШЕНИЯ, УКАЗАНИЯ 55. Следует из задач 18 и 53. 56. Пусть Т неполна. Тогда для некоторого предложения А не выполняется ни Т ~А, ни Т 'Г -~ А. Поэтому существуют счетные модели й, и й теории Ттакие, что й 14А, й 11-~А. Тогда существуют модели йзн й та~не,что %3 = й = п1,% -4%3,%2чй4 (см. зада- 4 ' 3 4 ' 1 чу 46). Поэтому й и й неизоморфны. 57. Теория Х, -категорична (см. задачу 13 из б 5 части 1) и поэтому полна (см.

задачу 561. 58. Пусть Г, 12 Г противоречиво. Тогда противоречиво некоторое подмножество Г 0 (В, ..., В ], гдеВ.~ Г, х > О. Поэтому Г ~--~(В,8... ЪВ ) и Г 1-Чх, ...Чх,-~В(х,, ..., х,), гдеВ (с,, ..., с,) = (В,$...8В ), с, ..., с — всеконсгантыизВ ...„В„, не входящие в о.

Так как Г полно н Г непротиворечиво, имеем Г РЧх ... Чх -~ В(х,, ..., х), поэтому Г, ьЧх ... Чх .~В (х, ..., х ) и Г, ь -~В (с, ..., с,). Противоречие. 59. Следует из задачи 58. 60. Пусть Г = ВР(й ) 1.1 ВР (й ). Любая система, в которой истинны все формулы из Г, удовлетворяет требованиям задачи. Непротиворечивость Г доказывается аналогично непротиворечивости Г, 11Г, из задачи 58. 61.

Пусть Г 1.2 (А] выполнимо в й = (М,; сг,), й = (М; о). Тогда РР (й') 12 (В] непротиворечиво (см. задачу 59) и выполнимо в% = (М; о ). Имеем% сй = (М; о). Поэтому существует система й =(М;о,) такая, что %1' %3' %гав %3=(М3'о)' Получаем последовательность й, й, й, ... такую, что 1' й -4% 4...4% 4% -4..., й -4% .4% -4... Положим М вЂ” 13 М., ! !и Х й = (М; о 11 а ), где й'-4 (М; о), й „, . 4 (М; ст ), й 4 (М; сг ) (см. задачу 47). Тогда Г 1.1 (А, В] выполнимо в й. 62.

Пусть а, ..., а — все константы, входящие в А и не входящие в о, Ь, ..., ܄— все константы, входящие в В и не входящие в а. Тогда фор.улы А,=Зх,...ЗхА(х,,...,х), В,=Зу,...ЗуВ(у,,...,у) 227 ч. 1Н. теОРия алгОРитмов и 1! удовлетворяют условиям задачи 61 и Г 11 (А, В ) непротиворечиво. Тогда Г О (А, В) непротиворечиво. 63. Пусть Т вЂ” множество предложений С сигнатуры о таких, что (А э В). предположим, что т 11 (.4В) непротиворечиво. тогда т 11 (-~В) выполнимо в некоторой системе Й.

Далее, Г О (А) непротиворечиво, где Г есть множество всех предложений сигнатуры о, истинных в М). Иначе было бы А «-~(С,8... 8С ) для некоторых С, ..., С Е Е Г, -~ (С, 8... 8С ) 1:- Т С Г и (С 8 ... 8 С ) Е Г. Из задачи 62 следу" ет, что Г 0 (А,.зВ] непротиворечиво и неверно 1-(А З В).

Поэтому ТН (-4В) противоречиво, а значит, «((С 8 ... ЬС ) ЭВ) для некоторых С, ..., С Е Т; (С 8... 8С„) есть искомая формула. Еслип пусто, А и .~ В выполнимы, то можно построить счетную модель, в которой выполнима (А $ .з В), т. е. не выполняется «(А э В). Ч А С Т Б 111. ТЕОРИЯ АЛГОРИТМОВ 8 Е Частично рекурсивные функции 2. функции11, 1, 1 и У4 получаются суперпозициями из 1 и 1~~а: 1а)11(х,,х,, ..., ) = ) — 1(1 (х, ..., х ), 1"(х, ..., х ), 1"(х, ..., х ), ..., 1 (х, ..., х )). (6Юх1 х2 "'." )= = У (1, "(х,, ..., х ), ..., 1",, (х,, ..., х„), 1" ,(х,, ..., х )). 4.

Пусть1(х1, ..., х ) получена из о и 1" с помощью суперпозиций и 1'"' в т примитивной рекурсии. Тогда 1'(О, „„0) = 0 и х ( 1, ..., х ( 1 ~У(х1, ..., х ) ~ 1. 5. (а)1(х) = з (з (... з(х) ...)) (прав). (б) 1'(х) = з (з (... з (о (х)) ...)) (л раз). ОтВеты„Решения, укАзания (в) /(х, у) получается примитивной рекурсией из а(х) = /,(х) и л(х'у'х) з()зз(х'у' ))' (г) /(х, у) получается примитивной рекурсией из х (х) = о (х) и й (х, у, х) = 1З (х, у, х) + 1 (х, у, х). (д) /(х, О) = 1, /(х, у+ 1) = х /(х, у).