1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 60
Текст из файла (страница 60)
Числоn называется степенью полинома t иобозначается через дхt или просто дt.Для полиномаDegx tt(x, у)степени= т ;::=:(nf\и числаtim, где О~ m ~ n, положим(у) ~ О /\ ~ tm (у) ~ о) ;m<i~nTmt;::::: tm(y)xmЗаметим, чтоDegx t =т иt+ ... + to(y).=Оформулы со свободными пере--менными из у и не содержат переменную х.Ниже вместо записиDegx t=тбудем писатьDeg t= т.Следующие замечания справедливы для любого полинома1.Формула ( _VDeg t~=О=i)Vt =Отождественно истинна (поскольку каждый полиномtкоэффициентыначиная с некоторого2.Формулаti(Y),t~Оtt.тождественно равен нулю или равны нулю егоi).эквивалентна формуле~ О /\ ((2,Deg t=i)Vt= О)(так как вторая формула получается из первой конъюнктивным добавлением тождественно истинной формулы).§ 8.2. Алгебраически замкнутые поля3.ФормулаDeg t =~ О Лt305О тождественно ложна (поскольку неможет равняться нулю полином нулевой степени с ненулевым коэффициентом4.tto (у)).Формула5.Формула= т Л тmt ~ Оt~ О Лt= О следует t ~ О).t=ОDeg t =~ О Лtэквивалентна формулетt=О(так как изэквивалентна формуле(поскольку для полиномаtс условиемDeg tDeg t == т запись~ О означает, что тmt ~ О).Будем говорить, что формула Ф находится в нормальной форме,если Ф имеет видВсилу приведенных вышезамечаний достаточно показать, чтобескванторной формуле эквивалентна всякая формула Ф, находящаясяв нормальной форме.
Мерой сложности такой формулы Ф будем назыkвать пару(k,l: дfi)-i=IДля сведения меры сложности к минимальному значениюбудем использовать деление с остатком вДляRes(s, t)многочленовЕZ[x, у]s, tЕZ[x, у]=1kZ[x, у].остатокотделенияsнаt,=п,определяется следующим образом. Пусть дsи t = tm(y)xm + ...
+ to(y). Еслиtm(Y) · s - sn(Y) · xn-m · t; заметим,что дD(s, t) < п. Если п < т, то Res(s, t) ;== s; если п ;?; т, тоRes(s, t) ;== Res(D(s, t), t). Заметим, что дRes(s, t) < m и существуютl ~ п - т, h Е Z[x, у] такие, что tm(y) 1 · s = h · t + Res(s, t).дt=тs = sn(y)xnп ;?; т, то полагаемЛемма8.2.2.+ ... + so(y)D(s, t);==Если дt ~ дs, то формулаэквивалентна формулеДо к аз ат ел ь ст в о~ ОЛtDeg t =дt Лt ~ О Л Deg t =Res(s, t) ~ О.дt Лs~ Оочевидно, поскольку при равном нулю делителе равенство нулю делимого равносильно равенству нулю остатка. ОВ силу леммы8.2.2общий случай с формулой Ф, находящейсяв нормальной форме, сводится к формуле со значениемk= 1,и темсамым остается рассмотреть следующие три вида формул:1)2)3)3хf3х~~ О;g ~ О;Deg f =3xf ~ О3х (!~О ЛФормуладf Л ~g~О), где дfэквивалентна>Ои дg> О.бескванторнойформуледff = О V V Deg f =i=li, поскольку в алгебраически замкнутом полеГл.306каждыйРазрешимые и неразрешимые теории8.многочленположительнойстепениимееткорень,адлянулевой степени имеются корни лишь у нулевого многочлена.Формула Зх ~ g ,:::: О эквивалентна формуле ~ gненулевого значенияgчто полиномg= О,так как наличиедля некоторого аргумента х равносильно тому,не является нулевым.Ф ;== Зх (! ~ О/\ Deg f = дf /\ ~g ~ О) придf > О и дg > О эквивалентна формуле зх~ Res(gдf, !) ~ О, которая всвою очередь эквивалентна бескванторной формуле ~(Res(gд{ !)О).Наконец,формула=Действительно, если рассматриваемая формула Ф неверна, то любойкорень многочлена f является корнем многочлена g и с учетом возможной кратности корней многочлен gдf без остатка делится на f, т.
е.Res(gд{ !)О. Обратно, если gдf без остатка делится на f, то любойкорень для f является корнем для g и ни для какого х одновременноне выполнятся условия f = О и g i- О.D=Обратимся к вопросу об истинности бескванторных предложенийсигнатуры а! в алгебраически замкнутых полях.Пусть Рмножество всех простых чисел, Р* ;== {О} U Р--множество всех возможных характеристик полей.Для любой характеристики х Е Р* пустьное) поле характеристики хFp= Z/pZ -(Fo;== Q -Fx -простое (минимальполе рациональных чисел,поле из р элементов для р ЕР).Пусть То-множество всех термов сигнатуры а1 , не имеющихвхождений переменных.Определим индукцией отображение ах: То--+Fx (= (Fx,Ox, lx,+х, -х, ·х)) для всех х ЕР*.
Полагаемах(О) ;== Ох,ax(to + t,);==ax(to) +х ax(t1),ax(to - t,);==ax(to)ax(to · t,);==ax(to)·x ax(t,).Заметим, что если р Е Р и ер :колец, то ар=Z--+-хFp -ax(t1),естественный эпиморфизмЕрао.Из определения следует, чтолеax(l) ;== lx,ax(t) = tFx -значение термаtв поFx.Замечаниех ЕР* полеПусть Ф8.2.3. Для любых терма t Е То и поля F характеристикиF содержит подполе, изоморфное Fx, и tF = tFx = ax(t).-атомарное предложение сигнатуры а!. Не уменьшаяобщности, можно считать, что Ф имеет видtЕ То.t~ О для подходящего§ 8.2.Алгебраически замкнутые поля307IПолагаем 0(Ф)(= 0(t ::::! О))~ {х х ЕР*, ax(t) = О}.
Имеет месторавенство 0(Ф) = {х I х ЕР*, ao(t) Е х · Z}. Заметим, что последнеемножество совпадает с множеством всех простых делителей числаao(t),еслиao(t)=f=. О, и с множеством Р*, еслиИз определения множества0( Ф)ao(t) =О.видно, что для любого поляFхарактеристики х справедливы эквивалентностиFFФ~ tF=О~ х Е 0( Ф ).Для любого бескванторного предложения Ф сигнатуры IJ" f, не со--,держащего знакаимпликации,определим по индукции множество0(Ф) ~ Р* так:i)если Фатомарное предложение, то 0(Ф) уже определено выше;-ii) если Ф = Ф 0 л Ф1, то 0(Ф) = 0(Фо) n 0(Ф1);iii) если Ф = Фо V Ф1, то 0(Ф) = 0(Фо) U 0(Ф1);iv) если Ф=~Фо, то 0(Ф)=Р*\0(Фо).Из определения видно, что по предложению Ф и характеристикех ЕР* можно эффективно узнать, будет лих принадлежать множеству0(Ф) и будет ли справедливо равенство 0(Ф)Замечание8.2.4.=Р*.Нетрудно проверить, что для любого бескванторного предложения Ф сигнатуры IJ" f одно из множествявляется конечным, 0(Ф)n 0(~Ф) = !ZJ,0(Ф) U 0СФ)0( Ф)= Р*,и 0(~Ф)и если 0(Ф)бесконечно, то О Е 0(Ф).Используя определение множества 0(Ф), индукцией по длине предложенияФбезтрудаустанавливаетсясправедливостьследующегопредложения.Предложениенатуры IJ"J,F -Пусть Ф8.2.5.-бескванторное предложение сигполе характеристики х ЕР*.
Тогда имеет местоэквивалентностьFFФ~ ХЕ 0(Ф).Важнейшим следствием этого предложения и свойства элиминациикванторов для теории алгебраически замкнутых полей являетсяТеорема8.2.6. 1).Теория АЗП всех алгебраически замкнутыхполей разрешима.2). Для любой характеристики х Е Р* теория АЗПх алгебраически замкнутых полей характеристики х полна и разрешима.Доказательство.1). Пусть Ф -предложение сигнатуры IJ"J·Эффективно находим бескванторное предложение Фотакое, что Ф= АзпФо.сигнатуры IJ" fДалее, эффективно проверяем, справедливо лиГл.
В. Разрешимые и неразрешимые теории308равенство 0(Фо)= Р*.Если 0(Фо)= Р*,то Фо (и Ф) принадлежит АЗП,а если 0(Фо)=1- Р., то Фо, Ф (j. АЗП.2). Пусть Фо - эффективно найденное бескванторное предложениесигнатуры 1Jf, соответствующее предложению Ф как выше. Тогда имеетuместо Ф Е АЗПх {=се? х Е 0(Фо). Так как 0(Фо)е(~Фо) = Р*, то Ф ЕЕ АЗПх или ~Ф Е АЗПх. Отсюда и следует заключение 2).ОВ силу теоремы(С,+,·, О,1)8.2.6,в частности, элементарная теория АЗПо полякомплексных чисел разрешима.Упражнение1.Для каждой характеристики х доказать разрешимость теорииалгебраически замкнутых полей характеристики х без использования элиминации кванторов.
(Указание. Воспользоваться категоричностью данных теорий в несчетных мощностях.)§ 8.3.Элиминация кванторов и разрешимость теориивещественно замкнутых полейУстановим сначала следующее утверждение.Предложение8.3.1.Элементарная теория ПЛП плотных линейных порядков без наименьшего и наибольшего элемента (см. пример3.1.6)разрешима.До к аз ат ель ст в о.По предложению3.1. 75.6.1rорична, следовательно, по предложениютеория ПЛП w-катеона полна. Так какПЛП имеет конечное множество аксиом, то по предложениюперечислима. Предложение7.5.9дает разрешимость ПЛП.7.5.8онаОТеория ПЛП, разрешимость которой установлена в предложении8.3.1,совпадает сTh((R, ~)),гдеR -множество действительныхчисел.
Имеется, однако, значительно более сильный результат: теорияTh( (R, +, ·.<,О, 1))разрешима. Для доказательства этой теоремы намбудут нужны некоторые общие факты.Предложение8.3.2.Пусть элементарная теория Т имеет покрайней мере одну константу в сигнатуре. Тогда следующие условия эквивалентны:l)в Т имеется элиминация кванторов;2) для любой модели Ql теории Т, любой w-насыщенной (см.§5.5)модели S:В теории Т, любых а,,изоморфного вложения ер подсистемы...
,ап,Ь Е АQl(a,, ... ,an)и любого(см.§3.1)в S:В найдется продолжение ер до изоморфного вложения ер'подсистемыs.2l(a1, ... , ап, Ь)в S:В.Вещественно замкнутые поля§ 8.3.Доказательство.~. ~. а1, ... , ап,V=Ь и1)как вr.p,{Ф(x,r.pa1, ... ,r.pan)Для доказательства2)2). Пусть выполнено 1) и выбраны==}2).309Рассмотрим множество1~ F Ф(Ь,а1, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
