1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 30
Текст из файла (страница 30)
Дляi:13 -были элементарно эквивалентны,i:13чтобыдлялюбогоп Е wилюбойконечной сигнатуры Е1 ~ Е существовали непустые множестваF1(E1,n), ... ,Fn(E1,n) конечных частичныхi:13 1Е1 со следующим свойством:изоморфизмов Qt 1Е1в(*) еслиfЕFi(E1,n), 1 (; i < п, то для любых а Е А, Ь ЕFi+1(E1,n), для которых а Е dom91,~ 91 и f ~ 92·ЕВ существуют 91,92 ЕЬ Е rang 92,fДо к аз ат ель ст в о.Достаточность. Индукцией по mчто если длина формулы Ф(х1,н.
ф., не больше1 (; i (; n,fm, множества Fi(E(Ф), п) ~ P(Qt I Е(Ф), i:!3 1Е(Ф)),(*) и i + m (; n, то для любогоудовлетворяют условиюЕ F1(Е(Ф),п) и любых ai, ...Если Ф-делениячастичногоtдокажем,находящейся в приведенной... , xk),,akЕdomfимеет местоатомная формула, то это утверждение следует из опреизоморфизма.ЕслиФ=~\[!илиФ=Ф1тФ2,Е { /\, V, __,}, то утверждение следует из индукционного предполо= ~зх~Фжения. Так как \iхФнорассмотреть лишьслучай,для любой формулы Ф, то достаточкогдаобщности. Пусть Ф(х1,Тогда Qt р Ф(ао,а1, ......
, Xk) =,ak) для9 Е Fi+I (Е(Ф), п), чтоfФнесодержит кванторавсеЗуФ(у, х1, ... , Xk) и Qt р Ф(а1, ... , аk)некоторого ао Е А. Возьмем такое~ 9 и ао Еdom9.Так как длина Ф меньшедлины Ф, то по индукционному предположениюследовательно,i:!3 р Ф(fа1, ... , f ak),i:!3 р Ф(fа1, ... , fak)- Пусть i:!3 р Ф(fа1, ... , fak)- Тогдаi:8pФ(bo,fa1,... ,fak)которогоf~9и Ьо Едля ЬоЕВ. Возьмем 9ЕFп+1(Е(Ф),п), дляrang9.Тогда по индукционному предположениюимеем Qt р Ф(9- 1 Ьо,а1, .. ,,аk), следовательно, Qt р Ф(а1, ... ,аk)Необходимость.
Пусть Е1 ~ Едля п, т Еw --конечная сигнатура и Х(п, т)максимальное множество попарно не эквивалентныхформул Ф сигнатуры Е1, находящихся в приведенной н. ф., содержащих(; п кванторов и FV(Ф) ~ {v1, ... , vm}- Так как имеется лишь конечноечисло атомных формул с переменными из множества {v1, ... , vk}, тоm множествоIX(n, m)I неубывающая по... , ak Е А попарно различны.индукцией по п легко показать, что для любых п иХ(п, т) конечно. Очевидно, что функциякаждой из переменных п иm.Пусть а1,Гл.146Отображение5.f: {a 1, ... ,ak}-----+Теория моделейВ назовем (п,т)-изоморфизмом, еслиk ~ т и для любой формулы Ф(х1, ... , Xk) Е Х(п, т) имеет место2lp=Ф(a1,... ,ak){==}!Ep=Ф(fa1,...
,fak)·f Е P(2t I I:1, !В I I:1), дляldom fl ~ m, является (О, m )-изоморфизмом. Для i = п,п-1, ... , 2, 1 будем определять неубывающие функции 9i: w -----+ w так,чтобы множества Fi(I:1,n) = {f I f является (9i(m),m)-изоморфизмомдля некоторого m Е w} удовлетворяли условию (*).В качестве 9п берем тождественный нуль. Если 1 < i ~ п, т Е w,Ясно, что любой частичный изоморфизмкоторогото полагаемЕсли9i-1(m) = 9i(m + 1) · IX(9i(m + 1), т + 1)1 + 1.9i - неубывающая, то очевидно, что 9i+I такжещая.
Из 2(= !Внеубываюf =IZJ является (п, 0)-изоморфизмом длялюбого п Е w. Следовательно, классы F1 (I:1, п), ... , Fn(I:1, п) непустые.Пустьdom fследует, чтоf Е Fн1 (I:1, п) является (9н1 (m), m)-изоморфизмом, 1 < i ~ п,= {а1, ... , ak}, k ~ т, и а Е А. Обозначим через Ф(v1, ... , vk+1)... , Vk+1) Е X(9i(k + 1), k + 1), для которыхF Ф(а1, ... ,аk,а). Число кванторов у Ф не превосходит 9i(k+ 1) хIX (9i (k + 1), k + 1) 1, поэтому существует формула Х( v,, ...
, vk) ЕКОНЪЮНКЦИЮ всех Ф(v1,2tхЕ X(9н1(k),k), эквивалентная формуле :Jvk+1Ф(v1,... ,vk+1). Так как9i-l (k) ~ 9i-l (m), 2t F Х(а1, ... , ak) и f - (9i-1 (т), m)-изоморфизм, то!В F X(fa1, ... , fak)- Тогда !В F Ф(fа1, ... , fak, Ь) для некоторого Ь ЕЕВ. Из построения Ф вытекает, что для любой Ф Е X(9i(k + 1), k + 1)либо Ф-----+ Ф, либо Ф-----+ ~Ф является тождественно истинной форму9 = f U { (а, Ь) }, будет 9i(k + 1)-изоморфизмом, т. е.Fi (I: 1, п).
Заменив в предыдущем рассуждении 2t на !В иf на 1- 1, получим, что для любого Ь' Е В существует а' Е Ak такое,что f U { (а', Ь')} принадлежит fi(I:1, п).DСледствие 5.1.2. Если 2( и !В - алгебраические системы ко1-tеч1-tой сuтатуры I:, то для того, чтобы 2( и !В были элеме1-tлой, следовательно,принадлежиттар1-tо эквивале1-tт1-tы, 1-tеобходимо и достаточ1-tо, чтобы для любого п Е w существовали 1-tепустые м1-tожестваFi(n) <;;;; P(2t, !В), ..... . , Fп(п) <;;;; P(2t, !В) со следующим свойством:(*) если f Е Fi(n), 1 ~ i < п, а Е А и Ь Е В, то существуют 91, 92 Е Fн1 (п), для которых f <;;;; 91, f <;;;; 92, а Е dom91и Ь Е rang92.До к аз ат ель ст в о. В качестве множеств F1 (п), ...
, Fп(п) береммножества F1 (I:, п ), ... , Fn(I:, п) из теоремы 5.1.1.DСледствие5.1.3.Еслиры I; и 2( ко1-tеч1-tа, то 2(21,= !В!В-алгебраические системы сuтатутогда и только тогда, когда 2( ~ !В.Элементарная эквивалентность§ 5.1.До к аз ат ель ст в о. В предложении=3.2. 7147доказано, что для лю=бых 21 и 23 из 21 ~ 23 следует 2123. Пусть 21 23 и IAI = то Е w.Так как в 23 истинна формула Фm 0 из предложения 3.2.9, то IBI = то.Для каждого п Е w имеется лишь конечное число попарно различныхп-местных предикатов и функций на конечном множестве, поэтомуимеется такая конечная или счетная I:' <:;; I:, что если s Е R U F, тоv 21 (s) = v21 (s') для некоторого s' Е R' U F'.
Поэтому достаточно показать, что 21 1I:' ~ 23 1I:'. Пусть I:' = U I:i, где I:i конечна и I:i <:;; I:i+l ·iEwРассмотрим множества частичных изоморфизмовF1(I:i,n),где п,iЕ wи1 ~ j ~ п, из теоремы 5.1.1. Из условия (*) теоремы 5.1.1 следует, чтодля любых п, i Е w, любого k < п и любых а 1 , ••• , ak Е А существуетотображение f Е Fk+ 1 (I: 1, п), для которого а 1, ...
, ak Е dom f. Следовательно, для любого п>21 1I:nто существуетfп(I:n, п), являющийсяIB11 = IAI = IBI,то 231 = 23. Существует лишь конечное число отображений f: А-. В,поэтому существует такое число по Е w, что f по: 21 1I:n ~ 23 1I:n длявсех п Е w, следовательно, fпо: 21~ 23.Dизоморфизмомна231 1I:n,гдеЕ Fmo+I231 <:;; 23.Так какПонятие элементарной эквивалентности с некоторой точки зренияможет быть дажеболееважным, чемпонятие изоморфизма. Делов том, что изоморфизм определяется через существование некоторойбесконечной функции, в то время как элементарная эквивалентностьопределяется через конечныесистемы210и230функции.Рассмотрим алгебраическиепустой сигнатуры, у которых Ао состоит из всехсчетных ординалов, а Во состоит из всех подмножеств натуральныхчисел.
Из результатов П. Коэна о независимости в210~230нельзя ни доказать,ни опровергнуть вZFCZFC.следует, чтоВ силу же<•финитарности~ понятия элементарной эквивалентности для <•хорошозаданных,> системвергнуть вZFC.21и23отношение21= 23 можно доказать или опро21 0 = 23 0 . Конечно,В частности, легко показать, чтоне надо забывать, что понятие изоморфизма играет исключительнуюроль, например, в алгебре, так как является <•пределом~ для различныхклассификаций алгебраических систем.Если элементарная эквивалентность является ослаблением понятияизоморфизма, то следующее понятие является усилением понятия подсистемы.Определение.
Подсистема23 <:;; 21системы21сигнатурыI:называется элементарной подсистемой (обозначаем23-< 21), если для любойформулы Ф(х1, ... , хп) сигнатуры I: и любых Ь1, ... , Ьп Е В имеет место231= Ф(Ь1, ... , Ьп){:::::=>211= Ф(Ь1, ... , Ьп)•(5.1)Гл.1485.Теория моделей5. t .4. Пусть Qt - алгебраическая система сигнаQt. Для того чтобы имело место !В -< Qt, необходимоПредложениетуры Е и !В ~и достаточно, чтобы для любой формулы Ф(хо,...
, хп) сигнатуры... , Ьп Е В имело место Qt F 3хоФ(хо, Ь1, ... , Ьп) ==}=> (Qt F Ф(Ьо, Ь1, ... , Ьп) для некоторого Ьо ЕВ).До к аз ат ель ст в о. Индукцией по длине формулы Ф(х,, ... , хп)сигнатуры Е покажем, что для любых Ь1, ... , Ьп ЕВ истинно (5.1).Е и любых Ь1,Если Фатомарная, то-Если Ф =~Фили Ф=следует из определения подсистемы.(5.1)Ф1тФ2 длят Е {Л,... , хп) =рассмотреть лишь случай Ф(х1,случае(5.1)тоV,--+},индукционного предположения. Так как \lхФ(5.1) следует из= ~3х~Ф,3хоФ(хо,то достаточно...
, Хп),но в этомследует из условия предложения и индукционного предположения.О5. t .5.ПредложениеПустьалгебраическая система сигнаQt -туры Е и !В~ Qt. Если для любой конечной сигнатуры Е1 ~ Е, любыхЬ1,... , ЬпQtI Е1,Е В и любого а Е А существует автоморфизмQtF 3хоФ(хо,Ь1, ... ,Ьп).fb1 =для которогоДо к аз ат ель ст в о.Е А. Пусть...
, fЬп =fа ЕF Ф(а,Ь1, ... ,Ьп)ЕВ. Из предложенияfaЬп иI Е(Ф),3.2.7системыfВ, то !ВВоспользуемся предложениемТогда Qtавтоморфизм системы Qtf -на месте, иЬ1,-< Qt.Пусть5.1.4.для некоторого а Еоставляющий Ь1,получаем Qt... , ЬпF Ф(fа, Ь1, ...... ,Ьп).ОЯсно,из=-<Qt следует !ВQt. Обратное в общем случае неверно. Например, рассмотрим системы (Q(l), ~) и (Q( 2), ~).!ВQ(I), Q( 2) -гдеичтонемножестваменьшихрациональных чисел,соответственно,2а~естьнеменьшихобычное1отношение<•меньше или равно~ на числах. По предложению 3.1. 7 системы(Q( 1), ~) и (Q( 2), ~) изоморфны, следовательно, элементарно эквивалентны. Однако в подсистеме (Q( 2), ~) системы (Q(I), ~) формула= \lv0 (vo ~ v, --+ vo ~ v,) истинна на элементе 2, а в системе(Q(I), ~) эта формула ложна на том же элементе 2. Таким образом,(Q(2), ~) -< (Q( 1), ~) не имеет места.Ф(v,)Примера !В-5.1.6.плотный вПусть Qt - счетный плотный линейный порядок,Qt порядок (т.
е. !В ~ Qt и для любых а < Ь из Асуществует с ЕВ, для которого а< с< Ь), тогда (!В содержит концевыеэлементы Qt)Для{==}(В-< Qt).доказательства ~замечаем, что так какQt= !В,!В имеют одинаковые концы. Теперь пусть, например, Ьоэлемент !В. Тогда !ВQtF \lvo( vo~ Ьо--+ voF \lvo( vo~ Ьо--+ vo~ Ьо) и, значит, Ьо~ Ьо). В силу !В-fQt ипервый-<Qt имеемпервый элемент Qt. Длядоказательства ==} нужно воспользоваться предложениембуемый изоморфизмто-строится так же, как в предложении5.1.5.3.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
