1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 61
Текст из файла (страница 61)
,аn),Фдостаточно показать, чтоВ силу w-насыщенности ~ и замкнутостиVбескванторная}.Vреализуется в~-относительно конъюнкциидостаточно показать, что~для любой Ф(x,r.pa1,F ЗхФ(х, r.pa1, ... , r.pan)(8. 1)... ,r.pan) Е V. Пусть Ф*(х1, ... ,хп)бескванторная формула, эквивалентная в Т формуле ЗхФ(х, х1,... , хп)- Таккак~ F ЗхФ(х,а1, ... ,ап), то~ F Ф*(а1, ... ,ап)- Из того, что r.p изоморфное вложение и Ф* бескванторная, вытекает ~ F Ф* ( r.pa1, .... . . , r.pan). Из эквивалентности в Т формул Ф* и ЗхФ получаем (8.1).2) ==} 1).
Пусть выполнено 2). Индукцией по числу кванторовв Ф будем находить бескванторную формулу Ф*, эквивалентную в Тформуле Ф. В силу эквивалентности 'v'хФ= ~3х~Ф для любой формулыФ, достаточно рассмотреть случай, когдаФ(х1, ... ,хп)где Ф -=бескванторная формула. Если Тстве Ф* можно взять ~с~ с, где сТЗхФ(х,х1, ... ,хп),-U { Ф} несовместно, то в каченекоторая константа. Пусть теперьU { Ф} совместно.
Рассмотрим множествоИ= {8(х1,Покажем,что Т... ,хп)U И 1>Ф.1 Т 1> Ф-, е, е бескванторная}.Предположим, что этоществуют модель ~ теории Т и элементы Ь1,~F... , Ьп8(Ь1, ... ,Ьп) для всех 8(х1, ... ,хп) Е И и~не так,т. е.суЕ В такие, чтоF~Ф(Ь1, ... ,Ьп).ПустьУ= {Х(х1, ... ,хп)Если бы множество Т1~ F Х(Ь1, ... ,Ьп), Х бескванторная}.U У U { Ф}было несовместным, то в силу замкнутости У относительно конъюнкции выполнялось бы Т 1> Ф - t ~хо длянекоторого Хо Е У.
Тогда ~хо Ебы выполнимости У. Итак, Ттеории Т, а1,совместно, и пусть~-модель... ,ап,ЬЕ А,~и ~И и в силу И~ У это противоречилоU У U { Ф}F X(ai, ... , an),F Ф(Ь, а1, ... , ап).Х(х1, ... , Хп) Е У,(8.2)Взяв, если нужно, ультрастепень ~ по неглавному ультрафильтру на w, можно считать, что ~ w-насыщена (тео-Гл.3108.Разрешимые и неразрешимые теории5.5.6). Из (8.2) вытекает, что отображение tpo: {а 1 , .. ,,ап} - t В,tpoai = bi, продолжается до изоморфного вложения tpподсистемы 2t( а,, ... , ап) в SВ. (Если п = О, то в качестве tp беремизоморфизм подсистем значений термов без переменных.) По 2) tpпродолжается до изоморфного вложения tp' подсистемы 2t( ai, ... , ап, Ь)в SВ. Так как \J! бескванторная, то SВ р \J!(tp'b, Ь1, ...
, Ьп), следовательно,SВ р :Jx\J!(x, Ь1, ... , Ьп), Это противоречит условию SВ р ~Ф(Ь1, ... , Ьп),ремадля которогоТак как множество И замкнуто относительно конъюнкции, то изТU И 1> Ф следует Т U { Ф*} I> Ф для некоторой Ф* Е И. Ясно, что Ф*эквивалентна в Т формуле Ф.ОСледующая система аксиом определяет теорию ВЗП (вещественнозамкнутых полей):1) аксиомы полей,2) ~х < х,3) (х <у/\ у< z) - t х < z,4) х < у V х ~ у V у < х,5) (О< х /\О< у) - t О< х · у,6) х7) о< у - t х + z <у+ z,< х - t :3у х ~ у 2 '8) :3y(y2n+l+ LXiYi) ~ О, n ЕW.i:(;2n(F, +, ·,<,О, 1) - вещественно замкнутое поле,(F, +,·,О, 1) имеет нулевую характеристику, а (F, <) - плотный строгий порядок (т.
е. (F, <) р Vx\:/y (х <у-, :Jz(x < z /\ z < у))).В самом деле, из аксиом 6) и 3) мы получаем х < О -, пх < О иО < х -, О < пх, п Е w \ {О}, что вместе с 2) и 4) дает ~х ~ О -,Заметим, что еслито поле-,~пх ~ О,п Е w \ {О}.Из аксиом1)-6)легко выводится такжех < у -, (х < х; У < у), что доказывает плотностьПредложение8.3.3.(F, <).В теории ВЗП имеется элиминация кванторов.До к аз ат ель ст в о.Пустьа,,SВ2t,-...
, ап, Ь Е А и 'РО 2t( а,, ... , ап) неСистемапозволяютвложенияединственнымtpПрименимвещественнокритерийзамкнутыеизоморфное вложениеявляетсяобразомминимального подполяполем,SВ'РОаксиомыдосодержащего8.3.2.w-насыщено,2t(a,, ... , ап)однакопродолжить2to <:;;; 2t,предложенияполя,вSВ.l )-6)изоморфного2t( а 1 , ... , ап),в SВ.Случай1:Ь алгебраичен над2toмногочлен с коэффициентами изпредложенияв2to.2t,т. е.2tрf(b)~ О, гдеf(x) 2)Существование требуемого в8.3.2 вложения tp 1 вытекает из следующей леммы курса§ 8.4. Разрешимые теории абелевых группалгебры: если Купорядоченное поле и К1, К2-311его вещественные-замыкания, индуцирующие заданное упорядочение на К, то существует изоморфизм К1 на К2, тождественный на К.Случай 2: Ь не алгебраичен надА1= {а Е Ао l 2io F а<в2ioЬ}, А22i.Пусть= {а Е Ао l 2io F Ь < а}.Обозначим через р(х) множество всех формул вида ера< х, а Е А 1 ,хера, а Е А2 и ~ Е<ep(ci)xi :::::: О для всех многочленов Е cixi,i<nciкаi<nЕ Ао, не равных тождественно нулю вв2io{а 12ioвытекает, что для любых а, Е А1F а,<а/\ а<Из плотности поряд-2io.и а2 Е А2множествоа2} бесконечно.
Так как корней любого многочлена в любом поле конечное число, то р(х) локально выполнимо в~Ввиду w-насыщенности ~ тип р(х) реализуется в~ некоторым элементом Ь'. Так как Ь не алгебраичен над2io, то отображение ер U { (Ь, Ь')}однозначно продолжается до изоморфного вложенияСледствиеTh( (R, +,8.3.4.·,<,О,l))2i(Ao U {Ь})в~- ОТеория ВЗП разрешима и совпадает с теориейупорядоченного поля действительных чисел.До к аз ат ель ст в о.
Атомарные предложения теории ВЗП эквивалентныn :::::: m и n< m,где черезn мы обозначаем терм l+ ... + 1,являющийся суммой п единиц, если п Е w \ {О}, и О совпадает с константой О. Из аксиом ВЗП легко вытекают свойствап=/=т=*ВЗП [>п<т=*ВЗП [> nт ~ п=*ВЗП [>~n:::::: m,<~nm,<m.Отсюда мы получаем, что для любой замкнутой бескванторной(+, ·,<,О, 1) мы имеем ВЗП [> Ф или ВЗП [> ~Ф.8.3.3 теория ВЗП полна. Так как (R, +, ·,<,О, 1)формулы Ф сигнатурыВ силу предложенияявляется моделью теории ВЗП, то из полноты ВЗП получаем совпаTh( (R, +,дение ВЗП и·,<,О,l) ).Так как ВЗП имеет перечислимоемножество аксиом, то по предложениям7.5.8, 7.5.9теория ВЗП разрешима.О§ 8.4.Разрешимые теории абелевых группВ отличие от полей действительных и комплексных чисел, теорииполярациональных чиселикольцашимыми.
Наша следующая цельTh( (Z, +,О))иTh( (Q, +,О))-целыхчиселявляютсянеразрепоказать разрешимость теорийсложения целых и рациональных чисел.Гл.312Разрешимые и неразрешимые теории8.Для этого сначала докажем некоторые утверждения, касающиеся произвольных абелевых групп.Пусть НН 1 +а=- абелева группа, Н1 {h + а / h Е Н1 }, где а Е Н,подгруппа Н.
Множество виданазывается, как известно, классом смежности подгруппы Н1 в группе Н. Если хжества классов смежности Н1 в Н, то мощностьмощность мно-min{ х, w}называетсяиндексом Н1 в Ни обозначается через [Н: Н1]. Если индекс [Н: Н1]бесконечен, то пишем [Н: Н1] = оо. Если Н2 - еще одна подгруппав Н, то индекс Н1n Н2в Н1 также будем называть индексом Н2 в Н1и обозначать [Н1: Н2].Лемма8.4.l.Пусть Н-абелева группа, Н1, Н2подгруппы Н.-Тогда+ Н2):а) [(Н1б) [Н1: Н2]Н2]=[Н1: Н2];· [Н: Н1] ;;:: [Н: Н2];в) если а Е Н, то число классов смежности по Н2, имеющихнепустое пересечение с Н1+ а, равноН1:Н2.До к аз ат ель ст в о легко получается из определения индексов.
ОЛемма8.4.2. Пусть Но, ... , Нп ... , an Е А, Но + ао 5,;;;подгруппы некоторой абелевойUгруппы А, ао,Тогда Но+ ао5,;;;U (Hi + ai ).iЕ(Hi+ ai)и [Но:Hn] >п!.\~i~n-1До к аз ат ел ь ст в о.Ко,l~i~nПокажем сначала, что если для подгрупп... , Кт группы А и ао, ... , ат{l, ... ,m}, то включениеЕ А мы имеем [Ко:UKo+aoS,;;;Ki]= оо длявсех(8.3)(Ki+ai)l~i~mне выполняется. Будем доказывать этот факт индукцией по числуразличных подгрупп среди Ко=Коn Km = К*,то(8.3)n К1, ... , Ко n Km.Если Коне выполняется, так как Кобесконечное число классов смежности по К*. Пустьn К1+ аоl= ...
=содержитl > 1 и к; = KinnKo.Случай 1: 1 < [(КоПК1): Ki0 ] < оо для некоторого io Е {2, ... ,m}.Из леммы 8.4.1,а), б) вытекает [Ко: (KfKI0 )]оо. Заменяя в по+следовательности К1,Ki 0 ,на К[+ к;0 ,... , Кт=все подгруппы, совпадающие с К1 илимы уменьшимlи воспользуемся индукционнымпредположением.Случай2:отрицание случаяs= {i I i1.ПустьЕ { 1, ... , т}, Коn Ki = Ко n к 1}.§ 8.4.Разрешимые теории абелевых групп= оо,+ а =!=- Ко n Ki + ai дляТак как [Ко: К1]313то найдется такое а Е Ко+ ао, что Ковсехn К1 +i Е s. Если выполнено (8.3), тоu(Коn Ki + ai),iE{l, ... ,m}\sчто противоречит индукционному предположению.Теперь покажем, что в условиях леммы найдетсяioЕ { 1,...
, п },для которого [Но: Hi0 ] ~ п. Предположим, что это не так. Пустьвсе подгруппы из последовательности Н1,Hi 1 , ••• , Hik -=m <ме 8.4.1, б) [Но: Н*]множество (Но+ ао)име... , Hn,= Hi n ... n Hik.ющие конечный индекс в Но. Пусть Н*По лем1оо. По предположению и лемме 8.4.1, в)n (His + aiJ,где1 ~ s ~ k, содержит менеет/п классов смежности по подгруппе Н*. Следовательно, найдетсяа Е (Но+ ао)\U (Hi + ai),iErгдеr={i1, ... , ik}. ТогдаUHonH* +а~(Hi+ ai)·(8.4)iE{l, ...
,n}\rТак как [(Но n Н*): Hi]= оодля любогоi Е { 1, ... , п} \ r, то (8.4)противоречит факту, установленному в начале доказательства.Докажем теперь утверждение леммы индукцией по п. Для путверждениетривиально,таккакусловиеся. Пусть утверждение верно для п -леммыне1. Так как [Но: Нп][Но: Hi0 ] ~ п, то по лемме 8.4.1,б) [(HonHi0 ): Нп]>индукционному предположению для любого а Е (Но+ ао)имеемu(Hi=1выполняет>п! и(п-1)!.
По\ (Hio+ ai0)+ ai),iE{ l, ... ,n} \ {io,n}Dоткуда получаем утверждение леммы.Дляформулировкижества Х черезмножество АnПIXIAiследующей леммынапомним,что дляобозначается его мощность, и еслиI=мно121, тобудем считать совпадающим с А.iEIЛеммаАо~8.4.3.UПусть Ао,Ai~l,;;;i,;;;n... , An -L(-l)lrliEr·IAonnлil=O.r<;::{1, ... ,n}Доказательство. Пусть Ао(лоnПА)конечные множества. Тогда=1=-121(8.5)iEr={а} и ro~ IAonnлiliEr= {i I а= 1Е Ai}. Тогда(8.6)Гл.314Правая часть(8.5)8.Разрешимые и неразрешимые теориив случае одноэлементного Ао тогда и только тогдаравна нулю, когда имеется одинаковое число четных и нечетныхс условием ( Ао n .n Ai)U Ai.т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
